libcxx initial import
llvm-svn: 103490
diff --git a/libcxx/test/containers/associative/tree_remove.pass.cpp b/libcxx/test/containers/associative/tree_remove.pass.cpp
new file mode 100644
index 0000000..03af737
--- /dev/null
+++ b/libcxx/test/containers/associative/tree_remove.pass.cpp
@@ -0,0 +1,1648 @@
+//===----------------------------------------------------------------------===//
+//
+// ÊÊÊÊÊÊÊÊÊÊÊÊÊÊÊÊÊÊÊÊThe LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// 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() : __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()
+{
+ test1();
+ test2();
+ test3();
+ test4();
+}