Mercurial > hg > shenandoah-preopenjdk-archive > openjdk8 > jdk
changeset 270:3e7a4b6ef105
6691185: (coll) TreeMap.navigableKeySet's descendingIterator method starts at first instead of last entry
Reviewed-by: dl, chegar
| author | martin |
|---|---|
| date | Sat, 10 May 2008 11:49:25 -0700 |
| parents | d64b14c25c82 |
| children | 9781e5c7b9ba |
| files | src/share/classes/java/util/TreeMap.java test/java/util/Collection/MOAT.java test/java/util/NavigableMap/LockStep.java |
| diffstat | 3 files changed, 205 insertions(+), 142 deletions(-) [+] |
line wrap: on
line diff
--- a/src/share/classes/java/util/TreeMap.java Sat May 10 11:30:53 2008 -0700 +++ b/src/share/classes/java/util/TreeMap.java Sat May 10 11:49:25 2008 -0700 @@ -1,5 +1,5 @@ /* - * Copyright 1997-2007 Sun Microsystems, Inc. All Rights Reserved. + * Copyright 1997-2008 Sun Microsystems, Inc. All Rights Reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it @@ -1021,7 +1021,7 @@ } Iterator<K> descendingKeyIterator() { - return new DescendingKeyIterator(getFirstEntry()); + return new DescendingKeyIterator(getLastEntry()); } static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {
--- a/test/java/util/Collection/MOAT.java Sat May 10 11:30:53 2008 -0700 +++ b/test/java/util/Collection/MOAT.java Sat May 10 11:49:25 2008 -0700 @@ -1,5 +1,5 @@ /* - * Copyright 2005-2007 Sun Microsystems, Inc. All Rights Reserved. + * Copyright 2005-2008 Sun Microsystems, Inc. All Rights Reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it @@ -25,7 +25,7 @@ * @test * @bug 6207984 6272521 6192552 6269713 6197726 6260652 5073546 4137464 * 4155650 4216399 4294891 6282555 6318622 6355327 6383475 6420753 - * 6431845 4802633 6570566 6570575 6570631 6570924 + * 6431845 4802633 6570566 6570575 6570631 6570924 6691185 * @summary Run many tests on many Collection and Map implementations * @author Martin Buchholz */ @@ -155,7 +155,7 @@ 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 @@ 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 @@ 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 @@ 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 @@ 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 @@ 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 @@ 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 @@ 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 @@ 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 @@ 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);
--- a/test/java/util/NavigableMap/LockStep.java Sat May 10 11:30:53 2008 -0700 +++ b/test/java/util/NavigableMap/LockStep.java Sat May 10 11:49:25 2008 -0700 @@ -1,5 +1,5 @@ /* - * Copyright 2006 Sun Microsystems, Inc. All Rights Reserved. + * Copyright 2006-2008 Sun Microsystems, Inc. All Rights Reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it @@ -23,7 +23,7 @@ /* * @test - * @bug 6420753 6242436 + * @bug 6420753 6242436 6691185 * @summary Compare NavigableMap implementations for identical behavior * @author Martin Buchholz */ @@ -159,6 +159,7 @@ Object[] a = new Object[1]; a[0] = Boolean.TRUE; equal(c.toArray(a), a); equal(a[0], null); + check(! c.iterator().hasNext()); } static void testEmptySet(Set<?> c) { @@ -262,6 +263,16 @@ } } + static void equalIterators(final Iterator<?> it1, + final Iterator<?> it2) { + while (it1.hasNext()) { + if (maybe(2)) + check(it2.hasNext()); + equal(it1.next(), it2.next()); + } + check(! it2.hasNext()); + } + static void equalNavigableSetsLeaf(final NavigableSet s1, final NavigableSet s2) { equal2(s1, s2); @@ -273,6 +284,8 @@ equal(s1.first(), s2.first()); equal(s1.last(), s2.last()); } + equalIterators(s1.iterator(), s2.iterator()); + equalIterators(s1.descendingIterator(), s2.descendingIterator()); checkNavigableSet(s1); checkNavigableSet(s2); } @@ -493,30 +506,23 @@ static MapFrobber randomAdder(NavigableMap m) { final Integer k = unusedKey(m); - MapFrobber f; - switch (rnd.nextInt(4)) { - case 0: f = new MapFrobber() {void frob(NavigableMap m) { - equal(m.put(k, k+1), null); - equal(m.get(k), k+1); - if (maybe(4)) { - equal(m.put(k, k+1), k+1); - equal(m.get(k), k+1);}}}; - break; - case 1: f = new MapFrobber() {void frob(NavigableMap m) { - m.descendingMap().put(k, k+1); - equal(m.get(k), k+1);}}; - break; - case 2: f = new MapFrobber() {void frob(NavigableMap m) { - m.tailMap(k,true).headMap(k,true).put(k,k+1);}}; - break; - case 3: f = new MapFrobber() {void frob(NavigableMap m) { - m.tailMap(k,true).headMap(k,true).descendingMap().put(k,k+1);}}; - break; - default: throw new Error(); - } - final MapFrobber ff = f; + final MapFrobber[] randomAdders = { + new MapFrobber() {void frob(NavigableMap m) { + equal(m.put(k, k+1), null); + equal(m.get(k), k+1); + if (maybe(4)) { + equal(m.put(k, k+1), k+1); + equal(m.get(k), k+1);}}}, + new MapFrobber() {void frob(NavigableMap m) { + m.descendingMap().put(k, k+1); + equal(m.get(k), k+1);}}, + new MapFrobber() {void frob(NavigableMap m) { + m.tailMap(k,true).headMap(k,true).put(k,k+1);}}, + new MapFrobber() {void frob(NavigableMap m) { + m.tailMap(k,true).headMap(k,true).descendingMap().put(k,k+1);}} + }; return new MapFrobber() {void frob(NavigableMap m) { - ff.frob(m); + randomAdders[rnd.nextInt(randomAdders.length)].frob(m); if (maybe(2)) equal(m.get(k), k+1); if (maybe(4)) { equal(m.put(k, k+1), k+1); @@ -525,26 +531,19 @@ static SetFrobber randomAdder(NavigableSet s) { final Integer e = unusedElt(s); - SetFrobber f; - switch (rnd.nextInt(4)) { - case 0: f = new SetFrobber() {void frob(NavigableSet s) { - check(s.add(e));}}; - break; - case 1: f = new SetFrobber() {void frob(NavigableSet s) { - s.descendingSet().add(e);}}; - break; - case 2: f = new SetFrobber() {void frob(NavigableSet s) { - s.tailSet(e,true).headSet(e,true).add(e);}}; - break; - case 3: f = new SetFrobber() {void frob(NavigableSet s) { - s.descendingSet().tailSet(e,true).headSet(e,true).add(e);}}; - break; - default: throw new Error(); - } - final SetFrobber ff = f; + final SetFrobber[] randomAdders = { + new SetFrobber() {void frob(NavigableSet s) { + check(s.add(e));}}, + new SetFrobber() {void frob(NavigableSet s) { + s.descendingSet().add(e);}}, + new SetFrobber() {void frob(NavigableSet s) { + s.tailSet(e,true).headSet(e,true).add(e);}}, + new SetFrobber() {void frob(NavigableSet s) { + s.descendingSet().tailSet(e,true).headSet(e,true).add(e);}} + }; return new SetFrobber() {void frob(NavigableSet s) { if (maybe(2)) check(! s.contains(e)); - ff.frob(s); + randomAdders[rnd.nextInt(randomAdders.length)].frob(s); if (maybe(2)) check(! s.add(e)); if (maybe(2)) check(s.contains(e));}}; } @@ -605,89 +604,112 @@ static MapFrobber randomRemover(NavigableMap m) { final Integer k = usedKey(m); - switch (rnd.nextInt(7)) { - default: throw new Error(); - case 0: return new MapFrobber() {void frob(NavigableMap m) { - Map.Entry e = m.firstEntry(); - equal(m.pollFirstEntry(), e); - checkUnusedKey(m, e.getKey());}}; - case 1: return new MapFrobber() {void frob(NavigableMap m) { - Map.Entry e = m.lastEntry(); - equal(m.pollLastEntry(), e); - checkUnusedKey(m, e.getKey());}}; - case 2: return new MapFrobber() {void frob(NavigableMap m) { - check(m.remove(k) != null); - checkUnusedKey(m, k);}}; - case 3: return new MapFrobber() {void frob(NavigableMap m) { - m.subMap(k, true, k, true).clear(); - checkUnusedKey(m, k);}}; - case 4: return new MapFrobber() {void frob(NavigableMap m) { - m.descendingMap().subMap(k, true, k, true).clear(); - checkUnusedKey(m, k);}}; - case 5: return new MapFrobber() {void frob(NavigableMap m) { - final Iterator it = m.keySet().iterator(); - while (it.hasNext()) - if (it.next().equals(k)) { - it.remove(); - if (maybe(2)) - THROWS(IllegalStateException.class, - new Fun(){void f(){ it.remove(); }}); - } - checkUnusedKey(m, k);}}; - case 6: return new MapFrobber() {void frob(NavigableMap m) { - final Iterator<Map.Entry> it = m.entrySet().iterator(); - while (it.hasNext()) - if (it.next().getKey().equals(k)) { - it.remove(); - if (maybe(2)) - THROWS(IllegalStateException.class, remover(it)); - } - checkUnusedKey(m, k);}}; - } + final MapFrobber[] randomRemovers = { + new MapFrobber() {void frob(NavigableMap m) { + Map.Entry e = m.firstEntry(); + equal(m.pollFirstEntry(), e); + checkUnusedKey(m, e.getKey());}}, + new MapFrobber() {void frob(NavigableMap m) { + Map.Entry e = m.lastEntry(); + equal(m.pollLastEntry(), e); + checkUnusedKey(m, e.getKey());}}, + new MapFrobber() {void frob(NavigableMap m) { + check(m.remove(k) != null); + checkUnusedKey(m, k);}}, + new MapFrobber() {void frob(NavigableMap m) { + m.subMap(k, true, k, true).clear(); + checkUnusedKey(m, k);}}, + new MapFrobber() {void frob(NavigableMap m) { + m.descendingMap().subMap(k, true, k, true).clear(); + checkUnusedKey(m, k);}}, + new MapFrobber() {void frob(NavigableMap m) { + final Iterator it = m.keySet().iterator(); + while (it.hasNext()) + if (it.next().equals(k)) { + it.remove(); + if (maybe(2)) + THROWS(IllegalStateException.class, + new Fun(){void f(){ it.remove(); }}); + } + checkUnusedKey(m, k);}}, + new MapFrobber() {void frob(NavigableMap m) { + final Iterator it = m.navigableKeySet().descendingIterator(); + while (it.hasNext()) + if (it.next().equals(k)) { + it.remove(); + if (maybe(2)) + THROWS(IllegalStateException.class, + new Fun(){void f(){ it.remove(); }}); + } + checkUnusedKey(m, k);}}, + new MapFrobber() {void frob(NavigableMap m) { + final Iterator<Map.Entry> it = m.entrySet().iterator(); + while (it.hasNext()) + if (it.next().getKey().equals(k)) { + it.remove(); + if (maybe(2)) + THROWS(IllegalStateException.class, remover(it)); + } + checkUnusedKey(m, k);}}, + }; + + return randomRemovers[rnd.nextInt(randomRemovers.length)]; } static SetFrobber randomRemover(NavigableSet s) { final Integer e = usedElt(s); - switch (rnd.nextInt(7)) { - default: throw new Error(); - case 0: return new SetFrobber() {void frob(NavigableSet s) { - Object e = s.first(); - equal(s.pollFirst(), e); - checkUnusedElt(s, e);}}; - case 1: return new SetFrobber() {void frob(NavigableSet s) { - Object e = s.last(); - equal(s.pollLast(), e); - checkUnusedElt(s, e);}}; - case 2: return new SetFrobber() {void frob(NavigableSet s) { - check(s.remove(e)); - checkUnusedElt(s, e);}}; - case 3: return new SetFrobber() {void frob(NavigableSet s) { - s.subSet(e, true, e, true).clear(); - checkUnusedElt(s, e);}}; - case 4: return new SetFrobber() {void frob(NavigableSet s) { - s.descendingSet().subSet(e, true, e, true).clear(); - checkUnusedElt(s, e);}}; - case 5: return new SetFrobber() {void frob(NavigableSet s) { - final Iterator it = s.iterator(); - while (it.hasNext()) - if (it.next().equals(e)) { - it.remove(); - if (maybe(2)) - THROWS(IllegalStateException.class, - new Fun(){void f(){ it.remove(); }}); - } - checkUnusedElt(s, e);}}; - case 6: return new SetFrobber() {void frob(NavigableSet s) { - final Iterator it = s.descendingSet().iterator(); - while (it.hasNext()) - if (it.next().equals(e)) { - it.remove(); - if (maybe(2)) - THROWS(IllegalStateException.class, - new Fun(){void f(){ it.remove(); }}); - } - checkUnusedElt(s, e);}}; - } + + final SetFrobber[] randomRemovers = { + new SetFrobber() {void frob(NavigableSet s) { + Object e = s.first(); + equal(s.pollFirst(), e); + checkUnusedElt(s, e);}}, + new SetFrobber() {void frob(NavigableSet s) { + Object e = s.last(); + equal(s.pollLast(), e); + checkUnusedElt(s, e);}}, + new SetFrobber() {void frob(NavigableSet s) { + check(s.remove(e)); + checkUnusedElt(s, e);}}, + new SetFrobber() {void frob(NavigableSet s) { + s.subSet(e, true, e, true).clear(); + checkUnusedElt(s, e);}}, + new SetFrobber() {void frob(NavigableSet s) { + s.descendingSet().subSet(e, true, e, true).clear(); + checkUnusedElt(s, e);}}, + new SetFrobber() {void frob(NavigableSet s) { + final Iterator it = s.iterator(); + while (it.hasNext()) + if (it.next().equals(e)) { + it.remove(); + if (maybe(2)) + THROWS(IllegalStateException.class, + new Fun(){void f(){ it.remove(); }}); + } + checkUnusedElt(s, e);}}, + new SetFrobber() {void frob(NavigableSet s) { + final Iterator it = s.descendingSet().iterator(); + while (it.hasNext()) + if (it.next().equals(e)) { + it.remove(); + if (maybe(2)) + THROWS(IllegalStateException.class, + new Fun(){void f(){ it.remove(); }}); + } + checkUnusedElt(s, e);}}, + new SetFrobber() {void frob(NavigableSet s) { + final Iterator it = s.descendingIterator(); + while (it.hasNext()) + if (it.next().equals(e)) { + it.remove(); + if (maybe(2)) + THROWS(IllegalStateException.class, + new Fun(){void f(){ it.remove(); }}); + } + checkUnusedElt(s, e);}} + }; + + return randomRemovers[rnd.nextInt(randomRemovers.length)]; } static void lockStep(NavigableMap m1,