Lines Matching refs:__x
61 // Returns: true if __x is a left child of its parent, else false
62 // Precondition: __x != nullptr.
66 __tree_is_left_child(_NodePtr __x) _NOEXCEPT
68 return __x == __x->__parent_->__left_;
71 // Determintes if the subtree rooted at __x is a proper red black subtree. If
72 // __x is a proper subtree, returns the black height (null counts as 1). If
73 // __x is an improper subtree, returns 0.
76 __tree_sub_invariant(_NodePtr __x)
78 if (__x == nullptr)
81 // check __x->__left_ consistency
82 if (__x->__left_ != nullptr && __x->__left_->__parent_ != __x)
84 // check __x->__right_ consistency
85 if (__x->__right_ != nullptr && __x->__right_->__parent_ != __x)
87 // check __x->__left_ != __x->__right_ unless both are nullptr
88 if (__x->__left_ == __x->__right_ && __x->__left_ != nullptr)
91 if (!__x->__is_black_)
93 if (__x->__left_ && !__x->__left_->__is_black_)
95 if (__x->__right_ && !__x->__right_->__is_black_)
98 unsigned __h = __tree_sub_invariant(__x->__left_);
101 if (__h != __tree_sub_invariant(__x->__right_))
103 return __h + __x->__is_black_; // return black height of this node
115 // check __x->__parent_ consistency
127 // Returns: pointer to the left-most node under __x.
128 // Precondition: __x != nullptr.
132 __tree_min(_NodePtr __x) _NOEXCEPT
134 while (__x->__left_ != nullptr)
135 __x = __x->__left_;
136 return __x;
139 // Returns: pointer to the right-most node under __x.
140 // Precondition: __x != nullptr.
144 __tree_max(_NodePtr __x) _NOEXCEPT
146 while (__x->__right_ != nullptr)
147 __x = __x->__right_;
148 return __x;
151 // Returns: pointer to the next in-order node after __x.
152 // Precondition: __x != nullptr.
155 __tree_next(_NodePtr __x) _NOEXCEPT
157 if (__x->__right_ != nullptr)
158 return __tree_min(__x->__right_);
159 while (!__tree_is_left_child(__x))
160 __x = __x->__parent_;
161 return __x->__parent_;
164 // Returns: pointer to the previous in-order node before __x.
165 // Precondition: __x != nullptr.
168 __tree_prev(_NodePtr __x) _NOEXCEPT
170 if (__x->__left_ != nullptr)
171 return __tree_max(__x->__left_);
172 while (__tree_is_left_child(__x))
173 __x = __x->__parent_;
174 return __x->__parent_;
178 // Precondition: __x != nullptr.
181 __tree_leaf(_NodePtr __x) _NOEXCEPT
185 if (__x->__left_ != nullptr)
187 __x = __x->__left_;
190 if (__x->__right_ != nullptr)
192 __x = __x->__right_;
197 return __x;
200 // Effects: Makes __x->__right_ the subtree root with __x as its left child
202 // Precondition: __x->__right_ != nullptr
205 __tree_left_rotate(_NodePtr __x) _NOEXCEPT
207 _NodePtr __y = __x->__right_;
208 __x->__right_ = __y->__left_;
209 if (__x->__right_ != nullptr)
210 __x->__right_->__parent_ = __x;
211 __y->__parent_ = __x->__parent_;
212 if (__tree_is_left_child(__x))
213 __x->__parent_->__left_ = __y;
215 __x->__parent_->__right_ = __y;
216 __y->__left_ = __x;
217 __x->__parent_ = __y;
220 // Effects: Makes __x->__left_ the subtree root with __x as its right child
222 // Precondition: __x->__left_ != nullptr
225 __tree_right_rotate(_NodePtr __x) _NOEXCEPT
227 _NodePtr __y = __x->__left_;
228 __x->__left_ = __y->__right_;
229 if (__x->__left_ != nullptr)
230 __x->__left_->__parent_ = __x;
231 __y->__parent_ = __x->__parent_;
232 if (__tree_is_left_child(__x))
233 __x->__parent_->__left_ = __y;
235 __x->__parent_->__right_ = __y;
236 __y->__right_ = __x;
237 __x->__parent_ = __y;
240 // Effects: Rebalances __root after attaching __x to a leaf.
241 // Precondition: __root != nulptr && __x != nullptr.
242 // __x has no children.
243 // __x == __root or == a direct or indirect child of __root.
244 // If __x were to be unlinked from __root (setting __root to
245 // nullptr if __root == __x), __tree_invariant(__root) == true.
250 __tree_balance_after_insert(_NodePtr __root, _NodePtr __x) _NOEXCEPT
252 __x->__is_black_ = __x == __root;
253 while (__x != __root && !__x->__parent_->__is_black_)
255 // __x->__parent_ != __root because __x->__parent_->__is_black == false
256 if (__tree_is_left_child(__x->__parent_))
258 _NodePtr __y = __x->__parent_->__parent_->__right_;
261 __x = __x->__parent_;
262 __x->__is_black_ = true;
263 __x = __x->__parent_;
264 __x->__is_black_ = __x == __root;
269 if (!__tree_is_left_child(__x))
271 __x = __x->__parent_;
272 __tree_left_rotate(__x);
274 __x = __x->__parent_;
275 __x->__is_black_ = true;
276 __x = __x->__parent_;
277 __x->__is_black_ = false;
278 __tree_right_rotate(__x);
284 _NodePtr __y = __x->__parent_->__parent_->__left_;
287 __x = __x->__parent_;
288 __x->__is_black_ = true;
289 __x = __x->__parent_;
290 __x->__is_black_ = __x == __root;
295 if (__tree_is_left_child(__x))
297 __x = __x->__parent_;
298 __tree_right_rotate(__x);
300 __x = __x->__parent_;
301 __x->__is_black_ = true;
302 __x = __x->__parent_;
303 __x->__is_black_ = false;
304 __tree_left_rotate(__x);
328 // __x is __y's possibly null single child
329 _NodePtr __x = __y->__left_ != nullptr ? __y->__left_ : __y->__right_;
330 // __w is __x's possibly null uncle (will become __x's sibling)
332 // link __x to __y's parent, and find __w
333 if (__x != nullptr)
334 __x->__parent_ = __y->__parent_;
337 __y->__parent_->__left_ = __x;
341 __root = __x; // __w == nullptr
345 __y->__parent_->__right_ = __x;
351 // but copy __z's color. This does not impact __x or __w.
354 // __z->__left_ != nulptr but __z->__right_ might == __x == nullptr
374 // __x has an implicit black color (transferred from the removed __y)
376 // If __x is __root (in which case it can't be null), it is supposed
379 // If __x is red (in which case it can't be null), then it can absorb
381 // Since __y was black and only had one child (which __x points to), __x
384 // if (__x == __root || __x != nullptr && !__x->__is_black_)
385 if (__x != nullptr)
386 __x->__is_black_ = true;
389 // Else __x isn't root, and is "doubly black", even though it may
391 // see a black height >= 2 on the __x side and a black height
403 // __x is still valid
415 __x = __w->__parent_;
416 // __x can no longer be null
417 if (__x == __root || !__x->__is_black_)
419 __x->__is_black_ = true;
423 __w = __tree_is_left_child(__x) ?
424 __x->__parent_->__right_ :
425 __x->__parent_->__left_;
455 // __x is still valid
467 __x = __w->__parent_;
468 // __x can no longer be null
469 if (!__x->__is_black_ || __x == __root)
471 __x->__is_black_ = true;
475 __w = __tree_is_left_child(__x) ?
476 __x->__parent_->__right_ :
477 __x->__parent_->__left_;
673 bool operator==(const __tree_iterator& __x, const __tree_iterator& __y)
674 {return __x.__ptr_ == __y.__ptr_;}
676 bool operator!=(const __tree_iterator& __x, const __tree_iterator& __y)
677 {return !(__x == __y);}
778 bool operator==(const __tree_const_iterator& __x, const __tree_const_iterator& __y)
779 {return __x.__ptr_ == __y.__ptr_;}
781 bool operator!=(const __tree_const_iterator& __x, const __tree_const_iterator& __y)
782 {return !(__x == __y);}
2296 swap(__tree<_Tp, _Compare, _Allocator>& __x,
2298 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
2300 __x.swap(__y);