Free cookie consent management tool by TermsFeed Policy Generator

source: branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Data/List/SkipList.cs @ 14875

Last change on this file since 14875 was 14875, checked in by pkimmesw, 7 years ago

#2665 BenchmarkSuite, all examples, partially tested, VectorExpressions added

File size: 14.2 KB
Line 
1using System;
2using System.Collections.Generic;
3
4namespace HeuristicLab.Problems.ProgramSynthesis.Push.Data.List {
5  using System.Collections;
6
7  using HeuristicLab.Core;
8  using HeuristicLab.Random;
9
10  /// <summary>
11  /// The basic data block of a Skip List
12  /// </summary>
13  class SkipListNode<T> : IDisposable
14      where T : IComparable {
15    private T value;
16    private SkipListNode<T> next;
17    private SkipListNode<T> previous;
18    private SkipListNode<T> above;
19    private SkipListNode<T> below;
20
21    public virtual T Value
22    {
23      get { return value; }
24      set { this.value = value; }
25    }
26
27    public virtual SkipListNode<T> Next
28    {
29      get { return next; }
30      set { next = value; }
31    }
32
33    public virtual SkipListNode<T> Previous
34    {
35      get { return previous; }
36      set { previous = value; }
37    }
38
39    public virtual SkipListNode<T> Above
40    {
41      get { return above; }
42      set { above = value; }
43    }
44
45    public virtual SkipListNode<T> Below
46    {
47      get { return below; }
48      set { below = value; }
49    }
50
51    public SkipListNode(T value) {
52      this.Value = value;
53    }
54
55    public void Dispose() {
56      value = default(T);
57      next = null;
58      previous = null;
59      above = null;
60      previous = null;
61    }
62
63    public virtual bool IsHeader() {
64      return this.GetType() == typeof(SkipListNodeHeader<T>);
65    }
66
67    public virtual bool IsFooter() {
68      return this.GetType() == typeof(SkipListNodeFooter<T>);
69    }
70  }
71
72  /// <summary>
73  /// Represents a Skip List node that is the header of a level
74  /// </summary>
75  class SkipListNodeHeader<T> : SkipListNode<T>
76      where T : IComparable {
77    public SkipListNodeHeader()
78        : base(default(T)) {
79    }
80  }
81
82  /// <summary>
83  /// Represents a Skip List node that is the footer of a level
84  /// </summary>
85  class SkipListNodeFooter<T> : SkipListNode<T>
86      where T : IComparable {
87    public SkipListNodeFooter()
88        : base(default(T)) {
89    }
90  }
91
92  class SkipList<T> : ICollection<T>
93      where T : IComparable {
94    internal SkipListNode<T> topLeft;
95    internal SkipListNode<T> bottomLeft;
96    internal IRandom random;
97    private int levels;
98    private int size;
99    private int maxLevels = int.MaxValue;
100
101    public virtual int Levels
102    {
103      get { return levels; }
104    }
105
106    public virtual int MaxLevels
107    {
108      get { return maxLevels; }
109      set { maxLevels = value; }
110    }
111
112    public virtual int Count
113    {
114      get { return size; }
115    }
116
117    public virtual bool IsReadOnly
118    {
119      get { return false; }
120    }
121
122    public virtual SkipListNode<T> Head
123    {
124      get { return bottomLeft; }
125    }
126
127    public SkipList(IRandom random = null) {
128      topLeft = getEmptyLevel(); //create an empty level
129      bottomLeft = topLeft;
130      levels = 1; //update the level count
131      size = 0; //no elements added
132      this.random = random ?? new FastRandom(); //used for adding new values
133    }
134
135    /// <summary>
136    /// Creates an empty level with a header and footer node
137    /// </summary>
138    protected SkipListNode<T> getEmptyLevel() {
139      SkipListNode<T> negativeInfinity = new SkipListNodeHeader<T>();
140      SkipListNode<T> positiveInfinity = new SkipListNodeFooter<T>();
141
142      negativeInfinity.Next = positiveInfinity;
143      positiveInfinity.Previous = negativeInfinity;
144
145      return negativeInfinity;
146    }
147
148    /// <summary>
149    /// Randomly determines how many levels to add
150    /// </summary>
151    protected int getRandomLevels() {
152      int newLevels = 0;
153      while (random.Next(0, 2) == 1 && newLevels < maxLevels) //1 is heads, 0 is tails
154      {
155        newLevels++;
156      }
157      return newLevels;
158    }
159
160    /// <summary>
161    /// Removes all the empty levels leftover in the Skip List
162    /// </summary>
163    protected void clearEmptyLevels() {
164      if (this.levels > 1) //more than one level, don't want to remove bottom level
165      {
166        SkipListNode<T> currentNode = this.topLeft;
167
168        while (currentNode != this.bottomLeft) //do not remove the bottom level
169        {
170          if (currentNode.IsHeader() && currentNode.Next.IsFooter()) {
171            SkipListNode<T> belowNode = currentNode.Below;
172
173            //Remove the empty level
174
175            //Update pointers
176            topLeft = currentNode.Below;
177
178            //Remove links
179            currentNode.Next.Dispose();
180            currentNode.Dispose();
181
182            //Update counters
183            this.levels--;
184
185            currentNode = belowNode; //scan down
186          } else
187            break; //a single non-emtpy level means the rest of the levels are not empty
188        }
189      }
190    }
191
192    /// <summary>
193    /// Add a value to the Skip List
194    /// </summary>
195    public virtual void Add(T value) {
196      int valueLevels = getRandomLevels(); //determine height of value's tower
197
198      //Add levels to entire list if necessary
199      int newLevelCount = valueLevels - this.levels; //number of levels missing
200      while (newLevelCount > 0) {
201        //Create new level
202        SkipListNode<T> newLevel = getEmptyLevel();
203
204        //Link down
205        newLevel.Below = this.topLeft;
206        this.topLeft.Above = newLevel;
207        this.topLeft = newLevel; //update reference to most top-left node
208
209        //Update counters
210        newLevelCount--;
211        this.levels++;
212      }
213
214      //Insert the value in the proper position, creating as many levels as was randomly determined
215      SkipListNode<T> currentNode = this.topLeft;
216      SkipListNode<T> lastNodeAbove = null; //keeps track of the upper-level nodes in a tower
217      int currentLevel = this.levels - 1;
218
219      while (currentLevel >= 0 && currentNode != null) {
220        if (currentLevel > valueLevels) //too high on the list, nothing would be added to this level
221        {
222          currentNode = currentNode.Below; //scan down
223          currentLevel--; //going one level lower
224          continue; //skip adding to this level
225        }
226
227        //Add the value to the current level
228
229        //Find the biggest value on the current level that is less than the value to be added
230        while (currentNode.Next != null) {
231          if (!currentNode.Next.IsFooter() && currentNode.Next.Value.CompareTo(value) < 0) //smaller
232            currentNode = currentNode.Next; //keep scanning across
233          else
234            break; //the next node would be bigger than the value
235
236        }
237
238        //Insert the value right after the node found
239        SkipListNode<T> newNode = new SkipListNode<T>(value);
240        newNode.Next = currentNode.Next;
241        newNode.Previous = currentNode;
242        newNode.Next.Previous = newNode;
243        currentNode.Next = newNode;
244
245        //Link down/up the tower
246        if (lastNodeAbove != null) //is this node part of a tower?
247        {
248          lastNodeAbove.Below = newNode;
249          newNode.Above = lastNodeAbove;
250        }
251        lastNodeAbove = newNode; //start/continue tower
252
253        //Scan down
254        currentNode = currentNode.Below;
255        currentLevel--;
256      }
257
258      this.size++; //update count
259    }
260
261    /// <summary>
262    /// Returns the first node whose value matches the input value
263    /// </summary>
264    public virtual SkipListNode<T> Find(T value) {
265      SkipListNode<T> foundNode = this.topLeft;
266
267      //Look for the highest-level node with an element value matching the parameter value
268      while (foundNode != null && foundNode.Next != null) {
269        if (!foundNode.Next.IsFooter() && foundNode.Next.Value.CompareTo(value) < 0) //next node's value is still smaller
270          foundNode = foundNode.Next; //keep scanning across
271        else {
272          if (!foundNode.Next.IsFooter() && foundNode.Next.Value.Equals(value)) //value found
273          {
274            foundNode = foundNode.Next;
275            break;
276          } else
277            foundNode = foundNode.Below; //element not in this level, scan down
278        }
279      }
280
281      return foundNode;
282    }
283
284    /// <summary>
285    /// Returns the lowest node on the first tower to match the input value
286    /// </summary>
287    public virtual SkipListNode<T> FindLowest(T value) {
288      SkipListNode<T> valueNode = this.Find(value);
289      return this.FindLowest(valueNode);
290    }
291
292    /// <summary>
293    /// Returns the lowest node on the first tower to match the input value
294    /// </summary>
295    public virtual SkipListNode<T> FindLowest(SkipListNode<T> valueNode) {
296      if (valueNode == null)
297        return null;
298      else {
299        //Scan down to the lowest level
300        while (valueNode.Below != null) {
301          valueNode = valueNode.Below;
302        }
303        return valueNode;
304      }
305    }
306
307    /// <summary>
308    /// Returns the highest node on the first tower to match the input value
309    /// </summary>
310    public virtual SkipListNode<T> FindHighest(T value) {
311      SkipListNode<T> valueNode = this.Find(value);
312      return this.FindHighest(valueNode);
313    }
314
315    /// <summary>
316    /// Returns the highest node on the first tower to match the input value
317    /// </summary>
318    public virtual SkipListNode<T> FindHighest(SkipListNode<T> valueNode) {
319      if (valueNode == null)
320        return null;
321      else {
322        //Scan up to the highest level
323        while (valueNode.Above != null) {
324          valueNode = valueNode.Above;
325        }
326        return valueNode;
327      }
328    }
329
330    /// <summary>
331    /// Returns whether a value exists in the Skip List
332    /// </summary>
333    public virtual bool Contains(T value) {
334      return (this.Find(value) != null);
335    }
336
337    /// <summary>
338    /// Removes a value or node from the Skip List
339    /// </summary>
340    public virtual bool Remove(T value) {
341      SkipListNode<T> valueNode = this.FindHighest(value);
342      return this.Remove(valueNode);
343    }
344
345    /// <summary>
346    /// Removes a value or node from the Skip List
347    /// </summary>
348    public virtual bool Remove(SkipListNode<T> valueNode) {
349      if (valueNode == null)
350        return false;
351      else {
352        //Make sure node is top-level node in it's tower
353        if (valueNode.Above != null)
354          valueNode = this.FindHighest(valueNode);
355
356        //---Delete nodes going down the tower
357        SkipListNode<T> currentNodeDown = valueNode;
358        while (currentNodeDown != null) {
359          //Remove right-left links
360          SkipListNode<T> previousNode = currentNodeDown.Previous;
361          SkipListNode<T> nextNode = currentNodeDown.Next;
362
363          //Link the previous and next nodes to each other
364          previousNode.Next = nextNode;
365          nextNode.Previous = previousNode;
366
367          SkipListNode<T> belowNode = currentNodeDown.Below; //scan down
368          currentNodeDown.Dispose(); //unlink previous
369
370          currentNodeDown = belowNode;
371        }
372
373        //update counter
374        this.size--;
375
376        //Clean up the Skip List by removing levels that are now empty
377        this.clearEmptyLevels();
378
379        return true;
380      }
381    }
382
383    /// <summary>
384    /// Removes all values in the Skip List
385    /// </summary>
386    public virtual void Clear() {
387      SkipListNode<T> currentNode = this.Head;
388
389      while (currentNode != null) {
390        SkipListNode<T> nextNode = currentNode.Next; //save reference to next node
391
392        if (!currentNode.IsHeader() && !currentNode.IsFooter()) {
393          this.Remove(currentNode);
394        }
395
396        currentNode = nextNode;
397      }
398    }
399
400    /// <summary>
401    /// Copies the values of the Skip List to an array
402    /// </summary>
403    public virtual void CopyTo(T[] array) {
404      CopyTo(array, 0);
405    }
406
407    /// <summary>
408    /// Copies the values of the Skip List to an array
409    /// </summary>
410    public virtual void CopyTo(T[] array, int startIndex) {
411      IEnumerator<T> enumerator = this.GetEnumerator();
412
413      for (int i = startIndex; i < array.Length; i++) {
414        if (enumerator.MoveNext())
415          array[i] = enumerator.Current;
416        else
417          break;
418      }
419    }
420
421    /// <summary>
422    /// Gets the number of levels of a value in the Skip List
423    /// </summary>
424    public virtual int GetHeight(T value) {
425      SkipListNode<T> valueNode = this.FindLowest(value);
426      return this.GetHeight(valueNode);
427    }
428
429    /// <summary>
430    /// Gets the number of levels of a value in the Skip List
431    /// </summary>
432    public virtual int GetHeight(SkipListNode<T> valueNode) {
433      int height = 0;
434      SkipListNode<T> currentNode = valueNode;
435
436      //Move all the way down to the bottom first
437      while (currentNode.Below != null) {
438        currentNode = currentNode.Below;
439      }
440
441      //ExpressionCount going back up to the top
442      while (currentNode != null) {
443        height++;
444        currentNode = currentNode.Above;
445      }
446
447      return height;
448    }
449
450    /// <summary>
451    /// Gets the enumerator for the Skip List
452    /// </summary>
453    public IEnumerator<T> GetEnumerator() {
454      return new SkipListEnumerator(this);
455    }
456
457    /// <summary>
458    /// Gets the enumerator for the Skip List
459    /// </summary>
460    IEnumerator IEnumerable.GetEnumerator() {
461      return this.GetEnumerator();
462    }
463
464    /// <summary>
465    /// Enumerator for a Skip List. Scans across the lowest level of a Skip List.
466    /// </summary>
467    internal class SkipListEnumerator : IEnumerator<T> {
468      private SkipListNode<T> current;
469      private SkipList<T> skipList;
470
471      public SkipListEnumerator(SkipList<T> skipList) {
472        this.skipList = skipList;
473      }
474
475      public T Current
476      {
477        get { return current.Value; }
478      }
479
480      object IEnumerator.Current
481      {
482        get { return this.Current; }
483      }
484
485      public void Dispose() {
486        current = null;
487      }
488
489      public void Reset() {
490        current = null;
491      }
492
493      public bool MoveNext() {
494        if (current == null)
495          current = this.skipList.Head.Next; //Head is header node, start after
496        else
497          current = current.Next;
498
499        if (current != null && current.IsFooter())
500          current = null; //end of list
501
502        return (current != null);
503      }
504    }
505  }
506}
Note: See TracBrowser for help on using the repository browser.