Path: csiph.com!usenet.pasdenom.info!gegeweb.org!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 11:45:41 -0600
Organization: Trip away; make no stay.
Lines: 70
Message-ID: <ydnr4p66x16.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>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Info: mx04.eternal-september.org; posting-host="75975abe3fe3503ca7350803ab98e478"; logging-data="4226"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX192TlwsbONLRcf3geazA77j"
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.3 (gnu/linux)
Cancel-Lock: sha1:ywvbJq7eg3ZIg2HuaEn79DrpWys= sha1:h+zO6/7GPyMDLgZ+9YSwKRgG4Ss=
Xref: csiph.com comp.lang.java.programmer:19228

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>();
  
  private static class OrderedComparator implements java.util.Comparator<Object> {
    private Map<?, Long> insertionRanks;
    
    @Override
    public int compare(Object o1, Object o2) {
      Long rank1 = insertionRanks.get(o1);
      Long rank2 = insertionRanks.get(o2);
      return rank1.compareTo(rank2);
    }
  }

  public InsertionOrderedMap() {
    super((java.util.Comparator< ? super K>)new OrderedComparator());
    ((OrderedComparator)comparator()).insertionRanks = this.insertionRanks;
  }

  @Override
  public V put(K key, V value) {
    insertionRanks.put(key, nextInsertionRank++);
    return super.put(key, value);
  };
  
  @Override
  public V remove(Object key) {
    insertionRanks.remove(key);
    return super.remove(key);
  }
}

Not tested, and I make no claims regarding its correctness.  I wanted to
make OrderedComparator a non-static inner class but I couldn't get the
constructor to compile, so there is some possibly avoidable ugliness
there.

-- 
Jim Janney