OSDN Git Service

2004-03-25 Gawain Bolton <gp.bolton@computer.org>
[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 #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