Efficient MruList Modeling in C # or Java

Question

How would you implement the universal MruList with limited features in C # or Java?

I want to have a class representing the most used cache or list (= MruList). It must be general and limited by the capacity (counter) specified when creating the instance. I would 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 place an item at the top (in front?) Of the list. GetList () should return all the items in an ordered list, sorted by the last store. If I call Store () 20 times and my list lasts 10, I want to save only the 10 most recently stored items. GetList and StoreRange are designed to support finding / saving MruList when the application starts and shuts down.

This is a graphical interface support. I think I might also need to know the timestamp for the saved item. May be. Not sure.

Inside, how do you implement it and why?

(no, this is not a course assignment)

Answer 1

A few comments about your approach

• Why return Store T? I know that I just added, I don’t need to return it unless you explicitly want the method chain
• Refactor GetNext() . ( ) . , , , , , ?
• GetList() IEnumerable<T>. List<T> , . .

. , , , . .

Answer 2

Cache, . . , . .

, MRU:)

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 3

ArrayList Store() , , . , , , " LRU", - , . . wikipedia.

Answer 4

Collections.Generic.LinkedList<T>. , . O (1), , .

Answer 5

.

.NET BCL , SortedList<T>. MRU . .

SortedList MSDN:

SortedList IComparer , SortedList IComparable . , SortedList .

. , SortedList . , . / SortedList.

SortedList , Hashtable - . SortedList , .

. .

Answer 6

Java LinkedHashMap, .

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

(.. LRU, MRU - ). MRU-first LinkedHashMap, , .

Answer 7

Java 6 Deque... Double-End Queue.

, , ​​ : 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 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);
        }
    }

}