struct Link(N) {
private:
    N* child;

public:
    this(N* n, Color c) {
        child = cast(N*) ((cast(size_t) n) | c);
    }

    auto getAs(Color c) {
        return Link(node(), c);
    }

    N* node() const {
        return cast(N*) ((cast(size_t) child) & ~0x01);
    }

    Color color() const {
        return cast(Color) ((cast(size_t) child) & 0x01);
    }

    bool isRed() const {
        return color() == Color.Red;
    }

    bool isBlack() const {
        return color() == Color.Black;
    }

private:
    // Rotate the tree and return the new root.
    auto rotateLeft() {
        auto right = node().right;
        node().right = right.node().left;
        right.node().left = node();
        return right;
    }

    // Rotate the tree and return the new root.
    auto rotateRight() {
        auto left = node().left;
        node().left = left.node().right;
        left.node().right = node();
        return left;
    }
}

enum Color {
    Black = false,
    Red = true,
}

// Insert a new node in the tree.
auto rb_insert(N)(N* root, N* n) {
    // rbtree's depth is ln(n) which is at most 8 * size_t.sizeof.
    // But a branch can be at most 2* longer than the shortest one.
    Path!N[16 * size_t.sizeof] path; // TODO: make this void initialized.
    auto stackp = &path[0]; // TODO: use .ptr when available.

    // Root is always black.
    stackp.link = Link!N(root, Color.Black);

    while (stackp.node !is null) {
        auto cmp = stackp.cmp = n.opCmp(stackp.node);
        assert(cmp != 0);

        auto link = stackp.link;
        stackp++;
        stackp.link = (cmp < 0)
            ? stackp.link.node().left
            : stackp.link.node().right;
    }

    // Inserted node is always red.
    stackp.link = Link!N(n, Color.Red);

    // Now we found an insertion point, let's fix the tree.
    for (stackp--; stackp !is &path[-1]; stackp--) {
        auto link = stackp.link;
        if (stackp.cmp < 0) {
            auto left = link.node().left = stackp[1].link;
            if (left.isBack()) {
                return;
            }

            auto leftleft = left.node().left;
            if (leftleft.isBlack()) {
                continue;
            }

            /**
             * l = left
             * b = changed to black
             *
             * NB: Because of the handling of the right branch,
             * it is impossible to have 2 red node on the right.
             *
             *      B
             *     /         Rl
             *    Rl   =>   / \
             *   /         Rb  B
             *  R
             */
            left.get().left = leftleft.getAs(Color.Black);
            stackp.link = link.rotateRight();
        } else {
            auto right = link.node().right = stackp[1].link;
            if (right.isBlack()) {
                return;
            }

            auto left = link.node().left;
            if (left.isRed()) {
                /**
                 * r = right
                 * b = changed to black
                 * r = changed to red
                 *
                 * NB: Because left is red, we know link is black.
                 * NB: We can't have 2 red nodes on the right.
                 *
                 *    B             Br
                 *   / \           / \
                 *  R   R    =>   Rb  Rb
                 *     / \           / \
                 *    R   B         R   B
                 */
                link.node().left = left.getAs(Color.Back);
                link.node().right = right.getAs(Color.Back);
                stackp.link = link.getAs(Color.Red);
                continue;
            }

            /**
             *                  R
             * This ensure that  \  is impossible.
             *                    R
             *
             * l = left
             * b = changed to black
             * r = changed to red
             *
             * If we have 2 red node on the right at link level
             * we rebalance to have them on the left and push
             * the problem one level up.
             *
             *                R
             *    R          /
             *   / \   =>   R
             *  B   R      /
             *            B
             *
             * Or we have 2 red on the left, in which case
             * the link must be black.
             *
             *    B             Rb
             *   / \           / \
             *  B   R    =>   Br  B
             *     / \       / \
             *    R   B     B   R
             *
             * And it is all screwed up :( What is wrong here ?
             */
            auto l = link.rotateLeft().getAs(link.color());
            l.node().left = link.getAs(Color.Red);
            stackp.link = l;
        }
    }

    return stackp.link.node();
}