Iterator, Collection, and Map
credit for this assignment: Ben Choi and Dennis Cosgrove
Contents
Motivation
We gain experience with interfaces and classes. In addition we will deal with generic types.
We implement our own Iterator, Collection, and Map @NotThreadSafe classes. Later in the semester we will implement a @ThreadSafe version of a Map.
In the creation of our Map class, we will gain experience with hashing which we will leverage throughout the semester.
Java Advice
Parameterized Type Array Tip
Creating arrays of parameterized types in Java is madness inducing. Some details are available in Java Generics Restrictions.
The example below creates an array of List<String>. The @SuppressWarnings annotation is optional.
@SuppressWarnings("unchecked")
List<String>[] result = new List[length];
Background
Java Util Documentation
VisuAlgo
Related Videos
Mistakes To Avoid
 Warning: Do NOT use == when comparing Objects (except when comparing to null). Use Objects.equals(a,b). |
| Warning: Do NOT use % which can return a negative number. Use Math.floorMod(x,y). |
| Warning: Do NOT parallelize. |
| Warning: Do NOT simply remove and add for put on a Map. Look for the entry and set its value if you find it. Otherwise add it. |
Code to Implement
To be an Iterable object a class must implement all of the abstract methods on Iterable. There happens to be only 1:
Iterator<T> iterator()
When you have an instance of Iterable you can then obviously invoke the iterator() method, then loop over the resulting iterator to process the elements in the Iterable:
private static void printAllViaIterator(Iterable<String> iterable) {
Iterator<String> iterator = iterable.iterator();
while(iterator.hasNext()) {
String element = iterator.next();
System.out.println(element);
}
}
As a bit of sweet syntactic sugar, any Iterable can be used in a for-each loop:
private static void printAllViaForEach(Iterable<String> iterable) {
for (String element : iterable) {
System.out.println(element);
}
}
Any class that implements Iterable must implement the iterator() method. A Collection isa Iterable. The interface Collection extends the interface Iterable. To be an Iterable
List<String> states = new LinkedList<>();
states.add("Delaware");
states.add("Idaho");
states.add("Alaska");
printAllViaIterator(states);
printAllViaForEach(states);
 Tip: It is good practice to declare variables, parameters, and fields to be of the least specific type possible (but no less specific :). This is commonly an interface. |
| Warning: A common mistake we see is students attempting to create an instance of an interface when they need to create an instance of a class (e.g. List<String> states = new LinkedList<>();). |
LinkedCollection
The most notable subinterface of Iterable is Collection. Collection in turn has often used subiterfaces List, Set, and Queue.
The class and interface heirarchy doc has the complete tree for the java.util package.
As part of this lab you will implement LinkedCollection, an abstract data type which extends the AbstractCollection in the java.util package. It would be nice if this lab could be more open ended. Experience has led us to force students to build a specific design. Hopefully that can change in future semesters. For now, keep track of the head and the tail DoublyLinkedNodes as well as the current size of the collection in instance variables (fields).
| class: | LinkedCollection.java |  |
| methods: | iterator size add |
|
| package: | util.lab.collection | |
| source folder: | student/src/main/java |
Since your class will implement Collection<E>, it must meet the specification of that interface. The links to the javadocs are provided for the details of each methods spec.
iterator()
method: public Iterator<E> iterator() 
(sequential implementation only)
size()
method: public int size() (sequential implementation only)
add(item)
method: public boolean add(E item) (sequential implementation only)
We will be creating our own implementation of Collection class LinkedCollection. Like many of the Collections you may have used in the past (e.g. LinkedList, HashSet) we will inherit functionality from AbstractCollection. In fact, we will only need to implement three of the public methods: size(), iterator(), and add(). The bulk of AbstractCollection's implementation relies on our correct implementation of iterator().
Correctly implementing size() should be trivial. Just be sure to increment and decrement size when adding or removing elements respectively.
| Warning: remove is achieved via the iterator. Be sure to keep the Collection up to date by invoking decrementSize(). |
add() will want to use the provided class DoublyLinkedNode<E>. Simply insert new elements in at the tail of your collection as deque.offerLast(element) does.
Providing the required iterator() method will in turn require us to build #LinkedIterator.
Note: The “head” is a sentinel node, meaning its sole purpose is to point its next reference to the true first node of the list. Having this empty node at the front might seem wasteful, however it makes everything's implementation (especially the Iterator> much more straightforward.
Empty
Collection<String> collection = new LinkedCollection<>();
would result in this data structure:
A
Collection<String> collection = new LinkedCollection<>();
collection.add("A");
would result in this data structure:
AB
Collection<String> collection = new LinkedCollection<>();
collection.add("A");
collection.add("B");
would result in this data structure:
ABC
Collection<String> collection = new LinkedCollection<>();
collection.add("A");
collection.add("B");
collection.add("C");
would result in this data structure:
LinkedIterator
| class: | LinkedIterator.java | |
| methods: | constructor hasNext next remove |
|
| package: | util.lab.collection | |
| source folder: | student/src/main/java |
LinkedIterator(head, tailUpdater, sizeDecrementer)
method: public LinkedIterator(DoublyLinkedNode<E> head, Consumer<DoublyLinkedNode<E>> tailUpdater, Runnable sizeDecrementer) (sequential implementation only)
head is the head of the list.
tailUpdater is used as callback to indicate that remove has changed the tail of the list (that is: the last element was successfully removed).
sizeDecrementer is used as callback to indicate that remove has successfully removed any node.
You will want to keep track of these three parameters in private instance variables.
The parameter head should be assigned to the current node instance variable which updates as you march through the LinkedCollection.
Further, the tailUpdater and sizeDecrementer instance variables should be declared final as they will never change.
An additional instance variable which tracks when remove is and is not valid is strongly recommended.
Since your class will implement Iterator<E>, it must meet the specification of that interface. The links to the javadocs are provided for the details of each methods spec.
hasNext() and next()
method: public boolean hasNext() (sequential implementation only)
method: public E next() (sequential implementation only)
| Warning: The iterator should start at the head (sentinel) node. |
State of the Iterator When next() Would Return A
State of the Iterator When next() Would Return B
State of the Iterator When next() Would Return C
State of the Iterator When next() Would Throw NoSuchElementException
Check out the docs for next() of when to throw NoSuchElementException and remove() for when to throw IllegalStateException. Think of edge cases like when the collection is empty or when the iterator tries to remove the sentinel node.
Iterator<Integer> iterator = collection.iterator();
if(iterator.hasNext()==false) {
iterator.next(); // NOTE: should throw NoSuchElementException
}
remove()
method: public void remove() (sequential implementation only)
note: you must invoke sizeDecrementer's run method when a node is successfully removed.
note: you must invoke tailUpdater's accept method with the new tail when the tail node is successfully removed.
State of the Iterator When next() Would Return C (i.e. just returned B)
note: this is the same diagram from above.
State of the Iterator When next() Would Return C (i.e. just returned B) Then remove() Was Invoked
Attempting to remove before next() is invoked at all should throw IllegalStateException:
Iterator<Integer> iterator = collection.iterator(); iterator.remove(); // NOTE: should throw IllegalStateException
Further, any attempt to remove twice without calling next() in between should throw IllegalStateException:
Iterator<Integer> iterator = collection.iterator(); iterator.next(); iterator.remove(); iterator.remove(); // NOTE: should throw IllegalStateException
Iterator<Integer> iterator = collection.iterator(); iterator.next(); iterator.next(); iterator.remove(); iterator.remove(); // NOTE: should throw IllegalStateException
Iterator<Integer> iterator = collection.iterator(); iterator.next(); iterator.next(); iterator.next(); iterator.remove(); iterator.remove(); // NOTE: should throw IllegalStateException
BucketsHashMap
How to use Maps in Java:
How to build a hash table:
You will most likely want to complete your Collection and Iterator implementations before moving on to the Map implementations as they will be built with them.
A Map (also sometimes referred to as a Dictionary or a Hashtable) is an abstract data structure which has the capabilities of associating a value with a key: map.put(key, value), looking up the associated value with a key: map.get(key), and removing map.remove(key).
The standard Java Collections Framework Map provides a number of other nice methods, but put, get, and remove are the core of any Map in any programming language.
Since your class will implement Map<K,V>, it must meet the specification of that interface. The links to the javadocs are provided for the details of each methods spec.
| class: | BucketsHashMap.java | |
| methods: | constructor getBucketIndex getBucketFor size put remove get |
|
| package: | util.lab.map | |
| source folder: | student/src/main/java |
method: public BucketsHashMap(int capacity, Supplier<Collection<Entry<K, V>>> collectionSupplier) (sequential implementation only)
Implementing the constructor has a couple of tricky parts.
First, you will encounter a much dreaded problem in Java. One cannot instantiate a new generic array. While there is a reason for this limitation, it is still frustrating.
So while you might think you should enter:
buckets = new Collection<Entry<K, V>>[capacity]; // NOTE: this will not compile
the error reported says it all "Cannot create a generic array of Collection<Map.Entry<K,V>>".
You must instead create the array without the generic type parameter:
buckets = new Collection[capacity];
This results in a warning which the @SuppressWarnings("unchecked") annotation we added to the constructor takes care of.
Second, there what to make of the collectionSupplier parameter. When creating a bucket for each slot in the array you should invoke the collectionSupplier's get() method instead of say... creating an instance of your LinkedCollection or a java.util.LinkedList.
getBucketIndex(key)
method: private int getBucketIndex(Object key) (sequential implementation only)
For a given key return the index into the array of buckets. The correct implementation should leverage the key's hash code to generate a valid index of the bucket array.
getBucketFor(key)
method: private Collection<Entry<K, V>> getBucketFor(Object key) (sequential implementation only)
getBucketIndex(key) returns the index. getBucketFor(key) returns the bucket at that index.
size()
method: public int size() (sequential implementation only)
put(key, value)
method: public V put(K key, V value) (sequential implementation only)
| Warning:Note the specification of the return value. |
remove(key)
method: public V remove(Object key) (sequential implementation only)
For an efficient solution (and to avoid a possible ConcurrentModificationException) you will want to use the bucket's iterator directly and leverage its remove method.
get(key)
method: public V get(Object key) (sequential implementation only)
The standard interface for a key value pair is Map's Entry with the critical methods:
- K getKey()
- V getValue()
- V setValue(V value)
We have provided an implementation of Entry for you called KeyMutableValuePair<K,V>.
BucketsHashMap will use an entry’s key to place an entry into one of several buckets.
If you have not taken CSE 247, this might not make as much sense. In short, these buckets exist to cut down the runtime of searching for entries within the map, as it is much quicker to search 1/total number of buckets than one large bucket which contains every entry.
In this class, you will use the entry’s key’s hashcode to determine which of the buckets it should fall into. In order to calculate the index of the bucket that the entry belongs in, we will make use of the hash function, which in turn uses Math.floorMod to calculate a modulo (remainder or % in Java) based on the number of buckets and the key’s hashcode. We will also make use of the getListFor method, which utilizes the hash method in order to return a pointer to the correct bucket.
reference material: Concept of Hashing
| Warning: Do NOT implement put as a remove followed by an add. While correct, it is undesirable. First look for the key and set its value if you find it before resorting to adding a new entry when you cannot find a previous entry with the key. |
Testing Your Solution
Correctness
Throughout the process, refer to the associated tests to check your progress. Feel free to run tests individually depending on which method you are working on or run the test suite in order to run every test in the associated package.
| class: | UtilTestSuite.java |  |
| package: | util.lab | |
| source folder: | testing/src/test/java |
Rubric
As always, please make sure to cite your work appropriately.
Total points: 100
LinkedIterator subtotal: 25
- Correct hasNext and next (10)
- Correct remove (15)
LinkedCollection subtotal: 20
- Correct constructor (2.5)
- Correct iterator (5)
- Correct size (2.5)
- Correct add (10)
BucketsHashMap subtotal: 45
- Correct constructor (2.5)
- Correct getBucketIndex (2.5)
- Correct getBucketFor (2.5)
- Correct size (2.5)
- Correct put (15)
- Correct remove (10)
- Correct get (10)
Whole project:
- Clarity and efficiency (10)
