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

Groups > comp.lang.java.programmer > #19095 > unrolled thread

Glitch in Java Collections (No descendingMap in LinkedHashMap)

Back to article view | Back to comp.lang.java.programmer

Contents

  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

Page 2 of 2 — ← Prev page 1 [2]

#19227

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.

-- 
Jim Janney

[toc] | [prev] | [next] | [standalone]

#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

[toc] | [prev] | [next] | [standalone]

#19229

Jim Janney wrote:
> ... 
> 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.

In Java terminology, an inner class is a non-static nested class, so "non-static
inner class" is redundant.

I cannot get my head around a comparator that uses information from the map 
to decide where in the map the comparator says the insertion should go, given 
that the map uses the comparator to do the insertion into the thing itself the 
comparator needs to decide what the map needs the comparator to decide.

-- 
Lew

[toc] | [prev] | [next] | [standalone]

#19231

Lew <lewbloch@gmail.com> writes:

> Jim Janney wrote:
>> ... 
>> 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.
>
> In Java terminology, an inner class is a non-static nested class, so "non-static
> inner class" is redundant.

Very true.  I sometimes employ redundancy for emphasis, as a stylistic choice.

> I cannot get my head around a comparator that uses information from the map 
> to decide where in the map the comparator says the insertion should go, given 
> that the map uses the comparator to do the insertion into the thing itself the 
> comparator needs to decide what the map needs the comparator to decide.

The ordering is defined by nextInsertionRank.  Making that a member of
the map may not be the best choice.  This is not a finished product,
only a sketch of an approach to the problem.  Some interesting bugs have
been left as an exercise for the reader...

-- 
Jim Janney

[toc] | [prev] | [next] | [standalone]

#19257

Jim Janney <jjanney@shell.xmission.com> writes:

> The ordering is defined by nextInsertionRank.  Making that a member of
> the map may not be the best choice.  This is not a finished product,
> only a sketch of an approach to the problem.  Some interesting bugs have
> been left as an exercise for the reader...

Here is a design I like better.  It reduces the coupling between classes
and better reflects the underlying concepts:

/**
 * Define an arbitrary ordering on a finite set of values.
 * The ordering is determined by the order of calls to {@code register}.
 */
public class ArbitraryOrder<T> implements Comparator<T> {
  private long nextInsertionRank = 0;
  private final Map<T, Long> insertionRanks = new HashMap<T, Long>();
  
  @Override
  public int compare(T o1, T o2) {
    Long rank1 = insertionRanks.get(o1);
    if (rank1 == null) {
      throw new IllegalArgumentException(o1 + " is not registered");
    }
    Long rank2 = insertionRanks.get(o2);
    if (rank2 == null) {
      throw new IllegalArgumentException(o2 + " is not registered");
    }
    return rank1.compareTo(rank2);
  }
  
  public void register(T value) {
    insertionRanks.put(value, nextInsertionRank++);
  }
  
  public void remove(Object key) {
    insertionRanks.remove(key);
  }
}

public class InsertionOrderedMap<K,V> extends TreeMap<K,V> {

  public InsertionOrderedMap() {
    super(new ArbitraryOrder<K>());
  }

  @Override
  public V put(K key, V value) {
    ((ArbitraryOrder<K>)comparator()).register(key);
    return super.put(key, value);
  };
  
  @Override
  public V remove(Object key) {
    V result = super.remove(key);
    ((ArbitraryOrder<K>)comparator()).remove(key);
    return result;
  }
}

-- 
Jim Janney

[toc] | [prev] | [next] | [standalone]

#19239

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.

-- 
Eric Sosman
esosman@comcast-dot-net.invalid

[toc] | [prev] | [next] | [standalone]

#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

[toc] | [prev] | [next] | [standalone]

#19262

Jim Janney schrieb:
>
> 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.
>

Any particular reason you use WeakHashMap?
You have:

   @Override
   public V remove(Object key) {
     insertionRanks.remove(key);
     return super.remove(key);
   }

So I guess an ordinary HashMap would do.

Further your implementation would not generate the
order I desire. It generates an insert-order, but
not a first-insert-order, but last-insert-order
since you have:

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

So when I do:

     put("2","a")
     put("1","b")
     put("2","a")

I get the order "1", "2".
But result should be "2", "1".

Bye

P.S.: It is also not access order as Eric Sosman
claims, since the get() does not influence the order.

[toc] | [prev] | [next] | [standalone]

#19263

Jan Burse <janburse@fastmail.fm> writes:

> Any particular reason you use WeakHashMap?
> You have:
>
>   @Override
>   public V remove(Object key) {
>     insertionRanks.remove(key);
>     return super.remove(key);
>   }
>
> So I guess an ordinary HashMap would do.

I was worried about a potential memory leak, but I hadn't thought it
through.  The keys are held in the TreeMap anyway, so using WeakHashMap
doesn't accomplish anything.

> Further your implementation would not generate the
> order I desire. It generates an insert-order, but
> not a first-insert-order, but last-insert-order
> since you have:
>
>   @Override
>   public V put(K key, V value) {
>     insertionRanks.put(key, nextInsertionRank++);
>     return super.put(key, value);
>   };
>
> So when I do:
>
>     put("2","a")
>     put("1","b")
>     put("2","a")
>
> I get the order "1", "2".
> But result should be "2", "1".
>
> Bye

I missed that.  For first-insert order it should be

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

And for last-insert order the original code is wrong: it should be

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

The tree structure is based on the ordering, so if you change the
ordering you have to modify the tree also.

>
> P.S.: It is also not access order as Eric Sosman
> claims, since the get() does not influence the order.

Right.  For access order you would have to remove the entry and add it
back on every get.

-- 
Jim Janney

[toc] | [prev] | [next] | [standalone]

#19264

On 10/12/2012 8:34 AM, Jan Burse wrote:
> Jim Janney schrieb:
> [...]
> P.S.: It is also not access order as Eric Sosman
> claims, since the get() does not influence the order.

     Not sure whose claim you're disputing, but it wasn't mine.

-- 
Eric Sosman
esosman@comcast-dot-net.invalid

[toc] | [prev] | [next] | [standalone]

#19266

Eric Sosman schrieb:
> n 10/12/2012 8:34 AM, Jan Burse wrote:
>> Jim Janney schrieb:
>> [...]
>> P.S.: It is also not access order as Eric Sosman
>> claims, since the get() does not influence the order.
>
>      Not sure whose claim you're disputing, but it wasn't mine.

I am refering to your:

	"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."

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.lang.java.programmer

csiph-web