/**

Written by Saurabh Gupta on 5/18/2015

*/

using System;

using System.Collections.Generic;

using System.Diagnostics;

using System.Linq;

​

public class Program

{

    public static void Main()

    {

        Debug.Listeners.Add(new TextWriterTraceListener(System.Console.Out));

        Debug.WriteLine("Testing...");

        //testing

        var memCache = new Cache<string,string>();

        Debug.WriteLine("Cache class testing...");

        //Test the Cache class

        memCache.create(2,new EvictMock1<string>());

        Debug.WriteLine(memCache != null);

        Debug.WriteLine(memCache.get("any-item") == null);

        Debug.WriteLine(memCache.exists("any-item") == false);

        memCache.add("key1","value1");

        Debug.WriteLine(memCache.get("key1") == "value1");

        memCache.add("key2","value2");

        Debug.WriteLine(memCache.exists("key2") == true);

        memCache.add("key3", "value2");

        Debug.WriteLine(memCache.exists("key3") == false);

        //Test eviction strategies

        Debug.WriteLine("FIFO testing...");

        //FIFO

        IEvictionStrategy<string> fifo = new EvictFIFO<string>();

        fifo.SetSize(2);

        var keyToRemove = fifo.OnAdd("key1");

        Debug.WriteLine(keyToRemove == null);

        keyToRemove = fifo.OnAdd("key2");

        Debug.WriteLine(keyToRemove == null);

        keyToRemove = fifo.OnAdd("key3");

        Debug.WriteLine(keyToRemove == "key1");

​

        Debug.WriteLine("LRU testing...");      

        //LRU

        IEvictionStrategy<string> lru = new EvictLRU<string>();

        lru.SetSize(2);

        keyToRemove = lru.OnAdd("key1");

        Debug.WriteLine(keyToRemove == null);

        System.Threading.Thread.Sleep(TimeSpan.FromSeconds(0.5));

        keyToRemove = lru.OnAdd("key2");

        Debug.WriteLine(keyToRemove == null);

​

        System.Threading.Thread.Sleep(TimeSpan.FromSeconds(0.5));

        keyToRemove = lru.OnAdd("key3");

        Debug.WriteLine(keyToRemove == "key1");

​

        System.Threading.Thread.Sleep(TimeSpan.FromSeconds(0.5));

        lru.OnGet("key2");

        System.Threading.Thread.Sleep(TimeSpan.FromSeconds(0.5));       

        keyToRemove = lru.OnAdd("key4");

        Debug.WriteLine(keyToRemove == "key3");

        System.Threading.Thread.Sleep(TimeSpan.FromSeconds(0.5));   

        keyToRemove = lru.OnAdd("key5");

        Debug.WriteLine(keyToRemove == "key2");

        //random strategy testing

        Debug.WriteLine("Random strategy testing...");  

        IEvictionStrategy<string> random = new EvictRandom<string>();

        memCache = new Cache<string,string>();

        memCache.create(5,random);

        memCache.add("key1","value1");

        memCache.add("key2","value2");

        memCache.add("key3","value3");

        memCache.add("key4","value4");

        memCache.add("key5","value5");      

        Debug.WriteLine((new string[]{"key1","key2","key3","key4","key5"}).Count(o=> memCache.exists(o)) == 5);

        memCache.add("key6","value6");              

​

        Debug.WriteLine(memCache.exists("key6"));

        Debug.WriteLine((new string[]{"key1","key2","key3","key4","key5"}).Count(o=>!memCache.exists(o)) == 1);     

    }

}

​

public class Cache<T1, T2>

{

    private IDictionary<T1, T2> _inMemoryCache;

    private IEvictionStrategy<T1> _evictionStrategy;

    private int _size;

    public void create(int size, IEvictionStrategy<T1> evictionStrategy)

    {

        if (_inMemoryCache == null)

        {

            _inMemoryCache = new Dictionary<T1, T2>(size); //this size just sets the initial size of collection

        }

​

        _size = size;

        _evictionStrategy = evictionStrategy;

        _evictionStrategy.SetSize(size);

    }

​

    public void add(T1 key, T2 keyValue)

    {

        Debug.Assert(_inMemoryCache != null);

        Debug.Assert(_evictionStrategy != null);

        if (_inMemoryCache.ContainsKey(key))

            _inMemoryCache[key] = keyValue;

        else

            _inMemoryCache.Add(key, keyValue);

        T1 keyToRemove = _evictionStrategy.OnAdd(key);

        if(keyToRemove != null)

            _inMemoryCache.Remove(keyToRemove);

        Debug.Assert(_inMemoryCache.Count <= _size);

    }

​

    public T2 get(T1 key)

    {

        if (_inMemoryCache == null || !_inMemoryCache.ContainsKey(key))

        {

            return default(T2);

        }

​

        Debug.Assert(_evictionStrategy != null);

        _evictionStrategy.OnGet(key);

        return _inMemoryCache[key];

    }

​

    public bool exists(T1 key)

    {

        if (_inMemoryCache == null || !_inMemoryCache.ContainsKey(key))

        {

            return false;

        }

​

        return true;

    }

}

​

public interface IEvictionStrategy<T1>

{

    T1 OnAdd(T1 key);

    void OnGet(T1 key);

    void SetSize(int size);

}

​

public class EvictMock1<T1> : IEvictionStrategy<T1>

{

    private int _size;

    private List<T1> _list;

    public T1 OnAdd(T1 key)

    {

        if(_list.Count == _list.Capacity)

        {

            return key;

        }

        else {

            _list.Add(key);

        }

        return default(T1);

    }

    public void OnGet(T1 key)

    {

        Debug.WriteLine("OnGet Called " + key.ToString());

    }

    public void SetSize(int size)

    {

        _size = size;

        _list = new List<T1>(size);

    }

}

​

​

public class EvictLRU<T1> : IEvictionStrategy<T1>

{

    private Dictionary<T1, long> _list;

    private int _size;

    public T1 OnAdd(T1 key)

    {

        T1 keyToRemove = default(T1);

        if(!_list.ContainsKey(key)){

            if(_list.Count >= _size) //if list is full

            {

                var enumerator = _list.GetEnumerator();

                long oldest = long.MaxValue;

                while(enumerator.MoveNext())

                {

                    if(oldest > enumerator.Current.Value){

                        keyToRemove = enumerator.Current.Key;

                        oldest = enumerator.Current.Value;

                    }

                }

                _list.Remove(keyToRemove);

            }

            _list.Add(key,DateTime.UtcNow.Ticks);

        }

        else{

            _list[key] = DateTime.UtcNow.Ticks;

        }

        return keyToRemove;

    }

​

    public void OnGet(T1 key)

    {

        _list[key] = DateTime.UtcNow.Ticks;

    }

​

    public void SetSize(int size)

    {

        _size = size;

        _list = new Dictionary<T1, long>(size);

    }

}

​

public class EvictFIFO<T1> : IEvictionStrategy<T1>

{

    private Queue<T1> _list;

    private int _size;

    public T1 OnAdd(T1 key)

    {

        T1 keyToRemove = default(T1);

        Debug.Assert(_list != null, "Call SetSize method before calling this method");

        if(!_list.Contains(key) && _list.Count >= _size){ //get keytoremove if key is not in there  and queue is full

            T1[] keyArray = _list.ToArray();

            keyToRemove = keyArray[0];

        }

        else{ //If it is in queue, createa a new queue without this key

            var newList = new List<T1>(_size);

            var enumerator = _list.GetEnumerator();

            while(enumerator.MoveNext() && !enumerator.Current.Equals(key))

                newList.Add(enumerator.Current);

            _list = new Queue<T1>(newList);

        }

        //Finally put in queue the key

        _list.Enqueue(key);

        //return key if determined to be removed

        return keyToRemove;

    }

​

    public void OnGet(T1 key)

    {

        //do nothing

    }

​

    public void SetSize(int size)

    {

        _size = size;

        _list = new Queue<T1>(size);

    }

}

​

public class EvictRandom<T1> : IEvictionStrategy<T1>

{

    private int _size;

    private List<T1> _list;

    public T1 OnAdd(T1 key)

    {   

        T1 keyToRemove = default(T1);

        if(_list.Count >= _size && !_list.Contains(key)){

            //get key to be removed

            int indexToRemove = new Random().Next(_size);

            keyToRemove = _list[indexToRemove];

            _list.RemoveAt(indexToRemove);

        }

        else if (!_list.Contains(key)){

            _list.Add(key);

        }

        return keyToRemove;

    }

​

    public void OnGet(T1 key)

    {

    //do nothing

    }

​

    public void SetSize(int size)

    {

        _size = size;

        _list = new List<T1>(size);

    }

}