]>
Commit | Line | Data |
---|---|---|
42526146 PE |
1 | // RB tree implementation -*- C++ -*- |
2 | ||
62e67651 | 3 | // Copyright (C) 2001, 2002, 2003, 2004 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 | 65 | |
725dc051 | 66 | #include <bits/stl_algobase.h> |
1ff9402d | 67 | #include <bits/allocator.h> |
725dc051 BK |
68 | #include <bits/stl_construct.h> |
69 | #include <bits/stl_function.h> | |
8bd22a3c | 70 | #include <bits/cpp_type_traits.h> |
725dc051 | 71 | |
d53d7f6e | 72 | namespace std |
ed6814f7 | 73 | { |
8bd22a3c BK |
74 | // Red-black tree class, designed for use in implementing STL |
75 | // associative containers (set, multiset, map, and multimap). The | |
76 | // insertion and deletion algorithms are based on those in Cormen, | |
77 | // Leiserson, and Rivest, Introduction to Algorithms (MIT Press, | |
78 | // 1990), except that | |
79 | // | |
80 | // (1) the header cell is maintained with links not only to the root | |
81 | // but also to the leftmost node of the tree, to enable constant | |
82 | // time begin(), and to the rightmost node of the tree, to enable | |
83 | // linear time performance when used with the generic set algorithms | |
84 | // (set_union, etc.) | |
85 | // | |
86 | // (2) when a node being deleted has two children its successor node | |
87 | // is relinked into its place, rather than copied, so that the only | |
88 | // iterators invalidated are those referring to the deleted node. | |
89 | ||
655d7821 | 90 | enum _Rb_tree_color { _S_red = false, _S_black = true }; |
725dc051 | 91 | |
d3d526ac BK |
92 | struct _Rb_tree_node_base |
93 | { | |
94 | typedef _Rb_tree_node_base* _Base_ptr; | |
b4c70e89 | 95 | typedef const _Rb_tree_node_base* _Const_Base_ptr; |
ed6814f7 BI |
96 | |
97 | _Rb_tree_color _M_color; | |
98 | _Base_ptr _M_parent; | |
99 | _Base_ptr _M_left; | |
100 | _Base_ptr _M_right; | |
101 | ||
102 | static _Base_ptr | |
d3d526ac BK |
103 | _S_minimum(_Base_ptr __x) |
104 | { | |
105 | while (__x->_M_left != 0) __x = __x->_M_left; | |
106 | return __x; | |
107 | } | |
725dc051 | 108 | |
b4c70e89 GB |
109 | static _Const_Base_ptr |
110 | _S_minimum(_Const_Base_ptr __x) | |
111 | { | |
112 | while (__x->_M_left != 0) __x = __x->_M_left; | |
113 | return __x; | |
114 | } | |
115 | ||
ed6814f7 | 116 | static _Base_ptr |
d3d526ac BK |
117 | _S_maximum(_Base_ptr __x) |
118 | { | |
119 | while (__x->_M_right != 0) __x = __x->_M_right; | |
120 | return __x; | |
121 | } | |
b4c70e89 GB |
122 | |
123 | static _Const_Base_ptr | |
124 | _S_maximum(_Const_Base_ptr __x) | |
125 | { | |
126 | while (__x->_M_right != 0) __x = __x->_M_right; | |
127 | return __x; | |
128 | } | |
d3d526ac | 129 | }; |
725dc051 | 130 | |
d3d526ac BK |
131 | template<typename _Val> |
132 | struct _Rb_tree_node : public _Rb_tree_node_base | |
133 | { | |
134 | typedef _Rb_tree_node<_Val>* _Link_type; | |
135 | _Val _M_value_field; | |
136 | }; | |
ed6814f7 | 137 | |
b4c70e89 GB |
138 | _Rb_tree_node_base* |
139 | _Rb_tree_increment(_Rb_tree_node_base* __x); | |
d3d526ac | 140 | |
e135a038 BK |
141 | const _Rb_tree_node_base* |
142 | _Rb_tree_increment(const _Rb_tree_node_base* __x); | |
143 | ||
b4c70e89 GB |
144 | _Rb_tree_node_base* |
145 | _Rb_tree_decrement(_Rb_tree_node_base* __x); | |
d3d526ac | 146 | |
e135a038 BK |
147 | const _Rb_tree_node_base* |
148 | _Rb_tree_decrement(const _Rb_tree_node_base* __x); | |
149 | ||
150 | template<typename _Tp> | |
b4c70e89 | 151 | struct _Rb_tree_iterator |
d3d526ac | 152 | { |
e135a038 BK |
153 | typedef _Tp value_type; |
154 | typedef _Tp& reference; | |
155 | typedef _Tp* pointer; | |
156 | ||
b4c70e89 | 157 | typedef bidirectional_iterator_tag iterator_category; |
e135a038 BK |
158 | typedef ptrdiff_t difference_type; |
159 | ||
160 | typedef _Rb_tree_iterator<_Tp> _Self; | |
161 | typedef _Rb_tree_node_base::_Base_ptr _Base_ptr; | |
162 | typedef _Rb_tree_node<_Tp>* _Link_type; | |
ed6814f7 | 163 | |
8bd22a3c | 164 | _Rb_tree_iterator() { } |
b4c70e89 GB |
165 | |
166 | _Rb_tree_iterator(_Link_type __x) | |
8bd22a3c | 167 | : _M_node(__x) { } |
b4c70e89 | 168 | |
ed6814f7 | 169 | reference |
b4c70e89 GB |
170 | operator*() const |
171 | { return static_cast<_Link_type>(_M_node)->_M_value_field; } | |
d3d526ac | 172 | |
ed6814f7 | 173 | pointer |
b4c70e89 GB |
174 | operator->() const |
175 | { return &static_cast<_Link_type>(_M_node)->_M_value_field; } | |
d3d526ac | 176 | |
ed6814f7 BI |
177 | _Self& |
178 | operator++() | |
179 | { | |
b4c70e89 | 180 | _M_node = _Rb_tree_increment(_M_node); |
ed6814f7 | 181 | return *this; |
d3d526ac | 182 | } |
725dc051 | 183 | |
ed6814f7 BI |
184 | _Self |
185 | operator++(int) | |
d3d526ac BK |
186 | { |
187 | _Self __tmp = *this; | |
b4c70e89 | 188 | _M_node = _Rb_tree_increment(_M_node); |
d3d526ac BK |
189 | return __tmp; |
190 | } | |
ed6814f7 BI |
191 | |
192 | _Self& | |
b4c70e89 GB |
193 | operator--() |
194 | { | |
195 | _M_node = _Rb_tree_decrement(_M_node); | |
196 | return *this; | |
197 | } | |
d3d526ac | 198 | |
ed6814f7 BI |
199 | _Self |
200 | operator--(int) | |
d3d526ac BK |
201 | { |
202 | _Self __tmp = *this; | |
b4c70e89 | 203 | _M_node = _Rb_tree_decrement(_M_node); |
d3d526ac BK |
204 | return __tmp; |
205 | } | |
b4c70e89 | 206 | |
e135a038 BK |
207 | bool |
208 | operator==(const _Self& __x) const | |
209 | { return _M_node == __x._M_node; } | |
210 | ||
211 | bool | |
212 | operator!=(const _Self& __x) const | |
213 | { return _M_node != __x._M_node; } | |
214 | ||
b4c70e89 | 215 | _Base_ptr _M_node; |
d3d526ac BK |
216 | }; |
217 | ||
e135a038 BK |
218 | template<typename _Tp> |
219 | struct _Rb_tree_const_iterator | |
220 | { | |
221 | typedef _Tp value_type; | |
222 | typedef const _Tp& reference; | |
223 | typedef const _Tp* pointer; | |
d3d526ac | 224 | |
e135a038 | 225 | typedef _Rb_tree_iterator<_Tp> iterator; |
d3d526ac | 226 | |
e135a038 BK |
227 | typedef bidirectional_iterator_tag iterator_category; |
228 | typedef ptrdiff_t difference_type; | |
d3d526ac | 229 | |
e135a038 BK |
230 | typedef _Rb_tree_const_iterator<_Tp> _Self; |
231 | typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr; | |
232 | typedef const _Rb_tree_node<_Tp>* _Link_type; | |
ed6814f7 | 233 | |
8bd22a3c | 234 | _Rb_tree_const_iterator() { } |
e135a038 BK |
235 | |
236 | _Rb_tree_const_iterator(_Link_type __x) | |
8bd22a3c | 237 | : _M_node(__x) { } |
e135a038 BK |
238 | |
239 | _Rb_tree_const_iterator(const iterator& __it) | |
8bd22a3c | 240 | : _M_node(__it._M_node) { } |
e135a038 BK |
241 | |
242 | reference | |
243 | operator*() const | |
244 | { return static_cast<_Link_type>(_M_node)->_M_value_field; } | |
245 | ||
246 | pointer | |
247 | operator->() const | |
248 | { return &static_cast<_Link_type>(_M_node)->_M_value_field; } | |
249 | ||
ed6814f7 BI |
250 | _Self& |
251 | operator++() | |
252 | { | |
e135a038 | 253 | _M_node = _Rb_tree_increment(_M_node); |
ed6814f7 | 254 | return *this; |
e135a038 BK |
255 | } |
256 | ||
ed6814f7 BI |
257 | _Self |
258 | operator++(int) | |
e135a038 BK |
259 | { |
260 | _Self __tmp = *this; | |
261 | _M_node = _Rb_tree_increment(_M_node); | |
262 | return __tmp; | |
263 | } | |
ed6814f7 BI |
264 | |
265 | _Self& | |
e135a038 BK |
266 | operator--() |
267 | { | |
268 | _M_node = _Rb_tree_decrement(_M_node); | |
269 | return *this; | |
270 | } | |
271 | ||
ed6814f7 BI |
272 | _Self |
273 | operator--(int) | |
e135a038 BK |
274 | { |
275 | _Self __tmp = *this; | |
276 | _M_node = _Rb_tree_decrement(_M_node); | |
277 | return __tmp; | |
278 | } | |
279 | ||
280 | bool | |
281 | operator==(const _Self& __x) const | |
282 | { return _M_node == __x._M_node; } | |
283 | ||
284 | bool | |
285 | operator!=(const _Self& __x) const | |
286 | { return _M_node != __x._M_node; } | |
287 | ||
288 | _Base_ptr _M_node; | |
737ab798 | 289 | }; |
d3d526ac BK |
290 | |
291 | template<typename _Val> | |
ed6814f7 | 292 | inline bool |
e135a038 | 293 | operator==(const _Rb_tree_iterator<_Val>& __x, |
ed6814f7 | 294 | const _Rb_tree_const_iterator<_Val>& __y) |
e135a038 | 295 | { return __x._M_node == __y._M_node; } |
d3d526ac BK |
296 | |
297 | template<typename _Val> | |
ed6814f7 | 298 | inline bool |
e135a038 | 299 | operator!=(const _Rb_tree_iterator<_Val>& __x, |
ed6814f7 | 300 | const _Rb_tree_const_iterator<_Val>& __y) |
d3d526ac BK |
301 | { return __x._M_node != __y._M_node; } |
302 | ||
ed6814f7 | 303 | void |
e135a038 BK |
304 | _Rb_tree_rotate_left(_Rb_tree_node_base* const __x, |
305 | _Rb_tree_node_base*& __root); | |
f92c5313 | 306 | |
ed6814f7 | 307 | void |
e135a038 BK |
308 | _Rb_tree_rotate_right(_Rb_tree_node_base* const __x, |
309 | _Rb_tree_node_base*& __root); | |
725dc051 | 310 | |
ed6814f7 | 311 | void |
8bd22a3c | 312 | _Rb_tree_insert_and_rebalance(const bool __insert_left, |
e135a038 BK |
313 | _Rb_tree_node_base* __x, |
314 | _Rb_tree_node_base* __p, | |
315 | _Rb_tree_node_base& __header); | |
ca1c7011 GB |
316 | |
317 | _Rb_tree_node_base* | |
ed6814f7 | 318 | _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z, |
8bd22a3c | 319 | _Rb_tree_node_base& __header); |
d3d526ac | 320 | |
d3d526ac | 321 | |
ed6814f7 | 322 | template<typename _Key, typename _Val, typename _KeyOfValue, |
d3d526ac | 323 | typename _Compare, typename _Alloc = allocator<_Val> > |
34c87829 | 324 | class _Rb_tree |
d3d526ac | 325 | { |
34c87829 MA |
326 | typedef typename _Alloc::template rebind<_Rb_tree_node<_Val> >::other |
327 | _Node_allocator; | |
ed6814f7 | 328 | |
d3d526ac BK |
329 | protected: |
330 | typedef _Rb_tree_node_base* _Base_ptr; | |
b4c70e89 | 331 | typedef const _Rb_tree_node_base* _Const_Base_ptr; |
d3d526ac | 332 | typedef _Rb_tree_node<_Val> _Rb_tree_node; |
ed6814f7 | 333 | |
d3d526ac BK |
334 | public: |
335 | typedef _Key key_type; | |
336 | typedef _Val value_type; | |
337 | typedef value_type* pointer; | |
338 | typedef const value_type* const_pointer; | |
339 | typedef value_type& reference; | |
340 | typedef const value_type& const_reference; | |
341 | typedef _Rb_tree_node* _Link_type; | |
b4c70e89 | 342 | typedef const _Rb_tree_node* _Const_Link_type; |
d3d526ac BK |
343 | typedef size_t size_type; |
344 | typedef ptrdiff_t difference_type; | |
34c87829 | 345 | typedef _Alloc allocator_type; |
8bd22a3c BK |
346 | |
347 | allocator_type | |
348 | get_allocator() const | |
349 | { return *static_cast<const _Node_allocator*>(&this->_M_impl); } | |
ed6814f7 | 350 | |
d3d526ac | 351 | protected: |
34c87829 | 352 | _Rb_tree_node* |
62e67651 | 353 | _M_get_node() |
8bd22a3c | 354 | { return _M_impl._Node_allocator::allocate(1); } |
34c87829 | 355 | |
ed6814f7 | 356 | void |
62e67651 | 357 | _M_put_node(_Rb_tree_node* __p) |
8bd22a3c | 358 | { _M_impl._Node_allocator::deallocate(__p, 1); } |
ed6814f7 | 359 | |
d3d526ac BK |
360 | _Link_type |
361 | _M_create_node(const value_type& __x) | |
362 | { | |
34c87829 | 363 | _Link_type __tmp = _M_get_node(); |
ed6814f7 | 364 | try |
1985f1cd | 365 | { get_allocator().construct(&__tmp->_M_value_field, __x); } |
d3d526ac BK |
366 | catch(...) |
367 | { | |
62e67651 | 368 | _M_put_node(__tmp); |
ed6814f7 | 369 | __throw_exception_again; |
d3d526ac BK |
370 | } |
371 | return __tmp; | |
725dc051 | 372 | } |
ed6814f7 BI |
373 | |
374 | _Link_type | |
b4c70e89 | 375 | _M_clone_node(_Const_Link_type __x) |
d3d526ac BK |
376 | { |
377 | _Link_type __tmp = _M_create_node(__x->_M_value_field); | |
378 | __tmp->_M_color = __x->_M_color; | |
379 | __tmp->_M_left = 0; | |
380 | __tmp->_M_right = 0; | |
381 | return __tmp; | |
725dc051 | 382 | } |
d3d526ac BK |
383 | |
384 | void | |
385 | destroy_node(_Link_type __p) | |
386 | { | |
1985f1cd | 387 | get_allocator().destroy(&__p->_M_value_field); |
d3d526ac BK |
388 | _M_put_node(__p); |
389 | } | |
390 | ||
34c87829 | 391 | protected: |
8bd22a3c BK |
392 | template<typename _Key_compare, |
393 | bool _Is_pod_comparator = std::__is_pod<_Key_compare>::_M_type> | |
394 | struct _Rb_tree_impl : public _Node_allocator | |
395 | { | |
396 | _Key_compare _M_key_compare; | |
397 | _Rb_tree_node_base _M_header; | |
398 | size_type _M_node_count; // Keeps track of size of tree. | |
399 | ||
400 | _Rb_tree_impl(const _Node_allocator& __a = _Node_allocator(), | |
401 | const _Key_compare& __comp = _Key_compare()) | |
06ce7726 | 402 | : _Node_allocator(__a), _M_key_compare(__comp), _M_node_count(0) |
8bd22a3c BK |
403 | { |
404 | this->_M_header._M_color = _S_red; | |
405 | this->_M_header._M_parent = 0; | |
406 | this->_M_header._M_left = &this->_M_header; | |
407 | this->_M_header._M_right = &this->_M_header; | |
408 | } | |
409 | }; | |
410 | ||
411 | // Specialization for _Comparison types that are not capable of | |
412 | // being base classes / super classes. | |
413 | template<typename _Key_compare> | |
414 | struct _Rb_tree_impl<_Key_compare, true> : public _Node_allocator | |
415 | { | |
416 | _Key_compare _M_key_compare; | |
417 | _Rb_tree_node_base _M_header; | |
418 | size_type _M_node_count; // Keeps track of size of tree. | |
419 | ||
420 | _Rb_tree_impl(const _Node_allocator& __a = _Node_allocator(), | |
421 | const _Key_compare& __comp = _Key_compare()) | |
422 | : _Node_allocator(__a), _M_key_compare(__comp), _M_node_count(0) | |
423 | { | |
424 | this->_M_header._M_color = _S_red; | |
425 | this->_M_header._M_parent = 0; | |
426 | this->_M_header._M_left = &this->_M_header; | |
427 | this->_M_header._M_right = &this->_M_header; | |
428 | } | |
429 | }; | |
430 | ||
431 | _Rb_tree_impl<_Compare> _M_impl; | |
ed6814f7 | 432 | |
34c87829 | 433 | protected: |
b4c70e89 | 434 | _Base_ptr& |
62e67651 | 435 | _M_root() |
8bd22a3c | 436 | { return this->_M_impl._M_header._M_parent; } |
d3d526ac | 437 | |
b4c70e89 | 438 | _Const_Base_ptr |
62e67651 | 439 | _M_root() const |
8bd22a3c | 440 | { return this->_M_impl._M_header._M_parent; } |
d3d526ac | 441 | |
b4c70e89 | 442 | _Base_ptr& |
62e67651 | 443 | _M_leftmost() |
8bd22a3c | 444 | { return this->_M_impl._M_header._M_left; } |
b4c70e89 GB |
445 | |
446 | _Const_Base_ptr | |
62e67651 | 447 | _M_leftmost() const |
8bd22a3c | 448 | { return this->_M_impl._M_header._M_left; } |
b4c70e89 GB |
449 | |
450 | _Base_ptr& | |
62e67651 | 451 | _M_rightmost() |
8bd22a3c | 452 | { return this->_M_impl._M_header._M_right; } |
b4c70e89 GB |
453 | |
454 | _Const_Base_ptr | |
62e67651 | 455 | _M_rightmost() const |
8bd22a3c | 456 | { return this->_M_impl._M_header._M_right; } |
d3d526ac | 457 | |
7f6dd1ca | 458 | _Link_type |
62e67651 | 459 | _M_begin() |
8bd22a3c | 460 | { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); } |
b4c70e89 GB |
461 | |
462 | _Const_Link_type | |
62e67651 | 463 | _M_begin() const |
11aaf40c PC |
464 | { |
465 | return static_cast<_Const_Link_type> | |
466 | (this->_M_impl._M_header._M_parent); | |
467 | } | |
d3d526ac | 468 | |
b4c70e89 | 469 | _Link_type |
62e67651 | 470 | _M_end() |
8bd22a3c | 471 | { return static_cast<_Link_type>(&this->_M_impl._M_header); } |
d3d526ac | 472 | |
b4c70e89 | 473 | _Const_Link_type |
62e67651 | 474 | _M_end() const |
8bd22a3c | 475 | { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); } |
d3d526ac | 476 | |
ed6814f7 | 477 | static const_reference |
62e67651 PC |
478 | _S_value(_Const_Link_type __x) |
479 | { return __x->_M_value_field; } | |
d3d526ac | 480 | |
ed6814f7 | 481 | static const _Key& |
62e67651 PC |
482 | _S_key(_Const_Link_type __x) |
483 | { return _KeyOfValue()(_S_value(__x)); } | |
b4c70e89 GB |
484 | |
485 | static _Link_type | |
62e67651 PC |
486 | _S_left(_Base_ptr __x) |
487 | { return static_cast<_Link_type>(__x->_M_left); } | |
d3d526ac | 488 | |
b4c70e89 | 489 | static _Const_Link_type |
62e67651 PC |
490 | _S_left(_Const_Base_ptr __x) |
491 | { return static_cast<_Const_Link_type>(__x->_M_left); } | |
d3d526ac | 492 | |
b4c70e89 | 493 | static _Link_type |
62e67651 PC |
494 | _S_right(_Base_ptr __x) |
495 | { return static_cast<_Link_type>(__x->_M_right); } | |
d3d526ac | 496 | |
b4c70e89 | 497 | static _Const_Link_type |
62e67651 PC |
498 | _S_right(_Const_Base_ptr __x) |
499 | { return static_cast<_Const_Link_type>(__x->_M_right); } | |
d3d526ac | 500 | |
b4c70e89 | 501 | static const_reference |
62e67651 PC |
502 | _S_value(_Const_Base_ptr __x) |
503 | { return static_cast<_Const_Link_type>(__x)->_M_value_field; } | |
d3d526ac | 504 | |
ed6814f7 | 505 | static const _Key& |
62e67651 PC |
506 | _S_key(_Const_Base_ptr __x) |
507 | { return _KeyOfValue()(_S_value(__x)); } | |
b4c70e89 | 508 | |
ed6814f7 BI |
509 | static _Base_ptr |
510 | _S_minimum(_Base_ptr __x) | |
b4c70e89 | 511 | { return _Rb_tree_node_base::_S_minimum(__x); } |
d3d526ac | 512 | |
b4c70e89 GB |
513 | static _Const_Base_ptr |
514 | _S_minimum(_Const_Base_ptr __x) | |
515 | { return _Rb_tree_node_base::_S_minimum(__x); } | |
d3d526ac | 516 | |
b4c70e89 GB |
517 | static _Base_ptr |
518 | _S_maximum(_Base_ptr __x) | |
519 | { return _Rb_tree_node_base::_S_maximum(__x); } | |
d3d526ac | 520 | |
b4c70e89 GB |
521 | static _Const_Base_ptr |
522 | _S_maximum(_Const_Base_ptr __x) | |
523 | { return _Rb_tree_node_base::_S_maximum(__x); } | |
d3d526ac BK |
524 | |
525 | public: | |
e135a038 BK |
526 | typedef _Rb_tree_iterator<value_type> iterator; |
527 | typedef _Rb_tree_const_iterator<value_type> const_iterator; | |
d3d526ac | 528 | |
e135a038 | 529 | typedef std::reverse_iterator<iterator> reverse_iterator; |
be26865d | 530 | typedef std::reverse_iterator<const_iterator> const_reverse_iterator; |
d3d526ac BK |
531 | |
532 | private: | |
ed6814f7 | 533 | iterator |
d3d526ac BK |
534 | _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v); |
535 | ||
ed6814f7 | 536 | _Link_type |
b4c70e89 | 537 | _M_copy(_Const_Link_type __x, _Link_type __p); |
d3d526ac | 538 | |
ed6814f7 | 539 | void |
d3d526ac BK |
540 | _M_erase(_Link_type __x); |
541 | ||
542 | public: | |
543 | // allocation/deallocation | |
544 | _Rb_tree() | |
8bd22a3c | 545 | { } |
d3d526ac BK |
546 | |
547 | _Rb_tree(const _Compare& __comp) | |
8bd22a3c BK |
548 | : _M_impl(allocator_type(), __comp) |
549 | { } | |
d3d526ac BK |
550 | |
551 | _Rb_tree(const _Compare& __comp, const allocator_type& __a) | |
8bd22a3c BK |
552 | : _M_impl(__a, __comp) |
553 | { } | |
d3d526ac | 554 | |
11aaf40c | 555 | _Rb_tree(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x) |
8bd22a3c | 556 | : _M_impl(__x.get_allocator(), __x._M_impl._M_key_compare) |
ed6814f7 | 557 | { |
8bd22a3c | 558 | if (__x._M_root() != 0) |
d3d526ac | 559 | { |
b4c70e89 | 560 | _M_root() = _M_copy(__x._M_begin(), _M_end()); |
d3d526ac BK |
561 | _M_leftmost() = _S_minimum(_M_root()); |
562 | _M_rightmost() = _S_maximum(_M_root()); | |
8bd22a3c | 563 | _M_impl._M_node_count = __x._M_impl._M_node_count; |
d3d526ac | 564 | } |
725dc051 | 565 | } |
d3d526ac | 566 | |
737ab798 PC |
567 | ~_Rb_tree() |
568 | { _M_erase(_M_begin()); } | |
d3d526ac | 569 | |
11aaf40c PC |
570 | _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& |
571 | operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x); | |
d3d526ac | 572 | |
d3d526ac | 573 | // Accessors. |
ed6814f7 | 574 | _Compare |
62e67651 | 575 | key_comp() const |
8bd22a3c | 576 | { return _M_impl._M_key_compare; } |
d3d526ac | 577 | |
ed6814f7 | 578 | iterator |
62e67651 | 579 | begin() |
8bd22a3c | 580 | { return static_cast<_Link_type>(this->_M_impl._M_header._M_left); } |
d3d526ac | 581 | |
ed6814f7 | 582 | const_iterator |
62e67651 | 583 | begin() const |
11aaf40c PC |
584 | { |
585 | return static_cast<_Const_Link_type> | |
586 | (this->_M_impl._M_header._M_left); | |
587 | } | |
d3d526ac | 588 | |
ed6814f7 | 589 | iterator |
62e67651 | 590 | end() |
8bd22a3c | 591 | { return static_cast<_Link_type>(&this->_M_impl._M_header); } |
d3d526ac | 592 | |
7f6dd1ca | 593 | const_iterator |
62e67651 | 594 | end() const |
8bd22a3c | 595 | { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); } |
d3d526ac | 596 | |
ed6814f7 | 597 | reverse_iterator |
62e67651 PC |
598 | rbegin() |
599 | { return reverse_iterator(end()); } | |
d3d526ac | 600 | |
ed6814f7 | 601 | const_reverse_iterator |
62e67651 PC |
602 | rbegin() const |
603 | { return const_reverse_iterator(end()); } | |
d3d526ac | 604 | |
ed6814f7 | 605 | reverse_iterator |
62e67651 PC |
606 | rend() |
607 | { return reverse_iterator(begin()); } | |
d3d526ac | 608 | |
ed6814f7 | 609 | const_reverse_iterator |
62e67651 PC |
610 | rend() const |
611 | { return const_reverse_iterator(begin()); } | |
ed6814f7 BI |
612 | |
613 | bool | |
62e67651 | 614 | empty() const |
8bd22a3c | 615 | { return _M_impl._M_node_count == 0; } |
d3d526ac | 616 | |
ed6814f7 | 617 | size_type |
62e67651 | 618 | size() const |
8bd22a3c | 619 | { return _M_impl._M_node_count; } |
d3d526ac | 620 | |
ed6814f7 | 621 | size_type |
62e67651 PC |
622 | max_size() const |
623 | { return size_type(-1); } | |
d3d526ac | 624 | |
ed6814f7 | 625 | void |
11aaf40c | 626 | swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t); |
ed6814f7 | 627 | |
d3d526ac | 628 | // Insert/erase. |
ed6814f7 | 629 | pair<iterator,bool> |
d3d526ac BK |
630 | insert_unique(const value_type& __x); |
631 | ||
ed6814f7 | 632 | iterator |
d3d526ac BK |
633 | insert_equal(const value_type& __x); |
634 | ||
ed6814f7 | 635 | iterator |
d3d526ac BK |
636 | insert_unique(iterator __position, const value_type& __x); |
637 | ||
ed6814f7 | 638 | iterator |
d3d526ac BK |
639 | insert_equal(iterator __position, const value_type& __x); |
640 | ||
641 | template<typename _InputIterator> | |
ed6814f7 | 642 | void |
d3d526ac BK |
643 | insert_unique(_InputIterator __first, _InputIterator __last); |
644 | ||
645 | template<typename _InputIterator> | |
ed6814f7 | 646 | void |
d3d526ac BK |
647 | insert_equal(_InputIterator __first, _InputIterator __last); |
648 | ||
ed6814f7 | 649 | void |
d3d526ac BK |
650 | erase(iterator __position); |
651 | ||
ed6814f7 | 652 | size_type |
d3d526ac BK |
653 | erase(const key_type& __x); |
654 | ||
ed6814f7 | 655 | void |
d3d526ac BK |
656 | erase(iterator __first, iterator __last); |
657 | ||
ed6814f7 | 658 | void |
d3d526ac BK |
659 | erase(const key_type* __first, const key_type* __last); |
660 | ||
e135a038 BK |
661 | void |
662 | clear() | |
d3d526ac | 663 | { |
e135a038 BK |
664 | _M_erase(_M_begin()); |
665 | _M_leftmost() = _M_end(); | |
666 | _M_root() = 0; | |
667 | _M_rightmost() = _M_end(); | |
8bd22a3c | 668 | _M_impl._M_node_count = 0; |
e135a038 | 669 | } |
d3d526ac BK |
670 | |
671 | // Set operations. | |
ed6814f7 | 672 | iterator |
d3d526ac BK |
673 | find(const key_type& __x); |
674 | ||
ed6814f7 | 675 | const_iterator |
d3d526ac BK |
676 | find(const key_type& __x) const; |
677 | ||
ed6814f7 | 678 | size_type |
d3d526ac BK |
679 | count(const key_type& __x) const; |
680 | ||
ed6814f7 | 681 | iterator |
d3d526ac BK |
682 | lower_bound(const key_type& __x); |
683 | ||
ed6814f7 | 684 | const_iterator |
d3d526ac BK |
685 | lower_bound(const key_type& __x) const; |
686 | ||
ed6814f7 | 687 | iterator |
d3d526ac BK |
688 | upper_bound(const key_type& __x); |
689 | ||
ed6814f7 | 690 | const_iterator |
d3d526ac BK |
691 | upper_bound(const key_type& __x) const; |
692 | ||
ed6814f7 | 693 | pair<iterator,iterator> |
d3d526ac BK |
694 | equal_range(const key_type& __x); |
695 | ||
ed6814f7 | 696 | pair<const_iterator, const_iterator> |
d3d526ac BK |
697 | equal_range(const key_type& __x) const; |
698 | ||
699 | // Debugging. | |
ed6814f7 | 700 | bool |
d3d526ac BK |
701 | __rb_verify() const; |
702 | }; | |
703 | ||
ed6814f7 | 704 | template<typename _Key, typename _Val, typename _KeyOfValue, |
d3d526ac | 705 | typename _Compare, typename _Alloc> |
ed6814f7 | 706 | inline bool |
11aaf40c PC |
707 | operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, |
708 | const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) | |
d3d526ac | 709 | { |
62e67651 PC |
710 | return __x.size() == __y.size() |
711 | && equal(__x.begin(), __x.end(), __y.begin()); | |
725dc051 | 712 | } |
d3d526ac | 713 | |
ed6814f7 | 714 | template<typename _Key, typename _Val, typename _KeyOfValue, |
d3d526ac | 715 | typename _Compare, typename _Alloc> |
ed6814f7 | 716 | inline bool |
11aaf40c PC |
717 | operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, |
718 | const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) | |
d3d526ac | 719 | { |
8bd22a3c | 720 | return lexicographical_compare(__x.begin(), __x.end(), |
d3d526ac | 721 | __y.begin(), __y.end()); |
725dc051 | 722 | } |
d3d526ac | 723 | |
ed6814f7 | 724 | template<typename _Key, typename _Val, typename _KeyOfValue, |
d3d526ac | 725 | typename _Compare, typename _Alloc> |
ed6814f7 | 726 | inline bool |
11aaf40c PC |
727 | operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, |
728 | const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) | |
d3d526ac BK |
729 | { return !(__x == __y); } |
730 | ||
ed6814f7 | 731 | template<typename _Key, typename _Val, typename _KeyOfValue, |
d3d526ac | 732 | typename _Compare, typename _Alloc> |
ed6814f7 | 733 | inline bool |
11aaf40c PC |
734 | operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, |
735 | const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) | |
d3d526ac BK |
736 | { return __y < __x; } |
737 | ||
ed6814f7 | 738 | template<typename _Key, typename _Val, typename _KeyOfValue, |
d3d526ac | 739 | typename _Compare, typename _Alloc> |
ed6814f7 | 740 | inline bool |
11aaf40c PC |
741 | operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, |
742 | const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) | |
737ab798 | 743 | { return !(__y < __x); } |
d3d526ac | 744 | |
ed6814f7 | 745 | template<typename _Key, typename _Val, typename _KeyOfValue, |
d3d526ac | 746 | typename _Compare, typename _Alloc> |
ed6814f7 | 747 | inline bool |
11aaf40c PC |
748 | operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, |
749 | const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) | |
737ab798 | 750 | { return !(__x < __y); } |
d3d526ac | 751 | |
ed6814f7 | 752 | template<typename _Key, typename _Val, typename _KeyOfValue, |
d3d526ac | 753 | typename _Compare, typename _Alloc> |
ed6814f7 | 754 | inline void |
11aaf40c PC |
755 | swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, |
756 | _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) | |
d3d526ac BK |
757 | { __x.swap(__y); } |
758 | ||
ed6814f7 | 759 | template<typename _Key, typename _Val, typename _KeyOfValue, |
d3d526ac | 760 | typename _Compare, typename _Alloc> |
11aaf40c PC |
761 | _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& |
762 | _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: | |
763 | operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x) | |
d3d526ac | 764 | { |
ed6814f7 | 765 | if (this != &__x) |
d3d526ac BK |
766 | { |
767 | // Note that _Key may be a constant type. | |
768 | clear(); | |
8bd22a3c | 769 | _M_impl._M_key_compare = __x._M_impl._M_key_compare; |
ed6814f7 | 770 | if (__x._M_root() != 0) |
d3d526ac | 771 | { |
b4c70e89 | 772 | _M_root() = _M_copy(__x._M_begin(), _M_end()); |
d3d526ac BK |
773 | _M_leftmost() = _S_minimum(_M_root()); |
774 | _M_rightmost() = _S_maximum(_M_root()); | |
8bd22a3c | 775 | _M_impl._M_node_count = __x._M_impl._M_node_count; |
d3d526ac BK |
776 | } |
777 | } | |
778 | return *this; | |
725dc051 | 779 | } |
d3d526ac | 780 | |
ed6814f7 | 781 | template<typename _Key, typename _Val, typename _KeyOfValue, |
d3d526ac | 782 | typename _Compare, typename _Alloc> |
11aaf40c PC |
783 | typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator |
784 | _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: | |
e135a038 | 785 | _M_insert(_Base_ptr __x, _Base_ptr __p, const _Val& __v) |
d3d526ac | 786 | { |
e135a038 BK |
787 | _Link_type __z = _M_create_node(__v); |
788 | bool __insert_left; | |
789 | ||
11aaf40c PC |
790 | __insert_left = (__x != 0 || __p == _M_end() |
791 | || _M_impl._M_key_compare(_KeyOfValue()(__v), | |
792 | _S_key(__p))); | |
e135a038 | 793 | |
8bd22a3c BK |
794 | _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, |
795 | this->_M_impl._M_header); | |
796 | ++_M_impl._M_node_count; | |
d3d526ac BK |
797 | return iterator(__z); |
798 | } | |
799 | ||
ed6814f7 | 800 | template<typename _Key, typename _Val, typename _KeyOfValue, |
d3d526ac | 801 | typename _Compare, typename _Alloc> |
11aaf40c PC |
802 | typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator |
803 | _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: | |
d3d526ac BK |
804 | insert_equal(const _Val& __v) |
805 | { | |
b4c70e89 | 806 | _Link_type __x = _M_begin(); |
7f6dd1ca | 807 | _Link_type __y = _M_end(); |
ed6814f7 | 808 | while (__x != 0) |
d3d526ac BK |
809 | { |
810 | __y = __x; | |
8bd22a3c | 811 | __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ? |
62e67651 | 812 | _S_left(__x) : _S_right(__x); |
d3d526ac BK |
813 | } |
814 | return _M_insert(__x, __y, __v); | |
815 | } | |
816 | ||
ed6814f7 | 817 | template<typename _Key, typename _Val, typename _KeyOfValue, |
7f6dd1ca GB |
818 | typename _Compare, typename _Alloc> |
819 | void | |
11aaf40c PC |
820 | _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: |
821 | swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t) | |
7f6dd1ca GB |
822 | { |
823 | if (_M_root() == 0) | |
824 | { | |
825 | if (__t._M_root() != 0) | |
826 | { | |
827 | _M_root() = __t._M_root(); | |
828 | _M_leftmost() = __t._M_leftmost(); | |
829 | _M_rightmost() = __t._M_rightmost(); | |
830 | _M_root()->_M_parent = _M_end(); | |
831 | ||
832 | __t._M_root() = 0; | |
833 | __t._M_leftmost() = __t._M_end(); | |
834 | __t._M_rightmost() = __t._M_end(); | |
835 | } | |
836 | } | |
837 | else if (__t._M_root() == 0) | |
838 | { | |
839 | __t._M_root() = _M_root(); | |
840 | __t._M_leftmost() = _M_leftmost(); | |
841 | __t._M_rightmost() = _M_rightmost(); | |
842 | __t._M_root()->_M_parent = __t._M_end(); | |
843 | ||
844 | _M_root() = 0; | |
845 | _M_leftmost() = _M_end(); | |
846 | _M_rightmost() = _M_end(); | |
847 | } | |
848 | else | |
849 | { | |
850 | std::swap(_M_root(),__t._M_root()); | |
851 | std::swap(_M_leftmost(),__t._M_leftmost()); | |
852 | std::swap(_M_rightmost(),__t._M_rightmost()); | |
853 | ||
854 | _M_root()->_M_parent = _M_end(); | |
855 | __t._M_root()->_M_parent = __t._M_end(); | |
856 | } | |
857 | // No need to swap header's color as it does not change. | |
8bd22a3c BK |
858 | std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count); |
859 | std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare); | |
7f6dd1ca GB |
860 | } |
861 | ||
ed6814f7 | 862 | template<typename _Key, typename _Val, typename _KeyOfValue, |
d3d526ac | 863 | typename _Compare, typename _Alloc> |
11aaf40c PC |
864 | pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, |
865 | _Compare, _Alloc>::iterator, bool> | |
866 | _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: | |
d3d526ac BK |
867 | insert_unique(const _Val& __v) |
868 | { | |
b4c70e89 | 869 | _Link_type __x = _M_begin(); |
7f6dd1ca | 870 | _Link_type __y = _M_end(); |
d3d526ac | 871 | bool __comp = true; |
62e67651 | 872 | while (__x != 0) |
d3d526ac BK |
873 | { |
874 | __y = __x; | |
8bd22a3c | 875 | __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)); |
d3d526ac BK |
876 | __x = __comp ? _S_left(__x) : _S_right(__x); |
877 | } | |
62e67651 | 878 | iterator __j = iterator(__y); |
d3d526ac | 879 | if (__comp) |
62e67651 | 880 | if (__j == begin()) |
d3d526ac BK |
881 | return pair<iterator,bool>(_M_insert(__x, __y, __v), true); |
882 | else | |
883 | --__j; | |
8bd22a3c | 884 | if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v))) |
11aaf40c PC |
885 | return pair<iterator, bool>(_M_insert(__x, __y, __v), true); |
886 | return pair<iterator, bool>(__j, false); | |
d3d526ac | 887 | } |
ed6814f7 BI |
888 | |
889 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
d3d526ac | 890 | typename _Compare, typename _Alloc> |
ed6814f7 | 891 | typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator |
d3d526ac BK |
892 | _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: |
893 | insert_unique(iterator __position, const _Val& __v) | |
894 | { | |
e135a038 | 895 | if (__position._M_node == _M_leftmost()) |
ed6814f7 | 896 | { |
d3d526ac | 897 | // begin() |
62e67651 | 898 | if (size() > 0 |
8bd22a3c BK |
899 | && _M_impl._M_key_compare(_KeyOfValue()(__v), |
900 | _S_key(__position._M_node))) | |
d3d526ac | 901 | return _M_insert(__position._M_node, __position._M_node, __v); |
8bd22a3c | 902 | // First argument just needs to be non-null. |
d3d526ac BK |
903 | else |
904 | return insert_unique(__v).first; | |
ed6814f7 BI |
905 | } |
906 | else if (__position._M_node == _M_end()) | |
907 | { | |
d3d526ac | 908 | // end() |
8bd22a3c BK |
909 | if (_M_impl._M_key_compare(_S_key(_M_rightmost()), |
910 | _KeyOfValue()(__v))) | |
d3d526ac BK |
911 | return _M_insert(0, _M_rightmost(), __v); |
912 | else | |
913 | return insert_unique(__v).first; | |
ed6814f7 BI |
914 | } |
915 | else | |
d3d526ac BK |
916 | { |
917 | iterator __before = __position; | |
918 | --__before; | |
8bd22a3c BK |
919 | if (_M_impl._M_key_compare(_S_key(__before._M_node), |
920 | _KeyOfValue()(__v)) | |
921 | && _M_impl._M_key_compare(_KeyOfValue()(__v), | |
922 | _S_key(__position._M_node))) | |
d3d526ac BK |
923 | { |
924 | if (_S_right(__before._M_node) == 0) | |
ed6814f7 | 925 | return _M_insert(0, __before._M_node, __v); |
d3d526ac BK |
926 | else |
927 | return _M_insert(__position._M_node, __position._M_node, __v); | |
8bd22a3c | 928 | // First argument just needs to be non-null. |
ed6814f7 | 929 | } |
d3d526ac BK |
930 | else |
931 | return insert_unique(__v).first; | |
932 | } | |
725dc051 | 933 | } |
d3d526ac | 934 | |
ed6814f7 | 935 | template<typename _Key, typename _Val, typename _KeyOfValue, |
d3d526ac | 936 | typename _Compare, typename _Alloc> |
11aaf40c PC |
937 | typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator |
938 | _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: | |
d3d526ac BK |
939 | insert_equal(iterator __position, const _Val& __v) |
940 | { | |
e135a038 | 941 | if (__position._M_node == _M_leftmost()) |
ed6814f7 | 942 | { |
d3d526ac | 943 | // begin() |
62e67651 | 944 | if (size() > 0 |
8bd22a3c BK |
945 | && !_M_impl._M_key_compare(_S_key(__position._M_node), |
946 | _KeyOfValue()(__v))) | |
d3d526ac | 947 | return _M_insert(__position._M_node, __position._M_node, __v); |
ed6814f7 | 948 | // first argument just needs to be non-null |
d3d526ac BK |
949 | else |
950 | return insert_equal(__v); | |
ed6814f7 BI |
951 | } |
952 | else if (__position._M_node == _M_end()) | |
d3d526ac BK |
953 | { |
954 | // end() | |
8bd22a3c BK |
955 | if (!_M_impl._M_key_compare(_KeyOfValue()(__v), |
956 | _S_key(_M_rightmost()))) | |
d3d526ac BK |
957 | return _M_insert(0, _M_rightmost(), __v); |
958 | else | |
959 | return insert_equal(__v); | |
ed6814f7 BI |
960 | } |
961 | else | |
d3d526ac BK |
962 | { |
963 | iterator __before = __position; | |
964 | --__before; | |
8bd22a3c BK |
965 | if (!_M_impl._M_key_compare(_KeyOfValue()(__v), |
966 | _S_key(__before._M_node)) | |
967 | && !_M_impl._M_key_compare(_S_key(__position._M_node), | |
968 | _KeyOfValue()(__v))) | |
d3d526ac BK |
969 | { |
970 | if (_S_right(__before._M_node) == 0) | |
ed6814f7 | 971 | return _M_insert(0, __before._M_node, __v); |
d3d526ac BK |
972 | else |
973 | return _M_insert(__position._M_node, __position._M_node, __v); | |
8bd22a3c | 974 | // First argument just needs to be non-null. |
ed6814f7 | 975 | } |
d3d526ac BK |
976 | else |
977 | return insert_equal(__v); | |
978 | } | |
979 | } | |
980 | ||
ed6814f7 | 981 | template<typename _Key, typename _Val, typename _KoV, |
d3d526ac BK |
982 | typename _Cmp, typename _Alloc> |
983 | template<class _II> | |
ed6814f7 | 984 | void |
11aaf40c | 985 | _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>:: |
d3d526ac | 986 | insert_equal(_II __first, _II __last) |
322821b9 | 987 | { |
11aaf40c | 988 | for (; __first != __last; ++__first) |
d3d526ac | 989 | insert_equal(*__first); |
322821b9 | 990 | } |
725dc051 | 991 | |
ed6814f7 BI |
992 | template<typename _Key, typename _Val, typename _KoV, |
993 | typename _Cmp, typename _Alloc> | |
d3d526ac | 994 | template<class _II> |
ed6814f7 | 995 | void |
11aaf40c | 996 | _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>:: |
ed6814f7 | 997 | insert_unique(_II __first, _II __last) |
d3d526ac | 998 | { |
11aaf40c | 999 | for (; __first != __last; ++__first) |
d3d526ac BK |
1000 | insert_unique(*__first); |
1001 | } | |
725dc051 | 1002 | |
ed6814f7 | 1003 | template<typename _Key, typename _Val, typename _KeyOfValue, |
d3d526ac | 1004 | typename _Compare, typename _Alloc> |
ed6814f7 | 1005 | inline void |
11aaf40c PC |
1006 | _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: |
1007 | erase(iterator __position) | |
d3d526ac | 1008 | { |
11aaf40c PC |
1009 | _Link_type __y = |
1010 | static_cast<_Link_type>(_Rb_tree_rebalance_for_erase | |
1011 | (__position._M_node, | |
1012 | this->_M_impl._M_header)); | |
d3d526ac | 1013 | destroy_node(__y); |
8bd22a3c | 1014 | --_M_impl._M_node_count; |
d3d526ac | 1015 | } |
725dc051 | 1016 | |
ed6814f7 | 1017 | template<typename _Key, typename _Val, typename _KeyOfValue, |
d3d526ac | 1018 | typename _Compare, typename _Alloc> |
11aaf40c PC |
1019 | typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type |
1020 | _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: | |
1021 | erase(const _Key& __x) | |
d3d526ac BK |
1022 | { |
1023 | pair<iterator,iterator> __p = equal_range(__x); | |
4977bab6 | 1024 | size_type __n = std::distance(__p.first, __p.second); |
d3d526ac BK |
1025 | erase(__p.first, __p.second); |
1026 | return __n; | |
725dc051 | 1027 | } |
725dc051 | 1028 | |
ed6814f7 | 1029 | template<typename _Key, typename _Val, typename _KoV, |
d3d526ac | 1030 | typename _Compare, typename _Alloc> |
ed6814f7 | 1031 | typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type |
11aaf40c | 1032 | _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>:: |
b4c70e89 | 1033 | _M_copy(_Const_Link_type __x, _Link_type __p) |
d3d526ac BK |
1034 | { |
1035 | // Structural copy. __x and __p must be non-null. | |
1036 | _Link_type __top = _M_clone_node(__x); | |
1037 | __top->_M_parent = __p; | |
ed6814f7 BI |
1038 | |
1039 | try | |
d3d526ac BK |
1040 | { |
1041 | if (__x->_M_right) | |
1042 | __top->_M_right = _M_copy(_S_right(__x), __top); | |
1043 | __p = __top; | |
1044 | __x = _S_left(__x); | |
ed6814f7 BI |
1045 | |
1046 | while (__x != 0) | |
d3d526ac BK |
1047 | { |
1048 | _Link_type __y = _M_clone_node(__x); | |
1049 | __p->_M_left = __y; | |
1050 | __y->_M_parent = __p; | |
1051 | if (__x->_M_right) | |
1052 | __y->_M_right = _M_copy(_S_right(__x), __y); | |
1053 | __p = __y; | |
1054 | __x = _S_left(__x); | |
1055 | } | |
1056 | } | |
1057 | catch(...) | |
1058 | { | |
1059 | _M_erase(__top); | |
ed6814f7 | 1060 | __throw_exception_again; |
d3d526ac BK |
1061 | } |
1062 | return __top; | |
725dc051 | 1063 | } |
d3d526ac | 1064 | |
ed6814f7 | 1065 | template<typename _Key, typename _Val, typename _KeyOfValue, |
d3d526ac | 1066 | typename _Compare, typename _Alloc> |
ed6814f7 | 1067 | void |
11aaf40c PC |
1068 | _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: |
1069 | _M_erase(_Link_type __x) | |
d3d526ac BK |
1070 | { |
1071 | // Erase without rebalancing. | |
ed6814f7 | 1072 | while (__x != 0) |
d3d526ac BK |
1073 | { |
1074 | _M_erase(_S_right(__x)); | |
1075 | _Link_type __y = _S_left(__x); | |
1076 | destroy_node(__x); | |
1077 | __x = __y; | |
1078 | } | |
725dc051 | 1079 | } |
d3d526ac | 1080 | |
ed6814f7 | 1081 | template<typename _Key, typename _Val, typename _KeyOfValue, |
d3d526ac | 1082 | typename _Compare, typename _Alloc> |
ed6814f7 | 1083 | void |
11aaf40c | 1084 | _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: |
d3d526ac BK |
1085 | erase(iterator __first, iterator __last) |
1086 | { | |
1087 | if (__first == begin() && __last == end()) | |
1088 | clear(); | |
1089 | else | |
4681bebd PC |
1090 | for (; __first != __last; ++__first) |
1091 | erase(__first); | |
725dc051 | 1092 | } |
d3d526ac | 1093 | |
ed6814f7 | 1094 | template<typename _Key, typename _Val, typename _KeyOfValue, |
d3d526ac | 1095 | typename _Compare, typename _Alloc> |
ed6814f7 | 1096 | void |
11aaf40c | 1097 | _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: |
ed6814f7 BI |
1098 | erase(const _Key* __first, const _Key* __last) |
1099 | { | |
1100 | while (__first != __last) | |
1101 | erase(*__first++); | |
725dc051 | 1102 | } |
d3d526ac | 1103 | |
ed6814f7 | 1104 | template<typename _Key, typename _Val, typename _KeyOfValue, |
d3d526ac | 1105 | typename _Compare, typename _Alloc> |
11aaf40c PC |
1106 | typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator |
1107 | _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: | |
1108 | find(const _Key& __k) | |
d3d526ac | 1109 | { |
b4c70e89 GB |
1110 | _Link_type __x = _M_begin(); // Current node. |
1111 | _Link_type __y = _M_end(); // Last node which is not less than __k. | |
ed6814f7 BI |
1112 | |
1113 | while (__x != 0) | |
8bd22a3c | 1114 | if (!_M_impl._M_key_compare(_S_key(__x), __k)) |
d3d526ac BK |
1115 | __y = __x, __x = _S_left(__x); |
1116 | else | |
1117 | __x = _S_right(__x); | |
ed6814f7 BI |
1118 | |
1119 | iterator __j = iterator(__y); | |
11aaf40c PC |
1120 | return (__j == end() |
1121 | || _M_impl._M_key_compare(__k, | |
1122 | _S_key(__j._M_node))) ? end() : __j; | |
d3d526ac | 1123 | } |
ed6814f7 BI |
1124 | |
1125 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
d3d526ac | 1126 | typename _Compare, typename _Alloc> |
11aaf40c PC |
1127 | typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator |
1128 | _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: | |
d3d526ac BK |
1129 | find(const _Key& __k) const |
1130 | { | |
b4c70e89 GB |
1131 | _Const_Link_type __x = _M_begin(); // Current node. |
1132 | _Const_Link_type __y = _M_end(); // Last node which is not less than __k. | |
ed6814f7 BI |
1133 | |
1134 | while (__x != 0) | |
d3d526ac | 1135 | { |
8bd22a3c | 1136 | if (!_M_impl._M_key_compare(_S_key(__x), __k)) |
d3d526ac BK |
1137 | __y = __x, __x = _S_left(__x); |
1138 | else | |
1139 | __x = _S_right(__x); | |
ed6814f7 BI |
1140 | } |
1141 | const_iterator __j = const_iterator(__y); | |
11aaf40c PC |
1142 | return (__j == end() |
1143 | || _M_impl._M_key_compare(__k, | |
1144 | _S_key(__j._M_node))) ? end() : __j; | |
725dc051 | 1145 | } |
d3d526ac | 1146 | |
ed6814f7 | 1147 | template<typename _Key, typename _Val, typename _KeyOfValue, |
d3d526ac | 1148 | typename _Compare, typename _Alloc> |
11aaf40c PC |
1149 | typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type |
1150 | _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: | |
d3d526ac | 1151 | count(const _Key& __k) const |
322821b9 | 1152 | { |
d3d526ac | 1153 | pair<const_iterator, const_iterator> __p = equal_range(__k); |
62e67651 | 1154 | const size_type __n = std::distance(__p.first, __p.second); |
d3d526ac | 1155 | return __n; |
322821b9 | 1156 | } |
d3d526ac | 1157 | |
ed6814f7 | 1158 | template<typename _Key, typename _Val, typename _KeyOfValue, |
d3d526ac | 1159 | typename _Compare, typename _Alloc> |
11aaf40c PC |
1160 | typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator |
1161 | _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: | |
d3d526ac BK |
1162 | lower_bound(const _Key& __k) |
1163 | { | |
b4c70e89 GB |
1164 | _Link_type __x = _M_begin(); // Current node. |
1165 | _Link_type __y = _M_end(); // Last node which is not less than __k. | |
ed6814f7 BI |
1166 | |
1167 | while (__x != 0) | |
8bd22a3c | 1168 | if (!_M_impl._M_key_compare(_S_key(__x), __k)) |
d3d526ac BK |
1169 | __y = __x, __x = _S_left(__x); |
1170 | else | |
1171 | __x = _S_right(__x); | |
ed6814f7 | 1172 | |
d3d526ac BK |
1173 | return iterator(__y); |
1174 | } | |
1175 | ||
ed6814f7 | 1176 | template<typename _Key, typename _Val, typename _KeyOfValue, |
d3d526ac | 1177 | typename _Compare, typename _Alloc> |
11aaf40c PC |
1178 | typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator |
1179 | _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: | |
d3d526ac BK |
1180 | lower_bound(const _Key& __k) const |
1181 | { | |
b4c70e89 GB |
1182 | _Const_Link_type __x = _M_begin(); // Current node. |
1183 | _Const_Link_type __y = _M_end(); // Last node which is not less than __k. | |
ed6814f7 BI |
1184 | |
1185 | while (__x != 0) | |
8bd22a3c | 1186 | if (!_M_impl._M_key_compare(_S_key(__x), __k)) |
d3d526ac BK |
1187 | __y = __x, __x = _S_left(__x); |
1188 | else | |
1189 | __x = _S_right(__x); | |
ed6814f7 | 1190 | |
d3d526ac BK |
1191 | return const_iterator(__y); |
1192 | } | |
1193 | ||
ed6814f7 | 1194 | template<typename _Key, typename _Val, typename _KeyOfValue, |
d3d526ac | 1195 | typename _Compare, typename _Alloc> |
11aaf40c PC |
1196 | typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator |
1197 | _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: | |
d3d526ac BK |
1198 | upper_bound(const _Key& __k) |
1199 | { | |
b4c70e89 | 1200 | _Link_type __x = _M_begin(); // Current node. |
7f6dd1ca | 1201 | _Link_type __y = _M_end(); // Last node which is greater than __k. |
ed6814f7 BI |
1202 | |
1203 | while (__x != 0) | |
8bd22a3c | 1204 | if (_M_impl._M_key_compare(__k, _S_key(__x))) |
d3d526ac BK |
1205 | __y = __x, __x = _S_left(__x); |
1206 | else | |
1207 | __x = _S_right(__x); | |
ed6814f7 | 1208 | |
d3d526ac BK |
1209 | return iterator(__y); |
1210 | } | |
1211 | ||
ed6814f7 | 1212 | template<typename _Key, typename _Val, typename _KeyOfValue, |
d3d526ac | 1213 | typename _Compare, typename _Alloc> |
11aaf40c PC |
1214 | typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator |
1215 | _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: | |
d3d526ac BK |
1216 | upper_bound(const _Key& __k) const |
1217 | { | |
b4c70e89 GB |
1218 | _Const_Link_type __x = _M_begin(); // Current node. |
1219 | _Const_Link_type __y = _M_end(); // Last node which is greater than __k. | |
ed6814f7 BI |
1220 | |
1221 | while (__x != 0) | |
8bd22a3c | 1222 | if (_M_impl._M_key_compare(__k, _S_key(__x))) |
d3d526ac BK |
1223 | __y = __x, __x = _S_left(__x); |
1224 | else | |
1225 | __x = _S_right(__x); | |
ed6814f7 | 1226 | |
d3d526ac BK |
1227 | return const_iterator(__y); |
1228 | } | |
1229 | ||
ed6814f7 | 1230 | template<typename _Key, typename _Val, typename _KeyOfValue, |
d3d526ac | 1231 | typename _Compare, typename _Alloc> |
ed6814f7 | 1232 | inline |
11aaf40c PC |
1233 | pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, |
1234 | _Compare, _Alloc>::iterator, | |
1235 | typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator> | |
1236 | _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: | |
d3d526ac BK |
1237 | equal_range(const _Key& __k) |
1238 | { return pair<iterator, iterator>(lower_bound(__k), upper_bound(__k)); } | |
1239 | ||
ed6814f7 | 1240 | template<typename _Key, typename _Val, typename _KoV, |
d3d526ac | 1241 | typename _Compare, typename _Alloc> |
ed6814f7 | 1242 | inline |
737ab798 PC |
1243 | pair<typename _Rb_tree<_Key, _Val, _KoV, |
1244 | _Compare, _Alloc>::const_iterator, | |
1245 | typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::const_iterator> | |
1246 | _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>:: | |
1247 | equal_range(const _Key& __k) const | |
1248 | { return pair<const_iterator, const_iterator>(lower_bound(__k), | |
1249 | upper_bound(__k)); } | |
d3d526ac | 1250 | |
b4c70e89 GB |
1251 | unsigned int |
1252 | _Rb_tree_black_count(const _Rb_tree_node_base* __node, | |
1253 | const _Rb_tree_node_base* __root); | |
d3d526ac | 1254 | |
ed6814f7 | 1255 | template<typename _Key, typename _Val, typename _KeyOfValue, |
d3d526ac | 1256 | typename _Compare, typename _Alloc> |
ed6814f7 | 1257 | bool |
d3d526ac BK |
1258 | _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const |
1259 | { | |
8bd22a3c BK |
1260 | if (_M_impl._M_node_count == 0 || begin() == end()) |
1261 | return _M_impl._M_node_count == 0 && begin() == end() | |
1262 | && this->_M_impl._M_header._M_left == _M_end() | |
1263 | && this->_M_impl._M_header._M_right == _M_end(); | |
ed6814f7 | 1264 | |
737ab798 | 1265 | unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root()); |
ed6814f7 | 1266 | for (const_iterator __it = begin(); __it != end(); ++__it) |
737ab798 PC |
1267 | { |
1268 | _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node); | |
1269 | _Const_Link_type __L = _S_left(__x); | |
1270 | _Const_Link_type __R = _S_right(__x); | |
ed6814f7 | 1271 | |
737ab798 | 1272 | if (__x->_M_color == _S_red) |
ed6814f7 | 1273 | if ((__L && __L->_M_color == _S_red) |
737ab798 PC |
1274 | || (__R && __R->_M_color == _S_red)) |
1275 | return false; | |
ed6814f7 | 1276 | |
8bd22a3c | 1277 | if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L))) |
737ab798 | 1278 | return false; |
8bd22a3c | 1279 | if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x))) |
737ab798 | 1280 | return false; |
ed6814f7 | 1281 | |
737ab798 PC |
1282 | if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len) |
1283 | return false; | |
1284 | } | |
ed6814f7 | 1285 | |
737ab798 PC |
1286 | if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root())) |
1287 | return false; | |
1288 | if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root())) | |
1289 | return false; | |
1290 | return true; | |
d3d526ac | 1291 | } |
ed6814f7 | 1292 | } // namespace std |
725dc051 | 1293 | |
ed6814f7 | 1294 | #endif |