Changeset 14657 for branches/PersistentDataStructures

Timestamp:

02/10/17 15:13:29 (8 years ago)

Author:

epitzer

Message:

#2727 add generic MetaInfo to AMT e.g. for tracking Count in facades

Location:

branches/PersistentDataStructures/HeuristicLab.Data/3.3

Files:

• PersistentDataStructures/Adaptations/HistoryArray.cs (modified) (4 diffs)
• PersistentDataStructures/Adaptations/HistoryList.cs (modified) (2 diffs)
• PersistentDataStructures/Implementations/ArrayMappedTrie.cs (modified) (6 diffs)
• ValueTypeArray.cs (modified) (8 diffs)

branches/PersistentDataStructures/HeuristicLab.Data/3.3/PersistentDataStructures/Adaptations/HistoryArray.cs

@@ -13 +13 @@
     [Storable]
     private ArrayMappedTrie<T> amt;
-    [Storable]
-    public int Count { get; private set; }
+
+    public int Count {
+      get { return (int?) amt.MetaInfo ?? 0; }
+      private set { amt.MetaInfo = value; }
+    }
+
     public int Length { get { return Count; } }
 
     [StorableConstructor]
     protected HistoryArray(bool isDeserializing) { }
+
+    private HistoryArray(ArrayMappedTrie<T> amt) {
+      this.amt = amt.Clone();
+      Count = (int?) amt.MetaInfo ?? 0;
+    }
 
     protected HistoryArray(HistoryArray<T> orig) {
@@ -26 +35 @@
 
     public HistoryArray(int size) {
-      amt = new ArrayMappedTrie<T>();
+      amt = new ArrayMappedTrie<T> { SnapshotInterval = 0 };
       Count = size;
     }
 
+    [Obsolete]
     public HistoryArray(IEnumerable<T> elements) {
-      amt = new ArrayMappedTrie<T>();
+      amt = new ArrayMappedTrie<T> { SnapshotInterval = 0 };
       Count = 0;
       foreach (var element in elements) {
@@ -125 +135 @@
         int hash = (int)2166136261;
         for (int i = 0; i < Count; i++) {
-          hash = (hash * 16777619) ^ (this[i]?.GetHashCode() ?? 0);
+          hash = (hash * 16777619) ^ (this[i] == null ? 0 : this[i].GetHashCode());
         }
         return hash;
@@ -137 +147 @@
       Count = newSize;
     }
+
+    public void CreateSnapshot() {
+      amt.CreateSnapshot();
+    }
+
+    public IEnumerable<HistoryArray<T>> GetHistory() {
+      yield return this;
+      var prev = amt.Rollback();
+      while (prev != null) {
+        yield return new HistoryArray<T>(prev);
+        prev = prev.Rollback();
+      }
+    }
   }
 }

branches/PersistentDataStructures/HeuristicLab.Data/3.3/PersistentDataStructures/Adaptations/HistoryList.cs

@@ -9 +9 @@
 
   [StorableClass]
-  public class HistoryList<T> : IList<T> {
+  public class HistoryList<T> : IList<T>, ICloneable {
 
     [Storable]
     private readonly ArrayMappedTrie<T> amt;
 
-    public int Count { get; private set; }
+    public int Count {
+      get { return (int) amt.MetaInfo; }
+      private set { amt.MetaInfo = value; }
+    }
 
     [StorableConstructor]
     protected HistoryList(bool isDesierializing) { }
 
+    private HistoryList(ArrayMappedTrie<T> amt) { this.amt = amt; }
+
     public HistoryList() {
-      amt = new ArrayMappedTrie<T>(true);
+      amt = new ArrayMappedTrie<T> { SnapshotInterval = 0 };
       Count = 0;
+    }
+
+    public HistoryList(HistoryList<T> orig) {
+      amt = orig.amt.Clone();
+      Count = orig.Count;
+    }
+
+
+    [Obsolete]
+    public HistoryList(IEnumerable<T> values) {
+      amt = new ArrayMappedTrie<T> { SnapshotInterval = 0 };
+      Count = 0;
+      foreach (var value in values) Add(value);
     }
 
@@ -114 +132 @@
         amt.CreateSnapshot();
     }
+
+    public void CreateSnapshot() {
+      amt.CreateSnapshot();
+    }
+
+    public IEnumerable<HistoryList<T>> GetHistory() {
+      yield return this;
+      var prev = amt.Rollback();
+      while (prev != null) {
+        yield return new HistoryList<T>(prev);
+        prev = prev.Rollback();
+      }
+    }
+
+    public object Clone() { return new HistoryList<T>(this); }
   }
 }

branches/PersistentDataStructures/HeuristicLab.Data/3.3/PersistentDataStructures/Implementations/ArrayMappedTrie.cs

@@ -5 +5 @@
 using System.Diagnostics;
 using System.Linq;
+using HeuristicLab.Persistence.Core.Tokens;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 
 namespace HeuristicLab.Data.PersistentDataStructures.Implementations {
+
 
   [StorableClass]
@@ -85 +87 @@
     }
 
-    [Storable]
-    private Node root;
-
-    [Storable]
-    private List<Node> oldRoots;
-
-    [Storable]
-    private UInt32 stepsSinceSnapshot = UInt32.MaxValue;
-
-    [Storable]
-    private readonly bool assumeFilledWithDefaultValue;
+    [Storable] private readonly bool assumeFilledWithDefaultValue;
+    [Storable] private Node root;
+    [Storable] private List<Tuple<Node, ValueType>> oldRoots;
+    [Storable] private UInt32 stepsSinceSnapshot = UInt32.MaxValue;
+    [Storable] public UInt32 SnapshotInterval { get; set; }
+    [Storable] public bool TrackClonedFrom { get; set; }
+    [Storable] public ArrayMappedTrie<T> ClonedFrom { get; private set; }
+    [Storable] public ValueType MetaInfo { get; set; }
+
+    public UInt32 Count { get { return DoCount(root); } }
+
+    protected ArrayMappedTrie() { }
 
     public ArrayMappedTrie(bool assumeFilledWithDefaultValue = true) {
@@ -110 +113 @@
     }
 
-    public UInt32 Count { get { return DoCount(root); } }
-
-    public UInt32 SnapshotInterval { get; set; }
-
-    public bool TrackClonedFrom { get; set; }
-
-    public ArrayMappedTrie<T> ClonedFrom { get; private set; }
-
     public void CreateSnapshot() {
-      if (oldRoots == null) oldRoots = new List<Node>();
-      oldRoots.Add(root);
+      if (oldRoots == null) oldRoots = new List<Tuple<Node, ValueType>>();
+      oldRoots.Add(Tuple.Create(root, MetaInfo));
       stepsSinceSnapshot = 0;
+    }
+
+    public ArrayMappedTrie<T> Rollback() {
+      if (oldRoots != null && oldRoots.Count > 0) {
+        return new ArrayMappedTrie<T>(assumeFilledWithDefaultValue) {
+          root = oldRoots.Last().Item1,
+          MetaInfo = oldRoots.Last().Item2,
+          oldRoots = oldRoots.GetRange(0, oldRoots.Count - 1),
+          SnapshotInterval = SnapshotInterval,
+          TrackClonedFrom = TrackClonedFrom,
+          ClonedFrom = ClonedFrom
+        };
+      } else {
+        return ClonedFrom;
+      }
     }
 
@@ -237 +247 @@
       if (oldRoots != null) {
         foreach (var node in oldRoots) {
-          AddNodeSizeRecursively(node, nodes);
+          AddNodeSizeRecursively(node.Item1, nodes);
         }
       }
@@ -257 +267 @@
 
     public ArrayMappedTrie<T> Clone() {
-      return new ArrayMappedTrie<T> {
-        TrackClonedFrom = this.TrackClonedFrom,
+      return new ArrayMappedTrie<T>(assumeFilledWithDefaultValue) {
+        root = root,
+        MetaInfo = MetaInfo,
+        oldRoots = null,
+        SnapshotInterval = SnapshotInterval,
+        TrackClonedFrom = TrackClonedFrom,
         ClonedFrom = TrackClonedFrom ? this : null,
-        oldRoots = new List<Node> {root},
-        root = root
       };
     } 
@@ -277 +289 @@
 
     private static IEnumerable<Node> GetChildrenRecursively(Node n, int level) {
-      if (level == 0) yield return n;
-      foreach (Node child in n) {
-        foreach (var grandchild in GetChildrenRecursively(child, level-1)) {
-          yield return grandchild;
+      if (level == 0) {
+        yield return n;
+      } else {
+        foreach (Node child in n) {
+          foreach (var grandchild in GetChildrenRecursively(child, level - 1)) {
+            yield return grandchild;
+          }
         }
       }

branches/PersistentDataStructures/HeuristicLab.Data/3.3/ValueTypeArray.cs

@@ -44 +44 @@
     protected T[] oldArrayValuePersistence { set { historyArray = new HistoryArray<T>(value); } }
 
+    [Storable(AllowOneWay = true, Name = "elementNames")]
+    protected List<string> oldElementNamesValuePersistence { set { historyElementNames = new HistoryList<string>(value); } }
+
     [Storable]
     protected HistoryArray<T> historyArray;
 
     [Storable]
-    protected List<string> elementNames;
+    protected HistoryList<string> historyElementNames;
+
     public virtual IEnumerable<string> ElementNames {
-      get { return this.elementNames; }
+      get { return this.historyElementNames; }
       set {
         if (ReadOnly) throw new NotSupportedException("ElementNames cannot be set. ValueTypeArray is read-only.");
         if (value == null || !value.Any())
-          elementNames = new List<string>();
+          historyElementNames = new HistoryList<string>();
         else if (value.Count() > Length)
           throw new ArgumentException("The number of element names must not exceed the array length.");
-        else
-          elementNames = new List<string>(value);
+        else 
+          historyElementNames = new HistoryList<string>(value);
         OnElementNamesChanged();
       }
@@ -71 +75 @@
         if (value != Length) {
           historyArray.Resize(value);
-          while (elementNames.Count > value)
-            elementNames.RemoveAt(elementNames.Count - 1);
+          while (historyElementNames.Count > value)
+            historyElementNames.RemoveAt(historyElementNames.Count - 1);
           OnElementNamesChanged();
           OnReset();
@@ -112 +116 @@
     [StorableHook(HookType.AfterDeserialization)]
     private void AfterDeserialization() {
-      if (elementNames == null) { elementNames = new List<string>(); }
+      if (historyElementNames == null) { historyElementNames = new HistoryList<string>(); }
     }
 
@@ -122 +126 @@
       this.readOnly = original.readOnly;
       this.resizable = original.resizable;
-      this.elementNames = new List<string>(original.elementNames);
+      this.historyElementNames = (HistoryList<string>)original.historyElementNames.Clone();
     }
     protected ValueTypeArray() {
@@ -128 +132 @@
       readOnly = false;
       resizable = true;
-      elementNames = new List<string>();
+      historyElementNames = new HistoryList<string>();
     }
     protected ValueTypeArray(int length) {
@@ -134 +138 @@
       readOnly = false;
       resizable = true;
-      elementNames = new List<string>();
+      historyElementNames = new HistoryList<string>();
     }
     protected ValueTypeArray(T[] elements) {
@@ -141 +145 @@
       readOnly = false;
       resizable = true;
-      elementNames = new List<string>();
+      historyElementNames = new HistoryList<string>();
+    }
+    private ValueTypeArray(HistoryArray<T> values, HistoryList<string> historyElementNames) {
+      this.historyArray = values;
+      this.historyElementNames = historyElementNames;
     }
 
@@ -205 +213 @@
       OnToStringChanged();
     }
+
+    public void CreateSnapshot() {
+      historyArray.CreateSnapshot();
+      historyElementNames.CreateSnapshot();
+    }
+
+    public IEnumerable<ValueTypeArray<T>> GetHistory() {
+      foreach (var vta in historyArray.GetHistory().Zip(historyElementNames.GetHistory(), (v, n) => new {v, n})) {
+        var clone = (ValueTypeArray<T>)Clone();
+        clone.historyArray = vta.v;
+        clone.historyElementNames = vta.n;
+        yield return clone;
+      }
+    }
   }
 }