more TreeMap questions (descendingMap, headMap and tailMap)

Wed May 28 23:20:47 UTC 2008

On Wed, May 28, 2008 at 6:29 AM, charlie hunt <charlie.hunt at sun.com> wrote:
> Are headmaps, tailmaps and descending maps considered to be, or defined to
> be submaps?

headmaps and tailmaps are submaps, but descending maps are not,
(except in the trivial sense that every map is a submap of itself)

> 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?

"its" refers to the returned map.

Range checks only ever have to look at the "nearest" map.

Martin

> 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/>
>
>