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

Last change on this file since 15915 was 15915, checked in by lkammere, 20 months ago

#2886: Add separate data structure for storing phrases in the queue.

File size: 3.5 KB
Line 
1using System;
2using System.Collections;
3using System.Collections.Generic;
4
5namespace HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.GrammarEnumeration {
6
7  public class SearchNode {
8    public readonly int Hash;
9    public readonly SymbolString SymbolString;
10    public readonly double Priority;
11    public readonly double R2;
12
13    public SearchNode(int hash, double priority, double r2, SymbolString symbolString) {
14      Hash = hash;
15      Priority = priority;
16      SymbolString = symbolString;
17      R2 = r2;
18    }
19  }
20
21  public enum StorageType {
22    PriorityQueue, Stack, Queue, RandomList
23  }
24
25  class SearchDataStore : IEnumerable<SearchNode> {
26
27    private Dictionary<int, SearchNode> storedValues; // Store hash-references and associated, actual values
28    private Action<int, double> storeInternal; // Store hash-references
29    private Func<int> fetchInternal; // Fetch hash-reference
30
31    public SearchDataStore(StorageType storageType) {
32      storedValues = new Dictionary<int, SearchNode>();
33
34      switch (storageType) {
35        case StorageType.PriorityQueue:
36          InitPriorityQueue();
37          break;
38        case StorageType.Stack:
39          InitStack();
40          break;
41        case StorageType.Queue:
42          InitQueue();
43          break;
44        case StorageType.RandomList:
45          InitRandomList();
46          break;
47      }
48
49    }
50
51    #region SearchStrategies
52
53    private void InitPriorityQueue() {
54      int capacity = 10000000;
55      PriorityQueue<double, int> queue = new PriorityQueue<double, int>(double.MaxValue, double.MinValue, capacity);
56      storeInternal = (hash, prio) => queue.Insert(prio, hash);
57      fetchInternal = () => {
58        int ret = queue.PeekMinValue();
59        queue.RemoveMin();
60        return ret;
61      };
62    }
63
64    private void InitStack() {
65      Stack<int> stack = new Stack<int>();
66
67      storeInternal = (hash, prio) => stack.Push(hash);
68      fetchInternal = () => stack.Pop();
69    }
70
71    private void InitQueue() {
72      Queue<int> queue = new Queue<int>();
73
74      storeInternal = (hash, prio) => queue.Enqueue(hash);
75      fetchInternal = () => queue.Dequeue();
76    }
77
78    private void InitRandomList() {
79      List<int> list = new List<int>();
80      System.Random rand = new System.Random(999);
81
82      storeInternal = (hash, prio) => list.Add(hash);
83      fetchInternal = () => {
84        int indexOfHash = rand.Next(list.Count);
85        int result = list[indexOfHash];
86        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.
87        return result;
88      };
89    }
90
91    #endregion
92
93    #region Interface
94
95    public SearchNode GetNext() {
96      int hash = fetchInternal.Invoke();
97      SearchNode result = storedValues[hash];
98      storedValues.Remove(hash);
99      return result;
100    }
101
102    public void Store(SearchNode sn) {
103      storeInternal(sn.Hash, sn.Priority);
104      storedValues[sn.Hash] = sn;
105    }
106
107    public bool Contains(int hash) {
108      return storedValues.ContainsKey(hash);
109    }
110
111    #endregion
112
113    #region Collection-Interface
114
115    public int Count {
116      get { return storedValues.Count; }
117    }
118
119    public IEnumerator<SearchNode> GetEnumerator() {
120      return storedValues.Values.GetEnumerator();
121    }
122
123    IEnumerator IEnumerable.GetEnumerator() {
124      return GetEnumerator();
125    }
126
127    #endregion
128  }
129}
Note: See TracBrowser for help on using the repository browser.