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