neptards
/
libcxx_old
Archived
Code Issues Pull Requests Releases Wiki Activity
You cannot select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
This repo is archived. You can view files and clone it, but cannot push or open issues/pull-requests.
libshit-vita
master
release_80
release_70
release_60
release_50
release_40
release_39
release_38
release_37
release_36
svn-tags/RELEASE_360
svn-tags/RELEASE_351
svn-tags/RELEASE_350
release_35
release_350
svn-tags/RELEASE_35
svn-tags/RELEASE_342
svn-tags/RELEASE_34
release_34
svn-tags/RELEASE_33
release_33
release_32
apple
svn-tags/RELEASE_30
release_30
svn-tags/libcpp-31
svn-tags/libcpp-30
svn-tags/libcpp-29
svn-tags/libcpp-28
svn-tags/libcpp-27
svn-tags/libcpp-26
svn-tags/libcpp-25.1
apple25
svn-tags/libcpp-25
svn-tags/libcpp-24
svn-tags/libcpp-23.1
svn-tags/libcpp-23
svn-tags/libcpp-22
svn-tags/libcpp-21
svn-tags/libcpp-20
svn-tags/libcpp-19
svn-tags/libcpp-18
svn-tags/libcpp-17
svn-tags/libcpp-16
svn-tags/libcpp-15
svn-tags/libcpp-14
svn-tags/libcpp-13
svn-tags/libcpp-12
svn-tags/libcpp-11
svn-tags/libcpp-10
svn-tags/libcpp-9
svn-tags/libcpp-8.1
svn-tags/libcpp-8
svn-tags/libcpp-7
svn-tags/libcpp-6
svn-tags/libcpp-5
svn-tags/libcpp-4
Branches Tags
${ item.name }
Create tag ${ searchTerm }
Create branch ${ searchTerm }
from 'master'
${ noResults }
libcxx_old/test/libcxx/containers/associative/tree_remove.pass.cpp

1655 lines
39 KiB
C++
Raw Permalink Blame History

//===----------------------------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
// Not a portable test
// Returns __tree_next(__z)
// template <class _NodePtr>
// void
// __tree_remove(_NodePtr __root, _NodePtr __z)
#include <__tree>
#include <cassert>
#include "test_macros.h"
struct Node
{
Node* __left_;
Node* __right_;
Node* __parent_;
bool __is_black_;
Node* __parent_unsafe() const { return __parent_; }
void __set_parent(Node* x) { __parent_ = x;}
Node() : __left_(), __right_(), __parent_(), __is_black_() {}
};
void
test1()
{
{
// 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(int, char**)
{
test1();
test2();
test3();
test4();
return 0;
}
Reference in New Issue View Git Blame Copy Permalink