lfu.cs

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication3
{
    class UsageNode<TKey>
    {
        public int Usage { get; set; }
        public LinkedList<KeyNode<TKey>> KeyList { get; set; }
    }

    class KeyNode<TKey>
    {
        public TKey Key { get; set; }
        public LinkedListNode<UsageNode<TKey>> ParentUsage { get; set; }
    }

    class DataNode<TKey, TValue>
    {
        public TValue Value { get; set; }
        public LinkedListNode<KeyNode<TKey>> KeyNode { get; set; }
    }

    class LFUCache<TKey, TValue>
    {
        private readonly int cacheSize;
        private readonly Dictionary<TKey, DataNode<TKey, TValue>> _data;
        private readonly LinkedList<UsageNode<TKey>> _usageList;
        public int Count => _data.Count;

        public LFUCache(int cacheSize)
        {
            this.cacheSize = cacheSize;
            _data = new Dictionary<TKey, DataNode<TKey, TValue>>(this.cacheSize);
            _usageList = new LinkedList<UsageNode<TKey>>();
        }

        public void Set(TKey key, TValue value)
        {
            if (_data.ContainsKey(key))
            {
                var node = _data[key].KeyNode.Value;
                _data.Remove(key);

                node.ParentUsage.Value.KeyList.Remove(node);

                if (node.ParentUsage.Value.KeyList.Count == 0)
                {
                    _usageList.Remove(node.ParentUsage);
                }
            }

            if (_data.Count >= this.cacheSize)
            {
                //removing a key from usage tree

                var first = _usageList.First.Value.KeyList.First;
                _data.Remove(first.Value.Key);
                _usageList.First.Value.KeyList.Remove(first);
                if (_usageList.First.Value.KeyList.Count == 0)
                {
                    _usageList.Remove(_usageList.First);
                }
            }

            if (_usageList.Count == 0 || _usageList.First.Value.Usage != 1)
            {
                var usageHead = new UsageNode<TKey>
                {
                    Usage = 1,
                    KeyList = new LinkedList<KeyNode<TKey>>()
                };

                _usageList.AddFirst(usageHead);
            }

            var newKeyNode = new KeyNode<TKey>()
            {
                Key = key,
                ParentUsage = _usageList.First
            };
            var newUsageNode = _usageList.First.Value.KeyList.AddFirst(newKeyNode);
            _data.Add(key, new DataNode<TKey, TValue>
            {
                Value = value,
                KeyNode = newUsageNode
            });
        }

        public TValue Get(TKey key)
        {
            if (!_data.ContainsKey(key))
            {
                throw new ArgumentException("No such key");
            }
            var returnValue = _data[key];

            var usageCurrent = returnValue.KeyNode.Value.ParentUsage;
            LinkedListNode<UsageNode<TKey>> usageNext = null;
            if (usageCurrent.Next == null || (usageCurrent.Next.Value.Usage != usageCurrent.Value.Usage + 1))
            {
                var usagenode = new UsageNode<TKey>()
                {
                    Usage = usageCurrent.Value.Usage + 1,
                    KeyList = new LinkedList<KeyNode<TKey>>()
                };

                usageNext = _usageList.AddAfter(usageCurrent, usagenode);
            }
            else
            {
                usageNext = usageCurrent.Next;
            }

            returnValue.KeyNode.Value.ParentUsage.Value.KeyList.Remove(returnValue.KeyNode);
            if (returnValue.KeyNode.Value.ParentUsage.Value.KeyList.Count == 0)
            {
                _usageList.Remove(returnValue.KeyNode.Value.ParentUsage);
            }

            usageNext.Value.KeyList.AddFirst(returnValue.KeyNode);
            returnValue.KeyNode.Value.ParentUsage = usageNext;

            return returnValue.Value;
        }

        public Dictionary<TKey, TValue> ToDictionary()
        {
            return _data.ToDictionary(x => x.Key, x => x.Value.Value);
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            var cache = new LFUCache<string, int>(2);
            cache.Set("a", 1);
            Console.WriteLine(cache.Get("a"));
            Console.WriteLine(cache.Get("a"));
            cache.Set("b", 2);
            cache.Get("b");
            cache.Set("c", 3);

            foreach (var kv in cache.ToDictionary())
            {
                Console.WriteLine($"K: {kv.Key} V:{kv.Value}");
            }
            Console.WriteLine($"Count {cache.Count}");
            Console.ReadKey(true);
        }
    }
}