Glitch in Java Collections (No descendingMap in LinkedHashMap)

[Jim Janney]

[...]
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]

[...]
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.

 

[Lew]

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

 

[Jim Janney]

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

 

[Eric Sosman]

On 10/10/2012 11:00 AM, Jim Janney wrote:

[...]
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.

 

[Jim Janney]

On 10/10/2012 11:00 AM, Jim Janney wrote:

[...]
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]

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;
}
}

 

[Jan Burse]

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.

 

[Jim Janney]

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.

 

[Eric Sosman]

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.

 

[Jan Burse]

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