summaryrefslogtreecommitdiff
path: root/test/std/containers/associative/tree_remove.pass.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'test/std/containers/associative/tree_remove.pass.cpp')
-rw-r--r--test/std/containers/associative/tree_remove.pass.cpp1648
1 files changed, 0 insertions, 1648 deletions
diff --git a/test/std/containers/associative/tree_remove.pass.cpp b/test/std/containers/associative/tree_remove.pass.cpp
deleted file mode 100644
index fb14bd929e91..000000000000
--- a/test/std/containers/associative/tree_remove.pass.cpp
+++ /dev/null
@@ -1,1648 +0,0 @@
-//===----------------------------------------------------------------------===//
-//
-// The LLVM Compiler Infrastructure
-//
-// This file is dual licensed under the MIT and the University of Illinois Open
-// Source Licenses. 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();
-}
generated by cgit v1.2.3 (git 2.25.1) at 2025-10-10 05:53:13 +0000