source: branches/PersistentDataStructures/HeuristicLab.Data/3.3/PersistentDataStructures/Implementations/ArrayMappedTrie.cs @ 14657

Last change on this file since 14657 was 14657, checked in by epitzer, 4 years ago

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

File size: 11.1 KB
Line 
1using System;
2using System.Collections;
3using System.Collections.Generic;
4using System.Collections.Specialized;
5using System.Diagnostics;
6using System.Linq;
7using HeuristicLab.Persistence.Core.Tokens;
8using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
9
10namespace HeuristicLab.Data.PersistentDataStructures.Implementations {
11
12
13  [StorableClass]
14  public class ArrayMappedTrie<T> : IEnumerable<T> {
15
16    [StorableClass]
17    private class Node : IEnumerable {
18
19      [Storable]
20      private BitVector32 bitmap;
21      [Storable]
22      private readonly object[] values;
23
24      private static UInt16 CalculateLocalIndex(UInt16 subIndex, BitVector32 bitmap) {
25        UInt32 relevantBits = ((((uint)1)<<subIndex) - 1) & (uint) bitmap.Data;
26        return (UInt16) PopCount(relevantBits);
27      }
28
29      public bool Contains(UInt16 localIndex) { return bitmap[1 << localIndex]; }
30
31      [StorableConstructor]
32      protected Node(bool isDeserializing) { }
33
34      protected Node(BitVector32 bitmap, object[] values) {
35        this.bitmap = bitmap;
36        this.values = values;
37      }
38
39      public Node(UInt16 subIndex, object value) {
40        bitmap[1 << subIndex] = true;
41        values = new[] {value};
42      }
43
44      public object Get(UInt16 subIndex) {
45        return Contains(subIndex) ? values[CalculateLocalIndex(subIndex, bitmap)] : null;
46      }
47
48      public Node Set(UInt16 subIndex, object value) {
49        Debug.Assert(subIndex < 32);
50        if (Contains(subIndex)) {
51          var newValues = new object[values.Length];
52          Array.Copy(values, newValues, newValues.Length);
53          newValues[CalculateLocalIndex(subIndex, bitmap)] = value;
54          return new Node(bitmap, newValues);
55        } else {
56          var newValues = new object[values.Length + 1];
57          BitVector32 newBitmap = bitmap;
58          newBitmap[1 << subIndex] = true;
59          var localIndex = CalculateLocalIndex(subIndex, newBitmap);
60          if (localIndex > 0)
61            Array.ConstrainedCopy(values, 0, newValues, 0, localIndex);
62          newValues[localIndex] = value;
63          if (values.Length - localIndex > 0)
64            Array.ConstrainedCopy(values, localIndex, newValues, localIndex + 1, values.Length - localIndex);
65          return new Node(newBitmap, newValues);
66        }
67      }
68
69      public Node Remove(UInt16 subIndex) {
70        Debug.Assert(subIndex < 32);
71        if (!Contains(subIndex)) return this;
72        if (Length == 1) return null;
73        var newBitmap = bitmap;
74        var localIndex = CalculateLocalIndex(subIndex, bitmap);
75        newBitmap[1 << subIndex] = false;
76        var newValues = new object[values.Length - 1];
77        Array.ConstrainedCopy(values, 0, newValues, 0, localIndex);
78        Array.ConstrainedCopy(values, localIndex + 1, newValues, localIndex, newValues.Length - localIndex);
79        return new Node(newBitmap, newValues);
80      }
81
82      public UInt16 Length { get { return (UInt16) values.Length; } }
83
84      public IEnumerator GetEnumerator() {
85        return values.GetEnumerator();
86      }
87    }
88
89    [Storable] private readonly bool assumeFilledWithDefaultValue;
90    [Storable] private Node root;
91    [Storable] private List<Tuple<Node, ValueType>> oldRoots;
92    [Storable] private UInt32 stepsSinceSnapshot = UInt32.MaxValue;
93    [Storable] public UInt32 SnapshotInterval { get; set; }
94    [Storable] public bool TrackClonedFrom { get; set; }
95    [Storable] public ArrayMappedTrie<T> ClonedFrom { get; private set; }
96    [Storable] public ValueType MetaInfo { get; set; }
97
98    public UInt32 Count { get { return DoCount(root); } }
99
100    protected ArrayMappedTrie() { }
101
102    public ArrayMappedTrie(bool assumeFilledWithDefaultValue = true) {
103      this.assumeFilledWithDefaultValue = assumeFilledWithDefaultValue;
104      root = null;
105      ClonedFrom = null;
106      TrackClonedFrom = true;
107      SnapshotInterval = 1;
108    }
109
110    public T this[UInt32 index] {
111      get { return Get(root, index); }
112      set { Set(index, value); }
113    }
114
115    public void CreateSnapshot() {
116      if (oldRoots == null) oldRoots = new List<Tuple<Node, ValueType>>();
117      oldRoots.Add(Tuple.Create(root, MetaInfo));
118      stepsSinceSnapshot = 0;
119    }
120
121    public ArrayMappedTrie<T> Rollback() {
122      if (oldRoots != null && oldRoots.Count > 0) {
123        return new ArrayMappedTrie<T>(assumeFilledWithDefaultValue) {
124          root = oldRoots.Last().Item1,
125          MetaInfo = oldRoots.Last().Item2,
126          oldRoots = oldRoots.GetRange(0, oldRoots.Count - 1),
127          SnapshotInterval = SnapshotInterval,
128          TrackClonedFrom = TrackClonedFrom,
129          ClonedFrom = ClonedFrom
130        };
131      } else {
132        return ClonedFrom;
133      }
134    }
135
136    public void Remove(UInt32 index) {
137      CreateSnapshotIfNeccessary();
138      Remove(root, index, 6);
139      stepsSinceSnapshot++;
140    }
141
142    public void Clear() {
143      CreateSnapshotIfNeccessary();
144      root = null;
145      stepsSinceSnapshot++;
146    }
147
148    private void CreateSnapshotIfNeccessary() {
149      if (SnapshotInterval > 0 && stepsSinceSnapshot > SnapshotInterval)
150        CreateSnapshot();
151    }
152
153    private void Set(UInt32 index, T value) {
154      if (assumeFilledWithDefaultValue) {
155        T oldValue;
156        var containsIndex = Get(root, index, out oldValue);
157        if (containsIndex && oldValue.Equals(value) ||
158            !containsIndex && value.Equals(default(T))) return;
159      }
160      CreateSnapshotIfNeccessary();
161      root = assumeFilledWithDefaultValue && value.Equals(default(T)) ? Remove(root, index, 6) : Set(root, index, 6, value);
162      stepsSinceSnapshot++;
163    }
164
165    private static Node Set(Node n, UInt32 index, UInt16 level, T value) {
166      var subIndex = ExtractSubIndex(index, level);
167      if (level == 0)
168        return n == null ?
169           new Node(subIndex, value) :
170           n.Set(subIndex, value);
171      return n == null ?
172        new Node(subIndex, Set(null, index, (UInt16) (level - 1), value)) :
173        n.Set(subIndex, Set((Node)n.Get(subIndex), index, (UInt16)(level - 1), value));
174    }
175
176    private static Node Remove(Node n, UInt32 index, UInt16 level) {
177      if (n == null) return null;
178      var subIndex = ExtractSubIndex(index, level);
179      if (level == 0) return n.Remove(subIndex);
180      var newN = Remove((Node) n.Get(subIndex), index, (UInt16) (level - 1));
181      return newN == null ? n.Remove(subIndex) : n.Set(subIndex, newN);
182    }
183
184    private bool Get(Node n, UInt32 index, out T value) {
185      value = default(T);
186      var leafNode = Get(root, index, 6);
187      if (leafNode == null) return false;
188      var subIndex = ExtractSubIndex(index, 0);
189      if (!leafNode.Contains(subIndex)) return false;
190      value = (T)leafNode.Get(ExtractSubIndex(index, 0));
191      return true;
192    }
193
194    private T Get(Node n, UInt32 index) {
195      T value;
196      if (Get(n, index, out value) || assumeFilledWithDefaultValue)
197        return value;
198      throw new IndexOutOfRangeException();
199    }
200
201    private static Node Get(Node n, UInt32 index, UInt16 level) {
202      while (true) {
203        var subIndex = ExtractSubIndex(index, level);
204        if (level == 0) return n;
205        if (n == null) return null;
206        n = (Node) n.Get(subIndex);
207        level = (UInt16) (level - 1);
208      }
209    }
210
211    private UInt32 DoCount(Node n) { return DoCount(root, 6); }
212
213    private static UInt32 DoCount(Node n, UInt16 level) {
214      if (n == null) return 0;
215      return level == 0 ? n.Length :
216        n.Cast<Node>().Aggregate<Node, uint>(0,
217        (current, child) =>
218          current + DoCount(child, (UInt16) (level - 1)));
219    }
220
221    public UInt32 CountNodes() { return CountNodes(root, 6);  }
222
223    private static UInt32 CountNodes(Node n, UInt16 level) {
224      if (n == null) return 0;
225      if (level == 0) return 1;
226      return 1 + n.Cast<Node>().Aggregate<Node, uint>(0,
227        (current, child) =>
228          current + CountNodes(child, (UInt16) (level - 1)));
229    }
230
231    public UInt32 Overhead() { return Overhead(root, 6); }
232
233    private static UInt32 Overhead(Node n, UInt16 level) {
234      if (n == null) return 0;
235      if (level == 0) return 1 + 1; /* bitmap + child, leaf arrays are not overhead */
236      UInt32 total = 0;
237      foreach (Node child in n) {
238        total += Overhead(child, (UInt16)(level - 1));
239      }
240      return 1 + 1 + (UInt32)n.Length + total; /* node + bitmap + array + children */
241    }
242
243    public long SizeWithHistory() {
244      var nodes = new Dictionary<Node, UInt16>();
245      AddNodeSizeRecursively(root, nodes);
246      var size = nodes.Sum(kvp => (long) kvp.Value);
247      if (oldRoots != null) {
248        foreach (var node in oldRoots) {
249          AddNodeSizeRecursively(node.Item1, nodes);
250        }
251      }
252      var sizeWithHistory = nodes.Sum(kvp => (long)kvp.Value);
253      Console.WriteLine("size = {0}, size with history = {1}", size, sizeWithHistory);
254      return sizeWithHistory;
255    }
256
257    private static void AddNodeSizeRecursively(Node n, IDictionary<Node, UInt16> d) {
258      if (n == null) return;
259      if (d.ContainsKey(n)) return;
260      d[n] = (UInt16)(n.Length + 1 + 1);
261      foreach (var child in n) {
262        var childNode = child as Node;
263        if (child == null) break;
264        AddNodeSizeRecursively(childNode, d);
265      }
266    }
267
268    public ArrayMappedTrie<T> Clone() {
269      return new ArrayMappedTrie<T>(assumeFilledWithDefaultValue) {
270        root = root,
271        MetaInfo = MetaInfo,
272        oldRoots = null,
273        SnapshotInterval = SnapshotInterval,
274        TrackClonedFrom = TrackClonedFrom,
275        ClonedFrom = TrackClonedFrom ? this : null,
276      };
277    }
278
279    public static UInt16 ExtractSubIndex(UInt32 index, int level) {
280      int offset = level*5;
281      const uint window = 0x1f;
282      UInt32 shiftedWindow = window << offset;
283      UInt32 maskedValue = index & shiftedWindow;
284      UInt32 subindex = maskedValue >> offset;
285      Debug.Assert(subindex < 32);
286      // Console.WriteLine("index {0} level {1} => {2} ({3})", index, level, subindex, subindex * Math.Pow(32, level));
287      return (UInt16)subindex;
288    }
289
290    private static IEnumerable<Node> GetChildrenRecursively(Node n, int level) {
291      if (level == 0) {
292        yield return n;
293      } else {
294        foreach (Node child in n) {
295          foreach (var grandchild in GetChildrenRecursively(child, level - 1)) {
296            yield return grandchild;
297          }
298        }
299      }
300    }
301
302    IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); }
303
304    public IEnumerator<T> GetEnumerator() {
305      foreach (var leaf in GetChildrenRecursively(root, 6)) {
306        foreach (var value in leaf)
307          yield return (T)value;
308      }
309    }
310
311    public const UInt32 SK5  = 0x55555555;
312    public const UInt32 SK3  = 0x33333333;
313    public const UInt32 SKF0 = 0x0f0f0f0f;
314    public const UInt32 SKFF = 0x00ff00ff;
315
316    public static UInt32 PopCount(UInt32 x) {
317      x -= (x>>1)&SK5;
318      x = (x & SK3) + ((x >> 2) & SK3);
319      x = (x & SKF0) + ((x >> 4) & SKF0);
320      x += x >> 8;
321      return (x + (x >> 16)) & 0x3F;
322    }
323
324  }
325}
Note: See TracBrowser for help on using the repository browser.