YSTest: tree.cpp 源文件

YSTest PreAlpha_b900_20201012 The YSLib Test Project

tree.cpp
浏览该文件的文档.
1 /*
2 © 2018, 2020 FrankHB.
3
4 This file is part of the YSLib project, and may only be used,
5 modified, and distributed under the terms of the YSLib project
6 license, LICENSE.TXT. By continuing to use, modify, or distribute
7 this file you indicate that you have read the license and
8 understand and accept it fully.
9 */
10
28 #include "ystdex/tree.h"
29
30 namespace ystdex
31 {
32
33 namespace details
34 {
35
36 inline namespace rb_tree
37 {
38
40 namespace
41 {
42
43 YB_PURE tree_node_base*
44 local_tree_increment(tree_node_base* x) ynothrow
45 {
46 if(x->right)
47 {
48 x = x->right;
49 while(x->left)
50 x = x->left;
51 }
52 else
53 {
54 auto y(x->parent);
55
56 while(x == y->right)
57 {
58 x = y;
59 y = y->parent;
60 }
61 if(x->right != y)
62 x = y;
63 }
64 return x;
65 }
66
67 YB_PURE tree_node_base*
68 local_tree_decrement(tree_node_base* x) ynothrow
69 {
70 if(x->color == tree_color::red && x->parent->parent == x)
71 x = x->right;
72 else if(x->left)
73 {
74 auto y(x->left);
75
76 while(y->right)
77 y = y->right;
78 x = y;
79 }
80 else
81 {
82 auto y(x->parent);
83
84 while(x == y->left)
85 {
86 x = y;
87 y = y->parent;
88 }
89 x = y;
90 }
91 return x;
92 }
93
94 void
95 local_tree_rotate_left(tree_node_base* x, tree_node_base*& root)
96 {
97 const auto y = x->right;
98
99 x->right = y->left;
100 if(y->left)
101 y->left->parent = x;
102 y->parent = x->parent;
103 if(x == root)
104 root = y;
105 else if(x == x->parent->left)
106 x->parent->left = y;
107 else
108 x->parent->right = y;
109 y->left = x;
110 x->parent = y;
111 }
112
113 void
114 local_tree_rotate_right(tree_node_base* x, tree_node_base*& root)
115 {
116 const auto y = x->left;
117
118 x->left = y->right;
119 if(y->right)
120 y->right->parent = x;
121 y->parent = x->parent;
122 if(x == root)
123 root = y;
124 else if(x == x->parent->right)
125 x->parent->right = y;
126 else
127 x->parent->left = y;
128 y->right = x;
129 x->parent = y;
130 }
131
132 } // unnamed namespace;
133
134
135 tree_node_base*
136 tree_increment(tree_node_base* x) ynothrow
137 {
138 return local_tree_increment(x);
139 }
140 const tree_node_base*
141 tree_increment(const tree_node_base* x) ynothrow
142 {
143 return local_tree_increment(const_cast< tree_node_base*>(x));
144 }
145
146 tree_node_base*
147 tree_decrement(tree_node_base* x) ynothrow
148 {
149 return local_tree_decrement(x);
150 }
151 const tree_node_base*
152 tree_decrement(const tree_node_base* x) ynothrow
153 {
154 return local_tree_decrement(const_cast< tree_node_base*>(x));
155 }
156
157 void
158 tree_insert_and_rebalance(bool insert_left, tree_node_base* x,
159 tree_node_base* p, tree_node_base& header) ynothrow
160 {
161 auto& root(header.parent);
162
163 // XXX: Initialized here for new node.
164 x->parent = p;
165 x->left = {};
166 x->right = {};
167 x->color = tree_color::red;
168
169 // NOTE: Make new node child of parent and maintain root, leftmost and
170 // rightmost nodes. First node is always inserted left.
171 if(insert_left)
172 {
173 // NOTE: Also makes leftmost = x when 'p == &header'.
174 p->left = x;
175 if(p == &header)
176 {
177 header.parent = x;
178 header.right = x;
179 }
180 else if(p == header.left)
181 header.left = x;
182 }
183 else
184 {
185 p->right = x;
186 if(p == header.right)
187 header.right = x;
188 }
189 // NOTE: Rebalance.
190 while(x != root && x->parent->color == tree_color::red)
191 {
192 const auto xpp(x->parent->parent);
193
194 if(x->parent == xpp->left)
195 {
196 const auto y(xpp->right);
197
198 if(y && y->color == tree_color::red)
199 {
200 x->parent->color = tree_color::black;
201 y->color = tree_color::black;
202 xpp->color = tree_color::red;
203 x = xpp;
204 }
205 else
206 {
207 if(x == x->parent->right)
208 {
209 x = x->parent;
210 local_tree_rotate_left(x, root);
211 }
212 x->parent->color = tree_color::black;
213 xpp->color = tree_color::red;
214 local_tree_rotate_right(xpp, root);
215 }
216 }
217 else
218 {
219 const auto y(xpp->left);
220
221 if(y && y->color == tree_color::red)
222 {
223 x->parent->color = tree_color::black;
224 y->color = tree_color::black;
225 xpp->color = tree_color::red;
226 x = xpp;
227 }
228 else
229 {
230 if(x == x->parent->left)
231 {
232 x = x->parent;
233 local_tree_rotate_right(x, root);
234 }
235 x->parent->color = tree_color::black;
236 xpp->color = tree_color::red;
237 local_tree_rotate_left(xpp, root);
238 }
239 }
240 }
241 root->color = tree_color::black;
242 }
243
244 tree_node_base*
245 tree_rebalance_for_erase(tree_node_base* z, tree_node_base& header) ynothrow
246 {
247 auto& root(header.parent);
248 auto& leftmost(header.left);
249 auto& rightmost(header.right);
250 auto y(z);
251 tree_node_base* x{};
252 tree_node_base* x_parent{};
253
254 if(!y->left)
255 x = y->right;
256 else if(!y->right)
257 x = y->left;
258 else
259 {
260 y = y->right;
261 while(y->left)
262 y = y->left;
263 x = y->right;
264 }
265 if(y != z)
266 {
267 z->left->parent = y;
268 y->left = z->left;
269 if(y != z->right)
270 {
271 x_parent = y->parent;
272 if(x)
273 x->parent = y->parent;
274 y->parent->left = x;
275 y->right = z->right;
276 z->right->parent = y;
277 }
278 else
279 x_parent = y;
280 if(root == z)
281 root = y;
282 else if(z->parent->left == z)
283 z->parent->left = y;
284 else
285 z->parent->right = y;
286 y->parent = z->parent;
287 std::swap(y->color, z->color);
288 y = z;
289 }
290 else
291 {
292 x_parent = y->parent;
293 if(x)
294 x->parent = y->parent;
295 if(root == z)
296 root = x;
297 else if(z->parent->left == z)
298 z->parent->left = x;
299 else
300 z->parent->right = x;
301 if(leftmost == z)
302 leftmost = !z->right ? z->parent : tree_node_base::minimum(x);
303 if(rightmost == z)
304 rightmost = !z->left ? z->parent : tree_node_base::maximum(x);
305 }
306 if(y->color != tree_color::red)
307 {
308 while(x != root && (!x|| x->color == tree_color::black))
309 if(x == x_parent->left)
310 {
311 tree_node_base* w = x_parent->right;
312 if(w->color == tree_color::red)
313 {
314 w->color = tree_color::black;
315 x_parent->color = tree_color::red;
316 local_tree_rotate_left(x_parent, root);
317 w = x_parent->right;
318 }
319 if((!w->left || w->left->color == tree_color::black)
320 && (!w->right || w->right->color == tree_color::black))
321 {
322 w->color = tree_color::red;
323 x = x_parent;
324 x_parent = x_parent->parent;
325 }
326 else
327 {
328 if(!w->right || w->right->color == tree_color::black)
329 {
330 w->left->color = tree_color::black;
331 w->color = tree_color::red;
332 local_tree_rotate_right(w, root);
333 w = x_parent->right;
334 }
335 w->color = x_parent->color;
336 x_parent->color = tree_color::black;
337 if(w->right)
338 w->right->color = tree_color::black;
339 local_tree_rotate_left(x_parent, root);
340 break;
341 }
342 }
343 else
344 {
345 tree_node_base* w = x_parent->left;
346 if(w->color == tree_color::red)
347 {
348 w->color = tree_color::black;
349 x_parent->color = tree_color::red;
350 local_tree_rotate_right(x_parent, root);
351 w = x_parent->left;
352 }
353 if((!w->right || w->right->color == tree_color::black)
354 && (!w->left
355 || w->left->color == tree_color::black))
356 {
357 w->color = tree_color::red;
358 x = x_parent;
359 x_parent = x_parent->parent;
360 }
361 else
362 {
363 if(!w->left || w->left->color == tree_color::black)
364 {
365 w->right->color = tree_color::black;
366 w->color = tree_color::red;
367 local_tree_rotate_left(w, root);
368 w = x_parent->left;
369 }
370 w->color = x_parent->color;
371 x_parent->color = tree_color::black;
372 if(w->left)
373 w->left->color = tree_color::black;
374 local_tree_rotate_right(x_parent, root);
375 break;
376 }
377 }
378 if(x)
379 x->color = tree_color::black;
380 }
381 return y;
382 }
383
384 size_t
385 tree_black_count(const tree_node_base* node, const tree_node_base* root)
386 ynothrow
387 {
388 if(node)
389 {
390 size_t sum(0);
391
392 while([&]{
393 if(node->color == tree_color::black)
394 ++sum;
395 return node != root;
396 }())
397 node = node->parent;
398 return sum;
399 }
400 return 0;
401 }
402
403 } // inline namespace rb_tree;
404
405 } // namespace details;
406
407 } // namespace ystdex;
408
x
const EncapsulationBase & x
Definition: NPLA1Forms.cpp:1536
ystdex::cpp2017::swap
void swap(optional< _type > &x, optional< _type > &y)
Definition: optional.h:888
ystdex::details::rb_tree::tree_black_count
size_t tree_black_count(const tree_node_base *, const tree_node_base *)
Definition: tree.cpp:385
YB_PURE
#define YB_PURE
指示函数或函数模板实例为纯函数。
Definition: ydef.h:919
ystdex::details::rb_tree::tree_node_base
Definition: tree.h:354
ystdex::details::rb_tree::tree_rebalance_for_erase
tree_node_base * tree_rebalance_for_erase(tree_node_base *, tree_node_base &)
Definition: tree.cpp:245
ystdex::details::rb_tree::tree_color::red
@ red
ystdex::details::rb_tree::tree_node_base::minimum
static base_ptr minimum(base_ptr x)
Definition: tree.h:378
YSLib::UI::y
SPos SPos y
Definition: YWidget.cpp:44
tree.h
作为关联容器实现的树。
ystdex::details::rb_tree::tree_increment
tree_node_base * tree_increment(tree_node_base *)
Definition: tree.cpp:136
ystdex::details::rb_tree::tree_decrement
tree_node_base * tree_decrement(tree_node_base *)
Definition: tree.cpp:147
ystdex
<memory> 特性测试宏。
Definition: ydef.h:1262
YSLib::Drawing::w
The boundary is out of the const Rect SDst w
Definition: YDraw.h:127
ystdex::details::rb_tree::tree_color::black
@ black
platform::p
return p p
Definition: YCLib/FileSystem.h:209
ystdex::path_category::node
@ node
ystdex::details::rb_tree::tree_node_base::maximum
static base_ptr maximum(base_ptr x)
Definition: tree.h:363
ynothrow
#define ynothrow
YSLib 无异常抛出保证：若支持 noexcept 关键字， 指定特定的 noexcept 异常规范。
Definition: ydef.h:1199
ystdex::details::rb_tree::tree_insert_and_rebalance
void tree_insert_and_rebalance(bool, tree_node_base *, tree_node_base *, tree_node_base &)
Definition: tree.cpp:158