source: branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/SearchDataStructure.cs @ 15977

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.GrammarEnumeration {
  [StorableClass]
  public class SearchNode : DeepCloneable {
    [Storable]
    public readonly int Hash;

    [Storable]
    public readonly SymbolString SymbolString;

    [Storable]
    public readonly double Priority;

    [Storable]
    public readonly double R2;

    private SearchNode() { }

    public SearchNode(int hash, double priority, double r2, SymbolString symbolString) {
      Hash = hash;
      Priority = priority;
      SymbolString = symbolString;
      R2 = r2;
    }

    protected SearchNode(SearchNode original, Cloner cloner) : base(original, cloner) {
      Hash = original.Hash;
      Priority = original.Priority;
      SymbolString = original.SymbolString;
      R2 = original.R2;
    }

    [StorableConstructor]
    protected SearchNode(bool deserializing) { }

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

  public enum StorageType {
    PriorityQueue, Stack, Queue, RandomList, SortedSet
  }

  [StorableClass]
  class SearchDataStore : DeepCloneable, IEnumerable<SearchNode> {
    [Storable]
    private LruCache<int, SearchNode> storedValues;
    //private Dictionary<int, SearchNode> storedValues; // Store hash-references and associated, actual values 

    [Storable]
    private StorageType storageType;

    [Storable]
    private Queue<int> queue;

    [Storable]
    private Stack<int> stack;

    [Storable]
    private List<int> list;

    [Storable]
    private SortedSet<Tuple<double, int>> sortedSet;

    [Storable]
    private int searchDataStructureSize; // storage size for search nodes 

    [Storable]
    private int cacheSize; // cache for already explored search nodes 

    [ExcludeFromObjectGraphTraversal]
    PriorityQueue<double, int> priorityQueue; // does not support [Storable], we rebuild it from the storedValues

    private Action<int, double> storeInternal; // Store hash-references 
    private Func<int> fetchInternal; // Fetch hash-reference

    public SearchDataStore() : this(StorageType.SortedSet) { }

    [StorableConstructor]
    protected SearchDataStore(bool deserializing) : this() { }

    public SearchDataStore(StorageType storageType, int searchDataStructureSize = (int)1e5, int cacheSize = (int)1e5) {
      this.storageType = storageType;

      this.searchDataStructureSize = searchDataStructureSize;
      this.cacheSize = cacheSize;

      storedValues = new LruCache<int, SearchNode>(this.cacheSize);
      InitSearchDataStructure();
    }

    private void InitSearchDataStructure() {
      switch (storageType) {
        case StorageType.PriorityQueue:
          InitPriorityQueue();
          break;
        case StorageType.Stack:
          InitStack();
          break;
        case StorageType.Queue:
          InitQueue();
          break;
        case StorageType.RandomList:
          InitRandomList();
          break;
        case StorageType.SortedSet:
          InitSortedSet();
          break;
      }
    }

    private void ClearSearchDataStructure() {
      switch (storageType) {
        case StorageType.PriorityQueue:
          priorityQueue = null;
          break;
        case StorageType.Stack:
          stack.Clear();
          break;
        case StorageType.Queue:
          queue.Clear();
          break;
        case StorageType.RandomList:
          list.Clear();
          break;
        case StorageType.SortedSet:
          sortedSet.Clear();
          break;
      }
    }

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

    protected SearchDataStore(SearchDataStore original, Cloner cloner) : base(original, cloner) {
      storedValues = cloner.Clone(original.storedValues);
      storageType = original.storageType;
      cacheSize = original.cacheSize;
      searchDataStructureSize = original.searchDataStructureSize;

      InitSearchDataStructure();
      switch (storageType) {
        case StorageType.PriorityQueue:
          foreach (var t in storedValues)
            storeInternal(t.Key, t.Value.Priority);
          break;
        case StorageType.Stack:
          foreach (var v in original.stack.Reverse()) {
            stack.Push(v);
          }
          break;
        case StorageType.Queue:
          foreach (var v in original.queue) {
            queue.Enqueue(v);
          }
          break;
        case StorageType.RandomList:
          list.AddRange(original.list);
          break;
        case StorageType.SortedSet:
          sortedSet = new SortedSet<Tuple<double, int>>(original.sortedSet);
          break;
      }
    }

    [StorableHook(HookType.AfterDeserialization)]
    private void AfterDeserialization() {
      // access lambdas need to be reinitialized
      switch (storageType) {
        case StorageType.PriorityQueue:
          InitPriorityQueue();
          foreach (var t in storedValues)
            storeInternal(t.Key, t.Value.Priority);
          break;
        case StorageType.Stack:
          storeInternal = (hash, prio) => stack.Push(hash);
          fetchInternal = () => stack.Pop();
          break;
        case StorageType.Queue:
          storeInternal = (hash, prio) => queue.Enqueue(hash);
          fetchInternal = () => queue.Dequeue();
          break;
        case StorageType.RandomList:
          System.Random rand = new System.Random(999);
          storeInternal = (hash, prio) => list.Add(hash);
          fetchInternal = () => {
            int indexOfHash = rand.Next(list.Count);
            int result = list[indexOfHash];
            list.RemoveAt(indexOfHash);  // TODO: beware this is O(n), at some point in time we should fix this. Maybe change to priority queue with random key.
            return result;
          };
          break;
        case StorageType.SortedSet:
          storeInternal = (hash, prio) => {
            if (sortedSet.Count >= searchDataStructureSize) {
              var max = sortedSet.Max;
              sortedSet.Remove(max);
              storedValues.Remove(max.Item2);
            }
            sortedSet.Add(Tuple.Create(prio, hash));
          };
          fetchInternal = () => {
            var elem = sortedSet.FirstOrDefault();
            if (elem == null)
              return 0;
            sortedSet.Remove(elem);
            return elem.Item2;
          };
          break;
      }
    }
    #region SearchStrategies

    private void InitPriorityQueue() {
      int capacity = searchDataStructureSize;
      priorityQueue = new PriorityQueue<double, int>(double.MaxValue, double.MinValue, capacity);
      storeInternal = (hash, prio) => {
        // size is the 0-based index of the last used element
        if (priorityQueue.Size == capacity - 1) {
          // if the queue is at capacity we have to replace 
          return;
        }
        priorityQueue.Insert(prio, hash);
      };
      fetchInternal = () => {
        int ret = priorityQueue.PeekMinValue();
        if (priorityQueue.Size > 0) {
          priorityQueue.RemoveMin();
        }
        return ret;
      };
    }

    private void InitStack() {
      stack = new Stack<int>();

      storeInternal = (hash, prio) => stack.Push(hash);
      fetchInternal = () => stack.Pop();
    }

    private void InitQueue() {
      queue = new Queue<int>();

      storeInternal = (hash, prio) => queue.Enqueue(hash);
      fetchInternal = () => queue.Dequeue();
    }

    private void InitRandomList() {
      list = new List<int>();
      System.Random rand = new System.Random(999);

      storeInternal = (hash, prio) => list.Add(hash);
      fetchInternal = () => {
        int indexOfHash = rand.Next(list.Count);
        int result = list[indexOfHash];
        list.RemoveAt(indexOfHash);  // TODO: beware this is O(n), at some point in time we should fix this. Maybe change to priority queue with random key.
        return result;
      };
    }

    private void InitSortedSet() {
      sortedSet = new SortedSet<Tuple<double, int>>();
      storeInternal = (hash, prio) => {
        if (sortedSet.Count >= searchDataStructureSize) {
          var max = sortedSet.Max;
          sortedSet.Remove(max);
          storedValues.Remove(max.Item2);
        }
        sortedSet.Add(Tuple.Create(prio, hash));
      };
      fetchInternal = () => {
        var elem = sortedSet.FirstOrDefault();
        if (elem == null)
          return default(int);
        sortedSet.Remove(elem);
        return elem.Item2;
      };
    }

    #endregion

    #region Interface

    public SearchNode GetNext() {
      int hash = fetchInternal.Invoke();
      SearchNode result = null;
      if (storedValues.TryGetValue(hash, out result)) {
        storedValues.Remove(hash);
      }
      return result;
    }

    public void Store(SearchNode sn) {
      storeInternal(sn.Hash, sn.Priority);
      storedValues[sn.Hash] = sn;
    }

    public bool Contains(int hash) {
      SearchNode result;
      return storedValues.TryGetValue(hash, out result);
    }

    public void Clear() {
      storedValues.Clear();
    }

    #endregion

    #region Collection-Interface

    public int Count {
      get {
        switch (storageType) {
          case StorageType.PriorityQueue:
            return priorityQueue.Size;
          case StorageType.Queue:
            return queue.Count;
          case StorageType.RandomList:
            return list.Count;
          case StorageType.Stack:
            return stack.Count;
          case StorageType.SortedSet:
            return sortedSet.Count;
          default:
            throw new InvalidOperationException("");
        }
      }
    }

    public IEnumerator<SearchNode> GetEnumerator() {
      return storedValues.Select(x => x.Value).GetEnumerator();
    }

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

    #endregion
  }
}