more TreeMap questions (descendingMap, headMap and tailMap)

charlie hunt charlie.hunt at sun.com
Wed May 28 13:29:43 UTC 2008


Are headmaps, tailmaps and descending maps considered to be, or defined 
to be submaps?

In the context of, "to construct a submap either of whose endpoints lie 
outside its range", the term "its" refers to what?  The map from which a 
submap is created, or the farthest back backing map, the domain of 
possible keys, or something else?

thanks,

charlie ...

Martin Buchholz wrote:
> There was an attempt made to be more precise about
> when  IllegalArgumentException would be thrown,
> consistent with this wording from subMap
>
>     * <p>The returned map will throw an {@code IllegalArgumentException}
>      * on an attempt to insert a key outside of its range, or to construct a
>      * submap either of whose endpoints lie outside its range.
>
> In all cases, the range refers to the endpoints passed to the
> methods creating sub-maps; they cannot change once the
> sub-map has been created.
>
> Martin
>
> On Fri, May 23, 2008 at 6:36 PM, charlie hunt <charlie.hunt at sun.com> wrote:
>   
>> If that's the definition given to "restricted range", I think there is some
>> inconsistencies in the behavior of TreeMap.
>>
>> If you play around with some of descendingMap(), subMap(), headMap() and
>> tailMap() variations such as those in the example program in my original
>> e-mail, I think you'll see there are some cases where
>> IllegalArgumentException is thrown.
>>
>> Are you suggesting that "could ever contain" to mean, for example, if I have
>> Integer keys, that all fromKey/toKey must be between Integer.MIN_VALUE and
>> Integer.MAX_VALUE?   Or, is it "restricted" to the bounds of the "backing"
>> map?
>>
>> Perhaps I'm just being naive, but it seems "restricted range" is rather
>> ambigious.
>>
>> charlie ...
>>
>> Martin Buchholz wrote:
>>     
>>> The "restricted range" refers to the elements that the submap could
>>> possibly ever contain,
>>> not the elements that it currently contains.
>>>
>>> This may not be described in the clearest way in the doc,
>>> but I'm not motivated to work on clarifying it,
>>> partly because I've generally felt it was a design mistake
>>> to try to enforce these kinds of range restrictions,
>>> although I helped to implement the enforcing code.
>>>
>>> Martin
>>>
>>> On Fri, May 23, 2008 at 6:11 AM, charlie hunt <charlie.hunt at sun.com>
>>> wrote:
>>>
>>>       
>>>> 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/>
>>>>
>>>>
>>>>
>>>>         
>>     

-- 

Charlie Hunt
Java Performance Engineer

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




More information about the core-libs-dev mailing list