Path: csiph.com!usenet.pasdenom.info!weretis.net!feeder4.news.weretis.net!eternal-september.org!feeder.eternal-september.org!mx04.eternal-september.org!.POSTED!not-for-mail
From: Jim Janney <jjanney@shell.xmission.com>
Newsgroups: comp.lang.java.programmer
Subject: Re: Glitch in Java Collections (No descendingMap in LinkedHashMap)
Date: Wed, 10 Oct 2012 16:51:11 -0600
Organization: absinthe will make my art grow stronger
Lines: 54
Message-ID: <ydnfw5m6iw0.fsf@shell.xmission.com>
References: <k4jua8$77d$1@news.albasani.net> <ydn4nm38kpc.fsf@shell.xmission.com> <ydnzk3u74od.fsf@shell.xmission.com> <k544ha$hj0$1@dont-email.me> <ydnvcei70lu.fsf@shell.xmission.com> <ydnr4p66x16.fsf@shell.xmission.com> <k54sau$htf$1@dont-email.me>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Info: mx04.eternal-september.org; posting-host="75975abe3fe3503ca7350803ab98e478"; logging-data="28394"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18E+hZ8QcuJpVdvvNEUQSVq"
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.3 (gnu/linux)
Cancel-Lock: sha1:NZms72Waov7Ut1IpN/oe4SoGEmw= sha1:dxXYIcBDzfDL1YTvX4GdxBVpYQw=
Xref: csiph.com comp.lang.java.programmer:19241

Eric Sosman <esosman@comcast-dot-net.invalid> writes:

> On 10/10/2012 1:45 PM, Jim Janney wrote:
>> Jim Janney <jjanney@shell.xmission.com> writes:
>>
>>> Eric Sosman <esosman@comcast-dot-net.invalid> writes:
>>>
>>>> On 10/10/2012 11:00 AM, Jim Janney wrote:
>>>>> Jim Janney <jjanney@shell.xmission.com> writes:
>>>>>
>>>>>> Jan Burse <janburse@fastmail.fm> writes:
>>>>>> [...]
>>>>>> If I really needed that functionality I'd probably try maintaining my
>>>>>> own access-order list in parallel to the map.
>>>>>
>>>>> Oops, stupid me.  The other way is to define a comparator based on
>>>>> insertion order, and then use a SortedMap.
>>>>
>>>>      Defining the comparator might be something of a struggle,
>>>> especially if the same object instance could be referred to by
>>>> two different LinkedHashMaps.
>>>
>>> The trick is finding a way to link the ordering information (probably a
>>> counter assocated with the map) with the keys themselves.  This is the
>>> kind of problem where IdentityHashMap comes in handy.
>>
>> Voila:
>>
>>
>> import java.util.Map;
>> import java.util.TreeMap;
>> import java.util.WeakHashMap;
>>
>> public class InsertionOrderedMap<K,V> extends TreeMap<K,V> {
>>    private long nextInsertionRank = 0;
>>    private Map<K, Long> insertionRanks = new WeakHashMap<K, Long>();
>>    [... in which a sequence number is stored.]
>
>     Okay, fine, but how does this qualify as an "other" way?
> To my eye it looks exactly like "my own access-order list in
> parallel to the map," and not something "other" at all.

My original idea would let you iterate over the list of keys in forward
or reverse order, but nothing else.  This approach implements the full
NavigableMap interface, with descendingMap, subMap, headMap, tailMap,
etc. all working as advertised.  It isn't clear whether the original
poster actually needs all functionality.

There is a performance penalty.  TreeMap guarantees no more than log(n)
comparisons per lookup, but each comparison now requires two extra
HashMap lookups.

-- 
Jim Janney