- Main Page
- Namespaces
- Classes
- Files
- Related Pages

# /Users/fpy/titan-1-5-MBARI/Mers/Executives/DeductiveController/Configs/TI_DSP_BIOS/stl/stl_tree.h

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