< Summary

Class:Towel.DataStructures.SkipList<T1, T2, T3>
Assembly:Towel
File(s):File 1: /home/runner/work/Towel/Towel/Sources/Towel/DataStructures/SkipList.cs
Covered lines:178
Uncovered lines:13
Coverable lines:191
Total lines:345
Line coverage:93.1% (178 of 191)
Covered branches:60
Total branches:62
Branch coverage:96.7% (60 of 62)

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
File 1: get_Level()100%1100%
File 1: .ctor(...)100%1100%
File 1: StepperBreak(...)100%2100%
File 1: .ctor(...)50%281.81%
File 1: get_Count()100%1100%
File 1: get_Levels()100%10%
File 1: get_Compare()100%10%
File 1: get_Random()100%10%
File 1: Search(...)100%14100%
File 1: Contains(...)100%1100%
File 1: SearchNext(...)100%10100%
File 1: RandomLevelNode(...)100%4100%
File 1: Remove(...)100%2100%
File 1: TryRemove(...)100%2100%
File 1: Clear()100%2100%
File 1: GetEnumerator()50%257.14%
File 1: System.Collections.IEnumerable.GetEnumerator()100%10%
File 1: RemoveAll(...)100%2100%
File 1: StepperBreak(...)100%1100%
File 1: ToArray()100%2100%
File 1: TryAdd(...)100%8100%
File 1: TryRemoveFirst(...)100%271.42%
File 1: Clone()100%8100%

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) =>
 15    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
 4892449    internal byte Level => (byte)_next.Length;
 50
 3054451    internal Node(byte length, T data)
 3054452    {
 3054453      _value = data;
 3054454      _next = new Node[length];
 3054455    }
 56
 57    internal StepStatus StepperBreak<TStep>(TStep step = default)
 58      where TStep : struct, IFunc<T, StepStatus>
 759    {
 760      Node? node = _next[0];
 868161      while (node is not null)
 867462      {
 867463        step.Invoke(node._value);
 867464        node = node._next[0];
 867465      }
 766      return StepStatus.Break;
 767    }
 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>
 1678  public SkipList(byte levels, TCompare compare = default, TRandom random = default)
 1679  {
 1680    if (levels < 2)
 081    {
 082      throw new ArgumentException("SkipList must have at least 2 levels", nameof(levels));
 83    }
 1684    _levels = levels;
 1685    _front = new Node(_levels, default!);
 1686    _count = 0;
 1687    _compare = compare;
 1688    _random = random;
 1689  }
 90
 91  #endregion
 92
 93  #region Properties
 94
 95  /// <inheritdoc/>
 1196  public int Count => _count;
 97
 98  /// <summary>The current number of levels in this <see cref="SkipList{T, TCompare, TRandom}"/>.</summary>
 099  public int Levels => _levels;
 100
 101  /// <inheritdoc/>
 0102  public TCompare Compare => _compare;
 103
 104  /// <summary>Gets the value of the random generation algorithm.</summary>
 0105  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)
 33036838127  {
 33036838128    node = _front;
 33036838129    links = new Node[_levels];
 130    Node? x;
 131    int c;
 1377467378132    for (c = 0; c < _levels; c++)
 655696851133    {
 655696851134      links[c] = _front;
 655696851135    }
 33036838136    int next = _levels - 1;
 137    CompareResult res;
 138    do
 994821457139    {
 994821457140      links[next] = node;
 994821457141      x = node._next[next];
 1650479499142      if (x is null || (res = _compare.Invoke(value, x._value)) is Less) next--;
 678298229143      else if (res is Greater) node = links[next] = x;
 47845144      else if (quick || next is 0) return x == (node = x);
 9357145      else next--;
 1989604426146    } while (next >= 0);
 33017594147    node = null;
 33017594148    return false;
 33036838149  }
 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>
 33001000154  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>
 4557158  {
 4557159    if (previous is null)
 7160    {
 7161      previous = new Node[_levels];
 106162      for (int i = 0; i < _levels; i++)
 46163      {
 46164        previous[i] = _front;
 46165      }
 7166    }
 4557167    Node? node = previous[0]._next[0];
 5151168    while (node is not null)
 5147169    {
 5147170      if (predicate.Invoke(node._value))
 4553171      {
 4553172        break;
 173      }
 3494174      for (int i = node.Level - 1; i >= 0; i--)
 1153175      {
 1153176        previous[i] = node;
 1153177      }
 594178      node = node._next[0];
 594179    }
 4557180    return (node, previous);
 4557181  }
 182
 183  internal Node RandomLevelNode(T value)
 26528184  {
 26528185    byte l = 1;
 52977186    while (_random.Invoke(0, 2) is 1 && l < _levels)
 26449187    {
 26449188      l++;
 26449189    }
 26528190    return new(l, value);
 26528191  }
 192
 193  internal void Remove(Node node, Node[] prev)
 13753194  {
 82934195    for (int i = node.Level - 1; i >= 0; i--)
 27714196    {
 27714197      prev[i]._next[i] = node._next[i];
 27714198    }
 13753199    _count--;
 13753200    node._next = null!;
 13753201  }
 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)
 9310207  {
 9310208    Search(value, out var node, out var links, false); // Need to do slow search only here
 9310209    if (node is not null)
 9200210    {
 9200211      Remove(node, links);
 9200212      return (true, null);
 213    }
 110214    return (false, new ArgumentException("Attempting to remove a non-existing value."));
 9310215  }
 216
 217  /// <inheritdoc/>
 218  public void Clear()
 2219  {
 2220    _count = 0;
 84221    for (byte c = 0; c < _levels; c++)
 40222    {
 40223      _front._next[c] = null;
 40224    }
 2225  }
 226
 227  /// <inheritdoc/>
 228  public System.Collections.Generic.IEnumerator<T> GetEnumerator()
 2229  {
 2230    Node? node = _front._next[0];
 2231    while (node is not null)
 0232    {
 0233      yield return node._value;
 0234    }
 2235    yield break;
 236  }
 237
 0238  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>
 3242  {
 3243    var (node, links) = SearchNext(predicate: predicate);
 4553244    while (node is not null)
 4550245    {
 4550246      Remove(node, links);
 4550247      (node, links) = SearchNext(links, predicate);
 4550248    }
 3249  }
 250
 251  /// <inheritdoc/>
 252  public StepStatus StepperBreak<TStep>(TStep step = default)
 253    where TStep : struct, IFunc<T, StepStatus> =>
 7254    _front.StepperBreak(step);
 255
 256  /// <inheritdoc/>
 257  public T[] ToArray()
 9258  {
 9259    if (_count is 0)
 2260    {
 2261      return Array.Empty<T>();
 262    }
 7263    T[] array = new T[Count];
 7264    this.Stepper<T, FillArray<T>>(array);
 7265    return array;
 9266  }
 267
 268  /// <inheritdoc/>
 269  public (bool Success, Exception? Exception) TryAdd(T value)
 26528270  {
 26528271    Search(value, out var x, out var links, true); // Perfrom quick search
 26528272    Node node = RandomLevelNode(value);
 26528273    int i = 0;
 26528274    int nl = node.Level;
 26528275    if (x is not null) // Since prev is incomplete, the remaining data is obtained from x
 48276    {
 48277      int xl = x.Level;
 166278      for (; i < xl && i < nl; i++)
 59279      {
 59280        node._next[i] = x._next[i];
 59281        x._next[i] = node;
 59282      }
 48283    } // If x is not found, then prev is complete
 132364284    for (; i < nl; i++)
 52918285    {
 52918286      node._next[i] = links[i]._next[i];
 52918287      links[i]._next[i] = node;
 52918288    }
 26528289    _count++;
 26528290    return (true, null);
 26528291  }
 292
 293  /// <inheritdoc/>
 294  public bool TryRemoveFirst<TPredicate>(out Exception? exception, TPredicate predicate = default) where TPredicate : st
 4295  {
 4296    exception = null;
 297    try
 4298    {
 4299      var found = SearchNext(null, predicate);
 4300      if (found.Node is null)
 1301      {
 1302        return false;
 303      }
 3304      Remove(found.Node, found.prevs);
 3305      return true;
 306    }
 0307    catch (Exception ex)
 0308    {
 0309      exception = ex;
 0310      return false;
 311    }
 4312  }
 313
 314  /// <inheritdoc/>
 315  public SkipList<T, TCompare, TRandom> Clone()
 1316  {
 1317    SkipList<T, TCompare, TRandom>? clone = new(_levels, _compare);
 1318    Node? orig = _front._next[0];
 1319    Node[] prev = new Node[_levels];
 1320    Node clonenode = clone._front;
 321    int i;
 42322    for (i = _levels - 1; i >= 0; i--)
 20323    {
 20324      prev[i] = clonenode;
 20325    }
 4001326    while (orig is not null)
 4000327    {
 4000328      clonenode = clonenode._next[0] = new Node(orig.Level, orig._value);
 4000329      orig = orig._next[0];
 24120330      for (i = clonenode.Level - 1; i >= 0; i--)
 8060331      {
 8060332        prev[i] = prev[i]._next[i] = clonenode;
 8060333      }
 4000334    }
 6335    for (i = clonenode.Level - 1; i >= 0; i--)
 2336    {
 2337      prev[i]._next[i] = null;
 2338    }
 1339    clone._count = _count;
 1340    clone._random = _random;
 1341    return clone;
 1342  }
 343
 344  #endregion
 345}
Generated by: ReportGenerator 4.8.11.0
08/14/2022 - 14:40:44
GitHub | www.palmmedia.de

Methods/Properties

get_Level()
.ctor(...)
StepperBreak(...)
.ctor(...)
get_Count()
get_Levels()
get_Compare()
get_Random()
Search(...)
Contains(...)
SearchNext(...)
RandomLevelNode(...)
Remove(...)
TryRemove(...)
Clear()
GetEnumerator()
System.Collections.IEnumerable.GetEnumerator()
RemoveAll(...)
StepperBreak(...)
ToArray()
TryAdd(...)
TryRemoveFirst(...)
Clone()