diff options
Diffstat (limited to 'libcxx/test/std')
18 files changed, 11 insertions, 3798 deletions
diff --git a/libcxx/test/std/containers/associative/tree_balance_after_insert.pass.cpp b/libcxx/test/std/containers/associative/tree_balance_after_insert.pass.cpp deleted file mode 100644 index b0a3e74cab0..00000000000 --- a/libcxx/test/std/containers/associative/tree_balance_after_insert.pass.cpp +++ /dev/null @@ -1,1616 +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 - -// 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() : __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/libcxx/test/std/containers/associative/tree_left_rotate.pass.cpp b/libcxx/test/std/containers/associative/tree_left_rotate.pass.cpp deleted file mode 100644 index 774cbc68798..00000000000 --- a/libcxx/test/std/containers/associative/tree_left_rotate.pass.cpp +++ /dev/null @@ -1,98 +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 - -// 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() : __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/libcxx/test/std/containers/associative/tree_remove.pass.cpp b/libcxx/test/std/containers/associative/tree_remove.pass.cpp deleted file mode 100644 index fb14bd929e9..00000000000 --- a/libcxx/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(); -} diff --git a/libcxx/test/std/containers/associative/tree_right_rotate.pass.cpp b/libcxx/test/std/containers/associative/tree_right_rotate.pass.cpp deleted file mode 100644 index 06ec7b88945..00000000000 --- a/libcxx/test/std/containers/associative/tree_right_rotate.pass.cpp +++ /dev/null @@ -1,98 +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 - -// 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() : __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(); -} diff --git a/libcxx/test/std/containers/sequences/deque/deque.capacity/resize_size.pass.cpp b/libcxx/test/std/containers/sequences/deque/deque.capacity/resize_size.pass.cpp index 84f04f9d52d..53c6bd3380a 100644 --- a/libcxx/test/std/containers/sequences/deque/deque.capacity/resize_size.pass.cpp +++ b/libcxx/test/std/containers/sequences/deque/deque.capacity/resize_size.pass.cpp @@ -12,6 +12,8 @@ // void resize(size_type n); #include <deque> +#include <algorithm> +#include <iterator> #include <cassert> #include "test_macros.h" diff --git a/libcxx/test/std/containers/sequences/deque/deque.capacity/resize_size_value.pass.cpp b/libcxx/test/std/containers/sequences/deque/deque.capacity/resize_size_value.pass.cpp index 2bf2423fb9a..12af64386bd 100644 --- a/libcxx/test/std/containers/sequences/deque/deque.capacity/resize_size_value.pass.cpp +++ b/libcxx/test/std/containers/sequences/deque/deque.capacity/resize_size_value.pass.cpp @@ -12,6 +12,8 @@ // void resize(size_type n, const value_type& v); #include <deque> +#include <algorithm> +#include <iterator> #include <cassert> #include "test_macros.h" diff --git a/libcxx/test/std/containers/sequences/deque/deque.modifiers/erase_iter.pass.cpp b/libcxx/test/std/containers/sequences/deque/deque.modifiers/erase_iter.pass.cpp index a45b75d25c9..a1c42a71dff 100644 --- a/libcxx/test/std/containers/sequences/deque/deque.modifiers/erase_iter.pass.cpp +++ b/libcxx/test/std/containers/sequences/deque/deque.modifiers/erase_iter.pass.cpp @@ -12,6 +12,8 @@ // iterator erase(const_iterator p) #include <deque> +#include <algorithm> +#include <iterator> #include <cassert> #include "min_allocator.h" diff --git a/libcxx/test/std/containers/sequences/deque/deque.modifiers/erase_iter_iter.pass.cpp b/libcxx/test/std/containers/sequences/deque/deque.modifiers/erase_iter_iter.pass.cpp index 0576aca5c1a..15d7400b869 100644 --- a/libcxx/test/std/containers/sequences/deque/deque.modifiers/erase_iter_iter.pass.cpp +++ b/libcxx/test/std/containers/sequences/deque/deque.modifiers/erase_iter_iter.pass.cpp @@ -14,6 +14,8 @@ // iterator erase(const_iterator f, const_iterator l) #include <deque> +#include <algorithm> +#include <iterator> #include <cassert> #include "min_allocator.h" diff --git a/libcxx/test/std/containers/sequences/list/list.special/db_swap_1.pass.cpp b/libcxx/test/std/containers/sequences/list/list.special/db_swap_1.pass.cpp deleted file mode 100644 index f7171795cd5..00000000000 --- a/libcxx/test/std/containers/sequences/list/list.special/db_swap_1.pass.cpp +++ /dev/null @@ -1,59 +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. -// -//===----------------------------------------------------------------------===// - -// <list> - -// template <class T, class Alloc> -// void swap(list<T,Alloc>& x, list<T,Alloc>& y); - -#if _LIBCPP_DEBUG >= 1 -#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(0)) -#endif - -#include <list> -#include <cassert> - -#include <__debug> -#include "min_allocator.h" - -int main() -{ -#if _LIBCPP_DEBUG >= 1 - { - int a1[] = {1, 3, 7, 9, 10}; - int a2[] = {0, 2, 4, 5, 6, 8, 11}; - std::list<int> c1(a1, a1+sizeof(a1)/sizeof(a1[0])); - std::list<int> c2(a2, a2+sizeof(a2)/sizeof(a2[0])); - std::list<int>::iterator i1 = c1.begin(); - std::list<int>::iterator i2 = c2.begin(); - swap(c1, c2); - c1.erase(i2); - c2.erase(i1); - std::list<int>::iterator j = i1; - c1.erase(i1); - assert(false); - } -#if __cplusplus >= 201103L - { - int a1[] = {1, 3, 7, 9, 10}; - int a2[] = {0, 2, 4, 5, 6, 8, 11}; - std::list<int, min_allocator<int>> c1(a1, a1+sizeof(a1)/sizeof(a1[0])); - std::list<int, min_allocator<int>> c2(a2, a2+sizeof(a2)/sizeof(a2[0])); - std::list<int, min_allocator<int>>::iterator i1 = c1.begin(); - std::list<int, min_allocator<int>>::iterator i2 = c2.begin(); - swap(c1, c2); - c1.erase(i2); - c2.erase(i1); - std::list<int, min_allocator<int>>::iterator j = i1; - c1.erase(i1); - assert(false); - } -#endif -#endif -} diff --git a/libcxx/test/std/containers/unord/next_prime.pass.cpp b/libcxx/test/std/containers/unord/next_prime.pass.cpp deleted file mode 100644 index 266d7f1f9d1..00000000000 --- a/libcxx/test/std/containers/unord/next_prime.pass.cpp +++ /dev/null @@ -1,51 +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. -// -//===----------------------------------------------------------------------===// -// -// REQUIRES: long_tests - -// Not a portable test - -// <__hash_table> - -// size_t __next_prime(size_t n); - -// If n == 0, return 0, else return the lowest prime greater than or equal to n - -#include <__hash_table> -#include <cassert> - -bool -is_prime(size_t n) -{ - switch (n) - { - case 0: - case 1: - return false; - } - for (size_t i = 2; i*i <= n; ++i) - { - if (n % i == 0) - return false; - } - return true; -} - -int main() -{ - assert(std::__next_prime(0) == 0); - for (std::size_t n = 1; n <= 100000; ++n) - { - std::size_t p = std::__next_prime(n); - assert(p >= n); - for (std::size_t i = n; i < p; ++i) - assert(!is_prime(i)); - assert(is_prime(p)); - } -} diff --git a/libcxx/test/std/containers/unord/unord.map/db_iterators_7.pass.cpp b/libcxx/test/std/containers/unord/unord.map/db_iterators_7.pass.cpp deleted file mode 100644 index b8db0a35ffc..00000000000 --- a/libcxx/test/std/containers/unord/unord.map/db_iterators_7.pass.cpp +++ /dev/null @@ -1,60 +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. -// -//===----------------------------------------------------------------------===// - -// <unordered_map> - -// Increment iterator past end. - -#if _LIBCPP_DEBUG >= 1 - -#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(0)) - -#include <unordered_map> -#include <string> -#include <cassert> -#include <iterator> -#include <exception> -#include <cstdlib> - -#include "min_allocator.h" - -int main() -{ - { - typedef std::unordered_map<int, std::string> C; - C c; - c.insert(std::make_pair(1, "one")); - C::iterator i = c.begin(); - ++i; - assert(i == c.end()); - ++i; - assert(false); - } -#if __cplusplus >= 201103L - { - typedef std::unordered_map<int, std::string, std::hash<int>, std::equal_to<int>, - min_allocator<std::pair<const int, std::string>>> C; - C c; - c.insert(std::make_pair(1, "one")); - C::iterator i = c.begin(); - ++i; - assert(i == c.end()); - ++i; - assert(false); - } -#endif -} - -#else - -int main() -{ -} - -#endif diff --git a/libcxx/test/std/containers/unord/unord.map/db_iterators_8.pass.cpp b/libcxx/test/std/containers/unord/unord.map/db_iterators_8.pass.cpp deleted file mode 100644 index c923dd77862..00000000000 --- a/libcxx/test/std/containers/unord/unord.map/db_iterators_8.pass.cpp +++ /dev/null @@ -1,56 +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. -// -//===----------------------------------------------------------------------===// - -// <unordered_map> - -// Dereference non-dereferenceable iterator. - -#if _LIBCPP_DEBUG >= 1 - -#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(0)) - -#include <unordered_map> -#include <string> -#include <cassert> -#include <iterator> -#include <exception> -#include <cstdlib> - -#include "min_allocator.h" - -int main() -{ - { - typedef std::unordered_map<int, std::string> C; - C c; - c.insert(std::make_pair(1, "one")); - C::iterator i = c.end(); - C::value_type j = *i; - assert(false); - } -#if __cplusplus >= 201103L - { - typedef std::unordered_map<int, std::string, std::hash<int>, std::equal_to<int>, - min_allocator<std::pair<const int, std::string>>> C; - C c; - c.insert(std::make_pair(1, "one")); - C::iterator i = c.end(); - C::value_type j = *i; - assert(false); - } -#endif -} - -#else - -int main() -{ -} - -#endif diff --git a/libcxx/test/std/containers/unord/unord.map/db_local_iterators_7.pass.cpp b/libcxx/test/std/containers/unord/unord.map/db_local_iterators_7.pass.cpp deleted file mode 100644 index fa1886bfff1..00000000000 --- a/libcxx/test/std/containers/unord/unord.map/db_local_iterators_7.pass.cpp +++ /dev/null @@ -1,57 +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. -// -//===----------------------------------------------------------------------===// - -// <unordered_map> - -// Increment local_iterator past end. - -#if _LIBCPP_DEBUG >= 1 - -#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(0)) - -#include <unordered_map> -#include <string> -#include <cassert> -#include <iterator> -#include <exception> -#include <cstdlib> - -#include "min_allocator.h" - -int main() -{ - { - typedef std::unordered_map<int, std::string> C; - C c(1); - C::local_iterator i = c.begin(0); - ++i; - ++i; - assert(false); - } -#if __cplusplus >= 201103L - { - typedef std::unordered_map<int, std::string, std::hash<int>, std::equal_to<int>, - min_allocator<std::pair<const int, std::string>>> C; - C c(1); - C::local_iterator i = c.begin(0); - ++i; - ++i; - assert(false); - } -#endif - -} - -#else - -int main() -{ -} - -#endif diff --git a/libcxx/test/std/containers/unord/unord.map/db_local_iterators_8.pass.cpp b/libcxx/test/std/containers/unord/unord.map/db_local_iterators_8.pass.cpp deleted file mode 100644 index 4b071cad7b4..00000000000 --- a/libcxx/test/std/containers/unord/unord.map/db_local_iterators_8.pass.cpp +++ /dev/null @@ -1,54 +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. -// -//===----------------------------------------------------------------------===// - -// <unordered_map> - -// Dereference non-dereferenceable iterator. - -#if _LIBCPP_DEBUG >= 1 - -#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(0)) - -#include <unordered_map> -#include <string> -#include <cassert> -#include <iterator> -#include <exception> -#include <cstdlib> - -#include "min_allocator.h" - -int main() -{ - { - typedef std::unordered_map<int, std::string> C; - C c(1); - C::local_iterator i = c.end(0); - C::value_type j = *i; - assert(false); - } -#if __cplusplus >= 201103L - { - typedef std::unordered_map<int, std::string, std::hash<int>, std::equal_to<int>, - min_allocator<std::pair<const int, std::string>>> C; - C c(1); - C::local_iterator i = c.end(0); - C::value_type j = *i; - assert(false); - } -#endif -} - -#else - -int main() -{ -} - -#endif diff --git a/libcxx/test/std/containers/unord/unord.map/unord.map.modifiers/try.emplace.pass.cpp b/libcxx/test/std/containers/unord/unord.map/unord.map.modifiers/try.emplace.pass.cpp index eabcf2e85db..adc4d6944ec 100644 --- a/libcxx/test/std/containers/unord/unord.map/unord.map.modifiers/try.emplace.pass.cpp +++ b/libcxx/test/std/containers/unord/unord.map/unord.map.modifiers/try.emplace.pass.cpp @@ -22,7 +22,6 @@ // template <class... Args> // iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args); // C++17 -#include <__config> #include <unordered_map> #include <cassert> #include <tuple> diff --git a/libcxx/test/std/numerics/rand/rand.dis/rand.dist.samp/rand.dist.samp.pconst/eval_param.pass.cpp b/libcxx/test/std/numerics/rand/rand.dis/rand.dist.samp/rand.dist.samp.pconst/eval_param.pass.cpp index 6850115875b..12b2f6b6485 100644 --- a/libcxx/test/std/numerics/rand/rand.dis/rand.dist.samp/rand.dist.samp.pconst/eval_param.pass.cpp +++ b/libcxx/test/std/numerics/rand/rand.dis/rand.dist.samp/rand.dist.samp.pconst/eval_param.pass.cpp @@ -17,6 +17,7 @@ // template<class _URNG> result_type operator()(_URNG& g, const param_type& parm); #include <random> +#include <algorithm> #include <vector> #include <iterator> #include <numeric> diff --git a/libcxx/test/std/numerics/rand/rand.dis/rand.dist.samp/rand.dist.samp.plinear/eval.pass.cpp b/libcxx/test/std/numerics/rand/rand.dis/rand.dist.samp/rand.dist.samp.plinear/eval.pass.cpp index af75fce512e..9606f96f911 100644 --- a/libcxx/test/std/numerics/rand/rand.dis/rand.dist.samp/rand.dist.samp.plinear/eval.pass.cpp +++ b/libcxx/test/std/numerics/rand/rand.dis/rand.dist.samp/rand.dist.samp.plinear/eval.pass.cpp @@ -19,6 +19,7 @@ #include <iostream> #include <random> +#include <algorithm> #include <vector> #include <iterator> #include <numeric> diff --git a/libcxx/test/std/utilities/tuple/tuple.tuple/tuple.elem/tuple.by.type.pass.cpp b/libcxx/test/std/utilities/tuple/tuple.tuple/tuple.elem/tuple.by.type.pass.cpp index b661a78de8d..01ee1ca1f43 100644 --- a/libcxx/test/std/utilities/tuple/tuple.tuple/tuple.elem/tuple.by.type.pass.cpp +++ b/libcxx/test/std/utilities/tuple/tuple.tuple/tuple.elem/tuple.by.type.pass.cpp @@ -11,6 +11,7 @@ #include <tuple> #include <utility> +#include <memory> #include <string> #include <complex> #include <type_traits> |
