iterator

Class RandomizedQueue<Item>

java.lang.Object

iterator.RandomizedQueue<Item>

All Implemented Interfaces:

java.lang.Iterable<Item>

public class RandomizedQueue<Item>
extends java.lang.Object
implements java.lang.Iterable<Item>

Written: 11/16/2017 Last updated: 11/16/2017

Requirement: Class must be in iterator package and exercises.* must be imported.

Javadoc: javadoc -author -version -private -classpath ./algs4_sts.jar; -d .\javadoc RandomizedQueue.java

Single Compilation: javac -cp .;algs4_sts.jar; RandomizedQueue.java

Execution 1: java -cp ../;.;algs4_sts.jar; iterator.RandomizedQueue < distinct.txt

Execution 2: java -cp ../;.;algs4_sts.jar; iterator.RandomizedQueue < duplicates.txt

Summary: RandomizedQueue is an abstract data type that implements the functions of a queue. However, the items manipulated by queue operations will be random. Since order is not a concern, but random data access is an array is the best choice to implement the RandomQueue. The program will read from a file, perform the basic RandomizedQueue operations and print the queue to screen using an iterator.

Note: The RandomizedQueue application is ran from a client (Percolation.java).

Files: The files contain a series of strings, seperated by spaces.

Version:

1.7

Author:

Tony Lockhart

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
class	RandomizedQueue.iteratorLoop Iterator Class contains hasNext() and next() methods, which are used to instantiate an iterator object.

Field Summary

Fields

Modifier and Type	Field and Description
private int	arraySize The size of the input array
private Item[]	input The input array contains the data read from the external file and manipulated.
private int	randomArrayCapacity The number of elements the randonIndexArray can hold.
private Item[]	randomIndexArray The array that holds the number of index values to be returned from the input array.
private int	totalItems The total number of filled (data added) nodes in the array.

Constructor Summary

Constructors

Constructor and Description
RandomizedQueue() Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
Item	dequeue() Selects a random index in the array, switches the value with the end index, before deleting the end index.
void	enqueue(Item item) Adds generic item to the end of the queue.
void	exch(int i) Exchanges the value of a random integer with the last index value in the input array.
Item[]	getInput() Returns a reference to the input Array.
Item	getRandomDefaultValue() Return the default array value -1 as an Item to be stored in randomIndexArray
Item[]	getRandomIndexArray() Returns a reference to the randomIndex Array.
boolean	isEmpty() Returns value indicating if the randomized queue is empty.
java.util.Iterator<Item>	iterator() The iterator method returns an object of the iterator class iteratorLoop
void	loop(RandomizedQueue<Item> dq) loop iterates through the queue and prints out all the items in the list.
static void	main(java.lang.String[] args)
void	print(Item[] input) Prints the queue without an iterator.
java.lang.Integer	RandomIndex() Returns a random index from the input array.
void	resizeArray(int newSize) Doubles the size of the input array when the end is reached.
Item	sample() Returns a random item (but do not remove it)
void	setRandomIndex(int capacity) Declares the size of the randomIndexArray.
void	shuffle(Item[] item) Shuffles the location of the generic item added.
int	size() Returns the number of elements (filled) in the inputArray.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

arraySize

private int arraySize

The size of the input array

randomIndexArray

private Item[] randomIndexArray

The array that holds the number of index values to be returned from the input array.

randomArrayCapacity

private int randomArrayCapacity

The number of elements the randonIndexArray can hold. Entered from command prompt.

input

private Item[] input

The input array contains the data read from the external file and manipulated. Since Item is a generic placeholder, it will be reduced to an object at runtime. It can not be referenced by a static method, therefore, all methods are non-static.

totalItems

private int totalItems

The total number of filled (data added) nodes in the array.

Constructor Detail

RandomizedQueue

public RandomizedQueue()

Constructor.

Method Detail

isEmpty

public boolean isEmpty()

Returns value indicating if the randomized queue is empty.

setRandomIndex

public void setRandomIndex(int capacity)

Declares the size of the randomIndexArray.

Parameters:

capacity - The size of array entered via command line.

getRandomIndexArray

public Item[] getRandomIndexArray()

Returns a reference to the randomIndex Array.

getInput

public Item[] getInput()

Returns a reference to the input Array.

size

public int size()

Returns the number of elements (filled) in the inputArray.

iterator

public java.util.Iterator<Item> iterator()

The iterator method returns an object of the iterator class iteratorLoop

Specified by:

iterator in interface java.lang.Iterable<Item>

loop

public void loop(RandomizedQueue<Item> dq)

loop iterates through the queue and prints out all the items in the list.

Parameters:

dq - A reference to a deque object.

getRandomDefaultValue

public Item getRandomDefaultValue()

Return the default array value -1 as an Item to be stored in randomIndexArray

sample

public Item sample()

Returns a random item (but do not remove it)

enqueue

public void enqueue(Item item)

Adds generic item to the end of the queue.

Parameters:

item - The generic item to be added to the queue.

resizeArray

public void resizeArray(int newSize)

Doubles the size of the input array when the end is reached.

Parameters:

newSize - the size of the new array.

print

public void print(Item[] input)

Prints the queue without an iterator.

shuffle

public void shuffle(Item[] item)

Shuffles the location of the generic item added.

dequeue

public Item dequeue()

Selects a random index in the array, switches the value with the end index, before deleting the end index.

RandomIndex

public java.lang.Integer RandomIndex()

Returns a random index from the input array. Since generics compile to Objects, the elements (randomIndex) in the Object array (randomIndexArray) must be returned as Integers, not ints. Because an object can be casted to an Integer (see permutations.java). Otherwise conversion methods woulds be required (.intValue() or new Integer(i);).

exch

public void exch(int i)

Exchanges the value of a random integer with the last index value in the input array.

Parameters:

i - random array index value to be exchanged.

main

public static void main(java.lang.String[] args)