Been looking at TreeMap's implementation rather closely and observed
something I don't understand. %-)
TreeMap (as of JDK 6 and later) implements NavigableMap. NavigableMap
requires an implementation of a navigableKeySet() method which returns a
NavigableSet<K>. So, in TreeMap I see:
public NavigableSet<K> navigableKeySet()
Then, the NavigableSet interface has an Iterator<E> descendingIterator()
and Iterator<E>iterator(). The former returns an iterator over the
elements in descending order. The latter in ascending order.
I also noticed in TreeMap, NavigableMap requires an implementation of a
descendingKeySet(), i.e. public NavigableSet<K> descendingKeySet().
Again, the NavigableSet interface has an Iterator<E>
descendingIterator() and iterator() as described above.
When I populate a TreeMap with some dummy data, let's say I populate it
with 15 Integer keys and String's representing those Integer keys as
values, I observe something I don't understand when using the
navigableKeySet().descendingIterator().
When, I try to iterate over the returned NavigableKeySet, I see the
lowest key printed and that's it. Nothing else prints. From looking at
the JavaDoc for TreeMap and NavigableSet, this doesn't seem right.
Shouldn't it iterate over the entire set in descending order? I looked
at the source and it creates an Iterator that starts at the lowest key
and then tries to find the next lowest key (which obviously doesn't
exist). Am I not reading something right in the JavaDoc?
When iterating using navigableKeySet().iterator() I see all 15 keys
printed in ascending order, (as expected).
When I iterate with descendingKeySet().descendingIterator() I see the 15
keys printed in ascending order, (as expected since descending set
followed by a descending iterator should give me ascending order).
When iterating using descendingKeySet().iterator, I see the 15 keys
printed in descending order, (as expected).
I've attached a very simple program that illustrates what I'm describing.
Could someone clarify this behavior?
thanks,
charlie ...
import java.util.Iterator;
import java.util.NavigableMap;
import java.util.TreeMap;
public class TestTreeMap {
private NavigableMap<Integer, String> tm;
private void populateTreeMap(int numberOfEntries) {
tm = new TreeMap<Integer, String>();
StringBuilder sb = new StringBuilder();
int start = 5;
for (int i = 1; i <= numberOfEntries; i++) {
sb.setLength(0);
int key = start * i;
sb.append("Value stored is -> ").append(key);
tm.put(key, sb.toString());
}
}
private void iterateKeysAndPrint() {
System.out.println("Printing TreeMap keys using TreeMap.keySet().iterator()");
Iterator<Integer> itr = tm.keySet().iterator();
while (itr.hasNext()) {
System.out.println("Key -> " + itr.next());
}
System.out.println("\n");
}
private void iterateKeysNavigableKeySetAndPrint() {
System.out.println("Printing TreeMap keys using TreeMap.navigableKeySet().iterator()");
Iterator<Integer> itr = tm.navigableKeySet().iterator();
while (itr.hasNext()) {
System.out.println("Key -> " + itr.next());
}
System.out.println("\n");
}
private void iterateDescendingKeysNavigableKeySetAndPrint() {
System.out.println("Printing TreeMap keys using TreeMap.navigableKeySet().descendingIterator()");
Iterator<Integer> itr = tm.navigableKeySet().descendingIterator();
while (itr.hasNext()) {
System.out.println("Key -> " + itr.next());
}
System.out.println("\n");
}
private void iterateDescendingKeysDescendingKeySetAndPrint() {
System.out.println("Printing TreeMap keys using TreeMap.descendingKeySet().descendingIterator()");
Iterator<Integer> itr = tm.descendingKeySet().descendingIterator();
while (itr.hasNext()) {
System.out.println("Key -> " + itr.next());
}
System.out.println("\n");
}
private void iterateKeysDescendingKeySetAndPrint() {
System.out.println("Printing TreeMap keys using TreeMap.descendingKeySet().iterator()");
Iterator<Integer> itr = tm.descendingKeySet().iterator();
while (itr.hasNext()) {
System.out.println("Key -> " + itr.next());
}
System.out.println("\n");
}
public static void main(String[] args) {
TestTreeMap ttm = new TestTreeMap();
ttm.populateTreeMap(15);
ttm.iterateKeysAndPrint();
ttm.iterateKeysNavigableKeySetAndPrint();
ttm.iterateDescendingKeysNavigableKeySetAndPrint();
ttm.iterateDescendingKeysDescendingKeySetAndPrint();
ttm.iterateKeysDescendingKeySetAndPrint();
}
}
