< Summary

Class:Towel.DataStructures.SkipList
Assembly:Towel
File(s):File 1: /home/runner/work/Towel/Towel/Sources/Towel/DataStructures/SkipList.cs
Covered lines:1
Uncovered lines:0
Coverable lines:1
Total lines:345
Line coverage:100% (1 of 1)
Covered branches:4
Total branches:4
Branch coverage:100% (4 of 4)

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
File 1: New(...)100%4100%

File(s)

/home/runner/work/Towel/Towel/Sources/Towel/DataStructures/SkipList.cs

#LineLine coverage
 1namespace Towel.DataStructures;
 2
 3/// <summary>Static helpers for <see cref="SkipList{T, TCompare, TRandom}"/>.</summary>
 4public static class SkipList
 5{
 6  #region Extension Methods
 7
 8  /// <inheritdoc cref="SkipList{T, TCompare, TRandom}.SkipList(byte, TCompare, TRandom)" />
 9  /// <inheritdoc cref="SkipList{T, TCompare, TRandom}" />
 10  /// <returns>The new constructed <see cref="SkipList{T, TCompare, TRandom}"/>.</returns>
 11  public static SkipList<T, SFunc<T, T, CompareResult>, SFunc<int, int, int>> New<T>(
 12    byte levels,
 13    Func<T, T, CompareResult>? compare = null,
 14    Func<int, int, int>? random = null) =>
 1515    new(levels, compare ?? Compare, random ?? new Random().Next);
 16
 17  #endregion
 18}
 19
 20/// <summary>SkipList Data structure</summary>
 21/// <typeparam name="T">The type of values.</typeparam>
 22/// <typeparam name="TCompare">The type for comparing</typeparam>
 23/// <typeparam name="TRandom">The type for generation algorithm.</typeparam>
 24public class SkipList<T, TCompare, TRandom> : IList<T>,
 25  IDataStructure<T>,
 26  DataStructure.IAddable<T>,
 27  DataStructure.IRemovable<T>,
 28  DataStructure.ICountable,
 29  DataStructure.IClearable,
 30  DataStructure.IAuditable<T>,
 31  DataStructure.IComparing<T, TCompare>,
 32  ICloneable<SkipList<T, TCompare, TRandom>>
 33  where TCompare : struct, IFunc<T, T, CompareResult>
 34  where TRandom : struct, IFunc<int, int, int>
 35{
 36  internal TRandom _random;
 37  internal TCompare _compare;
 38  internal Node _front;
 39  internal int _count;
 40  internal byte _levels;
 41
 42  #region Nested Types
 43
 44  internal class Node
 45  {
 46    internal T _value;
 47    internal Node?[] _next;
 48
 49    internal byte Level => (byte)_next.Length;
 50
 51    internal Node(byte length, T data)
 52    {
 53      _value = data;
 54      _next = new Node[length];
 55    }
 56
 57    internal StepStatus StepperBreak<TStep>(TStep step = default)
 58      where TStep : struct, IFunc<T, StepStatus>
 59    {
 60      Node? node = _next[0];
 61      while (node is not null)
 62      {
 63        step.Invoke(node._value);
 64        node = node._next[0];
 65      }
 66      return StepStatus.Break;
 67    }
 68  }
 69
 70  #endregion
 71
 72  #region Constructors
 73
 74  /// <summary> Creates a new SkipList object</summary>
 75  /// <param name="levels">The levels of lists within this list</param>
 76  /// <param name="compare">The compare type for this list</param>
 77  /// <param name="random">The type for generation algorithm.</param>
 78  public SkipList(byte levels, TCompare compare = default, TRandom random = default)
 79  {
 80    if (levels < 2)
 81    {
 82      throw new ArgumentException("SkipList must have at least 2 levels", nameof(levels));
 83    }
 84    _levels = levels;
 85    _front = new Node(_levels, default!);
 86    _count = 0;
 87    _compare = compare;
 88    _random = random;
 89  }
 90
 91  #endregion
 92
 93  #region Properties
 94
 95  /// <inheritdoc/>
 96  public int Count => _count;
 97
 98  /// <summary>The current number of levels in this <see cref="SkipList{T, TCompare, TRandom}"/>.</summary>
 99  public int Levels => _levels;
 100
 101  /// <inheritdoc/>
 102  public TCompare Compare => _compare;
 103
 104  /// <summary>Gets the value of the random generation algorithm.</summary>
 105  public TRandom Random => _random;
 106
 107  #endregion
 108
 109  #region Methods
 110
 111  /// <summary>
 112  /// Searches for a value in the list.
 113  /// If search is successful the node containing the value is returned.
 114  /// Otherwise the node after which the insertion should ouccer is returned
 115  /// </summary>
 116  /// <param name="value">The value to search</param>
 117  /// <param name="node">The output node</param>
 118  /// <param name="links">The previous nodes on the search path</param>
 119  /// <param name="quick">If true performs search with previous links
 120  /// partially initialized. <br/>
 121  /// This is faster since as soon as the node with the given value is
 122  /// found, the search terminates. <br/>
 123  /// If false, all the previous links are prepared.
 124  /// </param>
 125  /// <returns>true on successful search, false otherwise</returns>
 126  internal bool Search(T value, out Node? node, out Node[] links, bool quick = false)
 127  {
 128    node = _front;
 129    links = new Node[_levels];
 130    Node? x;
 131    int c;
 132    for (c = 0; c < _levels; c++)
 133    {
 134      links[c] = _front;
 135    }
 136    int next = _levels - 1;
 137    CompareResult res;
 138    do
 139    {
 140      links[next] = node;
 141      x = node._next[next];
 142      if (x is null || (res = _compare.Invoke(value, x._value)) is Less) next--;
 143      else if (res is Greater) node = links[next] = x;
 144      else if (quick || next is 0) return x == (node = x);
 145      else next--;
 146    } while (next >= 0);
 147    node = null;
 148    return false;
 149  }
 150
 151  /// <summary>Searches for an value in the list</summary>
 152  /// <param name="value">The value to search</param>
 153  /// <returns>Returns true if search is successful, otherwise false</returns>
 154  public bool Contains(T value) => Search(value, out var _, out var _, true); // Perform quick search
 155
 156  internal (Node? Node, Node[] prevs) SearchNext<TPredicate>(Node[]? previous = null, TPredicate predicate = default)
 157    where TPredicate : struct, IFunc<T, bool>
 158  {
 159    if (previous is null)
 160    {
 161      previous = new Node[_levels];
 162      for (int i = 0; i < _levels; i++)
 163      {
 164        previous[i] = _front;
 165      }
 166    }
 167    Node? node = previous[0]._next[0];
 168    while (node is not null)
 169    {
 170      if (predicate.Invoke(node._value))
 171      {
 172        break;
 173      }
 174      for (int i = node.Level - 1; i >= 0; i--)
 175      {
 176        previous[i] = node;
 177      }
 178      node = node._next[0];
 179    }
 180    return (node, previous);
 181  }
 182
 183  internal Node RandomLevelNode(T value)
 184  {
 185    byte l = 1;
 186    while (_random.Invoke(0, 2) is 1 && l < _levels)
 187    {
 188      l++;
 189    }
 190    return new(l, value);
 191  }
 192
 193  internal void Remove(Node node, Node[] prev)
 194  {
 195    for (int i = node.Level - 1; i >= 0; i--)
 196    {
 197      prev[i]._next[i] = node._next[i];
 198    }
 199    _count--;
 200    node._next = null!;
 201  }
 202
 203  /// <summary>Searches and removes a value from the list (if found)</summary>
 204  /// <param name="value">The value to remove from the list</param>
 205  /// <returns>True if value is found and removed, otherwise false</returns>
 206  public (bool Success, Exception? Exception) TryRemove(T value)
 207  {
 208    Search(value, out var node, out var links, false); // Need to do slow search only here
 209    if (node is not null)
 210    {
 211      Remove(node, links);
 212      return (true, null);
 213    }
 214    return (false, new ArgumentException("Attempting to remove a non-existing value."));
 215  }
 216
 217  /// <inheritdoc/>
 218  public void Clear()
 219  {
 220    _count = 0;
 221    for (byte c = 0; c < _levels; c++)
 222    {
 223      _front._next[c] = null;
 224    }
 225  }
 226
 227  /// <inheritdoc/>
 228  public System.Collections.Generic.IEnumerator<T> GetEnumerator()
 229  {
 230    Node? node = _front._next[0];
 231    while (node is not null)
 232    {
 233      yield return node._value;
 234    }
 235    yield break;
 236  }
 237
 238  System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() => GetEnumerator();
 239
 240  /// <inheritdoc/>
 241  public void RemoveAll<TPredicate>(TPredicate predicate = default) where TPredicate : struct, IFunc<T, bool>
 242  {
 243    var (node, links) = SearchNext(predicate: predicate);
 244    while (node is not null)
 245    {
 246      Remove(node, links);
 247      (node, links) = SearchNext(links, predicate);
 248    }
 249  }
 250
 251  /// <inheritdoc/>
 252  public StepStatus StepperBreak<TStep>(TStep step = default)
 253    where TStep : struct, IFunc<T, StepStatus> =>
 254    _front.StepperBreak(step);
 255
 256  /// <inheritdoc/>
 257  public T[] ToArray()
 258  {
 259    if (_count is 0)
 260    {
 261      return Array.Empty<T>();
 262    }
 263    T[] array = new T[Count];
 264    this.Stepper<T, FillArray<T>>(array);
 265    return array;
 266  }
 267
 268  /// <inheritdoc/>
 269  public (bool Success, Exception? Exception) TryAdd(T value)
 270  {
 271    Search(value, out var x, out var links, true); // Perfrom quick search
 272    Node node = RandomLevelNode(value);
 273    int i = 0;
 274    int nl = node.Level;
 275    if (x is not null) // Since prev is incomplete, the remaining data is obtained from x
 276    {
 277      int xl = x.Level;
 278      for (; i < xl && i < nl; i++)
 279      {
 280        node._next[i] = x._next[i];
 281        x._next[i] = node;
 282      }
 283    } // If x is not found, then prev is complete
 284    for (; i < nl; i++)
 285    {
 286      node._next[i] = links[i]._next[i];
 287      links[i]._next[i] = node;
 288    }
 289    _count++;
 290    return (true, null);
 291  }
 292
 293  /// <inheritdoc/>
 294  public bool TryRemoveFirst<TPredicate>(out Exception? exception, TPredicate predicate = default) where TPredicate : st
 295  {
 296    exception = null;
 297    try
 298    {
 299      var found = SearchNext(null, predicate);
 300      if (found.Node is null)
 301      {
 302        return false;
 303      }
 304      Remove(found.Node, found.prevs);
 305      return true;
 306    }
 307    catch (Exception ex)
 308    {
 309      exception = ex;
 310      return false;
 311    }
 312  }
 313
 314  /// <inheritdoc/>
 315  public SkipList<T, TCompare, TRandom> Clone()
 316  {
 317    SkipList<T, TCompare, TRandom>? clone = new(_levels, _compare);
 318    Node? orig = _front._next[0];
 319    Node[] prev = new Node[_levels];
 320    Node clonenode = clone._front;
 321    int i;
 322    for (i = _levels - 1; i >= 0; i--)
 323    {
 324      prev[i] = clonenode;
 325    }
 326    while (orig is not null)
 327    {
 328      clonenode = clonenode._next[0] = new Node(orig.Level, orig._value);
 329      orig = orig._next[0];
 330      for (i = clonenode.Level - 1; i >= 0; i--)
 331      {
 332        prev[i] = prev[i]._next[i] = clonenode;
 333      }
 334    }
 335    for (i = clonenode.Level - 1; i >= 0; i--)
 336    {
 337      prev[i]._next[i] = null;
 338    }
 339    clone._count = _count;
 340    clone._random = _random;
 341    return clone;
 342  }
 343
 344  #endregion
 345}
Generated by: ReportGenerator 4.8.11.0
08/14/2022 - 14:40:44
GitHub | www.palmmedia.de

Methods/Properties

New(...)