data-structures-and-algorithms/skip-list

import assert from 'assert';

import Node from './Node.js';
import heads from './heads.js';

/**
 * Make a balanced Skip-list with p = 1/2 but randomizing the choice of
 * promoted nodes at each level.
 */
const makeQuasiRandom = (p, head) => {
    assert(p === 1 / 2);

    // Together, the if and while conditions guarantee that `makeQuasiRandom`
    // does not do anything if the number of elements is <= 1
    // TODO Could use some other constant?
    if (head.right === null) return head;

    while (head.right.right !== null) {
        const newHead = new Node(head.key, head);

        let current = head;
        let next = newHead;
        while (current.right !== null) {
            current = current.right;
            let previousPromoted = false;

            if (heads(1 / 2)) {
                previousPromoted = true;
                next = new Node(current.key, current, next);
                next.left.right = next;
                current.up = next;
                // TODO can reduce branching by getting rid of `previousPromoted`
            }

            if (current.right === null) break;
            current = current.right;
            if (!previousPromoted) {
                next = new Node(current.key, current, next);
                next.left.right = next;
                current.up = next;
            }
        }

        head.up = newHead;
        head = newHead;
        assert(head.right !== null);
    }

    return head;
};

export default makeQuasiRandom;