projects / gcc.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
history | raw | HEAD
c++config: Add in revised namespace associations.
[gcc.git] / libstdc++-v3 / include / bits / stl_tree.h
1 // RB tree implementation -*- C++ -*-
2
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
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, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
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
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
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.
61 */
62
63 #ifndef _TREE_H
64 #define _TREE_H 1
65
66 #include <bits/stl_algobase.h>
67 #include <bits/allocator.h>
68 #include <bits/stl_construct.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 _S_minimum(_Base_ptr __x)
104 {
105 while (__x->_M_left != 0) __x = __x->_M_left;
106 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 _S_maximum(_Base_ptr __x)
118 {
119 while (__x->_M_right != 0) __x = __x->_M_right;
120 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 _Rb_tree_iterator(_Link_type __x)
169 : _M_node(__x) { }
170
171 reference
172 operator*() const
173 { return static_cast<_Link_type>(_M_node)->_M_value_field; }
174
175 pointer
176 operator->() const
177 { 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 operator++(int)
188 {
189 _Self __tmp = *this;
190 _M_node = _Rb_tree_increment(_M_node);
191 return __tmp;
192 }
193
194 _Self&
195 operator--()
196 {
197 _M_node = _Rb_tree_decrement(_M_node);
198 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 operator==(const _Self& __x) const
211 { return _M_node == __x._M_node; }
212
213 bool
214 operator!=(const _Self& __x) const
215 { 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 _Rb_tree_const_iterator(_Link_type __x)
241 : _M_node(__x) { }
242
243 _Rb_tree_const_iterator(const iterator& __it)
244 : _M_node(__it._M_node) { }
245
246 reference
247 operator*() const
248 { return static_cast<_Link_type>(_M_node)->_M_value_field; }
249
250 pointer
251 operator->() const
252 { return &static_cast<_Link_type>(_M_node)->_M_value_field; }
253
254 _Self&
255 operator++()
256 {
257 _M_node = _Rb_tree_increment(_M_node);
258 return *this;
259 }
260
261 _Self
262 operator++(int)
263 {
264 _Self __tmp = *this;
265 _M_node = _Rb_tree_increment(_M_node);
266 return __tmp;
267 }
268
269 _Self&
270 operator--()
271 {
272 _M_node = _Rb_tree_decrement(_M_node);
273 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 operator==(const _Self& __x) const
286 { return _M_node == __x._M_node; }
287
288 bool
289 operator!=(const _Self& __x) const
290 { 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_rotate_left(_Rb_tree_node_base* const __x,
309 _Rb_tree_node_base*& __root);
310
311 void
312 _Rb_tree_rotate_right(_Rb_tree_node_base* const __x,
313 _Rb_tree_node_base*& __root);
314
315 void
316 _Rb_tree_insert_and_rebalance(const bool __insert_left,
317 _Rb_tree_node_base* __x,
318 _Rb_tree_node_base* __p,
319 _Rb_tree_node_base& __header);
320
321 _Rb_tree_node_base*
322 _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
323 _Rb_tree_node_base& __header);
324
325
326 template<typename _Key, typename _Val, typename _KeyOfValue,
327 typename _Compare, typename _Alloc = allocator<_Val> >
328 class _Rb_tree
329 {
330 typedef typename _Alloc::template rebind<_Rb_tree_node<_Val> >::other
331 _Node_allocator;
332
333 protected:
334 typedef _Rb_tree_node_base* _Base_ptr;
335 typedef const _Rb_tree_node_base* _Const_Base_ptr;
336 typedef _Rb_tree_node<_Val> _Rb_tree_node;
337
338 public:
339 typedef _Key key_type;
340 typedef _Val value_type;
341 typedef value_type* pointer;
342 typedef const value_type* const_pointer;
343 typedef value_type& reference;
344 typedef const value_type& const_reference;
345 typedef _Rb_tree_node* _Link_type;
346 typedef const _Rb_tree_node* _Const_Link_type;
347 typedef size_t size_type;
348 typedef ptrdiff_t difference_type;
349 typedef _Alloc allocator_type;
350
351 allocator_type
352 get_allocator() const
353 { return *static_cast<const _Node_allocator*>(&this->_M_impl); }
354
355 protected:
356 _Rb_tree_node*
357 _M_get_node()
358 { return _M_impl._Node_allocator::allocate(1); }
359
360 void
361 _M_put_node(_Rb_tree_node* __p)
362 { _M_impl._Node_allocator::deallocate(__p, 1); }
363
364 _Link_type
365 _M_create_node(const value_type& __x)
366 {
367 _Link_type __tmp = _M_get_node();
368 try
369 { get_allocator().construct(&__tmp->_M_value_field, __x); }
370 catch(...)
371 {
372 _M_put_node(__tmp);
373 __throw_exception_again;
374 }
375 return __tmp;
376 }
377
378 _Link_type
379 _M_clone_node(_Const_Link_type __x)
380 {
381 _Link_type __tmp = _M_create_node(__x->_M_value_field);
382 __tmp->_M_color = __x->_M_color;
383 __tmp->_M_left = 0;
384 __tmp->_M_right = 0;
385 return __tmp;
386 }
387
388 void
389 destroy_node(_Link_type __p)
390 {
391 get_allocator().destroy(&__p->_M_value_field);
392 _M_put_node(__p);
393 }
394
395 protected:
396 template<typename _Key_compare,
397 bool _Is_pod_comparator = std::__is_pod<_Key_compare>::__value>
398 struct _Rb_tree_impl : public _Node_allocator
399 {
400 _Key_compare _M_key_compare;
401 _Rb_tree_node_base _M_header;
402 size_type _M_node_count; // Keeps track of size of tree.
403
404 _Rb_tree_impl(const _Node_allocator& __a = _Node_allocator(),
405 const _Key_compare& __comp = _Key_compare())
406 : _Node_allocator(__a), _M_key_compare(__comp), _M_header(),
407 _M_node_count(0)
408 {
409 this->_M_header._M_color = _S_red;
410 this->_M_header._M_parent = 0;
411 this->_M_header._M_left = &this->_M_header;
412 this->_M_header._M_right = &this->_M_header;
413 }
414 };
415
416 // Specialization for _Comparison types that are not capable of
417 // being base classes / super classes.
418 template<typename _Key_compare>
419 struct _Rb_tree_impl<_Key_compare, true> : public _Node_allocator
420 {
421 _Key_compare _M_key_compare;
422 _Rb_tree_node_base _M_header;
423 size_type _M_node_count; // Keeps track of size of tree.
424
425 _Rb_tree_impl(const _Node_allocator& __a = _Node_allocator(),
426 const _Key_compare& __comp = _Key_compare())
427 : _Node_allocator(__a), _M_key_compare(__comp), _M_header(),
428 _M_node_count(0)
429 {
430 this->_M_header._M_color = _S_red;
431 this->_M_header._M_parent = 0;
432 this->_M_header._M_left = &this->_M_header;
433 this->_M_header._M_right = &this->_M_header;
434 }
435 };
436
437 _Rb_tree_impl<_Compare> _M_impl;
438
439 protected:
440 _Base_ptr&
441 _M_root()
442 { return this->_M_impl._M_header._M_parent; }
443
444 _Const_Base_ptr
445 _M_root() const
446 { return this->_M_impl._M_header._M_parent; }
447
448 _Base_ptr&
449 _M_leftmost()
450 { return this->_M_impl._M_header._M_left; }
451
452 _Const_Base_ptr
453 _M_leftmost() const
454 { return this->_M_impl._M_header._M_left; }
455
456 _Base_ptr&
457 _M_rightmost()
458 { return this->_M_impl._M_header._M_right; }
459
460 _Const_Base_ptr
461 _M_rightmost() const
462 { return this->_M_impl._M_header._M_right; }
463
464 _Link_type
465 _M_begin()
466 { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
467
468 _Const_Link_type
469 _M_begin() const
470 {
471 return static_cast<_Const_Link_type>
472 (this->_M_impl._M_header._M_parent);
473 }
474
475 _Link_type
476 _M_end()
477 { return static_cast<_Link_type>(&this->_M_impl._M_header); }
478
479 _Const_Link_type
480 _M_end() const
481 { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); }
482
483 static const_reference
484 _S_value(_Const_Link_type __x)
485 { return __x->_M_value_field; }
486
487 static const _Key&
488 _S_key(_Const_Link_type __x)
489 { return _KeyOfValue()(_S_value(__x)); }
490
491 static _Link_type
492 _S_left(_Base_ptr __x)
493 { return static_cast<_Link_type>(__x->_M_left); }
494
495 static _Const_Link_type
496 _S_left(_Const_Base_ptr __x)
497 { return static_cast<_Const_Link_type>(__x->_M_left); }
498
499 static _Link_type
500 _S_right(_Base_ptr __x)
501 { return static_cast<_Link_type>(__x->_M_right); }
502
503 static _Const_Link_type
504 _S_right(_Const_Base_ptr __x)
505 { return static_cast<_Const_Link_type>(__x->_M_right); }
506
507 static const_reference
508 _S_value(_Const_Base_ptr __x)
509 { return static_cast<_Const_Link_type>(__x)->_M_value_field; }
510
511 static const _Key&
512 _S_key(_Const_Base_ptr __x)
513 { return _KeyOfValue()(_S_value(__x)); }
514
515 static _Base_ptr
516 _S_minimum(_Base_ptr __x)
517 { return _Rb_tree_node_base::_S_minimum(__x); }
518
519 static _Const_Base_ptr
520 _S_minimum(_Const_Base_ptr __x)
521 { return _Rb_tree_node_base::_S_minimum(__x); }
522
523 static _Base_ptr
524 _S_maximum(_Base_ptr __x)
525 { return _Rb_tree_node_base::_S_maximum(__x); }
526
527 static _Const_Base_ptr
528 _S_maximum(_Const_Base_ptr __x)
529 { return _Rb_tree_node_base::_S_maximum(__x); }
530
531 public:
532 typedef _Rb_tree_iterator<value_type> iterator;
533 typedef _Rb_tree_const_iterator<value_type> const_iterator;
534
535 typedef std::reverse_iterator<iterator> reverse_iterator;
536 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
537
538 private:
539 iterator
540 _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v);
541
542 const_iterator
543 _M_insert(_Const_Base_ptr __x, _Const_Base_ptr __y,
544 const value_type& __v);
545
546 _Link_type
547 _M_copy(_Const_Link_type __x, _Link_type __p);
548
549 void
550 _M_erase(_Link_type __x);
551
552 public:
553 // allocation/deallocation
554 _Rb_tree()
555 { }
556
557 _Rb_tree(const _Compare& __comp)
558 : _M_impl(allocator_type(), __comp)
559 { }
560
561 _Rb_tree(const _Compare& __comp, const allocator_type& __a)
562 : _M_impl(__a, __comp)
563 { }
564
565 _Rb_tree(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x)
566 : _M_impl(__x.get_allocator(), __x._M_impl._M_key_compare)
567 {
568 if (__x._M_root() != 0)
569 {
570 _M_root() = _M_copy(__x._M_begin(), _M_end());
571 _M_leftmost() = _S_minimum(_M_root());
572 _M_rightmost() = _S_maximum(_M_root());
573 _M_impl._M_node_count = __x._M_impl._M_node_count;
574 }
575 }
576
577 ~_Rb_tree()
578 { _M_erase(_M_begin()); }
579
580 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
581 operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x);
582
583 // Accessors.
584 _Compare
585 key_comp() const
586 { return _M_impl._M_key_compare; }
587
588 iterator
589 begin()
590 {
591 return iterator(static_cast<_Link_type>
592 (this->_M_impl._M_header._M_left));
593 }
594
595 const_iterator
596 begin() const
597 {
598 return const_iterator(static_cast<_Const_Link_type>
599 (this->_M_impl._M_header._M_left));
600 }
601
602 iterator
603 end()
604 { return iterator(static_cast<_Link_type>(&this->_M_impl._M_header)); }
605
606 const_iterator
607 end() const
608 {
609 return const_iterator(static_cast<_Const_Link_type>
610 (&this->_M_impl._M_header));
611 }
612
613 reverse_iterator
614 rbegin()
615 { return reverse_iterator(end()); }
616
617 const_reverse_iterator
618 rbegin() const
619 { return const_reverse_iterator(end()); }
620
621 reverse_iterator
622 rend()
623 { return reverse_iterator(begin()); }
624
625 const_reverse_iterator
626 rend() const
627 { return const_reverse_iterator(begin()); }
628
629 bool
630 empty() const
631 { return _M_impl._M_node_count == 0; }
632
633 size_type
634 size() const
635 { return _M_impl._M_node_count; }
636
637 size_type
638 max_size() const
639 { return size_type(-1); }
640
641 void
642 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t);
643
644 // Insert/erase.
645 pair<iterator,bool>
646 insert_unique(const value_type& __x);
647
648 iterator
649 insert_equal(const value_type& __x);
650
651 iterator
652 insert_unique(iterator __position, const value_type& __x);
653
654 const_iterator
655 insert_unique(const_iterator __position, const value_type& __x);
656
657 iterator
658 insert_equal(iterator __position, const value_type& __x);
659
660 const_iterator
661 insert_equal(const_iterator __position, const value_type& __x);
662
663 template<typename _InputIterator>
664 void
665 insert_unique(_InputIterator __first, _InputIterator __last);
666
667 template<typename _InputIterator>
668 void
669 insert_equal(_InputIterator __first, _InputIterator __last);
670
671 void
672 erase(iterator __position);
673
674 void
675 erase(const_iterator __position);
676
677 size_type
678 erase(const key_type& __x);
679
680 void
681 erase(iterator __first, iterator __last);
682
683 void
684 erase(const_iterator __first, const_iterator __last);
685
686 void
687 erase(const key_type* __first, const key_type* __last);
688
689 void
690 clear()
691 {
692 _M_erase(_M_begin());
693 _M_leftmost() = _M_end();
694 _M_root() = 0;
695 _M_rightmost() = _M_end();
696 _M_impl._M_node_count = 0;
697 }
698
699 // Set operations.
700 iterator
701 find(const key_type& __x);
702
703 const_iterator
704 find(const key_type& __x) const;
705
706 size_type
707 count(const key_type& __x) const;
708
709 iterator
710 lower_bound(const key_type& __x);
711
712 const_iterator
713 lower_bound(const key_type& __x) const;
714
715 iterator
716 upper_bound(const key_type& __x);
717
718 const_iterator
719 upper_bound(const key_type& __x) const;
720
721 pair<iterator,iterator>
722 equal_range(const key_type& __x);
723
724 pair<const_iterator, const_iterator>
725 equal_range(const key_type& __x) const;
726
727 // Debugging.
728 bool
729 __rb_verify() const;
730 };
731
732 template<typename _Key, typename _Val, typename _KeyOfValue,
733 typename _Compare, typename _Alloc>
734 inline bool
735 operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
736 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
737 {
738 return __x.size() == __y.size()
739 && std::equal(__x.begin(), __x.end(), __y.begin());
740 }
741
742 template<typename _Key, typename _Val, typename _KeyOfValue,
743 typename _Compare, typename _Alloc>
744 inline bool
745 operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
746 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
747 {
748 return std::lexicographical_compare(__x.begin(), __x.end(),
749 __y.begin(), __y.end());
750 }
751
752 template<typename _Key, typename _Val, typename _KeyOfValue,
753 typename _Compare, typename _Alloc>
754 inline bool
755 operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
756 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
757 { return !(__x == __y); }
758
759 template<typename _Key, typename _Val, typename _KeyOfValue,
760 typename _Compare, typename _Alloc>
761 inline bool
762 operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
763 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
764 { return __y < __x; }
765
766 template<typename _Key, typename _Val, typename _KeyOfValue,
767 typename _Compare, typename _Alloc>
768 inline bool
769 operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
770 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
771 { return !(__y < __x); }
772
773 template<typename _Key, typename _Val, typename _KeyOfValue,
774 typename _Compare, typename _Alloc>
775 inline bool
776 operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
777 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
778 { return !(__x < __y); }
779
780 template<typename _Key, typename _Val, typename _KeyOfValue,
781 typename _Compare, typename _Alloc>
782 inline void
783 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
784 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
785 { __x.swap(__y); }
786
787 template<typename _Key, typename _Val, typename _KeyOfValue,
788 typename _Compare, typename _Alloc>
789 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
790 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
791 operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x)
792 {
793 if (this != &__x)
794 {
795 // Note that _Key may be a constant type.
796 clear();
797 _M_impl._M_key_compare = __x._M_impl._M_key_compare;
798 if (__x._M_root() != 0)
799 {
800 _M_root() = _M_copy(__x._M_begin(), _M_end());
801 _M_leftmost() = _S_minimum(_M_root());
802 _M_rightmost() = _S_maximum(_M_root());
803 _M_impl._M_node_count = __x._M_impl._M_node_count;
804 }
805 }
806 return *this;
807 }
808
809 template<typename _Key, typename _Val, typename _KeyOfValue,
810 typename _Compare, typename _Alloc>
811 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
812 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
813 _M_insert(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
814 {
815 bool __insert_left = (__x != 0 || __p == _M_end()
816 || _M_impl._M_key_compare(_KeyOfValue()(__v),
817 _S_key(__p)));
818
819 _Link_type __z = _M_create_node(__v);
820
821 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
822 this->_M_impl._M_header);
823 ++_M_impl._M_node_count;
824 return iterator(__z);
825 }
826
827 template<typename _Key, typename _Val, typename _KeyOfValue,
828 typename _Compare, typename _Alloc>
829 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
830 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
831 _M_insert(_Const_Base_ptr __x, _Const_Base_ptr __p, const _Val& __v)
832 {
833 bool __insert_left = (__x != 0 || __p == _M_end()
834 || _M_impl._M_key_compare(_KeyOfValue()(__v),
835 _S_key(__p)));
836
837 _Link_type __z = _M_create_node(__v);
838
839 _Rb_tree_insert_and_rebalance(__insert_left, __z,
840 const_cast<_Base_ptr>(__p),
841 this->_M_impl._M_header);
842 ++_M_impl._M_node_count;
843 return const_iterator(__z);
844 }
845
846 template<typename _Key, typename _Val, typename _KeyOfValue,
847 typename _Compare, typename _Alloc>
848 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
849 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
850 insert_equal(const _Val& __v)
851 {
852 _Link_type __x = _M_begin();
853 _Link_type __y = _M_end();
854 while (__x != 0)
855 {
856 __y = __x;
857 __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
858 _S_left(__x) : _S_right(__x);
859 }
860 return _M_insert(__x, __y, __v);
861 }
862
863 template<typename _Key, typename _Val, typename _KeyOfValue,
864 typename _Compare, typename _Alloc>
865 void
866 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
867 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t)
868 {
869 if (_M_root() == 0)
870 {
871 if (__t._M_root() != 0)
872 {
873 _M_root() = __t._M_root();
874 _M_leftmost() = __t._M_leftmost();
875 _M_rightmost() = __t._M_rightmost();
876 _M_root()->_M_parent = _M_end();
877
878 __t._M_root() = 0;
879 __t._M_leftmost() = __t._M_end();
880 __t._M_rightmost() = __t._M_end();
881 }
882 }
883 else if (__t._M_root() == 0)
884 {
885 __t._M_root() = _M_root();
886 __t._M_leftmost() = _M_leftmost();
887 __t._M_rightmost() = _M_rightmost();
888 __t._M_root()->_M_parent = __t._M_end();
889
890 _M_root() = 0;
891 _M_leftmost() = _M_end();
892 _M_rightmost() = _M_end();
893 }
894 else
895 {
896 std::swap(_M_root(),__t._M_root());
897 std::swap(_M_leftmost(),__t._M_leftmost());
898 std::swap(_M_rightmost(),__t._M_rightmost());
899
900 _M_root()->_M_parent = _M_end();
901 __t._M_root()->_M_parent = __t._M_end();
902 }
903 // No need to swap header's color as it does not change.
904 std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
905 std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
906 }
907
908 template<typename _Key, typename _Val, typename _KeyOfValue,
909 typename _Compare, typename _Alloc>
910 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
911 _Compare, _Alloc>::iterator, bool>
912 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
913 insert_unique(const _Val& __v)
914 {
915 _Link_type __x = _M_begin();
916 _Link_type __y = _M_end();
917 bool __comp = true;
918 while (__x != 0)
919 {
920 __y = __x;
921 __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x));
922 __x = __comp ? _S_left(__x) : _S_right(__x);
923 }
924 iterator __j = iterator(__y);
925 if (__comp)
926 if (__j == begin())
927 return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
928 else
929 --__j;
930 if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
931 return pair<iterator, bool>(_M_insert(__x, __y, __v), true);
932 return pair<iterator, bool>(__j, false);
933 }
934
935 template<typename _Key, typename _Val, typename _KeyOfValue,
936 typename _Compare, typename _Alloc>
937 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
938 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
939 insert_unique(iterator __position, const _Val& __v)
940 {
941 // end()
942 if (__position._M_node == _M_end())
943 {
944 if (size() > 0
945 && _M_impl._M_key_compare(_S_key(_M_rightmost()),
946 _KeyOfValue()(__v)))
947 return _M_insert(0, _M_rightmost(), __v);
948 else
949 return insert_unique(__v).first;
950 }
951 else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
952 _S_key(__position._M_node)))
953 {
954 // First, try before...
955 iterator __before = __position;
956 if (__position._M_node == _M_leftmost()) // begin()
957 return _M_insert(_M_leftmost(), _M_leftmost(), __v);
958 else if (_M_impl._M_key_compare(_S_key((--__before)._M_node),
959 _KeyOfValue()(__v)))
960 {
961 if (_S_right(__before._M_node) == 0)
962 return _M_insert(0, __before._M_node, __v);
963 else
964 return _M_insert(__position._M_node,
965 __position._M_node, __v);
966 }
967 else
968 return insert_unique(__v).first;
969 }
970 else if (_M_impl._M_key_compare(_S_key(__position._M_node),
971 _KeyOfValue()(__v)))
972 {
973 // ... then try after.
974 iterator __after = __position;
975 if (__position._M_node == _M_rightmost())
976 return _M_insert(0, _M_rightmost(), __v);
977 else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
978 _S_key((++__after)._M_node)))
979 {
980 if (_S_right(__position._M_node) == 0)
981 return _M_insert(0, __position._M_node, __v);
982 else
983 return _M_insert(__after._M_node, __after._M_node, __v);
984 }
985 else
986 return insert_unique(__v).first;
987 }
988 else
989 return __position; // Equivalent keys.
990 }
991
992 template<typename _Key, typename _Val, typename _KeyOfValue,
993 typename _Compare, typename _Alloc>
994 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
995 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
996 insert_unique(const_iterator __position, const _Val& __v)
997 {
998 // end()
999 if (__position._M_node == _M_end())
1000 {
1001 if (size() > 0
1002 && _M_impl._M_key_compare(_S_key(_M_rightmost()),
1003 _KeyOfValue()(__v)))
1004 return _M_insert(0, _M_rightmost(), __v);
1005 else
1006 return const_iterator(insert_unique(__v).first);
1007 }
1008 else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
1009 _S_key(__position._M_node)))
1010 {
1011 // First, try before...
1012 const_iterator __before = __position;
1013 if (__position._M_node == _M_leftmost()) // begin()
1014 return _M_insert(_M_leftmost(), _M_leftmost(), __v);
1015 else if (_M_impl._M_key_compare(_S_key((--__before)._M_node),
1016 _KeyOfValue()(__v)))
1017 {
1018 if (_S_right(__before._M_node) == 0)
1019 return _M_insert(0, __before._M_node, __v);
1020 else
1021 return _M_insert(__position._M_node,
1022 __position._M_node, __v);
1023 }
1024 else
1025 return const_iterator(insert_unique(__v).first);
1026 }
1027 else if (_M_impl._M_key_compare(_S_key(__position._M_node),
1028 _KeyOfValue()(__v)))
1029 {
1030 // ... then try after.
1031 const_iterator __after = __position;
1032 if (__position._M_node == _M_rightmost())
1033 return _M_insert(0, _M_rightmost(), __v);
1034 else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
1035 _S_key((++__after)._M_node)))
1036 {
1037 if (_S_right(__position._M_node) == 0)
1038 return _M_insert(0, __position._M_node, __v);
1039 else
1040 return _M_insert(__after._M_node, __after._M_node, __v);
1041 }
1042 else
1043 return const_iterator(insert_unique(__v).first);
1044 }
1045 else
1046 return __position; // Equivalent keys.
1047 }
1048
1049 template<typename _Key, typename _Val, typename _KeyOfValue,
1050 typename _Compare, typename _Alloc>
1051 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1052 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1053 insert_equal(iterator __position, const _Val& __v)
1054 {
1055 // end()
1056 if (__position._M_node == _M_end())
1057 {
1058 if (size() > 0
1059 && !_M_impl._M_key_compare(_KeyOfValue()(__v),
1060 _S_key(_M_rightmost())))
1061 return _M_insert(0, _M_rightmost(), __v);
1062 else
1063 return insert_equal(__v);
1064 }
1065 else if (!_M_impl._M_key_compare(_S_key(__position._M_node),
1066 _KeyOfValue()(__v)))
1067 {
1068 // First, try before...
1069 iterator __before = __position;
1070 if (__position._M_node == _M_leftmost()) // begin()
1071 return _M_insert(_M_leftmost(), _M_leftmost(), __v);
1072 else if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
1073 _S_key((--__before)._M_node)))
1074 {
1075 if (_S_right(__before._M_node) == 0)
1076 return _M_insert(0, __before._M_node, __v);
1077 else
1078 return _M_insert(__position._M_node,
1079 __position._M_node, __v);
1080 }
1081 else
1082 return insert_equal(__v);
1083 }
1084 else
1085 {
1086 // ... then try after.
1087 iterator __after = __position;
1088 if (__position._M_node == _M_rightmost())
1089 return _M_insert(0, _M_rightmost(), __v);
1090 else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node),
1091 _KeyOfValue()(__v)))
1092 {
1093 if (_S_right(__position._M_node) == 0)
1094 return _M_insert(0, __position._M_node, __v);
1095 else
1096 return _M_insert(__after._M_node, __after._M_node, __v);
1097 }
1098 else
1099 return insert_equal(__v);
1100 }
1101 }
1102
1103 template<typename _Key, typename _Val, typename _KeyOfValue,
1104 typename _Compare, typename _Alloc>
1105 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
1106 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1107 insert_equal(const_iterator __position, const _Val& __v)
1108 {
1109 // end()
1110 if (__position._M_node == _M_end())
1111 {
1112 if (size() > 0
1113 && !_M_impl._M_key_compare(_KeyOfValue()(__v),
1114 _S_key(_M_rightmost())))
1115 return _M_insert(0, _M_rightmost(), __v);
1116 else
1117 return const_iterator(insert_equal(__v));
1118 }
1119 else if (!_M_impl._M_key_compare(_S_key(__position._M_node),
1120 _KeyOfValue()(__v)))
1121 {
1122 // First, try before...
1123 const_iterator __before = __position;
1124 if (__position._M_node == _M_leftmost()) // begin()
1125 return _M_insert(_M_leftmost(), _M_leftmost(), __v);
1126 else if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
1127 _S_key((--__before)._M_node)))
1128 {
1129 if (_S_right(__before._M_node) == 0)
1130 return _M_insert(0, __before._M_node, __v);
1131 else
1132 return _M_insert(__position._M_node,
1133 __position._M_node, __v);
1134 }
1135 else
1136 return const_iterator(insert_equal(__v));
1137 }
1138 else
1139 {
1140 // ... then try after.
1141 const_iterator __after = __position;
1142 if (__position._M_node == _M_rightmost())
1143 return _M_insert(0, _M_rightmost(), __v);
1144 else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node),
1145 _KeyOfValue()(__v)))
1146 {
1147 if (_S_right(__position._M_node) == 0)
1148 return _M_insert(0, __position._M_node, __v);
1149 else
1150 return _M_insert(__after._M_node, __after._M_node, __v);
1151 }
1152 else
1153 return const_iterator(insert_equal(__v));
1154 }
1155 }
1156
1157 template<typename _Key, typename _Val, typename _KoV,
1158 typename _Cmp, typename _Alloc>
1159 template<class _II>
1160 void
1161 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
1162 insert_equal(_II __first, _II __last)
1163 {
1164 for (; __first != __last; ++__first)
1165 insert_equal(end(), *__first);
1166 }
1167
1168 template<typename _Key, typename _Val, typename _KoV,
1169 typename _Cmp, typename _Alloc>
1170 template<class _II>
1171 void
1172 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
1173 insert_unique(_II __first, _II __last)
1174 {
1175 for (; __first != __last; ++__first)
1176 insert_unique(end(), *__first);
1177 }
1178
1179 template<typename _Key, typename _Val, typename _KeyOfValue,
1180 typename _Compare, typename _Alloc>
1181 inline void
1182 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1183 erase(iterator __position)
1184 {
1185 _Link_type __y =
1186 static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
1187 (__position._M_node,
1188 this->_M_impl._M_header));
1189 destroy_node(__y);
1190 --_M_impl._M_node_count;
1191 }
1192
1193 template<typename _Key, typename _Val, typename _KeyOfValue,
1194 typename _Compare, typename _Alloc>
1195 inline void
1196 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1197 erase(const_iterator __position)
1198 {
1199 _Link_type __y =
1200 static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
1201 (const_cast<_Base_ptr>(__position._M_node),
1202 this->_M_impl._M_header));
1203 destroy_node(__y);
1204 --_M_impl._M_node_count;
1205 }
1206
1207 template<typename _Key, typename _Val, typename _KeyOfValue,
1208 typename _Compare, typename _Alloc>
1209 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
1210 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1211 erase(const _Key& __x)
1212 {
1213 pair<iterator,iterator> __p = equal_range(__x);
1214 size_type __n = std::distance(__p.first, __p.second);
1215 erase(__p.first, __p.second);
1216 return __n;
1217 }
1218
1219 template<typename _Key, typename _Val, typename _KoV,
1220 typename _Compare, typename _Alloc>
1221 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
1222 _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
1223 _M_copy(_Const_Link_type __x, _Link_type __p)
1224 {
1225 // Structural copy. __x and __p must be non-null.
1226 _Link_type __top = _M_clone_node(__x);
1227 __top->_M_parent = __p;
1228
1229 try
1230 {
1231 if (__x->_M_right)
1232 __top->_M_right = _M_copy(_S_right(__x), __top);
1233 __p = __top;
1234 __x = _S_left(__x);
1235
1236 while (__x != 0)
1237 {
1238 _Link_type __y = _M_clone_node(__x);
1239 __p->_M_left = __y;
1240 __y->_M_parent = __p;
1241 if (__x->_M_right)
1242 __y->_M_right = _M_copy(_S_right(__x), __y);
1243 __p = __y;
1244 __x = _S_left(__x);
1245 }
1246 }
1247 catch(...)
1248 {
1249 _M_erase(__top);
1250 __throw_exception_again;
1251 }
1252 return __top;
1253 }
1254
1255 template<typename _Key, typename _Val, typename _KeyOfValue,
1256 typename _Compare, typename _Alloc>
1257 void
1258 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1259 _M_erase(_Link_type __x)
1260 {
1261 // Erase without rebalancing.
1262 while (__x != 0)
1263 {
1264 _M_erase(_S_right(__x));
1265 _Link_type __y = _S_left(__x);
1266 destroy_node(__x);
1267 __x = __y;
1268 }
1269 }
1270
1271 template<typename _Key, typename _Val, typename _KeyOfValue,
1272 typename _Compare, typename _Alloc>
1273 void
1274 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1275 erase(iterator __first, iterator __last)
1276 {
1277 if (__first == begin() && __last == end())
1278 clear();
1279 else
1280 while (__first != __last)
1281 erase(__first++);
1282 }
1283
1284 template<typename _Key, typename _Val, typename _KeyOfValue,
1285 typename _Compare, typename _Alloc>
1286 void
1287 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1288 erase(const_iterator __first, const_iterator __last)
1289 {
1290 if (__first == begin() && __last == end())
1291 clear();
1292 else
1293 while (__first != __last)
1294 erase(__first++);
1295 }
1296
1297 template<typename _Key, typename _Val, typename _KeyOfValue,
1298 typename _Compare, typename _Alloc>
1299 void
1300 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1301 erase(const _Key* __first, const _Key* __last)
1302 {
1303 while (__first != __last)
1304 erase(*__first++);
1305 }
1306
1307 template<typename _Key, typename _Val, typename _KeyOfValue,
1308 typename _Compare, typename _Alloc>
1309 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1310 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1311 find(const _Key& __k)
1312 {
1313 _Link_type __x = _M_begin(); // Current node.
1314 _Link_type __y = _M_end(); // Last node which is not less than __k.
1315
1316 while (__x != 0)
1317 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1318 __y = __x, __x = _S_left(__x);
1319 else
1320 __x = _S_right(__x);
1321
1322 iterator __j = iterator(__y);
1323 return (__j == end()
1324 || _M_impl._M_key_compare(__k,
1325 _S_key(__j._M_node))) ? end() : __j;
1326 }
1327
1328 template<typename _Key, typename _Val, typename _KeyOfValue,
1329 typename _Compare, typename _Alloc>
1330 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
1331 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1332 find(const _Key& __k) const
1333 {
1334 _Const_Link_type __x = _M_begin(); // Current node.
1335 _Const_Link_type __y = _M_end(); // Last node which is not less than __k.
1336
1337 while (__x != 0)
1338 {
1339 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1340 __y = __x, __x = _S_left(__x);
1341 else
1342 __x = _S_right(__x);
1343 }
1344 const_iterator __j = const_iterator(__y);
1345 return (__j == end()
1346 || _M_impl._M_key_compare(__k,
1347 _S_key(__j._M_node))) ? end() : __j;
1348 }
1349
1350 template<typename _Key, typename _Val, typename _KeyOfValue,
1351 typename _Compare, typename _Alloc>
1352 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
1353 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1354 count(const _Key& __k) const
1355 {
1356 pair<const_iterator, const_iterator> __p = equal_range(__k);
1357 const size_type __n = std::distance(__p.first, __p.second);
1358 return __n;
1359 }
1360
1361 template<typename _Key, typename _Val, typename _KeyOfValue,
1362 typename _Compare, typename _Alloc>
1363 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1364 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1365 lower_bound(const _Key& __k)
1366 {
1367 _Link_type __x = _M_begin(); // Current node.
1368 _Link_type __y = _M_end(); // Last node which is not less than __k.
1369
1370 while (__x != 0)
1371 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1372 __y = __x, __x = _S_left(__x);
1373 else
1374 __x = _S_right(__x);
1375
1376 return iterator(__y);
1377 }
1378
1379 template<typename _Key, typename _Val, typename _KeyOfValue,
1380 typename _Compare, typename _Alloc>
1381 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
1382 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1383 lower_bound(const _Key& __k) const
1384 {
1385 _Const_Link_type __x = _M_begin(); // Current node.
1386 _Const_Link_type __y = _M_end(); // Last node which is not less than __k.
1387
1388 while (__x != 0)
1389 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1390 __y = __x, __x = _S_left(__x);
1391 else
1392 __x = _S_right(__x);
1393
1394 return const_iterator(__y);
1395 }
1396
1397 template<typename _Key, typename _Val, typename _KeyOfValue,
1398 typename _Compare, typename _Alloc>
1399 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1400 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1401 upper_bound(const _Key& __k)
1402 {
1403 _Link_type __x = _M_begin(); // Current node.
1404 _Link_type __y = _M_end(); // Last node which is greater than __k.
1405
1406 while (__x != 0)
1407 if (_M_impl._M_key_compare(__k, _S_key(__x)))
1408 __y = __x, __x = _S_left(__x);
1409 else
1410 __x = _S_right(__x);
1411
1412 return iterator(__y);
1413 }
1414
1415 template<typename _Key, typename _Val, typename _KeyOfValue,
1416 typename _Compare, typename _Alloc>
1417 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
1418 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1419 upper_bound(const _Key& __k) const
1420 {
1421 _Const_Link_type __x = _M_begin(); // Current node.
1422 _Const_Link_type __y = _M_end(); // Last node which is greater than __k.
1423
1424 while (__x != 0)
1425 if (_M_impl._M_key_compare(__k, _S_key(__x)))
1426 __y = __x, __x = _S_left(__x);
1427 else
1428 __x = _S_right(__x);
1429
1430 return const_iterator(__y);
1431 }
1432
1433 template<typename _Key, typename _Val, typename _KeyOfValue,
1434 typename _Compare, typename _Alloc>
1435 inline
1436 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1437 _Compare, _Alloc>::iterator,
1438 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator>
1439 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1440 equal_range(const _Key& __k)
1441 { return pair<iterator, iterator>(lower_bound(__k), upper_bound(__k)); }
1442
1443 template<typename _Key, typename _Val, typename _KoV,
1444 typename _Compare, typename _Alloc>
1445 inline
1446 pair<typename _Rb_tree<_Key, _Val, _KoV,
1447 _Compare, _Alloc>::const_iterator,
1448 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::const_iterator>
1449 _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
1450 equal_range(const _Key& __k) const
1451 { return pair<const_iterator, const_iterator>(lower_bound(__k),
1452 upper_bound(__k)); }
1453
1454 unsigned int
1455 _Rb_tree_black_count(const _Rb_tree_node_base* __node,
1456 const _Rb_tree_node_base* __root);
1457
1458 template<typename _Key, typename _Val, typename _KeyOfValue,
1459 typename _Compare, typename _Alloc>
1460 bool
1461 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
1462 {
1463 if (_M_impl._M_node_count == 0 || begin() == end())
1464 return _M_impl._M_node_count == 0 && begin() == end()
1465 && this->_M_impl._M_header._M_left == _M_end()
1466 && this->_M_impl._M_header._M_right == _M_end();
1467
1468 unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
1469 for (const_iterator __it = begin(); __it != end(); ++__it)
1470 {
1471 _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
1472 _Const_Link_type __L = _S_left(__x);
1473 _Const_Link_type __R = _S_right(__x);
1474
1475 if (__x->_M_color == _S_red)
1476 if ((__L && __L->_M_color == _S_red)
1477 || (__R && __R->_M_color == _S_red))
1478 return false;
1479
1480 if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
1481 return false;
1482 if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
1483 return false;
1484
1485 if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
1486 return false;
1487 }
1488
1489 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
1490 return false;
1491 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
1492 return false;
1493 return true;
1494 }
1495
1496 _GLIBCXX_END_NAMESPACE
1497
1498 #endif