Data Structure for Dictionary with Max Size

Question

Possible Duplicate:
Is it there any LRU implementation of IDictionary?

I'm looking for a data structure that is like a dictionary but can only contain a set number of key value pairs. When a key value pair is added to a dictionary that is already full then a key value pair that hasn't been accessed recently would be removed.

Does anything like this already exist for C#?

I remember implementing something like this for an operating systems class and the data structure was used to decide which portion of RAM should be paged to disk. This was done by associating a reference bit with each key value pair which was set to true when the pair was accessed. When a pair needed to be removed the key values pairs would be iterated over until one was found with it's reference bit set to false. The reference bit of each pair iterated over would be set to false and the last one would be removed.

If a data structure for this doesn't already exist in C# then would the algorithm I described be a good way to implement it?

score 0 · Accepted Answer · answered Feb 03 '13 at 21:55

Looks like there aren't any implementations of this already in the .Net framework so here is what I ended up using

using System.Collections.Generic;
using System.Linq;

namespace MyProject.Util
{
public class LruCache<Key, Value>
{
    public delegate Value ValueCreator();

    Dictionary<Key, ValueWithReference> cache;

    //The maximum number of elements that can fit in the cache.
    int maxCacheSize;

    IEnumerator<Value> valueRemover;

    public LruCache(int maxCacheSize) {
        this.cache = new Dictionary<Key, ValueWithReference>();
        this.maxCacheSize = maxCacheSize;
        this.valueRemover = GetKeyValuePairRemover().GetEnumerator();
    }

    /// <summary>
    /// Gets the value associated with the specified key. If it doesn't exist in the cache 
    /// then it will be created with createValue() and added to the cache. 
    /// </summary>
    public Value GetAndAddValue(Key key, ValueCreator createValue) {
        if (this.cache.ContainsKey(key) == false)
        {
            while (this.cache.Count >= this.maxCacheSize) {
                this.valueRemover.MoveNext();
            }

            this.cache[key] = new ValueWithReference(createValue());
        }

        this.cache[key].recentlyUsed = true;
        return this.cache[key].value;

    }

    protected IEnumerable<Value> GetKeyValuePairRemover() { 
        while (true) {
            List<Key> keyList = this.cache.Keys.ToList();

            foreach(Key key in keyList) {
                if (this.cache[key].recentlyUsed)
                {
                    this.cache[key].recentlyUsed = false;
                }
                else {
                    Value removedValue = this.cache[key].value;
                    this.cache.Remove(key);
                    yield return removedValue;
                }
            }

        }
    }

    protected class ValueWithReference
    {
        public Value value;
        public bool recentlyUsed;

        public ValueWithReference(Value value)
        {
            this.value = value;
            this.recentlyUsed = true;
        }
    }
}
}

Data Structure for Dictionary with Max Size

1 Answers1