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

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

#2886: Changes in search heuristic for solving Poly-10 problem. Adapt tree evaluation to cover non-terminal symbols.

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