//===----------------------------------------------------------------------===//
//
// 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

// Precondition:  __root->__is_black_ == true
// template <class _NodePtr>
// void
// __tree_balance_after_insert(_NodePtr __root, _NodePtr __x)

#include <__tree>
#include <cassert>

#include "test_macros.h"

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()
{
    {
        Node root;
        Node a;
        Node b;
        Node c;
        Node d;

        root.__left_ = &c;

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

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

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

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

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

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

        assert(root.__left_ == &c);

        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(d.__parent_ == &c);
        assert(d.__left_ == 0);
        assert(d.__right_ == 0);
        assert(d.__is_black_ == true);

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

        root.__left_ = &c;

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

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

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

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

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

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

        assert(root.__left_ == &c);

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

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

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

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

        root.__left_ = &c;

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

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

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

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

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

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

        assert(root.__left_ == &c);

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

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

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

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

        root.__left_ = &c;

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

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

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

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

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

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

        assert(root.__left_ == &c);

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

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

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

        assert(a.__parent_ == &d);
        assert(a.__left_ == 0);
        assert(a.__right_ == 0);
        assert(a.__is_black_ == false);
    }
    {
        Node root;
        Node a;
        Node b;
        Node c;
        Node d;
        Node e;
        Node f;
        Node g;
        Node h;
        Node i;

        root.__left_ = &c;

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

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

        d.__parent_ = &c;
        d.__left_ = &h;
        d.__right_ = &i;
        d.__is_black_ = false;

        a.__parent_ = &b;
        a.__left_ = &e;
        a.__right_ = &f;
        a.__is_black_ = false;

        e.__parent_ = &a;
        e.__is_black_ = true;

        f.__parent_ = &a;
        f.__is_black_ = true;

        g.__parent_ = &b;
        g.__is_black_ = true;

        h.__parent_ = &d;
        h.__is_black_ = true;

        i.__parent_ = &d;
        i.__is_black_ = true;

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

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

        assert(root.__left_ == &c);

        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_ == &g);
        assert(b.__is_black_ == true);

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

        assert(a.__parent_ == &b);
        assert(a.__left_ == &e);
        assert(a.__right_ == &f);
        assert(a.__is_black_ == false);
    }
    {
        Node root;
        Node a;
        Node b;
        Node c;
        Node d;
        Node e;
        Node f;
        Node g;
        Node h;
        Node i;

        root.__left_ = &c;

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

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

        d.__parent_ = &c;
        d.__left_ = &h;
        d.__right_ = &i;
        d.__is_black_ = false;

        a.__parent_ = &b;
        a.__left_ = &e;
        a.__right_ = &f;
        a.__is_black_ = false;

        e.__parent_ = &a;
        e.__is_black_ = true;

        f.__parent_ = &a;
        f.__is_black_ = true;

        g.__parent_ = &b;
        g.__is_black_ = true;

        h.__parent_ = &d;
        h.__is_black_ = true;

        i.__parent_ = &d;
        i.__is_black_ = true;

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

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

        assert(root.__left_ == &c);

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

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

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

        assert(a.__parent_ == &b);
        assert(a.__left_ == &e);
        assert(a.__right_ == &f);
        assert(a.__is_black_ == false);
    }
    {
        Node root;
        Node a;
        Node b;
        Node c;
        Node d;
        Node e;
        Node f;
        Node g;
        Node h;
        Node i;

        root.__left_ = &c;

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

        b.__parent_ = &c;
        b.__left_ = &g;
        b.__right_ = &h;
        b.__is_black_ = false;

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

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

        e.__parent_ = &a;
        e.__is_black_ = true;

        f.__parent_ = &a;
        f.__is_black_ = true;

        g.__parent_ = &b;
        g.__is_black_ = true;

        h.__parent_ = &b;
        h.__is_black_ = true;

        i.__parent_ = &d;
        i.__is_black_ = true;

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

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

        assert(root.__left_ == &c);

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

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

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

        assert(a.__parent_ == &d);
        assert(a.__left_ == &e);
        assert(a.__right_ == &f);
        assert(a.__is_black_ == false);
    }
    {
        Node root;
        Node a;
        Node b;
        Node c;
        Node d;
        Node e;
        Node f;
        Node g;
        Node h;
        Node i;

        root.__left_ = &c;

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

        b.__parent_ = &c;
        b.__left_ = &g;
        b.__right_ = &h;
        b.__is_black_ = false;

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

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

        e.__parent_ = &a;
        e.__is_black_ = true;

        f.__parent_ = &a;
        f.__is_black_ = true;

        g.__parent_ = &b;
        g.__is_black_ = true;

        h.__parent_ = &b;
        h.__is_black_ = true;

        i.__parent_ = &d;
        i.__is_black_ = true;

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

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

        assert(root.__left_ == &c);

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

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

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

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

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

        root.__left_ = &c;

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

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

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

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

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

        assert(root.__left_ == &b);

        assert(c.__parent_ == &b);
        assert(c.__left_ == 0);
        assert(c.__right_ == 0);
        assert(c.__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_ == &c);
        assert(b.__is_black_ == true);
    }
    {
        Node root;
        Node a;
        Node b;
        Node c;

        root.__left_ = &a;

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

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

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

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

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

        assert(root.__left_ == &b);

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

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

        assert(b.__parent_ == &root);
        assert(b.__left_ == &a);
        assert(b.__right_ == &c);
        assert(b.__is_black_ == true);
    }
    {
        Node root;
        Node a;
        Node b;
        Node c;
        Node d;
        Node e;
        Node f;
        Node g;

        root.__left_ = &c;

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

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

        b.__parent_ = &a;
        b.__left_ = &e;
        b.__right_ = &f;
        b.__is_black_ = false;

        d.__parent_ = &a;
        d.__is_black_ = true;

        e.__parent_ = &b;
        e.__is_black_ = true;

        f.__parent_ = &b;
        f.__is_black_ = true;

        g.__parent_ = &c;
        g.__is_black_ = true;

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

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

        assert(root.__left_ == &b);

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

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

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

        assert(d.__parent_ == &a);
        assert(d.__is_black_ == true);

        assert(e.__parent_ == &a);
        assert(e.__is_black_ == true);

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

        assert(g.__parent_ == &c);
        assert(g.__is_black_ == true);
    }
    {
        Node root;
        Node a;
        Node b;
        Node c;
        Node d;
        Node e;
        Node f;
        Node g;

        root.__left_ = &a;

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

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

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

        d.__parent_ = &a;
        d.__is_black_ = true;

        e.__parent_ = &b;
        e.__is_black_ = true;

        f.__parent_ = &b;
        f.__is_black_ = true;

        g.__parent_ = &c;
        g.__is_black_ = true;

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

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

        assert(root.__left_ == &b);

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

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

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

        assert(d.__parent_ == &a);
        assert(d.__is_black_ == true);

        assert(e.__parent_ == &a);
        assert(e.__is_black_ == true);

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

        assert(g.__parent_ == &c);
        assert(g.__is_black_ == true);
    }
}

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

        root.__left_ = &c;

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

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

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

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

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

        assert(root.__left_ == &b);

        assert(c.__parent_ == &b);
        assert(c.__left_ == 0);
        assert(c.__right_ == 0);
        assert(c.__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_ == &c);
        assert(b.__is_black_ == true);
    }
    {
        Node root;
        Node a;
        Node b;
        Node c;

        root.__left_ = &a;

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

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

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

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

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

        assert(root.__left_ == &b);

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

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

        assert(b.__parent_ == &root);
        assert(b.__left_ == &a);
        assert(b.__right_ == &c);
        assert(b.__is_black_ == true);
    }
    {
        Node root;
        Node a;
        Node b;
        Node c;
        Node d;
        Node e;
        Node f;
        Node g;

        root.__left_ = &c;

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

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

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

        d.__parent_ = &a;
        d.__is_black_ = true;

        e.__parent_ = &a;
        e.__is_black_ = true;

        f.__parent_ = &b;
        f.__is_black_ = true;

        g.__parent_ = &c;
        g.__is_black_ = true;

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

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

        assert(root.__left_ == &b);

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

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

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

        assert(d.__parent_ == &a);
        assert(d.__is_black_ == true);

        assert(e.__parent_ == &a);
        assert(e.__is_black_ == true);

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

        assert(g.__parent_ == &c);
        assert(g.__is_black_ == true);
    }
    {
        Node root;
        Node a;
        Node b;
        Node c;
        Node d;
        Node e;
        Node f;
        Node g;

        root.__left_ = &a;

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

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

        c.__parent_ = &b;
        c.__left_ = &f;
        c.__right_ = &g;
        c.__is_black_ = false;

        d.__parent_ = &a;
        d.__is_black_ = true;

        e.__parent_ = &b;
        e.__is_black_ = true;

        f.__parent_ = &c;
        f.__is_black_ = true;

        g.__parent_ = &c;
        g.__is_black_ = true;

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

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

        assert(root.__left_ == &b);

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

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

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

        assert(d.__parent_ == &a);
        assert(d.__is_black_ == true);

        assert(e.__parent_ == &a);
        assert(e.__is_black_ == true);

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

        assert(g.__parent_ == &c);
        assert(g.__is_black_ == true);
    }
}

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

    root.__left_ = &a;
    a.__parent_ = &root;

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

    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);

    a.__right_ = &b;
    b.__parent_ = &a;

    std::__tree_balance_after_insert(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_ == &b);
    assert(a.__is_black_ == true);

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

    b.__right_ = &c;
    c.__parent_ = &b;

    std::__tree_balance_after_insert(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_ == &c);
    assert(b.__is_black_ == true);

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

    c.__right_ = &d;
    d.__parent_ = &c;

    std::__tree_balance_after_insert(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(a.__parent_ == &b);
    assert(a.__left_ == 0);
    assert(a.__right_ == 0);
    assert(a.__is_black_ == true);

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

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

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

    d.__right_ = &e;
    e.__parent_ = &d;

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

    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_ == &d);
    assert(b.__is_black_ == true);

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

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

    assert(c.__parent_ == &d);
    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_ == false);

    e.__right_ = &f;
    f.__parent_ = &e;

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

    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_ == &d);
    assert(b.__is_black_ == true);

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

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

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

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

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

    f.__right_ = &g;
    g.__parent_ = &f;

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

    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_ == &d);
    assert(b.__is_black_ == true);

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

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

    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_ == true);

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

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

    g.__right_ = &h;
    h.__parent_ = &g;

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

    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_ == &a);
    assert(b.__right_ == &c);
    assert(b.__is_black_ == false);

    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);

    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);
}

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

    root.__left_ = &h;
    h.__parent_ = &root;

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

    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);

    h.__left_ = &g;
    g.__parent_ = &h;

    std::__tree_balance_after_insert(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_ == &g);
    assert(h.__right_ == 0);
    assert(h.__is_black_ == true);

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

    g.__left_ = &f;
    f.__parent_ = &g;

    std::__tree_balance_after_insert(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_ == &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_ == false);

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

    f.__left_ = &e;
    e.__parent_ = &f;

    std::__tree_balance_after_insert(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_ == &e);
    assert(f.__right_ == 0);
    assert(f.__is_black_ == true);

    assert(e.__parent_ == &f);
    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_ == true);

    e.__left_ = &d;
    d.__parent_ = &e;

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

    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_ == &e);
    assert(g.__right_ == &h);
    assert(g.__is_black_ == true);

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

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

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

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

    d.__left_ = &c;
    c.__parent_ = &d;

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

    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_ == &e);
    assert(g.__right_ == &h);
    assert(g.__is_black_ == true);

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

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

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

    assert(f.__parent_ == &e);
    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);

    c.__left_ = &b;
    b.__parent_ = &c;

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

    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_ == &e);
    assert(g.__right_ == &h);
    assert(g.__is_black_ == true);

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

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

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

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

    assert(f.__parent_ == &e);
    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);

    b.__left_ = &a;
    a.__parent_ = &b;

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

    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(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(g.__parent_ == &e);
    assert(g.__left_ == &f);
    assert(g.__right_ == &h);
    assert(g.__is_black_ == false);

    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);
}

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

  return 0;
}