TreeMap.navigableKeySet().descendingIterator() sequence ?

[Martin Buchholz]

Yes, sad to say, looks like a serious and embarrassing bug.
This bit of code has no existing test case.
More tests should be added to MOAT.java.
Charlie, please file a bug.

In our defense, there are very many methods in the NavigableFoo interfaces,
and for completeness they have to be tested on subsets and submaps,
and Sun engineers have not historically had good code coverage tool support.

Martin

On Fri, Apr 18, 2008 at 2:39 PM, kevin bourrillion <kevinb at google.com>
wrote:

> Wow.  TreeMap.java line 1024:
>
>    return new DescendingKeyIterator(getFirstEntry());
>
> Sure does look fishy.
>
>
>
> On Thu, Apr 17, 2008 at 2:54 PM, charlie hunt <charlie.hunt at sun.com>
> wrote:
> > 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 ...
> >
> >
>
>
>
> --
> Kevin Bourrillion @ Google
> internal: go/javalibraries
> google-collections.googlecode.com
> google-guice.googlecode.com
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openjdk.java.net/pipermail/core-libs-dev/attachments/20080419/6759d7a8/attachment.html>