//===----------------------------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

// Not a portable test

// Returns __tree_next(__z)
// template <class _NodePtr>
// void
// __tree_remove(_NodePtr __root, _NodePtr __z)

#include <__tree>
#include <cassert>

struct Node
{
    Node* __left_;
    Node* __right_;
    Node* __parent_;
    bool __is_black_;

    Node* __parent_unsafe() const { return __parent_; }
    void __set_parent(Node* x) { __parent_ = x;}

    Node() : __left_(), __right_(), __parent_(), __is_black_() {}
};

void
test1()
{
    {
        // Left
        // Case 1 -> Case 2 -> x is red turned to black
        Node root;
        Node b;
        Node c;
        Node d;
        Node e;
        Node y;

        root.__left_ = &b;

        b.__parent_ = &root;
        b.__left_ = &y;
        b.__right_ = &d;
        b.__is_black_ = true;

        y.__parent_ = &b;
        y.__left_ = 0;
        y.__right_ = 0;
        y.__is_black_ = true;

        d.__parent_ = &b;
        d.__left_ = &c;
        d.__right_ = &e;
        d.__is_black_ = false;

        c.__parent_ = &d;
        c.__left_ = 0;
        c.__right_ = 0;
        c.__is_black_ = true;

        e.__parent_ = &d;
        e.__left_ = 0;
        e.__right_ = 0;
        e.__is_black_ = true;

        std::__tree_remove(root.__left_, &y);
        assert(std::__tree_invariant(root.__left_));

        assert(root.__parent_ == 0);
        assert(root.__left_ == &d);
        assert(root.__right_ == 0);
        assert(root.__is_black_ == false);

        assert(d.__parent_ == &root);
        assert(d.__left_ == &b);
        assert(d.__right_ == &e);
        assert(d.__is_black_ == true);

        assert(b.__parent_ == &d);
        assert(b.__left_ == 0);
        assert(b.__right_ == &c);
        assert(b.__is_black_ == true);

        assert(c.__parent_ == &b);
        assert(c.__left_ == 0);
        assert(c.__right_ == 0);
        assert(c.__is_black_ == false);

        assert(e.__parent_ == &d);
        assert(e.__left_ == 0);
        assert(e.__right_ == 0);
        assert(e.__is_black_ == true);
    }
    {
        // Right
        // Case 1 -> Case 2 -> x is red turned to black
        Node root;
        Node b;
        Node c;
        Node d;
        Node e;
        Node y;

        root.__left_ = &b;

        b.__parent_ = &root;
        b.__right_ = &y;
        b.__left_ = &d;
        b.__is_black_ = true;

        y.__parent_ = &b;
        y.__right_ = 0;
        y.__left_ = 0;
        y.__is_black_ = true;

        d.__parent_ = &b;
        d.__right_ = &c;
        d.__left_ = &e;
        d.__is_black_ = false;

        c.__parent_ = &d;
        c.__right_ = 0;
        c.__left_ = 0;
        c.__is_black_ = true;

        e.__parent_ = &d;
        e.__right_ = 0;
        e.__left_ = 0;
        e.__is_black_ = true;

        std::__tree_remove(root.__left_, &y);
        assert(std::__tree_invariant(root.__left_));

        assert(root.__parent_ == 0);
        assert(root.__left_ == &d);
        assert(root.__right_ == 0);
        assert(root.__is_black_ == false);

        assert(d.__parent_ == &root);
        assert(d.__right_ == &b);
        assert(d.__left_ == &e);
        assert(d.__is_black_ == true);

        assert(b.__parent_ == &d);
        assert(b.__right_ == 0);
        assert(b.__left_ == &c);
        assert(b.__is_black_ == true);

        assert(c.__parent_ == &b);
        assert(c.__right_ == 0);
        assert(c.__left_ == 0);
        assert(c.__is_black_ == false);

        assert(e.__parent_ == &d);
        assert(e.__right_ == 0);
        assert(e.__left_ == 0);
        assert(e.__is_black_ == true);
    }
    {
        // Left
        // Case 1 -> Case 3 -> Case 4
        Node root;
        Node b;
        Node c;
        Node d;
        Node e;
        Node f;
        Node y;

        root.__left_ = &b;

        b.__parent_ = &root;
        b.__left_ = &y;
        b.__right_ = &d;
        b.__is_black_ = true;

        y.__parent_ = &b;
        y.__left_ = 0;
        y.__right_ = 0;
        y.__is_black_ = true;

        d.__parent_ = &b;
        d.__left_ = &c;
        d.__right_ = &e;
        d.__is_black_ = false;

        c.__parent_ = &d;
        c.__left_ = &f;
        c.__right_ = 0;
        c.__is_black_ = true;

        e.__parent_ = &d;
        e.__left_ = 0;
        e.__right_ = 0;
        e.__is_black_ = true;

        f.__parent_ = &c;
        f.__left_ = 0;
        f.__right_ = 0;
        f.__is_black_ = false;

        std::__tree_remove(root.__left_, &y);
        assert(std::__tree_invariant(root.__left_));

        assert(root.__parent_ == 0);
        assert(root.__left_ == &d);
        assert(root.__right_ == 0);
        assert(root.__is_black_ == false);

        assert(d.__parent_ == &root);
        assert(d.__left_ == &f);
        assert(d.__right_ == &e);
        assert(d.__is_black_ == true);

        assert(f.__parent_ == &d);
        assert(f.__left_ == &b);
        assert(f.__right_ == &c);
        assert(f.__is_black_ == false);

        assert(b.__parent_ == &f);
        assert(b.__left_ == 0);
        assert(b.__right_ == 0);
        assert(b.__is_black_ == true);

        assert(c.__parent_ == &f);
        assert(c.__left_ == 0);
        assert(c.__right_ == 0);
        assert(c.__is_black_ == true);

        assert(e.__parent_ == &d);
        assert(e.__left_ == 0);
        assert(e.__right_ == 0);
        assert(e.__is_black_ == true);
    }
    {
        // Right
        // Case 1 -> Case 3 -> Case 4
        Node root;
        Node b;
        Node c;
        Node d;
        Node e;
        Node f;
        Node y;

        root.__left_ = &b;

        b.__parent_ = &root;
        b.__right_ = &y;
        b.__left_ = &d;
        b.__is_black_ = true;

        y.__parent_ = &b;
        y.__right_ = 0;
        y.__left_ = 0;
        y.__is_black_ = true;

        d.__parent_ = &b;
        d.__right_ = &c;
        d.__left_ = &e;
        d.__is_black_ = false;

        c.__parent_ = &d;
        c.__right_ = &f;
        c.__left_ = 0;
        c.__is_black_ = true;

        e.__parent_ = &d;
        e.__right_ = 0;
        e.__left_ = 0;
        e.__is_black_ = true;

        f.__parent_ = &c;
        f.__right_ = 0;
        f.__left_ = 0;
        f.__is_black_ = false;

        std::__tree_remove(root.__left_, &y);
        assert(std::__tree_invariant(root.__left_));

        assert(root.__parent_ == 0);
        assert(root.__left_ == &d);
        assert(root.__right_ == 0);
        assert(root.__is_black_ == false);

        assert(d.__parent_ == &root);
        assert(d.__right_ == &f);
        assert(d.__left_ == &e);
        assert(d.__is_black_ == true);

        assert(f.__parent_ == &d);
        assert(f.__right_ == &b);
        assert(f.__left_ == &c);
        assert(f.__is_black_ == false);

        assert(b.__parent_ == &f);
        assert(b.__right_ == 0);
        assert(b.__left_ == 0);
        assert(b.__is_black_ == true);

        assert(c.__parent_ == &f);
        assert(c.__right_ == 0);
        assert(c.__left_ == 0);
        assert(c.__is_black_ == true);

        assert(e.__parent_ == &d);
        assert(e.__right_ == 0);
        assert(e.__left_ == 0);
        assert(e.__is_black_ == true);
    }
}

void
test2()
{
    {
        Node root;
        Node a;
        Node b;
        Node c;

        root.__left_ = &b;

        b.__parent_ = &root;
        b.__left_ = &a;
        b.__right_ = &c;
        b.__is_black_ = true;

        a.__parent_ = &b;
        a.__left_ = 0;
        a.__right_ = 0;
        a.__is_black_ = true;

        c.__parent_ = &b;
        c.__left_ = 0;
        c.__right_ = 0;
        c.__is_black_ = true;

        std::__tree_remove(root.__left_, &a);

        assert(std::__tree_invariant(root.__left_));

        assert(root.__parent_ == 0);
        assert(root.__left_ == &b);
        assert(root.__right_ == 0);
        assert(root.__is_black_ == false);

        assert(b.__parent_ == &root);
        assert(b.__left_ == 0);
        assert(b.__right_ == &c);
        assert(b.__is_black_ == true);

        assert(c.__parent_ == &b);
        assert(c.__left_ == 0);
        assert(c.__right_ == 0);
        assert(c.__is_black_ == false);

        std::__tree_remove(root.__left_, &b);

        assert(std::__tree_invariant(root.__left_));

        assert(root.__parent_ == 0);
        assert(root.__left_ == &c);
        assert(root.__right_ == 0);
        assert(root.__is_black_ == false);

        assert(c.__parent_ == &root);
        assert(c.__left_ == 0);
        assert(c.__right_ == 0);
        assert(c.__is_black_ == true);

        std::__tree_remove(root.__left_, &c);

        assert(std::__tree_invariant(root.__left_));

        assert(root.__parent_ == 0);
        assert(root.__left_ == 0);
        assert(root.__right_ == 0);
        assert(root.__is_black_ == false);
    }
    {
        Node root;
        Node a;
        Node b;
        Node c;

        root.__left_ = &b;

        b.__parent_ = &root;
        b.__left_ = &a;
        b.__right_ = &c;
        b.__is_black_ = true;

        a.__parent_ = &b;
        a.__left_ = 0;
        a.__right_ = 0;
        a.__is_black_ = false;

        c.__parent_ = &b;
        c.__left_ = 0;
        c.__right_ = 0;
        c.__is_black_ = false;

        std::__tree_remove(root.__left_, &a);

        assert(std::__tree_invariant(root.__left_));

        assert(root.__parent_ == 0);
        assert(root.__left_ == &b);
        assert(root.__right_ == 0);
        assert(root.__is_black_ == false);

        assert(b.__parent_ == &root);
        assert(b.__left_ == 0);
        assert(b.__right_ == &c);
        assert(b.__is_black_ == true);

        assert(c.__parent_ == &b);
        assert(c.__left_ == 0);
        assert(c.__right_ == 0);
        assert(c.__is_black_ == false);

        std::__tree_remove(root.__left_, &b);

        assert(std::__tree_invariant(root.__left_));

        assert(root.__parent_ == 0);
        assert(root.__left_ == &c);
        assert(root.__right_ == 0);
        assert(root.__is_black_ == false);

        assert(c.__parent_ == &root);
        assert(c.__left_ == 0);
        assert(c.__right_ == 0);
        assert(c.__is_black_ == true);

        std::__tree_remove(root.__left_, &c);

        assert(std::__tree_invariant(root.__left_));

        assert(root.__parent_ == 0);
        assert(root.__left_ == 0);
        assert(root.__right_ == 0);
        assert(root.__is_black_ == false);
    }
    {
        Node root;
        Node a;
        Node b;
        Node c;

        root.__left_ = &b;

        b.__parent_ = &root;
        b.__left_ = &a;
        b.__right_ = &c;
        b.__is_black_ = true;

        a.__parent_ = &b;
        a.__left_ = 0;
        a.__right_ = 0;
        a.__is_black_ = true;

        c.__parent_ = &b;
        c.__left_ = 0;
        c.__right_ = 0;
        c.__is_black_ = true;

        std::__tree_remove(root.__left_, &a);

        assert(std::__tree_invariant(root.__left_));

        assert(root.__parent_ == 0);
        assert(root.__left_ == &b);
        assert(root.__right_ == 0);
        assert(root.__is_black_ == false);

        assert(b.__parent_ == &root);
        assert(b.__left_ == 0);
        assert(b.__right_ == &c);
        assert(b.__is_black_ == true);

        assert(c.__parent_ == &b);
        assert(c.__left_ == 0);
        assert(c.__right_ == 0);
        assert(c.__is_black_ == false);

        std::__tree_remove(root.__left_, &c);

        assert(std::__tree_invariant(root.__left_));

        assert(root.__parent_ == 0);
        assert(root.__left_ == &b);
        assert(root.__right_ == 0);
        assert(root.__is_black_ == false);

        assert(b.__parent_ == &root);
        assert(b.__left_ == 0);
        assert(b.__right_ == 0);
        assert(b.__is_black_ == true);

        std::__tree_remove(root.__left_, &b);

        assert(std::__tree_invariant(root.__left_));

        assert(root.__parent_ == 0);
        assert(root.__left_ == 0);
        assert(root.__right_ == 0);
        assert(root.__is_black_ == false);
    }
    {
        Node root;
        Node a;
        Node b;
        Node c;

        root.__left_ = &b;

        b.__parent_ = &root;
        b.__left_ = &a;
        b.__right_ = &c;
        b.__is_black_ = true;

        a.__parent_ = &b;
        a.__left_ = 0;
        a.__right_ = 0;
        a.__is_black_ = false;

        c.__parent_ = &b;
        c.__left_ = 0;
        c.__right_ = 0;
        c.__is_black_ = false;

        std::__tree_remove(root.__left_, &a);

        assert(std::__tree_invariant(root.__left_));

        assert(root.__parent_ == 0);
        assert(root.__left_ == &b);
        assert(root.__right_ == 0);
        assert(root.__is_black_ == false);

        assert(b.__parent_ == &root);
        assert(b.__left_ == 0);
        assert(b.__right_ == &c);
        assert(b.__is_black_ == true);

        assert(c.__parent_ == &b);
        assert(c.__left_ == 0);
        assert(c.__right_ == 0);
        assert(c.__is_black_ == false);

        std::__tree_remove(root.__left_, &c);

        assert(std::__tree_invariant(root.__left_));

        assert(root.__parent_ == 0);
        assert(root.__left_ == &b);
        assert(root.__right_ == 0);
        assert(root.__is_black_ == false);

        assert(b.__parent_ == &root);
        assert(b.__left_ == 0);
        assert(b.__right_ == 0);
        assert(b.__is_black_ == true);

        std::__tree_remove(root.__left_, &b);

        assert(std::__tree_invariant(root.__left_));

        assert(root.__parent_ == 0);
        assert(root.__left_ == 0);
        assert(root.__right_ == 0);
        assert(root.__is_black_ == false);
    }
    {
        Node root;
        Node a;
        Node b;
        Node c;

        root.__left_ = &b;

        b.__parent_ = &root;
        b.__left_ = &a;
        b.__right_ = &c;
        b.__is_black_ = true;

        a.__parent_ = &b;
        a.__left_ = 0;
        a.__right_ = 0;
        a.__is_black_ = true;

        c.__parent_ = &b;
        c.__left_ = 0;
        c.__right_ = 0;
        c.__is_black_ = true;

        std::__tree_remove(root.__left_, &b);

        assert(std::__tree_invariant(root.__left_));

        assert(root.__parent_ == 0);
        assert(root.__left_ == &c);
        assert(root.__right_ == 0);
        assert(root.__is_black_ == false);

        assert(a.__parent_ == &c);
        assert(a.__left_ == 0);
        assert(a.__right_ == 0);
        assert(a.__is_black_ == false);

        assert(c.__parent_ == &root);
        assert(c.__left_ == &a);
        assert(c.__right_ == 0);
        assert(c.__is_black_ == true);

        std::__tree_remove(root.__left_, &a);

        assert(std::__tree_invariant(root.__left_));

        assert(root.__parent_ == 0);
        assert(root.__left_ == &c);
        assert(root.__right_ == 0);
        assert(root.__is_black_ == false);

        assert(c.__parent_ == &root);
        assert(c.__left_ == 0);
        assert(c.__right_ == 0);
        assert(c.__is_black_ == true);

        std::__tree_remove(root.__left_, &c);

        assert(std::__tree_invariant(root.__left_));

        assert(root.__parent_ == 0);
        assert(root.__left_ == 0);
        assert(root.__right_ == 0);
        assert(root.__is_black_ == false);
    }
    {
        Node root;
        Node a;
        Node b;
        Node c;

        root.__left_ = &b;

        b.__parent_ = &root;
        b.__left_ = &a;
        b.__right_ = &c;
        b.__is_black_ = true;

        a.__parent_ = &b;
        a.__left_ = 0;
        a.__right_ = 0;
        a.__is_black_ = false;

        c.__parent_ = &b;
        c.__left_ = 0;
        c.__right_ = 0;
        c.__is_black_ = false;

        std::__tree_remove(root.__left_, &b);

        assert(std::__tree_invariant(root.__left_));

        assert(root.__parent_ == 0);
        assert(root.__left_ == &c);
        assert(root.__right_ == 0);
        assert(root.__is_black_ == false);

        assert(a.__parent_ == &c);
        assert(a.__left_ == 0);
        assert(a.__right_ == 0);
        assert(a.__is_black_ == false);

        assert(c.__parent_ == &root);
        assert(c.__left_ == &a);
        assert(c.__right_ == 0);
        assert(c.__is_black_ == true);

        std::__tree_remove(root.__left_, &a);

        assert(std::__tree_invariant(root.__left_));

        assert(root.__parent_ == 0);
        assert(root.__left_ == &c);
        assert(root.__right_ == 0);
        assert(root.__is_black_ == false);

        assert(c.__parent_ == &root);
        assert(c.__left_ == 0);
        assert(c.__right_ == 0);
        assert(c.__is_black_ == true);

        std::__tree_remove(root.__left_, &c);

        assert(std::__tree_invariant(root.__left_));

        assert(root.__parent_ == 0);
        assert(root.__left_ == 0);
        assert(root.__right_ == 0);
        assert(root.__is_black_ == false);
    }
    {
        Node root;
        Node a;
        Node b;
        Node c;

        root.__left_ = &b;

        b.__parent_ = &root;
        b.__left_ = &a;
        b.__right_ = &c;
        b.__is_black_ = true;

        a.__parent_ = &b;
        a.__left_ = 0;
        a.__right_ = 0;
        a.__is_black_ = true;

        c.__parent_ = &b;
        c.__left_ = 0;
        c.__right_ = 0;
        c.__is_black_ = true;

        std::__tree_remove(root.__left_, &b);

        assert(std::__tree_invariant(root.__left_));

        assert(root.__parent_ == 0);
        assert(root.__left_ == &c);
        assert(root.__right_ == 0);
        assert(root.__is_black_ == false);

        assert(a.__parent_ == &c);
        assert(a.__left_ == 0);
        assert(a.__right_ == 0);
        assert(a.__is_black_ == false);

        assert(c.__parent_ == &root);
        assert(c.__left_ == &a);
        assert(c.__right_ == 0);
        assert(c.__is_black_ == true);

        std::__tree_remove(root.__left_, &c);

        assert(std::__tree_invariant(root.__left_));

        assert(root.__parent_ == 0);
        assert(root.__left_ == &a);
        assert(root.__right_ == 0);
        assert(root.__is_black_ == false);

        assert(a.__parent_ == &root);
        assert(a.__left_ == 0);
        assert(a.__right_ == 0);
        assert(a.__is_black_ == true);

        std::__tree_remove(root.__left_, &a);

        assert(std::__tree_invariant(root.__left_));

        assert(root.__parent_ == 0);
        assert(root.__left_ == 0);
        assert(root.__right_ == 0);
        assert(root.__is_black_ == false);
    }
    {
        Node root;
        Node a;
        Node b;
        Node c;

        root.__left_ = &b;

        b.__parent_ = &root;
        b.__left_ = &a;
        b.__right_ = &c;
        b.__is_black_ = true;

        a.__parent_ = &b;
        a.__left_ = 0;
        a.__right_ = 0;
        a.__is_black_ = false;

        c.__parent_ = &b;
        c.__left_ = 0;
        c.__right_ = 0;
        c.__is_black_ = false;

        std::__tree_remove(root.__left_, &b);

        assert(std::__tree_invariant(root.__left_));

        assert(root.__parent_ == 0);
        assert(root.__left_ == &c);
        assert(root.__right_ == 0);
        assert(root.__is_black_ == false);

        assert(a.__parent_ == &c);
        assert(a.__left_ == 0);
        assert(a.__right_ == 0);
        assert(a.__is_black_ == false);

        assert(c.__parent_ == &root);
        assert(c.__left_ == &a);
        assert(c.__right_ == 0);
        assert(c.__is_black_ == true);

        std::__tree_remove(root.__left_, &c);

        assert(std::__tree_invariant(root.__left_));

        assert(root.__parent_ == 0);
        assert(root.__left_ == &a);
        assert(root.__right_ == 0);
        assert(root.__is_black_ == false);

        assert(a.__parent_ == &root);
        assert(a.__left_ == 0);
        assert(a.__right_ == 0);
        assert(a.__is_black_ == true);

        std::__tree_remove(root.__left_, &a);

        assert(std::__tree_invariant(root.__left_));

        assert(root.__parent_ == 0);
        assert(root.__left_ == 0);
        assert(root.__right_ == 0);
        assert(root.__is_black_ == false);
    }
    {
        Node root;
        Node a;
        Node b;
        Node c;

        root.__left_ = &b;

        b.__parent_ = &root;
        b.__left_ = &a;
        b.__right_ = &c;
        b.__is_black_ = true;

        a.__parent_ = &b;
        a.__left_ = 0;
        a.__right_ = 0;
        a.__is_black_ = true;

        c.__parent_ = &b;
        c.__left_ = 0;
        c.__right_ = 0;
        c.__is_black_ = true;

        std::__tree_remove(root.__left_, &c);

        assert(std::__tree_invariant(root.__left_));

        assert(root.__parent_ == 0);
        assert(root.__left_ == &b);
        assert(root.__right_ == 0);
        assert(root.__is_black_ == false);

        assert(a.__parent_ == &b);
        assert(a.__left_ == 0);
        assert(a.__right_ == 0);
        assert(a.__is_black_ == false);

        assert(b.__parent_ == &root);
        assert(b.__left_ == &a);
        assert(b.__right_ == 0);
        assert(b.__is_black_ == true);

        std::__tree_remove(root.__left_, &b);

        assert(std::__tree_invariant(root.__left_));

        assert(root.__parent_ == 0);
        assert(root.__left_ == &a);
        assert(root.__right_ == 0);
        assert(root.__is_black_ == false);

        assert(a.__parent_ == &root);
        assert(a.__left_ == 0);
        assert(a.__right_ == 0);
        assert(a.__is_black_ == true);

        std::__tree_remove(root.__left_, &a);

        assert(std::__tree_invariant(root.__left_));

        assert(root.__parent_ == 0);
        assert(root.__left_ == 0);
        assert(root.__right_ == 0);
        assert(root.__is_black_ == false);
    }
    {
        Node root;
        Node a;
        Node b;
        Node c;

        root.__left_ = &b;

        b.__parent_ = &root;
        b.__left_ = &a;
        b.__right_ = &c;
        b.__is_black_ = true;

        a.__parent_ = &b;
        a.__left_ = 0;
        a.__right_ = 0;
        a.__is_black_ = false;

        c.__parent_ = &b;
        c.__left_ = 0;
        c.__right_ = 0;
        c.__is_black_ = false;

        std::__tree_remove(root.__left_, &c);

        assert(std::__tree_invariant(root.__left_));

        assert(root.__parent_ == 0);
        assert(root.__left_ == &b);
        assert(root.__right_ == 0);
        assert(root.__is_black_ == false);

        assert(a.__parent_ == &b);
        assert(a.__left_ == 0);
        assert(a.__right_ == 0);
        assert(a.__is_black_ == false);

        assert(b.__parent_ == &root);
        assert(b.__left_ == &a);
        assert(b.__right_ == 0);
        assert(b.__is_black_ == true);

        std::__tree_remove(root.__left_, &b);

        assert(std::__tree_invariant(root.__left_));

        assert(root.__parent_ == 0);
        assert(root.__left_ == &a);
        assert(root.__right_ == 0);
        assert(root.__is_black_ == false);

        assert(a.__parent_ == &root);
        assert(a.__left_ == 0);
        assert(a.__right_ == 0);
        assert(a.__is_black_ == true);

        std::__tree_remove(root.__left_, &a);

        assert(std::__tree_invariant(root.__left_));

        assert(root.__parent_ == 0);
        assert(root.__left_ == 0);
        assert(root.__right_ == 0);
        assert(root.__is_black_ == false);
    }
    {
        Node root;
        Node a;
        Node b;
        Node c;

        root.__left_ = &b;

        b.__parent_ = &root;
        b.__left_ = &a;
        b.__right_ = &c;
        b.__is_black_ = true;

        a.__parent_ = &b;
        a.__left_ = 0;
        a.__right_ = 0;
        a.__is_black_ = true;

        c.__parent_ = &b;
        c.__left_ = 0;
        c.__right_ = 0;
        c.__is_black_ = true;

        std::__tree_remove(root.__left_, &c);

        assert(std::__tree_invariant(root.__left_));

        assert(root.__parent_ == 0);
        assert(root.__left_ == &b);
        assert(root.__right_ == 0);
        assert(root.__is_black_ == false);

        assert(a.__parent_ == &b);
        assert(a.__left_ == 0);
        assert(a.__right_ == 0);
        assert(a.__is_black_ == false);

        assert(b.__parent_ == &root);
        assert(b.__left_ == &a);
        assert(b.__right_ == 0);
        assert(b.__is_black_ == true);

        std::__tree_remove(root.__left_, &a);

        assert(std::__tree_invariant(root.__left_));

        assert(root.__parent_ == 0);
        assert(root.__left_ == &b);
        assert(root.__right_ == 0);
        assert(root.__is_black_ == false);

        assert(b.__parent_ == &root);
        assert(b.__left_ == 0);
        assert(b.__right_ == 0);
        assert(b.__is_black_ == true);

        std::__tree_remove(root.__left_, &b);

        assert(std::__tree_invariant(root.__left_));

        assert(root.__parent_ == 0);
        assert(root.__left_ == 0);
        assert(root.__right_ == 0);
        assert(root.__is_black_ == false);
    }
    {
        Node root;
        Node a;
        Node b;
        Node c;

        root.__left_ = &b;

        b.__parent_ = &root;
        b.__left_ = &a;
        b.__right_ = &c;
        b.__is_black_ = true;

        a.__parent_ = &b;
        a.__left_ = 0;
        a.__right_ = 0;
        a.__is_black_ = false;

        c.__parent_ = &b;
        c.__left_ = 0;
        c.__right_ = 0;
        c.__is_black_ = false;

        std::__tree_remove(root.__left_, &c);

        assert(std::__tree_invariant(root.__left_));

        assert(root.__parent_ == 0);
        assert(root.__left_ == &b);
        assert(root.__right_ == 0);
        assert(root.__is_black_ == false);

        assert(a.__parent_ == &b);
        assert(a.__left_ == 0);
        assert(a.__right_ == 0);
        assert(a.__is_black_ == false);

        assert(b.__parent_ == &root);
        assert(b.__left_ == &a);
        assert(b.__right_ == 0);
        assert(b.__is_black_ == true);

        std::__tree_remove(root.__left_, &a);

        assert(std::__tree_invariant(root.__left_));

        assert(root.__parent_ == 0);
        assert(root.__left_ == &b);
        assert(root.__right_ == 0);
        assert(root.__is_black_ == false);

        assert(b.__parent_ == &root);
        assert(b.__left_ == 0);
        assert(b.__right_ == 0);
        assert(b.__is_black_ == true);

        std::__tree_remove(root.__left_, &b);

        assert(std::__tree_invariant(root.__left_));

        assert(root.__parent_ == 0);
        assert(root.__left_ == 0);
        assert(root.__right_ == 0);
        assert(root.__is_black_ == false);
    }
}

void
test3()
{
    Node root;
    Node a;
    Node b;
    Node c;
    Node d;
    Node e;
    Node f;
    Node g;
    Node h;

    root.__left_ = &e;

    e.__parent_ = &root;
    e.__left_ = &c;
    e.__right_ = &g;
    e.__is_black_ = true;

    c.__parent_ = &e;
    c.__left_ = &b;
    c.__right_ = &d;
    c.__is_black_ = false;

    g.__parent_ = &e;
    g.__left_ = &f;
    g.__right_ = &h;
    g.__is_black_ = false;

    b.__parent_ = &c;
    b.__left_ = &a;
    b.__right_ = 0;
    b.__is_black_ = true;

    d.__parent_ = &c;
    d.__left_ = 0;
    d.__right_ = 0;
    d.__is_black_ = true;

    f.__parent_ = &g;
    f.__left_ = 0;
    f.__right_ = 0;
    f.__is_black_ = true;

    h.__parent_ = &g;
    h.__left_ = 0;
    h.__right_ = 0;
    h.__is_black_ = true;

    a.__parent_ = &b;
    a.__left_ = 0;
    a.__right_ = 0;
    a.__is_black_ = false;

    assert(std::__tree_invariant(root.__left_));

    std::__tree_remove(root.__left_, &h);

    assert(std::__tree_invariant(root.__left_));

    assert(root.__parent_ == 0);
    assert(root.__left_ == &e);
    assert(root.__right_ == 0);
    assert(root.__is_black_ == false);

    assert(e.__parent_ == &root);
    assert(e.__left_ == &c);
    assert(e.__right_ == &g);
    assert(e.__is_black_ == true);

    assert(c.__parent_ == &e);
    assert(c.__left_ == &b);
    assert(c.__right_ == &d);
    assert(c.__is_black_ == false);

    assert(g.__parent_ == &e);
    assert(g.__left_ == &f);
    assert(g.__right_ == 0);
    assert(g.__is_black_ == true);

    assert(b.__parent_ == &c);
    assert(b.__left_ == &a);
    assert(b.__right_ == 0);
    assert(b.__is_black_ == true);

    assert(a.__parent_ == &b);
    assert(a.__left_ == 0);
    assert(a.__right_ == 0);
    assert(a.__is_black_ == false);

    assert(d.__parent_ == &c);
    assert(d.__left_ == 0);
    assert(d.__right_ == 0);
    assert(d.__is_black_ == true);

    assert(f.__parent_ == &g);
    assert(f.__left_ == 0);
    assert(f.__right_ == 0);
    assert(f.__is_black_ == false);

    std::__tree_remove(root.__left_, &g);

    assert(std::__tree_invariant(root.__left_));

    assert(root.__parent_ == 0);
    assert(root.__left_ == &e);
    assert(root.__right_ == 0);
    assert(root.__is_black_ == false);

    assert(e.__parent_ == &root);
    assert(e.__left_ == &c);
    assert(e.__right_ == &f);
    assert(e.__is_black_ == true);

    assert(c.__parent_ == &e);
    assert(c.__left_ == &b);
    assert(c.__right_ == &d);
    assert(c.__is_black_ == false);

    assert(b.__parent_ == &c);
    assert(b.__left_ == &a);
    assert(b.__right_ == 0);
    assert(b.__is_black_ == true);

    assert(a.__parent_ == &b);
    assert(a.__left_ == 0);
    assert(a.__right_ == 0);
    assert(a.__is_black_ == false);

    assert(d.__parent_ == &c);
    assert(d.__left_ == 0);
    assert(d.__right_ == 0);
    assert(d.__is_black_ == true);

    assert(f.__parent_ == &e);
    assert(f.__left_ == 0);
    assert(f.__right_ == 0);
    assert(f.__is_black_ == true);

    std::__tree_remove(root.__left_, &f);

    assert(std::__tree_invariant(root.__left_));

    assert(root.__parent_ == 0);
    assert(root.__left_ == &c);
    assert(root.__right_ == 0);
    assert(root.__is_black_ == false);

    assert(c.__parent_ == &root);
    assert(c.__left_ == &b);
    assert(c.__right_ == &e);
    assert(c.__is_black_ == true);

    assert(b.__parent_ == &c);
    assert(b.__left_ == &a);
    assert(b.__right_ == 0);
    assert(b.__is_black_ == true);

    assert(e.__parent_ == &c);
    assert(e.__left_ == &d);
    assert(e.__right_ == 0);
    assert(e.__is_black_ == true);

    assert(a.__parent_ == &b);
    assert(a.__left_ == 0);
    assert(a.__right_ == 0);
    assert(a.__is_black_ == false);

    assert(d.__parent_ == &e);
    assert(d.__left_ == 0);
    assert(d.__right_ == 0);
    assert(d.__is_black_ == false);

    std::__tree_remove(root.__left_, &e);

    assert(std::__tree_invariant(root.__left_));

    assert(root.__parent_ == 0);
    assert(root.__left_ == &c);
    assert(root.__right_ == 0);
    assert(root.__is_black_ == false);

    assert(c.__parent_ == &root);
    assert(c.__left_ == &b);
    assert(c.__right_ == &d);
    assert(c.__is_black_ == true);

    assert(b.__parent_ == &c);
    assert(b.__left_ == &a);
    assert(b.__right_ == 0);
    assert(b.__is_black_ == true);

    assert(a.__parent_ == &b);
    assert(a.__left_ == 0);
    assert(a.__right_ == 0);
    assert(a.__is_black_ == false);

    assert(d.__parent_ == &c);
    assert(d.__left_ == 0);
    assert(d.__right_ == 0);
    assert(d.__is_black_ == true);

    std::__tree_remove(root.__left_, &d);

    assert(std::__tree_invariant(root.__left_));

    assert(root.__parent_ == 0);
    assert(root.__left_ == &b);
    assert(root.__right_ == 0);
    assert(root.__is_black_ == false);

    assert(b.__parent_ == &root);
    assert(b.__left_ == &a);
    assert(b.__right_ == &c);
    assert(b.__is_black_ == true);

    assert(a.__parent_ == &b);
    assert(a.__left_ == 0);
    assert(a.__right_ == 0);
    assert(a.__is_black_ == true);

    assert(c.__parent_ == &b);
    assert(c.__left_ == 0);
    assert(c.__right_ == 0);
    assert(c.__is_black_ == true);

    std::__tree_remove(root.__left_, &c);

    assert(std::__tree_invariant(root.__left_));

    assert(root.__parent_ == 0);
    assert(root.__left_ == &b);
    assert(root.__right_ == 0);
    assert(root.__is_black_ == false);

    assert(b.__parent_ == &root);
    assert(b.__left_ == &a);
    assert(b.__right_ == 0);
    assert(b.__is_black_ == true);

    assert(a.__parent_ == &b);
    assert(a.__left_ == 0);
    assert(a.__right_ == 0);
    assert(a.__is_black_ == false);

    std::__tree_remove(root.__left_, &b);

    assert(std::__tree_invariant(root.__left_));

    assert(root.__parent_ == 0);
    assert(root.__left_ == &a);
    assert(root.__right_ == 0);
    assert(root.__is_black_ == false);

    assert(a.__parent_ == &root);
    assert(a.__left_ == 0);
    assert(a.__right_ == 0);
    assert(a.__is_black_ == true);

    std::__tree_remove(root.__left_, &a);

    assert(std::__tree_invariant(root.__left_));

    assert(root.__parent_ == 0);
    assert(root.__left_ == 0);
    assert(root.__right_ == 0);
    assert(root.__is_black_ == false);
}

void
test4()
{
    Node root;
    Node a;
    Node b;
    Node c;
    Node d;
    Node e;
    Node f;
    Node g;
    Node h;

    root.__left_ = &d;

    d.__parent_ = &root;
    d.__left_ = &b;
    d.__right_ = &f;
    d.__is_black_ = true;

    b.__parent_ = &d;
    b.__left_ = &a;
    b.__right_ = &c;
    b.__is_black_ = false;

    f.__parent_ = &d;
    f.__left_ = &e;
    f.__right_ = &g;
    f.__is_black_ = false;

    a.__parent_ = &b;
    a.__left_ = 0;
    a.__right_ = 0;
    a.__is_black_ = true;

    c.__parent_ = &b;
    c.__left_ = 0;
    c.__right_ = 0;
    c.__is_black_ = true;

    e.__parent_ = &f;
    e.__left_ = 0;
    e.__right_ = 0;
    e.__is_black_ = true;

    g.__parent_ = &f;
    g.__left_ = 0;
    g.__right_ = &h;
    g.__is_black_ = true;

    h.__parent_ = &g;
    h.__left_ = 0;
    h.__right_ = 0;
    h.__is_black_ = false;

    assert(std::__tree_invariant(root.__left_));

    std::__tree_remove(root.__left_, &a);

    assert(std::__tree_invariant(root.__left_));

    assert(root.__parent_ == 0);
    assert(root.__left_ == &d);
    assert(root.__right_ == 0);
    assert(root.__is_black_ == false);

    assert(d.__parent_ == &root);
    assert(d.__left_ == &b);
    assert(d.__right_ == &f);
    assert(d.__is_black_ == true);

    assert(b.__parent_ == &d);
    assert(b.__left_ == 0);
    assert(b.__right_ == &c);
    assert(b.__is_black_ == true);

    assert(f.__parent_ == &d);
    assert(f.__left_ == &e);
    assert(f.__right_ == &g);
    assert(f.__is_black_ == false);

    assert(c.__parent_ == &b);
    assert(c.__left_ == 0);
    assert(c.__right_ == 0);
    assert(c.__is_black_ == false);

    assert(e.__parent_ == &f);
    assert(e.__left_ == 0);
    assert(e.__right_ == 0);
    assert(e.__is_black_ == true);

    assert(g.__parent_ == &f);
    assert(g.__left_ == 0);
    assert(g.__right_ == &h);
    assert(g.__is_black_ == true);

    assert(h.__parent_ == &g);
    assert(h.__left_ == 0);
    assert(h.__right_ == 0);
    assert(h.__is_black_ == false);

    std::__tree_remove(root.__left_, &b);

    assert(std::__tree_invariant(root.__left_));

    assert(root.__parent_ == 0);
    assert(root.__left_ == &d);
    assert(root.__right_ == 0);
    assert(root.__is_black_ == false);

    assert(d.__parent_ == &root);
    assert(d.__left_ == &c);
    assert(d.__right_ == &f);
    assert(d.__is_black_ == true);

    assert(c.__parent_ == &d);
    assert(c.__left_ == 0);
    assert(c.__right_ == 0);
    assert(c.__is_black_ == true);

    assert(f.__parent_ == &d);
    assert(f.__left_ == &e);
    assert(f.__right_ == &g);
    assert(f.__is_black_ == false);

    assert(e.__parent_ == &f);
    assert(e.__left_ == 0);
    assert(e.__right_ == 0);
    assert(e.__is_black_ == true);

    assert(g.__parent_ == &f);
    assert(g.__left_ == 0);
    assert(g.__right_ == &h);
    assert(g.__is_black_ == true);

    assert(h.__parent_ == &g);
    assert(h.__left_ == 0);
    assert(h.__right_ == 0);
    assert(h.__is_black_ == false);

    std::__tree_remove(root.__left_, &c);

    assert(std::__tree_invariant(root.__left_));

    assert(root.__parent_ == 0);
    assert(root.__left_ == &f);
    assert(root.__right_ == 0);
    assert(root.__is_black_ == false);

    assert(f.__parent_ == &root);
    assert(f.__left_ == &d);
    assert(f.__right_ == &g);
    assert(f.__is_black_ == true);

    assert(d.__parent_ == &f);
    assert(d.__left_ == 0);
    assert(d.__right_ == &e);
    assert(d.__is_black_ == true);

    assert(g.__parent_ == &f);
    assert(g.__left_ == 0);
    assert(g.__right_ == &h);
    assert(g.__is_black_ == true);

    assert(e.__parent_ == &d);
    assert(e.__left_ == 0);
    assert(e.__right_ == 0);
    assert(e.__is_black_ == false);

    assert(h.__parent_ == &g);
    assert(h.__left_ == 0);
    assert(h.__right_ == 0);
    assert(h.__is_black_ == false);

    std::__tree_remove(root.__left_, &d);

    assert(std::__tree_invariant(root.__left_));

    assert(root.__parent_ == 0);
    assert(root.__left_ == &f);
    assert(root.__right_ == 0);
    assert(root.__is_black_ == false);

    assert(f.__parent_ == &root);
    assert(f.__left_ == &e);
    assert(f.__right_ == &g);
    assert(f.__is_black_ == true);

    assert(e.__parent_ == &f);
    assert(e.__left_ == 0);
    assert(e.__right_ == 0);
    assert(e.__is_black_ == true);

    assert(g.__parent_ == &f);
    assert(g.__left_ == 0);
    assert(g.__right_ == &h);
    assert(g.__is_black_ == true);

    assert(h.__parent_ == &g);
    assert(h.__left_ == 0);
    assert(h.__right_ == 0);
    assert(h.__is_black_ == false);

    std::__tree_remove(root.__left_, &e);

    assert(std::__tree_invariant(root.__left_));

    assert(root.__parent_ == 0);
    assert(root.__left_ == &g);
    assert(root.__right_ == 0);
    assert(root.__is_black_ == false);

    assert(g.__parent_ == &root);
    assert(g.__left_ == &f);
    assert(g.__right_ == &h);
    assert(g.__is_black_ == true);

    assert(f.__parent_ == &g);
    assert(f.__left_ == 0);
    assert(f.__right_ == 0);
    assert(f.__is_black_ == true);

    assert(h.__parent_ == &g);
    assert(h.__left_ == 0);
    assert(h.__right_ == 0);
    assert(h.__is_black_ == true);

    std::__tree_remove(root.__left_, &f);

    assert(std::__tree_invariant(root.__left_));

    assert(root.__parent_ == 0);
    assert(root.__left_ == &g);
    assert(root.__right_ == 0);
    assert(root.__is_black_ == false);

    assert(g.__parent_ == &root);
    assert(g.__left_ == 0);
    assert(g.__right_ == &h);
    assert(g.__is_black_ == true);

    assert(h.__parent_ == &g);
    assert(h.__left_ == 0);
    assert(h.__right_ == 0);
    assert(h.__is_black_ == false);

    std::__tree_remove(root.__left_, &g);

    assert(std::__tree_invariant(root.__left_));

    assert(root.__parent_ == 0);
    assert(root.__left_ == &h);
    assert(root.__right_ == 0);
    assert(root.__is_black_ == false);

    assert(h.__parent_ == &root);
    assert(h.__left_ == 0);
    assert(h.__right_ == 0);
    assert(h.__is_black_ == true);

    std::__tree_remove(root.__left_, &h);

    assert(std::__tree_invariant(root.__left_));

    assert(root.__parent_ == 0);
    assert(root.__left_ == 0);
    assert(root.__right_ == 0);
    assert(root.__is_black_ == false);
}

int main(int, char**)
{
    test1();
    test2();
    test3();
    test4();

  return 0;
}