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

namespace HeuristicLab.Common {
  public class MostRecentlyUsedCache<TKey, TValue> {

    private LinkedList<KeyValuePair<TKey, TValue>> lruList;
    private Dictionary<TKey, LinkedListNode<KeyValuePair<TKey, TValue>>> dictionary;
    private int maxCapacity;

    public MostRecentlyUsedCache(int maxCapacity) {
      this.maxCapacity = maxCapacity;
      lruList = new LinkedList<KeyValuePair<TKey, TValue>>();
      dictionary = new Dictionary<TKey, LinkedListNode<KeyValuePair<TKey, TValue>>>(maxCapacity);
    }

    // drops the least-recently used element if necessary
    public void Add(TKey key, TValue value) {
      if (lruList.Count >= maxCapacity) {
        dictionary.Remove(lruList.Last.Value.Key);
        lruList.RemoveLast();
      }
      lruList.AddFirst(new KeyValuePair<TKey, TValue>(key, value));
      dictionary.Add(key, lruList.First);
    }

    public bool TryGetValue(TKey key, out TValue value) {
      // find matching element
      LinkedListNode<KeyValuePair<TKey, TValue>> node = null;
      if (!dictionary.TryGetValue(key, out node)) {
        value = default(TValue);
        return false;
      } else {
        lruList.Remove(node);
        lruList.AddFirst(node);
        value = node.Value.Value;
        return true;
      }
    }
  }
}