rbtree.d

/**
This module implements a red-black tree container.

This module is a submodule of $(MREF std, container).

Source: $(PHOBOSSRC std/container/rbtree.d)

Copyright: Red-black tree code copyright (C) 2008- by Steven Schveighoffer. Other code
copyright 2010- Andrei Alexandrescu. All rights reserved by the respective holders.

License: Distributed under the Boost Software License, Version 1.0.
(See accompanying file LICENSE_1_0.txt or copy at $(HTTP
boost.org/LICENSE_1_0.txt)).

Authors: Steven Schveighoffer, $(HTTP erdani.com, Andrei Alexandrescu)
*/
module std.container.rbtree;

///
@safe pure unittest
{
    import std.algorithm.comparison : equal;
    import std.container.rbtree;

    auto rbt = redBlackTree(3, 1, 4, 2, 5);
    assert(rbt.front == 1);
    assert(equal(rbt[], [1, 2, 3, 4, 5]));

    rbt.removeKey(1, 4);
    assert(equal(rbt[], [2, 3, 5]));

    rbt.removeFront();
    assert(equal(rbt[], [3, 5]));

    rbt.insert([1, 2, 4]);
    assert(equal(rbt[], [1, 2, 3, 4, 5]));

    // Query bounds in O(log(n))
    assert(rbt.lowerBound(3).equal([1, 2]));
    assert(rbt.equalRange(3).equal([3]));
    assert(rbt.upperBound(3).equal([4, 5]));

    // A Red Black tree with the highest element at front:
    import std.range : iota;
    auto maxTree = redBlackTree!"a > b"(iota(5));
    assert(equal(maxTree[], [4, 3, 2, 1, 0]));

    // adding duplicates will not add them, but return 0
    auto rbt2 = redBlackTree(1, 3);
    assert(rbt2.insert(1) == 0);
    assert(equal(rbt2[], [1, 3]));
    assert(rbt2.insert(2) == 1);

    // however you can allow duplicates
    auto ubt = redBlackTree!true([0, 1, 0, 1]);
    assert(equal(ubt[], [0, 0, 1, 1]));
}

import std.format;
import std.functional : binaryFun;

public import std.container.util;

version (StdUnittest) debug = RBDoChecks;

//debug = RBDoChecks;

/*
 * Implementation for a Red Black node for use in a Red Black Tree (see below)
 *
 * this implementation assumes we have a marker Node that is the parent of the
 * root Node.  This marker Node is not a valid Node, but marks the end of the
 * collection.  The root is the left child of the marker Node, so it is always
 * last in the collection.  The marker Node is passed in to the setColor
 * function, and the Node which has this Node as its parent is assumed to be
 * the root Node.
 *
 * A Red Black tree should have O(lg(n)) insertion, removal, and search time.
 */
struct RBNode(V)
{
    /*
     * Convenience alias
     */
    alias Node = RBNode*;

    private Node _left;
    private Node _right;
    private Node _parent;

    /**
     * The value held by this node
     */
    V value;

    /**
     * Enumeration determining what color the node is.  Null nodes are assumed
     * to be black.
     */
    enum Color : byte
    {
        Red,
        Black
    }

    /**
     * The color of the node.
     */
    Color color;

    /**
     * Get the left child
     */
    @property inout(RBNode)* left() inout return scope
    {
        return _left;
    }

    /**
     * Get the right child
     */
    @property inout(RBNode)* right() inout return scope
    {
        return _right;
    }

    /**
     * Get the parent
     */
    @property inout(RBNode)* parent() inout return scope
    {
        return _parent;
    }

    /**
     * Set the left child.  Also updates the new child's parent node.  This
     * does not update the previous child.
     *
     * $(RED Warning: If the node this is called on is a local variable, a stack pointer can be
     * escaped through `newNode.parent`. It's marked `@trusted` only for backwards compatibility.)
     *
     * Returns newNode
     */
    @property Node left(return scope Node newNode) @trusted
    {
        _left = newNode;
        if (newNode !is null)
            newNode._parent = &this;
        return newNode;
    }

    /**
     * Set the right child.  Also updates the new child's parent node.  This
     * does not update the previous child.
     *
     * $(RED Warning: If the node this is called on is a local variable, a stack pointer can be
     * escaped through `newNode.parent`. It's marked `@trusted` only for backwards compatibility.)
     *
     * Returns newNode
     */
    @property Node right(return scope Node newNode) @trusted
    {
        _right = newNode;
        if (newNode !is null)
            newNode._parent = &this;
        return newNode;
    }

    // assume _left is not null
    //
    // performs rotate-right operation, where this is T, _right is R, _left is
    // L, _parent is P:
    //
    //      P         P
    //      |   ->    |
    //      T         L
    //     / \       / \
    //    L   R     a   T
    //   / \           / \
    //  a   b         b   R
    //
    /**
     * Rotate right.  This performs the following operations:
     *  - The left child becomes the parent of this node.
     *  - This node becomes the new parent's right child.
     *  - The old right child of the new parent becomes the left child of this
     *    node.
     */
    Node rotateR()
    in
    {
        assert(_left !is null, "left node must not be null");
    }
    do
    {
        // sets _left._parent also
        if (isLeftNode)
            parent.left = _left;
        else
            parent.right = _left;
        Node tmp = _left._right;

        // sets _parent also
        _left.right = &this;

        // sets tmp._parent also
        left = tmp;

        return &this;
    }

    // assumes _right is non null
    //
    // performs rotate-left operation, where this is T, _right is R, _left is
    // L, _parent is P:
    //
    //      P           P
    //      |    ->     |
    //      T           R
    //     / \         / \
    //    L   R       T   b
    //       / \     / \
    //      a   b   L   a
    //
    /**
     * Rotate left.  This performs the following operations:
     *  - The right child becomes the parent of this node.
     *  - This node becomes the new parent's left child.
     *  - The old left child of the new parent becomes the right child of this
     *    node.
     */
    Node rotateL()
    in
    {
        assert(_right !is null, "right node must not be null");
    }
    do
    {
        // sets _right._parent also
        if (isLeftNode)
            parent.left = _right;
        else
            parent.right = _right;
        Node tmp = _right._left;

        // sets _parent also
        _right.left = &this;

        // sets tmp._parent also
        right = tmp;
        return &this;
    }


    /**
     * Returns true if this node is a left child.
     *
     * Note that this should always return a value because the root has a
     * parent which is the marker node.
     */
    @property bool isLeftNode() const
    in
    {
        assert(_parent !is null, "parent must not be null");
    }
    do
    {
        return _parent._left is &this;
    }

    /**
     * Set the color of the node after it is inserted.  This performs an
     * update to the whole tree, possibly rotating nodes to keep the Red-Black
     * properties correct.  This is an O(lg(n)) operation, where n is the
     * number of nodes in the tree.
     *
     * end is the marker node, which is the parent of the topmost valid node.
     */
    void setColor(Node end)
    {
        // test against the marker node
        if (_parent !is end)
        {
            if (_parent.color == Color.Red)
            {
                Node cur = &this;
                while (true)
                {
                    // because root is always black, _parent._parent always exists
                    if (cur._parent.isLeftNode)
                    {
                        // parent is left node, y is 'uncle', could be null
                        Node y = cur._parent._parent._right;
                        if (y !is null && y.color == Color.Red)
                        {
                            cur._parent.color = Color.Black;
                            y.color = Color.Black;
                            cur = cur._parent._parent;
                            if (cur._parent is end)
                            {
                                // root node
                                cur.color = Color.Black;
                                break;
                            }
                            else
                            {
                                // not root node
                                cur.color = Color.Red;
                                if (cur._parent.color == Color.Black)
                                    // satisfied, exit the loop
                                    break;
                            }
                        }
                        else
                        {
                            if (!cur.isLeftNode)
                                cur = cur._parent.rotateL();
                            cur._parent.color = Color.Black;
                            cur = cur._parent._parent.rotateR();
                            cur.color = Color.Red;
                            // tree should be satisfied now
                            break;
                        }
                    }
                    else
                    {
                        // parent is right node, y is 'uncle'
                        Node y = cur._parent._parent._left;
                        if (y !is null && y.color == Color.Red)
                        {
                            cur._parent.color = Color.Black;
                            y.color = Color.Black;
                            cur = cur._parent._parent;
                            if (cur._parent is end)
                            {
                                // root node
                                cur.color = Color.Black;
                                break;
                            }
                            else
                            {
                                // not root node
                                cur.color = Color.Red;
                                if (cur._parent.color == Color.Black)
                                    // satisfied, exit the loop
                                    break;
                            }
                        }
                        else
                        {
                            if (cur.isLeftNode)
                                cur = cur._parent.rotateR();
                            cur._parent.color = Color.Black;
                            cur = cur._parent._parent.rotateL();
                            cur.color = Color.Red;
                            // tree should be satisfied now
                            break;
                        }
                    }
                }

            }
        }
        else
        {
            //
            // this is the root node, color it black
            //
            color = Color.Black;
        }
    }

    /**
     * Remove this node from the tree.  The 'end' node is used as the marker
     * which is root's parent.  Note that this cannot be null!
     *
     * Returns the next highest valued node in the tree after this one, or end
     * if this was the highest-valued node.
     */
    Node remove(Node end) return
    {
        //
        // remove this node from the tree, fixing the color if necessary.
        //
        Node x;
        Node ret = next;

        // if this node has 2 children
        if (_left !is null && _right !is null)
        {
            //
            // normally, we can just swap this node's and y's value, but
            // because an iterator could be pointing to y and we don't want to
            // disturb it, we swap this node and y's structure instead.  This
            // can also be a benefit if the value of the tree is a large
            // struct, which takes a long time to copy.
            //
            Node yp, yl, yr;
            Node y = ret; // y = next
            yp = y._parent;
            yl = y._left;
            yr = y._right;
            auto yc = y.color;
            auto isyleft = y.isLeftNode;

            //
            // replace y's structure with structure of this node.
            //
            if (isLeftNode)
                _parent.left = y;
            else
                _parent.right = y;
            //
            // need special case so y doesn't point back to itself
            //
            y.left = _left;
            if (_right is y)
                y.right = &this;
            else
                y.right = _right;
            y.color = color;

            //
            // replace this node's structure with structure of y.
            //
            left = yl;
            right = yr;
            if (_parent !is y)
            {
                if (isyleft)
                    yp.left = &this;
                else
                    yp.right = &this;
            }
            color = yc;
        }

        // if this has less than 2 children, remove it
        if (_left !is null)
            x = _left;
        else
            x = _right;

        bool deferedUnlink = false;
        if (x is null)
        {
            // pretend this is a null node, defer unlinking the node
            x = &this;
            deferedUnlink = true;
        }
        else if (isLeftNode)
            _parent.left = x;
        else
            _parent.right = x;

        // if the color of this is black, then it needs to be fixed
        if (color == color.Black)
        {
            // need to recolor the tree.
            while (x._parent !is end && x.color == Node.Color.Black)
            {
                if (x.isLeftNode)
                {
                    // left node
                    Node w = x._parent._right;
                    if (w.color == Node.Color.Red)
                    {
                        w.color = Node.Color.Black;
                        x._parent.color = Node.Color.Red;
                        x._parent.rotateL();
                        w = x._parent._right;
                    }
                    Node wl = w.left;
                    Node wr = w.right;
                    if ((wl is null || wl.color == Node.Color.Black) &&
                            (wr is null || wr.color == Node.Color.Black))
                    {
                        w.color = Node.Color.Red;
                        x = x._parent;
                    }
                    else
                    {
                        if (wr is null || wr.color == Node.Color.Black)
                        {
                            // wl cannot be null here
                            wl.color = Node.Color.Black;
                            w.color = Node.Color.Red;
                            w.rotateR();
                            w = x._parent._right;
                        }

                        w.color = x._parent.color;
                        x._parent.color = Node.Color.Black;
                        w._right.color = Node.Color.Black;
                        x._parent.rotateL();
                        x = end.left; // x = root
                    }
                }
                else
                {
                    // right node
                    Node w = x._parent._left;
                    if (w.color == Node.Color.Red)
                    {
                        w.color = Node.Color.Black;
                        x._parent.color = Node.Color.Red;
                        x._parent.rotateR();
                        w = x._parent._left;
                    }
                    Node wl = w.left;
                    Node wr = w.right;
                    if ((wl is null || wl.color == Node.Color.Black) &&
                            (wr is null || wr.color == Node.Color.Black))
                    {
                        w.color = Node.Color.Red;
                        x = x._parent;
                    }
                    else
                    {
                        if (wl is null || wl.color == Node.Color.Black)
                        {
                            // wr cannot be null here
                            wr.color = Node.Color.Black;
                            w.color = Node.Color.Red;
                            w.rotateL();
                            w = x._parent._left;
                        }

                        w.color = x._parent.color;
                        x._parent.color = Node.Color.Black;
                        w._left.color = Node.Color.Black;
                        x._parent.rotateR();
                        x = end.left; // x = root
                    }
                }
            }
            x.color = Node.Color.Black;
        }

        if (deferedUnlink)
        {
            //
            // unlink this node from the tree
            //
            if (isLeftNode)
                _parent.left = null;
            else
                _parent.right = null;
        }

        // clean references to help GC
        // https://issues.dlang.org/show_bug.cgi?id=12915
        _left = _right = _parent = null;

        return ret;
    }

    /**
     * Return the leftmost descendant of this node.
     */
    @property inout(RBNode)* leftmost() inout return
    {
        inout(RBNode)* result = &this;
        while (result._left !is null)
            result = result._left;
        return result;
    }

    /**
     * Return the rightmost descendant of this node
     */
    @property inout(RBNode)* rightmost() inout return
    {
        inout(RBNode)* result = &this;
        while (result._right !is null)
            result = result._right;
        return result;
    }

    /**
     * Returns the next valued node in the tree.
     *
     * You should never call this on the marker node, as it is assumed that
     * there is a valid next node.
     */
    @property inout(RBNode)* next() inout return
    {
        inout(RBNode)* n = &this;
        if (n.right is null)
        {
            while (!n.isLeftNode)
                n = n._parent;
            return n._parent;
        }
        else
            return n.right.leftmost;
    }

    /**
     * Returns the previous valued node in the tree.
     *
     * You should never call this on the leftmost node of the tree as it is
     * assumed that there is a valid previous node.
     */
    @property inout(RBNode)* prev() inout return
    {
        inout(RBNode)* n = &this;
        if (n.left is null)
        {
            while (n.isLeftNode)
                n = n._parent;
            return n._parent;
        }
        else
            return n.left.rightmost;
    }

    Node dup(scope Node delegate(V v) alloc)
    {
        //
        // duplicate this and all child nodes
        //
        // The recursion should be lg(n), so we shouldn't have to worry about
        // stack size.
        //
        Node copy = alloc(value);
        copy.color = color;
        if (_left !is null)
            copy.left = _left.dup(alloc);
        if (_right !is null)
            copy.right = _right.dup(alloc);
        return copy;
    }

    Node dup()
    {
        Node copy = new RBNode!V(null, null, null, value);
        copy.color = color;
        if (_left !is null)
            copy.left = _left.dup();
        if (_right !is null)
            copy.right = _right.dup();
        return copy;
    }
}

//constness checks
@safe pure unittest
{
    const RBNode!int n;
    static assert(is(typeof(n.leftmost)));
    static assert(is(typeof(n.rightmost)));
    static assert(is(typeof(n.next)));
    static assert(is(typeof(n.prev)));
}

private struct RBRange(N)
{
    alias Node = N;
    alias Elem = typeof(Node.value);

    private Node _begin;
    private Node _end;

    private this(Node b, Node e)
    {
        _begin = b;
        _end = e;
    }

    /**
     * Returns `true` if the range is _empty
     */
    @property bool empty() const
    {
        return _begin is _end;
    }

    /**
     * Returns the first element in the range
     */
    @property Elem front()
    {
        return _begin.value;
    }

    /**
     * Returns the last element in the range
     */
    @property Elem back()
    {
        return _end.prev.value;
    }

    /**
     * pop the front element from the range
     *
     * Complexity: amortized $(BIGOH 1)
     */
    void popFront()
    {
        _begin = _begin.next;
    }

    /**
     * pop the back element from the range
     *
     * Complexity: amortized $(BIGOH 1)
     */
    void popBack()
    {
        _end = _end.prev;
    }

    /**
     * Trivial _save implementation, needed for `isForwardRange`.
     */
    @property RBRange save()
    {
        return this;
    }
}

/**
 * Implementation of a $(LINK2 https://en.wikipedia.org/wiki/Red%E2%80%93black_tree,
 * red-black tree) container.
 *
 * All inserts, removes, searches, and any function in general has complexity
 * of $(BIGOH lg(n)).
 *
 * To use a different comparison than $(D "a < b"), pass a different operator string
 * that can be used by $(REF binaryFun, std,functional), or pass in a
 * function, delegate, functor, or any type where $(D less(a, b)) results in a `bool`
 * value.
 *
 * Note that less should produce a strict ordering.  That is, for two unequal
 * elements `a` and `b`, $(D less(a, b) == !less(b, a)). $(D less(a, a)) should
 * always equal `false`.
 *
 * If `allowDuplicates` is set to `true`, then inserting the same element more than
 * once continues to add more elements.  If it is `false`, duplicate elements are
 * ignored on insertion.  If duplicates are allowed, then new elements are
 * inserted after all existing duplicate elements.
 */
final class RedBlackTree(T, alias less = "a < b", bool allowDuplicates = false)
if (is(typeof(binaryFun!less(T.init, T.init))))
{
    import std.meta : allSatisfy;
    import std.range : Take;
    import std.range.primitives : isInputRange, walkLength;
    import std.traits : isIntegral, isDynamicArray, isImplicitlyConvertible;

    alias _less = binaryFun!less;

    version (StdUnittest)
    {
        static if (is(typeof(less) == string))
        {
            private enum doUnittest = is(byte : T) && isIntegral!T && (less == "a < b" || less == "a > b");
        }
        else
            enum doUnittest = false;

        // note, this must be final so it does not affect the vtable layout
        bool arrayEqual(T[] arr)
        {
            if (walkLength(this[]) == arr.length)
            {
                foreach (v; arr)
                {
                    if (!(v in this))
                        return false;
                }
                return true;
            }
            return false;
        }
    }
    else
    {
        private enum doUnittest = false;
    }

    /**
      * Element type for the tree
      */
    alias Elem = T;

    // used for convenience
    private alias RBNode = .RBNode!Elem;
    private alias Node = RBNode.Node;

    private Node   _end;
    private Node   _begin;
    private size_t _length;

    private void _setup()
    {
        //Make sure that _setup isn't run more than once.
        assert(!_end, "Setup must only be run once");
        _begin = _end = allocate();
    }

    static private Node allocate()
    {
        return new RBNode;
    }

    static private Node allocate(Elem v)
    {
        return new RBNode(null, null, null, v);
    }

    /**
     * The range types for `RedBlackTree`
     */
    alias Range = RBRange!(RBNode*);
    alias ConstRange = RBRange!(const(RBNode)*); /// Ditto
    alias ImmutableRange = RBRange!(immutable(RBNode)*); /// Ditto

    static if (doUnittest) @safe pure unittest
    {
        import std.algorithm.comparison : equal;
        import std.range.primitives;
        auto ts = new RedBlackTree(1, 2, 3, 4, 5);
        assert(ts.length == 5);
        auto r = ts[];

        static if (less == "a < b")
            auto vals = [1, 2, 3, 4, 5];
        else
            auto vals = [5, 4, 3, 2, 1];
        assert(equal(r, vals));

        assert(r.front == vals.front);
        assert(r.back != r.front);
        auto oldfront = r.front;
        auto oldback = r.back;
        r.popFront();
        r.popBack();
        assert(r.front != r.back);
        assert(r.front != oldfront);
        assert(r.back != oldback);
        assert(ts.length == 5);
    }

    // find a node based on an element value
    private inout(RBNode)* _find(Elem e) inout
    {
        static if (allowDuplicates)
        {
            inout(RBNode)* cur = _end.left;
            inout(RBNode)* result = null;
            while (cur)
            {
                if (_less(cur.value, e))
                    cur = cur.right;
                else if (_less(e, cur.value))
                    cur = cur.left;
                else
                {
                    // want to find the left-most element
                    result = cur;
                    cur = cur.left;
                }
            }
            return result;
        }
        else
        {
            inout(RBNode)* cur = _end.left;
            while (cur)
            {
                if (_less(cur.value, e))
                    cur = cur.right;
                else if (_less(e, cur.value))
                    cur = cur.left;
                else
                    return cur;
            }
            return null;
        }
    }

    /* add an element to the tree, returns the node added, or the existing node
     * if it has already been added and allowDuplicates is false
     * Returns:
     *   true if node was added
     */
    private bool _add(return scope Elem n)
    {
        Node result;
        static if (!allowDuplicates)
            bool added = true;

        if (!_end.left)
        {
            result = allocate(n);
            (() @trusted { _end.left = _begin = result; }) ();
        }
        else
        {
            Node newParent = _end.left;
            Node nxt;
            while (true)
            {
                if (_less(n, newParent.value))
                {
                    nxt = newParent.left;
                    if (nxt is null)
                    {
                        //
                        // add to right of new parent
                        //
                        result = allocate(n);
                        (() @trusted { newParent.left = result; }) ();
                        break;
                    }
                }
                else
                {
                    static if (!allowDuplicates)
                    {
                        if (!_less(newParent.value, n))
                        {
                            result = newParent;
                            added = false;
                            break;
                        }
                    }
                    nxt = newParent.right;
                    if (nxt is null)
                    {
                        //
                        // add to right of new parent
                        //
                        result = allocate(n);
                        (() @trusted { newParent.right = result; }) ();
                        break;
                    }
                }
                newParent = nxt;
            }
            if (_begin.left)
                _begin = _begin.left;
        }
        static if (allowDuplicates)
        {
            result.setColor(_end);
            debug(RBDoChecks)
                check();
            ++_length;
            return true;
        }
        else
        {
            if (added)
            {
                ++_length;
                result.setColor(_end);
            }
            debug(RBDoChecks)
                check();
            return added;
        }
    }


    /**
     * Check if any elements exist in the container.  Returns `false` if at least
     * one element exists.
     */
    @property bool empty() const // pure, nothrow, @safe, @nogc: are inferred
    {
        return _end.left is null;
    }

    /++
        Returns the number of elements in the container.

        Complexity: $(BIGOH 1).
    +/
    @property size_t length() const
    {
        return _length;
    }

    /**
     * Duplicate this container.  The resulting container contains a shallow
     * copy of the elements.
     *
     * Complexity: $(BIGOH n)
     */
    @property RedBlackTree dup()
    {
        return new RedBlackTree(_end.dup(), _length);
    }

    static if (doUnittest) @safe pure unittest
    {
        import std.algorithm.comparison : equal;
        auto ts = new RedBlackTree(1, 2, 3, 4, 5);
        assert(ts.length == 5);
        auto ts2 = ts.dup;
        assert(ts2.length == 5);
        assert(equal(ts[], ts2[]));
        ts2.insert(cast(Elem) 6);
        assert(!equal(ts[], ts2[]));
        assert(ts.length == 5 && ts2.length == 6);
    }

    /**
     * Fetch a range that spans all the elements in the container.
     *
     * Complexity: $(BIGOH 1)
     */
    Range opSlice()
    {
        return Range(_begin, _end);
    }

    /// Ditto
    ConstRange opSlice() const
    {
        return ConstRange(_begin, _end);
    }

    /// Ditto
    ImmutableRange opSlice() immutable
    {
        return ImmutableRange(_begin, _end);
    }

    /**
     * The front element in the container
     *
     * Complexity: $(BIGOH 1)
     */
    inout(Elem) front() inout
    {
        return _begin.value;
    }

    /**
     * The last element in the container
     *
     * Complexity: $(BIGOH log(n))
     */
    inout(Elem) back() inout
    {
        return _end.prev.value;
    }

    /++
        `in` operator. Check to see if the given element exists in the
        container.

       Complexity: $(BIGOH log(n))
     +/
    bool opBinaryRight(string op)(Elem e) const if (op == "in")
    {
        return _find(e) !is null;
    }

    static if (doUnittest) @safe pure unittest
    {
        auto ts = new RedBlackTree(1, 2, 3, 4, 5);
        assert(cast(Elem) 3 in ts);
        assert(cast(Elem) 6 !in ts);
    }

    /**
     * Compares two trees for equality.
     *
     * Complexity: $(BIGOH n)
     */
    override bool opEquals(Object rhs)
    {
        import std.algorithm.comparison : equal;

        RedBlackTree that = cast(RedBlackTree) rhs;
        if (that is null) return false;

        // If there aren't the same number of nodes, we can't be equal.
        if (this._length != that._length) return false;

        auto thisRange = this[];
        auto thatRange = that[];
        return equal!((Elem a, Elem b) => !_less(a,b) && !_less(b,a))
                     (thisRange, thatRange);
    }

    static if (doUnittest) @system unittest
    {
        auto t1 = new RedBlackTree(1,2,3,4);
        auto t2 = new RedBlackTree(1,2,3,4);
        auto t3 = new RedBlackTree(1,2,3,5);
        auto t4 = new RedBlackTree(1,2,3,4,5);
        auto o = new Object();

        assert(t1 == t1);
        assert(t1 == t2);
        assert(t1 != t3);
        assert(t1 != t4);
        assert(t1 != o);  // pathological case, must not crash
    }

    /**
     * Generates a hash for the tree. Note that with a custom comparison function
     * it may not hold that if two rbtrees are equal, the hashes of the trees
     * will be equal.
     */
    override size_t toHash() nothrow @safe
    {
        size_t hash = cast(size_t) 0x6b63_616c_4264_6552UL;
        foreach (ref e; this[])
            // As in boost::hash_combine
            // https://www.boost.org/doc/libs/1_55_0/doc/html/hash/reference.html#boost.hash_combine
            hash += .hashOf(e) + 0x9e3779b9 + (hash << 6) + (hash >>> 2);
        return hash;
    }

    static if (doUnittest) @system unittest
    {
        auto t1 = new RedBlackTree(1,2,3,4);
        auto t2 = new RedBlackTree(1,2,3,4);
        auto t3 = new RedBlackTree(1,2,3,5);
        auto t4 = new RedBlackTree(1,2,3,4,5);

        assert(t1.toHash() == t2.toHash);

        assert(t1.toHash() != t3.toHash);
        assert(t2.toHash() != t3.toHash);

        assert(t3.toHash() != t4.toHash);
        assert(t1.toHash() != t4.toHash);

        // empty tree
        auto t5 = new RedBlackTree();
        auto t6 = new RedBlackTree();

        assert(t5.toHash() == t6.toHash());

        auto t7 = new RedBlackTree!string("red", "black");
        auto t8 = new RedBlackTree!string("white", "black");
        auto t9 = new RedBlackTree!string("red", "black");

        assert(t7.toHash() == t9.toHash());
        assert(t7.toHash() != t8.toHash());

        static struct MyInt
        {
            int x;

          @safe:

            this(int init_x)
            {
                x = init_x;
            }

            size_t toHash() const nothrow
            {
                return typeid(x).getHash(&x) ^ 0xF0F0_F0F0;
            }

            int opCmp(const MyInt that) const
            {
                return (x > that.x) - (x < that.x);
            }

            bool opEquals(const MyInt that) const
            {
                return (this.x == that.x);
            }
        }

        auto rbt1 = new RedBlackTree!MyInt(MyInt(1), MyInt(2), MyInt(3), MyInt(4));
        auto rbt2 = new RedBlackTree!MyInt(MyInt(1), MyInt(2), MyInt(3), MyInt(4));

        assert(rbt1.toHash() == rbt2.toHash());
        assert(rbt1.toHash() != t1.toHash());

        auto rbt3 = new RedBlackTree!MyInt(MyInt(4), MyInt(2), MyInt(3), MyInt(4));

        assert(rbt1.toHash() != rbt3.toHash());

        class MyInt2
        {
            int x;

            this(int init_x)
            {
                x = init_x;
            }

            override size_t toHash() const @safe nothrow
            {
                return typeid(x).getHash(&x) ^ 0xF0F0_F0F0;
            }

            int opCmp(const MyInt2 that) const
            {
                return (x > that.x) - (x < that.x);
            }

            bool opEquals(const MyInt2 that) const
            {
                return (this.x == that.x);
            }
        }

        static bool nullSafeLess(scope const MyInt2 a, scope const MyInt2 b)
        {
            return a is null ? b !is null : (b !is null && a < b);
        }

        auto rbt4 = new RedBlackTree!MyInt2(new MyInt2(1), new MyInt2(9), new MyInt2(3), new MyInt2(42));
        auto rbt5 = new RedBlackTree!MyInt2(new MyInt2(1), new MyInt2(9), new MyInt2(3), new MyInt2(42));
        auto rbt6 = new RedBlackTree!(MyInt2, nullSafeLess)(new MyInt2(9), new MyInt2(3), new MyInt2(42));
        auto rbt7 = new RedBlackTree!(MyInt2, nullSafeLess)(null);

        assert(rbt6.toHash() != rbt5.toHash());
        assert(rbt6.toHash() != rbt4.toHash());
        assert(rbt6.toHash() != rbt7.toHash());
        assert(rbt4.toHash() == rbt5.toHash());

        auto rbt8 = new RedBlackTree!(MyInt2, nullSafeLess)(null, new MyInt2(9), null, new MyInt2(42));
        auto rbt9 = new RedBlackTree!(MyInt2, nullSafeLess)(null, new MyInt2(9), null, new MyInt2(42));
        auto rbt10 = new RedBlackTree!(MyInt2, nullSafeLess)(new MyInt2(94), null, new MyInt2(147));

        assert(rbt8.toHash() == rbt9.toHash());
        assert(rbt8.toHash() != rbt10.toHash());
    }

    /**
     * Removes all elements from the container.
     *
     * Complexity: $(BIGOH 1)
     */
    void clear()
    {
        _end.left = null;
        _begin = _end;
        _length = 0;
    }

    static if (doUnittest) @safe pure unittest
    {
        auto ts = new RedBlackTree(1,2,3,4,5);
        assert(ts.length == 5);
        ts.clear();
        assert(ts.empty && ts.length == 0);
    }

    /**
     * Insert a single element in the container.  Note that this does not
     * invalidate any ranges currently iterating the container.
     *
     * Returns: The number of elements inserted.
     *
     * Complexity: $(BIGOH log(n))
     */
    size_t stableInsert(Stuff)(Stuff stuff) if (isImplicitlyConvertible!(Stuff, Elem))
    {
        static if (allowDuplicates)
        {
            _add(stuff);
            return 1;
        }
        else
        {
            return _add(stuff);
        }
    }

    /**
     * Insert a range of elements in the container.  Note that this does not
     * invalidate any ranges currently iterating the container.
     *
     * Returns: The number of elements inserted.
     *
     * Complexity: $(BIGOH m * log(n))
     */
    size_t stableInsert(Stuff)(scope Stuff stuff)
        if (isInputRange!Stuff &&
            isImplicitlyConvertible!(ElementType!Stuff, Elem))
    {
        size_t result = 0;
        static if (allowDuplicates)
        {
            foreach (e; stuff)
            {
                ++result;
                _add(e);
            }
        }
        else
        {
            foreach (e; stuff)
            {
                result += _add(e);
            }
        }
        return result;
    }

    /// ditto
    alias insert = stableInsert;

    static if (doUnittest) @safe pure unittest
    {
        auto ts = new RedBlackTree(2,1,3,4,5,2,5);
        static if (allowDuplicates)
        {
            assert(ts.length == 7);
            assert(ts.stableInsert(cast(Elem[])[7, 8, 6, 9, 10, 8]) == 6);
            assert(ts.length == 13);
            assert(ts.stableInsert(cast(Elem) 11) == 1 && ts.length == 14);
            assert(ts.stableInsert(cast(Elem) 7) == 1 && ts.length == 15);

            static if (less == "a < b")
                assert(ts.arrayEqual([1,2,2,3,4,5,5,6,7,7,8,8,9,10,11]));
            else
                assert(ts.arrayEqual([11,10,9,8,8,7,7,6,5,5,4,3,2,2,1]));
        }
        else
        {
            assert(ts.length == 5);
            Elem[] elems = [7, 8, 6, 9, 10, 8];
            assert(ts.stableInsert(elems) == 5);
            assert(ts.length == 10);
            assert(ts.stableInsert(cast(Elem) 11) == 1 && ts.length == 11);
            assert(ts.stableInsert(cast(Elem) 7) == 0 && ts.length == 11);

            static if (less == "a < b")
                assert(ts.arrayEqual([1,2,3,4,5,6,7,8,9,10,11]));
            else
                assert(ts.arrayEqual([11,10,9,8,7,6,5,4,3,2,1]));
        }
    }

    /**
     * Remove an element from the container and return its value.
     *
     * Complexity: $(BIGOH log(n))
     */
    Elem removeAny()
    {
        scope(success)
            --_length;
        auto n = _begin;
        auto result = n.value;
        _begin = n.remove(_end);
        debug(RBDoChecks)
            check();
        return result;
    }

    static if (doUnittest) @safe pure unittest
    {
        auto ts = new RedBlackTree(1,2,3,4,5);
        assert(ts.length == 5);
        auto x = ts.removeAny();
        assert(ts.length == 4);
        Elem[] arr;
        foreach (Elem i; 1 .. 6)
            if (i != x) arr ~= i;
        assert(ts.arrayEqual(arr));
    }

    /**
     * Remove the front element from the container.
     *
     * Complexity: $(BIGOH log(n))
     */
    void removeFront()
    {
        scope(success)
            --_length;
        _begin = _begin.remove(_end);
        debug(RBDoChecks)
            check();
    }

    /**
     * Remove the back element from the container.
     *
     * Complexity: $(BIGOH log(n))
     */
    void removeBack()
    {
        scope(success)
            --_length;
        auto lastnode = _end.prev;
        if (lastnode is _begin)
            _begin = _begin.remove(_end);
        else
            lastnode.remove(_end);
        debug(RBDoChecks)
            check();
    }

    static if (doUnittest) @safe pure unittest
    {
        auto ts = new RedBlackTree(1,2,3,4,5);
        assert(ts.length == 5);
        ts.removeBack();
        assert(ts.length == 4);

        static if (less == "a < b")
            assert(ts.arrayEqual([1,2,3,4]));
        else
            assert(ts.arrayEqual([2,3,4,5]));

        ts.removeFront();
        assert(ts.arrayEqual([2,3,4]) && ts.length == 3);
    }

    /++
        Removes the given range from the container.

        Returns: A range containing all of the elements that were after the
                 given range.

        Complexity: $(BIGOH m * log(n)) (where m is the number of elements in
                    the range)
     +/
    Range remove(Range r)
    {
        auto b = r._begin;
        auto e = r._end;
        if (_begin is b)
            _begin = e;
        while (b !is e)
        {
            b = b.remove(_end);
            --_length;
        }
        debug(RBDoChecks)
            check();
        return Range(e, _end);
    }

    static if (doUnittest) @safe pure unittest
    {
        import std.algorithm.comparison : equal;
        auto ts = new RedBlackTree(1,2,3,4,5);
        assert(ts.length == 5);
        auto r = ts[];
        r.popFront();
        r.popBack();
        assert(ts.length == 5);
        auto r2 = ts.remove(r);
        assert(ts.length == 2);
        assert(ts.arrayEqual([1,5]));

        static if (less == "a < b")
            assert(equal(r2, [5]));
        else
            assert(equal(r2, [1]));
    }

    /++
        Removes the given `Take!Range` from the container

        Returns: A range containing all of the elements that were after the
                 given range.

        Complexity: $(BIGOH m * log(n)) (where m is the number of elements in
                    the range)
     +/
    Range remove(Take!Range r)
    {
        immutable isBegin = (r.source._begin is _begin);
        auto b = r.source._begin;

        while (!r.empty)
        {
            r.popFront();
            b = b.remove(_end);
            --_length;
        }

        if (isBegin)
            _begin = b;

        return Range(b, _end);
    }

    static if (doUnittest) @safe pure unittest
    {
        import std.algorithm.comparison : equal;
        import std.range : take;
        auto ts = new RedBlackTree(1,2,3,4,5);
        auto r = ts[];
        r.popFront();
        assert(ts.length == 5);
        auto r2 = ts.remove(take(r, 0));

        static if (less == "a < b")
        {
            assert(equal(r2, [2,3,4,5]));
            auto r3 = ts.remove(take(r, 2));
            assert(ts.arrayEqual([1,4,5]) && ts.length == 3);
            assert(equal(r3, [4,5]));
        }
        else
        {
            assert(equal(r2, [4,3,2,1]));
            auto r3 = ts.remove(take(r, 2));
            assert(ts.arrayEqual([5,2,1]) && ts.length == 3);
            assert(equal(r3, [2,1]));
        }
    }

    /++
       Removes elements from the container that are equal to the given values
       according to the less comparator. One element is removed for each value
       given which is in the container. If `allowDuplicates` is true,
       duplicates are removed only if duplicate values are given.

       Returns: The number of elements removed.

       Complexity: $(BIGOH m log(n)) (where m is the number of elements to remove)

       Example:
--------------------
auto rbt = redBlackTree!true(0, 1, 1, 1, 4, 5, 7);
rbt.removeKey(1, 4, 7);
assert(equal(rbt[], [0, 1, 1, 5]));
rbt.removeKey(1, 1, 0);
assert(equal(rbt[], [5]));
--------------------
      +/
    size_t removeKey(U...)(U elems)
        if (allSatisfy!(isImplicitlyConvertibleToElem, U))
    {
        Elem[U.length] toRemove = [elems];
        return removeKey(toRemove[]);
    }

    /++ Ditto +/
    size_t removeKey(U)(scope U[] elems)
        if (isImplicitlyConvertible!(U, Elem))
    {
        immutable lenBefore = length;

        foreach (e; elems)
        {
            auto beg = _firstGreaterEqual(e);
            if (beg is _end || _less(e, beg.value))
                // no values are equal
                continue;
            immutable isBegin = (beg is _begin);
            beg = beg.remove(_end);
            if (isBegin)
                _begin = beg;
            --_length;
        }

        return lenBefore - length;
    }

    /++ Ditto +/
    size_t removeKey(Stuff)(Stuff stuff)
        if (isInputRange!Stuff &&
           isImplicitlyConvertible!(ElementType!Stuff, Elem) &&
           !isDynamicArray!Stuff)
    {
        import std.array : array;
        //We use array in case stuff is a Range from this RedBlackTree - either
        //directly or indirectly.
        return removeKey(array(stuff));
    }

    //Helper for removeKey.
    private template isImplicitlyConvertibleToElem(U)
    {
        enum isImplicitlyConvertibleToElem = isImplicitlyConvertible!(U, Elem);
    }

    static if (doUnittest) @safe pure unittest
    {
        import std.algorithm.comparison : equal;
        import std.range : take;
        auto rbt = new RedBlackTree(5, 4, 3, 7, 2, 1, 7, 6, 2, 19, 45);

        //The cast(Elem) is because these tests are instantiated with a variety
        //of numeric types, and the literals are all int, which is not always
        //implicitly convertible to Elem (e.g. short).
        static if (allowDuplicates)
        {
            assert(rbt.length == 11);
            assert(rbt.removeKey(cast(Elem) 4) == 1 && rbt.length == 10);
            assert(rbt.arrayEqual([1,2,2,3,5,6,7,7,19,45]) && rbt.length == 10);

            assert(rbt.removeKey(cast(Elem) 6, cast(Elem) 2, cast(Elem) 1) == 3);
            assert(rbt.arrayEqual([2,3,5,7,7,19,45]) && rbt.length == 7);

            assert(rbt.removeKey(cast(Elem)(42)) == 0 && rbt.length == 7);
            assert(rbt.removeKey(take(rbt[], 3)) == 3 && rbt.length == 4);

            static if (less == "a < b")
                assert(equal(rbt[], [7,7,19,45]));
            else
                assert(equal(rbt[], [7,5,3,2]));
        }
        else
        {
            assert(rbt.length == 9);
            assert(rbt.removeKey(cast(Elem) 4) == 1 && rbt.length == 8);
            assert(rbt.arrayEqual([1,2,3,5,6,7,19,45]));

            assert(rbt.removeKey(cast(Elem) 6, cast(Elem) 2, cast(Elem) 1) == 3);
            assert(rbt.arrayEqual([3,5,7,19,45]) && rbt.length == 5);

            assert(rbt.removeKey(cast(Elem)(42)) == 0 && rbt.length == 5);
            assert(rbt.removeKey(take(rbt[], 3)) == 3 && rbt.length == 2);

            static if (less == "a < b")
                assert(equal(rbt[], [19,45]));
            else
                assert(equal(rbt[], [5,3]));
        }
    }

    // find the first node where the value is > e
    private inout(RBNode)* _firstGreater(Elem e) inout
    {
        // can't use _find, because we cannot return null
        auto cur = _end.left;
        inout(RBNode)* result = _end;
        while (cur)
        {
            if (_less(e, cur.value))
            {
                result = cur;
                cur = cur.left;
            }
            else
                cur = cur.right;
        }
        return result;
    }

    // find the first node where the value is >= e
    private inout(RBNode)* _firstGreaterEqual(Elem e) inout
    {
        // can't use _find, because we cannot return null.
        auto cur = _end.left;
        inout(RBNode)* result = _end;
        while (cur)
        {
            if (_less(cur.value, e))
                cur = cur.right;
            else
            {
                result = cur;
                cur = cur.left;
            }

        }
        return result;
    }

    /**
     * Get a range from the container with all elements that are > e according
     * to the less comparator
     *
     * Complexity: $(BIGOH log(n))
     */
    Range upperBound(Elem e)
    {
        return Range(_firstGreater(e), _end);
    }

    /// Ditto
    ConstRange upperBound(Elem e) const
    {
        return ConstRange(_firstGreater(e), _end);
    }

    /// Ditto
    ImmutableRange upperBound(Elem e) immutable
    {
        return ImmutableRange(_firstGreater(e), _end);
    }

    /**
     * Get a range from the container with all elements that are < e according
     * to the less comparator
     *
     * Complexity: $(BIGOH log(n))
     */
    Range lowerBound(Elem e)
    {
        return Range(_begin, _firstGreaterEqual(e));
    }

    /// Ditto
    ConstRange lowerBound(Elem e) const
    {
        return ConstRange(_begin, _firstGreaterEqual(e));
    }

    /// Ditto
    ImmutableRange lowerBound(Elem e) immutable
    {
        return ImmutableRange(_begin, _firstGreaterEqual(e));
    }

    /**
     * Get a range from the container with all elements that are == e according
     * to the less comparator
     *
     * Complexity: $(BIGOH log(n))
     */
    auto equalRange(this This)(Elem e)
    {
        auto beg = _firstGreaterEqual(e);
        alias RangeType = RBRange!(typeof(beg));
        if (beg is _end || _less(e, beg.value))
            // no values are equal
            return RangeType(beg, beg);
        static if (allowDuplicates)
        {
            return RangeType(beg, _firstGreater(e));
        }
        else
        {
            // no sense in doing a full search, no duplicates are allowed,
            // so we just get the next node.
            return RangeType(beg, beg.next);
        }
    }

    static if (doUnittest) @safe pure unittest
    {
        import std.algorithm.comparison : equal;
        auto ts = new RedBlackTree(1, 2, 3, 4, 5);
        auto rl = ts.lowerBound(3);
        auto ru = ts.upperBound(3);
        auto re = ts.equalRange(3);

        static if (less == "a < b")
        {
            assert(equal(rl, [1,2]));
            assert(equal(ru, [4,5]));
        }
        else
        {
            assert(equal(rl, [5,4]));
            assert(equal(ru, [2,1]));
        }

        assert(equal(re, [3]));
    }

    debug(RBDoChecks)
    {
        /*
         * Print the tree.  This prints a sideways view of the tree in ASCII form,
         * with the number of indentations representing the level of the nodes.
         * It does not print values, only the tree structure and color of nodes.
         */
        void printTree(Node n, int indent = 0)
        {
            import std.stdio : write, writeln;
            if (n !is null)
            {
                printTree(n.right, indent + 2);
                for (int i = 0; i < indent; i++)
                    write(".");
                writeln(n.color == n.color.Black ? "B" : "R");
                printTree(n.left, indent + 2);
            }
            else
            {
                for (int i = 0; i < indent; i++)
                    write(".");
                writeln("N");
            }
            if (indent is 0)
                writeln();
        }

        /*
         * Check the tree for validity.  This is called after every add or remove.
         * This should only be enabled to debug the implementation of the RB Tree.
         */
        void check() @trusted
        {
            //
            // check implementation of the tree
            //
            int recurse(Node n, string path)
            {
                import std.stdio : writeln;
                if (n is null)
                    return 1;
                if (n.parent.left !is n && n.parent.right !is n)
                    throw new Exception("Node at path " ~ path ~ " has inconsistent pointers");
                Node next = n.next;
                static if (allowDuplicates)
                {
                    if (next !is _end && _less(next.value, n.value))
                        throw new Exception("ordering invalid at path " ~ path);
                }
                else
                {
                    if (next !is _end && !_less(n.value, next.value))
                        throw new Exception("ordering invalid at path " ~ path);
                }
                if (n.color == n.color.Red)
                {
                    if ((n.left !is null && n.left.color == n.color.Red) ||
                            (n.right !is null && n.right.color == n.color.Red))
                        throw new Exception("Node at path " ~ path ~ " is red with a red child");
                }

                int l = recurse(n.left, path ~ "L");
                int r = recurse(n.right, path ~ "R");
                if (l != r)
                {
                    writeln("bad tree at:");
                    debug printTree(n);
                    throw new Exception(
                        "Node at path " ~ path ~ " has different number of black nodes on left and right paths"
                    );
                }
                return l + (n.color == n.color.Black ? 1 : 0);
            }

            try
            {
                recurse(_end.left, "");
            }
            catch (Exception e)
            {
                debug printTree(_end.left, 0);
                throw e;
            }
        }
    }

    /**
      Formats the RedBlackTree into a sink function. For more info see $(D
      std.format.formatValue). Note that this only is available when the
      element type can be formatted. Otherwise, the default toString from
      Object is used.
     */
    static if (is(typeof((){FormatSpec!(char) fmt; formatValue((const(char)[]) {}, ConstRange.init, fmt);})))
    {
        void toString(scope void delegate(const(char)[]) sink, scope const ref FormatSpec!char fmt) const
        {
            sink("RedBlackTree(");
            sink.formatValue(this[], fmt);
            sink(")");
        }
    }

    /**
     * Constructor. Pass in an array of elements, or individual elements to
     * initialize the tree with.
     */
    this(Elem[] elems...)
    {
        _setup();
        stableInsert(elems);
    }

    /**
     * Constructor. Pass in a range of elements to initialize the tree with.
     */
    this(Stuff)(Stuff stuff) if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, Elem))
    {
        _setup();
        stableInsert(stuff);
    }

    ///
    this()
    {
        _setup();
    }

    private this(Node end, size_t length)
    {
        _end = end;
        _begin = end.leftmost;
        _length = length;
    }
}

//Verify Example for removeKey.
@safe pure unittest
{
    import std.algorithm.comparison : equal;
    auto rbt = redBlackTree!true(0, 1, 1, 1, 4, 5, 7);
    rbt.removeKey(1, 4, 7);
    assert(equal(rbt[], [0, 1, 1, 5]));
    rbt.removeKey(1, 1, 0);
    assert(equal(rbt[], [5]));
}

//Tests for removeKey
@safe pure unittest
{
    import std.algorithm.comparison : equal;
    {
        auto rbt = redBlackTree(["hello", "world", "foo", "bar"]);
        assert(equal(rbt[], ["bar", "foo", "hello", "world"]));
        assert(rbt.removeKey("hello") == 1);
        assert(equal(rbt[], ["bar", "foo", "world"]));
        assert(rbt.removeKey("hello") == 0);
        assert(equal(rbt[], ["bar", "foo", "world"]));
        assert(rbt.removeKey("hello", "foo", "bar") == 2);
        assert(equal(rbt[], ["world"]));
        assert(rbt.removeKey(["", "world", "hello"]) == 1);
        assert(rbt.empty);
    }

    {
        auto rbt = redBlackTree([1, 2, 12, 27, 4, 500]);
        assert(equal(rbt[], [1, 2, 4, 12, 27, 500]));
        assert(rbt.removeKey(1u) == 1);
        assert(equal(rbt[], [2, 4, 12, 27, 500]));
        assert(rbt.removeKey(cast(byte) 1) == 0);
        assert(equal(rbt[], [2, 4, 12, 27, 500]));
        assert(rbt.removeKey(1, 12u, cast(byte) 27) == 2);
        assert(equal(rbt[], [2, 4, 500]));
        assert(rbt.removeKey([cast(short) 0, cast(short) 500, cast(short) 1]) == 1);
        assert(equal(rbt[], [2, 4]));
    }
}

@safe pure unittest
{
    void test(T)()
    {
        auto rt1 = new RedBlackTree!(T, "a < b", false)();
        auto rt2 = new RedBlackTree!(T, "a < b", true)();
        auto rt3 = new RedBlackTree!(T, "a > b", false)();
        auto rt4 = new RedBlackTree!(T, "a > b", true)();
    }

    test!long();
    test!ulong();
    test!int();
    test!uint();
    test!short();
    test!ushort();
    test!byte();
    test!byte();
}

// https://issues.dlang.org/show_bug.cgi?id=19626
@safe pure unittest
{
    enum T { a, b }
    alias t = RedBlackTree!T;
}

import std.range.primitives : isInputRange, ElementType;
import std.traits : isArray, isSomeString;

/++
    Convenience function for creating a `RedBlackTree!E` from a list of
    values.

    Params:
        allowDuplicates =  Whether duplicates should be allowed (optional, default: false)
        less = predicate to sort by (optional)
        elems = elements to insert into the rbtree (variadic arguments)
        range = range elements to insert into the rbtree (alternative to elems)
  +/
auto redBlackTree(E)(E[] elems...)
{
    return new RedBlackTree!E(elems);
}

/++ Ditto +/
auto redBlackTree(bool allowDuplicates, E)(E[] elems...)
{
    return new RedBlackTree!(E, "a < b", allowDuplicates)(elems);
}

/++ Ditto +/
auto redBlackTree(alias less, E)(E[] elems...)
if (is(typeof(binaryFun!less(E.init, E.init))))
{
    return new RedBlackTree!(E, less)(elems);
}

/++ Ditto +/
auto redBlackTree(alias less, bool allowDuplicates, E)(E[] elems...)
if (is(typeof(binaryFun!less(E.init, E.init))))
{
    //We shouldn't need to instantiate less here, but for some reason,
    //dmd can't handle it if we don't (even though the template which
    //takes less but not allowDuplicates works just fine).
    return new RedBlackTree!(E, binaryFun!less, allowDuplicates)(elems);
}

/++ Ditto +/
auto redBlackTree(Stuff)(Stuff range)
if (isInputRange!Stuff && !isArray!(Stuff))
{
    return new RedBlackTree!(ElementType!Stuff)(range);
}

/++ Ditto +/
auto redBlackTree(bool allowDuplicates, Stuff)(Stuff range)
if (isInputRange!Stuff && !isArray!(Stuff))
{
    return new RedBlackTree!(ElementType!Stuff, "a < b", allowDuplicates)(range);
}

/++ Ditto +/
auto redBlackTree(alias less, Stuff)(Stuff range)
if ( is(typeof(binaryFun!less((ElementType!Stuff).init, (ElementType!Stuff).init)))
    && isInputRange!Stuff && !isArray!(Stuff))
{
    return new RedBlackTree!(ElementType!Stuff, less)(range);
}

/++ Ditto +/
auto redBlackTree(alias less, bool allowDuplicates, Stuff)(Stuff range)
if ( is(typeof(binaryFun!less((ElementType!Stuff).init, (ElementType!Stuff).init)))
    && isInputRange!Stuff && !isArray!(Stuff))
{
    //We shouldn't need to instantiate less here, but for some reason,
    //dmd can't handle it if we don't (even though the template which
    //takes less but not allowDuplicates works just fine).
    return new RedBlackTree!(ElementType!Stuff, binaryFun!less, allowDuplicates)(range);
}

///
@safe pure unittest
{
    import std.range : iota;

    auto rbt1 = redBlackTree(0, 1, 5, 7);
    auto rbt2 = redBlackTree!string("hello", "world");
    auto rbt3 = redBlackTree!true(0, 1, 5, 7, 5);
    auto rbt4 = redBlackTree!"a > b"(0, 1, 5, 7);
    auto rbt5 = redBlackTree!("a > b", true)(0.1, 1.3, 5.9, 7.2, 5.9);

    // also works with ranges
    auto rbt6 = redBlackTree(iota(3));
    auto rbt7 = redBlackTree!true(iota(3));
    auto rbt8 = redBlackTree!"a > b"(iota(3));
    auto rbt9 = redBlackTree!("a > b", true)(iota(3));
}

//Combinations not in examples.
@safe pure unittest
{
    auto rbt1 = redBlackTree!(true, string)("hello", "hello");
    auto rbt2 = redBlackTree!((a, b){return a < b;}, double)(5.1, 2.3);
    auto rbt3 = redBlackTree!("a > b", true, string)("hello", "world");
}

//Range construction.
@safe pure unittest
{
    import std.algorithm.comparison : equal;
    import std.range : iota;
    auto rbt = new RedBlackTree!(int, "a > b")(iota(5));
    assert(equal(rbt[], [4, 3, 2, 1, 0]));
}


// construction with arrays
@safe pure unittest
{
    import std.algorithm.comparison : equal;

    auto rbt = redBlackTree!"a > b"([0, 1, 2, 3, 4]);
    assert(equal(rbt[], [4, 3, 2, 1, 0]));

    auto rbt2 = redBlackTree!"a > b"(["a", "b"]);
    assert(equal(rbt2[], ["b", "a"]));

    auto rbt3 = redBlackTree!"a > b"([1, 2]);
    assert(equal(rbt3[], [2, 1]));

    auto rbt4 = redBlackTree([0, 1, 7, 5]);
    assert(equal(rbt4[], [0, 1, 5, 7]));

    auto rbt5 = redBlackTree(["hello", "world"]);
    assert(equal(rbt5[], ["hello", "world"]));

    auto rbt6 = redBlackTree!true([0, 1, 5, 7, 5]);
    assert(equal(rbt6[], [0, 1, 5, 5, 7]));

    auto rbt7 = redBlackTree!"a > b"([0, 1, 5, 7]);
    assert(equal(rbt7[], [7, 5, 1, 0]));

    auto rbt8 = redBlackTree!("a > b", true)([0.1, 1.3, 5.9, 7.2, 5.9]);
    assert(equal(rbt8[], [7.2, 5.9, 5.9, 1.3, 0.1]));
}

// convenience wrapper range construction
@safe pure unittest
{
    import std.algorithm.comparison : equal;
    import std.range : chain, iota;

    auto rbt = redBlackTree(iota(3));
    assert(equal(rbt[], [0, 1, 2]));

    auto rbt2 = redBlackTree!"a > b"(iota(2));
    assert(equal(rbt2[], [1, 0]));

    auto rbt3 = redBlackTree(chain([0, 1], [7, 5]));
    assert(equal(rbt3[], [0, 1, 5, 7]));

    auto rbt4 = redBlackTree(chain(["hello"], ["world"]));
    assert(equal(rbt4[], ["hello", "world"]));

    auto rbt5 = redBlackTree!true(chain([0, 1], [5, 7, 5]));
    assert(equal(rbt5[], [0, 1, 5, 5, 7]));

    auto rbt6 = redBlackTree!("a > b", true)(chain([0.1, 1.3], [5.9, 7.2, 5.9]));
    assert(equal(rbt6[], [7.2, 5.9, 5.9, 1.3, 0.1]));
}

@safe pure unittest
{
    import std.array : array;

    auto rt1 = redBlackTree(5, 4, 3, 2, 1);
    assert(rt1.length == 5);
    assert(array(rt1[]) == [1, 2, 3, 4, 5]);

    auto rt2 = redBlackTree!"a > b"(1.1, 2.1);
    assert(rt2.length == 2);
    assert(array(rt2[]) == [2.1, 1.1]);

    auto rt3 = redBlackTree!true(5, 5, 4);
    assert(rt3.length == 3);
    assert(array(rt3[]) == [4, 5, 5]);

    auto rt4 = redBlackTree!string("hello", "hello");
    assert(rt4.length == 1);
    assert(array(rt4[]) == ["hello"]);
}

@system unittest
{
    import std.conv : to;

    auto rt1 = redBlackTree!string();
    assert(rt1.to!string == "RedBlackTree([])");

    auto rt2 = redBlackTree!string("hello");
    assert(rt2.to!string == "RedBlackTree([\"hello\"])");

    auto rt3 = redBlackTree!string("hello", "world", "!");
    assert(rt3.to!string == "RedBlackTree([\"!\", \"hello\", \"world\"])");

    // type deduction can be done automatically
    auto rt4 = redBlackTree(["hello"]);
    assert(rt4.to!string == "RedBlackTree([\"hello\"])");
}

//constness checks
@safe pure unittest
{
    const rt1 = redBlackTree(5,4,3,2,1);
    void allQualifiers() pure nothrow @safe @nogc {
        assert(!rt1.empty);
        assert(rt1.length == 5);
        assert(5 in rt1);
    }
    allQualifiers();

    static assert(is(typeof(rt1.upperBound(3).front) == const(int)));
    import std.algorithm.comparison : equal;
    assert(rt1.upperBound(3).equal([4, 5]));
    assert(rt1.lowerBound(3).equal([1, 2]));
    assert(rt1.equalRange(3).equal([3]));
    assert(rt1[].equal([1, 2, 3, 4, 5]));
}

//immutable checks
@safe pure unittest
{
    immutable rt1 = redBlackTree(5,4,3,2,1);
    static assert(is(typeof(rt1.empty)));
    static assert(is(typeof(rt1.length)));
    static assert(is(typeof(5 in rt1)));

    static assert(is(typeof(rt1.upperBound(3).front) == immutable(int)));
    import std.algorithm.comparison : equal;
    assert(rt1.upperBound(2).equal([3, 4, 5]));
}

// https://issues.dlang.org/show_bug.cgi?id=15941
@safe pure unittest
{
    class C {}
    RedBlackTree!(C, "cast(void*)a < cast(void*) b") tree;
}

// const/immutable elements (https://issues.dlang.org/show_bug.cgi?id=17519)
@safe pure unittest
{
    RedBlackTree!(immutable int) t1;
    RedBlackTree!(const int) t2;

    import std.algorithm.iteration : map;
    static struct S { int* p; }
    auto t3 = new RedBlackTree!(immutable S, (a, b) => *a.p < *b.p);
    t3.insert([1, 2, 3].map!(x => immutable S(new int(x))));
    static assert(!__traits(compiles, *t3.front.p = 4));
    assert(*t3.front.p == 1);
}

// make sure the comparator can be a delegate
@safe pure unittest
{
    import std.algorithm.comparison : equal;

    auto t = new RedBlackTree!(int, delegate(a, b) => a > b);
    t.insert([1, 3, 5, 4, 2]);
    assert(t[].equal([5, 4, 3, 2, 1]));
}