using System;
using System.Collections.Generic;

namespace DataStructures.Cache
{
    /// <summary>
    /// Least Recently Used (LRU) cache implementation.
    /// </summary>
    /// <typeparam name="TKey">The type of the key (must be not null).</typeparam>
    /// <typeparam name="TValue">The type of the value.</typeparam>
    /// <remarks>
    /// Cache keeps up to <c>capacity</c> items. When new item is added and cache is full,
    /// the least recently used item is removed (e.g. it keeps N items that were recently requested
    /// using <c>Get()</c> or <c>Put()</c> methods).
    ///
    /// Cache is built on top of two data structures:
    /// - <c>Dictionary</c> - allows items to be looked up by key in O(1) time.
    /// - <c>LinkedList</c> - allows items to be ordered by last usage time in O(1) time.
    ///
    /// Useful links:
    /// https://en.wikipedia.org/wiki/Cache_replacement_policies
    /// https://www.educative.io/m/implement-least-recently-used-cache
    /// https://leetcode.com/problems/lru-cache/
    ///
    /// In order to make the most recently used (MRU) cache, when the cache is full,
    /// just remove the last node from the linked list in the method <c>Put</c>
    /// (replace <c>RemoveFirst</c> with <c>RemoveLast</c>).
    /// </remarks>
    public class LruCache<TKey, TValue> where TKey : notnull
    {
        private class CachedItem
        {
            public TKey Key { get; set; } = default!;

            public TValue? Value { get; set; }
        }

        private const int DefaultCapacity = 100;

        private readonly int capacity;

        // Note that <c>Dictionary</c> stores <c>LinkedListNode</c> as it allows
        // removing the node from the <c>LinkedList</c> in O(1) time.
        private readonly Dictionary<TKey, LinkedListNode<CachedItem>> cache = new();
        private readonly LinkedList<CachedItem> lruList = new();

        /// <summary>
        /// Initializes a new instance of the <see cref="LruCache{TKey, TValue}"/> class.
        /// </summary>
        /// <param name="capacity">The max number of items the cache can store.</param>
        public LruCache(int capacity = DefaultCapacity)
        {
            this.capacity = capacity;
        }

        public bool Contains(TKey key) => cache.ContainsKey(key);

        /// <summary>
        /// Gets the cached item by key.
        /// </summary>
        /// <param name="key">The key of cached item.</param>
        /// <returns>The cached item or <c>default</c> if item is not found.</returns>
        /// <remarks> Time complexity: O(1). </remarks>
        public TValue? Get(TKey key)
        {
            if (!cache.ContainsKey(key))
            {
                return default;
            }

            var node = cache[key];
            lruList.Remove(node);
            lruList.AddLast(node);

            return node.Value.Value;
        }

        /// <summary>
        /// Adds or updates the value in the cache.
        /// </summary>
        /// <param name="key">The key of item to cache.</param>
        /// <param name="value">The value to cache.</param>
        /// <remarks>
        /// Time complexity: O(1).
        /// If the value is already cached, it is updated and the item is moved
        /// to the end of the LRU list.
        /// If the cache is full, the least recently used item is removed.
        /// </remarks>
        public void Put(TKey key, TValue value)
        {
            if (cache.ContainsKey(key))
            {
                var existingNode = cache[key];
                existingNode.Value.Value = value;
                lruList.Remove(existingNode);
                lruList.AddLast(existingNode);
                return;
            }

            if (cache.Count >= capacity)
            {
                var first = lruList.First!;
                lruList.RemoveFirst();
                cache.Remove(first.Value.Key);
            }

            var item = new CachedItem { Key = key, Value = value };
            var newNode = lruList.AddLast(item);
            cache.Add(key, newNode);
        }
    }
}