OSDN Git Service

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