stl_tree.h

Go to the documentation of this file.
00001 // RB tree implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2001, 2002, 2005 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 2, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // You should have received a copy of the GNU General Public License along
00017 // with this library; see the file COPYING.  If not, write to the Free
00018 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
00019 // USA.
00020 
00021 // As a special exception, you may use this file as part of a free software
00022 // library without restriction.  Specifically, if other files instantiate
00023 // templates or use macros or inline functions from this file, or you compile
00024 // this file and link it with other files to produce an executable, this
00025 // file does not by itself cause the resulting executable to be covered by
00026 // the GNU General Public License.  This exception does not however
00027 // invalidate any other reasons why the executable file might be covered by
00028 // the GNU General Public License.
00029 
00030 /*
00031  *
00032  * Copyright (c) 1996,1997
00033  * Silicon Graphics Computer Systems, Inc.
00034  *
00035  * Permission to use, copy, modify, distribute and sell this software
00036  * and its documentation for any purpose is hereby granted without fee,
00037  * provided that the above copyright notice appear in all copies and
00038  * that both that copyright notice and this permission notice appear
00039  * in supporting documentation.  Silicon Graphics makes no
00040  * representations about the suitability of this software for any
00041  * purpose.  It is provided "as is" without express or implied warranty.
00042  *
00043  *
00044  * Copyright (c) 1994
00045  * Hewlett-Packard Company
00046  *
00047  * Permission to use, copy, modify, distribute and sell this software
00048  * and its documentation for any purpose is hereby granted without fee,
00049  * provided that the above copyright notice appear in all copies and
00050  * that both that copyright notice and this permission notice appear
00051  * in supporting documentation.  Hewlett-Packard Company makes no
00052  * representations about the suitability of this software for any
00053  * purpose.  It is provided "as is" without express or implied warranty.
00054  *
00055  *
00056  */
00057 
00058 /** @file stl_tree.h
00059  *  This is an internal header file, included by other library headers.
00060  *  You should not attempt to use it directly.
00061  */
00062 
00063 #ifndef __GLIBCPP_INTERNAL_TREE_H
00064 #define __GLIBCPP_INTERNAL_TREE_H
00065 
00066 /*
00067 
00068 Red-black tree class, designed for use in implementing STL
00069 associative containers (set, multiset, map, and multimap). The
00070 insertion and deletion algorithms are based on those in Cormen,
00071 Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 1990),
00072 except that
00073 
00074 (1) the header cell is maintained with links not only to the root
00075 but also to the leftmost node of the tree, to enable constant time
00076 begin(), and to the rightmost node of the tree, to enable linear time
00077 performance when used with the generic set algorithms (set_union,
00078 etc.);
00079 
00080 (2) when a node being deleted has two children its successor node is
00081 relinked into its place, rather than copied, so that the only
00082 iterators invalidated are those referring to the deleted node.
00083 
00084 */
00085 
00086 #include <bits/stl_algobase.h>
00087 #include <bits/stl_alloc.h>
00088 #include <bits/stl_construct.h>
00089 #include <bits/stl_function.h>
00090 
00091 namespace std
00092 { 
00093   enum _Rb_tree_color { _M_red = false, _M_black = true };
00094 
00095   struct _Rb_tree_node_base
00096   {
00097     typedef _Rb_tree_node_base* _Base_ptr;
00098     
00099     _Rb_tree_color  _M_color; 
00100     _Base_ptr       _M_parent;
00101     _Base_ptr       _M_left;
00102     _Base_ptr       _M_right;
00103     
00104     static _Base_ptr 
00105     _S_minimum(_Base_ptr __x)
00106     {
00107       while (__x->_M_left != 0) __x = __x->_M_left;
00108       return __x;
00109     }
00110 
00111     static _Base_ptr 
00112     _S_maximum(_Base_ptr __x)
00113     {
00114       while (__x->_M_right != 0) __x = __x->_M_right;
00115       return __x;
00116     }
00117   };
00118 
00119   template<typename _Val>
00120     struct _Rb_tree_node : public _Rb_tree_node_base
00121     {
00122       typedef _Rb_tree_node<_Val>* _Link_type;
00123       _Val _M_value_field;
00124     };
00125   
00126   struct _Rb_tree_base_iterator
00127   {
00128     typedef _Rb_tree_node_base::_Base_ptr   _Base_ptr;
00129     typedef bidirectional_iterator_tag      iterator_category;
00130     typedef ptrdiff_t               difference_type;
00131 
00132     _Base_ptr _M_node;
00133 
00134     void 
00135     _M_increment()
00136     {
00137       if (_M_node->_M_right != 0) 
00138     {
00139       _M_node = _M_node->_M_right;
00140       while (_M_node->_M_left != 0)
00141         _M_node = _M_node->_M_left;
00142     }
00143       else 
00144     {
00145       _Base_ptr __y = _M_node->_M_parent;
00146       while (_M_node == __y->_M_right) 
00147         {
00148           _M_node = __y;
00149           __y = __y->_M_parent;
00150         }
00151       if (_M_node->_M_right != __y)
00152         _M_node = __y;
00153     }
00154     }
00155 
00156     void 
00157     _M_decrement()
00158     {
00159       if (_M_node->_M_color == _M_red 
00160       && _M_node->_M_parent->_M_parent == _M_node)
00161     _M_node = _M_node->_M_right;
00162       else if (_M_node->_M_left != 0) 
00163     {
00164       _Base_ptr __y = _M_node->_M_left;
00165       while (__y->_M_right != 0)
00166         __y = __y->_M_right;
00167       _M_node = __y;
00168     }
00169       else 
00170     {
00171       _Base_ptr __y = _M_node->_M_parent;
00172       while (_M_node == __y->_M_left) 
00173         {
00174           _M_node = __y;
00175           __y = __y->_M_parent;
00176         }
00177       _M_node = __y;
00178     }
00179     }
00180   };
00181 
00182   template<typename _Val, typename _Ref, typename _Ptr>
00183     struct _Rb_tree_iterator : public _Rb_tree_base_iterator
00184     {
00185       typedef _Val value_type;
00186       typedef _Ref reference;
00187       typedef _Ptr pointer;
00188       typedef _Rb_tree_iterator<_Val, _Val&, _Val*> iterator;
00189       typedef _Rb_tree_iterator<_Val, const _Val&, const _Val*> 
00190       const_iterator;
00191       typedef _Rb_tree_iterator<_Val, _Ref, _Ptr> _Self;
00192       typedef _Rb_tree_node<_Val>* _Link_type;
00193       
00194       _Rb_tree_iterator() { _M_node = 0; }
00195       _Rb_tree_iterator(_Link_type __x) { _M_node = __x; }
00196       _Rb_tree_iterator(const iterator& __it) { _M_node = __it._M_node; }
00197 
00198       reference 
00199       operator*() const { return _Link_type(_M_node)->_M_value_field; }
00200 
00201       pointer 
00202       operator->() const { return &(operator*()); }
00203 
00204       _Self& 
00205       operator++() 
00206       { 
00207     _M_increment(); 
00208     return *this; 
00209       }
00210 
00211       _Self 
00212       operator++(int) 
00213       {
00214     _Self __tmp = *this;
00215     _M_increment();
00216     return __tmp;
00217       }
00218     
00219       _Self& 
00220       operator--() { _M_decrement(); return *this; }
00221 
00222       _Self 
00223       operator--(int) 
00224       {
00225     _Self __tmp = *this;
00226     _M_decrement();
00227     return __tmp;
00228       }
00229   };
00230 
00231   template<typename _Val, typename _Ref, typename _Ptr>
00232     inline bool 
00233     operator==(const _Rb_tree_iterator<_Val, _Ref, _Ptr>& __x,
00234            const _Rb_tree_iterator<_Val, _Ref, _Ptr>& __y) 
00235     { return __x._M_node == __y._M_node; }
00236 
00237   template<typename _Val>
00238     inline bool 
00239     operator==(const _Rb_tree_iterator<_Val, const _Val&, const _Val*>& __x,
00240            const _Rb_tree_iterator<_Val, _Val&, _Val*>& __y) 
00241     { return __x._M_node == __y._M_node; }
00242 
00243   template<typename _Val>
00244     inline bool 
00245     operator==(const _Rb_tree_iterator<_Val, _Val&, _Val*>& __x,
00246            const _Rb_tree_iterator<_Val, const _Val&, const _Val*>& __y) 
00247     { return __x._M_node == __y._M_node; }
00248 
00249   template<typename _Val, typename _Ref, typename _Ptr>
00250     inline bool 
00251     operator!=(const _Rb_tree_iterator<_Val, _Ref, _Ptr>& __x,
00252            const _Rb_tree_iterator<_Val, _Ref, _Ptr>& __y) 
00253     { return __x._M_node != __y._M_node; }
00254 
00255   template<typename _Val>
00256     inline bool 
00257     operator!=(const _Rb_tree_iterator<_Val, const _Val&, const _Val*>& __x,
00258            const _Rb_tree_iterator<_Val, _Val&, _Val*>& __y) 
00259     { return __x._M_node != __y._M_node; }
00260 
00261   template<typename _Val>
00262     inline bool 
00263     operator!=(const _Rb_tree_iterator<_Val, _Val&, _Val*>& __x,
00264            const _Rb_tree_iterator<_Val, const _Val&, const _Val*>& __y) 
00265     { return __x._M_node != __y._M_node; }
00266 
00267   inline void 
00268   _Rb_tree_rotate_left(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root)
00269   {
00270     _Rb_tree_node_base* __y = __x->_M_right;
00271     __x->_M_right = __y->_M_left;
00272     if (__y->_M_left !=0)
00273       __y->_M_left->_M_parent = __x;
00274     __y->_M_parent = __x->_M_parent;
00275     
00276     if (__x == __root)
00277       __root = __y;
00278     else if (__x == __x->_M_parent->_M_left)
00279       __x->_M_parent->_M_left = __y;
00280     else
00281       __x->_M_parent->_M_right = __y;
00282     __y->_M_left = __x;
00283     __x->_M_parent = __y;
00284   }
00285 
00286   inline void 
00287   _Rb_tree_rotate_right(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root)
00288   {
00289     _Rb_tree_node_base* __y = __x->_M_left;
00290     __x->_M_left = __y->_M_right;
00291     if (__y->_M_right != 0)
00292       __y->_M_right->_M_parent = __x;
00293     __y->_M_parent = __x->_M_parent;
00294 
00295     if (__x == __root)
00296       __root = __y;
00297     else if (__x == __x->_M_parent->_M_right)
00298       __x->_M_parent->_M_right = __y;
00299     else
00300       __x->_M_parent->_M_left = __y;
00301     __y->_M_right = __x;
00302     __x->_M_parent = __y;
00303   }
00304 
00305   inline void 
00306   _Rb_tree_rebalance(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root)
00307   {
00308     __x->_M_color = _M_red;
00309     while (__x != __root 
00310        && __x->_M_parent->_M_color == _M_red) 
00311       {
00312     if (__x->_M_parent == __x->_M_parent->_M_parent->_M_left) 
00313       {
00314         _Rb_tree_node_base* __y = __x->_M_parent->_M_parent->_M_right;
00315         if (__y && __y->_M_color == _M_red) 
00316           {
00317         __x->_M_parent->_M_color = _M_black;
00318         __y->_M_color = _M_black;
00319         __x->_M_parent->_M_parent->_M_color = _M_red;
00320         __x = __x->_M_parent->_M_parent;
00321           }
00322         else 
00323           {
00324         if (__x == __x->_M_parent->_M_right) 
00325           {
00326             __x = __x->_M_parent;
00327             _Rb_tree_rotate_left(__x, __root);
00328           }
00329         __x->_M_parent->_M_color = _M_black;
00330         __x->_M_parent->_M_parent->_M_color = _M_red;
00331         _Rb_tree_rotate_right(__x->_M_parent->_M_parent, __root);
00332           }
00333       }
00334     else 
00335       {
00336         _Rb_tree_node_base* __y = __x->_M_parent->_M_parent->_M_left;
00337         if (__y && __y->_M_color == _M_red) 
00338           {
00339         __x->_M_parent->_M_color = _M_black;
00340         __y->_M_color = _M_black;
00341         __x->_M_parent->_M_parent->_M_color = _M_red;
00342         __x = __x->_M_parent->_M_parent;
00343           }
00344         else 
00345           {
00346         if (__x == __x->_M_parent->_M_left) 
00347           {
00348             __x = __x->_M_parent;
00349             _Rb_tree_rotate_right(__x, __root);
00350           }
00351         __x->_M_parent->_M_color = _M_black;
00352         __x->_M_parent->_M_parent->_M_color = _M_red;
00353         _Rb_tree_rotate_left(__x->_M_parent->_M_parent, __root);
00354           }
00355       }
00356       }
00357     __root->_M_color = _M_black;
00358   }
00359 
00360   inline _Rb_tree_node_base*
00361   _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* __z, 
00362                    _Rb_tree_node_base*& __root,
00363                    _Rb_tree_node_base*& __leftmost,
00364                    _Rb_tree_node_base*& __rightmost)
00365   {
00366     _Rb_tree_node_base* __y = __z;
00367     _Rb_tree_node_base* __x = 0;
00368     _Rb_tree_node_base* __x_parent = 0;
00369     if (__y->_M_left == 0)     // __z has at most one non-null child. y == z.
00370       __x = __y->_M_right;     // __x might be null.
00371     else
00372       if (__y->_M_right == 0)  // __z has exactly one non-null child. y == z.
00373     __x = __y->_M_left;    // __x is not null.
00374       else 
00375     {
00376       // __z has two non-null children.  Set __y to
00377       __y = __y->_M_right;   //   __z's successor.  __x might be null.
00378       while (__y->_M_left != 0)
00379         __y = __y->_M_left;
00380       __x = __y->_M_right;
00381     }
00382     if (__y != __z) 
00383       {
00384     // relink y in place of z.  y is z's successor
00385     __z->_M_left->_M_parent = __y; 
00386     __y->_M_left = __z->_M_left;
00387     if (__y != __z->_M_right) 
00388       {
00389         __x_parent = __y->_M_parent;
00390         if (__x) __x->_M_parent = __y->_M_parent;
00391         __y->_M_parent->_M_left = __x;   // __y must be a child of _M_left
00392         __y->_M_right = __z->_M_right;
00393         __z->_M_right->_M_parent = __y;
00394       }
00395     else
00396       __x_parent = __y;  
00397     if (__root == __z)
00398       __root = __y;
00399     else if (__z->_M_parent->_M_left == __z)
00400       __z->_M_parent->_M_left = __y;
00401     else 
00402       __z->_M_parent->_M_right = __y;
00403     __y->_M_parent = __z->_M_parent;
00404     std::swap(__y->_M_color, __z->_M_color);
00405     __y = __z;
00406     // __y now points to node to be actually deleted
00407       }
00408     else 
00409       {                        // __y == __z
00410     __x_parent = __y->_M_parent;
00411     if (__x) 
00412       __x->_M_parent = __y->_M_parent;   
00413     if (__root == __z)
00414       __root = __x;
00415     else 
00416       if (__z->_M_parent->_M_left == __z)
00417         __z->_M_parent->_M_left = __x;
00418       else
00419         __z->_M_parent->_M_right = __x;
00420     if (__leftmost == __z) 
00421       if (__z->_M_right == 0)        // __z->_M_left must be null also
00422         __leftmost = __z->_M_parent;
00423     // makes __leftmost == _M_header if __z == __root
00424       else
00425         __leftmost = _Rb_tree_node_base::_S_minimum(__x);
00426     if (__rightmost == __z)  
00427       if (__z->_M_left == 0)         // __z->_M_right must be null also
00428         __rightmost = __z->_M_parent;  
00429     // makes __rightmost == _M_header if __z == __root
00430       else                      // __x == __z->_M_left
00431         __rightmost = _Rb_tree_node_base::_S_maximum(__x);
00432       }
00433     if (__y->_M_color != _M_red) 
00434       { 
00435     while (__x != __root && (__x == 0 || __x->_M_color == _M_black))
00436       if (__x == __x_parent->_M_left) 
00437         {
00438           _Rb_tree_node_base* __w = __x_parent->_M_right;
00439           if (__w->_M_color == _M_red) 
00440         {
00441           __w->_M_color = _M_black;
00442           __x_parent->_M_color = _M_red;
00443           _Rb_tree_rotate_left(__x_parent, __root);
00444           __w = __x_parent->_M_right;
00445         }
00446           if ((__w->_M_left == 0 || 
00447            __w->_M_left->_M_color == _M_black) &&
00448           (__w->_M_right == 0 || 
00449            __w->_M_right->_M_color == _M_black)) 
00450         {
00451           __w->_M_color = _M_red;
00452           __x = __x_parent;
00453           __x_parent = __x_parent->_M_parent;
00454         } 
00455           else 
00456         {
00457           if (__w->_M_right == 0 
00458               || __w->_M_right->_M_color == _M_black) 
00459             {
00460               __w->_M_left->_M_color = _M_black;
00461               __w->_M_color = _M_red;
00462               _Rb_tree_rotate_right(__w, __root);
00463               __w = __x_parent->_M_right;
00464             }
00465           __w->_M_color = __x_parent->_M_color;
00466           __x_parent->_M_color = _M_black;
00467           if (__w->_M_right) 
00468             __w->_M_right->_M_color = _M_black;
00469           _Rb_tree_rotate_left(__x_parent, __root);
00470           break;
00471         }
00472         } 
00473       else 
00474         {   
00475           // same as above, with _M_right <-> _M_left.
00476           _Rb_tree_node_base* __w = __x_parent->_M_left;
00477           if (__w->_M_color == _M_red) 
00478         {
00479           __w->_M_color = _M_black;
00480           __x_parent->_M_color = _M_red;
00481           _Rb_tree_rotate_right(__x_parent, __root);
00482           __w = __x_parent->_M_left;
00483         }
00484           if ((__w->_M_right == 0 || 
00485            __w->_M_right->_M_color == _M_black) &&
00486           (__w->_M_left == 0 || 
00487            __w->_M_left->_M_color == _M_black)) 
00488         {
00489           __w->_M_color = _M_red;
00490           __x = __x_parent;
00491           __x_parent = __x_parent->_M_parent;
00492         } 
00493           else 
00494         {
00495           if (__w->_M_left == 0 || __w->_M_left->_M_color == _M_black) 
00496             {
00497               __w->_M_right->_M_color = _M_black;
00498               __w->_M_color = _M_red;
00499               _Rb_tree_rotate_left(__w, __root);
00500               __w = __x_parent->_M_left;
00501             }
00502           __w->_M_color = __x_parent->_M_color;
00503           __x_parent->_M_color = _M_black;
00504           if (__w->_M_left) 
00505             __w->_M_left->_M_color = _M_black;
00506           _Rb_tree_rotate_right(__x_parent, __root);
00507           break;
00508         }
00509         }
00510     if (__x) __x->_M_color = _M_black;
00511       }
00512     return __y;
00513   }
00514 
00515   // Base class to encapsulate the differences between old SGI-style
00516   // allocators and standard-conforming allocators.  In order to avoid
00517   // having an empty base class, we arbitrarily move one of rb_tree's
00518   // data members into the base class.
00519 
00520   // _Base for general standard-conforming allocators.
00521   template<typename _Tp, typename _Alloc, bool _S_instanceless>
00522     class _Rb_tree_alloc_base 
00523     {
00524     public:
00525     typedef typename _Alloc_traits<_Tp, _Alloc>::allocator_type allocator_type;
00526 
00527       allocator_type 
00528       get_allocator() const { return _M_node_allocator; }
00529 
00530       _Rb_tree_alloc_base(const allocator_type& __a)
00531       : _M_node_allocator(__a), _M_header(0) {}
00532 
00533     protected:
00534       typename _Alloc_traits<_Rb_tree_node<_Tp>, _Alloc>::allocator_type
00535       _M_node_allocator;
00536 
00537       _Rb_tree_node<_Tp>* _M_header;
00538       
00539       _Rb_tree_node<_Tp>* 
00540       _M_get_node()  { return _M_node_allocator.allocate(1); }
00541 
00542       void 
00543       _M_put_node(_Rb_tree_node<_Tp>* __p) 
00544       { _M_node_allocator.deallocate(__p, 1); }
00545     };
00546 
00547   // Specialization for instanceless allocators.
00548   template<typename _Tp, typename _Alloc>
00549     class _Rb_tree_alloc_base<_Tp, _Alloc, true> 
00550     {
00551     public:
00552     typedef typename _Alloc_traits<_Tp, _Alloc>::allocator_type allocator_type;
00553       allocator_type get_allocator() const { return allocator_type(); }
00554 
00555       _Rb_tree_alloc_base(const allocator_type&) : _M_header(0) {}
00556 
00557     protected:
00558       _Rb_tree_node<_Tp>* _M_header;
00559       
00560       typedef typename _Alloc_traits<_Rb_tree_node<_Tp>, _Alloc>::_Alloc_type
00561       _Alloc_type;
00562       
00563       _Rb_tree_node<_Tp>* 
00564       _M_get_node() { return _Alloc_type::allocate(1); }
00565 
00566       void 
00567       _M_put_node(_Rb_tree_node<_Tp>* __p) { _Alloc_type::deallocate(__p, 1); }
00568     };
00569   
00570   template<typename _Tp, typename _Alloc>
00571     struct _Rb_tree_base : public _Rb_tree_alloc_base<_Tp, _Alloc, 
00572                                   _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
00573     {
00574       typedef _Rb_tree_alloc_base<_Tp, 
00575     _Alloc, _Alloc_traits<_Tp, _Alloc>::_S_instanceless> _Base;
00576       typedef typename _Base::allocator_type allocator_type;
00577 
00578       _Rb_tree_base(const allocator_type& __a) 
00579       : _Base(__a) { _M_header = _M_get_node(); }
00580       ~_Rb_tree_base() { _M_put_node(_M_header); }
00581     };
00582 
00583 
00584   template<typename _Key, typename _Val, typename _KeyOfValue, 
00585            typename _Compare, typename _Alloc = allocator<_Val> >
00586     class _Rb_tree : protected _Rb_tree_base<_Val, _Alloc> 
00587     {
00588       typedef _Rb_tree_base<_Val, _Alloc> _Base;
00589       
00590     protected:
00591       typedef _Rb_tree_node_base* _Base_ptr;
00592       typedef _Rb_tree_node<_Val> _Rb_tree_node;
00593       
00594     public:
00595       typedef _Key key_type;
00596       typedef _Val value_type;
00597       typedef value_type* pointer;
00598       typedef const value_type* const_pointer;
00599       typedef value_type& reference;
00600       typedef const value_type& const_reference;
00601       typedef _Rb_tree_node* _Link_type;
00602       typedef size_t size_type;
00603       typedef ptrdiff_t difference_type;
00604       
00605       typedef typename _Base::allocator_type allocator_type;
00606       allocator_type get_allocator() const { return _Base::get_allocator(); }
00607       
00608     protected:
00609       using _Base::_M_get_node;
00610       using _Base::_M_put_node;
00611       using _Base::_M_header;
00612       
00613       _Link_type
00614       _M_create_node(const value_type& __x)
00615       {
00616     _Link_type __tmp = _M_get_node();
00617     try 
00618       { _Construct(&__tmp->_M_value_field, __x); }
00619     catch(...)
00620       {
00621       _M_put_node(__tmp);
00622       __throw_exception_again; 
00623       }
00624     return __tmp;
00625       }
00626       
00627       _Link_type 
00628       _M_clone_node(_Link_type __x)
00629       {
00630     _Link_type __tmp = _M_create_node(__x->_M_value_field);
00631     __tmp->_M_color = __x->_M_color;
00632     __tmp->_M_left = 0;
00633     __tmp->_M_right = 0;
00634     return __tmp;
00635       }
00636 
00637       void
00638       destroy_node(_Link_type __p)
00639       {
00640     _Destroy(&__p->_M_value_field);
00641     _M_put_node(__p);
00642       }
00643 
00644       size_type _M_node_count; // keeps track of size of tree
00645       _Compare _M_key_compare;
00646 
00647       _Link_type& 
00648       _M_root() const { return (_Link_type&) _M_header->_M_parent; }
00649 
00650       _Link_type& 
00651       _M_leftmost() const { return (_Link_type&) _M_header->_M_left; }
00652 
00653       _Link_type& 
00654       _M_rightmost() const { return (_Link_type&) _M_header->_M_right; }
00655 
00656       static _Link_type& 
00657       _S_left(_Link_type __x) { return (_Link_type&)(__x->_M_left); }
00658 
00659       static _Link_type& 
00660       _S_right(_Link_type __x) { return (_Link_type&)(__x->_M_right); }
00661 
00662       static _Link_type& 
00663       _S_parent(_Link_type __x) { return (_Link_type&)(__x->_M_parent); }
00664 
00665       static reference 
00666       _S_value(_Link_type __x) { return __x->_M_value_field; }
00667 
00668       static const _Key& 
00669       _S_key(_Link_type __x) { return _KeyOfValue()(_S_value(__x)); }
00670 
00671       static _Rb_tree_color& 
00672       _S_color(_Link_type __x) { return __x->_M_color; }
00673 
00674       static _Link_type& 
00675       _S_left(_Base_ptr __x) { return (_Link_type&)(__x->_M_left); }
00676 
00677       static _Link_type& 
00678       _S_right(_Base_ptr __x) { return (_Link_type&)(__x->_M_right); }
00679 
00680       static _Link_type& 
00681       _S_parent(_Base_ptr __x) { return (_Link_type&)(__x->_M_parent); }
00682 
00683       static reference 
00684       _S_value(_Base_ptr __x) { return ((_Link_type)__x)->_M_value_field; }
00685 
00686       static const _Key& 
00687       _S_key(_Base_ptr __x) { return _KeyOfValue()(_S_value(_Link_type(__x)));} 
00688 
00689       static _Rb_tree_color&
00690       _S_color(_Base_ptr __x) { return (_Link_type(__x)->_M_color); }
00691 
00692       static _Link_type 
00693       _S_minimum(_Link_type __x) 
00694       { return (_Link_type)  _Rb_tree_node_base::_S_minimum(__x); }
00695 
00696       static _Link_type 
00697       _S_maximum(_Link_type __x)
00698       { return (_Link_type) _Rb_tree_node_base::_S_maximum(__x); }
00699 
00700     public:
00701       typedef _Rb_tree_iterator<value_type, reference, pointer> iterator;
00702       typedef _Rb_tree_iterator<value_type, const_reference, const_pointer> 
00703       const_iterator;
00704 
00705       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
00706       typedef std::reverse_iterator<iterator> reverse_iterator;
00707 
00708     private:
00709       iterator 
00710       _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v);
00711 
00712       _Link_type 
00713       _M_copy(_Link_type __x, _Link_type __p);
00714 
00715       void 
00716       _M_erase(_Link_type __x);
00717 
00718     public:
00719       // allocation/deallocation
00720       _Rb_tree()
00721     : _Base(allocator_type()), _M_node_count(0), _M_key_compare()
00722       { _M_empty_initialize(); }
00723 
00724       _Rb_tree(const _Compare& __comp)
00725     : _Base(allocator_type()), _M_node_count(0), _M_key_compare(__comp) 
00726       { _M_empty_initialize(); }
00727 
00728       _Rb_tree(const _Compare& __comp, const allocator_type& __a)
00729     : _Base(__a), _M_node_count(0), _M_key_compare(__comp) 
00730       { _M_empty_initialize(); }
00731 
00732       _Rb_tree(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x) 
00733     : _Base(__x.get_allocator()), _M_node_count(0), 
00734          _M_key_compare(__x._M_key_compare)
00735       { 
00736     if (__x._M_root() == 0)
00737       _M_empty_initialize();
00738     else 
00739       {
00740         _S_color(_M_header) = _M_red;
00741         _M_root() = _M_copy(__x._M_root(), _M_header);
00742         _M_leftmost() = _S_minimum(_M_root());
00743         _M_rightmost() = _S_maximum(_M_root());
00744       }
00745     _M_node_count = __x._M_node_count;
00746       }
00747 
00748       ~_Rb_tree() { clear(); }
00749 
00750       _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& 
00751       operator=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x);
00752 
00753     private:
00754       void _M_empty_initialize() 
00755       {
00756     _S_color(_M_header) = _M_red; // used to distinguish header from 
00757     // __root, in iterator.operator++
00758     _M_root() = 0;
00759     _M_leftmost() = _M_header;
00760     _M_rightmost() = _M_header;
00761       }
00762 
00763     public:    
00764       // Accessors.
00765       _Compare 
00766       key_comp() const { return _M_key_compare; }
00767 
00768       iterator 
00769       begin() { return _M_leftmost(); }
00770 
00771       const_iterator 
00772       begin() const { return _M_leftmost(); }
00773 
00774       iterator 
00775       end() { return _M_header; }
00776 
00777       const_iterator 
00778       end() const { return _M_header; }
00779 
00780       reverse_iterator 
00781       rbegin() { return reverse_iterator(end()); }
00782 
00783       const_reverse_iterator 
00784       rbegin() const { return const_reverse_iterator(end()); }
00785 
00786       reverse_iterator 
00787       rend() { return reverse_iterator(begin()); }
00788 
00789       const_reverse_iterator 
00790       rend() const { return const_reverse_iterator(begin()); }
00791  
00792       bool 
00793       empty() const { return _M_node_count == 0; }
00794 
00795       size_type 
00796       size() const { return _M_node_count; }
00797 
00798       size_type 
00799       max_size() const { return size_type(-1); }
00800 
00801       void 
00802       swap(_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __t) 
00803       {
00804     std::swap(_M_header, __t._M_header);
00805     std::swap(_M_node_count, __t._M_node_count);
00806     std::swap(_M_key_compare, __t._M_key_compare);
00807       }
00808     
00809       // Insert/erase.
00810       pair<iterator,bool> 
00811       insert_unique(const value_type& __x);
00812 
00813       iterator 
00814       insert_equal(const value_type& __x);
00815 
00816       iterator 
00817       insert_unique(iterator __position, const value_type& __x);
00818 
00819       iterator 
00820       insert_equal(iterator __position, const value_type& __x);
00821 
00822       template<typename _InputIterator>
00823       void 
00824       insert_unique(_InputIterator __first, _InputIterator __last);
00825 
00826       template<typename _InputIterator>
00827       void 
00828       insert_equal(_InputIterator __first, _InputIterator __last);
00829 
00830       void 
00831       erase(iterator __position);
00832 
00833       size_type 
00834       erase(const key_type& __x);
00835 
00836       void 
00837       erase(iterator __first, iterator __last);
00838 
00839       void 
00840       erase(const key_type* __first, const key_type* __last);
00841 
00842       void 
00843       clear() 
00844       {
00845     if (_M_node_count != 0) 
00846       {
00847         _M_erase(_M_root());
00848         _M_leftmost() = _M_header;
00849         _M_root() = 0;
00850         _M_rightmost() = _M_header;
00851         _M_node_count = 0;
00852       }
00853       }      
00854 
00855       // Set operations.
00856       iterator 
00857       find(const key_type& __x);
00858 
00859       const_iterator 
00860       find(const key_type& __x) const;
00861 
00862       size_type 
00863       count(const key_type& __x) const;
00864 
00865       iterator 
00866       lower_bound(const key_type& __x);
00867 
00868       const_iterator 
00869       lower_bound(const key_type& __x) const;
00870 
00871       iterator 
00872       upper_bound(const key_type& __x);
00873 
00874       const_iterator 
00875       upper_bound(const key_type& __x) const;
00876 
00877       pair<iterator,iterator> 
00878       equal_range(const key_type& __x);
00879 
00880       pair<const_iterator, const_iterator> 
00881       equal_range(const key_type& __x) const;
00882 
00883       // Debugging.
00884       bool 
00885       __rb_verify() const;
00886     };
00887 
00888   template<typename _Key, typename _Val, typename _KeyOfValue, 
00889            typename _Compare, typename _Alloc>
00890     inline bool 
00891     operator==(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x, 
00892            const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
00893     {
00894       return __x.size() == __y.size() && 
00895     equal(__x.begin(), __x.end(), __y.begin());
00896     }
00897 
00898   template<typename _Key, typename _Val, typename _KeyOfValue, 
00899            typename _Compare, typename _Alloc>
00900     inline bool 
00901     operator<(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x, 
00902           const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
00903     {
00904       return lexicographical_compare(__x.begin(), __x.end(),
00905                      __y.begin(), __y.end());
00906     }
00907 
00908   template<typename _Key, typename _Val, typename _KeyOfValue, 
00909            typename _Compare, typename _Alloc>
00910     inline bool 
00911     operator!=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x, 
00912            const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y) 
00913     { return !(__x == __y); }
00914 
00915   template<typename _Key, typename _Val, typename _KeyOfValue, 
00916            typename _Compare, typename _Alloc>
00917     inline bool 
00918     operator>(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x, 
00919           const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y) 
00920     { return __y < __x; }
00921 
00922   template<typename _Key, typename _Val, typename _KeyOfValue, 
00923            typename _Compare, typename _Alloc>
00924     inline bool 
00925     operator<=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x, 
00926            const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y) 
00927   { return !(__y < __x); }
00928 
00929   template<typename _Key, typename _Val, typename _KeyOfValue, 
00930            typename _Compare, typename _Alloc>
00931     inline bool 
00932     operator>=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x, 
00933            const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y) 
00934   { return !(__x < __y); }
00935 
00936   template<typename _Key, typename _Val, typename _KeyOfValue, 
00937            typename _Compare, typename _Alloc>
00938     inline void 
00939     swap(_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x, 
00940      _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
00941     { __x.swap(__y); }
00942 
00943   template<typename _Key, typename _Val, typename _KeyOfValue, 
00944            typename _Compare, typename _Alloc>
00945     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& 
00946     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
00947     operator=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x)
00948     {
00949       if (this != &__x) 
00950     {
00951       // Note that _Key may be a constant type.
00952       clear();
00953       _M_node_count = 0;
00954       _M_key_compare = __x._M_key_compare;        
00955       if (__x._M_root() == 0) 
00956         {
00957           _M_root() = 0;
00958           _M_leftmost() = _M_header;
00959           _M_rightmost() = _M_header;
00960         }
00961       else 
00962         {
00963           _M_root() = _M_copy(__x._M_root(), _M_header);
00964           _M_leftmost() = _S_minimum(_M_root());
00965           _M_rightmost() = _S_maximum(_M_root());
00966           _M_node_count = __x._M_node_count;
00967         }
00968     }
00969       return *this;
00970     }
00971 
00972   template<typename _Key, typename _Val, typename _KeyOfValue, 
00973            typename _Compare, typename _Alloc>
00974     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
00975     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
00976     _M_insert(_Base_ptr __x_, _Base_ptr __y_, const _Val& __v)
00977     {
00978       _Link_type __x = (_Link_type) __x_;
00979       _Link_type __y = (_Link_type) __y_;
00980       _Link_type __z;
00981       
00982       if (__y == _M_header || __x != 0 || 
00983       _M_key_compare(_KeyOfValue()(__v), _S_key(__y))) 
00984     {
00985       __z = _M_create_node(__v);
00986       _S_left(__y) = __z;               // also makes _M_leftmost() = __z 
00987       //    when __y == _M_header
00988       if (__y == _M_header) 
00989         {
00990           _M_root() = __z;
00991           _M_rightmost() = __z;
00992         }
00993       else if (__y == _M_leftmost())
00994         _M_leftmost() = __z; // maintain _M_leftmost() pointing to min node
00995     }
00996       else 
00997     {
00998       __z = _M_create_node(__v);
00999       _S_right(__y) = __z;
01000       // Maintain _M_rightmost() pointing to max node.
01001       if (__y == _M_rightmost())
01002         _M_rightmost() = __z; 
01003     }
01004       _S_parent(__z) = __y;
01005       _S_left(__z) = 0;
01006       _S_right(__z) = 0;
01007       _Rb_tree_rebalance(__z, _M_header->_M_parent);
01008       ++_M_node_count;
01009       return iterator(__z);
01010     }
01011 
01012   template<typename _Key, typename _Val, typename _KeyOfValue, 
01013            typename _Compare, typename _Alloc>
01014     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
01015     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
01016     insert_equal(const _Val& __v)
01017     {
01018       _Link_type __y = _M_header;
01019       _Link_type __x = _M_root();
01020       while (__x != 0) 
01021     {
01022       __y = __x;
01023       __x = _M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ? 
01024         _S_left(__x) : _S_right(__x);
01025     }
01026       return _M_insert(__x, __y, __v);
01027     }
01028 
01029   template<typename _Key, typename _Val, typename _KeyOfValue, 
01030            typename _Compare, typename _Alloc>
01031     pair<typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator, 
01032     bool>
01033     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
01034     insert_unique(const _Val& __v)
01035     {
01036       _Link_type __y = _M_header;
01037       _Link_type __x = _M_root();
01038       bool __comp = true;
01039       while (__x != 0) 
01040     {
01041       __y = __x;
01042       __comp = _M_key_compare(_KeyOfValue()(__v), _S_key(__x));
01043       __x = __comp ? _S_left(__x) : _S_right(__x);
01044     }
01045       iterator __j = iterator(__y);   
01046       if (__comp)
01047     if (__j == begin())     
01048       return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
01049     else
01050       --__j;
01051       if (_M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
01052     return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
01053       return pair<iterator,bool>(__j, false);
01054     }
01055   
01056 
01057   template<typename _Key, typename _Val, typename _KeyOfValue, 
01058            typename _Compare, typename _Alloc>
01059     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 
01060     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01061     insert_unique(iterator __position, const _Val& __v)
01062     {
01063       if (__position._M_node == _M_header->_M_left) 
01064     { 
01065       // begin()
01066       if (size() > 0 && 
01067           _M_key_compare(_KeyOfValue()(__v), _S_key(__position._M_node)))
01068         return _M_insert(__position._M_node, __position._M_node, __v);
01069       // first argument just needs to be non-null 
01070       else
01071         return insert_unique(__v).first;
01072     } 
01073       else if (__position._M_node == _M_header) 
01074     { 
01075       // end()
01076       if (_M_key_compare(_S_key(_M_rightmost()), _KeyOfValue()(__v)))
01077         return _M_insert(0, _M_rightmost(), __v);
01078       else
01079         return insert_unique(__v).first;
01080     } 
01081       else 
01082     {
01083       iterator __before = __position;
01084       --__before;
01085       if (_M_key_compare(_S_key(__before._M_node), _KeyOfValue()(__v)) 
01086           && _M_key_compare(_KeyOfValue()(__v),_S_key(__position._M_node)))
01087         {
01088           if (_S_right(__before._M_node) == 0)
01089         return _M_insert(0, __before._M_node, __v); 
01090           else
01091         return _M_insert(__position._M_node, __position._M_node, __v);
01092           // first argument just needs to be non-null 
01093         } 
01094       else
01095         return insert_unique(__v).first;
01096     }
01097     }
01098 
01099   template<typename _Key, typename _Val, typename _KeyOfValue, 
01100            typename _Compare, typename _Alloc>
01101     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator 
01102     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
01103     insert_equal(iterator __position, const _Val& __v)
01104     {
01105       if (__position._M_node == _M_header->_M_left) 
01106     { 
01107       // begin()
01108       if (size() > 0 && 
01109           !_M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__v)))
01110         return _M_insert(__position._M_node, __position._M_node, __v);
01111       // first argument just needs to be non-null 
01112       else
01113         return insert_equal(__v);
01114     } 
01115       else if (__position._M_node == _M_header) 
01116     {
01117       // end()
01118       if (!_M_key_compare(_KeyOfValue()(__v), _S_key(_M_rightmost())))
01119         return _M_insert(0, _M_rightmost(), __v);
01120       else
01121         return insert_equal(__v);
01122     } 
01123       else 
01124     {
01125       iterator __before = __position;
01126       --__before;
01127       if (!_M_key_compare(_KeyOfValue()(__v), _S_key(__before._M_node))
01128           && !_M_key_compare(_S_key(__position._M_node),
01129                  _KeyOfValue()(__v))) 
01130         {
01131           if (_S_right(__before._M_node) == 0)
01132         return _M_insert(0, __before._M_node, __v); 
01133           else
01134         return _M_insert(__position._M_node, __position._M_node, __v);
01135           // first argument just needs to be non-null 
01136         } 
01137       else
01138         return insert_equal(__v);
01139     }
01140     }
01141 
01142   template<typename _Key, typename _Val, typename _KoV, 
01143            typename _Cmp, typename _Alloc>
01144     template<class _II>
01145       void 
01146       _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>::
01147       insert_equal(_II __first, _II __last)
01148       {
01149     for ( ; __first != __last; ++__first)
01150       insert_equal(*__first);
01151       }
01152 
01153   template<typename _Key, typename _Val, typename _KoV, 
01154            typename _Cmp, typename _Alloc> 
01155     template<class _II>
01156     void 
01157     _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>::
01158     insert_unique(_II __first, _II __last) 
01159     {
01160       for ( ; __first != __last; ++__first)
01161     insert_unique(*__first);
01162     }
01163 
01164   template<typename _Key, typename _Val, typename _KeyOfValue, 
01165            typename _Compare, typename _Alloc>
01166     inline void 
01167     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::erase(iterator __position)
01168     {
01169       _Link_type __y = 
01170     (_Link_type) _Rb_tree_rebalance_for_erase(__position._M_node,
01171                           _M_header->_M_parent,
01172                           _M_header->_M_left,
01173                           _M_header->_M_right);
01174       destroy_node(__y);
01175       --_M_node_count;
01176     }
01177 
01178   template<typename _Key, typename _Val, typename _KeyOfValue, 
01179            typename _Compare, typename _Alloc>
01180     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::size_type 
01181     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::erase(const _Key& __x)
01182     {
01183       pair<iterator,iterator> __p = equal_range(__x);
01184       size_type __n = distance(__p.first, __p.second);
01185       erase(__p.first, __p.second);
01186       return __n;
01187     }
01188 
01189   template<typename _Key, typename _Val, typename _KoV, 
01190            typename _Compare, typename _Alloc>
01191     typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type 
01192     _Rb_tree<_Key,_Val,_KoV,_Compare,_Alloc>::
01193     _M_copy(_Link_type __x, _Link_type __p)
01194     {
01195       // Structural copy.  __x and __p must be non-null.
01196       _Link_type __top = _M_clone_node(__x);
01197       __top->_M_parent = __p;
01198       
01199       try 
01200     {
01201       if (__x->_M_right)
01202         __top->_M_right = _M_copy(_S_right(__x), __top);
01203       __p = __top;
01204       __x = _S_left(__x);
01205       
01206       while (__x != 0) 
01207         {
01208           _Link_type __y = _M_clone_node(__x);
01209           __p->_M_left = __y;
01210           __y->_M_parent = __p;
01211           if (__x->_M_right)
01212         __y->_M_right = _M_copy(_S_right(__x), __y);
01213           __p = __y;
01214           __x = _S_left(__x);
01215         }
01216     }
01217       catch(...)
01218     {
01219       _M_erase(__top);
01220       __throw_exception_again; 
01221     }
01222       return __top;
01223     }
01224 
01225   template<typename _Key, typename _Val, typename _KeyOfValue, 
01226            typename _Compare, typename _Alloc>
01227     void 
01228     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::_M_erase(_Link_type __x)
01229     {
01230       // Erase without rebalancing.
01231       while (__x != 0) 
01232     {
01233       _M_erase(_S_right(__x));
01234       _Link_type __y = _S_left(__x);
01235       destroy_node(__x);
01236       __x = __y;
01237     }
01238     }
01239 
01240   template<typename _Key, typename _Val, typename _KeyOfValue, 
01241            typename _Compare, typename _Alloc>
01242     void 
01243     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
01244     erase(iterator __first, iterator __last)
01245     {
01246       if (__first == begin() && __last == end())
01247     clear();
01248       else
01249     while (__first != __last) erase(__first++);
01250     }
01251 
01252   template<typename _Key, typename _Val, typename _KeyOfValue, 
01253            typename _Compare, typename _Alloc>
01254     void 
01255     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
01256     erase(const _Key* __first, const _Key* __last) 
01257     { 
01258       while (__first != __last) 
01259     erase(*__first++); 
01260     }
01261 
01262   template<typename _Key, typename _Val, typename _KeyOfValue, 
01263            typename _Compare, typename _Alloc>
01264     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator 
01265     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::find(const _Key& __k)
01266     {
01267       _Link_type __y = _M_header;  // Last node which is not less than __k. 
01268       _Link_type __x = _M_root();  // Current node. 
01269       
01270       while (__x != 0) 
01271     if (!_M_key_compare(_S_key(__x), __k))
01272       __y = __x, __x = _S_left(__x);
01273     else
01274       __x = _S_right(__x);
01275       
01276       iterator __j = iterator(__y);   
01277       return (__j == end() || _M_key_compare(__k, _S_key(__j._M_node))) ? 
01278     end() : __j;
01279     }
01280   
01281   template<typename _Key, typename _Val, typename _KeyOfValue, 
01282            typename _Compare, typename _Alloc>
01283     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::const_iterator 
01284     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
01285     find(const _Key& __k) const
01286     {
01287       _Link_type __y = _M_header; // Last node which is not less than __k. 
01288       _Link_type __x = _M_root(); // Current node. 
01289  
01290      while (__x != 0) 
01291        {
01292      if (!_M_key_compare(_S_key(__x), __k))
01293        __y = __x, __x = _S_left(__x);
01294      else
01295        __x = _S_right(__x);
01296        } 
01297      const_iterator __j = const_iterator(__y);   
01298      return (__j == end() || _M_key_compare(__k, _S_key(__j._M_node))) ?
01299        end() : __j;
01300     }
01301 
01302   template<typename _Key, typename _Val, typename _KeyOfValue, 
01303            typename _Compare, typename _Alloc>
01304     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::size_type 
01305     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
01306     count(const _Key& __k) const
01307     {
01308       pair<const_iterator, const_iterator> __p = equal_range(__k);
01309       size_type __n = distance(__p.first, __p.second);
01310       return __n;
01311     }
01312 
01313   template<typename _Key, typename _Val, typename _KeyOfValue, 
01314            typename _Compare, typename _Alloc>
01315     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator 
01316     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
01317     lower_bound(const _Key& __k)
01318     {
01319       _Link_type __y = _M_header; /* Last node which is not less than __k. */
01320       _Link_type __x = _M_root(); /* Current node. */
01321       
01322       while (__x != 0) 
01323     if (!_M_key_compare(_S_key(__x), __k))
01324       __y = __x, __x = _S_left(__x);
01325     else
01326       __x = _S_right(__x);
01327       
01328       return iterator(__y);
01329     }
01330 
01331   template<typename _Key, typename _Val, typename _KeyOfValue, 
01332            typename _Compare, typename _Alloc>
01333     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::const_iterator 
01334     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
01335     lower_bound(const _Key& __k) const
01336     {
01337       _Link_type __y = _M_header; /* Last node which is not less than __k. */
01338       _Link_type __x = _M_root(); /* Current node. */
01339       
01340       while (__x != 0) 
01341     if (!_M_key_compare(_S_key(__x), __k))
01342       __y = __x, __x = _S_left(__x);
01343     else
01344       __x = _S_right(__x);
01345       
01346       return const_iterator(__y);
01347     }
01348 
01349   template<typename _Key, typename _Val, typename _KeyOfValue, 
01350            typename _Compare, typename _Alloc>
01351     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator 
01352     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
01353     upper_bound(const _Key& __k)
01354     {
01355       _Link_type __y = _M_header; /* Last node which is greater than __k. */
01356       _Link_type __x = _M_root(); /* Current node. */
01357       
01358       while (__x != 0) 
01359     if (_M_key_compare(__k, _S_key(__x)))
01360       __y = __x, __x = _S_left(__x);
01361     else
01362       __x = _S_right(__x);
01363       
01364       return iterator(__y);
01365     }
01366 
01367   template<typename _Key, typename _Val, typename _KeyOfValue, 
01368            typename _Compare, typename _Alloc>
01369     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::const_iterator 
01370     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
01371     upper_bound(const _Key& __k) const
01372     {
01373       _Link_type __y = _M_header; /* Last node which is greater than __k. */
01374       _Link_type __x = _M_root(); /* Current node. */
01375       
01376       while (__x != 0) 
01377     if (_M_key_compare(__k, _S_key(__x)))
01378       __y = __x, __x = _S_left(__x);
01379     else
01380       __x = _S_right(__x);
01381       
01382       return const_iterator(__y);
01383     }
01384 
01385   template<typename _Key, typename _Val, typename _KeyOfValue, 
01386            typename _Compare, typename _Alloc>
01387     inline 
01388     pair<typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator,
01389                                    typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator>
01390     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
01391     equal_range(const _Key& __k)
01392     { return pair<iterator, iterator>(lower_bound(__k), upper_bound(__k)); }
01393 
01394   template<typename _Key, typename _Val, typename _KoV, 
01395            typename _Compare, typename _Alloc>
01396   inline 
01397   pair<typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::const_iterator,
01398                                 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::const_iterator>
01399   _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>
01400   ::equal_range(const _Key& __k) const
01401   {
01402     return pair<const_iterator,const_iterator>(lower_bound(__k),
01403                            upper_bound(__k));
01404   }
01405 
01406   inline int
01407   __black_count(_Rb_tree_node_base* __node, _Rb_tree_node_base* __root)
01408   {
01409     if (__node == 0)
01410       return 0;
01411     int __sum = 0;
01412     do 
01413       {
01414     if (__node->_M_color == _M_black) 
01415       ++__sum;
01416     if (__node == __root) 
01417       break;
01418     __node = __node->_M_parent;
01419       } 
01420     while (1);
01421     return __sum;
01422   }
01423 
01424   template<typename _Key, typename _Val, typename _KeyOfValue, 
01425            typename _Compare, typename _Alloc>
01426     bool 
01427     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
01428     {
01429     if (_M_node_count == 0 || begin() == end())
01430       return _M_node_count == 0 && begin() == end() &&
01431     _M_header->_M_left == _M_header && _M_header->_M_right == _M_header;
01432   
01433     int __len = __black_count(_M_leftmost(), _M_root());
01434     for (const_iterator __it = begin(); __it != end(); ++__it) 
01435       {
01436     _Link_type __x = (_Link_type) __it._M_node;
01437     _Link_type __L = _S_left(__x);
01438     _Link_type __R = _S_right(__x);
01439     
01440     if (__x->_M_color == _M_red)
01441       if ((__L && __L->_M_color == _M_red) 
01442           || (__R && __R->_M_color == _M_red))
01443         return false;
01444     
01445     if (__L && _M_key_compare(_S_key(__x), _S_key(__L)))
01446       return false;
01447     if (__R && _M_key_compare(_S_key(__R), _S_key(__x)))
01448       return false;
01449 
01450     if (!__L && !__R && __black_count(__x, _M_root()) != __len)
01451       return false;
01452       }
01453     
01454     if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
01455       return false;
01456     if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
01457       return false;
01458     return true;
01459     }
01460 } // namespace std 
01461 
01462 #endif 

Generated on Thu Feb 10 23:22:59 2005 for libstdc++-v3 Source by  doxygen 1.4.0