source: branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/LruCache.cs @ 16053

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
 *
 * This file is part of HeuristicLab.
 *
 * HeuristicLab is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * HeuristicLab is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
 */
#endregion

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using HeuristicLab.Common;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;

namespace HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration {
  /// <summary>
  /// A least-recently-used cache stored like a dictionary.
  /// </summary>
  /// <typeparam name="TKey">
  /// The type of the key to the cached item
  /// </typeparam>
  /// <typeparam name="TValue">
  /// The type of the cached item.
  /// </typeparam>
  /// <remarks>
  /// Derived from https://stackoverflow.com/a/3719378/240845
  /// </remarks>
  [StorableClass]
  public class LruCache<TKey, TValue> : DeepCloneable, IDictionary<TKey, TValue> {
    private Dictionary<TKey, LinkedListNode<LruCacheItem>> cacheMap = new Dictionary<TKey, LinkedListNode<LruCacheItem>>();
    private LinkedList<LruCacheItem> lruList = new LinkedList<LruCacheItem>();
    private readonly Action<TValue> dispose;

    [Storable]
    // since a linked list is not directly serializable we use a list of { key, value, index } tuples
    // the index is necessary to be able to restore the linked list with the correct order of nodes
    private List<Tuple<TKey, TValue, int>> cacheItems {
      get {
        var indexedNodes = lruList.Select((lruCacheItem, index) => new { lruCacheItem, index }).ToDictionary(x => x.lruCacheItem, x => x.index);
        return cacheMap.Select(x => Tuple.Create(x.Key, x.Value.Value.Value, indexedNodes[x.Value.Value])).ToList();
      }
      set {
        lruList = new LinkedList<LruCacheItem>();
        cacheMap = new Dictionary<TKey, LinkedListNode<LruCacheItem>>();
        foreach (var t in value.OrderBy(x => x.Item3)) {
          var key = t.Item1;
          var val = t.Item2;
          var item = new LruCacheItem(key, val);
          var node = new LinkedListNode<LruCacheItem>(item);
          lruList.AddLast(node);
          cacheMap.Add(key, node);
        }
      }
    }

    /// <summary>
    /// Initializes a new instance of the <see cref="LruCache{TKey, TValue}"/>
    /// class.
    /// </summary>
    /// <param name="capacity">
    /// Maximum number of elements to cache.
    /// </param>
    /// <param name="dispose">
    /// When elements cycle out of the cache, disposes them. May be null.
    /// </param>
    public LruCache(int capacity, Action<TValue> dispose = null) {
      this.Capacity = capacity;
      this.dispose = dispose;
    }

    [StorableConstructor]
    protected LruCache(bool deserializing) { }

    protected LruCache(LruCache<TKey, TValue> original, Cloner cloner) : base(original, cloner) {
      cacheMap = new Dictionary<TKey, LinkedListNode<LruCacheItem>>();
      lruList = new LinkedList<LruCacheItem>(original.lruList.Select(cloner.Clone));

      var nodeMap = new Dictionary<LruCacheItem, LinkedListNode<LruCacheItem>>();
      for (var node = lruList.First; node != null; node = node.Next) {
        nodeMap.Add(node.Value, node);
      }

      foreach (var t in original.cacheMap) {
        var node = t.Value;
        var item = node.Value;
        var clone = (LruCacheItem)cloner.GetClone(item);
        cacheMap.Add(t.Key, nodeMap[clone]);
      }
      Capacity = original.Capacity;
    }

    /// <summary>
    /// Gets the capacity of the cache.
    /// </summary>
    [Storable]
    public int Capacity { get; private set; }

    public ICollection<TKey> Keys => cacheMap.Keys;

    public ICollection<TValue> Values => (ICollection<TValue>)Keys.Select(x => cacheMap[x].Value.Value);

    public int Count => cacheMap.Count;

    public bool IsReadOnly => false;

    public TValue this[TKey key] {
      get { return Get(key, null); }
      set { Add(key, value); }
    }

    /// <summary>Gets the value associated with the specified key.</summary>
    /// <param name="key">
    /// The key of the value to get.
    /// </param>
    /// <param name="value">
    /// When this method returns, contains the value associated with the specified
    /// key, if the key is found; otherwise, the default value for the type of the 
    /// <paramref name="value" /> parameter. This parameter is passed
    /// uninitialized.
    /// </param>
    /// <returns>
    /// true if the <see cref="T:System.Collections.Generic.Dictionary`2" /> 
    /// contains an element with the specified key; otherwise, false.
    /// </returns>
    public bool TryGetValue(TKey key, out TValue value) {
      lock (cacheMap) {
        LinkedListNode<LruCacheItem> node;
        if (cacheMap.TryGetValue(key, out node)) {
          value = node.Value.Value;
          lruList.Remove(node);
          lruList.AddLast(node);
          return true;
        }

        value = default(TValue);
        return false;
      }
    }

    /// <summary>
    /// Looks for a value for the matching <paramref name="key"/>. If not found, 
    /// calls <paramref name="valueGenerator"/> to retrieve the value and add it to
    /// the cache.
    /// </summary>
    /// <param name="key">
    /// The key of the value to look up.
    /// </param>
    /// <param name="valueGenerator">
    /// Generates a value if one isn't found.
    /// </param>
    /// <returns>
    /// The requested value.
    /// </returns>
    public TValue Get(TKey key, Func<TValue> valueGenerator) {
      lock (cacheMap) {
        LinkedListNode<LruCacheItem> node;
        TValue value;
        if (cacheMap.TryGetValue(key, out node)) {
          value = node.Value.Value;
          lruList.Remove(node);
          lruList.AddLast(node);
        } else {
          value = valueGenerator();
          if (cacheMap.Count >= Capacity) {
            RemoveFirst();
          }

          LruCacheItem cacheItem = new LruCacheItem(key, value);
          node = new LinkedListNode<LruCacheItem>(cacheItem);
          lruList.AddLast(node);
          cacheMap.Add(key, node);
        }

        return value;
      }
    }

    /// <summary>
    /// Adds the specified key and value to the dictionary.
    /// </summary>
    /// <param name="key">
    /// The key of the element to add.
    /// </param>throw new NotImplementedException()
    /// <param name="value">
    /// The value of the element to add. The value can be null for reference types.
    /// </param>
    public void Add(TKey key, TValue value) {
      lock (cacheMap) {
        if (cacheMap.Count >= Capacity) {
          RemoveFirst();
        }

        LruCacheItem cacheItem = new LruCacheItem(key, value);
        LinkedListNode<LruCacheItem> node = new LinkedListNode<LruCacheItem>(cacheItem);
        lruList.AddLast(node);
        cacheMap.Add(key, node);
      }
    }

    public void Remove(TKey key) {
      LinkedListNode<LruCacheItem> node;
      if (cacheMap.TryGetValue(key, out node)) {
        lruList.Remove(node);
        cacheMap.Remove(key);
      }
      dispose?.Invoke(node.Value.Value);
    }

    private void RemoveFirst() {
      // Remove from LRUPriority
      LinkedListNode<LruCacheItem> node = lruList.First;
      lruList.RemoveFirst();

      // Remove from cache
      cacheMap.Remove(node.Value.Key);

      // dispose
      dispose?.Invoke(node.Value.Value);
    }

    private class LruCacheItem : DeepCloneable {
      public LruCacheItem(TKey k, TValue v) {
        Key = k;
        Value = v;
      }

      protected LruCacheItem(LruCacheItem original, Cloner cloner) : base(original, cloner) {
        Key = original.Key;
        Value = original.Value;
      }

      public TKey Key { get; }

      public TValue Value { get; }

      public override IDeepCloneable Clone(Cloner cloner) {
        return new LruCacheItem(this, cloner);
      }
    }

    #region implement DeepCloneable abstract methods
    public override IDeepCloneable Clone(Cloner cloner) {
      return new LruCache<TKey, TValue>(this, cloner);
    }

    public bool ContainsKey(TKey key) {
      return cacheMap.ContainsKey(key);
    }

    bool IDictionary<TKey, TValue>.Remove(TKey key) {
      return cacheMap.Remove(key);
    }

    public void Add(KeyValuePair<TKey, TValue> item) {
      Add(item.Key, item.Value);
    }

    public void Clear() {
      cacheMap.Clear();
      lruList.Clear();
    }

    public bool Contains(KeyValuePair<TKey, TValue> item) {
      return cacheMap.Select(x => new KeyValuePair<TKey, TValue>(x.Key, x.Value.Value.Value)).Contains(item);
    }

    public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex) {
      throw new NotImplementedException();
    }

    public bool Remove(KeyValuePair<TKey, TValue> item) {
      var ret = cacheMap.ContainsKey(item.Key);
      Remove(item.Key);
      return ret;
    }

    public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator() {
      return cacheMap.Select(x => new KeyValuePair<TKey, TValue>(x.Key, x.Value.Value.Value)).GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator() {
      return GetEnumerator();
    }
    #endregion
  }
}