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

using System;
using System.Collections;
using System.Collections.Generic;

namespace HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.GrammarEnumeration {

  public class SearchNode {
    public readonly int Hash;
    public readonly SymbolString SymbolString;
    public readonly double Priority;
    public readonly double R2;

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

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

  class SearchDataStore : IEnumerable<SearchNode> {

    private Dictionary<int, SearchNode> storedValues; // Store hash-references and associated, actual values 
    private Action<int, double> storeInternal; // Store hash-references 
    private Func<int> fetchInternal; // Fetch hash-reference

    public SearchDataStore(StorageType storageType) {
      storedValues = new Dictionary<int, SearchNode>();

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

    }

    #region SearchStrategies

    private void InitPriorityQueue() {
      int capacity = 10000000;
      PriorityQueue<double, int> queue = new PriorityQueue<double, int>(double.MaxValue, double.MinValue, capacity);
      storeInternal = (hash, prio) => queue.Insert(prio, hash);
      fetchInternal = () => {
        int ret = queue.PeekMinValue();
        queue.RemoveMin();
        return ret;
      };
    }

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

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

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

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

    private void InitRandomList() {
      List<int> 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;
      };
    }

    #endregion

    #region Interface

    public SearchNode GetNext() {
      int hash = fetchInternal.Invoke();
      SearchNode result = storedValues[hash];
      storedValues.Remove(hash);
      return result;
    }

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

    public bool Contains(int hash) {
      return storedValues.ContainsKey(hash);
    }

    #endregion

    #region Collection-Interface

    public int Count {
      get { return storedValues.Count; }
    }

    public IEnumerator<SearchNode> GetEnumerator() {
      return storedValues.Values.GetEnumerator();
    }

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

    #endregion
  }
}