Java's Iterable Interface
Java offers built-in support for custom iteration via the
Iterator interfaces. An interface in Java is essentially a contract stating a class will implement specific methods, but does not detail the implementation details.
Iterable interface requires the class implementing it has a publicly available
iterator() method that returns an
1 2 3 4 5
Iterator interface requires the class implementing it have the following methods:
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.
1 2 3 4 5
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
remove is optional; throwing a
UnsupportedOperationException() is advisable if the class does not require it.
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:
1 2 3 4 5 6 7 8 9 10 11
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.
1 2 3 4 5 6 7 8 9 10
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.
RandomizedQueue required different iterator implementations. Why? Because they used different data structures.
Deque Iterator Implementation
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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
RandomizedQueue Iterator Implementation
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.
RandomizedQueue example omits non-iterative methods for brevity.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
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.