]>
Commit | Line | Data |
---|---|---|
42526146 PE |
1 | // RB tree implementation -*- C++ -*- |
2 | ||
8fbc5ae7 | 3 | // Copyright (C) 2001, 2002, 2003 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 | ||
3d7c150e BK |
63 | #ifndef _TREE_H |
64 | #define _TREE_H 1 | |
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> | |
1ff9402d | 87 | #include <bits/allocator.h> |
725dc051 BK |
88 | #include <bits/stl_construct.h> |
89 | #include <bits/stl_function.h> | |
90 | ||
d53d7f6e PE |
91 | namespace std |
92 | { | |
655d7821 | 93 | enum _Rb_tree_color { _S_red = false, _S_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 | { | |
655d7821 | 159 | if (_M_node->_M_color == _S_red |
d3d526ac BK |
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() {} | |
7f6dd1ca | 195 | _Rb_tree_iterator(_Rb_tree_node_base* __x) { _M_node = __x; } |
d3d526ac BK |
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 | { |
655d7821 | 308 | __x->_M_color = _S_red; |
d3d526ac | 309 | while (__x != __root |
655d7821 | 310 | && __x->_M_parent->_M_color == _S_red) |
d3d526ac BK |
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; | |
655d7821 | 315 | if (__y && __y->_M_color == _S_red) |
d3d526ac | 316 | { |
655d7821 BK |
317 | __x->_M_parent->_M_color = _S_black; |
318 | __y->_M_color = _S_black; | |
319 | __x->_M_parent->_M_parent->_M_color = _S_red; | |
d3d526ac BK |
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 | } | |
655d7821 BK |
329 | __x->_M_parent->_M_color = _S_black; |
330 | __x->_M_parent->_M_parent->_M_color = _S_red; | |
d3d526ac BK |
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; | |
655d7821 | 337 | if (__y && __y->_M_color == _S_red) |
d3d526ac | 338 | { |
655d7821 BK |
339 | __x->_M_parent->_M_color = _S_black; |
340 | __y->_M_color = _S_black; | |
341 | __x->_M_parent->_M_parent->_M_color = _S_red; | |
d3d526ac BK |
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 | } | |
655d7821 BK |
351 | __x->_M_parent->_M_color = _S_black; |
352 | __x->_M_parent->_M_parent->_M_color = _S_red; | |
d3d526ac BK |
353 | _Rb_tree_rotate_left(__x->_M_parent->_M_parent, __root); |
354 | } | |
355 | } | |
725dc051 | 356 | } |
655d7821 | 357 | __root->_M_color = _S_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 | } | |
655d7821 | 433 | if (__y->_M_color != _S_red) |
d3d526ac | 434 | { |
655d7821 | 435 | while (__x != __root && (__x == 0 || __x->_M_color == _S_black)) |
d3d526ac BK |
436 | if (__x == __x_parent->_M_left) |
437 | { | |
438 | _Rb_tree_node_base* __w = __x_parent->_M_right; | |
655d7821 | 439 | if (__w->_M_color == _S_red) |
d3d526ac | 440 | { |
655d7821 BK |
441 | __w->_M_color = _S_black; |
442 | __x_parent->_M_color = _S_red; | |
d3d526ac BK |
443 | _Rb_tree_rotate_left(__x_parent, __root); |
444 | __w = __x_parent->_M_right; | |
445 | } | |
446 | if ((__w->_M_left == 0 || | |
655d7821 | 447 | __w->_M_left->_M_color == _S_black) && |
d3d526ac | 448 | (__w->_M_right == 0 || |
655d7821 | 449 | __w->_M_right->_M_color == _S_black)) |
d3d526ac | 450 | { |
655d7821 | 451 | __w->_M_color = _S_red; |
d3d526ac BK |
452 | __x = __x_parent; |
453 | __x_parent = __x_parent->_M_parent; | |
454 | } | |
455 | else | |
456 | { | |
457 | if (__w->_M_right == 0 | |
655d7821 | 458 | || __w->_M_right->_M_color == _S_black) |
d3d526ac | 459 | { |
655d7821 BK |
460 | __w->_M_left->_M_color = _S_black; |
461 | __w->_M_color = _S_red; | |
d3d526ac BK |
462 | _Rb_tree_rotate_right(__w, __root); |
463 | __w = __x_parent->_M_right; | |
464 | } | |
465 | __w->_M_color = __x_parent->_M_color; | |
655d7821 | 466 | __x_parent->_M_color = _S_black; |
d3d526ac | 467 | if (__w->_M_right) |
655d7821 | 468 | __w->_M_right->_M_color = _S_black; |
d3d526ac BK |
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; | |
655d7821 | 477 | if (__w->_M_color == _S_red) |
d3d526ac | 478 | { |
655d7821 BK |
479 | __w->_M_color = _S_black; |
480 | __x_parent->_M_color = _S_red; | |
d3d526ac BK |
481 | _Rb_tree_rotate_right(__x_parent, __root); |
482 | __w = __x_parent->_M_left; | |
483 | } | |
484 | if ((__w->_M_right == 0 || | |
655d7821 | 485 | __w->_M_right->_M_color == _S_black) && |
d3d526ac | 486 | (__w->_M_left == 0 || |
655d7821 | 487 | __w->_M_left->_M_color == _S_black)) |
d3d526ac | 488 | { |
655d7821 | 489 | __w->_M_color = _S_red; |
d3d526ac BK |
490 | __x = __x_parent; |
491 | __x_parent = __x_parent->_M_parent; | |
492 | } | |
493 | else | |
494 | { | |
655d7821 | 495 | if (__w->_M_left == 0 || __w->_M_left->_M_color == _S_black) |
d3d526ac | 496 | { |
655d7821 BK |
497 | __w->_M_right->_M_color = _S_black; |
498 | __w->_M_color = _S_red; | |
d3d526ac BK |
499 | _Rb_tree_rotate_left(__w, __root); |
500 | __w = __x_parent->_M_left; | |
501 | } | |
502 | __w->_M_color = __x_parent->_M_color; | |
655d7821 | 503 | __x_parent->_M_color = _S_black; |
d3d526ac | 504 | if (__w->_M_left) |
655d7821 | 505 | __w->_M_left->_M_color = _S_black; |
d3d526ac BK |
506 | _Rb_tree_rotate_right(__x_parent, __root); |
507 | break; | |
508 | } | |
509 | } | |
655d7821 | 510 | if (__x) __x->_M_color = _S_black; |
d3d526ac BK |
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) | |
7f6dd1ca | 531 | : _M_node_allocator(__a) {} |
d3d526ac BK |
532 | |
533 | protected: | |
534 | typename _Alloc_traits<_Rb_tree_node<_Tp>, _Alloc>::allocator_type | |
535 | _M_node_allocator; | |
536 | ||
7f6dd1ca | 537 | _Rb_tree_node_base _M_header; |
d3d526ac BK |
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 | ||
7f6dd1ca | 555 | _Rb_tree_alloc_base(const allocator_type&) {} |
d3d526ac BK |
556 | |
557 | protected: | |
7f6dd1ca | 558 | _Rb_tree_node_base _M_header; |
d3d526ac BK |
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) | |
7f6dd1ca | 579 | : _Base(__a) {} |
d3d526ac BK |
580 | }; |
581 | ||
582 | ||
583 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
584 | typename _Compare, typename _Alloc = allocator<_Val> > | |
585 | class _Rb_tree : protected _Rb_tree_base<_Val, _Alloc> | |
586 | { | |
587 | typedef _Rb_tree_base<_Val, _Alloc> _Base; | |
588 | ||
589 | protected: | |
590 | typedef _Rb_tree_node_base* _Base_ptr; | |
591 | typedef _Rb_tree_node<_Val> _Rb_tree_node; | |
592 | ||
593 | public: | |
594 | typedef _Key key_type; | |
595 | typedef _Val value_type; | |
596 | typedef value_type* pointer; | |
597 | typedef const value_type* const_pointer; | |
598 | typedef value_type& reference; | |
599 | typedef const value_type& const_reference; | |
600 | typedef _Rb_tree_node* _Link_type; | |
601 | typedef size_t size_type; | |
602 | typedef ptrdiff_t difference_type; | |
603 | ||
604 | typedef typename _Base::allocator_type allocator_type; | |
605 | allocator_type get_allocator() const { return _Base::get_allocator(); } | |
606 | ||
607 | protected: | |
608 | using _Base::_M_get_node; | |
609 | using _Base::_M_put_node; | |
610 | using _Base::_M_header; | |
611 | ||
612 | _Link_type | |
613 | _M_create_node(const value_type& __x) | |
614 | { | |
615 | _Link_type __tmp = _M_get_node(); | |
616 | try | |
9dd90ac6 | 617 | { std::_Construct(&__tmp->_M_value_field, __x); } |
d3d526ac BK |
618 | catch(...) |
619 | { | |
620 | _M_put_node(__tmp); | |
621 | __throw_exception_again; | |
622 | } | |
623 | return __tmp; | |
725dc051 | 624 | } |
d3d526ac BK |
625 | |
626 | _Link_type | |
627 | _M_clone_node(_Link_type __x) | |
628 | { | |
629 | _Link_type __tmp = _M_create_node(__x->_M_value_field); | |
630 | __tmp->_M_color = __x->_M_color; | |
631 | __tmp->_M_left = 0; | |
632 | __tmp->_M_right = 0; | |
633 | return __tmp; | |
725dc051 | 634 | } |
d3d526ac BK |
635 | |
636 | void | |
637 | destroy_node(_Link_type __p) | |
638 | { | |
9dd90ac6 | 639 | std::_Destroy(&__p->_M_value_field); |
d3d526ac BK |
640 | _M_put_node(__p); |
641 | } | |
642 | ||
643 | size_type _M_node_count; // keeps track of size of tree | |
644 | _Compare _M_key_compare; | |
645 | ||
646 | _Link_type& | |
7f6dd1ca | 647 | _M_root() const { return (_Link_type&) this->_M_header._M_parent; } |
d3d526ac BK |
648 | |
649 | _Link_type& | |
7f6dd1ca | 650 | _M_leftmost() const { return (_Link_type&) this->_M_header._M_left; } |
d3d526ac BK |
651 | |
652 | _Link_type& | |
7f6dd1ca | 653 | _M_rightmost() const { return (_Link_type&) this->_M_header._M_right; } |
d3d526ac | 654 | |
7f6dd1ca GB |
655 | _Link_type |
656 | _M_end() const { return (_Link_type) &this->_M_header; } | |
657 | ||
d3d526ac BK |
658 | static _Link_type& |
659 | _S_left(_Link_type __x) { return (_Link_type&)(__x->_M_left); } | |
660 | ||
661 | static _Link_type& | |
662 | _S_right(_Link_type __x) { return (_Link_type&)(__x->_M_right); } | |
663 | ||
664 | static _Link_type& | |
665 | _S_parent(_Link_type __x) { return (_Link_type&)(__x->_M_parent); } | |
666 | ||
667 | static reference | |
668 | _S_value(_Link_type __x) { return __x->_M_value_field; } | |
669 | ||
670 | static const _Key& | |
671 | _S_key(_Link_type __x) { return _KeyOfValue()(_S_value(__x)); } | |
672 | ||
d3d526ac BK |
673 | static _Link_type& |
674 | _S_left(_Base_ptr __x) { return (_Link_type&)(__x->_M_left); } | |
675 | ||
676 | static _Link_type& | |
677 | _S_right(_Base_ptr __x) { return (_Link_type&)(__x->_M_right); } | |
678 | ||
679 | static _Link_type& | |
680 | _S_parent(_Base_ptr __x) { return (_Link_type&)(__x->_M_parent); } | |
681 | ||
682 | static reference | |
683 | _S_value(_Base_ptr __x) { return ((_Link_type)__x)->_M_value_field; } | |
684 | ||
685 | static const _Key& | |
686 | _S_key(_Base_ptr __x) { return _KeyOfValue()(_S_value(_Link_type(__x)));} | |
687 | ||
688 | static _Rb_tree_color& | |
7f6dd1ca | 689 | _S_color(_Base_ptr __x) { return __x->_M_color; } |
d3d526ac BK |
690 | |
691 | static _Link_type | |
692 | _S_minimum(_Link_type __x) | |
693 | { return (_Link_type) _Rb_tree_node_base::_S_minimum(__x); } | |
694 | ||
695 | static _Link_type | |
696 | _S_maximum(_Link_type __x) | |
697 | { return (_Link_type) _Rb_tree_node_base::_S_maximum(__x); } | |
698 | ||
699 | public: | |
700 | typedef _Rb_tree_iterator<value_type, reference, pointer> iterator; | |
701 | typedef _Rb_tree_iterator<value_type, const_reference, const_pointer> | |
702 | const_iterator; | |
703 | ||
be26865d GDR |
704 | typedef std::reverse_iterator<const_iterator> const_reverse_iterator; |
705 | typedef std::reverse_iterator<iterator> reverse_iterator; | |
d3d526ac BK |
706 | |
707 | private: | |
708 | iterator | |
709 | _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v); | |
710 | ||
711 | _Link_type | |
712 | _M_copy(_Link_type __x, _Link_type __p); | |
713 | ||
714 | void | |
715 | _M_erase(_Link_type __x); | |
716 | ||
717 | public: | |
718 | // allocation/deallocation | |
719 | _Rb_tree() | |
720 | : _Base(allocator_type()), _M_node_count(0), _M_key_compare() | |
721 | { _M_empty_initialize(); } | |
722 | ||
723 | _Rb_tree(const _Compare& __comp) | |
724 | : _Base(allocator_type()), _M_node_count(0), _M_key_compare(__comp) | |
725 | { _M_empty_initialize(); } | |
726 | ||
727 | _Rb_tree(const _Compare& __comp, const allocator_type& __a) | |
728 | : _Base(__a), _M_node_count(0), _M_key_compare(__comp) | |
729 | { _M_empty_initialize(); } | |
730 | ||
731 | _Rb_tree(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x) | |
732 | : _Base(__x.get_allocator()), _M_node_count(0), | |
733 | _M_key_compare(__x._M_key_compare) | |
734 | { | |
735 | if (__x._M_root() == 0) | |
736 | _M_empty_initialize(); | |
737 | else | |
738 | { | |
7f6dd1ca GB |
739 | _S_color(&this->_M_header) = _S_red; |
740 | _M_root() = _M_copy(__x._M_root(), _M_end()); | |
d3d526ac BK |
741 | _M_leftmost() = _S_minimum(_M_root()); |
742 | _M_rightmost() = _S_maximum(_M_root()); | |
743 | } | |
744 | _M_node_count = __x._M_node_count; | |
725dc051 | 745 | } |
d3d526ac BK |
746 | |
747 | ~_Rb_tree() { clear(); } | |
748 | ||
749 | _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& | |
750 | operator=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x); | |
751 | ||
752 | private: | |
753 | void _M_empty_initialize() | |
754 | { | |
7f6dd1ca GB |
755 | // Used to distinguish header from __root, in iterator.operator++. |
756 | _S_color(&this->_M_header) = _S_red; | |
d3d526ac | 757 | _M_root() = 0; |
7f6dd1ca GB |
758 | _M_leftmost() = _M_end(); |
759 | _M_rightmost() = _M_end(); | |
d3d526ac BK |
760 | } |
761 | ||
762 | public: | |
763 | // Accessors. | |
764 | _Compare | |
765 | key_comp() const { return _M_key_compare; } | |
766 | ||
767 | iterator | |
768 | begin() { return _M_leftmost(); } | |
769 | ||
770 | const_iterator | |
771 | begin() const { return _M_leftmost(); } | |
772 | ||
773 | iterator | |
7f6dd1ca | 774 | end() { return &this->_M_header; } |
d3d526ac | 775 | |
7f6dd1ca GB |
776 | const_iterator |
777 | end() const { return const_cast<_Base_ptr>(&this->_M_header); } | |
d3d526ac BK |
778 | |
779 | reverse_iterator | |
780 | rbegin() { return reverse_iterator(end()); } | |
781 | ||
782 | const_reverse_iterator | |
783 | rbegin() const { return const_reverse_iterator(end()); } | |
784 | ||
785 | reverse_iterator | |
786 | rend() { return reverse_iterator(begin()); } | |
787 | ||
788 | const_reverse_iterator | |
789 | rend() const { return const_reverse_iterator(begin()); } | |
790 | ||
791 | bool | |
792 | empty() const { return _M_node_count == 0; } | |
793 | ||
794 | size_type | |
795 | size() const { return _M_node_count; } | |
796 | ||
797 | size_type | |
798 | max_size() const { return size_type(-1); } | |
799 | ||
800 | void | |
7f6dd1ca | 801 | swap(_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __t); |
d3d526ac BK |
802 | |
803 | // Insert/erase. | |
804 | pair<iterator,bool> | |
805 | insert_unique(const value_type& __x); | |
806 | ||
807 | iterator | |
808 | insert_equal(const value_type& __x); | |
809 | ||
810 | iterator | |
811 | insert_unique(iterator __position, const value_type& __x); | |
812 | ||
813 | iterator | |
814 | insert_equal(iterator __position, const value_type& __x); | |
815 | ||
816 | template<typename _InputIterator> | |
817 | void | |
818 | insert_unique(_InputIterator __first, _InputIterator __last); | |
819 | ||
820 | template<typename _InputIterator> | |
821 | void | |
822 | insert_equal(_InputIterator __first, _InputIterator __last); | |
823 | ||
824 | void | |
825 | erase(iterator __position); | |
826 | ||
827 | size_type | |
828 | erase(const key_type& __x); | |
829 | ||
830 | void | |
831 | erase(iterator __first, iterator __last); | |
832 | ||
833 | void | |
834 | erase(const key_type* __first, const key_type* __last); | |
835 | ||
836 | void | |
837 | clear() | |
838 | { | |
839 | if (_M_node_count != 0) | |
840 | { | |
841 | _M_erase(_M_root()); | |
7f6dd1ca | 842 | _M_leftmost() = _M_end(); |
d3d526ac | 843 | _M_root() = 0; |
7f6dd1ca | 844 | _M_rightmost() = _M_end(); |
d3d526ac BK |
845 | _M_node_count = 0; |
846 | } | |
847 | } | |
848 | ||
849 | // Set operations. | |
850 | iterator | |
851 | find(const key_type& __x); | |
852 | ||
853 | const_iterator | |
854 | find(const key_type& __x) const; | |
855 | ||
856 | size_type | |
857 | count(const key_type& __x) const; | |
858 | ||
859 | iterator | |
860 | lower_bound(const key_type& __x); | |
861 | ||
862 | const_iterator | |
863 | lower_bound(const key_type& __x) const; | |
864 | ||
865 | iterator | |
866 | upper_bound(const key_type& __x); | |
867 | ||
868 | const_iterator | |
869 | upper_bound(const key_type& __x) const; | |
870 | ||
871 | pair<iterator,iterator> | |
872 | equal_range(const key_type& __x); | |
873 | ||
874 | pair<const_iterator, const_iterator> | |
875 | equal_range(const key_type& __x) const; | |
876 | ||
877 | // Debugging. | |
878 | bool | |
879 | __rb_verify() const; | |
880 | }; | |
881 | ||
882 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
883 | typename _Compare, typename _Alloc> | |
884 | inline bool | |
885 | operator==(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x, | |
886 | const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y) | |
887 | { | |
888 | return __x.size() == __y.size() && | |
889 | equal(__x.begin(), __x.end(), __y.begin()); | |
725dc051 | 890 | } |
d3d526ac BK |
891 | |
892 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
893 | typename _Compare, typename _Alloc> | |
894 | inline bool | |
895 | operator<(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x, | |
896 | const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y) | |
897 | { | |
898 | return lexicographical_compare(__x.begin(), __x.end(), | |
899 | __y.begin(), __y.end()); | |
725dc051 | 900 | } |
d3d526ac BK |
901 | |
902 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
903 | typename _Compare, typename _Alloc> | |
904 | inline bool | |
905 | operator!=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x, | |
906 | const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y) | |
907 | { return !(__x == __y); } | |
908 | ||
909 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
910 | typename _Compare, typename _Alloc> | |
911 | inline bool | |
912 | operator>(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x, | |
913 | const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y) | |
914 | { return __y < __x; } | |
915 | ||
916 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
917 | typename _Compare, typename _Alloc> | |
918 | inline bool | |
919 | operator<=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x, | |
920 | const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y) | |
921 | { return !(__y < __x); } | |
922 | ||
923 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
924 | typename _Compare, typename _Alloc> | |
925 | inline bool | |
926 | operator>=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x, | |
927 | const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y) | |
928 | { return !(__x < __y); } | |
929 | ||
930 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
931 | typename _Compare, typename _Alloc> | |
932 | inline void | |
933 | swap(_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x, | |
934 | _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y) | |
935 | { __x.swap(__y); } | |
936 | ||
937 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
938 | typename _Compare, typename _Alloc> | |
939 | _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& | |
940 | _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: | |
941 | operator=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x) | |
942 | { | |
943 | if (this != &__x) | |
944 | { | |
945 | // Note that _Key may be a constant type. | |
946 | clear(); | |
947 | _M_node_count = 0; | |
948 | _M_key_compare = __x._M_key_compare; | |
949 | if (__x._M_root() == 0) | |
950 | { | |
951 | _M_root() = 0; | |
7f6dd1ca GB |
952 | _M_leftmost() = _M_end(); |
953 | _M_rightmost() = _M_end(); | |
d3d526ac BK |
954 | } |
955 | else | |
956 | { | |
7f6dd1ca | 957 | _M_root() = _M_copy(__x._M_root(), _M_end()); |
d3d526ac BK |
958 | _M_leftmost() = _S_minimum(_M_root()); |
959 | _M_rightmost() = _S_maximum(_M_root()); | |
960 | _M_node_count = __x._M_node_count; | |
961 | } | |
962 | } | |
963 | return *this; | |
725dc051 | 964 | } |
d3d526ac BK |
965 | |
966 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
967 | typename _Compare, typename _Alloc> | |
968 | typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator | |
969 | _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: | |
970 | _M_insert(_Base_ptr __x_, _Base_ptr __y_, const _Val& __v) | |
971 | { | |
972 | _Link_type __x = (_Link_type) __x_; | |
973 | _Link_type __y = (_Link_type) __y_; | |
974 | _Link_type __z; | |
975 | ||
7f6dd1ca | 976 | if (__y == &this->_M_header || __x != 0 || |
d3d526ac BK |
977 | _M_key_compare(_KeyOfValue()(__v), _S_key(__y))) |
978 | { | |
979 | __z = _M_create_node(__v); | |
980 | _S_left(__y) = __z; // also makes _M_leftmost() = __z | |
7f6dd1ca GB |
981 | // when __y == &_M_header |
982 | if (__y == &this->_M_header) | |
d3d526ac BK |
983 | { |
984 | _M_root() = __z; | |
985 | _M_rightmost() = __z; | |
986 | } | |
987 | else if (__y == _M_leftmost()) | |
988 | _M_leftmost() = __z; // maintain _M_leftmost() pointing to min node | |
989 | } | |
990 | else | |
991 | { | |
992 | __z = _M_create_node(__v); | |
993 | _S_right(__y) = __z; | |
994 | // Maintain _M_rightmost() pointing to max node. | |
995 | if (__y == _M_rightmost()) | |
996 | _M_rightmost() = __z; | |
997 | } | |
998 | _S_parent(__z) = __y; | |
999 | _S_left(__z) = 0; | |
1000 | _S_right(__z) = 0; | |
7f6dd1ca | 1001 | _Rb_tree_rebalance(__z, this->_M_header._M_parent); |
d3d526ac BK |
1002 | ++_M_node_count; |
1003 | return iterator(__z); | |
1004 | } | |
1005 | ||
1006 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
1007 | typename _Compare, typename _Alloc> | |
1008 | typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator | |
1009 | _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: | |
1010 | insert_equal(const _Val& __v) | |
1011 | { | |
7f6dd1ca | 1012 | _Link_type __y = _M_end(); |
d3d526ac BK |
1013 | _Link_type __x = _M_root(); |
1014 | while (__x != 0) | |
1015 | { | |
1016 | __y = __x; | |
1017 | __x = _M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ? | |
1018 | _S_left(__x) : _S_right(__x); | |
1019 | } | |
1020 | return _M_insert(__x, __y, __v); | |
1021 | } | |
1022 | ||
7f6dd1ca GB |
1023 | template<typename _Key, typename _Val, typename _KeyOfValue, |
1024 | typename _Compare, typename _Alloc> | |
1025 | void | |
1026 | _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: | |
1027 | swap(_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __t) | |
1028 | { | |
1029 | if (_M_root() == 0) | |
1030 | { | |
1031 | if (__t._M_root() != 0) | |
1032 | { | |
1033 | _M_root() = __t._M_root(); | |
1034 | _M_leftmost() = __t._M_leftmost(); | |
1035 | _M_rightmost() = __t._M_rightmost(); | |
1036 | _M_root()->_M_parent = _M_end(); | |
1037 | ||
1038 | __t._M_root() = 0; | |
1039 | __t._M_leftmost() = __t._M_end(); | |
1040 | __t._M_rightmost() = __t._M_end(); | |
1041 | } | |
1042 | } | |
1043 | else if (__t._M_root() == 0) | |
1044 | { | |
1045 | __t._M_root() = _M_root(); | |
1046 | __t._M_leftmost() = _M_leftmost(); | |
1047 | __t._M_rightmost() = _M_rightmost(); | |
1048 | __t._M_root()->_M_parent = __t._M_end(); | |
1049 | ||
1050 | _M_root() = 0; | |
1051 | _M_leftmost() = _M_end(); | |
1052 | _M_rightmost() = _M_end(); | |
1053 | } | |
1054 | else | |
1055 | { | |
1056 | std::swap(_M_root(),__t._M_root()); | |
1057 | std::swap(_M_leftmost(),__t._M_leftmost()); | |
1058 | std::swap(_M_rightmost(),__t._M_rightmost()); | |
1059 | ||
1060 | _M_root()->_M_parent = _M_end(); | |
1061 | __t._M_root()->_M_parent = __t._M_end(); | |
1062 | } | |
1063 | // No need to swap header's color as it does not change. | |
1064 | std::swap(this->_M_node_count, __t._M_node_count); | |
1065 | std::swap(this->_M_key_compare, __t._M_key_compare); | |
1066 | } | |
1067 | ||
d3d526ac BK |
1068 | template<typename _Key, typename _Val, typename _KeyOfValue, |
1069 | typename _Compare, typename _Alloc> | |
1070 | pair<typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator, | |
1071 | bool> | |
1072 | _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: | |
1073 | insert_unique(const _Val& __v) | |
1074 | { | |
7f6dd1ca | 1075 | _Link_type __y = _M_end(); |
d3d526ac BK |
1076 | _Link_type __x = _M_root(); |
1077 | bool __comp = true; | |
1078 | while (__x != 0) | |
1079 | { | |
1080 | __y = __x; | |
1081 | __comp = _M_key_compare(_KeyOfValue()(__v), _S_key(__x)); | |
1082 | __x = __comp ? _S_left(__x) : _S_right(__x); | |
1083 | } | |
1084 | iterator __j = iterator(__y); | |
1085 | if (__comp) | |
1086 | if (__j == begin()) | |
1087 | return pair<iterator,bool>(_M_insert(__x, __y, __v), true); | |
1088 | else | |
1089 | --__j; | |
1090 | if (_M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v))) | |
1091 | return pair<iterator,bool>(_M_insert(__x, __y, __v), true); | |
1092 | return pair<iterator,bool>(__j, false); | |
1093 | } | |
1094 | ||
1095 | ||
1096 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
1097 | typename _Compare, typename _Alloc> | |
1098 | typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator | |
1099 | _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: | |
1100 | insert_unique(iterator __position, const _Val& __v) | |
1101 | { | |
7f6dd1ca | 1102 | if (__position._M_node == this->_M_header._M_left) |
d3d526ac BK |
1103 | { |
1104 | // begin() | |
1105 | if (size() > 0 && | |
1106 | _M_key_compare(_KeyOfValue()(__v), _S_key(__position._M_node))) | |
1107 | return _M_insert(__position._M_node, __position._M_node, __v); | |
1108 | // first argument just needs to be non-null | |
1109 | else | |
1110 | return insert_unique(__v).first; | |
1111 | } | |
7f6dd1ca | 1112 | else if (__position._M_node == &this->_M_header) |
d3d526ac BK |
1113 | { |
1114 | // end() | |
1115 | if (_M_key_compare(_S_key(_M_rightmost()), _KeyOfValue()(__v))) | |
1116 | return _M_insert(0, _M_rightmost(), __v); | |
1117 | else | |
1118 | return insert_unique(__v).first; | |
1119 | } | |
1120 | else | |
1121 | { | |
1122 | iterator __before = __position; | |
1123 | --__before; | |
1124 | if (_M_key_compare(_S_key(__before._M_node), _KeyOfValue()(__v)) | |
1125 | && _M_key_compare(_KeyOfValue()(__v),_S_key(__position._M_node))) | |
1126 | { | |
1127 | if (_S_right(__before._M_node) == 0) | |
1128 | return _M_insert(0, __before._M_node, __v); | |
1129 | else | |
1130 | return _M_insert(__position._M_node, __position._M_node, __v); | |
1131 | // first argument just needs to be non-null | |
1132 | } | |
1133 | else | |
1134 | return insert_unique(__v).first; | |
1135 | } | |
725dc051 | 1136 | } |
d3d526ac BK |
1137 | |
1138 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
1139 | typename _Compare, typename _Alloc> | |
1140 | typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator | |
1141 | _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: | |
1142 | insert_equal(iterator __position, const _Val& __v) | |
1143 | { | |
7f6dd1ca | 1144 | if (__position._M_node == this->_M_header._M_left) |
d3d526ac BK |
1145 | { |
1146 | // begin() | |
1147 | if (size() > 0 && | |
1148 | !_M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__v))) | |
1149 | return _M_insert(__position._M_node, __position._M_node, __v); | |
1150 | // first argument just needs to be non-null | |
1151 | else | |
1152 | return insert_equal(__v); | |
1153 | } | |
7f6dd1ca | 1154 | else if (__position._M_node == &this->_M_header) |
d3d526ac BK |
1155 | { |
1156 | // end() | |
1157 | if (!_M_key_compare(_KeyOfValue()(__v), _S_key(_M_rightmost()))) | |
1158 | return _M_insert(0, _M_rightmost(), __v); | |
1159 | else | |
1160 | return insert_equal(__v); | |
1161 | } | |
1162 | else | |
1163 | { | |
1164 | iterator __before = __position; | |
1165 | --__before; | |
1166 | if (!_M_key_compare(_KeyOfValue()(__v), _S_key(__before._M_node)) | |
1167 | && !_M_key_compare(_S_key(__position._M_node), | |
1168 | _KeyOfValue()(__v))) | |
1169 | { | |
1170 | if (_S_right(__before._M_node) == 0) | |
1171 | return _M_insert(0, __before._M_node, __v); | |
1172 | else | |
1173 | return _M_insert(__position._M_node, __position._M_node, __v); | |
1174 | // first argument just needs to be non-null | |
1175 | } | |
1176 | else | |
1177 | return insert_equal(__v); | |
1178 | } | |
1179 | } | |
1180 | ||
1181 | template<typename _Key, typename _Val, typename _KoV, | |
1182 | typename _Cmp, typename _Alloc> | |
1183 | template<class _II> | |
1184 | void | |
1185 | _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>:: | |
1186 | insert_equal(_II __first, _II __last) | |
322821b9 | 1187 | { |
d3d526ac BK |
1188 | for ( ; __first != __last; ++__first) |
1189 | insert_equal(*__first); | |
322821b9 | 1190 | } |
725dc051 | 1191 | |
d3d526ac BK |
1192 | template<typename _Key, typename _Val, typename _KoV, |
1193 | typename _Cmp, typename _Alloc> | |
1194 | template<class _II> | |
1195 | void | |
1196 | _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>:: | |
1197 | insert_unique(_II __first, _II __last) | |
1198 | { | |
1199 | for ( ; __first != __last; ++__first) | |
1200 | insert_unique(*__first); | |
1201 | } | |
725dc051 | 1202 | |
d3d526ac BK |
1203 | template<typename _Key, typename _Val, typename _KeyOfValue, |
1204 | typename _Compare, typename _Alloc> | |
1205 | inline void | |
1206 | _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::erase(iterator __position) | |
1207 | { | |
1208 | _Link_type __y = | |
1209 | (_Link_type) _Rb_tree_rebalance_for_erase(__position._M_node, | |
7f6dd1ca GB |
1210 | this->_M_header._M_parent, |
1211 | this->_M_header._M_left, | |
1212 | this->_M_header._M_right); | |
d3d526ac BK |
1213 | destroy_node(__y); |
1214 | --_M_node_count; | |
1215 | } | |
725dc051 | 1216 | |
d3d526ac BK |
1217 | template<typename _Key, typename _Val, typename _KeyOfValue, |
1218 | typename _Compare, typename _Alloc> | |
1219 | typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::size_type | |
1220 | _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::erase(const _Key& __x) | |
1221 | { | |
1222 | pair<iterator,iterator> __p = equal_range(__x); | |
4977bab6 | 1223 | size_type __n = std::distance(__p.first, __p.second); |
d3d526ac BK |
1224 | erase(__p.first, __p.second); |
1225 | return __n; | |
725dc051 | 1226 | } |
725dc051 | 1227 | |
d3d526ac BK |
1228 | template<typename _Key, typename _Val, typename _KoV, |
1229 | typename _Compare, typename _Alloc> | |
1230 | typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type | |
1231 | _Rb_tree<_Key,_Val,_KoV,_Compare,_Alloc>:: | |
1232 | _M_copy(_Link_type __x, _Link_type __p) | |
1233 | { | |
1234 | // Structural copy. __x and __p must be non-null. | |
1235 | _Link_type __top = _M_clone_node(__x); | |
1236 | __top->_M_parent = __p; | |
1237 | ||
1238 | try | |
1239 | { | |
1240 | if (__x->_M_right) | |
1241 | __top->_M_right = _M_copy(_S_right(__x), __top); | |
1242 | __p = __top; | |
1243 | __x = _S_left(__x); | |
1244 | ||
1245 | while (__x != 0) | |
1246 | { | |
1247 | _Link_type __y = _M_clone_node(__x); | |
1248 | __p->_M_left = __y; | |
1249 | __y->_M_parent = __p; | |
1250 | if (__x->_M_right) | |
1251 | __y->_M_right = _M_copy(_S_right(__x), __y); | |
1252 | __p = __y; | |
1253 | __x = _S_left(__x); | |
1254 | } | |
1255 | } | |
1256 | catch(...) | |
1257 | { | |
1258 | _M_erase(__top); | |
1259 | __throw_exception_again; | |
1260 | } | |
1261 | return __top; | |
725dc051 | 1262 | } |
d3d526ac BK |
1263 | |
1264 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
1265 | typename _Compare, typename _Alloc> | |
1266 | void | |
1267 | _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::_M_erase(_Link_type __x) | |
1268 | { | |
1269 | // Erase without rebalancing. | |
1270 | while (__x != 0) | |
1271 | { | |
1272 | _M_erase(_S_right(__x)); | |
1273 | _Link_type __y = _S_left(__x); | |
1274 | destroy_node(__x); | |
1275 | __x = __y; | |
1276 | } | |
725dc051 | 1277 | } |
d3d526ac BK |
1278 | |
1279 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
1280 | typename _Compare, typename _Alloc> | |
1281 | void | |
1282 | _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: | |
1283 | erase(iterator __first, iterator __last) | |
1284 | { | |
1285 | if (__first == begin() && __last == end()) | |
1286 | clear(); | |
1287 | else | |
1288 | while (__first != __last) erase(__first++); | |
725dc051 | 1289 | } |
d3d526ac BK |
1290 | |
1291 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
1292 | typename _Compare, typename _Alloc> | |
1293 | void | |
1294 | _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: | |
1295 | erase(const _Key* __first, const _Key* __last) | |
1296 | { | |
1297 | while (__first != __last) | |
1298 | erase(*__first++); | |
725dc051 | 1299 | } |
d3d526ac BK |
1300 | |
1301 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
1302 | typename _Compare, typename _Alloc> | |
1303 | typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator | |
1304 | _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::find(const _Key& __k) | |
1305 | { | |
7f6dd1ca GB |
1306 | _Link_type __y = _M_end(); // Last node which is not less than __k. |
1307 | _Link_type __x = _M_root(); // Current node. | |
d3d526ac BK |
1308 | |
1309 | while (__x != 0) | |
1310 | if (!_M_key_compare(_S_key(__x), __k)) | |
1311 | __y = __x, __x = _S_left(__x); | |
1312 | else | |
1313 | __x = _S_right(__x); | |
1314 | ||
1315 | iterator __j = iterator(__y); | |
1316 | return (__j == end() || _M_key_compare(__k, _S_key(__j._M_node))) ? | |
1317 | end() : __j; | |
1318 | } | |
1319 | ||
1320 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
1321 | typename _Compare, typename _Alloc> | |
1322 | typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::const_iterator | |
1323 | _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: | |
1324 | find(const _Key& __k) const | |
1325 | { | |
7f6dd1ca | 1326 | _Link_type __y = _M_end(); // Last node which is not less than __k. |
d3d526ac | 1327 | _Link_type __x = _M_root(); // Current node. |
725dc051 | 1328 | |
d3d526ac BK |
1329 | while (__x != 0) |
1330 | { | |
1331 | if (!_M_key_compare(_S_key(__x), __k)) | |
1332 | __y = __x, __x = _S_left(__x); | |
1333 | else | |
1334 | __x = _S_right(__x); | |
1335 | } | |
1336 | const_iterator __j = const_iterator(__y); | |
1337 | return (__j == end() || _M_key_compare(__k, _S_key(__j._M_node))) ? | |
1338 | end() : __j; | |
725dc051 | 1339 | } |
d3d526ac BK |
1340 | |
1341 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
1342 | typename _Compare, typename _Alloc> | |
1343 | typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::size_type | |
1344 | _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: | |
1345 | count(const _Key& __k) const | |
322821b9 | 1346 | { |
d3d526ac | 1347 | pair<const_iterator, const_iterator> __p = equal_range(__k); |
4977bab6 | 1348 | size_type __n = std::distance(__p.first, __p.second); |
d3d526ac | 1349 | return __n; |
322821b9 | 1350 | } |
d3d526ac BK |
1351 | |
1352 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
1353 | typename _Compare, typename _Alloc> | |
1354 | typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator | |
1355 | _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: | |
1356 | lower_bound(const _Key& __k) | |
1357 | { | |
7f6dd1ca GB |
1358 | _Link_type __y = _M_end(); // Last node which is not less than __k |
1359 | _Link_type __x = _M_root(); // Current node. | |
d3d526ac BK |
1360 | |
1361 | while (__x != 0) | |
1362 | if (!_M_key_compare(_S_key(__x), __k)) | |
1363 | __y = __x, __x = _S_left(__x); | |
1364 | else | |
1365 | __x = _S_right(__x); | |
1366 | ||
1367 | return iterator(__y); | |
1368 | } | |
1369 | ||
1370 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
1371 | typename _Compare, typename _Alloc> | |
1372 | typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::const_iterator | |
1373 | _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: | |
1374 | lower_bound(const _Key& __k) const | |
1375 | { | |
7f6dd1ca GB |
1376 | _Link_type __y = _M_end(); // Last node which is not less than __k. |
1377 | _Link_type __x = _M_root(); // Current node. | |
d3d526ac BK |
1378 | |
1379 | while (__x != 0) | |
1380 | if (!_M_key_compare(_S_key(__x), __k)) | |
1381 | __y = __x, __x = _S_left(__x); | |
1382 | else | |
1383 | __x = _S_right(__x); | |
1384 | ||
1385 | return const_iterator(__y); | |
1386 | } | |
1387 | ||
1388 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
1389 | typename _Compare, typename _Alloc> | |
1390 | typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator | |
1391 | _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: | |
1392 | upper_bound(const _Key& __k) | |
1393 | { | |
7f6dd1ca GB |
1394 | _Link_type __y = _M_end(); // Last node which is greater than __k. |
1395 | _Link_type __x = _M_root(); // Current node. | |
d3d526ac BK |
1396 | |
1397 | while (__x != 0) | |
1398 | if (_M_key_compare(__k, _S_key(__x))) | |
1399 | __y = __x, __x = _S_left(__x); | |
1400 | else | |
1401 | __x = _S_right(__x); | |
1402 | ||
1403 | return iterator(__y); | |
1404 | } | |
1405 | ||
1406 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
1407 | typename _Compare, typename _Alloc> | |
1408 | typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::const_iterator | |
1409 | _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: | |
1410 | upper_bound(const _Key& __k) const | |
1411 | { | |
7f6dd1ca GB |
1412 | _Link_type __y = _M_end(); // Last node which is greater than __k. |
1413 | _Link_type __x = _M_root(); // Current node. | |
d3d526ac BK |
1414 | |
1415 | while (__x != 0) | |
1416 | if (_M_key_compare(__k, _S_key(__x))) | |
1417 | __y = __x, __x = _S_left(__x); | |
1418 | else | |
1419 | __x = _S_right(__x); | |
1420 | ||
1421 | return const_iterator(__y); | |
1422 | } | |
1423 | ||
1424 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
1425 | typename _Compare, typename _Alloc> | |
1426 | inline | |
1427 | pair<typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator, | |
1428 | typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator> | |
1429 | _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: | |
1430 | equal_range(const _Key& __k) | |
1431 | { return pair<iterator, iterator>(lower_bound(__k), upper_bound(__k)); } | |
1432 | ||
1433 | template<typename _Key, typename _Val, typename _KoV, | |
1434 | typename _Compare, typename _Alloc> | |
1435 | inline | |
1436 | pair<typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::const_iterator, | |
1437 | typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::const_iterator> | |
1438 | _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc> | |
1439 | ::equal_range(const _Key& __k) const | |
1440 | { | |
1441 | return pair<const_iterator,const_iterator>(lower_bound(__k), | |
1442 | upper_bound(__k)); | |
725dc051 | 1443 | } |
d3d526ac BK |
1444 | |
1445 | inline int | |
1446 | __black_count(_Rb_tree_node_base* __node, _Rb_tree_node_base* __root) | |
1447 | { | |
1448 | if (__node == 0) | |
1449 | return 0; | |
1450 | int __sum = 0; | |
1451 | do | |
1452 | { | |
655d7821 | 1453 | if (__node->_M_color == _S_black) |
d3d526ac BK |
1454 | ++__sum; |
1455 | if (__node == __root) | |
1456 | break; | |
1457 | __node = __node->_M_parent; | |
1458 | } | |
1459 | while (1); | |
1460 | return __sum; | |
725dc051 | 1461 | } |
d3d526ac BK |
1462 | |
1463 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
1464 | typename _Compare, typename _Alloc> | |
1465 | bool | |
1466 | _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const | |
1467 | { | |
1468 | if (_M_node_count == 0 || begin() == end()) | |
1469 | return _M_node_count == 0 && begin() == end() && | |
7f6dd1ca GB |
1470 | this->_M_header._M_left == &this->_M_header && |
1471 | this->_M_header._M_right == &this->_M_header; | |
725dc051 | 1472 | |
d3d526ac BK |
1473 | int __len = __black_count(_M_leftmost(), _M_root()); |
1474 | for (const_iterator __it = begin(); __it != end(); ++__it) | |
1475 | { | |
1476 | _Link_type __x = (_Link_type) __it._M_node; | |
1477 | _Link_type __L = _S_left(__x); | |
1478 | _Link_type __R = _S_right(__x); | |
1479 | ||
655d7821 BK |
1480 | if (__x->_M_color == _S_red) |
1481 | if ((__L && __L->_M_color == _S_red) | |
1482 | || (__R && __R->_M_color == _S_red)) | |
d3d526ac BK |
1483 | return false; |
1484 | ||
1485 | if (__L && _M_key_compare(_S_key(__x), _S_key(__L))) | |
1486 | return false; | |
1487 | if (__R && _M_key_compare(_S_key(__R), _S_key(__x))) | |
1488 | return false; | |
1489 | ||
1490 | if (!__L && !__R && __black_count(__x, _M_root()) != __len) | |
1491 | return false; | |
1492 | } | |
1493 | ||
1494 | if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root())) | |
725dc051 | 1495 | return false; |
d3d526ac | 1496 | if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root())) |
725dc051 | 1497 | return false; |
d3d526ac BK |
1498 | return true; |
1499 | } | |
d53d7f6e | 1500 | } // namespace std |
725dc051 | 1501 | |
d3d526ac | 1502 | #endif |