SkipList.cs

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace DataStructures.LinkedList.SkipList;

/// <summary>
/// Skip list implementation that is based on the singly linked list,
/// but offers O(log n) time complexity on most operations.
/// </summary>
/// <typeparam name="TValue">The type of the values in the list.</typeparam>
/// <remarks>
/// Skip list nodes sorted by key.
/// The "skip lanes" allow searching for a node in O(log n) time on average.
/// The worst case performence is O(n) when the height of all nodes is 1 (very
/// unluckily to happen on any decent list size).
/// These two properties make the skip list an excellent data structure for
/// implementing additional operations like finding min/max value in the list,
/// finding values with the key in a given range, etc.
///
/// Sourses:
/// - "Skip Lists: A Probabilistic Alternative to Balanced Trees" by William Pugh.
/// - https://en.wikipedia.org/wiki/Skip_list
/// - https://iq.opengenus.org/skip-list/
/// - https://medium.com/simple-computer-science/data-structures-basics-skip-list-8b8c69f9a044
/// - https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/lists/SkipList.java
///
/// The key is hardcoded to be of type <c>int</c> to simplify the implementation,
/// but it can be easily an any generic type that implements <c>IComparable</c>.
/// </remarks>
[DebuggerDisplay("Count = {Count}")]
public class SkipList<TValue>
{
    private const double Probability = 0.5;
    private readonly int maxLevels;
    private readonly SkipListNode<TValue> head;
    private readonly SkipListNode<TValue> tail;
    private readonly Random random = new Random();

    /// <summary>
    /// Initializes a new instance of the <see cref="SkipList{TValue}"/> class.
    /// </summary>
    /// <param name="capacity">Expected number of elements the list might contain.</param>
    public SkipList(int capacity = 255)
    {
        maxLevels = (int)Math.Log2(capacity) + 1;

        head = new(int.MinValue, default(TValue), maxLevels);
        tail = new(int.MaxValue, default(TValue), maxLevels);

        for(int i = 0; i < maxLevels; i++)
        {
            head.Next[i] = tail;
        }
    }

    /// <summary>
    /// Gets the number of elements currently in the list.
    /// </summary>
    public int Count { get; private set; }

    /// <summary>
    /// Gets or sets the element with the specified key.
    /// </summary>
    /// <exception cref="KeyNotFoundException">The key is not present in the list.</exception>
    public TValue this[int key]
    {
        get
        {
            var previousNode = GetSkipNodes(key).First();
            if(previousNode.Next[0].Key == key)
            {
                return previousNode.Next[0].Value!;
            }
            else
            {
                throw new KeyNotFoundException();
            }
        }

        set => AddOrUpdate(key, value);
    }

    /// <summary>
    /// Adds an element with the specified key and value to the list.
    /// If an element with the same key already exists, updates its value.
    /// </summary>
    /// <param name="key">The key of the element to add.</param>
    /// <param name="value">The value of the element to add.</param>
    /// <remarks>
    /// Time complexity: O(log n) where n is the number of elements in the list.
    /// </remarks>
    public void AddOrUpdate(int key, TValue value)
    {
        var skipNodes = GetSkipNodes(key);

        var previousNode = skipNodes.First();
        if (previousNode.Next[0].Key == key)
        {
            // Node with the given key already exists.
            // Update its value.
            previousNode.Next[0].Value = value;
            return;
        }

        // Node with the given key does not exist.
        // Insert the new one and update the skip nodes.
        var newNode = new SkipListNode<TValue>(key, value, GetRandomHeight());
        for (var level = 0; level < newNode.Height; level++)
        {
            newNode.Next[level] = skipNodes[level].Next[level];
            skipNodes[level].Next[level] = newNode;
        }

        Count++;
    }

    /// <summary>
    /// Returns whether a value with the given key exists in the list.
    /// </summary>
    /// <remarks>
    /// Time complexity: O(log n) where n is the number of elements in the list.
    /// </remarks>
    public bool Contains(int key)
    {
        var previousNode = GetSkipNodes(key).First();
        return previousNode.Next[0].Key == key;
    }

    /// <summary>
    /// Removes the value with the given key from the list.
    /// </summary>
    /// <returns>
    /// <c>true</c> if the value was removed; otherwise, <c>false</c>.
    /// </returns>
    /// <remarks>
    /// Time complexity: O(log n) where n is the number of elements in the list.
    /// </remarks>
    public bool Remove(int key)
    {
        var skipNodes = GetSkipNodes(key);
        var previousNode = skipNodes.First();
        if (previousNode.Next[0].Key != key)
        {
            return false;
        }

        // Key exists in the list, remove it and update the skip nodes.
        var nodeToRemove = previousNode.Next[0];
        for (var level = 0; level < nodeToRemove.Height; level++)
        {
            skipNodes[level].Next[level] = nodeToRemove.Next[level];
        }

        Count--;

        return true;
    }

    /// <summary>
    /// Returns an enumerator that iterates through the list.
    /// </summary>
    /// <remarks>
    /// Order of values is the ascending order of their keys.
    /// Time complexity: O(n) where n is the number of elements in the list.
    /// </remarks>
    public IEnumerable<TValue> GetValues()
    {
        var current = head.Next[0];
        while (current.Key != tail.Key)
        {
            yield return current.Value!;
            current = current.Next[0];
        }
    }

    /// <summary>
    /// Builds a list of skip nodes on each level that
    /// are closest, but smaller than the given key.
    /// </summary>
    /// <remarks>
    /// The node on level 0 will point to the node with the given key, if it exists.
    /// Time complexity: O(log n) where n is the number of elements in the list.
    /// </remarks>
    private SkipListNode<TValue>[] GetSkipNodes(int key)
    {
        var skipNodes = new SkipListNode<TValue>[maxLevels];
        var current = head;
        for (var level = head.Height - 1; level >= 0; level--)
        {
            while (current.Next[level].Key < key)
            {
                current = current.Next[level];
            }

            skipNodes[level] = current;
        }

        return skipNodes;
    }

    /// <summary>
    /// Determines the height of skip levels for the new node.
    /// </summary>
    /// <remarks>
    /// Probability of the next level is 1/(2^level).
    /// </remarks>
    private int GetRandomHeight()
    {
        int height = 1;
        while (random.NextDouble() < Probability && height < maxLevels)
        {
            height++;
        }

        return height;
    }
}