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