Skip to main content

MRUMap

No replies
i30817
Offline
Joined: 2006-05-02
Points: 0

Some time ago i had need to make a MRU (most recently used) Map. I know that the LinkedHashMap class has facilities to make a LRU (least recently used) map, but not the opposite apparently. I also know that jdk 6 will introduce the navigatableMap interface, and i suppose i could use that, however it apparently requires a comparator that compares by insertion (and removal) order. And i believe that is just pushing the work to another place. You see the problem with the code bellow is the remove O(n) calls. These are counterbalanced by only being needed if the value is indeed in the map, but it's pretty common. Replacing the list by something that keeps order and still allows efficient removal would minimize code impact. Unfortunately the skip lists that the ConcurrentSkipWhatever that is in jdk 6 also use a comparator. Any idea how to do this efficiently?

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