TreeMap.navigableKeySet().descendingIterator() sequence ?
Joshua Bloch
jjb at google.com
Sun Apr 20 07:07:03 UTC 2008
FWIW, I probably wrote the broken code. I wrote NavigableMap and
retrofitted TreeMap. Doug wrote ConcurrentSkipListMap. Sorry 'bout that.
Josh
On Sat, Apr 19, 2008 at 5:56 PM, Martin Buchholz <martinrb at google.com>
wrote:
> Alan, thanks for filing the bug.
>
> Charlie, thanks for the review. However, since you are not (yet?)
> an OpenJDK committer, I will still need an official review from Doug
> (or Alan?)
>
> I noticed there was another test case, NavigableMap/LockStep.java,
> that "almost" tested the faulty code.
>
> I include a change to that test case as well, below
> (as well as making the test case a little more maintainble).
>
> diff --git a/test/java/util/NavigableMap/LockStep.java
> b/test/java/util/NavigableMap/LockStep.java
> --- a/test/java/util/NavigableMap/LockStep.java
> +++ b/test/java/util/NavigableMap/LockStep.java
> @@ -159,6 +159,7 @@ public class LockStep {
> 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 @@ public class LockStep {
> }
> }
>
> + 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 @@ public class LockStep {
> 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 @@ public class LockStep {
>
> 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 @@ public class LockStep {
>
> 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 @@ public class LockStep {
>
> 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,
>
>
> Martin
>
> On Sat, Apr 19, 2008 at 2:07 PM, charlie hunt <charlie.hunt at sun.com>
> wrote:
> >
> > Alan Bateman wrote:
> >
> > > Martin Buchholz wrote:
> > >
> > > > :
> > > >
> > > > 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.
> > > >
> > > >
> > > I don't know if Charlie is online today, but as you seem to be ready
> to
> > create the change-set, I've created java/classes_util bug:
> > >
> > > 6691185: (coll) TreeMap.navigableKeySet's descendingIterator method
> > starts at first instead of last entry
> > >
> > > with a link to this thread. The synopsis can be changed if you want
> > something different.
> > >
> > > -Alan.
> > >
> >
> > Alan, thanks for filing the bug. One less item on my list of things to
> do.
> > :-)
> >
> > Fwiw, I've looked at Martin's proposed changes. From the familiarity
> I've
> > gotten with TreeMap over the past week or two, the changes look good to
> me.
> >
> > charlie ...
> >
> >
> >
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openjdk.java.net/pipermail/core-libs-dev/attachments/20080420/f70f420d/attachment.html>
More information about the core-libs-dev
mailing list