Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #19228

Re: Glitch in Java Collections (No descendingMap in LinkedHashMap)

Show all headers | View raw

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

Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Glitch in Java Collections (No descendingMap in LinkedHashMap) Jan Burse <janburse@fastmail.fm> - 2012-10-04 14:09 +0200
  Re: Glitch in Java Collections (No descendingMap in LinkedHashMap) Robert Klemme <shortcutter@googlemail.com> - 2012-10-04 23:01 +0200
    Re: Glitch in Java Collections (No descendingMap in LinkedHashMap) Lew <lewbloch@gmail.com> - 2012-10-04 14:43 -0700
      Re: Glitch in Java Collections (No descendingMap in LinkedHashMap) Jan Burse <janburse@fastmail.fm> - 2012-10-05 00:17 +0200
      Re: Glitch in Java Collections (No descendingMap in LinkedHashMap) Robert Klemme <shortcutter@googlemail.com> - 2012-10-05 19:11 +0200
        Re: Glitch in Java Collections (No descendingMap in LinkedHashMap) Lew <lewbloch@gmail.com> - 2012-10-05 11:05 -0700
          Re: Glitch in Java Collections (No descendingMap in LinkedHashMap) Jan Burse <janburse@fastmail.fm> - 2012-10-05 20:18 +0200
          Re: Glitch in Java Collections (No descendingMap in LinkedHashMap) Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-10-05 12:06 -0700
            Re: Glitch in Java Collections (No descendingMap in LinkedHashMap) Lew <lewbloch@gmail.com> - 2012-10-05 13:04 -0700
              Re: Glitch in Java Collections (No descendingMap in LinkedHashMap) Jan Burse <janburse@fastmail.fm> - 2012-10-05 23:44 +0200
                Re: Glitch in Java Collections (No descendingMap in LinkedHashMap) Jan Burse <janburse@fastmail.fm> - 2012-10-05 23:50 +0200
                Re: Glitch in Java Collections (No descendingMap in LinkedHashMap) Jan Burse <janburse@fastmail.fm> - 2012-10-06 00:00 +0200
                Re: Glitch in Java Collections (No descendingMap in LinkedHashMap) glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2012-10-05 23:39 +0000
                Re: Glitch in Java Collections (No descendingMap in LinkedHashMap) Jan Burse <janburse@fastmail.fm> - 2012-10-06 12:18 +0200
                Re: Glitch in Java Collections (No descendingMap in LinkedHashMap) Jan Burse <janburse@fastmail.fm> - 2012-10-06 12:22 +0200
              Re: Glitch in Java Collections (No descendingMap in LinkedHashMap) Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-10-05 15:51 -0700
          Re: Glitch in Java Collections (No descendingMap in LinkedHashMap) Robert Klemme <shortcutter@googlemail.com> - 2012-10-06 13:53 +0200
  Re: Glitch in Java Collections (No descendingMap in LinkedHashMap) Jim Janney <jjanney@shell.xmission.com> - 2012-10-09 14:16 -0600
    Re: Glitch in Java Collections (No descendingMap in LinkedHashMap) Jim Janney <jjanney@shell.xmission.com> - 2012-10-10 09:00 -0600
      Re: Glitch in Java Collections (No descendingMap in LinkedHashMap) Eric Sosman <esosman@comcast-dot-net.invalid> - 2012-10-10 11:34 -0400
        Re: Glitch in Java Collections (No descendingMap in LinkedHashMap) Jim Janney <jjanney@shell.xmission.com> - 2012-10-10 10:28 -0600
          Re: Glitch in Java Collections (No descendingMap in LinkedHashMap) Jim Janney <jjanney@shell.xmission.com> - 2012-10-10 11:45 -0600
            Re: Glitch in Java Collections (No descendingMap in LinkedHashMap) Lew <lewbloch@gmail.com> - 2012-10-10 10:52 -0700
              Re: Glitch in Java Collections (No descendingMap in LinkedHashMap) Jim Janney <jjanney@shell.xmission.com> - 2012-10-10 12:47 -0600
                Re: Glitch in Java Collections (No descendingMap in LinkedHashMap) Jim Janney <jjanney@shell.xmission.com> - 2012-10-11 14:17 -0600
            Re: Glitch in Java Collections (No descendingMap in LinkedHashMap) Eric Sosman <esosman@comcast-dot-net.invalid> - 2012-10-10 18:20 -0400
              Re: Glitch in Java Collections (No descendingMap in LinkedHashMap) Jim Janney <jjanney@shell.xmission.com> - 2012-10-10 16:51 -0600
                Re: Glitch in Java Collections (No descendingMap in LinkedHashMap) Jan Burse <janburse@fastmail.fm> - 2012-10-12 14:34 +0200
                Re: Glitch in Java Collections (No descendingMap in LinkedHashMap) Jim Janney <jjanney@shell.xmission.com> - 2012-10-12 09:12 -0600
                Re: Glitch in Java Collections (No descendingMap in LinkedHashMap) Eric Sosman <esosman@comcast-dot-net.invalid> - 2012-10-12 11:42 -0400
                Re: Glitch in Java Collections (No descendingMap in LinkedHashMap) Jan Burse <janburse@fastmail.fm> - 2012-10-12 21:02 +0200

csiph-web