source: branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/SearchDataStructure.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 {
  [StorableClass]
  public class SearchNode : DeepCloneable {
    [Storable]
    public readonly int Hash;

    [Storable]
    public readonly SymbolList SymbolList;

    [Storable]
    public readonly double Priority;

    [Storable]
    public readonly double R2;

    private SearchNode() { }

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

    protected SearchNode(SearchNode original, Cloner cloner) : base(original, cloner) {
      Hash = original.Hash;
      Priority = original.Priority;
      SymbolList = original.SymbolList;
      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 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 

    [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) {
      this.storageType = storageType;

      this.searchDataStructureSize = searchDataStructureSize;

      storedValues = new Dictionary<int, SearchNode>();
      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 = original.storedValues.ToDictionary(x => x.Key, x => cloner.Clone(x.Value));
      storageType = original.storageType;
      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); // should always be in sync with the sorted set
            }
            sortedSet.Add(Tuple.Create(prio, hash));
          };
          fetchInternal = () => {
            var elem = sortedSet.FirstOrDefault();
            if (elem == null)
              return default(int);
            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) {
          return; // if the queue is at capacity we have to 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
  }
}