Skip to content

Instantly share code, notes, and snippets.

@bbarry

bbarry/skiplist.cs

Last active December 1, 2016 17:11
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save bbarry/5e0f3cc1ac7f7521fe6ea25947f48ace to your computer and use it in GitHub Desktop.
Save bbarry/5e0f3cc1ac7f7521fe6ea25947f48ace to your computer and use it in GitHub Desktop.
Download ZIP
Raw
skiplist.cs
/// <summary>
/// A skip list is an ordered collection with O(log(n)) average case searching, inserting and removal. It also provides
/// O(n) enumeration and constant time access to the first element.
/// While the standard implementation is nondeterministic and based on overlapping forward linked lists, this
/// implementation is deterministic and uses double linked lists to provide constant time acess to the last element and
/// O(n) enumeration in reverse order as well as optimized insertion and removal for items in the last position.
/// </summary>
/// <typeparam name="T"></typeparam>
[PublicAPI]
[DebuggerDisplay("Count = {Count}, First = {SafeFirst}, Last = {SafeLast}")]
public class SkipList<T> : ICollection<T>, IEnumerable<T>, ICollection, IEnumerable
{
[NotNull]
private readonly Stack<Space> _emptySpaces;
[NotNull]
private readonly List<int> _heads;
[NotNull]
[ItemCanBeNull]
private readonly List<Node> _nodes;
[ItemCanBeNull]
private Node[] _cacheSlot;
/// <summary>
/// Initializes a new instance of the <see cref="SkipList{T}" /> class that has the default comparer
/// </summary>
public SkipList() : this(Array.Empty<T>(), Comparer<T>.Default, EqualityComparer<T>.Default) {}
/// <summary>
/// Initializes a new instance of the <see cref="SkipList{T}" /> class
/// that contains elements copied from the specified collection and uses a default comparer.
/// </summary>
/// <param name="collection">The collection whose elements are copied to the new <see cref="SkipList{T}" />.</param>
/// <exception cref="T:System.ArgumentNullException">
/// <paramref name="collection" /> is null.
/// </exception>
public SkipList([NotNull] IEnumerable<T> collection)
: this(collection, Comparer<T>.Default, EqualityComparer<T>.Default) {}
/// <summary>
/// Initializes a new instance of the <see cref="SkipList{T}" /> class
/// that contains elements copied from the specified collection and uses a default comparer.
/// </summary>
/// <param name="comparer">The <see cref="T:System.Collections.Generic.IComparer{T}" /> to use when comparing elements.</param>
/// <exception cref="T:System.ArgumentNullException">
/// <paramref name="comparer" /> is null.
/// </exception>
public SkipList([NotNull] IComparer<T> comparer) : this(Array.Empty<T>(), comparer, EqualityComparer<T>.Default) {}
/// <summary>
/// Initializes a new instance of the <see cref="SkipList{T}" /> class
/// that contains elements copied from the specified collection and uses a specified comparer.
/// </summary>
/// <param name="collection">The collection whose elements are copied to the new <see cref="SkipList{T}" />.</param>
/// <param name="comparer">The <see cref="T:System.Collections.Generic.IComparer{T}" /> to use when comparing elements.</param>
/// <param name="equalityComparer">
/// The <see cref="T:System.Collections.Generic.IEqualityComparer{T}" /> to use when
/// comparing elements for equality.
/// </param>
/// <exception cref="T:System.ArgumentNullException">
/// <paramref name="collection" /> is null. -or-
/// <paramref name="comparer" /> is null. -or-
/// <paramref name="equalityComparer" /> is null.
/// </exception>
public SkipList([NotNull] IEnumerable<T> collection, [NotNull] IComparer<T> comparer,
[NotNull] IEqualityComparer<T> equalityComparer)
{
if (collection == null)
{
throw new ArgumentNullException(nameof(collection));
}
if (comparer == null)
{
throw new ArgumentNullException(nameof(comparer));
}
if (equalityComparer == null)
{
throw new ArgumentNullException(nameof(equalityComparer));
}
Comparer = comparer;
EqualityComparer = equalityComparer;
_nodes = new List<Node>();
_emptySpaces = new Stack<Space>();
_heads = new List<int>();
AddRange(collection);
}
[DebuggerStepThrough]
private static int TrailingZeroCount(uint input)
{
//tzc is used to determine the distribution of forward references;
//whenever a new node is needed, tzc(_count + 1) + 1 forward references are added
//this ensures the proper distribution of forward references per node
//standard textbook tzc algorithm follows; replace with intrinsic whenever it becomes available
var c = 32;
input &= (uint) -input;
if (input != 0) c--;
if ((input & 0x0000FFFF) != 0) c -= 16;
if ((input & 0x00FF00FF) != 0) c -= 8;
if ((input & 0x0F0F0F0F) != 0) c -= 4;
if ((input & 0x33333333) != 0) c -= 2;
if ((input & 0x55555555) != 0) c -= 1;
return c;
}
/// <summary>
/// Adds the collection to the <see cref="SkipList{T}" />.
/// </summary>
/// <param name="collection">A collection of items to add to the <see cref="SkipList{T}" />.</param>
/// <exception cref="ArgumentNullException"><paramref name="collection" /> is null.</exception>
public void AddRange([NotNull] [ItemCanBeNull] IEnumerable<T> collection)
{
if (collection == null)
{
throw new ArgumentNullException(nameof(collection));
}
foreach (var item in collection)
{
Add(item);
}
}
/// <summary>
/// Gets the <see cref="IComparer{T}" /> for the <see cref="SkipList{T}" />.
/// </summary>
/// <value>
/// The <see cref="T:System.Collections.Generic.IComparer{T}" /> that is used when
/// comparing elements in the <see cref="SkipList{T}" />.
/// </value>
[NotNull]
public IComparer<T> Comparer { get; }
/// <summary>
/// Enumerates from this item towards <see cref="Last" />.
/// Item must be in the <see cref="SkipList{T}" /> and will be the first result.
/// </summary>
/// <param name="item">The item to start from.</param>
/// <returns>An enumerable starting from <paramref name="item" /> and heading towards <see cref="Last" />.</returns>
public Enumerable EnumerateFrom([CanBeNull] T item) => new Enumerable(this, item);
/// <summary>
/// Enumerates from this item towards <see cref="First" />.
/// Item must be in the <see cref="SkipList{T}" /> and will be the first result.
/// </summary>
/// <param name="item">The item to start from.</param>
/// <returns>An enumerable starting from <paramref name="item" /> and heading towards <see cref="First" />.</returns>
public ReverseEnumerable EnumerateFromReverse([CanBeNull] T item) => new ReverseEnumerable(this, item, true);
/// <summary>
/// Gets the <see cref="IEqualityComparer{T}" /> for the <see cref="SkipList{T}" />.
/// </summary>
/// <value>
/// The <see cref="T:System.Collections.Generic.IEqualityComparer{T}" /> that is used when
/// comparing elements in the <see cref="SkipList{T}" />.
/// </value>
[NotNull]
public IEqualityComparer<T> EqualityComparer { get; }
/// <summary>
/// Gets the first element in the <see cref="SkipList{T}" /> as ordered by the <see cref="Comparer" />.
/// </summary>
/// <value>The first element contained in the <see cref="SkipList{T}" />.</value>
[CanBeNull]
public T First
{
get
{
if (Count == 0) throw new InvalidOperationException("The collection is empty.");
return _nodes[_heads[0]].Value;
}
}
/// <summary>
/// Returns an enumerator that iterates through the <see cref="SkipList{T}" /> in ascending order as determined by the
/// <see cref="Comparer" />.
/// </summary>
/// <returns>An enumerator for the contents of the <see cref="SkipList{T}" />.</returns>
public Enumerator GetEnumerator() => new Enumerator(this);
/// <summary>
/// Gets the last element in the <see cref="SkipList{T}" /> as ordered by the <see cref="Comparer" />.
/// </summary>
/// <value>The last element contained in the <see cref="SkipList{T}" />.</value>
[CanBeNull]
public T Last
{
get
{
if (Count == 0) throw new InvalidOperationException("The collection is empty.");
return _nodes[_nodes[_heads[0]].Previous].Value;
}
}
/// <summary>
/// Removes the first item from the <see cref="SkipList{T}" />.
/// </summary>
/// <returns>true if an item was removed; false otherwise</returns>
public bool RemoveFirst()
{
if (Count == 0)
{
return false;
}
if (Count == 1)
{
Clear();
return true;
}
Count--;
var minIndex = _heads[0];
var min = _nodes[minIndex];
var next = _nodes[min.Next];
if (next != null)
{
next.Previous = min.Previous;
}
var i = 0;
_nodes[minIndex] = null;
for (; i < min.NextCount && i < _heads.Count && next != null; i++)
{
next = _nodes[min.Next + i];
if (next != null) _heads[i] = next.Next - 1;
_nodes[min.Next + i] = null;
}
if (next == null)
{
_heads.RemoveRange(i - 1, _heads.Count - i + 1);
}
_emptySpaces.Push(new Space(min.Next - 1, min.NextCount));
DebugAssertInvariants();
return true;
}
/// <summary>
/// Removes the last item from the <see cref="SkipList{T}" />.
/// </summary>
/// <returns>true if an item was removed; false otherwise.</returns>
public bool RemoveLast()
{
if (Count == 0)
{
return false;
}
if (Count == 1)
{
Clear();
return true;
}
Count--;
var start = _nodes[_heads[0]];
var max = _nodes[start.Previous];
DebugAssert(max != null);
Node current = null;
var heads = _heads.Count;
for (var i = heads - 1; i >= 0; i--)
{
var next = current == null ? _nodes[_heads[i]] : _nodes[current.Next + i];
while (next != null && next != max)
{
current = next;
next = _nodes[current.Next + i];
}
if (current == null)
{
//removed the tallest element
heads = i;
continue;
}
if (next == max)
{
_nodes[current.Next + i] = null;
}
}
if (heads != _heads.Count)
{
_heads.RemoveRange(heads, _heads.Count - heads);
}
_nodes[max.NodeId] = null;
start.Previous = max.Previous;
_emptySpaces.Push(new Space(max.NodeId, max.NextCount));
DebugAssertInvariants();
return true;
}
/// <summary>
/// Enumerates the <see cref="SkipList{T}" /> from <see cref="Last" /> to <see cref="First" />.
/// </summary>
/// <returns>an enumerable struct to provide effecient enumeration for the <see cref="SkipList{T}" />.</returns>
public ReverseEnumerable Reverse() => new ReverseEnumerable(this, default(T), false);
/// <summary>
/// Attempts to add a new item to the start of the <see cref="SkipList{T}" />.
/// The new item must pass the comparison <code>Count == 0 || Comparer.Compare(First, item) &lt; 0</code>.
/// </summary>
/// <param name="item">The item to add to the <see cref="SkipList{T}" />.</param>
/// <returns>true if the item was added; false otherwise.</returns>
public bool TryAddFirst([CanBeNull] T item)
{
if (TryAddIfEmpty(item)) return true;
return TryAddFirstInternal(item);
}
/// <summary>
/// Attempts to add a new item to the end of the <see cref="SkipList{T}" />.
/// The new item must pass the comparison <code>Count == 0 || Comparer.Compare(Last, item) >= 0</code>.
/// </summary>
/// <param name="item">The item to add to the <see cref="SkipList{T}" />.</param>
/// <returns>true if the item was added; false otherwise.</returns>
public bool TryAddLast([CanBeNull] T item)
{
if (TryAddIfEmpty(item))
{
return true;
}
return TryAddLastInternal(item);
}
/// <summary>
/// Cache for the toBeUpdated array for general case adds and removals to reduce allocations.
/// </summary>
[NotNull]
private Node[] AcquireNodeArray(int size)
{
if (_cacheSlot == null || _cacheSlot.Length < size) return new Node[size];
var take = _cacheSlot;
_cacheSlot = null;
return take;
}
private Space Allocate()
{
DebugAssert(_emptySpaces.Count == 0);
var nextCount = TrailingZeroCount((uint) (Count + 1)) + 1;
var index = _nodes.Count;
_nodes.AddRange(System.Linq.Enumerable.Repeat(default(Node), nextCount + 1));
return new Space(index, nextCount);
}
[Conditional("debugging")]
[ContractAnnotation("assertion: false => halt")]
private void DebugAssert(bool assertion, string text = "")
{
if (!assertion) throw new Exception(text);
}
[Conditional("debugging")]
private void DebugAssertInvariants()
{
if (Count == 0)
{
DebugAssert(_nodes.Count == 0);
DebugAssert(_heads.Count == 0);
DebugAssert(_emptySpaces.Count == 0);
return;
}
DebugAssert(_heads.Count > 0);
//weak assertions on IEnumerable basis
// var array = this.ToArray();
// DebugAssert(array.Length == _count);
// for (int i = 1; i < array.Length; i++)
// {
// DebugAssert(_comparer.Compare(array[i-1],array[i])<=0);
// }
// DebugAssert(_comparer.Compare(array[0], Minimum) == 0);
// DebugAssert(_comparer.Compare(array[array.Length - 1], Maximum) == 0);
//stronger assertions based on assumed implementation details
//each element in _nodes is either an identified node (index == node.NodeId)
//the nodes array fits a particular pattern:
// node, 1fr, node, 2fr, node, 1fr, node, 3fr, node, 1fr, node, 2fr, node, 1fr, ...
// see https://oeis.org/A001511
//identified nodes must be in _emptySpaces if they are null and all forward references must be null
//identified nodes must not be in _emptySpaces if they are not null
//though these nodes may not be representative of the order of the structure, each node is referentially sound:
// the foward references for a node must be representing a value at least as large as the node (or null: end of list)
// each node must also hold in the Previous property the index of the identified node
// also given a node that is not the start of the list, the first forward reference of the previous node must be the given node
//finally, all empty spaces must be accounted for and the count of the structure must be the number of identified nodes that are not null
var spaces = _emptySpaces.ToDictionary(key => key.NodeId, v => v.NextCount);
var n = 0;
var c = 0;
var ruler = 0;
while (n < _nodes.Count)
{
ruler++;
var nextcount = TrailingZeroCount((uint) ruler) + 1;
var node = _nodes[n];
if (node == null)
{
DebugAssert(spaces.Remove(n));
for (var i = 1; i <= nextcount; i++)
{
DebugAssert(_nodes[n + i] == null);
}
n += 1 + nextcount;
continue;
}
c++;
DebugAssert(!spaces.ContainsKey(n));
DebugAssert(node.NextCount == nextcount);
DebugAssert(node.Previous == _nodes[node.Previous].NodeId);
if (n != _heads[0])
{
DebugAssert(Comparer.Compare(_nodes[node.Previous].Value, node.Value) <= 0);
DebugAssert(_nodes[_nodes[node.Previous].Next] == node);
}
else
{
DebugAssert(Comparer.Compare(SafeFirst, node.Value) == 0);
}
var i1 = 1;
for (; i1 <= nextcount && _nodes[n + i1] != null; i1++)
{
var node1 = _nodes[n + i1];
DebugAssert(Comparer.Compare(_nodes[n + i1 - 1].Value, node1.Value) <= 0);
DebugAssert(node1.NextCount >= i1);
}
if (i1 == 1)
{
DebugAssert(Comparer.Compare(node.Value, SafeLast) == 0);
}
for (; i1 <= nextcount; i1++)
{
DebugAssert(_nodes[n + i1] == null);
}
n += 1 + nextcount;
}
DebugAssert(Count == c);
DebugAssert(spaces.Count == 0);
}
private int FindIndex([CanBeNull] T item)
{
if (Count == 0) return -1;
Node current = null;
for (var i = _heads.Count - 1; i >= 0; i--)
{
var next = current == null ? _nodes[_heads[i]] : _nodes[current.Next + i];
while (next != null && Comparer.Compare(next.Value, item) < 0)
{
DebugAssert(next.NextCount >= i);
current = next;
next = _nodes[current.Next + i];
}
if (next != null && EqualityComparer.Equals(next.Value, item))
{
return next.NodeId;
}
}
// no further ordering is possible; must check all elements that sort equivalently
// as candidates to be equal to the provided item
while (current != null && Comparer.Compare(current.Value, item) <= 0)
{
if (EqualityComparer.Equals(current.Value, item)) return current.NodeId;
current = _nodes[current.Next];
}
return -2;
}
private Space FindSpace()
{
var space = _emptySpaces.Count > 0 ? _emptySpaces.Pop() : Allocate();
#if debugging
for (var i = 0; i < space.NextCount; i++)
{
if (_nodes[space.NodeId + space.NextCount] != null)
{
throw new Exception("found space was not available");
}
}
#endif
return space;
}
private void ReleaseNodeArray([NotNull] Node[] array)
{
if (_cacheSlot == null || array.Length > _cacheSlot.Length) _cacheSlot = array;
}
[CanBeNull]
private T SafeFirst
{
get
{
if (Count == 0) throw new InvalidOperationException("The collection is empty.");
return _nodes[_heads[0]].Value;
}
}
[CanBeNull]
private T SafeLast
{
get
{
if (Count == 0) return default(T);
return _nodes[_nodes[_heads[0]].Previous].Value;
}
}
private bool TryAddFirstInternal([CanBeNull] T item)
{
DebugAssert(Count > 0, "must have items already");
var beginning = _nodes[_heads[0]];
if (Comparer.Compare(item, beginning.Value) >= 0)
{
return false;
}
//minimum adds must insert at the beginnings of each head list
//logic is much like the general case except we know toBeUpdated would be filled with nulls
//1.
var space = FindSpace();
//2. (empty)
//3.
Count++;
var newnode = new Node(item, space.NodeId + 1, space.NextCount);
_nodes[space.NodeId] = newnode;
for (var index = 0; index < space.NextCount && index < _heads.Count; index++)
{
_nodes[newnode.Next + index] = _nodes[_heads[index]];
_heads[index] = newnode.NodeId;
}
//4.
newnode.Previous = beginning.Previous;
beginning.Previous = space.NodeId;
//5.
while (_heads.Count < space.NextCount)
{
_heads.Add(space.NodeId);
}
DebugAssertInvariants();
return true;
}
private bool TryAddIfEmpty([CanBeNull] T item)
{
if (Count != 0)
{
return false;
}
//optimized form for adding the first node without checking conditions that are known
Count++;
_nodes.Add(new Node(item, 1, 1));
_nodes.Add(null);
_heads.Add(0);
DebugAssertInvariants();
return true;
}
private bool TryAddLastInternal([CanBeNull] T item)
{
DebugAssert(Count > 0, "must have items already");
var beginning = _nodes[_heads[0]];
var end = _nodes[beginning.Previous];
if (Comparer.Compare(item, end.Value) < 0)
{
return false;
}
//logic is again similar to the general case except that no items need to be compared internally
//instead just look for the first null item at each level needed and set it
//thus we roll steps 2 and 3 together:
//1.
var space = FindSpace();
//2+3.
Count++;
var newnode = new Node(item, space.NodeId + 1, space.NextCount);
_nodes[space.NodeId] = newnode;
Node current = null;
for (var i = _heads.Count - 1; i >= 0; i--)
{
var next = current == null ? _nodes[_heads[i]] : _nodes[current.Next + i];
while (next != null)
{
DebugAssert(next.NextCount >= i);
current = next;
next = _nodes[current.Next + i];
}
if (i < space.NextCount)
{
DebugAssert(current != null);
_nodes[current.Next + i] = newnode;
}
}
//4.
newnode.Previous = beginning.Previous;
beginning.Previous = space.NodeId;
//5.
while (_heads.Count < space.NextCount)
{
_heads.Add(space.NodeId);
}
DebugAssertInvariants();
return true;
}
void ICollection.CopyTo(Array array, int index)
{
var length = array.Length;
foreach (var item in this)
{
if (index >= length) return;
array.SetValue(item, index);
index++;
}
}
/// <summary>
/// obsolete, unused
/// </summary>
object ICollection.SyncRoot => this;
/// <summary>
/// obsolete, unused
/// </summary>
bool ICollection.IsSynchronized => false;
/// <summary>
/// Adds the specified item to the collection
/// </summary>
/// <param name="item">
/// The object to add to the <see cref="SkipList{T}" />.
/// The value can be null for reference types.
/// </param>
public void Add([CanBeNull] T item)
{
//attempt optimized paths first
if (TryAddIfEmpty(item)) return;
if (TryAddFirstInternal(item)) return;
if (TryAddLastInternal(item)) return;
DebugAssert(Count > 0);
DebugAssert(Comparer.Compare(item, SafeFirst) >= 0);
DebugAssert(Comparer.Compare(item, SafeLast) < 0);
/* general case
* given:
*
* 10
* 6 --------- 10
* 4 --- 6 --- 8 --- 10
* 2 3 4 5 6 8 8 9 10 ...
*
* heads: [0, 2, 4, 8]
*
* calling Add(9):
*
* supposing space returned a NextCount of 5
* toBeUpdated will contain
* { 9, 8, 6, null, ...}
* and 8 will be the second node containing the value 8
* and all elements after [3]=null are unknown
*
* the new list would become
*
* 9
* 9 10
* 6 --------- 9 10
* 4 --- 6 --- 8 --- 9 10
* 2 3 4 5 6 8 8 9 9 10 ...
*
* and heads will contain [0, 2, 4, 8, 8]
*
* This is to be done with a particular algorithm:
* 1. find space in the _nodes list of a suitable size to satisfy the complexity requirements
* 2. create an array of nodes to be updated with an appropriate height
* 3. splice the new node into each of the logical linked lists
* 4. splice into the reverse order linked list
* 5. add any necessary new heads
* */
//1.
var space = FindSpace();
//2.
//note compare <= here vs a similar loop in Remove
var toBeUpdated = AcquireNodeArray(Math.Min(space.NextCount, _heads.Count));
Node current = null;
for (var i = _heads.Count - 1; i >= 0; i--)
{
var next = current == null ? _nodes[_heads[i]] : _nodes[current.Next + i];
while (next != null && Comparer.Compare(next.Value, item) <= 0)
{
DebugAssert(next.NextCount >= i);
current = next;
next = _nodes[current.Next + i];
}
if (i < space.NextCount)
{
toBeUpdated[i] = current;
}
}
//3.
Count++;
var newnode = new Node(item, space.NodeId + 1, space.NextCount);
_nodes[space.NodeId] = newnode;
for (var index = 0; index < newnode.NextCount && index < _heads.Count; index++)
{
DebugAssert(index < toBeUpdated.Length);
var before = toBeUpdated[index];
if (before == null)
{
_nodes[newnode.Next + index] = _nodes[_heads[index]];
_heads[index] = space.NodeId;
continue;
}
var after = _nodes[before.Next + index];
_nodes[newnode.Next + index] = after;
_nodes[before.Next + index] = newnode;
}
//4.
DebugAssert(toBeUpdated[0] != null); //or we would have done an AddMinimum
newnode.Previous = toBeUpdated[0].NodeId;
DebugAssert(_nodes[newnode.Next] != null); //or we would have done an AddMaximum
_nodes[newnode.Next].Previous = newnode.NodeId;
ReleaseNodeArray(toBeUpdated);
//5.
while (_heads.Count < space.NextCount)
{
_heads.Add(space.NodeId);
}
DebugAssertInvariants();
}
/// <summary>
/// Removes all elements from the <see cref="SkipList{T}" />.
/// </summary>
public void Clear()
{
_nodes.Clear();
_heads.Clear();
_emptySpaces.Clear();
Count = 0;
}
/// <summary>
/// Determines whether an element is in the <see cref="SkipList{T}" />.
/// </summary>
/// <param name="item">
/// The object to find in the <see cref="SkipList{T}" />.
/// The value can be null for reference types.
/// </param>
/// <returns>
/// true if item is found in the <see cref="SkipList{T}" />; otherwise, false.
/// </returns>
public bool Contains([CanBeNull] T item)
{
return FindIndex(item) >= 0;
}
/// <summary>
/// Copies the items from the <see cref="SkipList{T}" /> in order.
/// </summary>
/// <param name="array">The array to copy items to.</param>
/// <param name="arrayIndex">index in the array to begin the copy.</param>
public void CopyTo(T[] array, int arrayIndex)
{
var length = array.Length;
foreach (var item in this)
{
if (arrayIndex >= length) return;
array[arrayIndex] = item;
arrayIndex++;
}
}
/// <summary>
/// Gets the number of elements contained in the <see cref="SkipList{T}" />.
/// </summary>
/// <value>The number of elements contained in the <see cref="SkipList{T}" />.</value>
public int Count { get; private set; }
bool ICollection<T>.IsReadOnly => false;
/// <summary>
/// Removes the specified item from the <see cref="SkipList{T}" />.
/// </summary>
/// <param name="item">The item to remove from the <see cref="SkipList{T}" />.</param>
/// <returns>true if the item was removed; false otherwise</returns>
public bool Remove([CanBeNull] T item)
{
if (Count == 0) return false;
var beginning = _nodes[_heads[0]];
if (Comparer.Compare(item, beginning.Value) < 0)
{
//item not in this due to being smaller than first element
return false;
}
if (EqualityComparer.Equals(beginning.Value, item))
{
//optimized first item removal (no more compares needed)
return RemoveFirst();
}
var end = _nodes[beginning.Previous];
if (Comparer.Compare(item, end.Value) > 0)
{
//not in list due to being larger than max
return false;
}
if (EqualityComparer.Equals(end.Value, item) && !EqualityComparer.Equals(item, _nodes[end.Previous].Value))
{
//optimized last item removal (no more compares needed)
return RemoveLast();
}
DebugAssert(_heads.Count > 0);
var toBeUpdated = AcquireNodeArray(_heads.Count);
DebugAssert(toBeUpdated.Length >= _heads.Count);
Node previousnode = null;
for (var i = _heads.Count - 1; i >= 0; i--)
{
var next = previousnode == null ? _nodes[_heads[i]] : _nodes[previousnode.Next + i];
while (next != null && Comparer.Compare(next.Value, item) < 0)
{
DebugAssert(next.NextCount >= i);
previousnode = next;
next = _nodes[previousnode.Next + i];
}
toBeUpdated[i] = previousnode;
}
DebugAssert(previousnode != null);
var node = _nodes[previousnode.Next];
var m = 0;
while (node != null && Comparer.Compare(node.Value, item) <= 0)
{
if (EqualityComparer.Equals(node.Value, item)) goto Found;
toBeUpdated[node.NextCount - 1] = node;
m = Math.Max(m, node.NextCount - 1);
node = _nodes[node.Next];
}
//not found
ReleaseNodeArray(toBeUpdated);
return false;
Found: //goto used to prevent one call to Equals
previousnode = toBeUpdated[m];
for (var i = m - 1; i >= 0; i--)
{
if (toBeUpdated[i].NextCount >= previousnode.NextCount)
toBeUpdated[i] = previousnode;
else
previousnode = toBeUpdated[i];
}
var nodeId = node.NodeId;
_nodes[node.Next].Previous = node.Previous;
Count--;
DebugAssert(node.NextCount <= _heads.Count);
for (var index = 0; index < node.NextCount; index++)
{
var before = toBeUpdated[index];
var after = _nodes[node.Next + index];
_nodes[node.Next + index] = null;
if (before == null)
{
DebugAssert(index > 0);
if (after != null)
{
_heads[index] = after.NodeId;
}
else if (_heads.Count > index && _heads[index] == nodeId)
{
_heads.RemoveRange(index, _heads.Count - index);
}
continue;
}
_nodes[before.Next + index] = after;
DebugAssert(_heads[index] != nodeId);
}
_nodes[nodeId] = null;
_emptySpaces.Push(new Space(nodeId, node.NextCount));
ReleaseNodeArray(toBeUpdated);
DebugAssertInvariants();
return true;
}
IEnumerator<T> IEnumerable<T>.GetEnumerator() => new Enumerator(this);
IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
private class Node
{
//an alternative implementation would be to store a ValueIndex int and compute NextCount
//and store values in a seperate list
//if this is done, _nodes can also be replaced with an array of ints and a few method calls worth of inlined logic:
//given List<int> _nodes, these methods:
// T Value(int nodeid) => _values[_nodes[nodeid]];
// int NextCount(int nodeid) => TrailingZeroCount(_nodes[nodeid] + 1) + 1;
// int Next(int nodeid, int index) => _nodes[nodeid + 2 + index];
// int Previous(int nodeid) => _nodes[nodeid + 1];
//
//the resulting _nodes array would be
//[0, p0, f00, 1, p1, f01, f11, 2, p2, f02, 3, p3, f03, f13, f23, 4, p4, f04, ...
//
//I have not investigated if that is better
public Node(T value, int next, int nextCount)
{
Value = value;
Next = next;
NextCount = nextCount;
}
public int Next { get; } //_nodes[n.Next], _nodes[n.Next+1], ... _nodes[n.Next+n.NextCount - 1]
public int NextCount { get; }
public int NodeId => Next - 1;
public int Previous { get; set; }
public override string ToString()
{
return $"[{NodeId}]: {Value}";
}
public T Value { get; }
}
private struct Space
{
//This could easily be KeyValuePair<int,int> ... I happened to find this easier to read
public int NodeId { get; }
public int NextCount { get; }
public Space(int nodeId, int nextCount)
{
NodeId = nodeId;
NextCount = nextCount;
}
}
public struct Enumerator : IEnumerator<T>
{
private readonly SkipList<T> _list;
private int _index;
private readonly int _start;
public Enumerator(SkipList<T> list)
{
_list = list;
_start = -1;
_index = -1;
Current = default(T);
}
public Enumerator(SkipList<T> list, T start)
{
_list = list;
_start = list.FindIndex(start);
_index = -1;
Current = default(T);
}
public void Dispose() {}
public bool MoveNext()
{
if (_list.Count == 0 || _index == -2)
{
return End();
}
if (_index == -1)
{
_index = _start >= 0 ? _start : _list._heads[0];
Current = _list._nodes[_index].Value;
return true;
}
var node = _list._nodes[_index];
if (node == null)
{
return End();
}
_index = node.Next;
node = _list._nodes[_index];
if (node == null)
{
return End();
}
Current = node.Value;
return true;
}
private bool End()
{
_index = -2;
Current = default(T);
return false;
}
public void Reset()
{
_index = -1;
Current = default(T);
}
public T Current { get; private set; }
object IEnumerator.Current => Current;
}
public struct Enumerable : IEnumerable<T>
{
private readonly SkipList<T> _list;
private readonly T _item;
public Enumerable(SkipList<T> list, T item)
{
_list = list;
_item = item;
}
public Enumerator GetEnumerator() => new Enumerator(_list, _item);
IEnumerator<T> IEnumerable<T>.GetEnumerator() => new Enumerator(_list, _item);
IEnumerator IEnumerable.GetEnumerator() => new Enumerator(_list, _item);
}
public struct ReverseEnumerable : IEnumerable<T>
{
private readonly SkipList<T> _list;
private readonly T _item;
private readonly bool _useItem;
public ReverseEnumerable(SkipList<T> list, T item, bool useItem)
{
_list = list;
_item = item;
_useItem = useItem;
}
public ReverseEnumerator GetEnumerator() => new ReverseEnumerator(_list, _item, _useItem);
IEnumerator<T> IEnumerable<T>.GetEnumerator() => new ReverseEnumerator(_list, _item, _useItem);
IEnumerator IEnumerable.GetEnumerator() => new ReverseEnumerator(_list, _item, _useItem);
}
public struct ReverseEnumerator : IEnumerator<T>
{
private readonly SkipList<T> _list;
private int _index;
private readonly int _start;
public ReverseEnumerator(SkipList<T> list, T item, bool useItem)
{
_list = list;
_index = -1;
_start = useItem ? list.FindIndex(item) : -1;
Current = default(T);
}
public void Dispose() {}
public bool MoveNext()
{
if (_list.Count == 0 || _index == -2)
{
return End();
}
if (_index == -1)
{
_index = _start >= 0 ? _start : _list._nodes[_list._heads[0]].Previous;
Current = _list._nodes[_index].Value;
return true;
}
var node = _list._nodes[_index];
if (node.NodeId == _list._heads[0])
{
return End();
}
_index = node.Previous;
node = _list._nodes[_index];
if (node == null)
{
return End();
}
Current = node.Value;
return true;
}
private bool End()
{
_index = -2;
Current = default(T);
return false;
}
public void Reset()
{
_index = -1;
Current = default(T);
}
public T Current { get; private set; }
object IEnumerator.Current => Current;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment