65.9K
CodeProject is changing. Read more.
Home

Cache Collection

starIconstarIcon
emptyStarIcon
starIcon
emptyStarIconemptyStarIcon

2.57/5 (4 votes)

Aug 11, 2008

CPOL
viewsIcon

20851

downloadIcon

97

A data structure implementation of a fixed size collection: the oldest element is automatically deleted if the maximum capacity is reached

Introduction

This is a class implementation of a collection with fixed capacity. The oldest elements added to the collection are automatically flushed after the maximum capacity is reached.

Typically, this can be used to cache a collection of objects.
Unlike other caching solutions like those offered in ASP.NET or Enterprise Library, the advantage here is the possibility to loop across the collection.

Using the Code

With a simple collection of strings, you use any other type:

CacheCollection<string> col = new CacheCollection<string>(3);
col.Add("A", "AA");
col.Add("B", "BB");
col.Add("C", "CC");

// access A => it becomes the newest element
string s = col.Get("A");

// the maximum capacity is reached => the oldest element "B" is deleted
col.Add("D", "DD");

When adding D element, B is deleted because it is the oldest.

-- newest --
D
A
C
B <-- deleted
-- oldest --

The Code Implementation

Internally, it uses 2 collections:

  • dic is the dictionary containing the actual values of the collection
  • stack is used to flag the newest element: the higher index contains the key of the newest element

The trick: when the maximum capacity is reached, the element at index 0 is deleted.

public class CacheCollection<T> : IEnumerable<T>
{
   int capacity = 10000;
   Dictionary<string, T> dic;
   List<string> stack = new List<string>(); // new element on top

   public CacheCollection(int capacity)
   {
      dic = new Dictionary<string, T>();
      stack = new List<string>(capacity);
      this.capacity = capacity;
   }

   public void Add(string key, T v)
   {
      if (!dic.ContainsKey(key))
      {
         dic.Add(key, v);
         stack.Add(key);
         if (dic.Count > capacity)
         {
            // delete oldest
            string keyDelete = stack[0];
            stack.RemoveAt(0);
            dic.Remove(keyDelete);
         }
      }
      else
      {
         dic[key] = v;
         BubbleUp(key);
      }
   }

   public T Get(string key)
   {
      if (dic.ContainsKey(key))
      {
          BubbleUp(key);
          return dic[key];
      }
      else
          throw new InvalidOperationException("the collection does not contain the key");
   }

    /// <summary>
    /// Set the element on the top to make it the freshest 
    /// </summary>
    /// <param name="key"></param>
    private void BubbleUp(string key)
    {
       stack.Remove(key);
       stack.Add(key);
    }

    public bool Contains(string key)
    {
       return dic.ContainsKey(key);
    }


    public int Count
    {
       get { return dic.Count; }
    }

    #region IEnumerable<T> Members
    public IEnumerator<T> GetEnumerator()
    {
        return dic.Values.GetEnumerator();
    }
    #endregion

    #region IEnumerable Members
    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        return dic.Values.GetEnumerator();
    }
    #endregion
} 

History

  • 11th August, 2008: Initial post