]>
Commit | Line | Data |
---|---|---|
42526146 PE |
1 | // RB tree implementation -*- C++ -*- |
2 | ||
00532602 | 3 | // Copyright (C) 2001, 2002 Free Software Foundation, Inc. |
42526146 PE |
4 | // |
5 | // This file is part of the GNU ISO C++ Library. This library is free | |
6 | // software; you can redistribute it and/or modify it under the | |
7 | // terms of the GNU General Public License as published by the | |
8 | // Free Software Foundation; either version 2, or (at your option) | |
9 | // any later version. | |
10 | ||
11 | // This library is distributed in the hope that it will be useful, | |
12 | // but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
14 | // GNU General Public License for more details. | |
15 | ||
16 | // You should have received a copy of the GNU General Public License along | |
17 | // with this library; see the file COPYING. If not, write to the Free | |
18 | // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, | |
19 | // USA. | |
20 | ||
21 | // As a special exception, you may use this file as part of a free software | |
22 | // library without restriction. Specifically, if other files instantiate | |
23 | // templates or use macros or inline functions from this file, or you compile | |
24 | // this file and link it with other files to produce an executable, this | |
25 | // file does not by itself cause the resulting executable to be covered by | |
26 | // the GNU General Public License. This exception does not however | |
27 | // invalidate any other reasons why the executable file might be covered by | |
28 | // the GNU General Public License. | |
29 | ||
725dc051 BK |
30 | /* |
31 | * | |
32 | * Copyright (c) 1996,1997 | |
33 | * Silicon Graphics Computer Systems, Inc. | |
34 | * | |
35 | * Permission to use, copy, modify, distribute and sell this software | |
36 | * and its documentation for any purpose is hereby granted without fee, | |
37 | * provided that the above copyright notice appear in all copies and | |
38 | * that both that copyright notice and this permission notice appear | |
39 | * in supporting documentation. Silicon Graphics makes no | |
40 | * representations about the suitability of this software for any | |
41 | * purpose. It is provided "as is" without express or implied warranty. | |
42 | * | |
43 | * | |
44 | * Copyright (c) 1994 | |
45 | * Hewlett-Packard Company | |
46 | * | |
47 | * Permission to use, copy, modify, distribute and sell this software | |
48 | * and its documentation for any purpose is hereby granted without fee, | |
49 | * provided that the above copyright notice appear in all copies and | |
50 | * that both that copyright notice and this permission notice appear | |
51 | * in supporting documentation. Hewlett-Packard Company makes no | |
52 | * representations about the suitability of this software for any | |
53 | * purpose. It is provided "as is" without express or implied warranty. | |
54 | * | |
55 | * | |
56 | */ | |
57 | ||
729e3d3f PE |
58 | /** @file stl_tree.h |
59 | * This is an internal header file, included by other library headers. | |
60 | * You should not attempt to use it directly. | |
725dc051 BK |
61 | */ |
62 | ||
9d6a24bd PE |
63 | #ifndef __GLIBCPP_INTERNAL_TREE_H |
64 | #define __GLIBCPP_INTERNAL_TREE_H | |
725dc051 BK |
65 | |
66 | /* | |
67 | ||
68 | Red-black tree class, designed for use in implementing STL | |
69 | associative containers (set, multiset, map, and multimap). The | |
70 | insertion and deletion algorithms are based on those in Cormen, | |
71 | Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 1990), | |
72 | except that | |
73 | ||
74 | (1) the header cell is maintained with links not only to the root | |
75 | but also to the leftmost node of the tree, to enable constant time | |
76 | begin(), and to the rightmost node of the tree, to enable linear time | |
77 | performance when used with the generic set algorithms (set_union, | |
78 | etc.); | |
79 | ||
80 | (2) when a node being deleted has two children its successor node is | |
81 | relinked into its place, rather than copied, so that the only | |
82 | iterators invalidated are those referring to the deleted node. | |
83 | ||
84 | */ | |
85 | ||
86 | #include <bits/stl_algobase.h> | |
87 | #include <bits/stl_alloc.h> | |
88 | #include <bits/stl_construct.h> | |
89 | #include <bits/stl_function.h> | |
90 | ||
d53d7f6e PE |
91 | namespace std |
92 | { | |
d3d526ac | 93 | enum _Rb_tree_color { _M_red = false, _M_black = true }; |
725dc051 | 94 | |
d3d526ac BK |
95 | struct _Rb_tree_node_base |
96 | { | |
97 | typedef _Rb_tree_node_base* _Base_ptr; | |
98 | ||
99 | _Rb_tree_color _M_color; | |
100 | _Base_ptr _M_parent; | |
101 | _Base_ptr _M_left; | |
102 | _Base_ptr _M_right; | |
103 | ||
104 | static _Base_ptr | |
105 | _S_minimum(_Base_ptr __x) | |
106 | { | |
107 | while (__x->_M_left != 0) __x = __x->_M_left; | |
108 | return __x; | |
109 | } | |
725dc051 | 110 | |
d3d526ac BK |
111 | static _Base_ptr |
112 | _S_maximum(_Base_ptr __x) | |
113 | { | |
114 | while (__x->_M_right != 0) __x = __x->_M_right; | |
115 | return __x; | |
116 | } | |
117 | }; | |
725dc051 | 118 | |
d3d526ac BK |
119 | template<typename _Val> |
120 | struct _Rb_tree_node : public _Rb_tree_node_base | |
121 | { | |
122 | typedef _Rb_tree_node<_Val>* _Link_type; | |
123 | _Val _M_value_field; | |
124 | }; | |
125 | ||
126 | struct _Rb_tree_base_iterator | |
725dc051 | 127 | { |
d3d526ac BK |
128 | typedef _Rb_tree_node_base::_Base_ptr _Base_ptr; |
129 | typedef bidirectional_iterator_tag iterator_category; | |
130 | typedef ptrdiff_t difference_type; | |
131 | ||
132 | _Base_ptr _M_node; | |
133 | ||
134 | void | |
135 | _M_increment() | |
136 | { | |
137 | if (_M_node->_M_right != 0) | |
138 | { | |
139 | _M_node = _M_node->_M_right; | |
140 | while (_M_node->_M_left != 0) | |
141 | _M_node = _M_node->_M_left; | |
142 | } | |
143 | else | |
144 | { | |
145 | _Base_ptr __y = _M_node->_M_parent; | |
146 | while (_M_node == __y->_M_right) | |
147 | { | |
148 | _M_node = __y; | |
149 | __y = __y->_M_parent; | |
150 | } | |
151 | if (_M_node->_M_right != __y) | |
152 | _M_node = __y; | |
153 | } | |
154 | } | |
155 | ||
156 | void | |
157 | _M_decrement() | |
158 | { | |
159 | if (_M_node->_M_color == _M_red | |
160 | && _M_node->_M_parent->_M_parent == _M_node) | |
161 | _M_node = _M_node->_M_right; | |
162 | else if (_M_node->_M_left != 0) | |
163 | { | |
164 | _Base_ptr __y = _M_node->_M_left; | |
165 | while (__y->_M_right != 0) | |
166 | __y = __y->_M_right; | |
167 | _M_node = __y; | |
168 | } | |
169 | else | |
170 | { | |
171 | _Base_ptr __y = _M_node->_M_parent; | |
172 | while (_M_node == __y->_M_left) | |
173 | { | |
174 | _M_node = __y; | |
175 | __y = __y->_M_parent; | |
176 | } | |
177 | _M_node = __y; | |
178 | } | |
179 | } | |
180 | }; | |
181 | ||
182 | template<typename _Val, typename _Ref, typename _Ptr> | |
183 | struct _Rb_tree_iterator : public _Rb_tree_base_iterator | |
184 | { | |
185 | typedef _Val value_type; | |
186 | typedef _Ref reference; | |
187 | typedef _Ptr pointer; | |
188 | typedef _Rb_tree_iterator<_Val, _Val&, _Val*> iterator; | |
189 | typedef _Rb_tree_iterator<_Val, const _Val&, const _Val*> | |
190 | const_iterator; | |
191 | typedef _Rb_tree_iterator<_Val, _Ref, _Ptr> _Self; | |
192 | typedef _Rb_tree_node<_Val>* _Link_type; | |
193 | ||
194 | _Rb_tree_iterator() {} | |
195 | _Rb_tree_iterator(_Link_type __x) { _M_node = __x; } | |
196 | _Rb_tree_iterator(const iterator& __it) { _M_node = __it._M_node; } | |
197 | ||
198 | reference | |
199 | operator*() const { return _Link_type(_M_node)->_M_value_field; } | |
200 | ||
201 | pointer | |
202 | operator->() const { return &(operator*()); } | |
203 | ||
204 | _Self& | |
205 | operator++() | |
206 | { | |
207 | _M_increment(); | |
208 | return *this; | |
209 | } | |
725dc051 | 210 | |
d3d526ac BK |
211 | _Self |
212 | operator++(int) | |
213 | { | |
214 | _Self __tmp = *this; | |
215 | _M_increment(); | |
216 | return __tmp; | |
217 | } | |
218 | ||
219 | _Self& | |
220 | operator--() { _M_decrement(); return *this; } | |
221 | ||
222 | _Self | |
223 | operator--(int) | |
224 | { | |
225 | _Self __tmp = *this; | |
226 | _M_decrement(); | |
227 | return __tmp; | |
228 | } | |
229 | }; | |
230 | ||
231 | template<typename _Val, typename _Ref, typename _Ptr> | |
232 | inline bool | |
233 | operator==(const _Rb_tree_iterator<_Val, _Ref, _Ptr>& __x, | |
234 | const _Rb_tree_iterator<_Val, _Ref, _Ptr>& __y) | |
235 | { return __x._M_node == __y._M_node; } | |
236 | ||
237 | template<typename _Val> | |
238 | inline bool | |
239 | operator==(const _Rb_tree_iterator<_Val, const _Val&, const _Val*>& __x, | |
240 | const _Rb_tree_iterator<_Val, _Val&, _Val*>& __y) | |
241 | { return __x._M_node == __y._M_node; } | |
242 | ||
243 | template<typename _Val> | |
244 | inline bool | |
245 | operator==(const _Rb_tree_iterator<_Val, _Val&, _Val*>& __x, | |
246 | const _Rb_tree_iterator<_Val, const _Val&, const _Val*>& __y) | |
247 | { return __x._M_node == __y._M_node; } | |
248 | ||
249 | template<typename _Val, typename _Ref, typename _Ptr> | |
250 | inline bool | |
251 | operator!=(const _Rb_tree_iterator<_Val, _Ref, _Ptr>& __x, | |
252 | const _Rb_tree_iterator<_Val, _Ref, _Ptr>& __y) | |
253 | { return __x._M_node != __y._M_node; } | |
254 | ||
255 | template<typename _Val> | |
256 | inline bool | |
257 | operator!=(const _Rb_tree_iterator<_Val, const _Val&, const _Val*>& __x, | |
258 | const _Rb_tree_iterator<_Val, _Val&, _Val*>& __y) | |
259 | { return __x._M_node != __y._M_node; } | |
260 | ||
261 | template<typename _Val> | |
262 | inline bool | |
263 | operator!=(const _Rb_tree_iterator<_Val, _Val&, _Val*>& __x, | |
264 | const _Rb_tree_iterator<_Val, const _Val&, const _Val*>& __y) | |
265 | { return __x._M_node != __y._M_node; } | |
266 | ||
267 | inline void | |
268 | _Rb_tree_rotate_left(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root) | |
725dc051 | 269 | { |
d3d526ac BK |
270 | _Rb_tree_node_base* __y = __x->_M_right; |
271 | __x->_M_right = __y->_M_left; | |
272 | if (__y->_M_left !=0) | |
273 | __y->_M_left->_M_parent = __x; | |
274 | __y->_M_parent = __x->_M_parent; | |
275 | ||
276 | if (__x == __root) | |
277 | __root = __y; | |
278 | else if (__x == __x->_M_parent->_M_left) | |
279 | __x->_M_parent->_M_left = __y; | |
280 | else | |
281 | __x->_M_parent->_M_right = __y; | |
282 | __y->_M_left = __x; | |
283 | __x->_M_parent = __y; | |
725dc051 | 284 | } |
725dc051 | 285 | |
d3d526ac BK |
286 | inline void |
287 | _Rb_tree_rotate_right(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root) | |
288 | { | |
289 | _Rb_tree_node_base* __y = __x->_M_left; | |
290 | __x->_M_left = __y->_M_right; | |
291 | if (__y->_M_right != 0) | |
292 | __y->_M_right->_M_parent = __x; | |
293 | __y->_M_parent = __x->_M_parent; | |
725dc051 | 294 | |
d3d526ac BK |
295 | if (__x == __root) |
296 | __root = __y; | |
297 | else if (__x == __x->_M_parent->_M_right) | |
298 | __x->_M_parent->_M_right = __y; | |
299 | else | |
300 | __x->_M_parent->_M_left = __y; | |
301 | __y->_M_right = __x; | |
302 | __x->_M_parent = __y; | |
303 | } | |
725dc051 | 304 | |
d3d526ac BK |
305 | inline void |
306 | _Rb_tree_rebalance(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root) | |
725dc051 | 307 | { |
d3d526ac BK |
308 | __x->_M_color = _M_red; |
309 | while (__x != __root | |
310 | && __x->_M_parent->_M_color == _M_red) | |
311 | { | |
312 | if (__x->_M_parent == __x->_M_parent->_M_parent->_M_left) | |
313 | { | |
314 | _Rb_tree_node_base* __y = __x->_M_parent->_M_parent->_M_right; | |
315 | if (__y && __y->_M_color == _M_red) | |
316 | { | |
317 | __x->_M_parent->_M_color = _M_black; | |
318 | __y->_M_color = _M_black; | |
319 | __x->_M_parent->_M_parent->_M_color = _M_red; | |
320 | __x = __x->_M_parent->_M_parent; | |
321 | } | |
322 | else | |
323 | { | |
324 | if (__x == __x->_M_parent->_M_right) | |
325 | { | |
326 | __x = __x->_M_parent; | |
327 | _Rb_tree_rotate_left(__x, __root); | |
328 | } | |
329 | __x->_M_parent->_M_color = _M_black; | |
330 | __x->_M_parent->_M_parent->_M_color = _M_red; | |
331 | _Rb_tree_rotate_right(__x->_M_parent->_M_parent, __root); | |
332 | } | |
333 | } | |
334 | else | |
335 | { | |
336 | _Rb_tree_node_base* __y = __x->_M_parent->_M_parent->_M_left; | |
337 | if (__y && __y->_M_color == _M_red) | |
338 | { | |
339 | __x->_M_parent->_M_color = _M_black; | |
340 | __y->_M_color = _M_black; | |
341 | __x->_M_parent->_M_parent->_M_color = _M_red; | |
342 | __x = __x->_M_parent->_M_parent; | |
343 | } | |
344 | else | |
345 | { | |
346 | if (__x == __x->_M_parent->_M_left) | |
347 | { | |
348 | __x = __x->_M_parent; | |
349 | _Rb_tree_rotate_right(__x, __root); | |
350 | } | |
351 | __x->_M_parent->_M_color = _M_black; | |
352 | __x->_M_parent->_M_parent->_M_color = _M_red; | |
353 | _Rb_tree_rotate_left(__x->_M_parent->_M_parent, __root); | |
354 | } | |
355 | } | |
725dc051 | 356 | } |
d3d526ac | 357 | __root->_M_color = _M_black; |
725dc051 BK |
358 | } |
359 | ||
d3d526ac BK |
360 | inline _Rb_tree_node_base* |
361 | _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* __z, | |
362 | _Rb_tree_node_base*& __root, | |
363 | _Rb_tree_node_base*& __leftmost, | |
364 | _Rb_tree_node_base*& __rightmost) | |
725dc051 | 365 | { |
d3d526ac BK |
366 | _Rb_tree_node_base* __y = __z; |
367 | _Rb_tree_node_base* __x = 0; | |
368 | _Rb_tree_node_base* __x_parent = 0; | |
369 | if (__y->_M_left == 0) // __z has at most one non-null child. y == z. | |
370 | __x = __y->_M_right; // __x might be null. | |
371 | else | |
372 | if (__y->_M_right == 0) // __z has exactly one non-null child. y == z. | |
373 | __x = __y->_M_left; // __x is not null. | |
374 | else | |
375 | { | |
376 | // __z has two non-null children. Set __y to | |
377 | __y = __y->_M_right; // __z's successor. __x might be null. | |
378 | while (__y->_M_left != 0) | |
379 | __y = __y->_M_left; | |
380 | __x = __y->_M_right; | |
381 | } | |
382 | if (__y != __z) | |
383 | { | |
384 | // relink y in place of z. y is z's successor | |
385 | __z->_M_left->_M_parent = __y; | |
386 | __y->_M_left = __z->_M_left; | |
387 | if (__y != __z->_M_right) | |
388 | { | |
389 | __x_parent = __y->_M_parent; | |
390 | if (__x) __x->_M_parent = __y->_M_parent; | |
391 | __y->_M_parent->_M_left = __x; // __y must be a child of _M_left | |
392 | __y->_M_right = __z->_M_right; | |
393 | __z->_M_right->_M_parent = __y; | |
394 | } | |
395 | else | |
396 | __x_parent = __y; | |
397 | if (__root == __z) | |
398 | __root = __y; | |
399 | else if (__z->_M_parent->_M_left == __z) | |
400 | __z->_M_parent->_M_left = __y; | |
401 | else | |
402 | __z->_M_parent->_M_right = __y; | |
403 | __y->_M_parent = __z->_M_parent; | |
404 | std::swap(__y->_M_color, __z->_M_color); | |
405 | __y = __z; | |
406 | // __y now points to node to be actually deleted | |
725dc051 | 407 | } |
d3d526ac BK |
408 | else |
409 | { // __y == __z | |
410 | __x_parent = __y->_M_parent; | |
411 | if (__x) | |
412 | __x->_M_parent = __y->_M_parent; | |
413 | if (__root == __z) | |
414 | __root = __x; | |
415 | else | |
416 | if (__z->_M_parent->_M_left == __z) | |
417 | __z->_M_parent->_M_left = __x; | |
418 | else | |
419 | __z->_M_parent->_M_right = __x; | |
420 | if (__leftmost == __z) | |
421 | if (__z->_M_right == 0) // __z->_M_left must be null also | |
422 | __leftmost = __z->_M_parent; | |
423 | // makes __leftmost == _M_header if __z == __root | |
424 | else | |
425 | __leftmost = _Rb_tree_node_base::_S_minimum(__x); | |
426 | if (__rightmost == __z) | |
427 | if (__z->_M_left == 0) // __z->_M_right must be null also | |
428 | __rightmost = __z->_M_parent; | |
429 | // makes __rightmost == _M_header if __z == __root | |
430 | else // __x == __z->_M_left | |
431 | __rightmost = _Rb_tree_node_base::_S_maximum(__x); | |
432 | } | |
433 | if (__y->_M_color != _M_red) | |
434 | { | |
435 | while (__x != __root && (__x == 0 || __x->_M_color == _M_black)) | |
436 | if (__x == __x_parent->_M_left) | |
437 | { | |
438 | _Rb_tree_node_base* __w = __x_parent->_M_right; | |
439 | if (__w->_M_color == _M_red) | |
440 | { | |
441 | __w->_M_color = _M_black; | |
442 | __x_parent->_M_color = _M_red; | |
443 | _Rb_tree_rotate_left(__x_parent, __root); | |
444 | __w = __x_parent->_M_right; | |
445 | } | |
446 | if ((__w->_M_left == 0 || | |
447 | __w->_M_left->_M_color == _M_black) && | |
448 | (__w->_M_right == 0 || | |
449 | __w->_M_right->_M_color == _M_black)) | |
450 | { | |
451 | __w->_M_color = _M_red; | |
452 | __x = __x_parent; | |
453 | __x_parent = __x_parent->_M_parent; | |
454 | } | |
455 | else | |
456 | { | |
457 | if (__w->_M_right == 0 | |
458 | || __w->_M_right->_M_color == _M_black) | |
459 | { | |
726a4d6d | 460 | __w->_M_left->_M_color = _M_black; |
d3d526ac BK |
461 | __w->_M_color = _M_red; |
462 | _Rb_tree_rotate_right(__w, __root); | |
463 | __w = __x_parent->_M_right; | |
464 | } | |
465 | __w->_M_color = __x_parent->_M_color; | |
466 | __x_parent->_M_color = _M_black; | |
467 | if (__w->_M_right) | |
468 | __w->_M_right->_M_color = _M_black; | |
469 | _Rb_tree_rotate_left(__x_parent, __root); | |
470 | break; | |
471 | } | |
472 | } | |
473 | else | |
474 | { | |
475 | // same as above, with _M_right <-> _M_left. | |
476 | _Rb_tree_node_base* __w = __x_parent->_M_left; | |
477 | if (__w->_M_color == _M_red) | |
478 | { | |
479 | __w->_M_color = _M_black; | |
480 | __x_parent->_M_color = _M_red; | |
481 | _Rb_tree_rotate_right(__x_parent, __root); | |
482 | __w = __x_parent->_M_left; | |
483 | } | |
484 | if ((__w->_M_right == 0 || | |
485 | __w->_M_right->_M_color == _M_black) && | |
486 | (__w->_M_left == 0 || | |
487 | __w->_M_left->_M_color == _M_black)) | |
488 | { | |
489 | __w->_M_color = _M_red; | |
490 | __x = __x_parent; | |
491 | __x_parent = __x_parent->_M_parent; | |
492 | } | |
493 | else | |
494 | { | |
495 | if (__w->_M_left == 0 || __w->_M_left->_M_color == _M_black) | |
496 | { | |
726a4d6d | 497 | __w->_M_right->_M_color = _M_black; |
d3d526ac BK |
498 | __w->_M_color = _M_red; |
499 | _Rb_tree_rotate_left(__w, __root); | |
500 | __w = __x_parent->_M_left; | |
501 | } | |
502 | __w->_M_color = __x_parent->_M_color; | |
503 | __x_parent->_M_color = _M_black; | |
504 | if (__w->_M_left) | |
505 | __w->_M_left->_M_color = _M_black; | |
506 | _Rb_tree_rotate_right(__x_parent, __root); | |
507 | break; | |
508 | } | |
509 | } | |
510 | if (__x) __x->_M_color = _M_black; | |
511 | } | |
512 | return __y; | |
725dc051 | 513 | } |
d3d526ac BK |
514 | |
515 | // Base class to encapsulate the differences between old SGI-style | |
516 | // allocators and standard-conforming allocators. In order to avoid | |
517 | // having an empty base class, we arbitrarily move one of rb_tree's | |
518 | // data members into the base class. | |
519 | ||
520 | // _Base for general standard-conforming allocators. | |
521 | template<typename _Tp, typename _Alloc, bool _S_instanceless> | |
522 | class _Rb_tree_alloc_base | |
523 | { | |
524 | public: | |
525 | typedef typename _Alloc_traits<_Tp, _Alloc>::allocator_type allocator_type; | |
526 | ||
527 | allocator_type | |
528 | get_allocator() const { return _M_node_allocator; } | |
529 | ||
530 | _Rb_tree_alloc_base(const allocator_type& __a) | |
531 | : _M_node_allocator(__a), _M_header(0) {} | |
532 | ||
533 | protected: | |
534 | typename _Alloc_traits<_Rb_tree_node<_Tp>, _Alloc>::allocator_type | |
535 | _M_node_allocator; | |
536 | ||
537 | _Rb_tree_node<_Tp>* _M_header; | |
538 | ||
539 | _Rb_tree_node<_Tp>* | |
540 | _M_get_node() { return _M_node_allocator.allocate(1); } | |
541 | ||
542 | void | |
543 | _M_put_node(_Rb_tree_node<_Tp>* __p) | |
544 | { _M_node_allocator.deallocate(__p, 1); } | |
545 | }; | |
546 | ||
547 | // Specialization for instanceless allocators. | |
548 | template<typename _Tp, typename _Alloc> | |
549 | class _Rb_tree_alloc_base<_Tp, _Alloc, true> | |
550 | { | |
551 | public: | |
552 | typedef typename _Alloc_traits<_Tp, _Alloc>::allocator_type allocator_type; | |
553 | allocator_type get_allocator() const { return allocator_type(); } | |
554 | ||
555 | _Rb_tree_alloc_base(const allocator_type&) : _M_header(0) {} | |
556 | ||
557 | protected: | |
558 | _Rb_tree_node<_Tp>* _M_header; | |
559 | ||
560 | typedef typename _Alloc_traits<_Rb_tree_node<_Tp>, _Alloc>::_Alloc_type | |
561 | _Alloc_type; | |
562 | ||
563 | _Rb_tree_node<_Tp>* | |
564 | _M_get_node() { return _Alloc_type::allocate(1); } | |
565 | ||
566 | void | |
567 | _M_put_node(_Rb_tree_node<_Tp>* __p) { _Alloc_type::deallocate(__p, 1); } | |
568 | }; | |
569 | ||
570 | template<typename _Tp, typename _Alloc> | |
571 | struct _Rb_tree_base : public _Rb_tree_alloc_base<_Tp, _Alloc, | |
572 | _Alloc_traits<_Tp, _Alloc>::_S_instanceless> | |
573 | { | |
574 | typedef _Rb_tree_alloc_base<_Tp, | |
575 | _Alloc, _Alloc_traits<_Tp, _Alloc>::_S_instanceless> _Base; | |
576 | typedef typename _Base::allocator_type allocator_type; | |
577 | ||
578 | _Rb_tree_base(const allocator_type& __a) | |
579 | : _Base(__a) { _M_header = _M_get_node(); } | |
580 | ~_Rb_tree_base() { _M_put_node(_M_header); } | |
581 | }; | |
582 | ||
583 | ||
584 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
585 | typename _Compare, typename _Alloc = allocator<_Val> > | |
586 | class _Rb_tree : protected _Rb_tree_base<_Val, _Alloc> | |
587 | { | |
588 | typedef _Rb_tree_base<_Val, _Alloc> _Base; | |
589 | ||
590 | protected: | |
591 | typedef _Rb_tree_node_base* _Base_ptr; | |
592 | typedef _Rb_tree_node<_Val> _Rb_tree_node; | |
593 | ||
594 | public: | |
595 | typedef _Key key_type; | |
596 | typedef _Val value_type; | |
597 | typedef value_type* pointer; | |
598 | typedef const value_type* const_pointer; | |
599 | typedef value_type& reference; | |
600 | typedef const value_type& const_reference; | |
601 | typedef _Rb_tree_node* _Link_type; | |
602 | typedef size_t size_type; | |
603 | typedef ptrdiff_t difference_type; | |
604 | ||
605 | typedef typename _Base::allocator_type allocator_type; | |
606 | allocator_type get_allocator() const { return _Base::get_allocator(); } | |
607 | ||
608 | protected: | |
609 | using _Base::_M_get_node; | |
610 | using _Base::_M_put_node; | |
611 | using _Base::_M_header; | |
612 | ||
613 | _Link_type | |
614 | _M_create_node(const value_type& __x) | |
615 | { | |
616 | _Link_type __tmp = _M_get_node(); | |
617 | try | |
618 | { _Construct(&__tmp->_M_value_field, __x); } | |
619 | catch(...) | |
620 | { | |
621 | _M_put_node(__tmp); | |
622 | __throw_exception_again; | |
623 | } | |
624 | return __tmp; | |
725dc051 | 625 | } |
d3d526ac BK |
626 | |
627 | _Link_type | |
628 | _M_clone_node(_Link_type __x) | |
629 | { | |
630 | _Link_type __tmp = _M_create_node(__x->_M_value_field); | |
631 | __tmp->_M_color = __x->_M_color; | |
632 | __tmp->_M_left = 0; | |
633 | __tmp->_M_right = 0; | |
634 | return __tmp; | |
725dc051 | 635 | } |
d3d526ac BK |
636 | |
637 | void | |
638 | destroy_node(_Link_type __p) | |
639 | { | |
640 | _Destroy(&__p->_M_value_field); | |
641 | _M_put_node(__p); | |
642 | } | |
643 | ||
644 | size_type _M_node_count; // keeps track of size of tree | |
645 | _Compare _M_key_compare; | |
646 | ||
647 | _Link_type& | |
648 | _M_root() const { return (_Link_type&) _M_header->_M_parent; } | |
649 | ||
650 | _Link_type& | |
651 | _M_leftmost() const { return (_Link_type&) _M_header->_M_left; } | |
652 | ||
653 | _Link_type& | |
654 | _M_rightmost() const { return (_Link_type&) _M_header->_M_right; } | |
655 | ||
656 | static _Link_type& | |
657 | _S_left(_Link_type __x) { return (_Link_type&)(__x->_M_left); } | |
658 | ||
659 | static _Link_type& | |
660 | _S_right(_Link_type __x) { return (_Link_type&)(__x->_M_right); } | |
661 | ||
662 | static _Link_type& | |
663 | _S_parent(_Link_type __x) { return (_Link_type&)(__x->_M_parent); } | |
664 | ||
665 | static reference | |
666 | _S_value(_Link_type __x) { return __x->_M_value_field; } | |
667 | ||
668 | static const _Key& | |
669 | _S_key(_Link_type __x) { return _KeyOfValue()(_S_value(__x)); } | |
670 | ||
671 | static _Rb_tree_color& | |
672 | _S_color(_Link_type __x) { return __x->_M_color; } | |
673 | ||
674 | static _Link_type& | |
675 | _S_left(_Base_ptr __x) { return (_Link_type&)(__x->_M_left); } | |
676 | ||
677 | static _Link_type& | |
678 | _S_right(_Base_ptr __x) { return (_Link_type&)(__x->_M_right); } | |
679 | ||
680 | static _Link_type& | |
681 | _S_parent(_Base_ptr __x) { return (_Link_type&)(__x->_M_parent); } | |
682 | ||
683 | static reference | |
684 | _S_value(_Base_ptr __x) { return ((_Link_type)__x)->_M_value_field; } | |
685 | ||
686 | static const _Key& | |
687 | _S_key(_Base_ptr __x) { return _KeyOfValue()(_S_value(_Link_type(__x)));} | |
688 | ||
689 | static _Rb_tree_color& | |
690 | _S_color(_Base_ptr __x) { return (_Link_type(__x)->_M_color); } | |
691 | ||
692 | static _Link_type | |
693 | _S_minimum(_Link_type __x) | |
694 | { return (_Link_type) _Rb_tree_node_base::_S_minimum(__x); } | |
695 | ||
696 | static _Link_type | |
697 | _S_maximum(_Link_type __x) | |
698 | { return (_Link_type) _Rb_tree_node_base::_S_maximum(__x); } | |
699 | ||
700 | public: | |
701 | typedef _Rb_tree_iterator<value_type, reference, pointer> iterator; | |
702 | typedef _Rb_tree_iterator<value_type, const_reference, const_pointer> | |
703 | const_iterator; | |
704 | ||
be26865d GDR |
705 | typedef std::reverse_iterator<const_iterator> const_reverse_iterator; |
706 | typedef std::reverse_iterator<iterator> reverse_iterator; | |
d3d526ac BK |
707 | |
708 | private: | |
709 | iterator | |
710 | _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v); | |
711 | ||
712 | _Link_type | |
713 | _M_copy(_Link_type __x, _Link_type __p); | |
714 | ||
715 | void | |
716 | _M_erase(_Link_type __x); | |
717 | ||
718 | public: | |
719 | // allocation/deallocation | |
720 | _Rb_tree() | |
721 | : _Base(allocator_type()), _M_node_count(0), _M_key_compare() | |
722 | { _M_empty_initialize(); } | |
723 | ||
724 | _Rb_tree(const _Compare& __comp) | |
725 | : _Base(allocator_type()), _M_node_count(0), _M_key_compare(__comp) | |
726 | { _M_empty_initialize(); } | |
727 | ||
728 | _Rb_tree(const _Compare& __comp, const allocator_type& __a) | |
729 | : _Base(__a), _M_node_count(0), _M_key_compare(__comp) | |
730 | { _M_empty_initialize(); } | |
731 | ||
732 | _Rb_tree(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x) | |
733 | : _Base(__x.get_allocator()), _M_node_count(0), | |
734 | _M_key_compare(__x._M_key_compare) | |
735 | { | |
736 | if (__x._M_root() == 0) | |
737 | _M_empty_initialize(); | |
738 | else | |
739 | { | |
740 | _S_color(_M_header) = _M_red; | |
741 | _M_root() = _M_copy(__x._M_root(), _M_header); | |
742 | _M_leftmost() = _S_minimum(_M_root()); | |
743 | _M_rightmost() = _S_maximum(_M_root()); | |
744 | } | |
745 | _M_node_count = __x._M_node_count; | |
725dc051 | 746 | } |
d3d526ac BK |
747 | |
748 | ~_Rb_tree() { clear(); } | |
749 | ||
750 | _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& | |
751 | operator=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x); | |
752 | ||
753 | private: | |
754 | void _M_empty_initialize() | |
755 | { | |
756 | _S_color(_M_header) = _M_red; // used to distinguish header from | |
757 | // __root, in iterator.operator++ | |
758 | _M_root() = 0; | |
759 | _M_leftmost() = _M_header; | |
760 | _M_rightmost() = _M_header; | |
761 | } | |
762 | ||
763 | public: | |
764 | // Accessors. | |
765 | _Compare | |
766 | key_comp() const { return _M_key_compare; } | |
767 | ||
768 | iterator | |
769 | begin() { return _M_leftmost(); } | |
770 | ||
771 | const_iterator | |
772 | begin() const { return _M_leftmost(); } | |
773 | ||
774 | iterator | |
775 | end() { return _M_header; } | |
776 | ||
777 | const_iterator | |
778 | end() const { return _M_header; } | |
779 | ||
780 | reverse_iterator | |
781 | rbegin() { return reverse_iterator(end()); } | |
782 | ||
783 | const_reverse_iterator | |
784 | rbegin() const { return const_reverse_iterator(end()); } | |
785 | ||
786 | reverse_iterator | |
787 | rend() { return reverse_iterator(begin()); } | |
788 | ||
789 | const_reverse_iterator | |
790 | rend() const { return const_reverse_iterator(begin()); } | |
791 | ||
792 | bool | |
793 | empty() const { return _M_node_count == 0; } | |
794 | ||
795 | size_type | |
796 | size() const { return _M_node_count; } | |
797 | ||
798 | size_type | |
799 | max_size() const { return size_type(-1); } | |
800 | ||
801 | void | |
802 | swap(_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __t) | |
803 | { | |
804 | std::swap(_M_header, __t._M_header); | |
805 | std::swap(_M_node_count, __t._M_node_count); | |
806 | std::swap(_M_key_compare, __t._M_key_compare); | |
725dc051 | 807 | } |
d3d526ac BK |
808 | |
809 | // Insert/erase. | |
810 | pair<iterator,bool> | |
811 | insert_unique(const value_type& __x); | |
812 | ||
813 | iterator | |
814 | insert_equal(const value_type& __x); | |
815 | ||
816 | iterator | |
817 | insert_unique(iterator __position, const value_type& __x); | |
818 | ||
819 | iterator | |
820 | insert_equal(iterator __position, const value_type& __x); | |
821 | ||
822 | template<typename _InputIterator> | |
823 | void | |
824 | insert_unique(_InputIterator __first, _InputIterator __last); | |
825 | ||
826 | template<typename _InputIterator> | |
827 | void | |
828 | insert_equal(_InputIterator __first, _InputIterator __last); | |
829 | ||
830 | void | |
831 | erase(iterator __position); | |
832 | ||
833 | size_type | |
834 | erase(const key_type& __x); | |
835 | ||
836 | void | |
837 | erase(iterator __first, iterator __last); | |
838 | ||
839 | void | |
840 | erase(const key_type* __first, const key_type* __last); | |
841 | ||
842 | void | |
843 | clear() | |
844 | { | |
845 | if (_M_node_count != 0) | |
846 | { | |
847 | _M_erase(_M_root()); | |
848 | _M_leftmost() = _M_header; | |
849 | _M_root() = 0; | |
850 | _M_rightmost() = _M_header; | |
851 | _M_node_count = 0; | |
852 | } | |
853 | } | |
854 | ||
855 | // Set operations. | |
856 | iterator | |
857 | find(const key_type& __x); | |
858 | ||
859 | const_iterator | |
860 | find(const key_type& __x) const; | |
861 | ||
862 | size_type | |
863 | count(const key_type& __x) const; | |
864 | ||
865 | iterator | |
866 | lower_bound(const key_type& __x); | |
867 | ||
868 | const_iterator | |
869 | lower_bound(const key_type& __x) const; | |
870 | ||
871 | iterator | |
872 | upper_bound(const key_type& __x); | |
873 | ||
874 | const_iterator | |
875 | upper_bound(const key_type& __x) const; | |
876 | ||
877 | pair<iterator,iterator> | |
878 | equal_range(const key_type& __x); | |
879 | ||
880 | pair<const_iterator, const_iterator> | |
881 | equal_range(const key_type& __x) const; | |
882 | ||
883 | // Debugging. | |
884 | bool | |
885 | __rb_verify() const; | |
886 | }; | |
887 | ||
888 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
889 | typename _Compare, typename _Alloc> | |
890 | inline bool | |
891 | operator==(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x, | |
892 | const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y) | |
893 | { | |
894 | return __x.size() == __y.size() && | |
895 | equal(__x.begin(), __x.end(), __y.begin()); | |
725dc051 | 896 | } |
d3d526ac BK |
897 | |
898 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
899 | typename _Compare, typename _Alloc> | |
900 | inline bool | |
901 | operator<(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x, | |
902 | const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y) | |
903 | { | |
904 | return lexicographical_compare(__x.begin(), __x.end(), | |
905 | __y.begin(), __y.end()); | |
725dc051 | 906 | } |
d3d526ac BK |
907 | |
908 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
909 | typename _Compare, typename _Alloc> | |
910 | inline bool | |
911 | operator!=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x, | |
912 | const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y) | |
913 | { return !(__x == __y); } | |
914 | ||
915 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
916 | typename _Compare, typename _Alloc> | |
917 | inline bool | |
918 | operator>(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x, | |
919 | const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y) | |
920 | { return __y < __x; } | |
921 | ||
922 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
923 | typename _Compare, typename _Alloc> | |
924 | inline bool | |
925 | operator<=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x, | |
926 | const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y) | |
927 | { return !(__y < __x); } | |
928 | ||
929 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
930 | typename _Compare, typename _Alloc> | |
931 | inline bool | |
932 | operator>=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x, | |
933 | const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y) | |
934 | { return !(__x < __y); } | |
935 | ||
936 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
937 | typename _Compare, typename _Alloc> | |
938 | inline void | |
939 | swap(_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x, | |
940 | _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y) | |
941 | { __x.swap(__y); } | |
942 | ||
943 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
944 | typename _Compare, typename _Alloc> | |
945 | _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& | |
946 | _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: | |
947 | operator=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x) | |
948 | { | |
949 | if (this != &__x) | |
950 | { | |
951 | // Note that _Key may be a constant type. | |
952 | clear(); | |
953 | _M_node_count = 0; | |
954 | _M_key_compare = __x._M_key_compare; | |
955 | if (__x._M_root() == 0) | |
956 | { | |
957 | _M_root() = 0; | |
958 | _M_leftmost() = _M_header; | |
959 | _M_rightmost() = _M_header; | |
960 | } | |
961 | else | |
962 | { | |
963 | _M_root() = _M_copy(__x._M_root(), _M_header); | |
964 | _M_leftmost() = _S_minimum(_M_root()); | |
965 | _M_rightmost() = _S_maximum(_M_root()); | |
966 | _M_node_count = __x._M_node_count; | |
967 | } | |
968 | } | |
969 | return *this; | |
725dc051 | 970 | } |
d3d526ac BK |
971 | |
972 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
973 | typename _Compare, typename _Alloc> | |
974 | typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator | |
975 | _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: | |
976 | _M_insert(_Base_ptr __x_, _Base_ptr __y_, const _Val& __v) | |
977 | { | |
978 | _Link_type __x = (_Link_type) __x_; | |
979 | _Link_type __y = (_Link_type) __y_; | |
980 | _Link_type __z; | |
981 | ||
982 | if (__y == _M_header || __x != 0 || | |
983 | _M_key_compare(_KeyOfValue()(__v), _S_key(__y))) | |
984 | { | |
985 | __z = _M_create_node(__v); | |
986 | _S_left(__y) = __z; // also makes _M_leftmost() = __z | |
987 | // when __y == _M_header | |
988 | if (__y == _M_header) | |
989 | { | |
990 | _M_root() = __z; | |
991 | _M_rightmost() = __z; | |
992 | } | |
993 | else if (__y == _M_leftmost()) | |
994 | _M_leftmost() = __z; // maintain _M_leftmost() pointing to min node | |
995 | } | |
996 | else | |
997 | { | |
998 | __z = _M_create_node(__v); | |
999 | _S_right(__y) = __z; | |
1000 | // Maintain _M_rightmost() pointing to max node. | |
1001 | if (__y == _M_rightmost()) | |
1002 | _M_rightmost() = __z; | |
1003 | } | |
1004 | _S_parent(__z) = __y; | |
1005 | _S_left(__z) = 0; | |
1006 | _S_right(__z) = 0; | |
1007 | _Rb_tree_rebalance(__z, _M_header->_M_parent); | |
1008 | ++_M_node_count; | |
1009 | return iterator(__z); | |
1010 | } | |
1011 | ||
1012 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
1013 | typename _Compare, typename _Alloc> | |
1014 | typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator | |
1015 | _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: | |
1016 | insert_equal(const _Val& __v) | |
1017 | { | |
1018 | _Link_type __y = _M_header; | |
1019 | _Link_type __x = _M_root(); | |
1020 | while (__x != 0) | |
1021 | { | |
1022 | __y = __x; | |
1023 | __x = _M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ? | |
1024 | _S_left(__x) : _S_right(__x); | |
1025 | } | |
1026 | return _M_insert(__x, __y, __v); | |
1027 | } | |
1028 | ||
1029 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
1030 | typename _Compare, typename _Alloc> | |
1031 | pair<typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator, | |
1032 | bool> | |
1033 | _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: | |
1034 | insert_unique(const _Val& __v) | |
1035 | { | |
1036 | _Link_type __y = _M_header; | |
1037 | _Link_type __x = _M_root(); | |
1038 | bool __comp = true; | |
1039 | while (__x != 0) | |
1040 | { | |
1041 | __y = __x; | |
1042 | __comp = _M_key_compare(_KeyOfValue()(__v), _S_key(__x)); | |
1043 | __x = __comp ? _S_left(__x) : _S_right(__x); | |
1044 | } | |
1045 | iterator __j = iterator(__y); | |
1046 | if (__comp) | |
1047 | if (__j == begin()) | |
1048 | return pair<iterator,bool>(_M_insert(__x, __y, __v), true); | |
1049 | else | |
1050 | --__j; | |
1051 | if (_M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v))) | |
1052 | return pair<iterator,bool>(_M_insert(__x, __y, __v), true); | |
1053 | return pair<iterator,bool>(__j, false); | |
1054 | } | |
1055 | ||
1056 | ||
1057 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
1058 | typename _Compare, typename _Alloc> | |
1059 | typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator | |
1060 | _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: | |
1061 | insert_unique(iterator __position, const _Val& __v) | |
1062 | { | |
1063 | if (__position._M_node == _M_header->_M_left) | |
1064 | { | |
1065 | // begin() | |
1066 | if (size() > 0 && | |
1067 | _M_key_compare(_KeyOfValue()(__v), _S_key(__position._M_node))) | |
1068 | return _M_insert(__position._M_node, __position._M_node, __v); | |
1069 | // first argument just needs to be non-null | |
1070 | else | |
1071 | return insert_unique(__v).first; | |
1072 | } | |
1073 | else if (__position._M_node == _M_header) | |
1074 | { | |
1075 | // end() | |
1076 | if (_M_key_compare(_S_key(_M_rightmost()), _KeyOfValue()(__v))) | |
1077 | return _M_insert(0, _M_rightmost(), __v); | |
1078 | else | |
1079 | return insert_unique(__v).first; | |
1080 | } | |
1081 | else | |
1082 | { | |
1083 | iterator __before = __position; | |
1084 | --__before; | |
1085 | if (_M_key_compare(_S_key(__before._M_node), _KeyOfValue()(__v)) | |
1086 | && _M_key_compare(_KeyOfValue()(__v),_S_key(__position._M_node))) | |
1087 | { | |
1088 | if (_S_right(__before._M_node) == 0) | |
1089 | return _M_insert(0, __before._M_node, __v); | |
1090 | else | |
1091 | return _M_insert(__position._M_node, __position._M_node, __v); | |
1092 | // first argument just needs to be non-null | |
1093 | } | |
1094 | else | |
1095 | return insert_unique(__v).first; | |
1096 | } | |
725dc051 | 1097 | } |
d3d526ac BK |
1098 | |
1099 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
1100 | typename _Compare, typename _Alloc> | |
1101 | typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator | |
1102 | _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: | |
1103 | insert_equal(iterator __position, const _Val& __v) | |
1104 | { | |
1105 | if (__position._M_node == _M_header->_M_left) | |
1106 | { | |
1107 | // begin() | |
1108 | if (size() > 0 && | |
1109 | !_M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__v))) | |
1110 | return _M_insert(__position._M_node, __position._M_node, __v); | |
1111 | // first argument just needs to be non-null | |
1112 | else | |
1113 | return insert_equal(__v); | |
1114 | } | |
1115 | else if (__position._M_node == _M_header) | |
1116 | { | |
1117 | // end() | |
1118 | if (!_M_key_compare(_KeyOfValue()(__v), _S_key(_M_rightmost()))) | |
1119 | return _M_insert(0, _M_rightmost(), __v); | |
1120 | else | |
1121 | return insert_equal(__v); | |
1122 | } | |
1123 | else | |
1124 | { | |
1125 | iterator __before = __position; | |
1126 | --__before; | |
1127 | if (!_M_key_compare(_KeyOfValue()(__v), _S_key(__before._M_node)) | |
1128 | && !_M_key_compare(_S_key(__position._M_node), | |
1129 | _KeyOfValue()(__v))) | |
1130 | { | |
1131 | if (_S_right(__before._M_node) == 0) | |
1132 | return _M_insert(0, __before._M_node, __v); | |
1133 | else | |
1134 | return _M_insert(__position._M_node, __position._M_node, __v); | |
1135 | // first argument just needs to be non-null | |
1136 | } | |
1137 | else | |
1138 | return insert_equal(__v); | |
1139 | } | |
1140 | } | |
1141 | ||
1142 | template<typename _Key, typename _Val, typename _KoV, | |
1143 | typename _Cmp, typename _Alloc> | |
1144 | template<class _II> | |
1145 | void | |
1146 | _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>:: | |
1147 | insert_equal(_II __first, _II __last) | |
322821b9 | 1148 | { |
d3d526ac BK |
1149 | for ( ; __first != __last; ++__first) |
1150 | insert_equal(*__first); | |
322821b9 | 1151 | } |
725dc051 | 1152 | |
d3d526ac BK |
1153 | template<typename _Key, typename _Val, typename _KoV, |
1154 | typename _Cmp, typename _Alloc> | |
1155 | template<class _II> | |
1156 | void | |
1157 | _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>:: | |
1158 | insert_unique(_II __first, _II __last) | |
1159 | { | |
1160 | for ( ; __first != __last; ++__first) | |
1161 | insert_unique(*__first); | |
1162 | } | |
725dc051 | 1163 | |
d3d526ac BK |
1164 | template<typename _Key, typename _Val, typename _KeyOfValue, |
1165 | typename _Compare, typename _Alloc> | |
1166 | inline void | |
1167 | _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::erase(iterator __position) | |
1168 | { | |
1169 | _Link_type __y = | |
1170 | (_Link_type) _Rb_tree_rebalance_for_erase(__position._M_node, | |
1171 | _M_header->_M_parent, | |
1172 | _M_header->_M_left, | |
1173 | _M_header->_M_right); | |
1174 | destroy_node(__y); | |
1175 | --_M_node_count; | |
1176 | } | |
725dc051 | 1177 | |
d3d526ac BK |
1178 | template<typename _Key, typename _Val, typename _KeyOfValue, |
1179 | typename _Compare, typename _Alloc> | |
1180 | typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::size_type | |
1181 | _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::erase(const _Key& __x) | |
1182 | { | |
1183 | pair<iterator,iterator> __p = equal_range(__x); | |
4977bab6 | 1184 | size_type __n = std::distance(__p.first, __p.second); |
d3d526ac BK |
1185 | erase(__p.first, __p.second); |
1186 | return __n; | |
725dc051 | 1187 | } |
725dc051 | 1188 | |
d3d526ac BK |
1189 | template<typename _Key, typename _Val, typename _KoV, |
1190 | typename _Compare, typename _Alloc> | |
1191 | typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type | |
1192 | _Rb_tree<_Key,_Val,_KoV,_Compare,_Alloc>:: | |
1193 | _M_copy(_Link_type __x, _Link_type __p) | |
1194 | { | |
1195 | // Structural copy. __x and __p must be non-null. | |
1196 | _Link_type __top = _M_clone_node(__x); | |
1197 | __top->_M_parent = __p; | |
1198 | ||
1199 | try | |
1200 | { | |
1201 | if (__x->_M_right) | |
1202 | __top->_M_right = _M_copy(_S_right(__x), __top); | |
1203 | __p = __top; | |
1204 | __x = _S_left(__x); | |
1205 | ||
1206 | while (__x != 0) | |
1207 | { | |
1208 | _Link_type __y = _M_clone_node(__x); | |
1209 | __p->_M_left = __y; | |
1210 | __y->_M_parent = __p; | |
1211 | if (__x->_M_right) | |
1212 | __y->_M_right = _M_copy(_S_right(__x), __y); | |
1213 | __p = __y; | |
1214 | __x = _S_left(__x); | |
1215 | } | |
1216 | } | |
1217 | catch(...) | |
1218 | { | |
1219 | _M_erase(__top); | |
1220 | __throw_exception_again; | |
1221 | } | |
1222 | return __top; | |
725dc051 | 1223 | } |
d3d526ac BK |
1224 | |
1225 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
1226 | typename _Compare, typename _Alloc> | |
1227 | void | |
1228 | _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::_M_erase(_Link_type __x) | |
1229 | { | |
1230 | // Erase without rebalancing. | |
1231 | while (__x != 0) | |
1232 | { | |
1233 | _M_erase(_S_right(__x)); | |
1234 | _Link_type __y = _S_left(__x); | |
1235 | destroy_node(__x); | |
1236 | __x = __y; | |
1237 | } | |
725dc051 | 1238 | } |
d3d526ac BK |
1239 | |
1240 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
1241 | typename _Compare, typename _Alloc> | |
1242 | void | |
1243 | _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: | |
1244 | erase(iterator __first, iterator __last) | |
1245 | { | |
1246 | if (__first == begin() && __last == end()) | |
1247 | clear(); | |
1248 | else | |
1249 | while (__first != __last) erase(__first++); | |
725dc051 | 1250 | } |
d3d526ac BK |
1251 | |
1252 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
1253 | typename _Compare, typename _Alloc> | |
1254 | void | |
1255 | _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: | |
1256 | erase(const _Key* __first, const _Key* __last) | |
1257 | { | |
1258 | while (__first != __last) | |
1259 | erase(*__first++); | |
725dc051 | 1260 | } |
d3d526ac BK |
1261 | |
1262 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
1263 | typename _Compare, typename _Alloc> | |
1264 | typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator | |
1265 | _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::find(const _Key& __k) | |
1266 | { | |
1267 | _Link_type __y = _M_header; // Last node which is not less than __k. | |
1268 | _Link_type __x = _M_root(); // Current node. | |
1269 | ||
1270 | while (__x != 0) | |
1271 | if (!_M_key_compare(_S_key(__x), __k)) | |
1272 | __y = __x, __x = _S_left(__x); | |
1273 | else | |
1274 | __x = _S_right(__x); | |
1275 | ||
1276 | iterator __j = iterator(__y); | |
1277 | return (__j == end() || _M_key_compare(__k, _S_key(__j._M_node))) ? | |
1278 | end() : __j; | |
1279 | } | |
1280 | ||
1281 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
1282 | typename _Compare, typename _Alloc> | |
1283 | typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::const_iterator | |
1284 | _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: | |
1285 | find(const _Key& __k) const | |
1286 | { | |
1287 | _Link_type __y = _M_header; // Last node which is not less than __k. | |
1288 | _Link_type __x = _M_root(); // Current node. | |
725dc051 | 1289 | |
d3d526ac BK |
1290 | while (__x != 0) |
1291 | { | |
1292 | if (!_M_key_compare(_S_key(__x), __k)) | |
1293 | __y = __x, __x = _S_left(__x); | |
1294 | else | |
1295 | __x = _S_right(__x); | |
1296 | } | |
1297 | const_iterator __j = const_iterator(__y); | |
1298 | return (__j == end() || _M_key_compare(__k, _S_key(__j._M_node))) ? | |
1299 | end() : __j; | |
725dc051 | 1300 | } |
d3d526ac BK |
1301 | |
1302 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
1303 | typename _Compare, typename _Alloc> | |
1304 | typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::size_type | |
1305 | _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: | |
1306 | count(const _Key& __k) const | |
322821b9 | 1307 | { |
d3d526ac | 1308 | pair<const_iterator, const_iterator> __p = equal_range(__k); |
4977bab6 | 1309 | size_type __n = std::distance(__p.first, __p.second); |
d3d526ac | 1310 | return __n; |
322821b9 | 1311 | } |
d3d526ac BK |
1312 | |
1313 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
1314 | typename _Compare, typename _Alloc> | |
1315 | typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator | |
1316 | _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: | |
1317 | lower_bound(const _Key& __k) | |
1318 | { | |
1319 | _Link_type __y = _M_header; /* Last node which is not less than __k. */ | |
1320 | _Link_type __x = _M_root(); /* Current node. */ | |
1321 | ||
1322 | while (__x != 0) | |
1323 | if (!_M_key_compare(_S_key(__x), __k)) | |
1324 | __y = __x, __x = _S_left(__x); | |
1325 | else | |
1326 | __x = _S_right(__x); | |
1327 | ||
1328 | return iterator(__y); | |
1329 | } | |
1330 | ||
1331 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
1332 | typename _Compare, typename _Alloc> | |
1333 | typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::const_iterator | |
1334 | _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: | |
1335 | lower_bound(const _Key& __k) const | |
1336 | { | |
1337 | _Link_type __y = _M_header; /* Last node which is not less than __k. */ | |
1338 | _Link_type __x = _M_root(); /* Current node. */ | |
1339 | ||
1340 | while (__x != 0) | |
1341 | if (!_M_key_compare(_S_key(__x), __k)) | |
1342 | __y = __x, __x = _S_left(__x); | |
1343 | else | |
1344 | __x = _S_right(__x); | |
1345 | ||
1346 | return const_iterator(__y); | |
1347 | } | |
1348 | ||
1349 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
1350 | typename _Compare, typename _Alloc> | |
1351 | typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator | |
1352 | _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: | |
1353 | upper_bound(const _Key& __k) | |
1354 | { | |
1355 | _Link_type __y = _M_header; /* Last node which is greater than __k. */ | |
1356 | _Link_type __x = _M_root(); /* Current node. */ | |
1357 | ||
1358 | while (__x != 0) | |
1359 | if (_M_key_compare(__k, _S_key(__x))) | |
1360 | __y = __x, __x = _S_left(__x); | |
1361 | else | |
1362 | __x = _S_right(__x); | |
1363 | ||
1364 | return iterator(__y); | |
1365 | } | |
1366 | ||
1367 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
1368 | typename _Compare, typename _Alloc> | |
1369 | typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::const_iterator | |
1370 | _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: | |
1371 | upper_bound(const _Key& __k) const | |
1372 | { | |
1373 | _Link_type __y = _M_header; /* Last node which is greater than __k. */ | |
1374 | _Link_type __x = _M_root(); /* Current node. */ | |
1375 | ||
1376 | while (__x != 0) | |
1377 | if (_M_key_compare(__k, _S_key(__x))) | |
1378 | __y = __x, __x = _S_left(__x); | |
1379 | else | |
1380 | __x = _S_right(__x); | |
1381 | ||
1382 | return const_iterator(__y); | |
1383 | } | |
1384 | ||
1385 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
1386 | typename _Compare, typename _Alloc> | |
1387 | inline | |
1388 | pair<typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator, | |
1389 | typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator> | |
1390 | _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: | |
1391 | equal_range(const _Key& __k) | |
1392 | { return pair<iterator, iterator>(lower_bound(__k), upper_bound(__k)); } | |
1393 | ||
1394 | template<typename _Key, typename _Val, typename _KoV, | |
1395 | typename _Compare, typename _Alloc> | |
1396 | inline | |
1397 | pair<typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::const_iterator, | |
1398 | typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::const_iterator> | |
1399 | _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc> | |
1400 | ::equal_range(const _Key& __k) const | |
1401 | { | |
1402 | return pair<const_iterator,const_iterator>(lower_bound(__k), | |
1403 | upper_bound(__k)); | |
725dc051 | 1404 | } |
d3d526ac BK |
1405 | |
1406 | inline int | |
1407 | __black_count(_Rb_tree_node_base* __node, _Rb_tree_node_base* __root) | |
1408 | { | |
1409 | if (__node == 0) | |
1410 | return 0; | |
1411 | int __sum = 0; | |
1412 | do | |
1413 | { | |
1414 | if (__node->_M_color == _M_black) | |
1415 | ++__sum; | |
1416 | if (__node == __root) | |
1417 | break; | |
1418 | __node = __node->_M_parent; | |
1419 | } | |
1420 | while (1); | |
1421 | return __sum; | |
725dc051 | 1422 | } |
d3d526ac BK |
1423 | |
1424 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
1425 | typename _Compare, typename _Alloc> | |
1426 | bool | |
1427 | _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const | |
1428 | { | |
1429 | if (_M_node_count == 0 || begin() == end()) | |
1430 | return _M_node_count == 0 && begin() == end() && | |
1431 | _M_header->_M_left == _M_header && _M_header->_M_right == _M_header; | |
725dc051 | 1432 | |
d3d526ac BK |
1433 | int __len = __black_count(_M_leftmost(), _M_root()); |
1434 | for (const_iterator __it = begin(); __it != end(); ++__it) | |
1435 | { | |
1436 | _Link_type __x = (_Link_type) __it._M_node; | |
1437 | _Link_type __L = _S_left(__x); | |
1438 | _Link_type __R = _S_right(__x); | |
1439 | ||
1440 | if (__x->_M_color == _M_red) | |
1441 | if ((__L && __L->_M_color == _M_red) | |
1442 | || (__R && __R->_M_color == _M_red)) | |
1443 | return false; | |
1444 | ||
1445 | if (__L && _M_key_compare(_S_key(__x), _S_key(__L))) | |
1446 | return false; | |
1447 | if (__R && _M_key_compare(_S_key(__R), _S_key(__x))) | |
1448 | return false; | |
1449 | ||
1450 | if (!__L && !__R && __black_count(__x, _M_root()) != __len) | |
1451 | return false; | |
1452 | } | |
1453 | ||
1454 | if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root())) | |
725dc051 | 1455 | return false; |
d3d526ac | 1456 | if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root())) |
725dc051 | 1457 | return false; |
d3d526ac BK |
1458 | return true; |
1459 | } | |
d53d7f6e | 1460 | } // namespace std |
725dc051 | 1461 | |
d3d526ac | 1462 | #endif |