Efficient modelling of an MruList in C# or Java

Question

How would you implement a capacity-limited, generic MruList in C# or Java?

I want to have a class that represents a most-recently-used cache or list (= MruList). It should be generic, and limited to a capacity (count) specified at instantiation. I'd like the interface to be something like:

public interface IMruList<T>
{
    public T Store(T item);
    public void Clear();
    public void StoreRange(T[] range);
    public List<T> GetList();
    public T GetNext(); // cursor-based retrieval
}

Each Store() should put the item at the top (front?) of the list. The GetList() should return all items in an ordered list, ordered by most recent store. If I call Store() 20 times and my list is 10 items long, I only want to retain the 10 most-recently Stored items. The GetList and StoreRange is intended to support retrieval/save of the MruList on app start and shutdown.

This is to support a GUI app. I guess I might also want to know the timestamp on a stored item. Maybe. Not sure.

Internally, how would you implement it, and why?

(no, this is not a course assignment)

Answer 1

Couple of comments about your approach

• Why have Store return T? I know what I just added, returning it back to me is un-necessary unless you explicitly want method chaining
• Refactor GetNext() into a new class. It represents a different set of functionality (storage vs. cursor traversal) and should be represented by a separate interface. It also has usability concerns as what happens when two different methods active on the same stack want to traverse the structure?
• GetList() should likely return IEnumerable<T>. Returning List<T> either forces an explicit copy up front or returns a pointer to an underlying implementation. Neither is a great choice.

As for what is the best structure to back the interface. It seems like the best to implement is to have a data structure which is efficient at adding to one end, and removing from the other. A doubly linked list would suit this nicely.

Answer 2

I would have an internal ArrayList and have Store() delete the last element if its size exceeds the capacity established in the constructor. I think standard terminology, strangely enough, calls this an "LRU" list, because the least-recently-used item is what gets discarded. See wikipedia's entry for this.

Answer 3

You can build this up with a Collections.Generic.LinkedList<T>. When you push an item into a full list, delete the last one and insert the new one at the front. Most operations should be in O(1) which is better than a array-based implementation.

Answer 4

Here's a Cache class that stores objects by the time they were accessed. More recent items bubble to the end of the list. The cache operates off an indexer property that takes an object key. You could easily replace the internal dictionary to a list and reference the list from the indexer.

BTW, you should rename the class to MRU as well :)

class Cache
    {
        Dictionary<object, object> cache = new Dictionary<object, object>();

        /// <summary>
        /// Keeps up with the most recently read items.
        /// Items at the end of the list were read last. 
        /// Items at the front of the list have been the most idle.
        /// Items at the front are removed if the cache capacity is reached.
        /// </summary>
        List<object> priority = new List<object>();
        public Type Type { get; set; }
        public Cache(Type type)
        {
            this.Type = type;

            //TODO: register this cache with the manager 

        }
        public object this[object key]
        { 
            get 
            {
                lock (this)
                {
                    if (!cache.ContainsKey(key)) return null;
                    //move the item to the end of the list                    
                    priority.Remove(key);
                    priority.Add(key);
                    return cache[key];
                }
            }
            set 
            {
                lock (this)
                {
                    if (Capacity > 0 && cache.Count == Capacity)
                    {
                        cache.Remove(priority[0]);
                        priority.RemoveAt(0);
                    }
                    cache[key] = value;
                    priority.Remove(key);
                    priority.Add(key);

                    if (priority.Count != cache.Count)
                        throw new Exception("Capacity mismatch.");
                }
            }
        }
        public int Count { get { return cache.Count; } }
        public int Capacity { get; set; }

        public void Clear()
        {
            lock (this)
            {
                priority.Clear();
                cache.Clear();
            }
        }
    }

Answer 5

In Java, I'd use the LinkedHashMap, which is built for this sort of thing.

public class MRUList<E> implements Iterable<E> {
    private final LinkedHashMap<E, Void> backing;

    public MRUList() {
        this(10);
    }

    public MRUList(final int maxSize) {
        this.backing = new LinkedHashMap<E,Void>(maxSize, maxSize, true){
           private final int MAX_SIZE = maxSize;
           @Override
           protected boolean removeEldestEntry(Map.Entry<E,Void> eldest){
               return size() > MAX_SIZE;
           }
        };
    }

    public void store(E item) {
        backing.put(item, null);
    }

    public void clear() {
        backing.clear();
    }

    public void storeRange(E[] range) {
        for (E e : range) {
            backing.put(e, null);
        }
    }

    public List<E> getList() {
        return new ArrayList<E>(backing.keySet());
    }

    public Iterator<E> iterator() {
        return backing.keySet().iterator();
    }
}

However, this does iterate in exactly reverse order (i.e. LRU first, MRU last). Making it MRU-first would require basically reimplementing LinkedHashMap but inserting new elements at the front of the backing list, instead of at the end.

Answer 6

Java 6 added a new Collection type named Deque... for Double-ended Queue.

There's one in particular that can be given a limited capacity: LinkedBlockingDeque.

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.LinkedBlockingDeque;

public class DequeMruList<T> implements IMruList<T> {

    private LinkedBlockingDeque<T> store;

    public DequeMruList(int capacity) {
     store = new LinkedBlockingDeque<T>(capacity);
    }

    @Override
    public void Clear() {
     store.clear();
    }

    @Override
    public List<T> GetList() {
     return new ArrayList<T>(store);
    }

    @Override
    public T GetNext() {
 // Get the item, but don't remove it
     return store.peek();
    }

    @Override
    public T Store(T item) {
     boolean stored = false;
     // Keep looping until the item is added
     while (!stored) {
      // Add if there's room
      if (store.offerFirst(item)) {
       stored = true;
      } else {
       // No room, remove the last item
       store.removeLast();
      }
     }
     return item;
    }

    @Override
    public void StoreRange(T[] range) {
     for (T item : range) {
      Store(item);
     }
    }

}

Answer 7

Everyone enjoys rolling their own container classes.

But in the .NET BCL there is a little gem called SortedList<T>. You can use this to implement your MRU list or any other priority-queue type list. It uses an efficient tree structure for efficient additions.

From SortedList on MSDN:

The elements of a SortedList object are sorted by the keys either according to a specific IComparer implementation specified when the SortedList is created or according to the IComparable implementation provided by the keys themselves. In either case, a SortedList does not allow duplicate keys.

The index sequence is based on the sort sequence. When an element is added, it is inserted into SortedList in the correct sort order, and the indexing adjusts accordingly. When an element is removed, the indexing also adjusts accordingly. Therefore, the index of a specific key/value pair might change as elements are added or removed from the SortedList object.

Operations on a SortedList object tend to be slower than operations on a Hashtable object because of the sorting. However, the SortedList offers more flexibility by allowing access to the values either through the associated keys or through the indexes.

Elements in this collection can be accessed using an integer index. Indexes in this collection are zero-based.