home *** CD-ROM | disk | FTP | other *** search
/ PC World 2000 November / PCWorld_2000-11_cd.bin / Software / Topware / devc40 / _SETUP.6 / Group14 / stl_tree.h < prev    next >
C/C++ Source or Header  |  2000-01-21  |  44KB  |  1,334 lines
  1. /*
  2.  *
  3.  * Copyright (c) 1996,1997
  4.  * Silicon Graphics Computer Systems, Inc.
  5.  *
  6.  * Permission to use, copy, modify, distribute and sell this software
  7.  * and its documentation for any purpose is hereby granted without fee,
  8.  * provided that the above copyright notice appear in all copies and
  9.  * that both that copyright notice and this permission notice appear
  10.  * in supporting documentation.  Silicon Graphics makes no
  11.  * representations about the suitability of this software for any
  12.  * purpose.  It is provided "as is" without express or implied warranty.
  13.  *
  14.  *
  15.  * Copyright (c) 1994
  16.  * Hewlett-Packard Company
  17.  *
  18.  * Permission to use, copy, modify, distribute and sell this software
  19.  * and its documentation for any purpose is hereby granted without fee,
  20.  * provided that the above copyright notice appear in all copies and
  21.  * that both that copyright notice and this permission notice appear
  22.  * in supporting documentation.  Hewlett-Packard Company makes no
  23.  * representations about the suitability of this software for any
  24.  * purpose.  It is provided "as is" without express or implied warranty.
  25.  *
  26.  *
  27.  */
  28.  
  29. /* NOTE: This is an internal header file, included by other STL headers.
  30.  *   You should not attempt to use it directly.
  31.  */
  32.  
  33. #ifndef __SGI_STL_INTERNAL_TREE_H
  34. #define __SGI_STL_INTERNAL_TREE_H
  35.  
  36. /*
  37.  
  38. Red-black tree class, designed for use in implementing STL
  39. associative containers (set, multiset, map, and multimap). The
  40. insertion and deletion algorithms are based on those in Cormen,
  41. Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 1990),
  42. except that
  43.  
  44. (1) the header cell is maintained with links not only to the root
  45. but also to the leftmost node of the tree, to enable constant time
  46. begin(), and to the rightmost node of the tree, to enable linear time
  47. performance when used with the generic set algorithms (set_union,
  48. etc.);
  49.  
  50. (2) when a node being deleted has two children its successor node is
  51. relinked into its place, rather than copied, so that the only
  52. iterators invalidated are those referring to the deleted node.
  53.  
  54. */
  55.  
  56. #include <stl_algobase.h>
  57. #include <stl_alloc.h>
  58. #include <stl_construct.h>
  59. #include <stl_function.h>
  60.  
  61. __STL_BEGIN_NAMESPACE 
  62.  
  63. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  64. #pragma set woff 1375
  65. #endif
  66.  
  67. typedef bool _Rb_tree_Color_type;
  68. const _Rb_tree_Color_type _S_rb_tree_red = false;
  69. const _Rb_tree_Color_type _S_rb_tree_black = true;
  70.  
  71. struct _Rb_tree_node_base
  72. {
  73.   typedef _Rb_tree_Color_type _Color_type;
  74.   typedef _Rb_tree_node_base* _Base_ptr;
  75.  
  76.   _Color_type _M_color; 
  77.   _Base_ptr _M_parent;
  78.   _Base_ptr _M_left;
  79.   _Base_ptr _M_right;
  80.  
  81.   static _Base_ptr _S_minimum(_Base_ptr __x)
  82.   {
  83.     while (__x->_M_left != 0) __x = __x->_M_left;
  84.     return __x;
  85.   }
  86.  
  87.   static _Base_ptr _S_maximum(_Base_ptr __x)
  88.   {
  89.     while (__x->_M_right != 0) __x = __x->_M_right;
  90.     return __x;
  91.   }
  92. };
  93.  
  94. template <class _Value>
  95. struct _Rb_tree_node : public _Rb_tree_node_base
  96. {
  97.   typedef _Rb_tree_node<_Value>* _Link_type;
  98.   _Value _M_value_field;
  99. };
  100.  
  101.  
  102. struct _Rb_tree_base_iterator
  103. {
  104.   typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
  105.   typedef bidirectional_iterator_tag iterator_category;
  106.   typedef ptrdiff_t difference_type;
  107.   _Base_ptr _M_node;
  108.  
  109.   void _M_increment()
  110.   {
  111.     if (_M_node->_M_right != 0) {
  112.       _M_node = _M_node->_M_right;
  113.       while (_M_node->_M_left != 0)
  114.         _M_node = _M_node->_M_left;
  115.     }
  116.     else {
  117.       _Base_ptr __y = _M_node->_M_parent;
  118.       while (_M_node == __y->_M_right) {
  119.         _M_node = __y;
  120.         __y = __y->_M_parent;
  121.       }
  122.       if (_M_node->_M_right != __y)
  123.         _M_node = __y;
  124.     }
  125.   }
  126.  
  127.   void _M_decrement()
  128.   {
  129.     if (_M_node->_M_color == _S_rb_tree_red &&
  130.         _M_node->_M_parent->_M_parent == _M_node)
  131.       _M_node = _M_node->_M_right;
  132.     else if (_M_node->_M_left != 0) {
  133.       _Base_ptr __y = _M_node->_M_left;
  134.       while (__y->_M_right != 0)
  135.         __y = __y->_M_right;
  136.       _M_node = __y;
  137.     }
  138.     else {
  139.       _Base_ptr __y = _M_node->_M_parent;
  140.       while (_M_node == __y->_M_left) {
  141.         _M_node = __y;
  142.         __y = __y->_M_parent;
  143.       }
  144.       _M_node = __y;
  145.     }
  146.   }
  147. };
  148.  
  149. template <class _Value, class _Ref, class _Ptr>
  150. struct _Rb_tree_iterator : public _Rb_tree_base_iterator
  151. {
  152.   typedef _Value value_type;
  153.   typedef _Ref reference;
  154.   typedef _Ptr pointer;
  155.   typedef _Rb_tree_iterator<_Value, _Value&, _Value*>             
  156.     iterator;
  157.   typedef _Rb_tree_iterator<_Value, const _Value&, const _Value*> 
  158.     const_iterator;
  159.   typedef _Rb_tree_iterator<_Value, _Ref, _Ptr>                   
  160.     _Self;
  161.   typedef _Rb_tree_node<_Value>* _Link_type;
  162.  
  163.   _Rb_tree_iterator() {}
  164.   _Rb_tree_iterator(_Link_type __x) { _M_node = __x; }
  165.   _Rb_tree_iterator(const iterator& __it) { _M_node = __it._M_node; }
  166.  
  167.   reference operator*() const { return _Link_type(_M_node)->_M_value_field; }
  168. #ifndef __SGI_STL_NO_ARROW_OPERATOR
  169.   pointer operator->() const { return &(operator*()); }
  170. #endif /* __SGI_STL_NO_ARROW_OPERATOR */
  171.  
  172.   _Self& operator++() { _M_increment(); return *this; }
  173.   _Self operator++(int) {
  174.     _Self __tmp = *this;
  175.     _M_increment();
  176.     return __tmp;
  177.   }
  178.     
  179.   _Self& operator--() { _M_decrement(); return *this; }
  180.   _Self operator--(int) {
  181.     _Self __tmp = *this;
  182.     _M_decrement();
  183.     return __tmp;
  184.   }
  185. };
  186.  
  187. inline bool operator==(const _Rb_tree_base_iterator& __x,
  188.                        const _Rb_tree_base_iterator& __y) {
  189.   return __x._M_node == __y._M_node;
  190. }
  191.  
  192. inline bool operator!=(const _Rb_tree_base_iterator& __x,
  193.                        const _Rb_tree_base_iterator& __y) {
  194.   return __x._M_node != __y._M_node;
  195. }
  196.  
  197. #ifndef __STL_CLASS_PARTIAL_SPECIALIZATION
  198.  
  199. inline bidirectional_iterator_tag
  200. iterator_category(const _Rb_tree_base_iterator&) {
  201.   return bidirectional_iterator_tag();
  202. }
  203.  
  204. inline _Rb_tree_base_iterator::difference_type*
  205. distance_type(const _Rb_tree_base_iterator&) {
  206.   return (_Rb_tree_base_iterator::difference_type*) 0;
  207. }
  208.  
  209. template <class _Value, class _Ref, class _Ptr>
  210. inline _Value* value_type(const _Rb_tree_iterator<_Value, _Ref, _Ptr>&) {
  211.   return (_Value*) 0;
  212. }
  213.  
  214. #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  215.  
  216. inline void 
  217. _Rb_tree_rotate_left(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root)
  218. {
  219.   _Rb_tree_node_base* __y = __x->_M_right;
  220.   __x->_M_right = __y->_M_left;
  221.   if (__y->_M_left !=0)
  222.     __y->_M_left->_M_parent = __x;
  223.   __y->_M_parent = __x->_M_parent;
  224.  
  225.   if (__x == __root)
  226.     __root = __y;
  227.   else if (__x == __x->_M_parent->_M_left)
  228.     __x->_M_parent->_M_left = __y;
  229.   else
  230.     __x->_M_parent->_M_right = __y;
  231.   __y->_M_left = __x;
  232.   __x->_M_parent = __y;
  233. }
  234.  
  235. inline void 
  236. _Rb_tree_rotate_right(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root)
  237. {
  238.   _Rb_tree_node_base* __y = __x->_M_left;
  239.   __x->_M_left = __y->_M_right;
  240.   if (__y->_M_right != 0)
  241.     __y->_M_right->_M_parent = __x;
  242.   __y->_M_parent = __x->_M_parent;
  243.  
  244.   if (__x == __root)
  245.     __root = __y;
  246.   else if (__x == __x->_M_parent->_M_right)
  247.     __x->_M_parent->_M_right = __y;
  248.   else
  249.     __x->_M_parent->_M_left = __y;
  250.   __y->_M_right = __x;
  251.   __x->_M_parent = __y;
  252. }
  253.  
  254. inline void 
  255. _Rb_tree_rebalance(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root)
  256. {
  257.   __x->_M_color = _S_rb_tree_red;
  258.   while (__x != __root && __x->_M_parent->_M_color == _S_rb_tree_red) {
  259.     if (__x->_M_parent == __x->_M_parent->_M_parent->_M_left) {
  260.       _Rb_tree_node_base* __y = __x->_M_parent->_M_parent->_M_right;
  261.       if (__y && __y->_M_color == _S_rb_tree_red) {
  262.         __x->_M_parent->_M_color = _S_rb_tree_black;
  263.         __y->_M_color = _S_rb_tree_black;
  264.         __x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
  265.         __x = __x->_M_parent->_M_parent;
  266.       }
  267.       else {
  268.         if (__x == __x->_M_parent->_M_right) {
  269.           __x = __x->_M_parent;
  270.           _Rb_tree_rotate_left(__x, __root);
  271.         }
  272.         __x->_M_parent->_M_color = _S_rb_tree_black;
  273.         __x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
  274.         _Rb_tree_rotate_right(__x->_M_parent->_M_parent, __root);
  275.       }
  276.     }
  277.     else {
  278.       _Rb_tree_node_base* __y = __x->_M_parent->_M_parent->_M_left;
  279.       if (__y && __y->_M_color == _S_rb_tree_red) {
  280.         __x->_M_parent->_M_color = _S_rb_tree_black;
  281.         __y->_M_color = _S_rb_tree_black;
  282.         __x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
  283.         __x = __x->_M_parent->_M_parent;
  284.       }
  285.       else {
  286.         if (__x == __x->_M_parent->_M_left) {
  287.           __x = __x->_M_parent;
  288.           _Rb_tree_rotate_right(__x, __root);
  289.         }
  290.         __x->_M_parent->_M_color = _S_rb_tree_black;
  291.         __x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
  292.         _Rb_tree_rotate_left(__x->_M_parent->_M_parent, __root);
  293.       }
  294.     }
  295.   }
  296.   __root->_M_color = _S_rb_tree_black;
  297. }
  298.  
  299. inline _Rb_tree_node_base*
  300. _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* __z,
  301.                              _Rb_tree_node_base*& __root,
  302.                              _Rb_tree_node_base*& __leftmost,
  303.                              _Rb_tree_node_base*& __rightmost)
  304. {
  305.   _Rb_tree_node_base* __y = __z;
  306.   _Rb_tree_node_base* __x = 0;
  307.   _Rb_tree_node_base* __x_parent = 0;
  308.   if (__y->_M_left == 0)     // __z has at most one non-null child. y == z.
  309.     __x = __y->_M_right;     // __x might be null.
  310.   else
  311.     if (__y->_M_right == 0)  // __z has exactly one non-null child. y == z.
  312.       __x = __y->_M_left;    // __x is not null.
  313.     else {                   // __z has two non-null children.  Set __y to
  314.       __y = __y->_M_right;   //   __z's successor.  __x might be null.
  315.       while (__y->_M_left != 0)
  316.         __y = __y->_M_left;
  317.       __x = __y->_M_right;
  318.     }
  319.   if (__y != __z) {          // relink y in place of z.  y is z's successor
  320.     __z->_M_left->_M_parent = __y; 
  321.     __y->_M_left = __z->_M_left;
  322.     if (__y != __z->_M_right) {
  323.       __x_parent = __y->_M_parent;
  324.       if (__x) __x->_M_parent = __y->_M_parent;
  325.       __y->_M_parent->_M_left = __x;      // __y must be a child of _M_left
  326.       __y->_M_right = __z->_M_right;
  327.       __z->_M_right->_M_parent = __y;
  328.     }
  329.     else
  330.       __x_parent = __y;  
  331.     if (__root == __z)
  332.       __root = __y;
  333.     else if (__z->_M_parent->_M_left == __z)
  334.       __z->_M_parent->_M_left = __y;
  335.     else 
  336.       __z->_M_parent->_M_right = __y;
  337.     __y->_M_parent = __z->_M_parent;
  338.     __STD::swap(__y->_M_color, __z->_M_color);
  339.     __y = __z;
  340.     // __y now points to node to be actually deleted
  341.   }
  342.   else {                        // __y == __z
  343.     __x_parent = __y->_M_parent;
  344.     if (__x) __x->_M_parent = __y->_M_parent;   
  345.     if (__root == __z)
  346.       __root = __x;
  347.     else 
  348.       if (__z->_M_parent->_M_left == __z)
  349.         __z->_M_parent->_M_left = __x;
  350.       else
  351.         __z->_M_parent->_M_right = __x;
  352.     if (__leftmost == __z) 
  353.       if (__z->_M_right == 0)        // __z->_M_left must be null also
  354.         __leftmost = __z->_M_parent;
  355.     // makes __leftmost == _M_header if __z == __root
  356.       else
  357.         __leftmost = _Rb_tree_node_base::_S_minimum(__x);
  358.     if (__rightmost == __z)  
  359.       if (__z->_M_left == 0)         // __z->_M_right must be null also
  360.         __rightmost = __z->_M_parent;  
  361.     // makes __rightmost == _M_header if __z == __root
  362.       else                      // __x == __z->_M_left
  363.         __rightmost = _Rb_tree_node_base::_S_maximum(__x);
  364.   }
  365.   if (__y->_M_color != _S_rb_tree_red) { 
  366.     while (__x != __root && (__x == 0 || __x->_M_color == _S_rb_tree_black))
  367.       if (__x == __x_parent->_M_left) {
  368.         _Rb_tree_node_base* __w = __x_parent->_M_right;
  369.         if (__w->_M_color == _S_rb_tree_red) {
  370.           __w->_M_color = _S_rb_tree_black;
  371.           __x_parent->_M_color = _S_rb_tree_red;
  372.           _Rb_tree_rotate_left(__x_parent, __root);
  373.           __w = __x_parent->_M_right;
  374.         }
  375.         if ((__w->_M_left == 0 || 
  376.              __w->_M_left->_M_color == _S_rb_tree_black) &&
  377.             (__w->_M_right == 0 || 
  378.              __w->_M_right->_M_color == _S_rb_tree_black)) {
  379.           __w->_M_color = _S_rb_tree_red;
  380.           __x = __x_parent;
  381.           __x_parent = __x_parent->_M_parent;
  382.         } else {
  383.           if (__w->_M_right == 0 || 
  384.               __w->_M_right->_M_color == _S_rb_tree_black) {
  385.             if (__w->_M_left) __w->_M_left->_M_color = _S_rb_tree_black;
  386.             __w->_M_color = _S_rb_tree_red;
  387.             _Rb_tree_rotate_right(__w, __root);
  388.             __w = __x_parent->_M_right;
  389.           }
  390.           __w->_M_color = __x_parent->_M_color;
  391.           __x_parent->_M_color = _S_rb_tree_black;
  392.           if (__w->_M_right) __w->_M_right->_M_color = _S_rb_tree_black;
  393.           _Rb_tree_rotate_left(__x_parent, __root);
  394.           break;
  395.         }
  396.       } else {                  // same as above, with _M_right <-> _M_left.
  397.         _Rb_tree_node_base* __w = __x_parent->_M_left;
  398.         if (__w->_M_color == _S_rb_tree_red) {
  399.           __w->_M_color = _S_rb_tree_black;
  400.           __x_parent->_M_color = _S_rb_tree_red;
  401.           _Rb_tree_rotate_right(__x_parent, __root);
  402.           __w = __x_parent->_M_left;
  403.         }
  404.         if ((__w->_M_right == 0 || 
  405.              __w->_M_right->_M_color == _S_rb_tree_black) &&
  406.             (__w->_M_left == 0 || 
  407.              __w->_M_left->_M_color == _S_rb_tree_black)) {
  408.           __w->_M_color = _S_rb_tree_red;
  409.           __x = __x_parent;
  410.           __x_parent = __x_parent->_M_parent;
  411.         } else {
  412.           if (__w->_M_left == 0 || 
  413.               __w->_M_left->_M_color == _S_rb_tree_black) {
  414.             if (__w->_M_right) __w->_M_right->_M_color = _S_rb_tree_black;
  415.             __w->_M_color = _S_rb_tree_red;
  416.             _Rb_tree_rotate_left(__w, __root);
  417.             __w = __x_parent->_M_left;
  418.           }
  419.           __w->_M_color = __x_parent->_M_color;
  420.           __x_parent->_M_color = _S_rb_tree_black;
  421.           if (__w->_M_left) __w->_M_left->_M_color = _S_rb_tree_black;
  422.           _Rb_tree_rotate_right(__x_parent, __root);
  423.           break;
  424.         }
  425.       }
  426.     if (__x) __x->_M_color = _S_rb_tree_black;
  427.   }
  428.   return __y;
  429. }
  430.  
  431. // Base class to encapsulate the differences between old SGI-style
  432. // allocators and standard-conforming allocators.  In order to avoid
  433. // having an empty base class, we arbitrarily move one of rb_tree's
  434. // data members into the base class.
  435.  
  436. #ifdef __STL_USE_STD_ALLOCATORS
  437.  
  438. // _Base for general standard-conforming allocators.
  439. template <class _Tp, class _Alloc, bool _S_instanceless>
  440. class _Rb_tree_alloc_base {
  441. public:
  442.   typedef typename _Alloc_traits<_Tp, _Alloc>::allocator_type allocator_type;
  443.   allocator_type get_allocator() const { return _M_node_allocator; }
  444.  
  445.   _Rb_tree_alloc_base(const allocator_type& __a)
  446.     : _M_node_allocator(__a), _M_header(0) {}
  447.  
  448. protected:
  449.   typename _Alloc_traits<_Rb_tree_node<_Tp>, _Alloc>::allocator_type
  450.            _M_node_allocator;
  451.   _Rb_tree_node<_Tp>* _M_header;
  452.  
  453.   _Rb_tree_node<_Tp>* _M_get_node() 
  454.     { return _M_node_allocator.allocate(1); }
  455.   void _M_put_node(_Rb_tree_node<_Tp>* __p) 
  456.     { _M_node_allocator.deallocate(__p, 1); }
  457. };
  458.  
  459. // Specialization for instanceless allocators.
  460. template <class _Tp, class _Alloc>
  461. class _Rb_tree_alloc_base<_Tp, _Alloc, true> {
  462. public:
  463.   typedef typename _Alloc_traits<_Tp, _Alloc>::allocator_type allocator_type;
  464.   allocator_type get_allocator() const { return allocator_type(); }
  465.  
  466.   _Rb_tree_alloc_base(const allocator_type&) : _M_header(0) {}
  467.  
  468. protected:
  469.   _Rb_tree_node<_Tp>* _M_header;
  470.  
  471.   typedef typename _Alloc_traits<_Rb_tree_node<_Tp>, _Alloc>::_Alloc_type
  472.           _Alloc_type;
  473.  
  474.   _Rb_tree_node<_Tp>* _M_get_node()
  475.     { return _Alloc_type::allocate(1); }
  476.   void _M_put_node(_Rb_tree_node<_Tp>* __p)
  477.     { _Alloc_type::deallocate(__p, 1); }
  478. };
  479.  
  480. template <class _Tp, class _Alloc>
  481. struct _Rb_tree_base
  482.   : public _Rb_tree_alloc_base<_Tp, _Alloc,
  483.                                _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
  484. {
  485.   typedef _Rb_tree_alloc_base<_Tp, _Alloc,
  486.                               _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
  487.           _Base;
  488.   typedef typename _Base::allocator_type allocator_type;
  489.  
  490.   _Rb_tree_base(const allocator_type& __a) 
  491.     : _Base(__a) { _M_header = _M_get_node(); }
  492.   ~_Rb_tree_base() { _M_put_node(_M_header); }
  493.  
  494. };
  495.  
  496. #else /* __STL_USE_STD_ALLOCATORS */
  497.  
  498. template <class _Tp, class _Alloc>
  499. struct _Rb_tree_base
  500. {
  501.   typedef _Alloc allocator_type;
  502.   allocator_type get_allocator() const { return allocator_type(); }
  503.  
  504.   _Rb_tree_base(const allocator_type&) 
  505.     : _M_header(0) { _M_header = _M_get_node(); }
  506.   ~_Rb_tree_base() { _M_put_node(_M_header); }
  507.  
  508. protected:
  509.   _Rb_tree_node<_Tp>* _M_header;
  510.  
  511.   typedef simple_alloc<_Rb_tree_node<_Tp>, _Alloc> _Alloc_type;
  512.  
  513.   _Rb_tree_node<_Tp>* _M_get_node()
  514.     { return _Alloc_type::allocate(1); }
  515.   void _M_put_node(_Rb_tree_node<_Tp>* __p)
  516.     { _Alloc_type::deallocate(__p, 1); }
  517. };
  518.  
  519. #endif /* __STL_USE_STD_ALLOCATORS */
  520.  
  521. template <class _Key, class _Value, class _KeyOfValue, class _Compare,
  522.           class _Alloc = __STL_DEFAULT_ALLOCATOR(_Value) >
  523. class _Rb_tree : protected _Rb_tree_base<_Value, _Alloc> {
  524.   typedef _Rb_tree_base<_Value, _Alloc> _Base;
  525. protected:
  526.   typedef _Rb_tree_node_base* _Base_ptr;
  527.   typedef _Rb_tree_node<_Value> _Rb_tree_node;
  528.   typedef _Rb_tree_Color_type _Color_type;
  529. public:
  530.   typedef _Key key_type;
  531.   typedef _Value value_type;
  532.   typedef value_type* pointer;
  533.   typedef const value_type* const_pointer;
  534.   typedef value_type& reference;
  535.   typedef const value_type& const_reference;
  536.   typedef _Rb_tree_node* _Link_type;
  537.   typedef size_t size_type;
  538.   typedef ptrdiff_t difference_type;
  539.  
  540.   typedef typename _Base::allocator_type allocator_type;
  541.   allocator_type get_allocator() const { return _Base::get_allocator(); }
  542.  
  543. protected:
  544. #ifdef __STL_USE_NAMESPACES
  545.   using _Base::_M_get_node;
  546.   using _Base::_M_put_node;
  547.   using _Base::_M_header;
  548. #endif /* __STL_USE_NAMESPACES */
  549.  
  550. protected:
  551.  
  552.   _Link_type _M_create_node(const value_type& __x)
  553.   {
  554.     _Link_type __tmp = _M_get_node();
  555.     __STL_TRY {
  556.       construct(&__tmp->_M_value_field, __x);
  557.     }
  558.     __STL_UNWIND(_M_put_node(__tmp));
  559.     return __tmp;
  560.   }
  561.  
  562.   _Link_type _M_clone_node(_Link_type __x)
  563.   {
  564.     _Link_type __tmp = _M_create_node(__x->_M_value_field);
  565.     __tmp->_M_color = __x->_M_color;
  566.     __tmp->_M_left = 0;
  567.     __tmp->_M_right = 0;
  568.     return __tmp;
  569.   }
  570.  
  571.   void destroy_node(_Link_type __p)
  572.   {
  573.     destroy(&__p->_M_value_field);
  574.     _M_put_node(__p);
  575.   }
  576.  
  577. protected:
  578.   size_type _M_node_count; // keeps track of size of tree
  579.   _Compare _M_key_compare;
  580.  
  581.   _Link_type& _M_root() const 
  582.     { return (_Link_type&) _M_header->_M_parent; }
  583.   _Link_type& _M_leftmost() const 
  584.     { return (_Link_type&) _M_header->_M_left; }
  585.   _Link_type& _M_rightmost() const 
  586.     { return (_Link_type&) _M_header->_M_right; }
  587.  
  588.   static _Link_type& _S_left(_Link_type __x)
  589.     { return (_Link_type&)(__x->_M_left); }
  590.   static _Link_type& _S_right(_Link_type __x)
  591.     { return (_Link_type&)(__x->_M_right); }
  592.   static _Link_type& _S_parent(_Link_type __x)
  593.     { return (_Link_type&)(__x->_M_parent); }
  594.   static reference _S_value(_Link_type __x)
  595.     { return __x->_M_value_field; }
  596.   static const _Key& _S_key(_Link_type __x)
  597.     { return _KeyOfValue()(_S_value(__x)); }
  598.   static _Color_type& _S_color(_Link_type __x)
  599.     { return (_Color_type&)(__x->_M_color); }
  600.  
  601.   static _Link_type& _S_left(_Base_ptr __x)
  602.     { return (_Link_type&)(__x->_M_left); }
  603.   static _Link_type& _S_right(_Base_ptr __x)
  604.     { return (_Link_type&)(__x->_M_right); }
  605.   static _Link_type& _S_parent(_Base_ptr __x)
  606.     { return (_Link_type&)(__x->_M_parent); }
  607.   static reference _S_value(_Base_ptr __x)
  608.     { return ((_Link_type)__x)->_M_value_field; }
  609.   static const _Key& _S_key(_Base_ptr __x)
  610.     { return _KeyOfValue()(_S_value(_Link_type(__x)));} 
  611.   static _Color_type& _S_color(_Base_ptr __x)
  612.     { return (_Color_type&)(_Link_type(__x)->_M_color); }
  613.  
  614.   static _Link_type _S_minimum(_Link_type __x) 
  615.     { return (_Link_type)  _Rb_tree_node_base::_S_minimum(__x); }
  616.  
  617.   static _Link_type _S_maximum(_Link_type __x)
  618.     { return (_Link_type) _Rb_tree_node_base::_S_maximum(__x); }
  619.  
  620. public:
  621.   typedef _Rb_tree_iterator<value_type, reference, pointer> iterator;
  622.   typedef _Rb_tree_iterator<value_type, const_reference, const_pointer> 
  623.           const_iterator;
  624.  
  625. #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
  626.   typedef reverse_iterator<const_iterator> const_reverse_iterator;
  627.   typedef reverse_iterator<iterator> reverse_iterator;
  628. #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  629.   typedef reverse_bidirectional_iterator<iterator, value_type, reference,
  630.                                          difference_type>
  631.           reverse_iterator; 
  632.   typedef reverse_bidirectional_iterator<const_iterator, value_type,
  633.                                          const_reference, difference_type>
  634.           const_reverse_iterator;
  635. #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ 
  636.  
  637. private:
  638.   iterator _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v);
  639.   _Link_type _M_copy(_Link_type __x, _Link_type __p);
  640.   void _M_erase(_Link_type __x);
  641.  
  642. public:
  643.                                 // allocation/deallocation
  644.   _Rb_tree()
  645.     : _Base(allocator_type()), _M_node_count(0), _M_key_compare()
  646.     { _M_empty_initialize(); }
  647.  
  648.   _Rb_tree(const _Compare& __comp)
  649.     : _Base(allocator_type()), _M_node_count(0), _M_key_compare(__comp) 
  650.     { _M_empty_initialize(); }
  651.  
  652.   _Rb_tree(const _Compare& __comp, const allocator_type& __a)
  653.     : _Base(__a), _M_node_count(0), _M_key_compare(__comp) 
  654.     { _M_empty_initialize(); }
  655.  
  656.   _Rb_tree(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x) 
  657.     : _Base(__x.get_allocator()),
  658.       _M_node_count(0), _M_key_compare(__x._M_key_compare)
  659.   { 
  660.     if (__x._M_root() == 0)
  661.       _M_empty_initialize();
  662.     else {
  663.       _S_color(_M_header) = _S_rb_tree_red;
  664.       _M_root() = _M_copy(__x._M_root(), _M_header);
  665.       _M_leftmost() = _S_minimum(_M_root());
  666.       _M_rightmost() = _S_maximum(_M_root());
  667.     }
  668.     _M_node_count = __x._M_node_count;
  669.   }
  670.   ~_Rb_tree() { clear(); }
  671.   _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& 
  672.   operator=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x);
  673.  
  674. private:
  675.   void _M_empty_initialize() {
  676.     _S_color(_M_header) = _S_rb_tree_red; // used to distinguish header from 
  677.                                           // __root, in iterator.operator++
  678.     _M_root() = 0;
  679.     _M_leftmost() = _M_header;
  680.     _M_rightmost() = _M_header;
  681.   }
  682.  
  683. public:    
  684.                                 // accessors:
  685.   _Compare key_comp() const { return _M_key_compare; }
  686.   iterator begin() { return _M_leftmost(); }
  687.   const_iterator begin() const { return _M_leftmost(); }
  688.   iterator end() { return _M_header; }
  689.   const_iterator end() const { return _M_header; }
  690.   reverse_iterator rbegin() { return reverse_iterator(end()); }
  691.   const_reverse_iterator rbegin() const { 
  692.     return const_reverse_iterator(end()); 
  693.   }
  694.   reverse_iterator rend() { return reverse_iterator(begin()); }
  695.   const_reverse_iterator rend() const { 
  696.     return const_reverse_iterator(begin());
  697.   } 
  698.   bool empty() const { return _M_node_count == 0; }
  699.   size_type size() const { return _M_node_count; }
  700.   size_type max_size() const { return size_type(-1); }
  701.  
  702.   void swap(_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __t) {
  703.     __STD::swap(_M_header, __t._M_header);
  704.     __STD::swap(_M_node_count, __t._M_node_count);
  705.     __STD::swap(_M_key_compare, __t._M_key_compare);
  706.   }
  707.     
  708. public:
  709.                                 // insert/erase
  710.   pair<iterator,bool> insert_unique(const value_type& __x);
  711.   iterator insert_equal(const value_type& __x);
  712.  
  713.   iterator insert_unique(iterator __position, const value_type& __x);
  714.   iterator insert_equal(iterator __position, const value_type& __x);
  715.  
  716. #ifdef __STL_MEMBER_TEMPLATES  
  717.   template <class _InputIterator>
  718.   void insert_unique(_InputIterator __first, _InputIterator __last);
  719.   template <class _InputIterator>
  720.   void insert_equal(_InputIterator __first, _InputIterator __last);
  721. #else /* __STL_MEMBER_TEMPLATES */
  722.   void insert_unique(const_iterator __first, const_iterator __last);
  723.   void insert_unique(const value_type* __first, const value_type* __last);
  724.   void insert_equal(const_iterator __first, const_iterator __last);
  725.   void insert_equal(const value_type* __first, const value_type* __last);
  726. #endif /* __STL_MEMBER_TEMPLATES */
  727.  
  728.   void erase(iterator __position);
  729.   size_type erase(const key_type& __x);
  730.   void erase(iterator __first, iterator __last);
  731.   void erase(const key_type* __first, const key_type* __last);
  732.   void clear() {
  733.     if (_M_node_count != 0) {
  734.       _M_erase(_M_root());
  735.       _M_leftmost() = _M_header;
  736.       _M_root() = 0;
  737.       _M_rightmost() = _M_header;
  738.       _M_node_count = 0;
  739.     }
  740.   }      
  741.  
  742. public:
  743.                                 // set operations:
  744.   iterator find(const key_type& __x);
  745.   const_iterator find(const key_type& __x) const;
  746.   size_type count(const key_type& __x) const;
  747.   iterator lower_bound(const key_type& __x);
  748.   const_iterator lower_bound(const key_type& __x) const;
  749.   iterator upper_bound(const key_type& __x);
  750.   const_iterator upper_bound(const key_type& __x) const;
  751.   pair<iterator,iterator> equal_range(const key_type& __x);
  752.   pair<const_iterator, const_iterator> equal_range(const key_type& __x) const;
  753.  
  754. public:
  755.                                 // Debugging.
  756.   bool __rb_verify() const;
  757. };
  758.  
  759. template <class _Key, class _Value, class _KeyOfValue, 
  760.           class _Compare, class _Alloc>
  761. inline bool 
  762. operator==(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x, 
  763.            const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y)
  764. {
  765.   return __x.size() == __y.size() &&
  766.          equal(__x.begin(), __x.end(), __y.begin());
  767. }
  768.  
  769. template <class _Key, class _Value, class _KeyOfValue, 
  770.           class _Compare, class _Alloc>
  771. inline bool 
  772. operator<(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x, 
  773.           const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y)
  774. {
  775.   return lexicographical_compare(__x.begin(), __x.end(), 
  776.                                  __y.begin(), __y.end());
  777. }
  778.  
  779. #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
  780.  
  781. template <class _Key, class _Value, class _KeyOfValue, 
  782.           class _Compare, class _Alloc>
  783. inline void 
  784. swap(_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x, 
  785.      _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y)
  786. {
  787.   __x.swap(__y);
  788. }
  789.  
  790. #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
  791.  
  792.  
  793. template <class _Key, class _Value, class _KeyOfValue, 
  794.           class _Compare, class _Alloc>
  795. _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& 
  796. _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
  797.   ::operator=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x)
  798. {
  799.   if (this != &__x) {
  800.                                 // Note that _Key may be a constant type.
  801.     clear();
  802.     _M_node_count = 0;
  803.     _M_key_compare = __x._M_key_compare;        
  804.     if (__x._M_root() == 0) {
  805.       _M_root() = 0;
  806.       _M_leftmost() = _M_header;
  807.       _M_rightmost() = _M_header;
  808.     }
  809.     else {
  810.       _M_root() = _M_copy(__x._M_root(), _M_header);
  811.       _M_leftmost() = _S_minimum(_M_root());
  812.       _M_rightmost() = _S_maximum(_M_root());
  813.       _M_node_count = __x._M_node_count;
  814.     }
  815.   }
  816.   return *this;
  817. }
  818.  
  819. template <class _Key, class _Value, class _KeyOfValue, 
  820.           class _Compare, class _Alloc>
  821. typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator
  822. _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
  823.   ::_M_insert(_Base_ptr __x_, _Base_ptr __y_, const _Value& __v)
  824. {
  825.   _Link_type __x = (_Link_type) __x_;
  826.   _Link_type __y = (_Link_type) __y_;
  827.   _Link_type __z;
  828.  
  829.   if (__y == _M_header || __x != 0 || 
  830.       _M_key_compare(_KeyOfValue()(__v), _S_key(__y))) {
  831.     __z = _M_create_node(__v);
  832.     _S_left(__y) = __z;               // also makes _M_leftmost() = __z 
  833.                                       //    when __y == _M_header
  834.     if (__y == _M_header) {
  835.       _M_root() = __z;
  836.       _M_rightmost() = __z;
  837.     }
  838.     else if (__y == _M_leftmost())
  839.       _M_leftmost() = __z;   // maintain _M_leftmost() pointing to min node
  840.   }
  841.   else {
  842.     __z = _M_create_node(__v);
  843.     _S_right(__y) = __z;
  844.     if (__y == _M_rightmost())
  845.       _M_rightmost() = __z;  // maintain _M_rightmost() pointing to max node
  846.   }
  847.   _S_parent(__z) = __y;
  848.   _S_left(__z) = 0;
  849.   _S_right(__z) = 0;
  850.   _Rb_tree_rebalance(__z, _M_header->_M_parent);
  851.   ++_M_node_count;
  852.   return iterator(__z);
  853. }
  854.  
  855. template <class _Key, class _Value, class _KeyOfValue, 
  856.           class _Compare, class _Alloc>
  857. typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator
  858. _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
  859.   ::insert_equal(const _Value& __v)
  860. {
  861.   _Link_type __y = _M_header;
  862.   _Link_type __x = _M_root();
  863.   while (__x != 0) {
  864.     __y = __x;
  865.     __x = _M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ? 
  866.             _S_left(__x) : _S_right(__x);
  867.   }
  868.   return _M_insert(__x, __y, __v);
  869. }
  870.  
  871.  
  872. template <class _Key, class _Value, class _KeyOfValue, 
  873.           class _Compare, class _Alloc>
  874. pair<typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator, 
  875.      bool>
  876. _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
  877.   ::insert_unique(const _Value& __v)
  878. {
  879.   _Link_type __y = _M_header;
  880.   _Link_type __x = _M_root();
  881.   bool __comp = true;
  882.   while (__x != 0) {
  883.     __y = __x;
  884.     __comp = _M_key_compare(_KeyOfValue()(__v), _S_key(__x));
  885.     __x = __comp ? _S_left(__x) : _S_right(__x);
  886.   }
  887.   iterator __j = iterator(__y);   
  888.   if (__comp)
  889.     if (__j == begin())     
  890.       return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
  891.     else
  892.       --__j;
  893.   if (_M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
  894.     return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
  895.   return pair<iterator,bool>(__j, false);
  896. }
  897.  
  898.  
  899. template <class _Key, class _Val, class _KeyOfValue, 
  900.           class _Compare, class _Alloc>
  901. typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 
  902. _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>
  903.   ::insert_unique(iterator __position, const _Val& __v)
  904. {
  905.   if (__position._M_node == _M_header->_M_left) { // begin()
  906.     if (size() > 0 && 
  907.         _M_key_compare(_KeyOfValue()(__v), _S_key(__position._M_node)))
  908.       return _M_insert(__position._M_node, __position._M_node, __v);
  909.     // first argument just needs to be non-null 
  910.     else
  911.       return insert_unique(__v).first;
  912.   } else if (__position._M_node == _M_header) { // end()
  913.     if (_M_key_compare(_S_key(_M_rightmost()), _KeyOfValue()(__v)))
  914.       return _M_insert(0, _M_rightmost(), __v);
  915.     else
  916.       return insert_unique(__v).first;
  917.   } else {
  918.     iterator __before = __position;
  919.     --__before;
  920.     if (_M_key_compare(_S_key(__before._M_node), _KeyOfValue()(__v)) 
  921.         && _M_key_compare(_KeyOfValue()(__v), _S_key(__position._M_node))) {
  922.       if (_S_right(__before._M_node) == 0)
  923.         return _M_insert(0, __before._M_node, __v); 
  924.       else
  925.         return _M_insert(__position._M_node, __position._M_node, __v);
  926.     // first argument just needs to be non-null 
  927.     } else
  928.       return insert_unique(__v).first;
  929.   }
  930. }
  931.  
  932. template <class _Key, class _Val, class _KeyOfValue, 
  933.           class _Compare, class _Alloc>
  934. typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator 
  935. _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>
  936.   ::insert_equal(iterator __position, const _Val& __v)
  937. {
  938.   if (__position._M_node == _M_header->_M_left) { // begin()
  939.     if (size() > 0 && 
  940.         _M_key_compare(_KeyOfValue()(__v), _S_key(__position._M_node)))
  941.       return _M_insert(__position._M_node, __position._M_node, __v);
  942.     // first argument just needs to be non-null 
  943.     else
  944.       return insert_equal(__v);
  945.   } else if (__position._M_node == _M_header) {// end()
  946.     if (!_M_key_compare(_KeyOfValue()(__v), _S_key(_M_rightmost())))
  947.       return _M_insert(0, _M_rightmost(), __v);
  948.     else
  949.       return insert_equal(__v);
  950.   } else {
  951.     iterator __before = __position;
  952.     --__before;
  953.     if (!_M_key_compare(_KeyOfValue()(__v), _S_key(__before._M_node))
  954.         && !_M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__v))) {
  955.       if (_S_right(__before._M_node) == 0)
  956.         return _M_insert(0, __before._M_node, __v); 
  957.       else
  958.         return _M_insert(__position._M_node, __position._M_node, __v);
  959.     // first argument just needs to be non-null 
  960.     } else
  961.       return insert_equal(__v);
  962.   }
  963. }
  964.  
  965. #ifdef __STL_MEMBER_TEMPLATES  
  966.  
  967. template <class _Key, class _Val, class _KoV, class _Cmp, class _Alloc>
  968.   template<class _II>
  969. void _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>
  970.   ::insert_equal(_II __first, _II __last)
  971. {
  972.   for ( ; __first != __last; ++__first)
  973.     insert_equal(*__first);
  974. }
  975.  
  976. template <class _Key, class _Val, class _KoV, class _Cmp, class _Alloc> 
  977.   template<class _II>
  978. void _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>
  979.   ::insert_unique(_II __first, _II __last) {
  980.   for ( ; __first != __last; ++__first)
  981.     insert_unique(*__first);
  982. }
  983.  
  984. #else /* __STL_MEMBER_TEMPLATES */
  985.  
  986. template <class _Key, class _Val, class _KoV, class _Cmp, class _Alloc>
  987. void
  988. _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>
  989.   ::insert_equal(const _Val* __first, const _Val* __last)
  990. {
  991.   for ( ; __first != __last; ++__first)
  992.     insert_equal(*__first);
  993. }
  994.  
  995. template <class _Key, class _Val, class _KoV, class _Cmp, class _Alloc>
  996. void
  997. _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>
  998.   ::insert_equal(const_iterator __first, const_iterator __last)
  999. {
  1000.   for ( ; __first != __last; ++__first)
  1001.     insert_equal(*__first);
  1002. }
  1003.  
  1004. template <class _Key, class _Val, class _KoV, class _Cmp, class _Alloc>
  1005. void 
  1006. _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>
  1007.   ::insert_unique(const _Val* __first, const _Val* __last)
  1008. {
  1009.   for ( ; __first != __last; ++__first)
  1010.     insert_unique(*__first);
  1011. }
  1012.  
  1013. template <class _Key, class _Val, class _KoV, class _Cmp, class _Alloc>
  1014. void _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>
  1015.   ::insert_unique(const_iterator __first, const_iterator __last)
  1016. {
  1017.   for ( ; __first != __last; ++__first)
  1018.     insert_unique(*__first);
  1019. }
  1020.  
  1021. #endif /* __STL_MEMBER_TEMPLATES */
  1022.          
  1023. template <class _Key, class _Value, class _KeyOfValue, 
  1024.           class _Compare, class _Alloc>
  1025. inline void _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
  1026.   ::erase(iterator __position)
  1027. {
  1028.   _Link_type __y = 
  1029.     (_Link_type) _Rb_tree_rebalance_for_erase(__position._M_node,
  1030.                                               _M_header->_M_parent,
  1031.                                               _M_header->_M_left,
  1032.                                               _M_header->_M_right);
  1033.   destroy_node(__y);
  1034.   --_M_node_count;
  1035. }
  1036.  
  1037. template <class _Key, class _Value, class _KeyOfValue, 
  1038.           class _Compare, class _Alloc>
  1039. typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::size_type 
  1040. _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::erase(const _Key& __x)
  1041. {
  1042.   pair<iterator,iterator> __p = equal_range(__x);
  1043.   size_type __n = 0;
  1044.   distance(__p.first, __p.second, __n);
  1045.   erase(__p.first, __p.second);
  1046.   return __n;
  1047. }
  1048.  
  1049. template <class _Key, class _Val, class _KoV, class _Compare, class _Alloc>
  1050. typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type 
  1051. _Rb_tree<_Key,_Val,_KoV,_Compare,_Alloc>
  1052.   ::_M_copy(_Link_type __x, _Link_type __p)
  1053. {
  1054.                         // structural copy.  __x and __p must be non-null.
  1055.   _Link_type __top = _M_clone_node(__x);
  1056.   __top->_M_parent = __p;
  1057.  
  1058.   __STL_TRY {
  1059.     if (__x->_M_right)
  1060.       __top->_M_right = _M_copy(_S_right(__x), __top);
  1061.     __p = __top;
  1062.     __x = _S_left(__x);
  1063.  
  1064.     while (__x != 0) {
  1065.       _Link_type __y = _M_clone_node(__x);
  1066.       __p->_M_left = __y;
  1067.       __y->_M_parent = __p;
  1068.       if (__x->_M_right)
  1069.         __y->_M_right = _M_copy(_S_right(__x), __y);
  1070.       __p = __y;
  1071.       __x = _S_left(__x);
  1072.     }
  1073.   }
  1074.   __STL_UNWIND(_M_erase(__top));
  1075.  
  1076.   return __top;
  1077. }
  1078.  
  1079. template <class _Key, class _Value, class _KeyOfValue, 
  1080.           class _Compare, class _Alloc>
  1081. void _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
  1082.   ::_M_erase(_Link_type __x)
  1083. {
  1084.                                 // erase without rebalancing
  1085.   while (__x != 0) {
  1086.     _M_erase(_S_right(__x));
  1087.     _Link_type __y = _S_left(__x);
  1088.     destroy_node(__x);
  1089.     __x = __y;
  1090.   }
  1091. }
  1092.  
  1093. template <class _Key, class _Value, class _KeyOfValue, 
  1094.           class _Compare, class _Alloc>
  1095. void _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
  1096.   ::erase(iterator __first, iterator __last)
  1097. {
  1098.   if (__first == begin() && __last == end())
  1099.     clear();
  1100.   else
  1101.     while (__first != __last) erase(__first++);
  1102. }
  1103.  
  1104. template <class _Key, class _Value, class _KeyOfValue, 
  1105.           class _Compare, class _Alloc>
  1106. void _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
  1107.   ::erase(const _Key* __first, const _Key* __last) 
  1108. {
  1109.   while (__first != __last) erase(*__first++);
  1110. }
  1111.  
  1112. template <class _Key, class _Value, class _KeyOfValue, 
  1113.           class _Compare, class _Alloc>
  1114. typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator 
  1115. _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::find(const _Key& __k)
  1116. {
  1117.   _Link_type __y = _M_header;      // Last node which is not less than __k. 
  1118.   _Link_type __x = _M_root();      // Current node. 
  1119.  
  1120.   while (__x != 0) 
  1121.     if (!_M_key_compare(_S_key(__x), __k))
  1122.       __y = __x, __x = _S_left(__x);
  1123.     else
  1124.       __x = _S_right(__x);
  1125.  
  1126.   iterator __j = iterator(__y);   
  1127.   return (__j == end() || _M_key_compare(__k, _S_key(__j._M_node))) ? 
  1128.      end() : __j;
  1129. }
  1130.  
  1131. template <class _Key, class _Value, class _KeyOfValue, 
  1132.           class _Compare, class _Alloc>
  1133. typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::const_iterator 
  1134. _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::find(const _Key& __k) const
  1135. {
  1136.   _Link_type __y = _M_header; /* Last node which is not less than __k. */
  1137.   _Link_type __x = _M_root(); /* Current node. */
  1138.  
  1139.   while (__x != 0) {
  1140.     if (!_M_key_compare(_S_key(__x), __k))
  1141.       __y = __x, __x = _S_left(__x);
  1142.     else
  1143.       __x = _S_right(__x);
  1144.   }
  1145.   const_iterator __j = const_iterator(__y);   
  1146.   return (__j == end() || _M_key_compare(__k, _S_key(__j._M_node))) ?
  1147.     end() : __j;
  1148. }
  1149.  
  1150. template <class _Key, class _Value, class _KeyOfValue, 
  1151.           class _Compare, class _Alloc>
  1152. typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::size_type 
  1153. _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
  1154.   ::count(const _Key& __k) const
  1155. {
  1156.   pair<const_iterator, const_iterator> __p = equal_range(__k);
  1157.   size_type __n = 0;
  1158.   distance(__p.first, __p.second, __n);
  1159.   return __n;
  1160. }
  1161.  
  1162. template <class _Key, class _Value, class _KeyOfValue, 
  1163.           class _Compare, class _Alloc>
  1164. typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator 
  1165. _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
  1166.   ::lower_bound(const _Key& __k)
  1167. {
  1168.   _Link_type __y = _M_header; /* Last node which is not less than __k. */
  1169.   _Link_type __x = _M_root(); /* Current node. */
  1170.  
  1171.   while (__x != 0) 
  1172.     if (!_M_key_compare(_S_key(__x), __k))
  1173.       __y = __x, __x = _S_left(__x);
  1174.     else
  1175.       __x = _S_right(__x);
  1176.  
  1177.   return iterator(__y);
  1178. }
  1179.  
  1180. template <class _Key, class _Value, class _KeyOfValue, 
  1181.           class _Compare, class _Alloc>
  1182. typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::const_iterator 
  1183. _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
  1184.   ::lower_bound(const _Key& __k) const
  1185. {
  1186.   _Link_type __y = _M_header; /* Last node which is not less than __k. */
  1187.   _Link_type __x = _M_root(); /* Current node. */
  1188.  
  1189.   while (__x != 0) 
  1190.     if (!_M_key_compare(_S_key(__x), __k))
  1191.       __y = __x, __x = _S_left(__x);
  1192.     else
  1193.       __x = _S_right(__x);
  1194.  
  1195.   return const_iterator(__y);
  1196. }
  1197.  
  1198. template <class _Key, class _Value, class _KeyOfValue, 
  1199.           class _Compare, class _Alloc>
  1200. typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator 
  1201. _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
  1202.   ::upper_bound(const _Key& __k)
  1203. {
  1204.   _Link_type __y = _M_header; /* Last node which is greater than __k. */
  1205.   _Link_type __x = _M_root(); /* Current node. */
  1206.  
  1207.    while (__x != 0) 
  1208.      if (_M_key_compare(__k, _S_key(__x)))
  1209.        __y = __x, __x = _S_left(__x);
  1210.      else
  1211.        __x = _S_right(__x);
  1212.  
  1213.    return iterator(__y);
  1214. }
  1215.  
  1216. template <class _Key, class _Value, class _KeyOfValue, 
  1217.           class _Compare, class _Alloc>
  1218. typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::const_iterator 
  1219. _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
  1220.   ::upper_bound(const _Key& __k) const
  1221. {
  1222.   _Link_type __y = _M_header; /* Last node which is greater than __k. */
  1223.   _Link_type __x = _M_root(); /* Current node. */
  1224.  
  1225.    while (__x != 0) 
  1226.      if (_M_key_compare(__k, _S_key(__x)))
  1227.        __y = __x, __x = _S_left(__x);
  1228.      else
  1229.        __x = _S_right(__x);
  1230.  
  1231.    return const_iterator(__y);
  1232. }
  1233.  
  1234. template <class _Key, class _Value, class _KeyOfValue, 
  1235.           class _Compare, class _Alloc>
  1236. inline 
  1237. pair<typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator,
  1238.      typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator>
  1239. _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
  1240.   ::equal_range(const _Key& __k)
  1241. {
  1242.   return pair<iterator, iterator>(lower_bound(__k), upper_bound(__k));
  1243. }
  1244.  
  1245. template <class _Key, class _Value, class _KoV, class _Compare, class _Alloc>
  1246. inline 
  1247. pair<typename _Rb_tree<_Key, _Value, _KoV, _Compare, _Alloc>::const_iterator,
  1248.      typename _Rb_tree<_Key, _Value, _KoV, _Compare, _Alloc>::const_iterator>
  1249. _Rb_tree<_Key, _Value, _KoV, _Compare, _Alloc>
  1250.   ::equal_range(const _Key& __k) const
  1251. {
  1252.   return pair<const_iterator,const_iterator>(lower_bound(__k),
  1253.                                              upper_bound(__k));
  1254. }
  1255.  
  1256. inline int 
  1257. __black_count(_Rb_tree_node_base* __node, _Rb_tree_node_base* __root)
  1258. {
  1259.   if (__node == 0)
  1260.     return 0;
  1261.   else {
  1262.     int __bc = __node->_M_color == _S_rb_tree_black ? 1 : 0;
  1263.     if (__node == __root)
  1264.       return __bc;
  1265.     else
  1266.       return __bc + __black_count(__node->_M_parent, __root);
  1267.   }
  1268. }
  1269.  
  1270. template <class _Key, class _Value, class _KeyOfValue, 
  1271.           class _Compare, class _Alloc>
  1272. bool _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
  1273. {
  1274.   if (_M_node_count == 0 || begin() == end())
  1275.     return _M_node_count == 0 && begin() == end() &&
  1276.       _M_header->_M_left == _M_header && _M_header->_M_right == _M_header;
  1277.   
  1278.   int __len = __black_count(_M_leftmost(), _M_root());
  1279.   for (const_iterator __it = begin(); __it != end(); ++__it) {
  1280.     _Link_type __x = (_Link_type) __it._M_node;
  1281.     _Link_type __L = _S_left(__x);
  1282.     _Link_type __R = _S_right(__x);
  1283.  
  1284.     if (__x->_M_color == _S_rb_tree_red)
  1285.       if ((__L && __L->_M_color == _S_rb_tree_red) ||
  1286.           (__R && __R->_M_color == _S_rb_tree_red))
  1287.         return false;
  1288.  
  1289.     if (__L && _M_key_compare(_S_key(__x), _S_key(__L)))
  1290.       return false;
  1291.     if (__R && _M_key_compare(_S_key(__R), _S_key(__x)))
  1292.       return false;
  1293.  
  1294.     if (!__L && !__R && __black_count(__x, _M_root()) != __len)
  1295.       return false;
  1296.   }
  1297.  
  1298.   if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
  1299.     return false;
  1300.   if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
  1301.     return false;
  1302.  
  1303.   return true;
  1304. }
  1305.  
  1306. // Class rb_tree is not part of the C++ standard.  It is provided for
  1307. // compatibility with the HP STL.
  1308.  
  1309. template <class _Key, class _Value, class _KeyOfValue, class _Compare,
  1310.           class _Alloc = __STL_DEFAULT_ALLOCATOR(_Value) >
  1311. struct rb_tree : public _Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc>
  1312. {
  1313.   typedef _Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc> _Base;
  1314.   typedef typename _Base::allocator_type allocator_type;
  1315.  
  1316.   rb_tree(const _Compare& __comp = _Compare(),
  1317.           const allocator_type& __a = allocator_type())
  1318.     : _Base(__comp, __a) {}
  1319.   
  1320.   ~rb_tree() {}
  1321. };
  1322.  
  1323. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  1324. #pragma reset woff 1375
  1325. #endif
  1326.  
  1327. __STL_END_NAMESPACE 
  1328.  
  1329. #endif /* __SGI_STL_INTERNAL_TREE_H */
  1330.  
  1331. // Local Variables:
  1332. // mode:C++
  1333. // End:
  1334.