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

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

#2727 completely replace basic array with array mapped trie in ValueTypeArray and descendants

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