I’m trying to do a most recently used map, but i’d like the remove calls to be gone - O(N) - but the sets have no linear view, or their linear view is based on comparators, and i can’t think of a comparator that implements access ordering - and especially not a efficient one.
I was thinking about skip-lists too…
package util;
import java.util.AbstractCollection;
import java.util.AbstractSet;
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
/**
* A simple (ie broken for multipurpose) MRU map.
* The iteration order is the opposite of the
* JDK LinkedHashMap LRU configuration.
* (from most to least recently accessed).
*
* In this class putting or getting a value
* will modify iteration order, but setting
* or getting a value from the iterators, will
* NOT change the next or current order.
*
* The iterators of this class are fail fast.
* So no structural modification
* outside of the iterators when using them,
* or unsynchonized access to them if working
* with threads. Ok?
*/
public class MRUMap<K, V> extends HashMap<K, V> {
private final LinkedList<K> set = new LinkedList<K>();
private final int MAX_ENTRIES;
private static final long serialVersionUID = 3221271453622736157L;
public MRUMap() {
super();
MAX_ENTRIES = 100;
}
public MRUMap(final int maxEntries) {
super();
MAX_ENTRIES = maxEntries;
}
@Override
public V put(final K key, final V value) {
//to create access order instead of insertion order
if (super.containsKey(key)) {
set.remove(key);
}
set.addFirst(key);
if (removeEldestEntries()) {
super.remove(set.removeLast());
}
return super.put(key, value);
}
@Override
@SuppressWarnings(value = "unchecked")
public V get(final Object key) {
if (super.containsKey(key)) {
set.remove(key);
set.addFirst((K) key);
return super.get(key);
}
return null;
}
@Override
public V remove(final Object key) {
if (super.containsKey(key)) {
set.remove(key);
return super.remove(key);
}
return null;
}
@Override
public void clear() {
set.clear();
super.clear();
}
/**
* Used to tell if the eldest entry
* should be removed when adding to
* the map.
*/
protected boolean removeEldestEntries() {
return size() > MAX_ENTRIES;
}
/**
* Used to tell the number of entries
* to remove on the putAll method.
* This method shoud be consistent with
* removeEldestEntries, ie when it returns true,
* this method should return a value > 0
*/
protected int eldestEntries() {
return size() - MAX_ENTRIES;
}
@Override
public void putAll(Map<? extends K, ? extends V> t) {
if (set.isEmpty()) {
for (Map.Entry<? extends K, ? extends V> e : t.entrySet()) {
set.addFirst(e.getKey());
super.put(e.getKey(), e.getValue());
}
} else {
for (Map.Entry<? extends K, ? extends V> e : t.entrySet()) {
if (super.containsKey(e)) {
set.remove(e);
}
set.addFirst(e.getKey());
super.put(e.getKey(), e.getValue());
}
}
if(removeEldestEntries()){
ListIterator<K> i = set.listIterator(set.size() - eldestEntries());
while(i.hasNext()){
super.remove(i.next());
i.remove();
}
}
}
@Override
public Set<K> keySet() {
return new AbstractSet<K>() {
@SuppressWarnings("unchecked")
public Iterator<K> iterator() {
return new KeyIt();
}
public int size() {
return set.size();
}
};
}
@Override
public Collection<V> values() {
return new AbstractCollection<V>() {
@SuppressWarnings("unchecked")
public Iterator<V> iterator() {
return new ValueIt();
}
public int size() {
return set.size();
}
};
}
@Override
public Set<Map.Entry<K, V>> entrySet() {
return new AbstractSet<Entry<K, V>>() {
@SuppressWarnings("unchecked")
public Iterator<Entry<K, V>> iterator() {
return new EntryIt();
}
public int size() {
return set.size();
}
};
}
private final class EntryIt extends LRUIterator {
public Object next() {
return nextEntry();
}
}
private final class KeyIt extends LRUIterator {
public Object next() {
return nextKey();
}
}
private final class ValueIt extends LRUIterator {
public Object next() {
return nextValue();
}
}
private abstract class LRUIterator implements Iterator {
private Iterator<K> it = set.iterator();
public K current;
public boolean hasNext() {
return it.hasNext();
}
Map.Entry<K, V> nextEntry() {
current = it.next();
return new EntryImpl();
}
V nextValue() {
current = it.next();
return MRUMap.super.get(current);
}
K nextKey() {
return it.next();
}
public void remove() {
it.remove();
MRUMap.super.remove(current);
}
private final class EntryImpl implements Entry<K, V> {
private EntryImpl() {
}
public K getKey() {
return current;
}
public V getValue() {
return MRUMap.super.get(current);
}
public V setValue(V value) {
return MRUMap.super.put(current, value);
}
}
}
}
