Java offers built-in support for custom iteration via the Iterable and Iterator interfaces. An interface in Java is essentially a contract stating a class will implement specific methods, but does not detail the implementation details.
The Java Iterable interface requires the class implementing it has a publicly available iterator() method that returns an Iterator object:
public class Items<Item> implements Iterable<Item> {
public Iterator<Item> iterator() {
return new ThingsIterator<Item>();
}
}The Iterator interface requires the class implementing it have the following methods: hasNext(), next(), and remove(). To expand on the above Items class, adding an class to Items that implements the Iterator interface is one way to go about it.
private class ThingsIterator<Item> implements Iterator<Item> {
public boolean hasNext() { ... }
public Item next() { ... }
public void remove() { ... }
}hasNext will return a boolean, determining if there is a next item in the data structure. hasNext is called by the next method to determine whether to return an item in the collection if it’s available. Otherwise throw a NoSuchElementException.
Implementing remove is optional; throwing a UnsupportedOperationException() is advisable if the class does not require it.
Using Iterable allows you to write custom collections hidden behind an abstract data type - the client does not have to know how the collection is implemented, all it needs to know is it can iterate over a collection provided by the instance of the iterable implemented class.
For instance, if I have an iterable abstract data type called Things that uses an array or linked list to represent its internal collection, the client only cares about being able to use a for-loop on that collection.
Writing custom iterators is requisite for the Algorithms Stacks, Queues, and Bags assignment. Coding up a Deque and RandomQueue requires the following:
Deque Requirements
public class Deque<Item> implements Iterable<Item> {
public Deque() // construct an empty deque
public boolean isEmpty() // is the deque empty?
public int size() // return the number of items on the deque
public void addFirst(Item item) // add the item to the front
public void addLast(Item item) // add the item to the end
public Item removeFirst() // remove and return the item from the front
public Item removeLast() // remove and return the item from the end
public Iterator<Item> iterator() // return an iterator over items in order from front to end
public static void main(String[] args) // unit testing (optional)
}Performance requirements. Your deque implementation must support each deque operation in constant worst-case time. A deque containing n items must use at most 48n + 192 bytes of memory. and use space proportional to the number of items currently in the deque. Additionally, your iterator implementation must support each operation (including construction) in constant worst-case time.
RandomizedQueue Requirements
public class RandomizedQueue<Item> implements Iterable<Item> {
public RandomizedQueue() // construct an empty randomized queue
public boolean isEmpty() // is the queue empty?
public int size() // return the number of items on the queue
public void enqueue(Item item) // add the item
public Item dequeue() // remove and return a random item
public Item sample() // return (but do not remove) a random item
public Iterator<Item> iterator() // return an independent iterator over items in random order
public static void main(String[] args) // unit testing (optional)
}Performance requirements. Your randomized queue implementation must support each randomized queue operation (besides creating an iterator) in constant amortized time. That is, any sequence of m randomized queue operations (starting from an empty queue) should take at most cm steps in the worst case, for some constant c. A randomized queue containing n items must use at most 48n + 192 bytes of memory. Additionally, your iterator implementation must support operations next() and hasNext() in constant worst-case time; and construction in linear time; you may (and will need to) use a linear amount of extra memory per iterator.
Deque and RandomizedQueue required different iterator implementations. Why? Because they used different data structures.
Deque Iterator Implementation
I implemented Deque using a doubly linked list data structure because all non-iterative operations had to be implemented with constant worst-case time, which is not acheivable with an array when adding or removing an item to/from index 0; the rest of the items in the array have to be shifted back or forward one slot, which takes linear time.
Using a doubly linked list runs constant time for the non-iterative operations because the Deque keeps track of the first and last nodes in the list, and updates those values accordingly when the non-iterative operations are executed.
Here’s how the Deque implements custom iteration. The example omits non-iterative methods for brevity.
public class Deque<Item> implements Iterable<Item> {
private Node first;
private Node last;
private int count;
private class Node {
private Item item;
private Node next;
private Node previous;
}
private class ListIterator implements Iterator<Item> {
private Node current = first;
public boolean hasNext() {
return current != null;
}
public Item next() {
if (!hasNext()) throw new NoSuchElementException();
Item item = current.item;
current = current.next;
return item;
}
public void remove() { throw new UnsupportedOperationException(); }
}
public Iterator<Item> iterator() { return new ListIterator(); }
// non-iterative methods...
}RandomizedQueue Iterator Implementation
Implementing a RandomizedQueue used an array as it’s data structure. This was needed because retrieving items from the array had to be at random and in constant amortized time. The reason it’s amortized is to take into account array resizing procedures, which essentially copies the current array to a new, larger or smaller sized array when the contents don’t fit within a desired threshold.
The RandomizedQueue example omits non-iterative methods for brevity.
public class RandomizedQueue<Item> implements Iterable<Item> {
private Item[] arr = (Item[]) new Object[1];
private int count;
private class RandomIter implements Iterator<Item> {
private int current = 0;
private Item[] iterArr;
public RandomIter() {
iterArr = (Item[]) new Object[count];
for (int i = 0; i < count; i++) {
iterArr[i] = arr[i];
}
StdRandom.shuffle(iterArr); // Knuth shuffle
}
public boolean hasNext() {
if (iterArr.length > current && iterArr[current] != null) return true;
return false;
}
public Item next() {
if (!hasNext()) throw new NoSuchElementException();
return iterArr[current++];
}
public void remove() { throw new UnsupportedOperationException(); }
}
public Iterator<Item> iterator() { return new RandomIter(); }
// non-iterative methods...
}The broad strokes of the above iterator implementation: create a new array that belongs to the iterator inner class and copy over the values of RandomizedQueue. Copying the RandomizedQueue array to iterArr is necessary as shuffling it would break behavior related to enqueuing and dequeuing. hasNext() checks the current index current does not go out of bounds. next() returns the current index item.