using System.Collections.Generic;
using System.Linq;
namespace UndauntedTK.Utility
{
    public class LFUCache<TKey, TValue>
    {
        private readonly int _agePolicy;

        private readonly Dictionary<TKey, LinkedListNode<CacheNode>> _cache =
            new Dictionary<TKey, LinkedListNode<CacheNode>>();

        private readonly LinkedList<CacheNode> _lfuList = new LinkedList<CacheNode>();

        private readonly int _size;
        private int _age;

        public LFUCache(int size)
            : this(size, 1000)
        {
        }


        /// <summary>
        ///
        /// </summary>
        /// <param name="size"></param>
        /// <param name="agePolicy">after this number of gets the cache will take 1 off all UseCounts, forcing old stuff to expire.</param>
        public LFUCache(int size, int agePolicy)
        {
            _agePolicy = agePolicy;
            _size = size;
        }

        private IEnumerable<LinkedListNode<CacheNode>> Nodes
        {
            get
            {
                LinkedListNode<CacheNode> node = _lfuList.First;
                while (node != null)
                {
                    yield return node;
                    node = node.Next;
                }
            }
        }

        private void Remove(TKey key)
        {
            _lfuList.Remove(_cache[key]);
            _cache.Remove(key);
        }

        public void Add(TKey key, TValue val)
        {
            TValue existing;
            if (!TryGet(key, out existing))
            {
                var node = new CacheNode { Key = key, Data = val, UseCount = 1 };
                if (_lfuList.Count == _size)
                {
                    _cache.Remove(_lfuList.First.Value.Key);
                    _lfuList.RemoveFirst();
                }

                LinkedListNode<CacheNode> insertionPoint = Nodes.LastOrDefault(n => n.Value.UseCount < 2);

                LinkedListNode<CacheNode> inserted;

                inserted = insertionPoint == null ? _lfuList.AddFirst(node) : _lfuList.AddAfter(insertionPoint, node);
                _cache[key] = inserted;
            }
            else
            {
                Remove(key);
                Add(key, val);
            }
        }

        private static IEnumerable<LinkedListNode<CacheNode>> IterateFrom(LinkedListNode<CacheNode> node)
        {
            while (node != null)
            {
                yield return node;
                node = node.Next;
            }
        }

        public TValue GetOrDefault(TKey key)
        {
            TValue val;
            TryGet(key, out val);
            return val;
        }

        public bool TryGet(TKey key, out TValue val)
        {
            _age++;
            if (_age > _agePolicy)
            {
                _age = 0;
                foreach (var node in _cache.Values)
                {
                    CacheNode v = node.Value;
                    v.UseCount--;
                }
            }

            LinkedListNode<CacheNode> data;
            bool success = false;

            if (_cache.TryGetValue(key, out data))
            {
                CacheNode cacheNode = data.Value;
                val = cacheNode.Data;
                cacheNode.UseCount++;
                success = true;
                LinkedListNode<CacheNode> insertionPoint =
                    IterateFrom(data).Last(n => n.Value.UseCount <= cacheNode.UseCount);

                if (insertionPoint != data)
                {
                    _lfuList.Remove(data);
                    _lfuList.AddAfter(insertionPoint, data);
                }
            }
            else
            {
                val = default(TValue);
            }

            return success;
        }

        #region Nested type: CacheNode

        private class CacheNode
        {
            public TKey Key { get; set; }
            public TValue Data { get; set; }
            public int UseCount { get; set; }
        }

        #endregion
    }
}