Re: ordering of items in a treemap
Andrea Francia wrote:
Lew wrote:
I'm more interested in how one would write a Comparator that knows
about insertion order. This was not illustrated in the suggestion to
subclass TreeMap, and is the biggest difficulty with the approach.
One could mantain a second map of type Map<String,Integer> where records
the key and the insertion index the write a compare method that returns
the difference of the two insertion indexes:
// not thread safe
public InsertionOrderedTreeMap extends TreeMap<String,String> {
Map<String,Integer> insertionIndexes = ...
int lastInsertionIndex = 0;
public InsertionOrderedTreeMap() {
super(new MyComparator());
}
public String put(String key, String value) {
insertionIndexes.put(key,lastInsertionIndexes);
lastInsertionIndex++;
super.put(key,value);
}
private class MyComparator extends Comparator {
public int compare(Object o1, Object o2) {
returns insertionIndexes.get(o2) - insertionIndexes.get(o1);
}
}
}
There could still a memory leak problem because the references hold by
insertionIndexes are never released.
Sure, but wouldn't you remove the insertion index of an entry when it's
removed from the Map?
This is an aspect of the difficulty to which I referred. It's a long way
around the barn to make a TreeMap work for this approach.
Another approach would be to store an internal wrapper object that holds the
value and the inssertion order, and use a Comparator on that field. No
subclassing of TreeMap here, you'd compose a TreeMap (or whatever) and the
nested wrapper class in a custom type.
Also difficult compared to simpler suggestions offered by others on this thread.
--
Lew