diff options
| author | Nikolas Klauser <nikolasklauser@berlin.de> | 2025-06-09 18:17:31 +0200 |
|---|---|---|
| committer | Nikolas Klauser <nikolasklauser@berlin.de> | 2025-09-15 13:06:05 +0200 |
| commit | 6fc41ee338dde1faf1fdd2a2df78b99221d94d53 (patch) | |
| tree | 1a1107bde4ab2edea7a48ec65b05b681e19eef1e | |
| parent | 5926cdffc062593ab00e66365f8ffb513e724e38 (diff) | |
| download | llvm-users/philnik777/tree_node_base_accessor_functions.zip llvm-users/philnik777/tree_node_base_accessor_functions.tar.gz llvm-users/philnik777/tree_node_base_accessor_functions.tar.bz2 | |
[libc++] Add accessor functions to __tree_node_baseusers/philnik777/tree_node_base_accessor_functions
5 files changed, 644 insertions, 617 deletions
diff --git a/libcxx/include/__tree b/libcxx/include/__tree index 61c910c..a829e71 100644 --- a/libcxx/include/__tree +++ b/libcxx/include/__tree @@ -86,6 +86,11 @@ class __tree_node; template <class _Key, class _Value> struct __value_type; +enum class __tree_color : bool { + __red = false, + __black = true, +}; + /* _NodePtr algorithms @@ -111,7 +116,7 @@ __root, have a non-null __parent_ field. // Precondition: __x != nullptr. template <class _NodePtr> inline _LIBCPP_HIDE_FROM_ABI bool __tree_is_left_child(_NodePtr __x) _NOEXCEPT { - return __x == __x->__parent_->__left_; + return __x == __x->__get_parent()->__left_; } // Determines if the subtree rooted at __x is a proper red black subtree. If @@ -119,6 +124,8 @@ inline _LIBCPP_HIDE_FROM_ABI bool __tree_is_left_child(_NodePtr __x) _NOEXCEPT { // __x is an improper subtree, returns 0. template <class _NodePtr> unsigned __tree_sub_invariant(_NodePtr __x) { + using enum __tree_color; + if (__x == nullptr) return 1; // parent consistency checked by caller @@ -132,10 +139,10 @@ unsigned __tree_sub_invariant(_NodePtr __x) { if (__x->__left_ == __x->__right_ && __x->__left_ != nullptr) return 0; // If this is red, neither child can be red - if (!__x->__is_black_) { - if (__x->__left_ && !__x->__left_->__is_black_) + if (__x->__color_ == __red) { + if (__x->__left_ && __x->__left_->__color_ == __red) return 0; - if (__x->__right_ && !__x->__right_->__is_black_) + if (__x->__right_ && __x->__right_->__color_ == __red) return 0; } unsigned __h = std::__tree_sub_invariant(__x->__left_); @@ -143,7 +150,7 @@ unsigned __tree_sub_invariant(_NodePtr __x) { return 0; // invalid left subtree if (__h != std::__tree_sub_invariant(__x->__right_)) return 0; // invalid or different height right subtree - return __h + __x->__is_black_; // return black height of this node + return __h + (__x->__color_ == __black ? 1 : 0); // return black height of this node } // Determines if the red black tree rooted at __root is a proper red black tree. @@ -159,7 +166,7 @@ _LIBCPP_HIDE_FROM_ABI bool __tree_invariant(_NodePtr __root) { if (!std::__tree_is_left_child(__root)) return false; // root must be black - if (!__root->__is_black_) + if (__root->__color_ == __tree_color::__red) return false; // do normal node checks return std::__tree_sub_invariant(__root) != 0; @@ -206,7 +213,7 @@ inline _LIBCPP_HIDE_FROM_ABI _EndNodePtr __tree_next_iter(_NodePtr __x) _NOEXCEP return static_cast<_EndNodePtr>(std::__tree_min(__x->__right_)); while (!std::__tree_is_left_child(__x)) __x = __x->__parent_unsafe(); - return static_cast<_EndNodePtr>(__x->__parent_); + return static_cast<_EndNodePtr>(__x->__get_parent()); } // Returns: pointer to the previous in-order node before __x. @@ -250,9 +257,9 @@ _LIBCPP_HIDE_FROM_ABI void __tree_left_rotate(_NodePtr __x) _NOEXCEPT { __x->__right_ = __y->__left_; if (__x->__right_ != nullptr) __x->__right_->__set_parent(__x); - __y->__parent_ = __x->__parent_; + __y->__set_parent(__x->__get_parent()); if (std::__tree_is_left_child(__x)) - __x->__parent_->__left_ = __y; + __x->__get_parent()->__left_ = __y; else __x->__parent_unsafe()->__right_ = __y; __y->__left_ = __x; @@ -269,9 +276,9 @@ _LIBCPP_HIDE_FROM_ABI void __tree_right_rotate(_NodePtr __x) _NOEXCEPT { __x->__left_ = __y->__right_; if (__x->__left_ != nullptr) __x->__left_->__set_parent(__x); - __y->__parent_ = __x->__parent_; + __y->__set_parent(__x->__get_parent()); if (std::__tree_is_left_child(__x)) - __x->__parent_->__left_ = __y; + __x->__get_parent()->__left_ = __y; else __x->__parent_unsafe()->__right_ = __y; __y->__right_ = __x; @@ -289,46 +296,47 @@ template <class _NodePtr> _LIBCPP_HIDE_FROM_ABI void __tree_balance_after_insert(_NodePtr __root, _NodePtr __x) _NOEXCEPT { _LIBCPP_ASSERT_INTERNAL(__root != nullptr, "Root of the tree shouldn't be null"); _LIBCPP_ASSERT_INTERNAL(__x != nullptr, "Can't attach null node to a leaf"); - __x->__is_black_ = __x == __root; - while (__x != __root && !__x->__parent_unsafe()->__is_black_) { - // __x->__parent_ != __root because __x->__parent_->__is_black == false + using enum __tree_color; + __x->__set_color(__x == __root ? __black : __red); + while (__x != __root && __x->__parent_unsafe()->__get_color() == __red) { + // __x->__parent_ != __root because __x->__parent_->__get_color() == __red if (std::__tree_is_left_child(__x->__parent_unsafe())) { _NodePtr __y = __x->__parent_unsafe()->__parent_unsafe()->__right_; - if (__y != nullptr && !__y->__is_black_) { - __x = __x->__parent_unsafe(); - __x->__is_black_ = true; - __x = __x->__parent_unsafe(); - __x->__is_black_ = __x == __root; - __y->__is_black_ = true; + if (__y != nullptr && __y->__get_color() == __red) { + __x = __x->__parent_unsafe(); + __x->__set_color(__black); + __x = __x->__parent_unsafe(); + __x->__set_color(__x == __root ? __black : __red); + __y->__set_color(__black); } else { if (!std::__tree_is_left_child(__x)) { __x = __x->__parent_unsafe(); std::__tree_left_rotate(__x); } - __x = __x->__parent_unsafe(); - __x->__is_black_ = true; - __x = __x->__parent_unsafe(); - __x->__is_black_ = false; + __x = __x->__parent_unsafe(); + __x->__set_color(__black); + __x = __x->__parent_unsafe(); + __x->__set_color(__red); std::__tree_right_rotate(__x); break; } } else { - _NodePtr __y = __x->__parent_unsafe()->__parent_->__left_; - if (__y != nullptr && !__y->__is_black_) { - __x = __x->__parent_unsafe(); - __x->__is_black_ = true; - __x = __x->__parent_unsafe(); - __x->__is_black_ = __x == __root; - __y->__is_black_ = true; + _NodePtr __y = __x->__parent_unsafe()->__get_parent()->__left_; + if (__y != nullptr && __y->__get_color() == __red) { + __x = __x->__parent_unsafe(); + __x->__set_color(__black); + __x = __x->__parent_unsafe(); + __x->__set_color(__x == __root ? __black : __red); + __y->__set_color(__black); } else { if (std::__tree_is_left_child(__x)) { __x = __x->__parent_unsafe(); std::__tree_right_rotate(__x); } - __x = __x->__parent_unsafe(); - __x->__is_black_ = true; - __x = __x->__parent_unsafe(); - __x->__is_black_ = false; + __x = __x->__parent_unsafe(); + __x->__set_color(__black); + __x = __x->__parent_unsafe(); + __x->__set_color(__red); std::__tree_left_rotate(__x); break; } @@ -346,6 +354,9 @@ _LIBCPP_HIDE_FROM_ABI void __tree_remove(_NodePtr __root, _NodePtr __z) _NOEXCEP _LIBCPP_ASSERT_INTERNAL(__root != nullptr, "Root node should not be null"); _LIBCPP_ASSERT_INTERNAL(__z != nullptr, "The node to remove should not be null"); _LIBCPP_ASSERT_INTERNAL(std::__tree_invariant(__root), "The tree invariants should hold"); + + using enum __tree_color; + // __z will be removed from the tree. Client still needs to destruct/deallocate it // __y is either __z, or if __z has two children, __tree_next(__z). // __y will have at most one child. @@ -357,9 +368,9 @@ _LIBCPP_HIDE_FROM_ABI void __tree_remove(_NodePtr __root, _NodePtr __z) _NOEXCEP _NodePtr __w = nullptr; // link __x to __y's parent, and find __w if (__x != nullptr) - __x->__parent_ = __y->__parent_; + __x->__set_parent(__y->__get_parent()); if (std::__tree_is_left_child(__y)) { - __y->__parent_->__left_ = __x; + __y->__get_parent()->__left_ = __x; if (__y != __root) __w = __y->__parent_unsafe()->__right_; else @@ -367,16 +378,16 @@ _LIBCPP_HIDE_FROM_ABI void __tree_remove(_NodePtr __root, _NodePtr __z) _NOEXCEP } else { __y->__parent_unsafe()->__right_ = __x; // __y can't be root if it is a right child - __w = __y->__parent_->__left_; + __w = __y->__get_parent()->__left_; } - bool __removed_black = __y->__is_black_; + bool __removed_black = __y->__get_color() == __black; // If we didn't remove __z, do so now by splicing in __y for __z, // but copy __z's color. This does not impact __x or __w. if (__y != __z) { // __z->__left_ != nulptr but __z->__right_ might == __x == nullptr - __y->__parent_ = __z->__parent_; + __y->__set_parent(__z->__get_parent()); if (std::__tree_is_left_child(__z)) - __y->__parent_->__left_ = __y; + __y->__get_parent()->__left_ = __y; else __y->__parent_unsafe()->__right_ = __y; __y->__left_ = __z->__left_; @@ -384,7 +395,7 @@ _LIBCPP_HIDE_FROM_ABI void __tree_remove(_NodePtr __root, _NodePtr __z) _NOEXCEP __y->__right_ = __z->__right_; if (__y->__right_ != nullptr) __y->__right_->__set_parent(__y); - __y->__is_black_ = __z->__is_black_; + __y->__set_color(__z->__get_color()); if (__root == __z) __root = __y; } @@ -404,7 +415,7 @@ _LIBCPP_HIDE_FROM_ABI void __tree_remove(_NodePtr __root, _NodePtr __z) _NOEXCEP // different black heights under left and right pointers. // if (__x == __root || __x != nullptr && !__x->__is_black_) if (__x != nullptr) - __x->__is_black_ = true; + __x->__set_color(__black); else { // Else __x isn't root, and is "doubly black", even though it may // be null. __w can not be null here, else the parent would @@ -414,9 +425,9 @@ _LIBCPP_HIDE_FROM_ABI void __tree_remove(_NodePtr __root, _NodePtr __z) _NOEXCEP while (true) { if (!std::__tree_is_left_child(__w)) // if x is left child { - if (!__w->__is_black_) { - __w->__is_black_ = true; - __w->__parent_unsafe()->__is_black_ = false; + if (__w->__get_color() == __red) { + __w->__set_color(__black); + __w->__parent_unsafe()->__set_color(__red); std::__tree_left_rotate(__w->__parent_unsafe()); // __x is still valid // reset __root only if necessary @@ -426,40 +437,40 @@ _LIBCPP_HIDE_FROM_ABI void __tree_remove(_NodePtr __root, _NodePtr __z) _NOEXCEP __w = __w->__left_->__right_; } // __w->__is_black_ is now true, __w may have null children - if ((__w->__left_ == nullptr || __w->__left_->__is_black_) && - (__w->__right_ == nullptr || __w->__right_->__is_black_)) { - __w->__is_black_ = false; - __x = __w->__parent_unsafe(); + if ((__w->__left_ == nullptr || __w->__left_->__get_color() == __black) && + (__w->__right_ == nullptr || __w->__right_->__get_color() == __black)) { + __w->__set_color(__red); + __x = __w->__parent_unsafe(); // __x can no longer be null - if (__x == __root || !__x->__is_black_) { - __x->__is_black_ = true; + if (__x == __root || __x->__get_color() == __red) { + __x->__set_color(__black); break; } // reset sibling, and it still can't be null - __w = std::__tree_is_left_child(__x) ? __x->__parent_unsafe()->__right_ : __x->__parent_->__left_; + __w = std::__tree_is_left_child(__x) ? __x->__parent_unsafe()->__right_ : __x->__get_parent()->__left_; // continue; } else // __w has a red child { - if (__w->__right_ == nullptr || __w->__right_->__is_black_) { + if (__w->__right_ == nullptr || __w->__right_->__get_color() == __black) { // __w left child is non-null and red - __w->__left_->__is_black_ = true; - __w->__is_black_ = false; + __w->__left_->__set_color(__black); + __w->__set_color(__red); std::__tree_right_rotate(__w); // __w is known not to be root, so root hasn't changed // reset sibling, and it still can't be null __w = __w->__parent_unsafe(); } // __w has a right red child, left child may be null - __w->__is_black_ = __w->__parent_unsafe()->__is_black_; - __w->__parent_unsafe()->__is_black_ = true; - __w->__right_->__is_black_ = true; + __w->__set_color(__w->__parent_unsafe()->__get_color()); + __w->__parent_unsafe()->__set_color(__black); + __w->__right_->__set_color(__black); std::__tree_left_rotate(__w->__parent_unsafe()); break; } } else { - if (!__w->__is_black_) { - __w->__is_black_ = true; - __w->__parent_unsafe()->__is_black_ = false; + if (__w->__get_color() == __red) { + __w->__set_color(__black); + __w->__parent_unsafe()->__set_color(__red); std::__tree_right_rotate(__w->__parent_unsafe()); // __x is still valid // reset __root only if necessary @@ -469,33 +480,33 @@ _LIBCPP_HIDE_FROM_ABI void __tree_remove(_NodePtr __root, _NodePtr __z) _NOEXCEP __w = __w->__right_->__left_; } // __w->__is_black_ is now true, __w may have null children - if ((__w->__left_ == nullptr || __w->__left_->__is_black_) && - (__w->__right_ == nullptr || __w->__right_->__is_black_)) { - __w->__is_black_ = false; - __x = __w->__parent_unsafe(); + if ((__w->__left_ == nullptr || __w->__left_->__get_color() == __black) && + (__w->__right_ == nullptr || __w->__right_->__get_color() == __black)) { + __w->__set_color(__red); + __x = __w->__parent_unsafe(); // __x can no longer be null - if (!__x->__is_black_ || __x == __root) { - __x->__is_black_ = true; + if (__x->__get_color() == __red || __x == __root) { + __x->__set_color(__black); break; } // reset sibling, and it still can't be null - __w = std::__tree_is_left_child(__x) ? __x->__parent_unsafe()->__right_ : __x->__parent_->__left_; + __w = std::__tree_is_left_child(__x) ? __x->__parent_unsafe()->__right_ : __x->__get_parent()->__left_; // continue; } else // __w has a red child { - if (__w->__left_ == nullptr || __w->__left_->__is_black_) { + if (__w->__left_ == nullptr || __w->__left_->__get_color() == __black) { // __w right child is non-null and red - __w->__right_->__is_black_ = true; - __w->__is_black_ = false; + __w->__right_->__set_color(__black); + __w->__set_color(__red); std::__tree_left_rotate(__w); // __w is known not to be root, so root hasn't changed // reset sibling, and it still can't be null __w = __w->__parent_unsafe(); } // __w has a left red child, right child may be null - __w->__is_black_ = __w->__parent_unsafe()->__is_black_; - __w->__parent_unsafe()->__is_black_ = true; - __w->__left_->__is_black_ = true; + __w->__set_color(__w->__parent_unsafe()->__get_color()); + __w->__parent_unsafe()->__set_color(__black); + __w->__left_->__set_color(__black); std::__tree_right_rotate(__w->__parent_unsafe()); break; } @@ -567,12 +578,19 @@ public: using __end_node_pointer _LIBCPP_NODEBUG = __rebind_pointer_t<_VoidPtr, __tree_end_node<pointer> >; pointer __right_; + +private: __end_node_pointer __parent_; - bool __is_black_; + __tree_color __color_; +public: _LIBCPP_HIDE_FROM_ABI pointer __parent_unsafe() const { return static_cast<pointer>(__parent_); } _LIBCPP_HIDE_FROM_ABI void __set_parent(pointer __p) { __parent_ = static_cast<__end_node_pointer>(__p); } + _LIBCPP_HIDE_FROM_ABI void __set_parent(__end_node_pointer __p) { __parent_ = __p; } + _LIBCPP_HIDE_FROM_ABI __end_node_pointer __get_parent() const { return __parent_; } + _LIBCPP_HIDE_FROM_ABI __tree_color __get_color() const { return __color_; } + _LIBCPP_HIDE_FROM_ABI void __set_color(__tree_color __color) { __color_ = __color; } _LIBCPP_HIDE_FROM_ABI __tree_node_base() = default; __tree_node_base(__tree_node_base const&) = delete; @@ -1295,8 +1313,8 @@ private: _LIBCPP_HIDE_FROM_ABI ~_DetachedTreeCache() { __t_->destroy(__cache_elem_); if (__cache_root_) { - while (__cache_root_->__parent_ != nullptr) - __cache_root_ = static_cast<__node_pointer>(__cache_root_->__parent_); + while (__cache_root_->__get_parent() != nullptr) + __cache_root_ = static_cast<__node_pointer>(__cache_root_->__get_parent()); __t_->destroy(__cache_root_); } } @@ -1360,13 +1378,13 @@ private: __node_pointer __new_node_ptr = __new_node.release(); - __new_node_ptr->__is_black_ = __src->__is_black_; - __new_node_ptr->__left_ = static_cast<__node_base_pointer>(__left.release()); - __new_node_ptr->__right_ = static_cast<__node_base_pointer>(__right); + __new_node_ptr->__set_color(__src->__get_color()); + __new_node_ptr->__left_ = static_cast<__node_base_pointer>(__left.release()); + __new_node_ptr->__right_ = static_cast<__node_base_pointer>(__right); if (__new_node_ptr->__left_) - __new_node_ptr->__left_->__parent_ = static_cast<__end_node_pointer>(__new_node_ptr); + __new_node_ptr->__left_->__set_parent(static_cast<__end_node_pointer>(__new_node_ptr)); if (__new_node_ptr->__right_) - __new_node_ptr->__right_->__parent_ = static_cast<__end_node_pointer>(__new_node_ptr); + __new_node_ptr->__right_->__set_parent(static_cast<__end_node_pointer>(__new_node_ptr)); return __new_node_ptr; } @@ -1384,7 +1402,7 @@ private: } __assign_value(__dest->__get_value(), __src->__get_value()); - __dest->__is_black_ = __src->__is_black_; + __dest->__set_color(__src->__get_color()); // If we already have a left node in the destination tree, reuse it and copy-assign recursively if (__dest->__left_) { @@ -1393,9 +1411,9 @@ private: // Otherwise, we must create new nodes; copy-construct from here on } else if (__src->__left_) { - auto __new_left = __copy_construct_tree(static_cast<__node_pointer>(__src->__left_)); - __dest->__left_ = static_cast<__node_base_pointer>(__new_left); - __new_left->__parent_ = static_cast<__end_node_pointer>(__dest); + auto __new_left = __copy_construct_tree(static_cast<__node_pointer>(__src->__left_)); + __dest->__left_ = static_cast<__node_base_pointer>(__new_left); + __new_left->__set_parent(static_cast<__end_node_pointer>(__dest)); } // Identical to the left case above, just for the right nodes @@ -1403,9 +1421,9 @@ private: __dest->__right_ = static_cast<__node_base_pointer>(__copy_assign_tree( static_cast<__node_pointer>(__dest->__right_), static_cast<__node_pointer>(__src->__right_))); } else if (__src->__right_) { - auto __new_right = __copy_construct_tree(static_cast<__node_pointer>(__src->__right_)); - __dest->__right_ = static_cast<__node_base_pointer>(__new_right); - __new_right->__parent_ = static_cast<__end_node_pointer>(__dest); + auto __new_right = __copy_construct_tree(static_cast<__node_pointer>(__src->__right_)); + __dest->__right_ = static_cast<__node_base_pointer>(__new_right); + __new_right->__set_parent(static_cast<__end_node_pointer>(__dest)); } return __dest; @@ -1416,11 +1434,11 @@ private: template <class _Tp, class _Compare, class _Allocator> typename __tree<_Tp, _Compare, _Allocator>::__node_pointer __tree<_Tp, _Compare, _Allocator>::_DetachedTreeCache::__detach_from_tree(__tree* __t) _NOEXCEPT { - __node_pointer __cache = static_cast<__node_pointer>(__t->__begin_node_); - __t->__begin_node_ = __t->__end_node(); - __t->__end_node()->__left_->__parent_ = nullptr; - __t->__end_node()->__left_ = nullptr; - __t->__size_ = 0; + __node_pointer __cache = static_cast<__node_pointer>(__t->__begin_node_); + __t->__begin_node_ = __t->__end_node(); + __t->__end_node()->__left_->__set_parent(__parent_pointer(nullptr)); + __t->__end_node()->__left_ = nullptr; + __t->__size_ = 0; // __cache->__left_ == nullptr if (__cache->__right_ != nullptr) __cache = static_cast<__node_pointer>(__cache->__right_); @@ -1436,18 +1454,18 @@ __tree<_Tp, _Compare, _Allocator>::_DetachedTreeCache::__detach_from_tree(__tree template <class _Tp, class _Compare, class _Allocator> typename __tree<_Tp, _Compare, _Allocator>::__node_pointer __tree<_Tp, _Compare, _Allocator>::_DetachedTreeCache::__detach_next(__node_pointer __cache) _NOEXCEPT { - if (__cache->__parent_ == nullptr) + if (__cache->__get_parent() == nullptr) return nullptr; if (std::__tree_is_left_child(static_cast<__node_base_pointer>(__cache))) { - __cache->__parent_->__left_ = nullptr; - __cache = static_cast<__node_pointer>(__cache->__parent_); + __cache->__get_parent()->__left_ = nullptr; + __cache = static_cast<__node_pointer>(__cache->__get_parent()); if (__cache->__right_ == nullptr) return __cache; return static_cast<__node_pointer>(std::__tree_leaf(__cache->__right_)); } // __cache is right child __cache->__parent_unsafe()->__right_ = nullptr; - __cache = static_cast<__node_pointer>(__cache->__parent_); + __cache = static_cast<__node_pointer>(__cache->__get_parent()); if (__cache->__left_ == nullptr) return __cache; return static_cast<__node_pointer>(std::__tree_leaf(__cache->__left_)); @@ -1466,7 +1484,7 @@ __tree<_Tp, _Compare, _Allocator>& __tree<_Tp, _Compare, _Allocator>::operator=( } else { *__root_ptr() = static_cast<__node_base_pointer>(__copy_construct_tree(__t.__root())); if (__root()) - __root()->__parent_ = __end_node(); + __root()->__set_parent(__end_node()); } __begin_node_ = __end_node()->__left_ ? static_cast<__end_node_pointer>(std::__tree_min(__end_node()->__left_)) : __end_node(); @@ -1525,7 +1543,7 @@ __tree<_Tp, _Compare, _Allocator>::__tree(const __tree& __t) return; *__root_ptr() = static_cast<__node_base_pointer>(__copy_construct_tree(__t.__root())); - __root()->__parent_ = __end_node(); + __root()->__set_parent(__end_node()); __begin_node_ = static_cast<__end_node_pointer>(std::__tree_min(__end_node()->__left_)); __size_ = __t.size(); } @@ -1541,10 +1559,10 @@ __tree<_Tp, _Compare, _Allocator>::__tree(__tree&& __t) _NOEXCEPT_( if (__size_ == 0) __begin_node_ = __end_node(); else { - __end_node()->__left_->__parent_ = static_cast<__end_node_pointer>(__end_node()); - __t.__begin_node_ = __t.__end_node(); - __t.__end_node()->__left_ = nullptr; - __t.__size_ = 0; + __end_node()->__left_->__set_parent(static_cast<__end_node_pointer>(__end_node())); + __t.__begin_node_ = __t.__end_node(); + __t.__end_node()->__left_ = nullptr; + __t.__size_ = 0; } } @@ -1555,13 +1573,13 @@ __tree<_Tp, _Compare, _Allocator>::__tree(__tree&& __t, const allocator_type& __ if (__t.__size_ == 0) __begin_node_ = __end_node(); else { - __begin_node_ = __t.__begin_node_; - __end_node()->__left_ = __t.__end_node()->__left_; - __end_node()->__left_->__parent_ = static_cast<__end_node_pointer>(__end_node()); - __size_ = __t.__size_; - __t.__begin_node_ = __t.__end_node(); - __t.__end_node()->__left_ = nullptr; - __t.__size_ = 0; + __begin_node_ = __t.__begin_node_; + __end_node()->__left_ = __t.__end_node()->__left_; + __end_node()->__left_->__set_parent(static_cast<__end_node_pointer>(__end_node())); + __size_ = __t.__size_; + __t.__begin_node_ = __t.__end_node(); + __t.__end_node()->__left_ = nullptr; + __t.__size_ = 0; } } else { __begin_node_ = __end_node(); @@ -1580,10 +1598,10 @@ void __tree<_Tp, _Compare, _Allocator>::__move_assign(__tree& __t, true_type) if (__size_ == 0) __begin_node_ = __end_node(); else { - __end_node()->__left_->__parent_ = static_cast<__end_node_pointer>(__end_node()); - __t.__begin_node_ = __t.__end_node(); - __t.__end_node()->__left_ = nullptr; - __t.__size_ = 0; + __end_node()->__left_->__set_parent(static_cast<__end_node_pointer>(__end_node())); + __t.__begin_node_ = __t.__end_node(); + __t.__end_node()->__left_ = nullptr; + __t.__size_ = 0; } } @@ -1626,11 +1644,11 @@ void __tree<_Tp, _Compare, _Allocator>::swap(__tree& __t) if (__size_ == 0) __begin_node_ = __end_node(); else - __end_node()->__left_->__parent_ = __end_node(); + __end_node()->__left_->__set_parent(__end_node()); if (__t.__size_ == 0) __t.__begin_node_ = __t.__end_node(); else - __t.__end_node()->__left_->__parent_ = __t.__end_node(); + __t.__end_node()->__left_->__set_parent(static_cast<__end_node_pointer>(__t.__end_node())); } template <class _Tp, class _Compare, class _Allocator> @@ -1821,7 +1839,7 @@ void __tree<_Tp, _Compare, _Allocator>::__insert_node_at( __end_node_pointer __parent, __node_base_pointer& __child, __node_base_pointer __new_node) _NOEXCEPT { __new_node->__left_ = nullptr; __new_node->__right_ = nullptr; - __new_node->__parent_ = __parent; + __new_node->__set_parent(__parent); // __new_node->__is_black_ is initialized in __tree_balance_after_insert __child = __new_node; if (__begin_node_->__left_ != nullptr) @@ -2261,7 +2279,7 @@ __tree<_Tp, _Compare, _Allocator>::remove(const_iterator __p) _NOEXCEPT { if (__np->__right_ != nullptr) __begin_node_ = static_cast<__end_node_pointer>(__np->__right_); else - __begin_node_ = static_cast<__end_node_pointer>(__np->__parent_); + __begin_node_ = static_cast<__end_node_pointer>(__np->__get_parent()); } --__size_; std::__tree_remove(__end_node()->__left_, static_cast<__node_base_pointer>(__np)); diff --git a/libcxx/test/libcxx/containers/associative/tree_balance_after_insert.pass.cpp b/libcxx/test/libcxx/containers/associative/tree_balance_after_insert.pass.cpp index 4fb9d8e..4f5718e 100644 --- a/libcxx/test/libcxx/containers/associative/tree_balance_after_insert.pass.cpp +++ b/libcxx/test/libcxx/containers/associative/tree_balance_after_insert.pass.cpp @@ -8,7 +8,7 @@ // Not a portable test -// Precondition: __root->__is_black_ == true +// Precondition: __root->__color_ == std::__tree_color::__black // template <class _NodePtr> // void // __tree_balance_after_insert(_NodePtr __root, _NodePtr __x) @@ -22,12 +22,15 @@ struct Node { Node* __left_; Node* __right_; Node* __parent_; - bool __is_black_; + std::__tree_color __color_; Node* __parent_unsafe() const { return __parent_; } void __set_parent(Node* x) { __parent_ = x; } + Node* __get_parent() { return __parent_; } + void __set_color(std::__tree_color __color) { __color_ = __color; } + std::__tree_color __get_color() { return __color_; } - Node() : __left_(), __right_(), __parent_(), __is_black_() {} + Node() : __left_(), __right_(), __parent_(), __color_() {} }; void test1() { @@ -43,22 +46,22 @@ void test1() { c.__parent_ = &root; c.__left_ = &b; c.__right_ = &d; - c.__is_black_ = true; + c.__color_ = std::__tree_color::__black; b.__parent_ = &c; b.__left_ = &a; b.__right_ = 0; - b.__is_black_ = false; + b.__color_ = std::__tree_color::__red; d.__parent_ = &c; d.__left_ = 0; d.__right_ = 0; - d.__is_black_ = false; + d.__color_ = std::__tree_color::__red; a.__parent_ = &b; a.__left_ = 0; a.__right_ = 0; - a.__is_black_ = false; + a.__color_ = std::__tree_color::__red; std::__tree_balance_after_insert(root.__left_, &a); @@ -69,22 +72,22 @@ void test1() { assert(c.__parent_ == &root); assert(c.__left_ == &b); assert(c.__right_ == &d); - assert(c.__is_black_ == true); + assert(c.__color_ == std::__tree_color::__black); assert(b.__parent_ == &c); assert(b.__left_ == &a); assert(b.__right_ == 0); - assert(b.__is_black_ == true); + assert(b.__color_ == std::__tree_color::__black); assert(d.__parent_ == &c); assert(d.__left_ == 0); assert(d.__right_ == 0); - assert(d.__is_black_ == true); + assert(d.__color_ == std::__tree_color::__black); assert(a.__parent_ == &b); assert(a.__left_ == 0); assert(a.__right_ == 0); - assert(a.__is_black_ == false); + assert(a.__color_ == std::__tree_color::__red); } { Node root; @@ -98,22 +101,22 @@ void test1() { c.__parent_ = &root; c.__left_ = &b; c.__right_ = &d; - c.__is_black_ = true; + c.__color_ = std::__tree_color::__black; b.__parent_ = &c; b.__left_ = 0; b.__right_ = &a; - b.__is_black_ = false; + b.__color_ = std::__tree_color::__red; d.__parent_ = &c; d.__left_ = 0; d.__right_ = 0; - d.__is_black_ = false; + d.__color_ = std::__tree_color::__red; a.__parent_ = &b; a.__left_ = 0; a.__right_ = 0; - a.__is_black_ = false; + a.__color_ = std::__tree_color::__red; std::__tree_balance_after_insert(root.__left_, &a); @@ -124,22 +127,22 @@ void test1() { assert(c.__parent_ == &root); assert(c.__left_ == &b); assert(c.__right_ == &d); - assert(c.__is_black_ == true); + assert(c.__color_ == std::__tree_color::__black); assert(b.__parent_ == &c); assert(b.__left_ == 0); assert(b.__right_ == &a); - assert(b.__is_black_ == true); + assert(b.__color_ == std::__tree_color::__black); assert(d.__parent_ == &c); assert(d.__left_ == 0); assert(d.__right_ == 0); - assert(d.__is_black_ == true); + assert(d.__color_ == std::__tree_color::__black); assert(a.__parent_ == &b); assert(a.__left_ == 0); assert(a.__right_ == 0); - assert(a.__is_black_ == false); + assert(a.__color_ == std::__tree_color::__red); } { Node root; @@ -153,22 +156,22 @@ void test1() { c.__parent_ = &root; c.__left_ = &b; c.__right_ = &d; - c.__is_black_ = true; + c.__color_ = std::__tree_color::__black; b.__parent_ = &c; b.__left_ = 0; b.__right_ = 0; - b.__is_black_ = false; + b.__color_ = std::__tree_color::__red; d.__parent_ = &c; d.__left_ = &a; d.__right_ = 0; - d.__is_black_ = false; + d.__color_ = std::__tree_color::__red; a.__parent_ = &d; a.__left_ = 0; a.__right_ = 0; - a.__is_black_ = false; + a.__color_ = std::__tree_color::__red; std::__tree_balance_after_insert(root.__left_, &a); @@ -179,22 +182,22 @@ void test1() { assert(c.__parent_ == &root); assert(c.__left_ == &b); assert(c.__right_ == &d); - assert(c.__is_black_ == true); + assert(c.__color_ == std::__tree_color::__black); assert(b.__parent_ == &c); assert(b.__left_ == 0); assert(b.__right_ == 0); - assert(b.__is_black_ == true); + assert(b.__color_ == std::__tree_color::__black); assert(d.__parent_ == &c); assert(d.__left_ == &a); assert(d.__right_ == 0); - assert(d.__is_black_ == true); + assert(d.__color_ == std::__tree_color::__black); assert(a.__parent_ == &d); assert(a.__left_ == 0); assert(a.__right_ == 0); - assert(a.__is_black_ == false); + assert(a.__color_ == std::__tree_color::__red); } { Node root; @@ -208,22 +211,22 @@ void test1() { c.__parent_ = &root; c.__left_ = &b; c.__right_ = &d; - c.__is_black_ = true; + c.__color_ = std::__tree_color::__black; b.__parent_ = &c; b.__left_ = 0; b.__right_ = 0; - b.__is_black_ = false; + b.__color_ = std::__tree_color::__red; d.__parent_ = &c; d.__left_ = 0; d.__right_ = &a; - d.__is_black_ = false; + d.__color_ = std::__tree_color::__red; a.__parent_ = &d; a.__left_ = 0; a.__right_ = 0; - a.__is_black_ = false; + a.__color_ = std::__tree_color::__red; std::__tree_balance_after_insert(root.__left_, &a); @@ -234,22 +237,22 @@ void test1() { assert(c.__parent_ == &root); assert(c.__left_ == &b); assert(c.__right_ == &d); - assert(c.__is_black_ == true); + assert(c.__color_ == std::__tree_color::__black); assert(b.__parent_ == &c); assert(b.__left_ == 0); assert(b.__right_ == 0); - assert(b.__is_black_ == true); + assert(b.__color_ == std::__tree_color::__black); assert(d.__parent_ == &c); assert(d.__left_ == 0); assert(d.__right_ == &a); - assert(d.__is_black_ == true); + assert(d.__color_ == std::__tree_color::__black); assert(a.__parent_ == &d); assert(a.__left_ == 0); assert(a.__right_ == 0); - assert(a.__is_black_ == false); + assert(a.__color_ == std::__tree_color::__red); } { Node root; @@ -268,37 +271,37 @@ void test1() { c.__parent_ = &root; c.__left_ = &b; c.__right_ = &d; - c.__is_black_ = true; + c.__color_ = std::__tree_color::__black; b.__parent_ = &c; b.__left_ = &a; b.__right_ = &g; - b.__is_black_ = false; + b.__color_ = std::__tree_color::__red; d.__parent_ = &c; d.__left_ = &h; d.__right_ = &i; - d.__is_black_ = false; + d.__color_ = std::__tree_color::__red; a.__parent_ = &b; a.__left_ = &e; a.__right_ = &f; - a.__is_black_ = false; + a.__color_ = std::__tree_color::__red; e.__parent_ = &a; - e.__is_black_ = true; + e.__color_ = std::__tree_color::__black; f.__parent_ = &a; - f.__is_black_ = true; + f.__color_ = std::__tree_color::__black; g.__parent_ = &b; - g.__is_black_ = true; + g.__color_ = std::__tree_color::__black; h.__parent_ = &d; - h.__is_black_ = true; + h.__color_ = std::__tree_color::__black; i.__parent_ = &d; - i.__is_black_ = true; + i.__color_ = std::__tree_color::__black; std::__tree_balance_after_insert(root.__left_, &a); @@ -309,22 +312,22 @@ void test1() { assert(c.__parent_ == &root); assert(c.__left_ == &b); assert(c.__right_ == &d); - assert(c.__is_black_ == true); + assert(c.__color_ == std::__tree_color::__black); assert(b.__parent_ == &c); assert(b.__left_ == &a); assert(b.__right_ == &g); - assert(b.__is_black_ == true); + assert(b.__color_ == std::__tree_color::__black); assert(d.__parent_ == &c); assert(d.__left_ == &h); assert(d.__right_ == &i); - assert(d.__is_black_ == true); + assert(d.__color_ == std::__tree_color::__black); assert(a.__parent_ == &b); assert(a.__left_ == &e); assert(a.__right_ == &f); - assert(a.__is_black_ == false); + assert(a.__color_ == std::__tree_color::__red); } { Node root; @@ -343,37 +346,37 @@ void test1() { c.__parent_ = &root; c.__left_ = &b; c.__right_ = &d; - c.__is_black_ = true; + c.__color_ = std::__tree_color::__black; b.__parent_ = &c; b.__left_ = &g; b.__right_ = &a; - b.__is_black_ = false; + b.__color_ = std::__tree_color::__red; d.__parent_ = &c; d.__left_ = &h; d.__right_ = &i; - d.__is_black_ = false; + d.__color_ = std::__tree_color::__red; a.__parent_ = &b; a.__left_ = &e; a.__right_ = &f; - a.__is_black_ = false; + a.__color_ = std::__tree_color::__red; e.__parent_ = &a; - e.__is_black_ = true; + e.__color_ = std::__tree_color::__black; f.__parent_ = &a; - f.__is_black_ = true; + f.__color_ = std::__tree_color::__black; g.__parent_ = &b; - g.__is_black_ = true; + g.__color_ = std::__tree_color::__black; h.__parent_ = &d; - h.__is_black_ = true; + h.__color_ = std::__tree_color::__black; i.__parent_ = &d; - i.__is_black_ = true; + i.__color_ = std::__tree_color::__black; std::__tree_balance_after_insert(root.__left_, &a); @@ -384,22 +387,22 @@ void test1() { assert(c.__parent_ == &root); assert(c.__left_ == &b); assert(c.__right_ == &d); - assert(c.__is_black_ == true); + assert(c.__color_ == std::__tree_color::__black); assert(b.__parent_ == &c); assert(b.__left_ == &g); assert(b.__right_ == &a); - assert(b.__is_black_ == true); + assert(b.__color_ == std::__tree_color::__black); assert(d.__parent_ == &c); assert(d.__left_ == &h); assert(d.__right_ == &i); - assert(d.__is_black_ == true); + assert(d.__color_ == std::__tree_color::__black); assert(a.__parent_ == &b); assert(a.__left_ == &e); assert(a.__right_ == &f); - assert(a.__is_black_ == false); + assert(a.__color_ == std::__tree_color::__red); } { Node root; @@ -418,37 +421,37 @@ void test1() { c.__parent_ = &root; c.__left_ = &b; c.__right_ = &d; - c.__is_black_ = true; + c.__color_ = std::__tree_color::__black; b.__parent_ = &c; b.__left_ = &g; b.__right_ = &h; - b.__is_black_ = false; + b.__color_ = std::__tree_color::__red; d.__parent_ = &c; d.__left_ = &a; d.__right_ = &i; - d.__is_black_ = false; + d.__color_ = std::__tree_color::__red; a.__parent_ = &d; a.__left_ = &e; a.__right_ = &f; - a.__is_black_ = false; + a.__color_ = std::__tree_color::__red; e.__parent_ = &a; - e.__is_black_ = true; + e.__color_ = std::__tree_color::__black; f.__parent_ = &a; - f.__is_black_ = true; + f.__color_ = std::__tree_color::__black; g.__parent_ = &b; - g.__is_black_ = true; + g.__color_ = std::__tree_color::__black; h.__parent_ = &b; - h.__is_black_ = true; + h.__color_ = std::__tree_color::__black; i.__parent_ = &d; - i.__is_black_ = true; + i.__color_ = std::__tree_color::__black; std::__tree_balance_after_insert(root.__left_, &a); @@ -459,22 +462,22 @@ void test1() { assert(c.__parent_ == &root); assert(c.__left_ == &b); assert(c.__right_ == &d); - assert(c.__is_black_ == true); + assert(c.__color_ == std::__tree_color::__black); assert(b.__parent_ == &c); assert(b.__left_ == &g); assert(b.__right_ == &h); - assert(b.__is_black_ == true); + assert(b.__color_ == std::__tree_color::__black); assert(d.__parent_ == &c); assert(d.__left_ == &a); assert(d.__right_ == &i); - assert(d.__is_black_ == true); + assert(d.__color_ == std::__tree_color::__black); assert(a.__parent_ == &d); assert(a.__left_ == &e); assert(a.__right_ == &f); - assert(a.__is_black_ == false); + assert(a.__color_ == std::__tree_color::__red); } { Node root; @@ -493,37 +496,37 @@ void test1() { c.__parent_ = &root; c.__left_ = &b; c.__right_ = &d; - c.__is_black_ = true; + c.__color_ = std::__tree_color::__black; b.__parent_ = &c; b.__left_ = &g; b.__right_ = &h; - b.__is_black_ = false; + b.__color_ = std::__tree_color::__red; d.__parent_ = &c; d.__left_ = &i; d.__right_ = &a; - d.__is_black_ = false; + d.__color_ = std::__tree_color::__red; a.__parent_ = &d; a.__left_ = &e; a.__right_ = &f; - a.__is_black_ = false; + a.__color_ = std::__tree_color::__red; e.__parent_ = &a; - e.__is_black_ = true; + e.__color_ = std::__tree_color::__black; f.__parent_ = &a; - f.__is_black_ = true; + f.__color_ = std::__tree_color::__black; g.__parent_ = &b; - g.__is_black_ = true; + g.__color_ = std::__tree_color::__black; h.__parent_ = &b; - h.__is_black_ = true; + h.__color_ = std::__tree_color::__black; i.__parent_ = &d; - i.__is_black_ = true; + i.__color_ = std::__tree_color::__black; std::__tree_balance_after_insert(root.__left_, &a); @@ -534,22 +537,22 @@ void test1() { assert(c.__parent_ == &root); assert(c.__left_ == &b); assert(c.__right_ == &d); - assert(c.__is_black_ == true); + assert(c.__color_ == std::__tree_color::__black); assert(b.__parent_ == &c); assert(b.__left_ == &g); assert(b.__right_ == &h); - assert(b.__is_black_ == true); + assert(b.__color_ == std::__tree_color::__black); assert(d.__parent_ == &c); assert(d.__left_ == &i); assert(d.__right_ == &a); - assert(d.__is_black_ == true); + assert(d.__color_ == std::__tree_color::__black); assert(a.__parent_ == &d); assert(a.__left_ == &e); assert(a.__right_ == &f); - assert(a.__is_black_ == false); + assert(a.__color_ == std::__tree_color::__red); } } @@ -565,17 +568,17 @@ void test2() { c.__parent_ = &root; c.__left_ = &a; c.__right_ = 0; - c.__is_black_ = true; + c.__color_ = std::__tree_color::__black; a.__parent_ = &c; a.__left_ = 0; a.__right_ = &b; - a.__is_black_ = false; + a.__color_ = std::__tree_color::__red; b.__parent_ = &a; b.__left_ = 0; b.__right_ = 0; - b.__is_black_ = false; + b.__color_ = std::__tree_color::__red; std::__tree_balance_after_insert(root.__left_, &b); @@ -586,17 +589,17 @@ void test2() { assert(c.__parent_ == &b); assert(c.__left_ == 0); assert(c.__right_ == 0); - assert(c.__is_black_ == false); + assert(c.__color_ == std::__tree_color::__red); assert(a.__parent_ == &b); assert(a.__left_ == 0); assert(a.__right_ == 0); - assert(a.__is_black_ == false); + assert(a.__color_ == std::__tree_color::__red); assert(b.__parent_ == &root); assert(b.__left_ == &a); assert(b.__right_ == &c); - assert(b.__is_black_ == true); + assert(b.__color_ == std::__tree_color::__black); } { Node root; @@ -609,17 +612,17 @@ void test2() { a.__parent_ = &root; a.__left_ = 0; a.__right_ = &c; - a.__is_black_ = true; + a.__color_ = std::__tree_color::__black; c.__parent_ = &a; c.__left_ = &b; c.__right_ = 0; - c.__is_black_ = false; + c.__color_ = std::__tree_color::__red; b.__parent_ = &c; b.__left_ = 0; b.__right_ = 0; - b.__is_black_ = false; + b.__color_ = std::__tree_color::__red; std::__tree_balance_after_insert(root.__left_, &b); @@ -630,17 +633,17 @@ void test2() { assert(a.__parent_ == &b); assert(a.__left_ == 0); assert(a.__right_ == 0); - assert(a.__is_black_ == false); + assert(a.__color_ == std::__tree_color::__red); assert(c.__parent_ == &b); assert(c.__left_ == 0); assert(c.__right_ == 0); - assert(c.__is_black_ == false); + assert(c.__color_ == std::__tree_color::__red); assert(b.__parent_ == &root); assert(b.__left_ == &a); assert(b.__right_ == &c); - assert(b.__is_black_ == true); + assert(b.__color_ == std::__tree_color::__black); } { Node root; @@ -657,29 +660,29 @@ void test2() { c.__parent_ = &root; c.__left_ = &a; c.__right_ = &g; - c.__is_black_ = true; + c.__color_ = std::__tree_color::__black; a.__parent_ = &c; a.__left_ = &d; a.__right_ = &b; - a.__is_black_ = false; + a.__color_ = std::__tree_color::__red; b.__parent_ = &a; b.__left_ = &e; b.__right_ = &f; - b.__is_black_ = false; + b.__color_ = std::__tree_color::__red; d.__parent_ = &a; - d.__is_black_ = true; + d.__color_ = std::__tree_color::__black; e.__parent_ = &b; - e.__is_black_ = true; + e.__color_ = std::__tree_color::__black; f.__parent_ = &b; - f.__is_black_ = true; + f.__color_ = std::__tree_color::__black; g.__parent_ = &c; - g.__is_black_ = true; + g.__color_ = std::__tree_color::__black; std::__tree_balance_after_insert(root.__left_, &b); @@ -690,29 +693,29 @@ void test2() { assert(c.__parent_ == &b); assert(c.__left_ == &f); assert(c.__right_ == &g); - assert(c.__is_black_ == false); + assert(c.__color_ == std::__tree_color::__red); assert(a.__parent_ == &b); assert(a.__left_ == &d); assert(a.__right_ == &e); - assert(a.__is_black_ == false); + assert(a.__color_ == std::__tree_color::__red); assert(b.__parent_ == &root); assert(b.__left_ == &a); assert(b.__right_ == &c); - assert(b.__is_black_ == true); + assert(b.__color_ == std::__tree_color::__black); assert(d.__parent_ == &a); - assert(d.__is_black_ == true); + assert(d.__color_ == std::__tree_color::__black); assert(e.__parent_ == &a); - assert(e.__is_black_ == true); + assert(e.__color_ == std::__tree_color::__black); assert(f.__parent_ == &c); - assert(f.__is_black_ == true); + assert(f.__color_ == std::__tree_color::__black); assert(g.__parent_ == &c); - assert(g.__is_black_ == true); + assert(g.__color_ == std::__tree_color::__black); } { Node root; @@ -729,29 +732,29 @@ void test2() { a.__parent_ = &root; a.__left_ = &d; a.__right_ = &c; - a.__is_black_ = true; + a.__color_ = std::__tree_color::__black; c.__parent_ = &a; c.__left_ = &b; c.__right_ = &g; - c.__is_black_ = false; + c.__color_ = std::__tree_color::__red; b.__parent_ = &c; b.__left_ = &e; b.__right_ = &f; - b.__is_black_ = false; + b.__color_ = std::__tree_color::__red; d.__parent_ = &a; - d.__is_black_ = true; + d.__color_ = std::__tree_color::__black; e.__parent_ = &b; - e.__is_black_ = true; + e.__color_ = std::__tree_color::__black; f.__parent_ = &b; - f.__is_black_ = true; + f.__color_ = std::__tree_color::__black; g.__parent_ = &c; - g.__is_black_ = true; + g.__color_ = std::__tree_color::__black; std::__tree_balance_after_insert(root.__left_, &b); @@ -762,29 +765,29 @@ void test2() { assert(c.__parent_ == &b); assert(c.__left_ == &f); assert(c.__right_ == &g); - assert(c.__is_black_ == false); + assert(c.__color_ == std::__tree_color::__red); assert(a.__parent_ == &b); assert(a.__left_ == &d); assert(a.__right_ == &e); - assert(a.__is_black_ == false); + assert(a.__color_ == std::__tree_color::__red); assert(b.__parent_ == &root); assert(b.__left_ == &a); assert(b.__right_ == &c); - assert(b.__is_black_ == true); + assert(b.__color_ == std::__tree_color::__black); assert(d.__parent_ == &a); - assert(d.__is_black_ == true); + assert(d.__color_ == std::__tree_color::__black); assert(e.__parent_ == &a); - assert(e.__is_black_ == true); + assert(e.__color_ == std::__tree_color::__black); assert(f.__parent_ == &c); - assert(f.__is_black_ == true); + assert(f.__color_ == std::__tree_color::__black); assert(g.__parent_ == &c); - assert(g.__is_black_ == true); + assert(g.__color_ == std::__tree_color::__black); } } @@ -800,17 +803,17 @@ void test3() { c.__parent_ = &root; c.__left_ = &b; c.__right_ = 0; - c.__is_black_ = true; + c.__color_ = std::__tree_color::__black; b.__parent_ = &c; b.__left_ = &a; b.__right_ = 0; - b.__is_black_ = false; + b.__color_ = std::__tree_color::__red; a.__parent_ = &b; a.__left_ = 0; a.__right_ = 0; - a.__is_black_ = false; + a.__color_ = std::__tree_color::__red; std::__tree_balance_after_insert(root.__left_, &a); @@ -821,17 +824,17 @@ void test3() { assert(c.__parent_ == &b); assert(c.__left_ == 0); assert(c.__right_ == 0); - assert(c.__is_black_ == false); + assert(c.__color_ == std::__tree_color::__red); assert(a.__parent_ == &b); assert(a.__left_ == 0); assert(a.__right_ == 0); - assert(a.__is_black_ == false); + assert(a.__color_ == std::__tree_color::__red); assert(b.__parent_ == &root); assert(b.__left_ == &a); assert(b.__right_ == &c); - assert(b.__is_black_ == true); + assert(b.__color_ == std::__tree_color::__black); } { Node root; @@ -844,17 +847,17 @@ void test3() { a.__parent_ = &root; a.__left_ = 0; a.__right_ = &b; - a.__is_black_ = true; + a.__color_ = std::__tree_color::__black; b.__parent_ = &a; b.__left_ = 0; b.__right_ = &c; - b.__is_black_ = false; + b.__color_ = std::__tree_color::__red; c.__parent_ = &b; c.__left_ = 0; c.__right_ = 0; - c.__is_black_ = false; + c.__color_ = std::__tree_color::__red; std::__tree_balance_after_insert(root.__left_, &c); @@ -865,17 +868,17 @@ void test3() { assert(a.__parent_ == &b); assert(a.__left_ == 0); assert(a.__right_ == 0); - assert(a.__is_black_ == false); + assert(a.__color_ == std::__tree_color::__red); assert(c.__parent_ == &b); assert(c.__left_ == 0); assert(c.__right_ == 0); - assert(c.__is_black_ == false); + assert(c.__color_ == std::__tree_color::__red); assert(b.__parent_ == &root); assert(b.__left_ == &a); assert(b.__right_ == &c); - assert(b.__is_black_ == true); + assert(b.__color_ == std::__tree_color::__black); } { Node root; @@ -892,29 +895,29 @@ void test3() { c.__parent_ = &root; c.__left_ = &b; c.__right_ = &g; - c.__is_black_ = true; + c.__color_ = std::__tree_color::__black; b.__parent_ = &c; b.__left_ = &a; b.__right_ = &f; - b.__is_black_ = false; + b.__color_ = std::__tree_color::__red; a.__parent_ = &b; a.__left_ = &d; a.__right_ = &e; - a.__is_black_ = false; + a.__color_ = std::__tree_color::__red; d.__parent_ = &a; - d.__is_black_ = true; + d.__color_ = std::__tree_color::__black; e.__parent_ = &a; - e.__is_black_ = true; + e.__color_ = std::__tree_color::__black; f.__parent_ = &b; - f.__is_black_ = true; + f.__color_ = std::__tree_color::__black; g.__parent_ = &c; - g.__is_black_ = true; + g.__color_ = std::__tree_color::__black; std::__tree_balance_after_insert(root.__left_, &a); @@ -925,29 +928,29 @@ void test3() { assert(c.__parent_ == &b); assert(c.__left_ == &f); assert(c.__right_ == &g); - assert(c.__is_black_ == false); + assert(c.__color_ == std::__tree_color::__red); assert(a.__parent_ == &b); assert(a.__left_ == &d); assert(a.__right_ == &e); - assert(a.__is_black_ == false); + assert(a.__color_ == std::__tree_color::__red); assert(b.__parent_ == &root); assert(b.__left_ == &a); assert(b.__right_ == &c); - assert(b.__is_black_ == true); + assert(b.__color_ == std::__tree_color::__black); assert(d.__parent_ == &a); - assert(d.__is_black_ == true); + assert(d.__color_ == std::__tree_color::__black); assert(e.__parent_ == &a); - assert(e.__is_black_ == true); + assert(e.__color_ == std::__tree_color::__black); assert(f.__parent_ == &c); - assert(f.__is_black_ == true); + assert(f.__color_ == std::__tree_color::__black); assert(g.__parent_ == &c); - assert(g.__is_black_ == true); + assert(g.__color_ == std::__tree_color::__black); } { Node root; @@ -964,29 +967,29 @@ void test3() { a.__parent_ = &root; a.__left_ = &d; a.__right_ = &b; - a.__is_black_ = true; + a.__color_ = std::__tree_color::__black; b.__parent_ = &a; b.__left_ = &e; b.__right_ = &c; - b.__is_black_ = false; + b.__color_ = std::__tree_color::__red; c.__parent_ = &b; c.__left_ = &f; c.__right_ = &g; - c.__is_black_ = false; + c.__color_ = std::__tree_color::__red; d.__parent_ = &a; - d.__is_black_ = true; + d.__color_ = std::__tree_color::__black; e.__parent_ = &b; - e.__is_black_ = true; + e.__color_ = std::__tree_color::__black; f.__parent_ = &c; - f.__is_black_ = true; + f.__color_ = std::__tree_color::__black; g.__parent_ = &c; - g.__is_black_ = true; + g.__color_ = std::__tree_color::__black; std::__tree_balance_after_insert(root.__left_, &c); @@ -997,29 +1000,29 @@ void test3() { assert(c.__parent_ == &b); assert(c.__left_ == &f); assert(c.__right_ == &g); - assert(c.__is_black_ == false); + assert(c.__color_ == std::__tree_color::__red); assert(a.__parent_ == &b); assert(a.__left_ == &d); assert(a.__right_ == &e); - assert(a.__is_black_ == false); + assert(a.__color_ == std::__tree_color::__red); assert(b.__parent_ == &root); assert(b.__left_ == &a); assert(b.__right_ == &c); - assert(b.__is_black_ == true); + assert(b.__color_ == std::__tree_color::__black); assert(d.__parent_ == &a); - assert(d.__is_black_ == true); + assert(d.__color_ == std::__tree_color::__black); assert(e.__parent_ == &a); - assert(e.__is_black_ == true); + assert(e.__color_ == std::__tree_color::__black); assert(f.__parent_ == &c); - assert(f.__is_black_ == true); + assert(f.__color_ == std::__tree_color::__black); assert(g.__parent_ == &c); - assert(g.__is_black_ == true); + assert(g.__color_ == std::__tree_color::__black); } } @@ -1044,12 +1047,12 @@ void test4() { assert(root.__parent_ == 0); assert(root.__left_ == &a); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(a.__parent_ == &root); assert(a.__left_ == 0); assert(a.__right_ == 0); - assert(a.__is_black_ == true); + assert(a.__color_ == std::__tree_color::__black); a.__right_ = &b; b.__parent_ = &a; @@ -1061,17 +1064,17 @@ void test4() { assert(root.__parent_ == 0); assert(root.__left_ == &a); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(a.__parent_ == &root); assert(a.__left_ == 0); assert(a.__right_ == &b); - assert(a.__is_black_ == true); + assert(a.__color_ == std::__tree_color::__black); assert(b.__parent_ == &a); assert(b.__left_ == 0); assert(b.__right_ == 0); - assert(b.__is_black_ == false); + assert(b.__color_ == std::__tree_color::__red); b.__right_ = &c; c.__parent_ = &b; @@ -1083,22 +1086,22 @@ void test4() { assert(root.__parent_ == 0); assert(root.__left_ == &b); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(a.__parent_ == &b); assert(a.__left_ == 0); assert(a.__right_ == 0); - assert(a.__is_black_ == false); + assert(a.__color_ == std::__tree_color::__red); assert(b.__parent_ == &root); assert(b.__left_ == &a); assert(b.__right_ == &c); - assert(b.__is_black_ == true); + assert(b.__color_ == std::__tree_color::__black); assert(c.__parent_ == &b); assert(c.__left_ == 0); assert(c.__right_ == 0); - assert(c.__is_black_ == false); + assert(c.__color_ == std::__tree_color::__red); c.__right_ = &d; d.__parent_ = &c; @@ -1110,27 +1113,27 @@ void test4() { assert(root.__parent_ == 0); assert(root.__left_ == &b); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(a.__parent_ == &b); assert(a.__left_ == 0); assert(a.__right_ == 0); - assert(a.__is_black_ == true); + assert(a.__color_ == std::__tree_color::__black); assert(b.__parent_ == &root); assert(b.__left_ == &a); assert(b.__right_ == &c); - assert(b.__is_black_ == true); + assert(b.__color_ == std::__tree_color::__black); assert(c.__parent_ == &b); assert(c.__left_ == 0); assert(c.__right_ == &d); - assert(c.__is_black_ == true); + assert(c.__color_ == std::__tree_color::__black); assert(d.__parent_ == &c); assert(d.__left_ == 0); assert(d.__right_ == 0); - assert(d.__is_black_ == false); + assert(d.__color_ == std::__tree_color::__red); d.__right_ = &e; e.__parent_ = &d; @@ -1142,32 +1145,32 @@ void test4() { assert(root.__parent_ == 0); assert(root.__left_ == &b); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(b.__parent_ == &root); assert(b.__left_ == &a); assert(b.__right_ == &d); - assert(b.__is_black_ == true); + assert(b.__color_ == std::__tree_color::__black); assert(a.__parent_ == &b); assert(a.__left_ == 0); assert(a.__right_ == 0); - assert(a.__is_black_ == true); + assert(a.__color_ == std::__tree_color::__black); assert(d.__parent_ == &b); assert(d.__left_ == &c); assert(d.__right_ == &e); - assert(d.__is_black_ == true); + assert(d.__color_ == std::__tree_color::__black); assert(c.__parent_ == &d); assert(c.__left_ == 0); assert(c.__right_ == 0); - assert(c.__is_black_ == false); + assert(c.__color_ == std::__tree_color::__red); assert(e.__parent_ == &d); assert(e.__left_ == 0); assert(e.__right_ == 0); - assert(e.__is_black_ == false); + assert(e.__color_ == std::__tree_color::__red); e.__right_ = &f; f.__parent_ = &e; @@ -1179,37 +1182,37 @@ void test4() { assert(root.__parent_ == 0); assert(root.__left_ == &b); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(b.__parent_ == &root); assert(b.__left_ == &a); assert(b.__right_ == &d); - assert(b.__is_black_ == true); + assert(b.__color_ == std::__tree_color::__black); assert(a.__parent_ == &b); assert(a.__left_ == 0); assert(a.__right_ == 0); - assert(a.__is_black_ == true); + assert(a.__color_ == std::__tree_color::__black); assert(d.__parent_ == &b); assert(d.__left_ == &c); assert(d.__right_ == &e); - assert(d.__is_black_ == false); + assert(d.__color_ == std::__tree_color::__red); assert(c.__parent_ == &d); assert(c.__left_ == 0); assert(c.__right_ == 0); - assert(c.__is_black_ == true); + assert(c.__color_ == std::__tree_color::__black); assert(e.__parent_ == &d); assert(e.__left_ == 0); assert(e.__right_ == &f); - assert(e.__is_black_ == true); + assert(e.__color_ == std::__tree_color::__black); assert(f.__parent_ == &e); assert(f.__left_ == 0); assert(f.__right_ == 0); - assert(f.__is_black_ == false); + assert(f.__color_ == std::__tree_color::__red); f.__right_ = &g; g.__parent_ = &f; @@ -1221,42 +1224,42 @@ void test4() { assert(root.__parent_ == 0); assert(root.__left_ == &b); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(b.__parent_ == &root); assert(b.__left_ == &a); assert(b.__right_ == &d); - assert(b.__is_black_ == true); + assert(b.__color_ == std::__tree_color::__black); assert(a.__parent_ == &b); assert(a.__left_ == 0); assert(a.__right_ == 0); - assert(a.__is_black_ == true); + assert(a.__color_ == std::__tree_color::__black); assert(d.__parent_ == &b); assert(d.__left_ == &c); assert(d.__right_ == &f); - assert(d.__is_black_ == false); + assert(d.__color_ == std::__tree_color::__red); assert(c.__parent_ == &d); assert(c.__left_ == 0); assert(c.__right_ == 0); - assert(c.__is_black_ == true); + assert(c.__color_ == std::__tree_color::__black); assert(f.__parent_ == &d); assert(f.__left_ == &e); assert(f.__right_ == &g); - assert(f.__is_black_ == true); + assert(f.__color_ == std::__tree_color::__black); assert(e.__parent_ == &f); assert(e.__left_ == 0); assert(e.__right_ == 0); - assert(e.__is_black_ == false); + assert(e.__color_ == std::__tree_color::__red); assert(g.__parent_ == &f); assert(g.__left_ == 0); assert(g.__right_ == 0); - assert(g.__is_black_ == false); + assert(g.__color_ == std::__tree_color::__red); g.__right_ = &h; h.__parent_ = &g; @@ -1268,47 +1271,47 @@ void test4() { assert(root.__parent_ == 0); assert(root.__left_ == &d); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(d.__parent_ == &root); assert(d.__left_ == &b); assert(d.__right_ == &f); - assert(d.__is_black_ == true); + assert(d.__color_ == std::__tree_color::__black); assert(b.__parent_ == &d); assert(b.__left_ == &a); assert(b.__right_ == &c); - assert(b.__is_black_ == false); + assert(b.__color_ == std::__tree_color::__red); assert(a.__parent_ == &b); assert(a.__left_ == 0); assert(a.__right_ == 0); - assert(a.__is_black_ == true); + assert(a.__color_ == std::__tree_color::__black); assert(c.__parent_ == &b); assert(c.__left_ == 0); assert(c.__right_ == 0); - assert(c.__is_black_ == true); + assert(c.__color_ == std::__tree_color::__black); assert(f.__parent_ == &d); assert(f.__left_ == &e); assert(f.__right_ == &g); - assert(f.__is_black_ == false); + assert(f.__color_ == std::__tree_color::__red); assert(e.__parent_ == &f); assert(e.__left_ == 0); assert(e.__right_ == 0); - assert(e.__is_black_ == true); + assert(e.__color_ == std::__tree_color::__black); assert(g.__parent_ == &f); assert(g.__left_ == 0); assert(g.__right_ == &h); - assert(g.__is_black_ == true); + assert(g.__color_ == std::__tree_color::__black); assert(h.__parent_ == &g); assert(h.__left_ == 0); assert(h.__right_ == 0); - assert(h.__is_black_ == false); + assert(h.__color_ == std::__tree_color::__red); } void test5() { @@ -1332,12 +1335,12 @@ void test5() { assert(root.__parent_ == 0); assert(root.__left_ == &h); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(h.__parent_ == &root); assert(h.__left_ == 0); assert(h.__right_ == 0); - assert(h.__is_black_ == true); + assert(h.__color_ == std::__tree_color::__black); h.__left_ = &g; g.__parent_ = &h; @@ -1349,17 +1352,17 @@ void test5() { assert(root.__parent_ == 0); assert(root.__left_ == &h); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(h.__parent_ == &root); assert(h.__left_ == &g); assert(h.__right_ == 0); - assert(h.__is_black_ == true); + assert(h.__color_ == std::__tree_color::__black); assert(g.__parent_ == &h); assert(g.__left_ == 0); assert(g.__right_ == 0); - assert(g.__is_black_ == false); + assert(g.__color_ == std::__tree_color::__red); g.__left_ = &f; f.__parent_ = &g; @@ -1371,22 +1374,22 @@ void test5() { assert(root.__parent_ == 0); assert(root.__left_ == &g); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(g.__parent_ == &root); assert(g.__left_ == &f); assert(g.__right_ == &h); - assert(g.__is_black_ == true); + assert(g.__color_ == std::__tree_color::__black); assert(f.__parent_ == &g); assert(f.__left_ == 0); assert(f.__right_ == 0); - assert(f.__is_black_ == false); + assert(f.__color_ == std::__tree_color::__red); assert(h.__parent_ == &g); assert(h.__left_ == 0); assert(h.__right_ == 0); - assert(h.__is_black_ == false); + assert(h.__color_ == std::__tree_color::__red); f.__left_ = &e; e.__parent_ = &f; @@ -1398,27 +1401,27 @@ void test5() { assert(root.__parent_ == 0); assert(root.__left_ == &g); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(g.__parent_ == &root); assert(g.__left_ == &f); assert(g.__right_ == &h); - assert(g.__is_black_ == true); + assert(g.__color_ == std::__tree_color::__black); assert(f.__parent_ == &g); assert(f.__left_ == &e); assert(f.__right_ == 0); - assert(f.__is_black_ == true); + assert(f.__color_ == std::__tree_color::__black); assert(e.__parent_ == &f); assert(e.__left_ == 0); assert(e.__right_ == 0); - assert(e.__is_black_ == false); + assert(e.__color_ == std::__tree_color::__red); assert(h.__parent_ == &g); assert(h.__left_ == 0); assert(h.__right_ == 0); - assert(h.__is_black_ == true); + assert(h.__color_ == std::__tree_color::__black); e.__left_ = &d; d.__parent_ = &e; @@ -1430,32 +1433,32 @@ void test5() { assert(root.__parent_ == 0); assert(root.__left_ == &g); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(g.__parent_ == &root); assert(g.__left_ == &e); assert(g.__right_ == &h); - assert(g.__is_black_ == true); + assert(g.__color_ == std::__tree_color::__black); assert(e.__parent_ == &g); assert(e.__left_ == &d); assert(e.__right_ == &f); - assert(e.__is_black_ == true); + assert(e.__color_ == std::__tree_color::__black); assert(d.__parent_ == &e); assert(d.__left_ == 0); assert(d.__right_ == 0); - assert(d.__is_black_ == false); + assert(d.__color_ == std::__tree_color::__red); assert(f.__parent_ == &e); assert(f.__left_ == 0); assert(f.__right_ == 0); - assert(f.__is_black_ == false); + assert(f.__color_ == std::__tree_color::__red); assert(h.__parent_ == &g); assert(h.__left_ == 0); assert(h.__right_ == 0); - assert(h.__is_black_ == true); + assert(h.__color_ == std::__tree_color::__black); d.__left_ = &c; c.__parent_ = &d; @@ -1467,37 +1470,37 @@ void test5() { assert(root.__parent_ == 0); assert(root.__left_ == &g); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(g.__parent_ == &root); assert(g.__left_ == &e); assert(g.__right_ == &h); - assert(g.__is_black_ == true); + assert(g.__color_ == std::__tree_color::__black); assert(e.__parent_ == &g); assert(e.__left_ == &d); assert(e.__right_ == &f); - assert(e.__is_black_ == false); + assert(e.__color_ == std::__tree_color::__red); assert(d.__parent_ == &e); assert(d.__left_ == &c); assert(d.__right_ == 0); - assert(d.__is_black_ == true); + assert(d.__color_ == std::__tree_color::__black); assert(c.__parent_ == &d); assert(c.__left_ == 0); assert(c.__right_ == 0); - assert(c.__is_black_ == false); + assert(c.__color_ == std::__tree_color::__red); assert(f.__parent_ == &e); assert(f.__left_ == 0); assert(f.__right_ == 0); - assert(f.__is_black_ == true); + assert(f.__color_ == std::__tree_color::__black); assert(h.__parent_ == &g); assert(h.__left_ == 0); assert(h.__right_ == 0); - assert(h.__is_black_ == true); + assert(h.__color_ == std::__tree_color::__black); c.__left_ = &b; b.__parent_ = &c; @@ -1509,42 +1512,42 @@ void test5() { assert(root.__parent_ == 0); assert(root.__left_ == &g); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(g.__parent_ == &root); assert(g.__left_ == &e); assert(g.__right_ == &h); - assert(g.__is_black_ == true); + assert(g.__color_ == std::__tree_color::__black); assert(e.__parent_ == &g); assert(e.__left_ == &c); assert(e.__right_ == &f); - assert(e.__is_black_ == false); + assert(e.__color_ == std::__tree_color::__red); assert(c.__parent_ == &e); assert(c.__left_ == &b); assert(c.__right_ == &d); - assert(c.__is_black_ == true); + assert(c.__color_ == std::__tree_color::__black); assert(b.__parent_ == &c); assert(b.__left_ == 0); assert(b.__right_ == 0); - assert(b.__is_black_ == false); + assert(b.__color_ == std::__tree_color::__red); assert(d.__parent_ == &c); assert(d.__left_ == 0); assert(d.__right_ == 0); - assert(d.__is_black_ == false); + assert(d.__color_ == std::__tree_color::__red); assert(f.__parent_ == &e); assert(f.__left_ == 0); assert(f.__right_ == 0); - assert(f.__is_black_ == true); + assert(f.__color_ == std::__tree_color::__black); assert(h.__parent_ == &g); assert(h.__left_ == 0); assert(h.__right_ == 0); - assert(h.__is_black_ == true); + assert(h.__color_ == std::__tree_color::__black); b.__left_ = &a; a.__parent_ = &b; @@ -1556,47 +1559,47 @@ void test5() { assert(root.__parent_ == 0); assert(root.__left_ == &e); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(e.__parent_ == &root); assert(e.__left_ == &c); assert(e.__right_ == &g); - assert(e.__is_black_ == true); + assert(e.__color_ == std::__tree_color::__black); assert(c.__parent_ == &e); assert(c.__left_ == &b); assert(c.__right_ == &d); - assert(c.__is_black_ == false); + assert(c.__color_ == std::__tree_color::__red); assert(b.__parent_ == &c); assert(b.__left_ == &a); assert(b.__right_ == 0); - assert(b.__is_black_ == true); + assert(b.__color_ == std::__tree_color::__black); assert(a.__parent_ == &b); assert(a.__left_ == 0); assert(a.__right_ == 0); - assert(a.__is_black_ == false); + assert(a.__color_ == std::__tree_color::__red); assert(d.__parent_ == &c); assert(d.__left_ == 0); assert(d.__right_ == 0); - assert(d.__is_black_ == true); + assert(d.__color_ == std::__tree_color::__black); assert(g.__parent_ == &e); assert(g.__left_ == &f); assert(g.__right_ == &h); - assert(g.__is_black_ == false); + assert(g.__color_ == std::__tree_color::__red); assert(f.__parent_ == &g); assert(f.__left_ == 0); assert(f.__right_ == 0); - assert(f.__is_black_ == true); + assert(f.__color_ == std::__tree_color::__black); assert(h.__parent_ == &g); assert(h.__left_ == 0); assert(h.__right_ == 0); - assert(h.__is_black_ == true); + assert(h.__color_ == std::__tree_color::__black); } int main(int, char**) { diff --git a/libcxx/test/libcxx/containers/associative/tree_left_rotate.pass.cpp b/libcxx/test/libcxx/containers/associative/tree_left_rotate.pass.cpp index e6cc646..8a318ff 100644 --- a/libcxx/test/libcxx/containers/associative/tree_left_rotate.pass.cpp +++ b/libcxx/test/libcxx/containers/associative/tree_left_rotate.pass.cpp @@ -25,6 +25,7 @@ struct Node { Node* __parent_unsafe() const { return __parent_; } void __set_parent(Node* x) { __parent_ = x; } + Node* __get_parent() { return __parent_; } Node() : __left_(), __right_(), __parent_() {} }; diff --git a/libcxx/test/libcxx/containers/associative/tree_remove.pass.cpp b/libcxx/test/libcxx/containers/associative/tree_remove.pass.cpp index dd9e7af..8702243 100644 --- a/libcxx/test/libcxx/containers/associative/tree_remove.pass.cpp +++ b/libcxx/test/libcxx/containers/associative/tree_remove.pass.cpp @@ -22,12 +22,15 @@ struct Node { Node* __left_; Node* __right_; Node* __parent_; - bool __is_black_; + std::__tree_color __color_; Node* __parent_unsafe() const { return __parent_; } void __set_parent(Node* x) { __parent_ = x; } + Node* __get_parent() { return __parent_; } + void __set_color(std::__tree_color __color) { __color_ = __color; } + std::__tree_color __get_color() { return __color_; } - Node() : __left_(), __right_(), __parent_(), __is_black_() {} + Node() : __left_(), __right_(), __parent_(), __color_() {} }; void test1() { @@ -46,27 +49,27 @@ void test1() { b.__parent_ = &root; b.__left_ = &y; b.__right_ = &d; - b.__is_black_ = true; + b.__color_ = std::__tree_color::__black; y.__parent_ = &b; y.__left_ = 0; y.__right_ = 0; - y.__is_black_ = true; + y.__color_ = std::__tree_color::__black; d.__parent_ = &b; d.__left_ = &c; d.__right_ = &e; - d.__is_black_ = false; + d.__color_ = std::__tree_color::__red; c.__parent_ = &d; c.__left_ = 0; c.__right_ = 0; - c.__is_black_ = true; + c.__color_ = std::__tree_color::__black; e.__parent_ = &d; e.__left_ = 0; e.__right_ = 0; - e.__is_black_ = true; + e.__color_ = std::__tree_color::__black; std::__tree_remove(root.__left_, &y); assert(std::__tree_invariant(root.__left_)); @@ -74,27 +77,27 @@ void test1() { assert(root.__parent_ == 0); assert(root.__left_ == &d); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(d.__parent_ == &root); assert(d.__left_ == &b); assert(d.__right_ == &e); - assert(d.__is_black_ == true); + assert(d.__color_ == std::__tree_color::__black); assert(b.__parent_ == &d); assert(b.__left_ == 0); assert(b.__right_ == &c); - assert(b.__is_black_ == true); + assert(b.__color_ == std::__tree_color::__black); assert(c.__parent_ == &b); assert(c.__left_ == 0); assert(c.__right_ == 0); - assert(c.__is_black_ == false); + assert(c.__color_ == std::__tree_color::__red); assert(e.__parent_ == &d); assert(e.__left_ == 0); assert(e.__right_ == 0); - assert(e.__is_black_ == true); + assert(e.__color_ == std::__tree_color::__black); } { // Right @@ -111,55 +114,56 @@ void test1() { b.__parent_ = &root; b.__right_ = &y; b.__left_ = &d; - b.__is_black_ = true; + b.__color_ = std::__tree_color::__black; y.__parent_ = &b; y.__right_ = 0; y.__left_ = 0; - y.__is_black_ = true; + y.__color_ = std::__tree_color::__black; d.__parent_ = &b; d.__right_ = &c; d.__left_ = &e; - d.__is_black_ = false; + d.__color_ = std::__tree_color::__red; c.__parent_ = &d; c.__right_ = 0; c.__left_ = 0; - c.__is_black_ = true; + c.__color_ = std::__tree_color::__black; e.__parent_ = &d; e.__right_ = 0; e.__left_ = 0; - e.__is_black_ = true; + e.__color_ = std::__tree_color::__black; + assert(std::__tree_invariant(root.__left_)); 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(root.__color_ == std::__tree_color::__red); assert(d.__parent_ == &root); assert(d.__right_ == &b); assert(d.__left_ == &e); - assert(d.__is_black_ == true); + assert(d.__color_ == std::__tree_color::__black); assert(b.__parent_ == &d); assert(b.__right_ == 0); assert(b.__left_ == &c); - assert(b.__is_black_ == true); + assert(b.__color_ == std::__tree_color::__black); assert(c.__parent_ == &b); assert(c.__right_ == 0); assert(c.__left_ == 0); - assert(c.__is_black_ == false); + assert(c.__color_ == std::__tree_color::__red); assert(e.__parent_ == &d); assert(e.__right_ == 0); assert(e.__left_ == 0); - assert(e.__is_black_ == true); + assert(e.__color_ == std::__tree_color::__black); } { // Left @@ -177,32 +181,32 @@ void test1() { b.__parent_ = &root; b.__left_ = &y; b.__right_ = &d; - b.__is_black_ = true; + b.__color_ = std::__tree_color::__black; y.__parent_ = &b; y.__left_ = 0; y.__right_ = 0; - y.__is_black_ = true; + y.__color_ = std::__tree_color::__black; d.__parent_ = &b; d.__left_ = &c; d.__right_ = &e; - d.__is_black_ = false; + d.__color_ = std::__tree_color::__red; c.__parent_ = &d; c.__left_ = &f; c.__right_ = 0; - c.__is_black_ = true; + c.__color_ = std::__tree_color::__black; e.__parent_ = &d; e.__left_ = 0; e.__right_ = 0; - e.__is_black_ = true; + e.__color_ = std::__tree_color::__black; f.__parent_ = &c; f.__left_ = 0; f.__right_ = 0; - f.__is_black_ = false; + f.__color_ = std::__tree_color::__red; std::__tree_remove(root.__left_, &y); assert(std::__tree_invariant(root.__left_)); @@ -210,32 +214,32 @@ void test1() { assert(root.__parent_ == 0); assert(root.__left_ == &d); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(d.__parent_ == &root); assert(d.__left_ == &f); assert(d.__right_ == &e); - assert(d.__is_black_ == true); + assert(d.__color_ == std::__tree_color::__black); assert(f.__parent_ == &d); assert(f.__left_ == &b); assert(f.__right_ == &c); - assert(f.__is_black_ == false); + assert(f.__color_ == std::__tree_color::__red); assert(b.__parent_ == &f); assert(b.__left_ == 0); assert(b.__right_ == 0); - assert(b.__is_black_ == true); + assert(b.__color_ == std::__tree_color::__black); assert(c.__parent_ == &f); assert(c.__left_ == 0); assert(c.__right_ == 0); - assert(c.__is_black_ == true); + assert(c.__color_ == std::__tree_color::__black); assert(e.__parent_ == &d); assert(e.__left_ == 0); assert(e.__right_ == 0); - assert(e.__is_black_ == true); + assert(e.__color_ == std::__tree_color::__black); } { // Right @@ -253,32 +257,32 @@ void test1() { b.__parent_ = &root; b.__right_ = &y; b.__left_ = &d; - b.__is_black_ = true; + b.__color_ = std::__tree_color::__black; y.__parent_ = &b; y.__right_ = 0; y.__left_ = 0; - y.__is_black_ = true; + y.__color_ = std::__tree_color::__black; d.__parent_ = &b; d.__right_ = &c; d.__left_ = &e; - d.__is_black_ = false; + d.__color_ = std::__tree_color::__red; c.__parent_ = &d; c.__right_ = &f; c.__left_ = 0; - c.__is_black_ = true; + c.__color_ = std::__tree_color::__black; e.__parent_ = &d; e.__right_ = 0; e.__left_ = 0; - e.__is_black_ = true; + e.__color_ = std::__tree_color::__black; f.__parent_ = &c; f.__right_ = 0; f.__left_ = 0; - f.__is_black_ = false; + f.__color_ = std::__tree_color::__red; std::__tree_remove(root.__left_, &y); assert(std::__tree_invariant(root.__left_)); @@ -286,32 +290,32 @@ void test1() { assert(root.__parent_ == 0); assert(root.__left_ == &d); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(d.__parent_ == &root); assert(d.__right_ == &f); assert(d.__left_ == &e); - assert(d.__is_black_ == true); + assert(d.__color_ == std::__tree_color::__black); assert(f.__parent_ == &d); assert(f.__right_ == &b); assert(f.__left_ == &c); - assert(f.__is_black_ == false); + assert(f.__color_ == std::__tree_color::__red); assert(b.__parent_ == &f); assert(b.__right_ == 0); assert(b.__left_ == 0); - assert(b.__is_black_ == true); + assert(b.__color_ == std::__tree_color::__black); assert(c.__parent_ == &f); assert(c.__right_ == 0); assert(c.__left_ == 0); - assert(c.__is_black_ == true); + assert(c.__color_ == std::__tree_color::__black); assert(e.__parent_ == &d); assert(e.__right_ == 0); assert(e.__left_ == 0); - assert(e.__is_black_ == true); + assert(e.__color_ == std::__tree_color::__black); } } @@ -327,17 +331,17 @@ void test2() { b.__parent_ = &root; b.__left_ = &a; b.__right_ = &c; - b.__is_black_ = true; + b.__color_ = std::__tree_color::__black; a.__parent_ = &b; a.__left_ = 0; a.__right_ = 0; - a.__is_black_ = true; + a.__color_ = std::__tree_color::__black; c.__parent_ = &b; c.__left_ = 0; c.__right_ = 0; - c.__is_black_ = true; + c.__color_ = std::__tree_color::__black; std::__tree_remove(root.__left_, &a); @@ -346,17 +350,17 @@ void test2() { assert(root.__parent_ == 0); assert(root.__left_ == &b); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(b.__parent_ == &root); assert(b.__left_ == 0); assert(b.__right_ == &c); - assert(b.__is_black_ == true); + assert(b.__color_ == std::__tree_color::__black); assert(c.__parent_ == &b); assert(c.__left_ == 0); assert(c.__right_ == 0); - assert(c.__is_black_ == false); + assert(c.__color_ == std::__tree_color::__red); std::__tree_remove(root.__left_, &b); @@ -365,12 +369,12 @@ void test2() { assert(root.__parent_ == 0); assert(root.__left_ == &c); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(c.__parent_ == &root); assert(c.__left_ == 0); assert(c.__right_ == 0); - assert(c.__is_black_ == true); + assert(c.__color_ == std::__tree_color::__black); std::__tree_remove(root.__left_, &c); @@ -379,7 +383,7 @@ void test2() { assert(root.__parent_ == 0); assert(root.__left_ == 0); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); } { Node root; @@ -392,17 +396,17 @@ void test2() { b.__parent_ = &root; b.__left_ = &a; b.__right_ = &c; - b.__is_black_ = true; + b.__color_ = std::__tree_color::__black; a.__parent_ = &b; a.__left_ = 0; a.__right_ = 0; - a.__is_black_ = false; + a.__color_ = std::__tree_color::__red; c.__parent_ = &b; c.__left_ = 0; c.__right_ = 0; - c.__is_black_ = false; + c.__color_ = std::__tree_color::__red; std::__tree_remove(root.__left_, &a); @@ -411,17 +415,17 @@ void test2() { assert(root.__parent_ == 0); assert(root.__left_ == &b); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(b.__parent_ == &root); assert(b.__left_ == 0); assert(b.__right_ == &c); - assert(b.__is_black_ == true); + assert(b.__color_ == std::__tree_color::__black); assert(c.__parent_ == &b); assert(c.__left_ == 0); assert(c.__right_ == 0); - assert(c.__is_black_ == false); + assert(c.__color_ == std::__tree_color::__red); std::__tree_remove(root.__left_, &b); @@ -430,12 +434,12 @@ void test2() { assert(root.__parent_ == 0); assert(root.__left_ == &c); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(c.__parent_ == &root); assert(c.__left_ == 0); assert(c.__right_ == 0); - assert(c.__is_black_ == true); + assert(c.__color_ == std::__tree_color::__black); std::__tree_remove(root.__left_, &c); @@ -444,7 +448,7 @@ void test2() { assert(root.__parent_ == 0); assert(root.__left_ == 0); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); } { Node root; @@ -457,17 +461,17 @@ void test2() { b.__parent_ = &root; b.__left_ = &a; b.__right_ = &c; - b.__is_black_ = true; + b.__color_ = std::__tree_color::__black; a.__parent_ = &b; a.__left_ = 0; a.__right_ = 0; - a.__is_black_ = true; + a.__color_ = std::__tree_color::__black; c.__parent_ = &b; c.__left_ = 0; c.__right_ = 0; - c.__is_black_ = true; + c.__color_ = std::__tree_color::__black; std::__tree_remove(root.__left_, &a); @@ -476,17 +480,17 @@ void test2() { assert(root.__parent_ == 0); assert(root.__left_ == &b); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(b.__parent_ == &root); assert(b.__left_ == 0); assert(b.__right_ == &c); - assert(b.__is_black_ == true); + assert(b.__color_ == std::__tree_color::__black); assert(c.__parent_ == &b); assert(c.__left_ == 0); assert(c.__right_ == 0); - assert(c.__is_black_ == false); + assert(c.__color_ == std::__tree_color::__red); std::__tree_remove(root.__left_, &c); @@ -495,12 +499,12 @@ void test2() { assert(root.__parent_ == 0); assert(root.__left_ == &b); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(b.__parent_ == &root); assert(b.__left_ == 0); assert(b.__right_ == 0); - assert(b.__is_black_ == true); + assert(b.__color_ == std::__tree_color::__black); std::__tree_remove(root.__left_, &b); @@ -509,7 +513,7 @@ void test2() { assert(root.__parent_ == 0); assert(root.__left_ == 0); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); } { Node root; @@ -522,17 +526,17 @@ void test2() { b.__parent_ = &root; b.__left_ = &a; b.__right_ = &c; - b.__is_black_ = true; + b.__color_ = std::__tree_color::__black; a.__parent_ = &b; a.__left_ = 0; a.__right_ = 0; - a.__is_black_ = false; + a.__color_ = std::__tree_color::__red; c.__parent_ = &b; c.__left_ = 0; c.__right_ = 0; - c.__is_black_ = false; + c.__color_ = std::__tree_color::__red; std::__tree_remove(root.__left_, &a); @@ -541,17 +545,17 @@ void test2() { assert(root.__parent_ == 0); assert(root.__left_ == &b); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(b.__parent_ == &root); assert(b.__left_ == 0); assert(b.__right_ == &c); - assert(b.__is_black_ == true); + assert(b.__color_ == std::__tree_color::__black); assert(c.__parent_ == &b); assert(c.__left_ == 0); assert(c.__right_ == 0); - assert(c.__is_black_ == false); + assert(c.__color_ == std::__tree_color::__red); std::__tree_remove(root.__left_, &c); @@ -560,12 +564,12 @@ void test2() { assert(root.__parent_ == 0); assert(root.__left_ == &b); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(b.__parent_ == &root); assert(b.__left_ == 0); assert(b.__right_ == 0); - assert(b.__is_black_ == true); + assert(b.__color_ == std::__tree_color::__black); std::__tree_remove(root.__left_, &b); @@ -574,7 +578,7 @@ void test2() { assert(root.__parent_ == 0); assert(root.__left_ == 0); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); } { Node root; @@ -587,17 +591,17 @@ void test2() { b.__parent_ = &root; b.__left_ = &a; b.__right_ = &c; - b.__is_black_ = true; + b.__color_ = std::__tree_color::__black; a.__parent_ = &b; a.__left_ = 0; a.__right_ = 0; - a.__is_black_ = true; + a.__color_ = std::__tree_color::__black; c.__parent_ = &b; c.__left_ = 0; c.__right_ = 0; - c.__is_black_ = true; + c.__color_ = std::__tree_color::__black; std::__tree_remove(root.__left_, &b); @@ -606,17 +610,17 @@ void test2() { assert(root.__parent_ == 0); assert(root.__left_ == &c); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(a.__parent_ == &c); assert(a.__left_ == 0); assert(a.__right_ == 0); - assert(a.__is_black_ == false); + assert(a.__color_ == std::__tree_color::__red); assert(c.__parent_ == &root); assert(c.__left_ == &a); assert(c.__right_ == 0); - assert(c.__is_black_ == true); + assert(c.__color_ == std::__tree_color::__black); std::__tree_remove(root.__left_, &a); @@ -625,12 +629,12 @@ void test2() { assert(root.__parent_ == 0); assert(root.__left_ == &c); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(c.__parent_ == &root); assert(c.__left_ == 0); assert(c.__right_ == 0); - assert(c.__is_black_ == true); + assert(c.__color_ == std::__tree_color::__black); std::__tree_remove(root.__left_, &c); @@ -639,7 +643,7 @@ void test2() { assert(root.__parent_ == 0); assert(root.__left_ == 0); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); } { Node root; @@ -652,17 +656,17 @@ void test2() { b.__parent_ = &root; b.__left_ = &a; b.__right_ = &c; - b.__is_black_ = true; + b.__color_ = std::__tree_color::__black; a.__parent_ = &b; a.__left_ = 0; a.__right_ = 0; - a.__is_black_ = false; + a.__color_ = std::__tree_color::__red; c.__parent_ = &b; c.__left_ = 0; c.__right_ = 0; - c.__is_black_ = false; + c.__color_ = std::__tree_color::__red; std::__tree_remove(root.__left_, &b); @@ -671,17 +675,17 @@ void test2() { assert(root.__parent_ == 0); assert(root.__left_ == &c); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(a.__parent_ == &c); assert(a.__left_ == 0); assert(a.__right_ == 0); - assert(a.__is_black_ == false); + assert(a.__color_ == std::__tree_color::__red); assert(c.__parent_ == &root); assert(c.__left_ == &a); assert(c.__right_ == 0); - assert(c.__is_black_ == true); + assert(c.__color_ == std::__tree_color::__black); std::__tree_remove(root.__left_, &a); @@ -690,12 +694,12 @@ void test2() { assert(root.__parent_ == 0); assert(root.__left_ == &c); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(c.__parent_ == &root); assert(c.__left_ == 0); assert(c.__right_ == 0); - assert(c.__is_black_ == true); + assert(c.__color_ == std::__tree_color::__black); std::__tree_remove(root.__left_, &c); @@ -704,7 +708,7 @@ void test2() { assert(root.__parent_ == 0); assert(root.__left_ == 0); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); } { Node root; @@ -717,17 +721,17 @@ void test2() { b.__parent_ = &root; b.__left_ = &a; b.__right_ = &c; - b.__is_black_ = true; + b.__color_ = std::__tree_color::__black; a.__parent_ = &b; a.__left_ = 0; a.__right_ = 0; - a.__is_black_ = true; + a.__color_ = std::__tree_color::__black; c.__parent_ = &b; c.__left_ = 0; c.__right_ = 0; - c.__is_black_ = true; + c.__color_ = std::__tree_color::__black; std::__tree_remove(root.__left_, &b); @@ -736,17 +740,17 @@ void test2() { assert(root.__parent_ == 0); assert(root.__left_ == &c); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(a.__parent_ == &c); assert(a.__left_ == 0); assert(a.__right_ == 0); - assert(a.__is_black_ == false); + assert(a.__color_ == std::__tree_color::__red); assert(c.__parent_ == &root); assert(c.__left_ == &a); assert(c.__right_ == 0); - assert(c.__is_black_ == true); + assert(c.__color_ == std::__tree_color::__black); std::__tree_remove(root.__left_, &c); @@ -755,12 +759,12 @@ void test2() { assert(root.__parent_ == 0); assert(root.__left_ == &a); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(a.__parent_ == &root); assert(a.__left_ == 0); assert(a.__right_ == 0); - assert(a.__is_black_ == true); + assert(a.__color_ == std::__tree_color::__black); std::__tree_remove(root.__left_, &a); @@ -769,7 +773,7 @@ void test2() { assert(root.__parent_ == 0); assert(root.__left_ == 0); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); } { Node root; @@ -782,17 +786,17 @@ void test2() { b.__parent_ = &root; b.__left_ = &a; b.__right_ = &c; - b.__is_black_ = true; + b.__color_ = std::__tree_color::__black; a.__parent_ = &b; a.__left_ = 0; a.__right_ = 0; - a.__is_black_ = false; + a.__color_ = std::__tree_color::__red; c.__parent_ = &b; c.__left_ = 0; c.__right_ = 0; - c.__is_black_ = false; + c.__color_ = std::__tree_color::__red; std::__tree_remove(root.__left_, &b); @@ -801,17 +805,17 @@ void test2() { assert(root.__parent_ == 0); assert(root.__left_ == &c); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(a.__parent_ == &c); assert(a.__left_ == 0); assert(a.__right_ == 0); - assert(a.__is_black_ == false); + assert(a.__color_ == std::__tree_color::__red); assert(c.__parent_ == &root); assert(c.__left_ == &a); assert(c.__right_ == 0); - assert(c.__is_black_ == true); + assert(c.__color_ == std::__tree_color::__black); std::__tree_remove(root.__left_, &c); @@ -820,12 +824,12 @@ void test2() { assert(root.__parent_ == 0); assert(root.__left_ == &a); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(a.__parent_ == &root); assert(a.__left_ == 0); assert(a.__right_ == 0); - assert(a.__is_black_ == true); + assert(a.__color_ == std::__tree_color::__black); std::__tree_remove(root.__left_, &a); @@ -834,7 +838,7 @@ void test2() { assert(root.__parent_ == 0); assert(root.__left_ == 0); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); } { Node root; @@ -847,17 +851,17 @@ void test2() { b.__parent_ = &root; b.__left_ = &a; b.__right_ = &c; - b.__is_black_ = true; + b.__color_ = std::__tree_color::__black; a.__parent_ = &b; a.__left_ = 0; a.__right_ = 0; - a.__is_black_ = true; + a.__color_ = std::__tree_color::__black; c.__parent_ = &b; c.__left_ = 0; c.__right_ = 0; - c.__is_black_ = true; + c.__color_ = std::__tree_color::__black; std::__tree_remove(root.__left_, &c); @@ -866,17 +870,17 @@ void test2() { assert(root.__parent_ == 0); assert(root.__left_ == &b); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(a.__parent_ == &b); assert(a.__left_ == 0); assert(a.__right_ == 0); - assert(a.__is_black_ == false); + assert(a.__color_ == std::__tree_color::__red); assert(b.__parent_ == &root); assert(b.__left_ == &a); assert(b.__right_ == 0); - assert(b.__is_black_ == true); + assert(b.__color_ == std::__tree_color::__black); std::__tree_remove(root.__left_, &b); @@ -885,12 +889,12 @@ void test2() { assert(root.__parent_ == 0); assert(root.__left_ == &a); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(a.__parent_ == &root); assert(a.__left_ == 0); assert(a.__right_ == 0); - assert(a.__is_black_ == true); + assert(a.__color_ == std::__tree_color::__black); std::__tree_remove(root.__left_, &a); @@ -899,7 +903,7 @@ void test2() { assert(root.__parent_ == 0); assert(root.__left_ == 0); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); } { Node root; @@ -912,17 +916,17 @@ void test2() { b.__parent_ = &root; b.__left_ = &a; b.__right_ = &c; - b.__is_black_ = true; + b.__color_ = std::__tree_color::__black; a.__parent_ = &b; a.__left_ = 0; a.__right_ = 0; - a.__is_black_ = false; + a.__color_ = std::__tree_color::__red; c.__parent_ = &b; c.__left_ = 0; c.__right_ = 0; - c.__is_black_ = false; + c.__color_ = std::__tree_color::__red; std::__tree_remove(root.__left_, &c); @@ -931,17 +935,17 @@ void test2() { assert(root.__parent_ == 0); assert(root.__left_ == &b); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(a.__parent_ == &b); assert(a.__left_ == 0); assert(a.__right_ == 0); - assert(a.__is_black_ == false); + assert(a.__color_ == std::__tree_color::__red); assert(b.__parent_ == &root); assert(b.__left_ == &a); assert(b.__right_ == 0); - assert(b.__is_black_ == true); + assert(b.__color_ == std::__tree_color::__black); std::__tree_remove(root.__left_, &b); @@ -950,12 +954,12 @@ void test2() { assert(root.__parent_ == 0); assert(root.__left_ == &a); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(a.__parent_ == &root); assert(a.__left_ == 0); assert(a.__right_ == 0); - assert(a.__is_black_ == true); + assert(a.__color_ == std::__tree_color::__black); std::__tree_remove(root.__left_, &a); @@ -964,7 +968,7 @@ void test2() { assert(root.__parent_ == 0); assert(root.__left_ == 0); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); } { Node root; @@ -977,17 +981,17 @@ void test2() { b.__parent_ = &root; b.__left_ = &a; b.__right_ = &c; - b.__is_black_ = true; + b.__color_ = std::__tree_color::__black; a.__parent_ = &b; a.__left_ = 0; a.__right_ = 0; - a.__is_black_ = true; + a.__color_ = std::__tree_color::__black; c.__parent_ = &b; c.__left_ = 0; c.__right_ = 0; - c.__is_black_ = true; + c.__color_ = std::__tree_color::__black; std::__tree_remove(root.__left_, &c); @@ -996,17 +1000,17 @@ void test2() { assert(root.__parent_ == 0); assert(root.__left_ == &b); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(a.__parent_ == &b); assert(a.__left_ == 0); assert(a.__right_ == 0); - assert(a.__is_black_ == false); + assert(a.__color_ == std::__tree_color::__red); assert(b.__parent_ == &root); assert(b.__left_ == &a); assert(b.__right_ == 0); - assert(b.__is_black_ == true); + assert(b.__color_ == std::__tree_color::__black); std::__tree_remove(root.__left_, &a); @@ -1015,12 +1019,12 @@ void test2() { assert(root.__parent_ == 0); assert(root.__left_ == &b); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(b.__parent_ == &root); assert(b.__left_ == 0); assert(b.__right_ == 0); - assert(b.__is_black_ == true); + assert(b.__color_ == std::__tree_color::__black); std::__tree_remove(root.__left_, &b); @@ -1029,7 +1033,7 @@ void test2() { assert(root.__parent_ == 0); assert(root.__left_ == 0); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); } { Node root; @@ -1042,17 +1046,17 @@ void test2() { b.__parent_ = &root; b.__left_ = &a; b.__right_ = &c; - b.__is_black_ = true; + b.__color_ = std::__tree_color::__black; a.__parent_ = &b; a.__left_ = 0; a.__right_ = 0; - a.__is_black_ = false; + a.__color_ = std::__tree_color::__red; c.__parent_ = &b; c.__left_ = 0; c.__right_ = 0; - c.__is_black_ = false; + c.__color_ = std::__tree_color::__red; std::__tree_remove(root.__left_, &c); @@ -1061,17 +1065,17 @@ void test2() { assert(root.__parent_ == 0); assert(root.__left_ == &b); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(a.__parent_ == &b); assert(a.__left_ == 0); assert(a.__right_ == 0); - assert(a.__is_black_ == false); + assert(a.__color_ == std::__tree_color::__red); assert(b.__parent_ == &root); assert(b.__left_ == &a); assert(b.__right_ == 0); - assert(b.__is_black_ == true); + assert(b.__color_ == std::__tree_color::__black); std::__tree_remove(root.__left_, &a); @@ -1080,12 +1084,12 @@ void test2() { assert(root.__parent_ == 0); assert(root.__left_ == &b); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(b.__parent_ == &root); assert(b.__left_ == 0); assert(b.__right_ == 0); - assert(b.__is_black_ == true); + assert(b.__color_ == std::__tree_color::__black); std::__tree_remove(root.__left_, &b); @@ -1094,7 +1098,7 @@ void test2() { assert(root.__parent_ == 0); assert(root.__left_ == 0); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); } } @@ -1114,42 +1118,42 @@ void test3() { e.__parent_ = &root; e.__left_ = &c; e.__right_ = &g; - e.__is_black_ = true; + e.__color_ = std::__tree_color::__black; c.__parent_ = &e; c.__left_ = &b; c.__right_ = &d; - c.__is_black_ = false; + c.__color_ = std::__tree_color::__red; g.__parent_ = &e; g.__left_ = &f; g.__right_ = &h; - g.__is_black_ = false; + g.__color_ = std::__tree_color::__red; b.__parent_ = &c; b.__left_ = &a; b.__right_ = 0; - b.__is_black_ = true; + b.__color_ = std::__tree_color::__black; d.__parent_ = &c; d.__left_ = 0; d.__right_ = 0; - d.__is_black_ = true; + d.__color_ = std::__tree_color::__black; f.__parent_ = &g; f.__left_ = 0; f.__right_ = 0; - f.__is_black_ = true; + f.__color_ = std::__tree_color::__black; h.__parent_ = &g; h.__left_ = 0; h.__right_ = 0; - h.__is_black_ = true; + h.__color_ = std::__tree_color::__black; a.__parent_ = &b; a.__left_ = 0; a.__right_ = 0; - a.__is_black_ = false; + a.__color_ = std::__tree_color::__red; assert(std::__tree_invariant(root.__left_)); @@ -1160,42 +1164,42 @@ void test3() { assert(root.__parent_ == 0); assert(root.__left_ == &e); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(e.__parent_ == &root); assert(e.__left_ == &c); assert(e.__right_ == &g); - assert(e.__is_black_ == true); + assert(e.__color_ == std::__tree_color::__black); assert(c.__parent_ == &e); assert(c.__left_ == &b); assert(c.__right_ == &d); - assert(c.__is_black_ == false); + assert(c.__color_ == std::__tree_color::__red); assert(g.__parent_ == &e); assert(g.__left_ == &f); assert(g.__right_ == 0); - assert(g.__is_black_ == true); + assert(g.__color_ == std::__tree_color::__black); assert(b.__parent_ == &c); assert(b.__left_ == &a); assert(b.__right_ == 0); - assert(b.__is_black_ == true); + assert(b.__color_ == std::__tree_color::__black); assert(a.__parent_ == &b); assert(a.__left_ == 0); assert(a.__right_ == 0); - assert(a.__is_black_ == false); + assert(a.__color_ == std::__tree_color::__red); assert(d.__parent_ == &c); assert(d.__left_ == 0); assert(d.__right_ == 0); - assert(d.__is_black_ == true); + assert(d.__color_ == std::__tree_color::__black); assert(f.__parent_ == &g); assert(f.__left_ == 0); assert(f.__right_ == 0); - assert(f.__is_black_ == false); + assert(f.__color_ == std::__tree_color::__red); std::__tree_remove(root.__left_, &g); @@ -1204,37 +1208,37 @@ void test3() { assert(root.__parent_ == 0); assert(root.__left_ == &e); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(e.__parent_ == &root); assert(e.__left_ == &c); assert(e.__right_ == &f); - assert(e.__is_black_ == true); + assert(e.__color_ == std::__tree_color::__black); assert(c.__parent_ == &e); assert(c.__left_ == &b); assert(c.__right_ == &d); - assert(c.__is_black_ == false); + assert(c.__color_ == std::__tree_color::__red); assert(b.__parent_ == &c); assert(b.__left_ == &a); assert(b.__right_ == 0); - assert(b.__is_black_ == true); + assert(b.__color_ == std::__tree_color::__black); assert(a.__parent_ == &b); assert(a.__left_ == 0); assert(a.__right_ == 0); - assert(a.__is_black_ == false); + assert(a.__color_ == std::__tree_color::__red); assert(d.__parent_ == &c); assert(d.__left_ == 0); assert(d.__right_ == 0); - assert(d.__is_black_ == true); + assert(d.__color_ == std::__tree_color::__black); assert(f.__parent_ == &e); assert(f.__left_ == 0); assert(f.__right_ == 0); - assert(f.__is_black_ == true); + assert(f.__color_ == std::__tree_color::__black); std::__tree_remove(root.__left_, &f); @@ -1243,32 +1247,32 @@ void test3() { assert(root.__parent_ == 0); assert(root.__left_ == &c); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(c.__parent_ == &root); assert(c.__left_ == &b); assert(c.__right_ == &e); - assert(c.__is_black_ == true); + assert(c.__color_ == std::__tree_color::__black); assert(b.__parent_ == &c); assert(b.__left_ == &a); assert(b.__right_ == 0); - assert(b.__is_black_ == true); + assert(b.__color_ == std::__tree_color::__black); assert(e.__parent_ == &c); assert(e.__left_ == &d); assert(e.__right_ == 0); - assert(e.__is_black_ == true); + assert(e.__color_ == std::__tree_color::__black); assert(a.__parent_ == &b); assert(a.__left_ == 0); assert(a.__right_ == 0); - assert(a.__is_black_ == false); + assert(a.__color_ == std::__tree_color::__red); assert(d.__parent_ == &e); assert(d.__left_ == 0); assert(d.__right_ == 0); - assert(d.__is_black_ == false); + assert(d.__color_ == std::__tree_color::__red); std::__tree_remove(root.__left_, &e); @@ -1277,27 +1281,27 @@ void test3() { assert(root.__parent_ == 0); assert(root.__left_ == &c); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(c.__parent_ == &root); assert(c.__left_ == &b); assert(c.__right_ == &d); - assert(c.__is_black_ == true); + assert(c.__color_ == std::__tree_color::__black); assert(b.__parent_ == &c); assert(b.__left_ == &a); assert(b.__right_ == 0); - assert(b.__is_black_ == true); + assert(b.__color_ == std::__tree_color::__black); assert(a.__parent_ == &b); assert(a.__left_ == 0); assert(a.__right_ == 0); - assert(a.__is_black_ == false); + assert(a.__color_ == std::__tree_color::__red); assert(d.__parent_ == &c); assert(d.__left_ == 0); assert(d.__right_ == 0); - assert(d.__is_black_ == true); + assert(d.__color_ == std::__tree_color::__black); std::__tree_remove(root.__left_, &d); @@ -1306,22 +1310,22 @@ void test3() { assert(root.__parent_ == 0); assert(root.__left_ == &b); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(b.__parent_ == &root); assert(b.__left_ == &a); assert(b.__right_ == &c); - assert(b.__is_black_ == true); + assert(b.__color_ == std::__tree_color::__black); assert(a.__parent_ == &b); assert(a.__left_ == 0); assert(a.__right_ == 0); - assert(a.__is_black_ == true); + assert(a.__color_ == std::__tree_color::__black); assert(c.__parent_ == &b); assert(c.__left_ == 0); assert(c.__right_ == 0); - assert(c.__is_black_ == true); + assert(c.__color_ == std::__tree_color::__black); std::__tree_remove(root.__left_, &c); @@ -1330,17 +1334,17 @@ void test3() { assert(root.__parent_ == 0); assert(root.__left_ == &b); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(b.__parent_ == &root); assert(b.__left_ == &a); assert(b.__right_ == 0); - assert(b.__is_black_ == true); + assert(b.__color_ == std::__tree_color::__black); assert(a.__parent_ == &b); assert(a.__left_ == 0); assert(a.__right_ == 0); - assert(a.__is_black_ == false); + assert(a.__color_ == std::__tree_color::__red); std::__tree_remove(root.__left_, &b); @@ -1349,12 +1353,12 @@ void test3() { assert(root.__parent_ == 0); assert(root.__left_ == &a); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(a.__parent_ == &root); assert(a.__left_ == 0); assert(a.__right_ == 0); - assert(a.__is_black_ == true); + assert(a.__color_ == std::__tree_color::__black); std::__tree_remove(root.__left_, &a); @@ -1363,7 +1367,7 @@ void test3() { assert(root.__parent_ == 0); assert(root.__left_ == 0); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); } void test4() { @@ -1382,42 +1386,42 @@ void test4() { d.__parent_ = &root; d.__left_ = &b; d.__right_ = &f; - d.__is_black_ = true; + d.__color_ = std::__tree_color::__black; b.__parent_ = &d; b.__left_ = &a; b.__right_ = &c; - b.__is_black_ = false; + b.__color_ = std::__tree_color::__red; f.__parent_ = &d; f.__left_ = &e; f.__right_ = &g; - f.__is_black_ = false; + f.__color_ = std::__tree_color::__red; a.__parent_ = &b; a.__left_ = 0; a.__right_ = 0; - a.__is_black_ = true; + a.__color_ = std::__tree_color::__black; c.__parent_ = &b; c.__left_ = 0; c.__right_ = 0; - c.__is_black_ = true; + c.__color_ = std::__tree_color::__black; e.__parent_ = &f; e.__left_ = 0; e.__right_ = 0; - e.__is_black_ = true; + e.__color_ = std::__tree_color::__black; g.__parent_ = &f; g.__left_ = 0; g.__right_ = &h; - g.__is_black_ = true; + g.__color_ = std::__tree_color::__black; h.__parent_ = &g; h.__left_ = 0; h.__right_ = 0; - h.__is_black_ = false; + h.__color_ = std::__tree_color::__red; assert(std::__tree_invariant(root.__left_)); @@ -1428,42 +1432,42 @@ void test4() { assert(root.__parent_ == 0); assert(root.__left_ == &d); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(d.__parent_ == &root); assert(d.__left_ == &b); assert(d.__right_ == &f); - assert(d.__is_black_ == true); + assert(d.__color_ == std::__tree_color::__black); assert(b.__parent_ == &d); assert(b.__left_ == 0); assert(b.__right_ == &c); - assert(b.__is_black_ == true); + assert(b.__color_ == std::__tree_color::__black); assert(f.__parent_ == &d); assert(f.__left_ == &e); assert(f.__right_ == &g); - assert(f.__is_black_ == false); + assert(f.__color_ == std::__tree_color::__red); assert(c.__parent_ == &b); assert(c.__left_ == 0); assert(c.__right_ == 0); - assert(c.__is_black_ == false); + assert(c.__color_ == std::__tree_color::__red); assert(e.__parent_ == &f); assert(e.__left_ == 0); assert(e.__right_ == 0); - assert(e.__is_black_ == true); + assert(e.__color_ == std::__tree_color::__black); assert(g.__parent_ == &f); assert(g.__left_ == 0); assert(g.__right_ == &h); - assert(g.__is_black_ == true); + assert(g.__color_ == std::__tree_color::__black); assert(h.__parent_ == &g); assert(h.__left_ == 0); assert(h.__right_ == 0); - assert(h.__is_black_ == false); + assert(h.__color_ == std::__tree_color::__red); std::__tree_remove(root.__left_, &b); @@ -1472,37 +1476,37 @@ void test4() { assert(root.__parent_ == 0); assert(root.__left_ == &d); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(d.__parent_ == &root); assert(d.__left_ == &c); assert(d.__right_ == &f); - assert(d.__is_black_ == true); + assert(d.__color_ == std::__tree_color::__black); assert(c.__parent_ == &d); assert(c.__left_ == 0); assert(c.__right_ == 0); - assert(c.__is_black_ == true); + assert(c.__color_ == std::__tree_color::__black); assert(f.__parent_ == &d); assert(f.__left_ == &e); assert(f.__right_ == &g); - assert(f.__is_black_ == false); + assert(f.__color_ == std::__tree_color::__red); assert(e.__parent_ == &f); assert(e.__left_ == 0); assert(e.__right_ == 0); - assert(e.__is_black_ == true); + assert(e.__color_ == std::__tree_color::__black); assert(g.__parent_ == &f); assert(g.__left_ == 0); assert(g.__right_ == &h); - assert(g.__is_black_ == true); + assert(g.__color_ == std::__tree_color::__black); assert(h.__parent_ == &g); assert(h.__left_ == 0); assert(h.__right_ == 0); - assert(h.__is_black_ == false); + assert(h.__color_ == std::__tree_color::__red); std::__tree_remove(root.__left_, &c); @@ -1511,32 +1515,32 @@ void test4() { assert(root.__parent_ == 0); assert(root.__left_ == &f); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(f.__parent_ == &root); assert(f.__left_ == &d); assert(f.__right_ == &g); - assert(f.__is_black_ == true); + assert(f.__color_ == std::__tree_color::__black); assert(d.__parent_ == &f); assert(d.__left_ == 0); assert(d.__right_ == &e); - assert(d.__is_black_ == true); + assert(d.__color_ == std::__tree_color::__black); assert(g.__parent_ == &f); assert(g.__left_ == 0); assert(g.__right_ == &h); - assert(g.__is_black_ == true); + assert(g.__color_ == std::__tree_color::__black); assert(e.__parent_ == &d); assert(e.__left_ == 0); assert(e.__right_ == 0); - assert(e.__is_black_ == false); + assert(e.__color_ == std::__tree_color::__red); assert(h.__parent_ == &g); assert(h.__left_ == 0); assert(h.__right_ == 0); - assert(h.__is_black_ == false); + assert(h.__color_ == std::__tree_color::__red); std::__tree_remove(root.__left_, &d); @@ -1545,27 +1549,27 @@ void test4() { assert(root.__parent_ == 0); assert(root.__left_ == &f); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(f.__parent_ == &root); assert(f.__left_ == &e); assert(f.__right_ == &g); - assert(f.__is_black_ == true); + assert(f.__color_ == std::__tree_color::__black); assert(e.__parent_ == &f); assert(e.__left_ == 0); assert(e.__right_ == 0); - assert(e.__is_black_ == true); + assert(e.__color_ == std::__tree_color::__black); assert(g.__parent_ == &f); assert(g.__left_ == 0); assert(g.__right_ == &h); - assert(g.__is_black_ == true); + assert(g.__color_ == std::__tree_color::__black); assert(h.__parent_ == &g); assert(h.__left_ == 0); assert(h.__right_ == 0); - assert(h.__is_black_ == false); + assert(h.__color_ == std::__tree_color::__red); std::__tree_remove(root.__left_, &e); @@ -1574,22 +1578,22 @@ void test4() { assert(root.__parent_ == 0); assert(root.__left_ == &g); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(g.__parent_ == &root); assert(g.__left_ == &f); assert(g.__right_ == &h); - assert(g.__is_black_ == true); + assert(g.__color_ == std::__tree_color::__black); assert(f.__parent_ == &g); assert(f.__left_ == 0); assert(f.__right_ == 0); - assert(f.__is_black_ == true); + assert(f.__color_ == std::__tree_color::__black); assert(h.__parent_ == &g); assert(h.__left_ == 0); assert(h.__right_ == 0); - assert(h.__is_black_ == true); + assert(h.__color_ == std::__tree_color::__black); std::__tree_remove(root.__left_, &f); @@ -1598,17 +1602,17 @@ void test4() { assert(root.__parent_ == 0); assert(root.__left_ == &g); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(g.__parent_ == &root); assert(g.__left_ == 0); assert(g.__right_ == &h); - assert(g.__is_black_ == true); + assert(g.__color_ == std::__tree_color::__black); assert(h.__parent_ == &g); assert(h.__left_ == 0); assert(h.__right_ == 0); - assert(h.__is_black_ == false); + assert(h.__color_ == std::__tree_color::__red); std::__tree_remove(root.__left_, &g); @@ -1617,12 +1621,12 @@ void test4() { assert(root.__parent_ == 0); assert(root.__left_ == &h); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); assert(h.__parent_ == &root); assert(h.__left_ == 0); assert(h.__right_ == 0); - assert(h.__is_black_ == true); + assert(h.__color_ == std::__tree_color::__black); std::__tree_remove(root.__left_, &h); @@ -1631,7 +1635,7 @@ void test4() { assert(root.__parent_ == 0); assert(root.__left_ == 0); assert(root.__right_ == 0); - assert(root.__is_black_ == false); + assert(root.__color_ == std::__tree_color::__red); } int main(int, char**) { diff --git a/libcxx/test/libcxx/containers/associative/tree_right_rotate.pass.cpp b/libcxx/test/libcxx/containers/associative/tree_right_rotate.pass.cpp index f3297de..1084445 100644 --- a/libcxx/test/libcxx/containers/associative/tree_right_rotate.pass.cpp +++ b/libcxx/test/libcxx/containers/associative/tree_right_rotate.pass.cpp @@ -25,6 +25,7 @@ struct Node { Node* __parent_unsafe() const { return __parent_; } void __set_parent(Node* x) { __parent_ = x; } + Node* __get_parent() { return __parent_; } Node() : __left_(), __right_(), __parent_() {} }; |