more TreeMap questions (descendingMap, headMap and tailMap)

charlie hunt charlie.hunt at sun.com
Fri May 23 13:11:31 UTC 2008


I have run across a couple cases which may or may not be defects in 
TreeMap.  Or, it's simply a case where I am not understanding the Java 
docs for TreeMap & NavigableMap correctly.

When looking at the Java docs for TreeMap / NavigableMap tailMap() I 
read, "Returns a view of the portion of this map whose keys are greater 
than (or equal to, if |inclusive| is true) |fromKey|. The returned map 
is backed by this map, so changes in the returned map are reflected in 
this map, and vice-versa. The returned map supports all optional map 
operations that this map supports."  More importantly, I read this 
method will throw an "||IllegalArgumentException if this map itself has 
a restricted range, and |fromKey| lies outside the bounds of the range".

I interpret the latter here to mean if I create a subMap(), headMap() or 
tailMap() I have a map which has "a restricted range"?

Assuming my interpretation is correct.  I wrote a test program on a 
TreeMap containing Integer keys and String values.  I populated the 
TreeMap with keys 5 - 5000 at every 5th integer, (i.e. 5,10,15,20,25, 
.... 4985,4990,4995,5000).  And, for each key, I just created a string 
such as, "Value stored is -> <key>".

I found if I do a 
subMap(Integer.valueOf(5),true,Integer.valueOf(5000),true) I get a 
NavigableMap back containing the same keys/values as the TreeMap.  If I 
then do a tailMap(Integer.valueOf(4850),false), I get a NavigableMap 
back containing keys 4855 - 5000 and their corresponding values.  All as 
expected to this point.  If I now do a 
tailMap(Integer.valueOf(4850,false) on that last NavigableMap I got back 
which contains keys 4855 - 5000, according to the Java doc, I would 
expect an IllegalArgumentException to be thrown since 4850 is outside 
the bounds of 4855 - 5000.   But, this is not what happens. I get the 
same NavigableMap back containing keys 4855 - 5000.

I can produce a similar result by taking the same initial TreeMap, doing 
a descendingMap() on it.  Then, doing a headMap(Integer.valueOf(4850)) 
followed by a headMap(Integer.valueOf(4850)).  I am interpreting that a 
headMap(K key) on a descendingMap is essentially the same as a tailMap(K 
key, false) on an ascending map of the same underlying TreeMap.

Am I interpreting some completely wrong?  Or, is the not throwing of an 
IllegalArgumentException expected behavior?  Or, is this indeed a defect?

Attached is a simple program which illustrates what I have described.

thanks,

charlie ...


-- 

Charlie Hunt
Java Performance Engineer

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

-------------- next part --------------
A non-text attachment was scrubbed...
Name: TestTreeMap.java
Type: text/x-java
Size: 4055 bytes
Desc: not available
URL: <http://mail.openjdk.java.net/pipermail/core-libs-dev/attachments/20080523/641d8d18/TestTreeMap.java>


More information about the core-libs-dev mailing list