libphobos/libdruntime/core/internal/container/treap.d

/**
 * Treap container for internal usage.
 *
 * Copyright: Copyright Digital Mars 2014 - 2014.
 * License:   $(HTTP www.boost.org/LICENSE_1_0.txt, Boost License 1.0).
 */
module core.internal.container.treap;

static import common = core.internal.container.common;
import core.internal.qsort;

struct Treap(E)
{
nothrow:
    static struct Node
    {
        Node* left, right;
        E element;
        uint priority;
    }

    @disable this(this);

    ~this()
    {
        removeAll();
    }

    void initialize(ulong randSeed)
    {
        Rand _rand = { randSeed };
        rand = _rand;
    }

    void insert(E element) @nogc
    {
        root = insert(root, element);
    }

    void remove(E element)
    {
        remove(&root, element);
    }

    int opApply(scope int delegate(ref E) nothrow dg)
    {
        return (cast(const)&this).opApply((ref const E e) => dg(*cast(E*)&e));
    }

    int opApply(scope int delegate(ref const E) nothrow dg) const
    {
        return opApplyHelper(root, dg);
    }

    version (CoreUnittest)
    bool opEquals(E[] elements)
    {
        size_t i;
        foreach (e; this)
        {
            if (i >= elements.length)
                return false;
            if (e != elements[i++])
                return false;
        }
        return i == elements.length;
    }

    void removeAll()
    {
        removeAll(root);
        root = null;
    }

    version (CoreUnittest)
    bool valid()
    {
        return valid(root);
    }


    version (none)
    uint height()
    {
        static uint height(Node* node)
        {
            if (!node)
                return 0;
            auto left = height(node.left);
            auto right = height(node.right);
            return 1 + (left > right ? left : right);
        }
        return height(root);
    }

    version (none)
    size_t count()
    {
        static size_t count(Node* node)
        {
            if (!node)
                return 0;
            return count(node.left) + count(node.right) + 1;
        }
        return count(root);
    }


private:
    Node* root;
    Rand rand;

    Node* allocNode(E element) @nogc
    {
        Node* node = cast(Node*)common.xmalloc(Node.sizeof);
        node.left = node.right = null;
        node.priority = rand();
        node.element = element;
        return node;
    }

    Node* insert(Node* node, E element) @nogc
    {
        if (!node)
            return allocNode(element);
        else if (element < node.element)
        {
            node.left = insert(node.left, element);
            if (node.left.priority < node.priority)
                node = rotateR(node);
        }
        else if (element > node.element)
        {
            node.right = insert(node.right, element);
            if (node.right.priority < node.priority)
                node = rotateL(node);
        }
        else
        {} // ignore duplicate

        return node;
    }

static:

    void freeNode(Node* node)
    {
        common.free(node);
    }

    Node* rotateL(Node* root)
    {
        auto pivot = root.right;
        root.right = pivot.left;
        pivot.left = root;
        return pivot;
    }

    Node* rotateR(Node* root)
    {
        auto pivot = root.left;
        root.left = pivot.right;
        pivot.right = root;
        return pivot;
    }

    void remove(Node** ppnode, E element)
    {
        Node* node = *ppnode;
        if (!node)
            return; // element not in treap

        if (element < node.element)
        {
            remove(&node.left, element);
        }
        else if (element > node.element)
        {
            remove(&node.right, element);
        }
        else
        {
            while (node.left && node.right)
            {
                if (node.left.priority < node.right.priority)
                {
                    *ppnode = rotateR(node);
                    ppnode = &(*ppnode).right;
                }
                else
                {
                    *ppnode = rotateL(node);
                    ppnode = &(*ppnode).left;
                }
            }
            if (!node.left)
                *ppnode = node.right;
            else
                *ppnode = node.left;
            freeNode(node);
        }
    }

    void removeAll(Node* node)
    {
        if (!node)
            return;
        removeAll(node.left);
        removeAll(node.right);
        freeNode(node);
    }

    int opApplyHelper(const Node* node, scope int delegate(ref const E) nothrow dg)
    {
        if (!node)
            return 0;

        int result = opApplyHelper(node.left, dg);
        if (result)
            return result;
        result = dg(node.element);
        if (result)
            return result;
        return opApplyHelper(node.right, dg);
    }

    version (CoreUnittest)
    bool valid(Node* node)
    {
        if (!node)
            return true;

        if (node.left)
        {
            if (node.left.priority < node.priority)
                return false;
            if (node.left.element > node.element)
                return false;
        }
        if (node.right)
        {
            if (node.right.priority < node.priority)
                return false;
            if (node.right.element < node.element)
                return false;
        }
        return valid(node.left) && valid(node.right);
    }
}

unittest
{
    // randomized unittest for randomized data structure
    import /*cstdlib = */core.stdc.stdlib : rand, srand;
    import /*ctime = */core.stdc.time : time;

    enum OP { add, remove }
    enum initialSize = 1000;
    enum randOps = 1000;

    Treap!uint treap;
    OP[] ops;
    uint[] opdata;

    srand(cast(uint)time(null));
    treap.initialize(rand());

    uint[] data;
initialLoop:
    foreach (i; 0 .. initialSize)
    {
        data ~= rand();
        treap.insert(data[$-1]);
        foreach (e; data[0..$-1])
            if (e == data[$-1])
            {
                data = data[0..$-1];
                continue initialLoop;
            }
    }
    _adSort(*cast(void[]*)&data, typeid(data[0]));
    assert(treap == data);
    assert(treap.valid());

    for (int i = randOps; i > 0; --i)
    {
        ops ~= cast(OP)(rand() < uint.max / 2 ? OP.add: OP.remove);
        opdata ~= rand();
    }

    foreach (op; ops)
    {
        if (op == OP.add)
        {
            treap.insert(opdata[0]);

            size_t i;
            for (i = 0; i < data.length; ++i)
                if (data[i] >= opdata[0])
                    break;

            if (i == data.length || data[i] != opdata[0])
            {    // not a duplicate
                data.length++;
                uint tmp = opdata[0];
                for (; i < data.length; ++i)
                {
                    uint tmp2 = data[i];
                    data[i] = tmp;
                    tmp = tmp2;
                }
            }
        }
        else if (!data.length)    // nothing to remove
        {
            opdata = opdata[1..$];
            continue;
        }
        else
        {
            uint tmp = data[opdata[0]%data.length];
            treap.remove(tmp);
            size_t i;
            for (i = 0; data[i] < tmp; ++i)
            {}
            for (; i < data.length-1; ++i)
                data[i] = data[i+1];
            data.length--;
        }
        assert(treap.valid());
        assert(treap == data);
        opdata = opdata[1..$];
    }

    treap.removeAll();
    data.length = 0;
    assert(treap == data);
}

/// Random number generators for internal usage.
private struct Rand
{
    private ulong rng_state;

@safe @nogc nothrow:
pure:

    auto opCall()
    {
        auto result = front;
        popFront();
        return result;
    }

    @property uint front()
    {
        return cast(uint)(rng_state >> 32);
    }

    void popFront()
    {
        immutable ulong a = 2862933555777941757;
        immutable ulong c = 1;
        rng_state = a * rng_state + c;
    }

    enum empty = false;
}