CircularBuffer IDictionary in C#?

Question

I need a CircularBuffer IDictionary. Can anyone point me to a good open source implementation.

So a IDictionary that has a maximum capacity, say configured to 100 items, which when item 101 is added the original first item is popped/removed from the dictionary thus ensuring the item count never exceeds 100.

Thanks

Answer 1

I don't know of any such implementations, but it doesn't sound hard to implement yourself. Since dictionaries don't have any inherent order, either the key or the value type in the dictionary would need to have some property representing the order in which it was inserted into the dictionary. Then, in your override of the Add method, it could check to see if the count was at the max. If so, then look through the existing key-value pairs to find the one whose insert-order property is lowest and replace it with the new key-value pair. Otherwise, insert the new key-value pair as usual.

Answer 2

Found two after five minutes of googling:

• Free to use, looks like a fully implemented circular buffer: http://www.codeproject.com/KB/recipes/circularbuffer.aspx
  Proof of freeness: http://www.codeproject.com/KB/recipes/circularbuffer.aspx?msg=402807#xx402807xx
• No clear licencing, probably normal copyright, threadsafe, nonboundaried circular buffer: http://blog.umut.tezduyar.com/2008/06/c-circular-buffer-not-thread-safe.html

Answer 3

How about this:

    public class CircularDictionary<TKey, TValue> : Dictionary<TKey, TValue>
    {
        private Queue<TKey> m_ItemInsertList = new Queue<TKey>();
        private int m_ItemsToHold = 100;

        public int ItemsToHold
        {
            get { return m_ItemsToHold; }
            set {
                if (value < 1)
                    throw new ArgumentException("Items to hold must be at least 1");
                m_ItemsToHold = value; 
            }
        }

        public new void Add(TKey key, TValue value)
        {
            base.Add(key, value);
            if (m_ItemInsertList.Count == m_ItemsToHold)
                base.Remove(m_ItemInsertList.Dequeue());
            m_ItemInsertList.Enqueue(key);
        }
    }

Answer 4

To keep O(1) insertion (with removal of the oldest item past 100) and O(1) lookups, you'll need a class that implements IDictionary and keeps an internal ordered list. If memory is more a concern, a BST implementation like SortedList could be more appropriate. Anyway, your class will contain both a T[] and a Dictionary<T,K> (or SortedList<T,K>). Do your own circular buffer indexing (easy), and keep both collections current in the add, remove, etc. methods. You'll have:

• O(1) enqueue (to back)
• O(n) insertion that violates order of adding (since you have to keep the array up to date); you'll likely never need this anyway
• O(1) dequeue (from front)
• O(1) or O(log n) keyed lookup

Make it generic and implement IDictionary<T,K> and IDictionary since there's no reason not to and you'll get an edge in performance.

One major consideration: what do you do about duplicate keys? I'm assuming you can't actually keep the duplicates, so:

• Throw an exception (if there are never duplicate keys, so it's simply an error to insert something twice)
• Move to back: check the Count of the dictionary, then insert the key using the this[key] indexer. if the size increases, then check if the list already has the maximum capacity, remove the front item from the list and dictionary and add the new item to the back. If the dictionary did not increase in size, move the item from its existing place in the list to the back of the list.
• Overwrite without moving: The same as the previous item, but you don't have to mess with the list.

Finally, note that the internal list keeps keys, not values. This is to ensure O(1) dequeue when the list capacity is exceeded.

Answer 5

I wrote a complete implementation of a circular buffer in C# 3.0 not too long ago, and release the source on CodePlex. It follows BCL design guidelines, and implements all the appropiate interfaces from System.Collections.

I believe it should be very easy to adapt to use a Dictionary<TKey, TValue> as the backing collection instead of a List<T>.

Answer 6

I've implemented something akin to this by using a SQLite database table via the System.Data.Sqlite (http://sqlite.phxsoftware.com/) wrapper. You can store it on disk or as an in-memory database. You can choose whether or not to have unique keys and let the database engine handle the indexing for you. You can even have multiple values per key.

As you write to the table, check to see if you're at the 100-record limit, and if so then delete before inserting. SQLite supports an "insert or replace" command if you want to preserve unique keys. Perhaps this isn't as elegant as a custom IDictionary derivation, but it works, it's flexible, and it's readily shared across threads.