#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 .
*/
#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 {
[Storable]
private Dictionary storedValues; // Store hash-references and associated, actual values
[Storable]
private StorageType storageType;
[Storable]
private Queue queue;
[Storable]
private Stack stack;
[Storable]
private List list;
[Storable]
private SortedSet> sortedSet;
[Storable]
private int searchDataStructureSize; // storage size for search nodes
[ExcludeFromObjectGraphTraversal]
PriorityQueue priorityQueue; // does not support [Storable], we rebuild it from the storedValues
private Action storeInternal; // Store hash-references
private Func 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();
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>(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.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();
storeInternal = (hash, prio) => stack.Push(hash);
fetchInternal = () => stack.Pop();
}
private void InitQueue() {
queue = new Queue();
storeInternal = (hash, prio) => queue.Enqueue(hash);
fetchInternal = () => queue.Dequeue();
}
private void InitRandomList() {
list = new List();
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>();
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 GetEnumerator() {
return storedValues.Select(x => x.Value).GetEnumerator();
}
IEnumerator IEnumerable.GetEnumerator() {
return GetEnumerator();
}
#endregion
}
}