TreeMap.navigableKeySet().descendingIterator() sequence ?

[Martin Buchholz]

Below is the proposed patch.

We had alredy been testing
m.descendingKeySet().iterator()
but not the equivalent
m.navigableKeySet().descendingIterator()
which goes down a different code path.

To get this into the JDK, we will need:

1. Review from Doug (or some other person empowered to do so)

2. Bug creation from Charlie (or some other person empowered to do so)
I suggest making this bug P2-S2.

I will need the bug id and synopsis to create the proper mercurial comment.

3. Someone at Sun will need to backport this to JDK 6.
It's time to appoint a Sun engineer to the Collections/Concurrency area
for tasks such as this.

(I would have used webrev if that was publically available, and there was a
place to store it)

The added tests are rather more than strictly necessary to expose the bug,
but that's no defect.

diff --git a/src/share/classes/java/util/TreeMap.java
b/src/share/classes/java/util/TreeMap.java
--- a/src/share/classes/java/util/TreeMap.java
+++ b/src/share/classes/java/util/TreeMap.java
@@ -1021,7 +1021,7 @@ public class TreeMap<K,V>
     }

     Iterator<K> descendingKeyIterator() {
-        return new DescendingKeyIterator(getFirstEntry());
+        return new DescendingKeyIterator(getLastEntry());
     }

     static final class KeySet<E> extends AbstractSet<E> implements
NavigableSet<E> {
diff --git a/test/java/util/Collection/MOAT.java
b/test/java/util/Collection/MOAT.java
--- a/test/java/util/Collection/MOAT.java
+++ b/test/java/util/Collection/MOAT.java
@@ -155,7 +155,7 @@ public class MOAT {
         check(c.containsAll(new ArrayList<Integer>()));
     }

-    private static void testEmptyCollection(Collection<?> c) {
+    private static <T> void testEmptyCollection(Collection<T> c) {
         check(c.isEmpty());
         equal(c.size(), 0);
         equal(c.toString(),"[]");
@@ -165,6 +165,23 @@ public class MOAT {
         Object[] a = new Object[1]; a[0] = Boolean.TRUE;
         equal(c.toArray(a), a);
         equal(a[0], null);
+        testEmptyIterator(c.iterator());
+    }
+
+    static <T> void testEmptyIterator(final Iterator<T> it) {
+        if (rnd.nextBoolean())
+            check(! it.hasNext());
+
+        THROWS(NoSuchElementException.class,
+               new Fun(){void f(){ it.next(); }});
+
+        try { it.remove(); }
+        catch (IllegalStateException _) { pass(); }
+        catch (UnsupportedOperationException _) { pass(); }
+        catch (Throwable t) { unexpected(t); }
+
+        if (rnd.nextBoolean())
+            check(! it.hasNext());
     }

     private static void testEmptyList(List<?> c) {
@@ -173,10 +190,12 @@ public class MOAT {
         equal2(c, Collections.<Integer>emptyList());
     }

-    private static void testEmptySet(Set<?> c) {
+    private static <T> void testEmptySet(Set<T> c) {
         testEmptyCollection(c);
         equal(c.hashCode(), 0);
         equal2(c, Collections.<Integer>emptySet());
+        if (c instanceof NavigableSet<?>)
+            testEmptyIterator(((NavigableSet<T>)c).descendingIterator());
     }

     private static void testImmutableCollection(final Collection<Integer> c) {
@@ -221,7 +240,7 @@ public class MOAT {
         testEmptyCollection(c);
     }

-    private static void testEmptyMap(final Map<?,?> m) {
+    private static <K,V> void testEmptyMap(final Map<K,V> m) {
         check(m.isEmpty());
         equal(m.size(), 0);
         equal(m.toString(),"{}");
@@ -433,8 +452,18 @@ public class MOAT {
         if (! supportsAdd(c)) return;
         //System.out.println("add() supported");

-        if (c instanceof NavigableSet)
-            testNavigableSet((NavigableSet<Integer>)c);
+        if (c instanceof NavigableSet) {
+            System.out.println("NavigableSet tests...");
+
+            NavigableSet<Integer> ns = (NavigableSet<Integer>)c;
+            testNavigableSet(ns);
+            testNavigableSet(ns.headSet(6, false));
+            testNavigableSet(ns.headSet(5, true));
+            testNavigableSet(ns.tailSet(0, false));
+            testNavigableSet(ns.tailSet(1, true));
+            testNavigableSet(ns.subSet(0, false, 5, true));
+            testNavigableSet(ns.subSet(1, true, 6, false));
+        }

         if (c instanceof Queue)
             testQueue((Queue<Integer>)c);
@@ -514,8 +543,19 @@ public class MOAT {
         if (m instanceof ConcurrentMap)
             testConcurrentMap((ConcurrentMap<Integer,Integer>) m);

-        if (m instanceof NavigableMap)
-            testNavigableMap((NavigableMap<Integer,Integer>) m);
+        if (m instanceof NavigableMap) {
+            System.out.println("NavigableMap tests...");
+
+            NavigableMap<Integer,Integer> nm =
+                (NavigableMap<Integer,Integer>) m;
+            testNavigableMap(nm);
+            testNavigableMap(nm.headMap(6, false));
+            testNavigableMap(nm.headMap(5, true));
+            testNavigableMap(nm.tailMap(0, false));
+            testNavigableMap(nm.tailMap(1, true));
+            testNavigableMap(nm.subMap(1, true, 6, false));
+            testNavigableMap(nm.subMap(0, false, 5, true));
+        }

         checkFunctionalInvariants(m);

@@ -697,8 +737,6 @@ public class MOAT {

     private static void testNavigableMap(NavigableMap<Integer,Integer> m)
     {
-        System.out.println("NavigableMap tests...");
-
         clear(m);
         checkNavigableMapKeys(m, 1, null, null, null, null);

@@ -717,9 +755,11 @@ public class MOAT {
         checkNavigableMapKeys(m, 5,    3,    5,    5, null);
         checkNavigableMapKeys(m, 6,    5,    5, null, null);

-        {
-            final Iterator<Integer> it
-                = m.descendingKeySet().iterator();
+        for (final Iterator<Integer> it :
+                 (Iterator<Integer>[])
+                 new Iterator<?>[] {
+                     m.descendingKeySet().iterator(),
+                     m.navigableKeySet().descendingIterator()}) {
             equalNext(it, 5);
             equalNext(it, 3);
             equalNext(it, 1);
@@ -742,8 +782,6 @@ public class MOAT {


     private static void testNavigableSet(NavigableSet<Integer> s) {
-        System.out.println("NavigableSet tests...");
-
         clear(s);
         checkNavigableSetKeys(s, 1, null, null, null, null);

@@ -762,8 +800,11 @@ public class MOAT {
         checkNavigableSetKeys(s, 5,    3,    5,    5, null);
         checkNavigableSetKeys(s, 6,    5,    5, null, null);

-        {
-            final Iterator<Integer> it = s.descendingIterator();
+        for (final Iterator<Integer> it :
+                 (Iterator<Integer>[])
+                 new Iterator<?>[] {
+                     s.descendingIterator(),
+                     s.descendingSet().iterator()}) {
             equalNext(it, 5);
             equalNext(it, 3);
             equalNext(it, 1);