diff options
Diffstat (limited to 'test/libcxx/containers/associative')
7 files changed, 3571 insertions, 0 deletions
diff --git a/test/libcxx/containers/associative/map/version.pass.cpp b/test/libcxx/containers/associative/map/version.pass.cpp new file mode 100644 index 0000000000000..b2e3fa43e7879 --- /dev/null +++ b/test/libcxx/containers/associative/map/version.pass.cpp @@ -0,0 +1,20 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <map> + +#include <map> + +#ifndef _LIBCPP_VERSION +#error _LIBCPP_VERSION not defined +#endif + +int main() +{ +} diff --git a/test/libcxx/containers/associative/set/version.pass.cpp b/test/libcxx/containers/associative/set/version.pass.cpp new file mode 100644 index 0000000000000..c3c4d926e5c33 --- /dev/null +++ b/test/libcxx/containers/associative/set/version.pass.cpp @@ -0,0 +1,20 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <set> + +#include <set> + +#ifndef _LIBCPP_VERSION +#error _LIBCPP_VERSION not defined +#endif + +int main() +{ +} diff --git a/test/libcxx/containers/associative/tree_balance_after_insert.pass.cpp b/test/libcxx/containers/associative/tree_balance_after_insert.pass.cpp new file mode 100644 index 0000000000000..300c1e9a49157 --- /dev/null +++ b/test/libcxx/containers/associative/tree_balance_after_insert.pass.cpp @@ -0,0 +1,1619 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// Precondition: __root->__is_black_ == true +// template <class _NodePtr> +// void +// __tree_balance_after_insert(_NodePtr __root, _NodePtr __x) + +#include <__tree> +#include <cassert> + +struct Node +{ + Node* __left_; + Node* __right_; + Node* __parent_; + bool __is_black_; + + Node* __parent_unsafe() const { return __parent_; } + void __set_parent(Node* x) { __parent_ = x;} + + Node() : __left_(), __right_(), __parent_(), __is_black_() {} +}; + +void +test1() +{ + { + 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() +{ + test1(); + test2(); + test3(); + test4(); + test5(); +} diff --git a/test/libcxx/containers/associative/tree_key_value_traits.pass.cpp b/test/libcxx/containers/associative/tree_key_value_traits.pass.cpp new file mode 100644 index 0000000000000..0befd749a50c0 --- /dev/null +++ b/test/libcxx/containers/associative/tree_key_value_traits.pass.cpp @@ -0,0 +1,59 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +#include <__tree> +#include <map> +#include <set> +#include <type_traits> + +#include "test_macros.h" +#include "min_allocator.h" + +void testKeyValueTrait() { + { + typedef int Tp; + typedef std::__tree_key_value_types<Tp> Traits; + static_assert((std::is_same<Traits::key_type, int>::value), ""); + static_assert((std::is_same<Traits::__node_value_type, Tp>::value), ""); + static_assert((std::is_same<Traits::__container_value_type, Tp>::value), ""); + static_assert(Traits::__is_map == false, ""); + } + { + typedef std::pair<int, int> Tp; + typedef std::__tree_key_value_types<Tp> Traits; + static_assert((std::is_same<Traits::key_type, Tp>::value), ""); + static_assert((std::is_same<Traits::__node_value_type, Tp>::value), ""); + static_assert((std::is_same<Traits::__container_value_type, Tp>::value), ""); + static_assert(Traits::__is_map == false, ""); + } + { + typedef std::pair<const int, int> Tp; + typedef std::__tree_key_value_types<Tp> Traits; + static_assert((std::is_same<Traits::key_type, Tp>::value), ""); + static_assert((std::is_same<Traits::__node_value_type, Tp>::value), ""); + static_assert((std::is_same<Traits::__container_value_type, Tp>::value), ""); + static_assert(Traits::__is_map == false, ""); + } + { + typedef std::__value_type<int, int> Tp; + typedef std::__tree_key_value_types<Tp> Traits; + static_assert((std::is_same<Traits::key_type, int>::value), ""); + static_assert((std::is_same<Traits::mapped_type, int>::value), ""); + static_assert((std::is_same<Traits::__node_value_type, Tp>::value), ""); + static_assert((std::is_same<Traits::__container_value_type, + std::pair<const int, int> >::value), ""); + static_assert((std::is_same<Traits::__map_value_type, + std::pair<const int, int> >::value), ""); + static_assert(Traits::__is_map == true, ""); + } +} + +int main() { + testKeyValueTrait(); +} diff --git a/test/libcxx/containers/associative/tree_left_rotate.pass.cpp b/test/libcxx/containers/associative/tree_left_rotate.pass.cpp new file mode 100644 index 0000000000000..2720b448bdd4e --- /dev/null +++ b/test/libcxx/containers/associative/tree_left_rotate.pass.cpp @@ -0,0 +1,101 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// Precondition: __x->__right_ != nullptr +// template <class _NodePtr> +// void +// __tree_left_rotate(_NodePtr __x); + +#include <__tree> +#include <cassert> + +struct Node +{ + Node* __left_; + Node* __right_; + Node* __parent_; + + Node* __parent_unsafe() const { return __parent_; } + void __set_parent(Node* x) { __parent_ = x;} + + Node() : __left_(), __right_(), __parent_() {} +}; + +void +test1() +{ + Node root; + Node x; + Node y; + root.__left_ = &x; + x.__left_ = 0; + x.__right_ = &y; + x.__parent_ = &root; + y.__left_ = 0; + y.__right_ = 0; + y.__parent_ = &x; + std::__tree_left_rotate(&x); + assert(root.__parent_ == 0); + assert(root.__left_ == &y); + assert(root.__right_ == 0); + assert(y.__parent_ == &root); + assert(y.__left_ == &x); + assert(y.__right_ == 0); + assert(x.__parent_ == &y); + assert(x.__left_ == 0); + assert(x.__right_ == 0); +} + +void +test2() +{ + Node root; + Node x; + Node y; + Node a; + Node b; + Node c; + root.__left_ = &x; + x.__left_ = &a; + x.__right_ = &y; + x.__parent_ = &root; + y.__left_ = &b; + y.__right_ = &c; + y.__parent_ = &x; + a.__parent_ = &x; + b.__parent_ = &y; + c.__parent_ = &y; + std::__tree_left_rotate(&x); + assert(root.__parent_ == 0); + assert(root.__left_ == &y); + assert(root.__right_ == 0); + assert(y.__parent_ == &root); + assert(y.__left_ == &x); + assert(y.__right_ == &c); + assert(x.__parent_ == &y); + assert(x.__left_ == &a); + assert(x.__right_ == &b); + assert(a.__parent_ == &x); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(b.__parent_ == &x); + assert(b.__left_ == 0); + assert(b.__right_ == 0); + assert(c.__parent_ == &y); + assert(c.__left_ == 0); + assert(c.__right_ == 0); +} + +int main() +{ + test1(); + test2(); +} diff --git a/test/libcxx/containers/associative/tree_remove.pass.cpp b/test/libcxx/containers/associative/tree_remove.pass.cpp new file mode 100644 index 0000000000000..fa0b7d4a13117 --- /dev/null +++ b/test/libcxx/containers/associative/tree_remove.pass.cpp @@ -0,0 +1,1651 @@ +//===----------------------------------------------------------------------===// +// +// 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* __parent_unsafe() const { return __parent_; } + void __set_parent(Node* x) { __parent_ = x;} + + Node() : __left_(), __right_(), __parent_(), __is_black_() {} +}; + +void +test1() +{ + { + // Left + // Case 1 -> Case 2 -> x is red turned to black + Node root; + Node b; + Node c; + Node d; + Node e; + Node y; + + root.__left_ = &b; + + b.__parent_ = &root; + b.__left_ = &y; + b.__right_ = &d; + b.__is_black_ = true; + + y.__parent_ = &b; + y.__left_ = 0; + y.__right_ = 0; + y.__is_black_ = true; + + d.__parent_ = &b; + d.__left_ = &c; + d.__right_ = &e; + d.__is_black_ = false; + + c.__parent_ = &d; + c.__left_ = 0; + c.__right_ = 0; + c.__is_black_ = true; + + e.__parent_ = &d; + e.__left_ = 0; + e.__right_ = 0; + e.__is_black_ = true; + + std::__tree_remove(root.__left_, &y); + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &d); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(d.__parent_ == &root); + assert(d.__left_ == &b); + assert(d.__right_ == &e); + assert(d.__is_black_ == true); + + assert(b.__parent_ == &d); + assert(b.__left_ == 0); + assert(b.__right_ == &c); + assert(b.__is_black_ == true); + + assert(c.__parent_ == &b); + assert(c.__left_ == 0); + assert(c.__right_ == 0); + assert(c.__is_black_ == false); + + assert(e.__parent_ == &d); + assert(e.__left_ == 0); + assert(e.__right_ == 0); + assert(e.__is_black_ == true); + } + { + // Right + // Case 1 -> Case 2 -> x is red turned to black + Node root; + Node b; + Node c; + Node d; + Node e; + Node y; + + root.__left_ = &b; + + b.__parent_ = &root; + b.__right_ = &y; + b.__left_ = &d; + b.__is_black_ = true; + + y.__parent_ = &b; + y.__right_ = 0; + y.__left_ = 0; + y.__is_black_ = true; + + d.__parent_ = &b; + d.__right_ = &c; + d.__left_ = &e; + d.__is_black_ = false; + + c.__parent_ = &d; + c.__right_ = 0; + c.__left_ = 0; + c.__is_black_ = true; + + e.__parent_ = &d; + e.__right_ = 0; + e.__left_ = 0; + e.__is_black_ = true; + + std::__tree_remove(root.__left_, &y); + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &d); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(d.__parent_ == &root); + assert(d.__right_ == &b); + assert(d.__left_ == &e); + assert(d.__is_black_ == true); + + assert(b.__parent_ == &d); + assert(b.__right_ == 0); + assert(b.__left_ == &c); + assert(b.__is_black_ == true); + + assert(c.__parent_ == &b); + assert(c.__right_ == 0); + assert(c.__left_ == 0); + assert(c.__is_black_ == false); + + assert(e.__parent_ == &d); + assert(e.__right_ == 0); + assert(e.__left_ == 0); + assert(e.__is_black_ == true); + } + { + // Left + // Case 1 -> Case 3 -> Case 4 + Node root; + Node b; + Node c; + Node d; + Node e; + Node f; + Node y; + + root.__left_ = &b; + + b.__parent_ = &root; + b.__left_ = &y; + b.__right_ = &d; + b.__is_black_ = true; + + y.__parent_ = &b; + y.__left_ = 0; + y.__right_ = 0; + y.__is_black_ = true; + + d.__parent_ = &b; + d.__left_ = &c; + d.__right_ = &e; + d.__is_black_ = false; + + c.__parent_ = &d; + c.__left_ = &f; + c.__right_ = 0; + c.__is_black_ = true; + + e.__parent_ = &d; + e.__left_ = 0; + e.__right_ = 0; + e.__is_black_ = true; + + f.__parent_ = &c; + f.__left_ = 0; + f.__right_ = 0; + f.__is_black_ = false; + + std::__tree_remove(root.__left_, &y); + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &d); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(d.__parent_ == &root); + assert(d.__left_ == &f); + assert(d.__right_ == &e); + assert(d.__is_black_ == true); + + assert(f.__parent_ == &d); + assert(f.__left_ == &b); + assert(f.__right_ == &c); + assert(f.__is_black_ == false); + + assert(b.__parent_ == &f); + assert(b.__left_ == 0); + assert(b.__right_ == 0); + assert(b.__is_black_ == true); + + assert(c.__parent_ == &f); + assert(c.__left_ == 0); + assert(c.__right_ == 0); + assert(c.__is_black_ == true); + + assert(e.__parent_ == &d); + assert(e.__left_ == 0); + assert(e.__right_ == 0); + assert(e.__is_black_ == true); + } + { + // Right + // Case 1 -> Case 3 -> Case 4 + Node root; + Node b; + Node c; + Node d; + Node e; + Node f; + Node y; + + root.__left_ = &b; + + b.__parent_ = &root; + b.__right_ = &y; + b.__left_ = &d; + b.__is_black_ = true; + + y.__parent_ = &b; + y.__right_ = 0; + y.__left_ = 0; + y.__is_black_ = true; + + d.__parent_ = &b; + d.__right_ = &c; + d.__left_ = &e; + d.__is_black_ = false; + + c.__parent_ = &d; + c.__right_ = &f; + c.__left_ = 0; + c.__is_black_ = true; + + e.__parent_ = &d; + e.__right_ = 0; + e.__left_ = 0; + e.__is_black_ = true; + + f.__parent_ = &c; + f.__right_ = 0; + f.__left_ = 0; + f.__is_black_ = false; + + std::__tree_remove(root.__left_, &y); + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &d); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(d.__parent_ == &root); + assert(d.__right_ == &f); + assert(d.__left_ == &e); + assert(d.__is_black_ == true); + + assert(f.__parent_ == &d); + assert(f.__right_ == &b); + assert(f.__left_ == &c); + assert(f.__is_black_ == false); + + assert(b.__parent_ == &f); + assert(b.__right_ == 0); + assert(b.__left_ == 0); + assert(b.__is_black_ == true); + + assert(c.__parent_ == &f); + assert(c.__right_ == 0); + assert(c.__left_ == 0); + assert(c.__is_black_ == true); + + assert(e.__parent_ == &d); + assert(e.__right_ == 0); + assert(e.__left_ == 0); + assert(e.__is_black_ == true); + } +} + +void +test2() +{ + { + Node root; + Node a; + Node b; + Node c; + + root.__left_ = &b; + + b.__parent_ = &root; + b.__left_ = &a; + b.__right_ = &c; + b.__is_black_ = true; + + a.__parent_ = &b; + a.__left_ = 0; + a.__right_ = 0; + a.__is_black_ = true; + + c.__parent_ = &b; + c.__left_ = 0; + c.__right_ = 0; + c.__is_black_ = true; + + std::__tree_remove(root.__left_, &a); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &b); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(b.__parent_ == &root); + assert(b.__left_ == 0); + assert(b.__right_ == &c); + assert(b.__is_black_ == true); + + assert(c.__parent_ == &b); + assert(c.__left_ == 0); + assert(c.__right_ == 0); + assert(c.__is_black_ == false); + + std::__tree_remove(root.__left_, &b); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &c); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(c.__parent_ == &root); + assert(c.__left_ == 0); + assert(c.__right_ == 0); + assert(c.__is_black_ == true); + + std::__tree_remove(root.__left_, &c); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == 0); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + } + { + Node root; + Node a; + Node b; + Node c; + + root.__left_ = &b; + + b.__parent_ = &root; + b.__left_ = &a; + b.__right_ = &c; + b.__is_black_ = true; + + a.__parent_ = &b; + a.__left_ = 0; + a.__right_ = 0; + a.__is_black_ = false; + + c.__parent_ = &b; + c.__left_ = 0; + c.__right_ = 0; + c.__is_black_ = false; + + std::__tree_remove(root.__left_, &a); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &b); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(b.__parent_ == &root); + assert(b.__left_ == 0); + assert(b.__right_ == &c); + assert(b.__is_black_ == true); + + assert(c.__parent_ == &b); + assert(c.__left_ == 0); + assert(c.__right_ == 0); + assert(c.__is_black_ == false); + + std::__tree_remove(root.__left_, &b); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &c); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(c.__parent_ == &root); + assert(c.__left_ == 0); + assert(c.__right_ == 0); + assert(c.__is_black_ == true); + + std::__tree_remove(root.__left_, &c); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == 0); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + } + { + Node root; + Node a; + Node b; + Node c; + + root.__left_ = &b; + + b.__parent_ = &root; + b.__left_ = &a; + b.__right_ = &c; + b.__is_black_ = true; + + a.__parent_ = &b; + a.__left_ = 0; + a.__right_ = 0; + a.__is_black_ = true; + + c.__parent_ = &b; + c.__left_ = 0; + c.__right_ = 0; + c.__is_black_ = true; + + std::__tree_remove(root.__left_, &a); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &b); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(b.__parent_ == &root); + assert(b.__left_ == 0); + assert(b.__right_ == &c); + assert(b.__is_black_ == true); + + assert(c.__parent_ == &b); + assert(c.__left_ == 0); + assert(c.__right_ == 0); + assert(c.__is_black_ == false); + + std::__tree_remove(root.__left_, &c); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &b); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(b.__parent_ == &root); + assert(b.__left_ == 0); + assert(b.__right_ == 0); + assert(b.__is_black_ == true); + + std::__tree_remove(root.__left_, &b); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == 0); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + } + { + Node root; + Node a; + Node b; + Node c; + + root.__left_ = &b; + + b.__parent_ = &root; + b.__left_ = &a; + b.__right_ = &c; + b.__is_black_ = true; + + a.__parent_ = &b; + a.__left_ = 0; + a.__right_ = 0; + a.__is_black_ = false; + + c.__parent_ = &b; + c.__left_ = 0; + c.__right_ = 0; + c.__is_black_ = false; + + std::__tree_remove(root.__left_, &a); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &b); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(b.__parent_ == &root); + assert(b.__left_ == 0); + assert(b.__right_ == &c); + assert(b.__is_black_ == true); + + assert(c.__parent_ == &b); + assert(c.__left_ == 0); + assert(c.__right_ == 0); + assert(c.__is_black_ == false); + + std::__tree_remove(root.__left_, &c); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &b); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(b.__parent_ == &root); + assert(b.__left_ == 0); + assert(b.__right_ == 0); + assert(b.__is_black_ == true); + + std::__tree_remove(root.__left_, &b); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == 0); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + } + { + Node root; + Node a; + Node b; + Node c; + + root.__left_ = &b; + + b.__parent_ = &root; + b.__left_ = &a; + b.__right_ = &c; + b.__is_black_ = true; + + a.__parent_ = &b; + a.__left_ = 0; + a.__right_ = 0; + a.__is_black_ = true; + + c.__parent_ = &b; + c.__left_ = 0; + c.__right_ = 0; + c.__is_black_ = true; + + std::__tree_remove(root.__left_, &b); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &c); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(a.__parent_ == &c); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == false); + + assert(c.__parent_ == &root); + assert(c.__left_ == &a); + assert(c.__right_ == 0); + assert(c.__is_black_ == true); + + std::__tree_remove(root.__left_, &a); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &c); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(c.__parent_ == &root); + assert(c.__left_ == 0); + assert(c.__right_ == 0); + assert(c.__is_black_ == true); + + std::__tree_remove(root.__left_, &c); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == 0); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + } + { + Node root; + Node a; + Node b; + Node c; + + root.__left_ = &b; + + b.__parent_ = &root; + b.__left_ = &a; + b.__right_ = &c; + b.__is_black_ = true; + + a.__parent_ = &b; + a.__left_ = 0; + a.__right_ = 0; + a.__is_black_ = false; + + c.__parent_ = &b; + c.__left_ = 0; + c.__right_ = 0; + c.__is_black_ = false; + + std::__tree_remove(root.__left_, &b); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &c); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(a.__parent_ == &c); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == false); + + assert(c.__parent_ == &root); + assert(c.__left_ == &a); + assert(c.__right_ == 0); + assert(c.__is_black_ == true); + + std::__tree_remove(root.__left_, &a); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &c); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(c.__parent_ == &root); + assert(c.__left_ == 0); + assert(c.__right_ == 0); + assert(c.__is_black_ == true); + + std::__tree_remove(root.__left_, &c); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == 0); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + } + { + Node root; + Node a; + Node b; + Node c; + + root.__left_ = &b; + + b.__parent_ = &root; + b.__left_ = &a; + b.__right_ = &c; + b.__is_black_ = true; + + a.__parent_ = &b; + a.__left_ = 0; + a.__right_ = 0; + a.__is_black_ = true; + + c.__parent_ = &b; + c.__left_ = 0; + c.__right_ = 0; + c.__is_black_ = true; + + std::__tree_remove(root.__left_, &b); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &c); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(a.__parent_ == &c); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == false); + + assert(c.__parent_ == &root); + assert(c.__left_ == &a); + assert(c.__right_ == 0); + assert(c.__is_black_ == true); + + std::__tree_remove(root.__left_, &c); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &a); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(a.__parent_ == &root); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == true); + + std::__tree_remove(root.__left_, &a); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == 0); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + } + { + Node root; + Node a; + Node b; + Node c; + + root.__left_ = &b; + + b.__parent_ = &root; + b.__left_ = &a; + b.__right_ = &c; + b.__is_black_ = true; + + a.__parent_ = &b; + a.__left_ = 0; + a.__right_ = 0; + a.__is_black_ = false; + + c.__parent_ = &b; + c.__left_ = 0; + c.__right_ = 0; + c.__is_black_ = false; + + std::__tree_remove(root.__left_, &b); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &c); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(a.__parent_ == &c); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == false); + + assert(c.__parent_ == &root); + assert(c.__left_ == &a); + assert(c.__right_ == 0); + assert(c.__is_black_ == true); + + std::__tree_remove(root.__left_, &c); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &a); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(a.__parent_ == &root); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == true); + + std::__tree_remove(root.__left_, &a); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == 0); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + } + { + Node root; + Node a; + Node b; + Node c; + + root.__left_ = &b; + + b.__parent_ = &root; + b.__left_ = &a; + b.__right_ = &c; + b.__is_black_ = true; + + a.__parent_ = &b; + a.__left_ = 0; + a.__right_ = 0; + a.__is_black_ = true; + + c.__parent_ = &b; + c.__left_ = 0; + c.__right_ = 0; + c.__is_black_ = true; + + std::__tree_remove(root.__left_, &c); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &b); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(a.__parent_ == &b); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == false); + + assert(b.__parent_ == &root); + assert(b.__left_ == &a); + assert(b.__right_ == 0); + assert(b.__is_black_ == true); + + std::__tree_remove(root.__left_, &b); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &a); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(a.__parent_ == &root); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == true); + + std::__tree_remove(root.__left_, &a); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == 0); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + } + { + Node root; + Node a; + Node b; + Node c; + + root.__left_ = &b; + + b.__parent_ = &root; + b.__left_ = &a; + b.__right_ = &c; + b.__is_black_ = true; + + a.__parent_ = &b; + a.__left_ = 0; + a.__right_ = 0; + a.__is_black_ = false; + + c.__parent_ = &b; + c.__left_ = 0; + c.__right_ = 0; + c.__is_black_ = false; + + std::__tree_remove(root.__left_, &c); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &b); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(a.__parent_ == &b); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == false); + + assert(b.__parent_ == &root); + assert(b.__left_ == &a); + assert(b.__right_ == 0); + assert(b.__is_black_ == true); + + std::__tree_remove(root.__left_, &b); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &a); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(a.__parent_ == &root); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == true); + + std::__tree_remove(root.__left_, &a); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == 0); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + } + { + Node root; + Node a; + Node b; + Node c; + + root.__left_ = &b; + + b.__parent_ = &root; + b.__left_ = &a; + b.__right_ = &c; + b.__is_black_ = true; + + a.__parent_ = &b; + a.__left_ = 0; + a.__right_ = 0; + a.__is_black_ = true; + + c.__parent_ = &b; + c.__left_ = 0; + c.__right_ = 0; + c.__is_black_ = true; + + std::__tree_remove(root.__left_, &c); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &b); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(a.__parent_ == &b); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == false); + + assert(b.__parent_ == &root); + assert(b.__left_ == &a); + assert(b.__right_ == 0); + assert(b.__is_black_ == true); + + std::__tree_remove(root.__left_, &a); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &b); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(b.__parent_ == &root); + assert(b.__left_ == 0); + assert(b.__right_ == 0); + assert(b.__is_black_ == true); + + std::__tree_remove(root.__left_, &b); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == 0); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + } + { + Node root; + Node a; + Node b; + Node c; + + root.__left_ = &b; + + b.__parent_ = &root; + b.__left_ = &a; + b.__right_ = &c; + b.__is_black_ = true; + + a.__parent_ = &b; + a.__left_ = 0; + a.__right_ = 0; + a.__is_black_ = false; + + c.__parent_ = &b; + c.__left_ = 0; + c.__right_ = 0; + c.__is_black_ = false; + + std::__tree_remove(root.__left_, &c); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &b); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(a.__parent_ == &b); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == false); + + assert(b.__parent_ == &root); + assert(b.__left_ == &a); + assert(b.__right_ == 0); + assert(b.__is_black_ == true); + + std::__tree_remove(root.__left_, &a); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &b); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(b.__parent_ == &root); + assert(b.__left_ == 0); + assert(b.__right_ == 0); + assert(b.__is_black_ == true); + + std::__tree_remove(root.__left_, &b); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == 0); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + } +} + +void +test3() +{ + Node root; + Node a; + Node b; + Node c; + Node d; + Node e; + Node f; + Node g; + Node h; + + root.__left_ = &e; + + e.__parent_ = &root; + e.__left_ = &c; + e.__right_ = &g; + e.__is_black_ = true; + + c.__parent_ = &e; + c.__left_ = &b; + c.__right_ = &d; + c.__is_black_ = false; + + g.__parent_ = &e; + g.__left_ = &f; + g.__right_ = &h; + g.__is_black_ = false; + + b.__parent_ = &c; + b.__left_ = &a; + b.__right_ = 0; + b.__is_black_ = true; + + d.__parent_ = &c; + d.__left_ = 0; + d.__right_ = 0; + d.__is_black_ = true; + + f.__parent_ = &g; + f.__left_ = 0; + f.__right_ = 0; + f.__is_black_ = true; + + h.__parent_ = &g; + h.__left_ = 0; + h.__right_ = 0; + h.__is_black_ = true; + + a.__parent_ = &b; + a.__left_ = 0; + a.__right_ = 0; + a.__is_black_ = false; + + assert(std::__tree_invariant(root.__left_)); + + std::__tree_remove(root.__left_, &h); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &e); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(e.__parent_ == &root); + assert(e.__left_ == &c); + assert(e.__right_ == &g); + assert(e.__is_black_ == true); + + assert(c.__parent_ == &e); + assert(c.__left_ == &b); + assert(c.__right_ == &d); + assert(c.__is_black_ == false); + + assert(g.__parent_ == &e); + assert(g.__left_ == &f); + assert(g.__right_ == 0); + assert(g.__is_black_ == true); + + assert(b.__parent_ == &c); + assert(b.__left_ == &a); + assert(b.__right_ == 0); + assert(b.__is_black_ == true); + + assert(a.__parent_ == &b); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == false); + + assert(d.__parent_ == &c); + assert(d.__left_ == 0); + assert(d.__right_ == 0); + assert(d.__is_black_ == true); + + assert(f.__parent_ == &g); + assert(f.__left_ == 0); + assert(f.__right_ == 0); + assert(f.__is_black_ == false); + + std::__tree_remove(root.__left_, &g); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &e); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(e.__parent_ == &root); + assert(e.__left_ == &c); + assert(e.__right_ == &f); + assert(e.__is_black_ == true); + + assert(c.__parent_ == &e); + assert(c.__left_ == &b); + assert(c.__right_ == &d); + assert(c.__is_black_ == false); + + assert(b.__parent_ == &c); + assert(b.__left_ == &a); + assert(b.__right_ == 0); + assert(b.__is_black_ == true); + + assert(a.__parent_ == &b); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == false); + + assert(d.__parent_ == &c); + assert(d.__left_ == 0); + assert(d.__right_ == 0); + assert(d.__is_black_ == true); + + assert(f.__parent_ == &e); + assert(f.__left_ == 0); + assert(f.__right_ == 0); + assert(f.__is_black_ == true); + + std::__tree_remove(root.__left_, &f); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &c); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(c.__parent_ == &root); + assert(c.__left_ == &b); + assert(c.__right_ == &e); + assert(c.__is_black_ == true); + + assert(b.__parent_ == &c); + assert(b.__left_ == &a); + assert(b.__right_ == 0); + assert(b.__is_black_ == true); + + assert(e.__parent_ == &c); + assert(e.__left_ == &d); + assert(e.__right_ == 0); + assert(e.__is_black_ == true); + + assert(a.__parent_ == &b); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == false); + + assert(d.__parent_ == &e); + assert(d.__left_ == 0); + assert(d.__right_ == 0); + assert(d.__is_black_ == false); + + std::__tree_remove(root.__left_, &e); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &c); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(c.__parent_ == &root); + assert(c.__left_ == &b); + assert(c.__right_ == &d); + assert(c.__is_black_ == true); + + assert(b.__parent_ == &c); + assert(b.__left_ == &a); + assert(b.__right_ == 0); + assert(b.__is_black_ == true); + + assert(a.__parent_ == &b); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == false); + + assert(d.__parent_ == &c); + assert(d.__left_ == 0); + assert(d.__right_ == 0); + assert(d.__is_black_ == true); + + std::__tree_remove(root.__left_, &d); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &b); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(b.__parent_ == &root); + assert(b.__left_ == &a); + assert(b.__right_ == &c); + assert(b.__is_black_ == true); + + assert(a.__parent_ == &b); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == true); + + assert(c.__parent_ == &b); + assert(c.__left_ == 0); + assert(c.__right_ == 0); + assert(c.__is_black_ == true); + + std::__tree_remove(root.__left_, &c); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &b); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(b.__parent_ == &root); + assert(b.__left_ == &a); + assert(b.__right_ == 0); + assert(b.__is_black_ == true); + + assert(a.__parent_ == &b); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == false); + + std::__tree_remove(root.__left_, &b); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &a); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(a.__parent_ == &root); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == true); + + std::__tree_remove(root.__left_, &a); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == 0); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); +} + +void +test4() +{ + Node root; + Node a; + Node b; + Node c; + Node d; + Node e; + Node f; + Node g; + Node h; + + root.__left_ = &d; + + d.__parent_ = &root; + d.__left_ = &b; + d.__right_ = &f; + d.__is_black_ = true; + + b.__parent_ = &d; + b.__left_ = &a; + b.__right_ = &c; + b.__is_black_ = false; + + f.__parent_ = &d; + f.__left_ = &e; + f.__right_ = &g; + f.__is_black_ = false; + + a.__parent_ = &b; + a.__left_ = 0; + a.__right_ = 0; + a.__is_black_ = true; + + c.__parent_ = &b; + c.__left_ = 0; + c.__right_ = 0; + c.__is_black_ = true; + + e.__parent_ = &f; + e.__left_ = 0; + e.__right_ = 0; + e.__is_black_ = true; + + g.__parent_ = &f; + g.__left_ = 0; + g.__right_ = &h; + g.__is_black_ = true; + + h.__parent_ = &g; + h.__left_ = 0; + h.__right_ = 0; + h.__is_black_ = false; + + assert(std::__tree_invariant(root.__left_)); + + std::__tree_remove(root.__left_, &a); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &d); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(d.__parent_ == &root); + assert(d.__left_ == &b); + assert(d.__right_ == &f); + assert(d.__is_black_ == true); + + assert(b.__parent_ == &d); + assert(b.__left_ == 0); + assert(b.__right_ == &c); + assert(b.__is_black_ == true); + + assert(f.__parent_ == &d); + assert(f.__left_ == &e); + assert(f.__right_ == &g); + assert(f.__is_black_ == false); + + assert(c.__parent_ == &b); + assert(c.__left_ == 0); + assert(c.__right_ == 0); + assert(c.__is_black_ == false); + + assert(e.__parent_ == &f); + assert(e.__left_ == 0); + assert(e.__right_ == 0); + assert(e.__is_black_ == true); + + assert(g.__parent_ == &f); + assert(g.__left_ == 0); + assert(g.__right_ == &h); + assert(g.__is_black_ == true); + + assert(h.__parent_ == &g); + assert(h.__left_ == 0); + assert(h.__right_ == 0); + assert(h.__is_black_ == false); + + std::__tree_remove(root.__left_, &b); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &d); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(d.__parent_ == &root); + assert(d.__left_ == &c); + assert(d.__right_ == &f); + assert(d.__is_black_ == true); + + assert(c.__parent_ == &d); + assert(c.__left_ == 0); + assert(c.__right_ == 0); + assert(c.__is_black_ == true); + + assert(f.__parent_ == &d); + assert(f.__left_ == &e); + assert(f.__right_ == &g); + assert(f.__is_black_ == false); + + assert(e.__parent_ == &f); + assert(e.__left_ == 0); + assert(e.__right_ == 0); + assert(e.__is_black_ == true); + + assert(g.__parent_ == &f); + assert(g.__left_ == 0); + assert(g.__right_ == &h); + assert(g.__is_black_ == true); + + assert(h.__parent_ == &g); + assert(h.__left_ == 0); + assert(h.__right_ == 0); + assert(h.__is_black_ == false); + + std::__tree_remove(root.__left_, &c); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &f); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(f.__parent_ == &root); + assert(f.__left_ == &d); + assert(f.__right_ == &g); + assert(f.__is_black_ == true); + + assert(d.__parent_ == &f); + assert(d.__left_ == 0); + assert(d.__right_ == &e); + assert(d.__is_black_ == true); + + assert(g.__parent_ == &f); + assert(g.__left_ == 0); + assert(g.__right_ == &h); + assert(g.__is_black_ == true); + + assert(e.__parent_ == &d); + assert(e.__left_ == 0); + assert(e.__right_ == 0); + assert(e.__is_black_ == false); + + assert(h.__parent_ == &g); + assert(h.__left_ == 0); + assert(h.__right_ == 0); + assert(h.__is_black_ == false); + + std::__tree_remove(root.__left_, &d); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &f); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(f.__parent_ == &root); + assert(f.__left_ == &e); + assert(f.__right_ == &g); + assert(f.__is_black_ == true); + + assert(e.__parent_ == &f); + assert(e.__left_ == 0); + assert(e.__right_ == 0); + assert(e.__is_black_ == true); + + assert(g.__parent_ == &f); + assert(g.__left_ == 0); + assert(g.__right_ == &h); + assert(g.__is_black_ == true); + + assert(h.__parent_ == &g); + assert(h.__left_ == 0); + assert(h.__right_ == 0); + assert(h.__is_black_ == false); + + std::__tree_remove(root.__left_, &e); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &g); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(g.__parent_ == &root); + assert(g.__left_ == &f); + assert(g.__right_ == &h); + assert(g.__is_black_ == true); + + assert(f.__parent_ == &g); + assert(f.__left_ == 0); + assert(f.__right_ == 0); + assert(f.__is_black_ == true); + + assert(h.__parent_ == &g); + assert(h.__left_ == 0); + assert(h.__right_ == 0); + assert(h.__is_black_ == true); + + std::__tree_remove(root.__left_, &f); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &g); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(g.__parent_ == &root); + assert(g.__left_ == 0); + assert(g.__right_ == &h); + assert(g.__is_black_ == true); + + assert(h.__parent_ == &g); + assert(h.__left_ == 0); + assert(h.__right_ == 0); + assert(h.__is_black_ == false); + + std::__tree_remove(root.__left_, &g); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &h); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(h.__parent_ == &root); + assert(h.__left_ == 0); + assert(h.__right_ == 0); + assert(h.__is_black_ == true); + + std::__tree_remove(root.__left_, &h); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == 0); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); +} + +int main() +{ + test1(); + test2(); + test3(); + test4(); +} diff --git a/test/libcxx/containers/associative/tree_right_rotate.pass.cpp b/test/libcxx/containers/associative/tree_right_rotate.pass.cpp new file mode 100644 index 0000000000000..9355a46b4e2b7 --- /dev/null +++ b/test/libcxx/containers/associative/tree_right_rotate.pass.cpp @@ -0,0 +1,101 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// Precondition: __x->__left_ != nullptr +// template <class _NodePtr> +// void +// __tree_right_rotate(_NodePtr __x); + +#include <__tree> +#include <cassert> + +struct Node +{ + Node* __left_; + Node* __right_; + Node* __parent_; + + Node* __parent_unsafe() const { return __parent_; } + void __set_parent(Node* x) { __parent_ = x;} + + Node() : __left_(), __right_(), __parent_() {} +}; + +void +test1() +{ + Node root; + Node x; + Node y; + root.__left_ = &x; + x.__left_ = &y; + x.__right_ = 0; + x.__parent_ = &root; + y.__left_ = 0; + y.__right_ = 0; + y.__parent_ = &x; + std::__tree_right_rotate(&x); + assert(root.__parent_ == 0); + assert(root.__left_ == &y); + assert(root.__right_ == 0); + assert(y.__parent_ == &root); + assert(y.__left_ == 0); + assert(y.__right_ == &x); + assert(x.__parent_ == &y); + assert(x.__left_ == 0); + assert(x.__right_ == 0); +} + +void +test2() +{ + Node root; + Node x; + Node y; + Node a; + Node b; + Node c; + root.__left_ = &x; + x.__left_ = &y; + x.__right_ = &c; + x.__parent_ = &root; + y.__left_ = &a; + y.__right_ = &b; + y.__parent_ = &x; + a.__parent_ = &y; + b.__parent_ = &y; + c.__parent_ = &x; + std::__tree_right_rotate(&x); + assert(root.__parent_ == 0); + assert(root.__left_ == &y); + assert(root.__right_ == 0); + assert(y.__parent_ == &root); + assert(y.__left_ == &a); + assert(y.__right_ == &x); + assert(x.__parent_ == &y); + assert(x.__left_ == &b); + assert(x.__right_ == &c); + assert(a.__parent_ == &y); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(b.__parent_ == &x); + assert(b.__left_ == 0); + assert(b.__right_ == 0); + assert(c.__parent_ == &x); + assert(c.__left_ == 0); + assert(c.__right_ == 0); +} + +int main() +{ + test1(); + test2(); +} |