TreeMap.navigableKeySet().descendingIterator() sequence ?

[charlie hunt]

I'll file a bug.  I'll also suggest in the bug report additional tests 
be added to MOAT.java.

You are right, there are very many Navigable* interface methods  ("very 
many" doesn't seem to do justice to describe the number of methods).  
TreeMap is rather complex beast!   It's complexity really increased 
between Java 5 and Java 6. In looking at TreeMap closely over the last 
week, writing a complete suite of tests for TreeMap would be lengthy and 
difficult task. It's easy to see how this bug could have slipped through.

Looks like the fix is changing TreeMap line 1024, from "return 
DescendingKeyIterator(getFirstEntry())" to "return 
DescendingKeyIterator(getLastEntry())".

thanks,

charlie ...

Martin Buchholz wrote:
> 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 
> <mailto: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 <mailto: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
>     <http://google-collections.googlecode.com>
>     google-guice.googlecode.com <http://google-guice.googlecode.com>
>
>

-- 

Charlie Hunt
Java Performance Engineer

<http://java.sun.com/docs/performance/>