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 <[EMAIL PROTECTED]
<mailto:[EMAIL PROTECTED]>> 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
<[EMAIL PROTECTED] <mailto:[EMAIL PROTECTED]>> 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/>
