home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / stlpt453.zip / STLport-4.5.3 / stlport / stl / _tree.c < prev    next >
C/C++ Source or Header  |  2002-02-02  |  25KB  |  715 lines
  1. /*
  2.  *
  3.  *
  4.  * Copyright (c) 1994
  5.  * Hewlett-Packard Company
  6.  *
  7.  * Copyright (c) 1996,1997
  8.  * Silicon Graphics Computer Systems, Inc.
  9.  *
  10.  * Copyright (c) 1997
  11.  * Moscow Center for SPARC Technology
  12.  *
  13.  * Copyright (c) 1999 
  14.  * Boris Fomitchev
  15.  *
  16.  * This material is provided "as is", with absolutely no warranty expressed
  17.  * or implied. Any use is at your own risk.
  18.  *
  19.  * Permission to use or copy this software for any purpose is hereby granted 
  20.  * without fee, provided the above notices are retained on all copies.
  21.  * Permission to modify the code and to distribute modified code is granted,
  22.  * provided the above notices are retained, and a notice that the code was
  23.  * modified is included with the above copyright notice.
  24.  *
  25.  * Modified CRP 7/10/00 for improved conformance / efficiency on insert_unique /
  26.  * insert_equal with valid hint -- efficiency is improved all around, and it is
  27.  * should now be standard conforming for complexity on insert point immediately
  28.  * after hint (amortized constant time).
  29.  *
  30.  */
  31. #ifndef _STLP_TREE_C
  32. #define _STLP_TREE_C
  33.  
  34. #ifndef _STLP_INTERNAL_TREE_H
  35. # include <stl/_tree.h>
  36. #endif
  37.  
  38. // fbp: these defines are for outline methods definitions.
  39. // needed for definitions to be portable. Should not be used in method bodies.
  40. # if defined  ( _STLP_NESTED_TYPE_PARAM_BUG )
  41. #  define __iterator__        _Rb_tree_iterator<_Value, _Nonconst_traits<_Value> > #  define __size_type__       size_t
  42. #  define iterator __iterator__
  43. # else
  44. #  define __iterator__  _STLP_TYPENAME_ON_RETURN_TYPE _Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc>::iterator
  45. #  define __size_type__  _STLP_TYPENAME_ON_RETURN_TYPE _Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc>::size_type
  46. # endif
  47.  
  48. #if defined ( _STLP_DEBUG)
  49. #  define _Rb_tree __WORKAROUND_DBG_RENAME(Rb_tree)
  50. #endif
  51.  
  52. _STLP_BEGIN_NAMESPACE
  53.  
  54. # if defined (_STLP_EXPOSE_GLOBALS_IMPLEMENTATION)
  55.  
  56. template <class _Dummy> void _STLP_CALL
  57. _Rb_global<_Dummy>::_Rotate_left(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root)
  58. {
  59.   _Rb_tree_node_base* __y = __x->_M_right;
  60.   __x->_M_right = __y->_M_left;
  61.   if (__y->_M_left !=0)
  62.     __y->_M_left->_M_parent = __x;
  63.   __y->_M_parent = __x->_M_parent;
  64.  
  65.   if (__x == __root)
  66.     __root = __y;
  67.   else if (__x == __x->_M_parent->_M_left)
  68.     __x->_M_parent->_M_left = __y;
  69.   else
  70.     __x->_M_parent->_M_right = __y;
  71.   __y->_M_left = __x;
  72.   __x->_M_parent = __y;
  73. }
  74.  
  75. template <class _Dummy> void _STLP_CALL 
  76. _Rb_global<_Dummy>::_Rotate_right(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root)
  77. {
  78.   _Rb_tree_node_base* __y = __x->_M_left;
  79.   __x->_M_left = __y->_M_right;
  80.   if (__y->_M_right != 0)
  81.     __y->_M_right->_M_parent = __x;
  82.   __y->_M_parent = __x->_M_parent;
  83.  
  84.   if (__x == __root)
  85.     __root = __y;
  86.   else if (__x == __x->_M_parent->_M_right)
  87.     __x->_M_parent->_M_right = __y;
  88.   else
  89.     __x->_M_parent->_M_left = __y;
  90.   __y->_M_right = __x;
  91.   __x->_M_parent = __y;
  92. }
  93.  
  94. template <class _Dummy> void _STLP_CALL
  95. _Rb_global<_Dummy>::_Rebalance(_Rb_tree_node_base* __x, 
  96.                    _Rb_tree_node_base*& __root)
  97. {
  98.   __x->_M_color = _S_rb_tree_red;
  99.   while (__x != __root && __x->_M_parent->_M_color == _S_rb_tree_red) {
  100.     if (__x->_M_parent == __x->_M_parent->_M_parent->_M_left) {
  101.       _Rb_tree_node_base* __y = __x->_M_parent->_M_parent->_M_right;
  102.       if (__y && __y->_M_color == _S_rb_tree_red) {
  103.         __x->_M_parent->_M_color = _S_rb_tree_black;
  104.         __y->_M_color = _S_rb_tree_black;
  105.         __x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
  106.         __x = __x->_M_parent->_M_parent;
  107.       }
  108.       else {
  109.         if (__x == __x->_M_parent->_M_right) {
  110.           __x = __x->_M_parent;
  111.           _Rotate_left(__x, __root);
  112.         }
  113.         __x->_M_parent->_M_color = _S_rb_tree_black;
  114.         __x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
  115.         _Rotate_right(__x->_M_parent->_M_parent, __root);
  116.       }
  117.     }
  118.     else {
  119.       _Rb_tree_node_base* __y = __x->_M_parent->_M_parent->_M_left;
  120.       if (__y && __y->_M_color == _S_rb_tree_red) {
  121.         __x->_M_parent->_M_color = _S_rb_tree_black;
  122.         __y->_M_color = _S_rb_tree_black;
  123.         __x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
  124.         __x = __x->_M_parent->_M_parent;
  125.       }
  126.       else {
  127.         if (__x == __x->_M_parent->_M_left) {
  128.           __x = __x->_M_parent;
  129.           _Rotate_right(__x, __root);
  130.         }
  131.         __x->_M_parent->_M_color = _S_rb_tree_black;
  132.         __x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
  133.         _Rotate_left(__x->_M_parent->_M_parent, __root);
  134.       }
  135.     }
  136.   }
  137.   __root->_M_color = _S_rb_tree_black;
  138. }
  139.  
  140. template <class _Dummy> _Rb_tree_node_base* _STLP_CALL
  141. _Rb_global<_Dummy>::_Rebalance_for_erase(_Rb_tree_node_base* __z,
  142.                      _Rb_tree_node_base*& __root,
  143.                      _Rb_tree_node_base*& __leftmost,
  144.                      _Rb_tree_node_base*& __rightmost)
  145. {
  146.   _Rb_tree_node_base* __y = __z;
  147.   _Rb_tree_node_base* __x = 0;
  148.   _Rb_tree_node_base* __x_parent = 0;
  149.   if (__y->_M_left == 0)     // __z has at most one non-null child. y == z.
  150.     __x = __y->_M_right;     // __x might be null.
  151.   else
  152.     if (__y->_M_right == 0)  // __z has exactly one non-null child. y == z.
  153.       __x = __y->_M_left;    // __x is not null.
  154.     else {                   // __z has two non-null children.  Set __y to
  155.       __y = __y->_M_right;   //   __z's successor.  __x might be null.
  156.       while (__y->_M_left != 0)
  157.         __y = __y->_M_left;
  158.       __x = __y->_M_right;
  159.     }
  160.   if (__y != __z) {          // relink y in place of z.  y is z's successor
  161.     __z->_M_left->_M_parent = __y; 
  162.     __y->_M_left = __z->_M_left;
  163.     if (__y != __z->_M_right) {
  164.       __x_parent = __y->_M_parent;
  165.       if (__x) __x->_M_parent = __y->_M_parent;
  166.       __y->_M_parent->_M_left = __x;      // __y must be a child of _M_left
  167.       __y->_M_right = __z->_M_right;
  168.       __z->_M_right->_M_parent = __y;
  169.     }
  170.     else
  171.       __x_parent = __y;  
  172.     if (__root == __z)
  173.       __root = __y;
  174.     else if (__z->_M_parent->_M_left == __z)
  175.       __z->_M_parent->_M_left = __y;
  176.     else 
  177.       __z->_M_parent->_M_right = __y;
  178.     __y->_M_parent = __z->_M_parent;
  179.     _STLP_STD::swap(__y->_M_color, __z->_M_color);
  180.     __y = __z;
  181.     // __y now points to node to be actually deleted
  182.   }
  183.   else {                        // __y == __z
  184.     __x_parent = __y->_M_parent;
  185.     if (__x) __x->_M_parent = __y->_M_parent;   
  186.     if (__root == __z)
  187.       __root = __x;
  188.     else 
  189.       if (__z->_M_parent->_M_left == __z)
  190.         __z->_M_parent->_M_left = __x;
  191.       else
  192.         __z->_M_parent->_M_right = __x;
  193.     if (__leftmost == __z) 
  194.       if (__z->_M_right == 0)        // __z->_M_left must be null also
  195.         __leftmost = __z->_M_parent;
  196.     // makes __leftmost == _M_header if __z == __root
  197.       else
  198.         __leftmost = _Rb_tree_node_base::_S_minimum(__x);
  199.     if (__rightmost == __z)  
  200.       if (__z->_M_left == 0)         // __z->_M_right must be null also
  201.         __rightmost = __z->_M_parent;  
  202.     // makes __rightmost == _M_header if __z == __root
  203.       else                      // __x == __z->_M_left
  204.         __rightmost = _Rb_tree_node_base::_S_maximum(__x);
  205.   }
  206.   if (__y->_M_color != _S_rb_tree_red) { 
  207.     while (__x != __root && (__x == 0 || __x->_M_color == _S_rb_tree_black))
  208.       if (__x == __x_parent->_M_left) {
  209.         _Rb_tree_node_base* __w = __x_parent->_M_right;
  210.         if (__w->_M_color == _S_rb_tree_red) {
  211.           __w->_M_color = _S_rb_tree_black;
  212.           __x_parent->_M_color = _S_rb_tree_red;
  213.           _Rotate_left(__x_parent, __root);
  214.           __w = __x_parent->_M_right;
  215.         }
  216.         if ((__w->_M_left == 0 || 
  217.              __w->_M_left->_M_color == _S_rb_tree_black) && (__w->_M_right == 0 || 
  218.              __w->_M_right->_M_color == _S_rb_tree_black)) {
  219.           __w->_M_color = _S_rb_tree_red;
  220.           __x = __x_parent;
  221.           __x_parent = __x_parent->_M_parent;
  222.         } else {
  223.           if (__w->_M_right == 0 || 
  224.               __w->_M_right->_M_color == _S_rb_tree_black) {
  225.             if (__w->_M_left) __w->_M_left->_M_color = _S_rb_tree_black;
  226.             __w->_M_color = _S_rb_tree_red;
  227.             _Rotate_right(__w, __root);
  228.             __w = __x_parent->_M_right;
  229.           }
  230.           __w->_M_color = __x_parent->_M_color;
  231.           __x_parent->_M_color = _S_rb_tree_black;
  232.           if (__w->_M_right) __w->_M_right->_M_color = _S_rb_tree_black;
  233.           _Rotate_left(__x_parent, __root);
  234.           break;
  235.         }
  236.       } else {                  // same as above, with _M_right <-> _M_left.
  237.         _Rb_tree_node_base* __w = __x_parent->_M_left;
  238.         if (__w->_M_color == _S_rb_tree_red) {
  239.           __w->_M_color = _S_rb_tree_black;
  240.           __x_parent->_M_color = _S_rb_tree_red;
  241.           _Rotate_right(__x_parent, __root);
  242.           __w = __x_parent->_M_left;
  243.         }
  244.         if ((__w->_M_right == 0 || 
  245.              __w->_M_right->_M_color == _S_rb_tree_black) && (__w->_M_left == 0 || 
  246.              __w->_M_left->_M_color == _S_rb_tree_black)) {
  247.           __w->_M_color = _S_rb_tree_red;
  248.           __x = __x_parent;
  249.           __x_parent = __x_parent->_M_parent;
  250.         } else {
  251.           if (__w->_M_left == 0 || 
  252.               __w->_M_left->_M_color == _S_rb_tree_black) {
  253.             if (__w->_M_right) __w->_M_right->_M_color = _S_rb_tree_black;
  254.             __w->_M_color = _S_rb_tree_red;
  255.             _Rotate_left(__w, __root);
  256.             __w = __x_parent->_M_left;
  257.           }
  258.           __w->_M_color = __x_parent->_M_color;
  259.           __x_parent->_M_color = _S_rb_tree_black;
  260.           if (__w->_M_left) __w->_M_left->_M_color = _S_rb_tree_black;
  261.           _Rotate_right(__x_parent, __root);
  262.           break;
  263.         }
  264.       }
  265.     if (__x) __x->_M_color = _S_rb_tree_black;
  266.   }
  267.   return __y;
  268. }
  269.  
  270. template <class _Dummy> _Rb_tree_node_base* _STLP_CALL
  271. _Rb_global<_Dummy>::_M_decrement(_Rb_tree_node_base* _M_node)
  272. {
  273.   if (_M_node->_M_color == _S_rb_tree_red && _M_node->_M_parent->_M_parent == _M_node)
  274.     _M_node = _M_node->_M_right;
  275.   else if (_M_node->_M_left != 0) {
  276.     _Base_ptr __y = _M_node->_M_left;
  277.     while (__y->_M_right != 0)
  278.       __y = __y->_M_right;
  279.     _M_node = __y;
  280.   }
  281.   else {
  282.     _Base_ptr __y = _M_node->_M_parent;
  283.     while (_M_node == __y->_M_left) {
  284.       _M_node = __y;
  285.       __y = __y->_M_parent;
  286.     }
  287.     _M_node = __y;
  288.   }
  289.   return _M_node;
  290. }
  291.  
  292. template <class _Dummy> _Rb_tree_node_base* _STLP_CALL
  293. _Rb_global<_Dummy>::_M_increment(_Rb_tree_node_base* _M_node)
  294. {
  295.   if (_M_node->_M_right != 0) {
  296.     _M_node = _M_node->_M_right;
  297.     while (_M_node->_M_left != 0)
  298.       _M_node = _M_node->_M_left;
  299.   }
  300.   else {
  301.     _Base_ptr __y = _M_node->_M_parent;
  302.     while (_M_node == __y->_M_right) {
  303.       _M_node = __y;
  304.       __y = __y->_M_parent;
  305.     }
  306.     if (_M_node->_M_right != __y)
  307.       _M_node = __y;
  308.   }
  309.   return _M_node;
  310. }
  311.  
  312. #endif /* defined (__BUILDING_STLPORT) || ! defined (_STLP_OWN_IOSTREAMS) */
  313.  
  314.  
  315. template <class _Key, class _Value, class _KeyOfValue, 
  316.           class _Compare, class _Alloc> _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> ::operator=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x)
  317. {
  318.   if (this != &__x) {
  319.                                 // Note that _Key may be a constant type.
  320.     clear();
  321.     _M_node_count = 0;
  322.     _M_key_compare = __x._M_key_compare;        
  323.     if (__x._M_root() == 0) {
  324.       _M_root() = 0;
  325.       _M_leftmost() = this->_M_header._M_data;
  326.       _M_rightmost() = this->_M_header._M_data;
  327.     }
  328.     else {
  329.       _M_root() = _M_copy(__x._M_root(), this->_M_header._M_data);
  330.       _M_leftmost() = _S_minimum(_M_root());
  331.       _M_rightmost() = _S_maximum(_M_root());
  332.       _M_node_count = __x._M_node_count;
  333.     }
  334.   }
  335.   return *this;
  336. }
  337.  
  338. // CRP 7/10/00 inserted argument __w_, which is another hint (meant to
  339. // act like __x_ and ignore a portion of the if conditions -- specify
  340. // __w_ != 0 to bypass comparison as false or __x_ != 0 to bypass
  341. // comparison as true)
  342. template <class _Key, class _Value, class _KeyOfValue, 
  343.           class _Compare, class _Alloc> __iterator__ 
  344. _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> ::_M_insert(_Rb_tree_node_base* __x_, _Rb_tree_node_base* __y_, const _Value& __v,
  345.   _Rb_tree_node_base* __w_)
  346. {
  347.   _Link_type __w = (_Link_type) __w_;
  348.   _Link_type __x = (_Link_type) __x_;
  349.   _Link_type __y = (_Link_type) __y_;
  350.   _Link_type __z;
  351.  
  352.   if ( __y == this->_M_header._M_data ||
  353.        ( __w == 0 && // If w != 0, the remainder fails to false
  354.          ( __x != 0 ||     // If x != 0, the remainder succeeds to true
  355.            _M_key_compare( _KeyOfValue()(__v), _S_key(__y) ) )
  356.      )
  357.        ) {
  358.     
  359.     __z = _M_create_node(__v);
  360.     _S_left(__y) = __z;               // also makes _M_leftmost() = __z 
  361.                                       //    when __y == _M_header
  362.     if (__y == this->_M_header._M_data) {
  363.       _M_root() = __z;
  364.       _M_rightmost() = __z;
  365.     }
  366.     else if (__y == _M_leftmost())
  367.       _M_leftmost() = __z;   // maintain _M_leftmost() pointing to min node
  368.   }
  369.   else {
  370.     __z = _M_create_node(__v);
  371.     _S_right(__y) = __z;
  372.     if (__y == _M_rightmost())
  373.       _M_rightmost() = __z;  // maintain _M_rightmost() pointing to max node
  374.   }
  375.   _S_parent(__z) = __y;
  376.   _S_left(__z) = 0;
  377.   _S_right(__z) = 0;
  378.   _Rb_global_inst::_Rebalance(__z, this->_M_header._M_data->_M_parent);
  379.   ++_M_node_count;
  380.   return iterator(__z);
  381. }
  382.  
  383. template <class _Key, class _Value, class _KeyOfValue, 
  384.           class _Compare, class _Alloc> __iterator__
  385. _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> ::insert_equal(const _Value& __v)
  386. {
  387.   _Link_type __y = this->_M_header._M_data;
  388.   _Link_type __x = _M_root();
  389.   while (__x != 0) {
  390.     __y = __x;
  391.     __x = _M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ? 
  392.             _S_left(__x) : _S_right(__x);
  393.   }
  394.   return _M_insert(__x, __y, __v);
  395. }
  396.  
  397.  
  398. template <class _Key, class _Value, class _KeyOfValue, 
  399.           class _Compare, class _Alloc> pair< _Rb_tree_iterator<_Value, _Nonconst_traits<_Value> >, bool> _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> ::insert_unique(const _Value& __v)
  400. {
  401.   _Link_type __y = this->_M_header._M_data;
  402.   _Link_type __x = _M_root();
  403.   bool __comp = true;
  404.   while (__x != 0) {
  405.     __y = __x;
  406.     __comp = _M_key_compare(_KeyOfValue()(__v), _S_key(__x));
  407.     __x = __comp ? _S_left(__x) : _S_right(__x);
  408.   }
  409.   iterator __j = iterator(__y);   
  410.   if (__comp)
  411.     if (__j == begin())     
  412.       return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
  413.     else
  414.       --__j;
  415.   if (_M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
  416.     return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
  417.   return pair<iterator,bool>(__j, false);
  418. }
  419.  
  420. // Modifications CRP 7/10/00 as noted to improve conformance and
  421. // efficiency.
  422. template <class _Key, class _Value, class _KeyOfValue, 
  423.           class _Compare, class _Alloc> __iterator__ 
  424. _Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc> ::insert_unique(iterator __position, const _Value& __v)
  425. {
  426.   if (__position._M_node == this->_M_header._M_data->_M_left) { // begin()
  427.  
  428.     // if the container is empty, fall back on insert_unique.
  429.     if (size() <= 0)
  430.       return insert_unique(__v).first;
  431.  
  432.     if ( _M_key_compare(_KeyOfValue()(__v), _S_key(__position._M_node)))
  433.       return _M_insert(__position._M_node, __position._M_node, __v);
  434.     // first argument just needs to be non-null 
  435.     else
  436.       {
  437.     bool __comp_pos_v = _M_key_compare( _S_key(__position._M_node), _KeyOfValue()(__v) );
  438.     
  439.     if (__comp_pos_v == false)  // compare > and compare < both false so compare equal
  440.       return __position;
  441.     //Below __comp_pos_v == true
  442.  
  443.     // Standard-conformance - does the insertion point fall immediately AFTER
  444.     // the hint?
  445.     iterator __after = __position;
  446.     ++__after;
  447.  
  448.     // Check for only one member -- in that case, __position points to itself,
  449.     // and attempting to increment will cause an infinite loop.
  450.     if (__after._M_node == this->_M_header._M_data)
  451.       // Check guarantees exactly one member, so comparison was already
  452.       // performed and we know the result; skip repeating it in _M_insert
  453.       // by specifying a non-zero fourth argument.
  454.       return _M_insert(0, __position._M_node, __v, __position._M_node);
  455.         
  456.     
  457.     // All other cases:
  458.     
  459.     // Optimization to catch insert-equivalent -- save comparison results,
  460.     // and we get this for free.
  461.     if(_M_key_compare( _KeyOfValue()(__v), _S_key(__after._M_node) )) {
  462.       if (_S_right(__position._M_node) == 0)
  463.         return _M_insert(0, __position._M_node, __v, __position._M_node);
  464.       else
  465.         return _M_insert(__after._M_node, __after._M_node, __v);
  466.     } else {
  467.         return insert_unique(__v).first;
  468.     }
  469.       }
  470.  
  471.   } else if (__position._M_node == this->_M_header._M_data) { // end()
  472.     if (_M_key_compare(_S_key(_M_rightmost()), _KeyOfValue()(__v)))
  473.       // pass along to _M_insert that it can skip comparing
  474.       // v, Key ; since compare Key, v was true, compare v, Key must be false.
  475.       return _M_insert(0, _M_rightmost(), __v, __position._M_node); // Last argument only needs to be non-null
  476.     else
  477.       return insert_unique(__v).first;
  478.   } else {
  479.     iterator __before = __position;
  480.     --__before;
  481.     
  482.     bool __comp_v_pos = _M_key_compare(_KeyOfValue()(__v), _S_key(__position._M_node));
  483.  
  484.     if (__comp_v_pos
  485.       && _M_key_compare( _S_key(__before._M_node), _KeyOfValue()(__v) )) {
  486.  
  487.       if (_S_right(__before._M_node) == 0)
  488.         return _M_insert(0, __before._M_node, __v, __before._M_node); // Last argument only needs to be non-null
  489.       else
  490.         return _M_insert(__position._M_node, __position._M_node, __v);
  491.     // first argument just needs to be non-null 
  492.     } else
  493.       {
  494.     // Does the insertion point fall immediately AFTER the hint?
  495.     iterator __after = __position;
  496.     ++__after;
  497.     
  498.     // Optimization to catch equivalent cases and avoid unnecessary comparisons
  499.     bool __comp_pos_v = !__comp_v_pos;  // Stored this result earlier
  500.     // If the earlier comparison was true, this comparison doesn't need to be
  501.     // performed because it must be false.  However, if the earlier comparison
  502.     // was false, we need to perform this one because in the equal case, both will
  503.     // be false.
  504.     if (!__comp_v_pos) __comp_pos_v = _M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__v));
  505.     
  506.     if ( (!__comp_v_pos) // comp_v_pos true implies comp_v_pos false
  507.          && __comp_pos_v
  508.          && (__after._M_node == this->_M_header._M_data ||
  509.             _M_key_compare( _KeyOfValue()(__v), _S_key(__after._M_node) ))) {
  510.       
  511.       if (_S_right(__position._M_node) == 0)
  512.         return _M_insert(0, __position._M_node, __v, __position._M_node);
  513.       else
  514.         return _M_insert(__after._M_node, __after._M_node, __v);
  515.     } else {
  516.       // Test for equivalent case
  517.       if (__comp_v_pos == __comp_pos_v)
  518.         return __position;
  519.       else
  520.         return insert_unique(__v).first;
  521.     }
  522.       }
  523.   }
  524. }
  525.  
  526.  
  527. template <class _Key, class _Value, class _KeyOfValue, 
  528.           class _Compare, class _Alloc> __iterator__ 
  529. _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> ::insert_equal(iterator __position, const _Value& __v)
  530. {
  531.   if (__position._M_node == this->_M_header._M_data->_M_left) { // begin()
  532.  
  533.     // Check for zero members
  534.     if (size() <= 0)
  535.         return insert_equal(__v);
  536.  
  537.     if (!_M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__v)))
  538.       return _M_insert(__position._M_node, __position._M_node, __v);
  539.     else    {
  540.       // Check for only one member
  541.       if (__position._M_node->_M_left == __position._M_node)
  542.         // Unlike insert_unique, can't avoid doing a comparison here.
  543.         return _M_insert(0, __position._M_node, __v);
  544.                 
  545.       // All other cases:
  546.       // Standard-conformance - does the insertion point fall immediately AFTER
  547.       // the hint?
  548.       iterator __after = __position;
  549.       ++__after;
  550.       
  551.       // Already know that compare(pos, v) must be true!
  552.       // Therefore, we want to know if compare(after, v) is false.
  553.       // (i.e., we now pos < v, now we want to know if v <= after)
  554.       // If not, invalid hint.
  555.       if ( __after._M_node==this->_M_header._M_data ||
  556.        !_M_key_compare( _S_key(__after._M_node), _KeyOfValue()(__v) ) ) {
  557.         if (_S_right(__position._M_node) == 0)
  558.           return _M_insert(0, __position._M_node, __v, __position._M_node);
  559.         else
  560.           return _M_insert(__after._M_node, __after._M_node, __v);
  561.       } else // Invalid hint
  562.         return insert_equal(__v);
  563.     }
  564.   } else if (__position._M_node == this->_M_header._M_data) {// end()
  565.     if (!_M_key_compare(_KeyOfValue()(__v), _S_key(_M_rightmost())))
  566.       return _M_insert(0, _M_rightmost(), __v, __position._M_node); // Last argument only needs to be non-null
  567.     else
  568.       return insert_equal(__v);
  569.   } else {
  570.     iterator __before = __position;
  571.     --__before;
  572.     // store the result of the comparison between pos and v so
  573.     // that we don't have to do it again later.  Note that this reverses the shortcut
  574.     // on the if, possibly harming efficiency in comparisons; I think the harm will
  575.     // be negligible, and to do what I want to do (save the result of a comparison so
  576.     // that it can be re-used) there is no alternative.  Test here is for before <= v <= pos.
  577.     bool __comp_pos_v = _M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__v));
  578.     if (!__comp_pos_v
  579.         && !_M_key_compare(_KeyOfValue()(__v), _S_key(__before._M_node))) {
  580.       if (_S_right(__before._M_node) == 0)
  581.         return _M_insert(0, __before._M_node, __v, __before._M_node); // Last argument only needs to be non-null
  582.       else
  583.         return _M_insert(__position._M_node, __position._M_node, __v);
  584.     } else  {
  585.       // Does the insertion point fall immediately AFTER the hint?
  586.       // Test for pos < v <= after
  587.       iterator __after = __position;
  588.       ++__after;
  589.       
  590.       if (__comp_pos_v
  591.       && ( __after._M_node==this->_M_header._M_data 
  592.            || !_M_key_compare( _S_key(__after._M_node), _KeyOfValue()(__v) ) ) ) {
  593.         if (_S_right(__position._M_node) == 0)
  594.           return _M_insert(0, __position._M_node, __v, __position._M_node);
  595.         else
  596.           return _M_insert(__after._M_node, __after._M_node, __v);
  597.       } else // Invalid hint
  598.         return insert_equal(__v);
  599.     }
  600.   }
  601. }
  602.  
  603. template <class _Key, class _Value, class _KeyOfValue, class _Compare, class _Alloc> _Rb_tree_node<_Value>* 
  604. _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> ::_M_copy(_Rb_tree_node<_Value>* __x, _Rb_tree_node<_Value>* __p)
  605. {
  606.                         // structural copy.  __x and __p must be non-null.
  607.   _Link_type __top = _M_clone_node(__x);
  608.   __top->_M_parent = __p;
  609.   
  610.   _STLP_TRY {
  611.     if (__x->_M_right)
  612.       __top->_M_right = _M_copy(_S_right(__x), __top);
  613.     __p = __top;
  614.     __x = _S_left(__x);
  615.  
  616.     while (__x != 0) {
  617.       _Link_type __y = _M_clone_node(__x);
  618.       __p->_M_left = __y;
  619.       __y->_M_parent = __p;
  620.       if (__x->_M_right)
  621.         __y->_M_right = _M_copy(_S_right(__x), __y);
  622.       __p = __y;
  623.       __x = _S_left(__x);
  624.     }
  625.   }
  626.   _STLP_UNWIND(_M_erase(__top));
  627.  
  628.   return __top;
  629. }
  630.  
  631. // this has to stay out-of-line : it's recursive
  632. template <class _Key, class _Value, class _KeyOfValue, 
  633.           class _Compare, class _Alloc> void 
  634. _Rb_tree<_Key,_Value,_KeyOfValue,
  635.   _Compare,_Alloc>::_M_erase(_Rb_tree_node<_Value>* __x)
  636. {
  637.                                 // erase without rebalancing
  638.   while (__x != 0) {
  639.     _M_erase(_S_right(__x));
  640.     _Link_type __y = _S_left(__x);
  641.     _Destroy(&__x->_M_value_field);
  642.     this->_M_header.deallocate(__x,1);
  643.     __x = __y;
  644.   }
  645. }
  646.  
  647. template <class _Key, class _Value, class _KeyOfValue, 
  648.           class _Compare, class _Alloc> __size_type__ 
  649. _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> ::count(const _Key& __k) const
  650. {
  651.   pair<const_iterator, const_iterator> __p = equal_range(__k);
  652.   size_type __n = distance(__p.first, __p.second);
  653.   return __n;
  654. }
  655.  
  656. inline int 
  657. __black_count(_Rb_tree_node_base* __node, _Rb_tree_node_base* __root)
  658. {
  659.   if (__node == 0)
  660.     return 0;
  661.   else {
  662.     int __bc = __node->_M_color == _S_rb_tree_black ? 1 : 0;
  663.     if (__node == __root)
  664.       return __bc;
  665.     else
  666.       return __bc + __black_count(__node->_M_parent, __root);
  667.   }
  668. }
  669.  
  670. template <class _Key, class _Value, class _KeyOfValue, 
  671.           class _Compare, class _Alloc> bool _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
  672. {
  673.   if (_M_node_count == 0 || begin() == end())
  674.     return _M_node_count == 0 && begin() == end() && this->_M_header._M_data->_M_left == this->_M_header._M_data
  675.       && this->_M_header._M_data->_M_right == this->_M_header._M_data;
  676.   
  677.   int __len = __black_count(_M_leftmost(), _M_root());
  678.   for (const_iterator __it = begin(); __it != end(); ++__it) {
  679.     _Link_type __x = (_Link_type) __it._M_node;
  680.     _Link_type __L = _S_left(__x);
  681.     _Link_type __R = _S_right(__x);
  682.  
  683.     if (__x->_M_color == _S_rb_tree_red)
  684.       if ((__L && __L->_M_color == _S_rb_tree_red) ||
  685.           (__R && __R->_M_color == _S_rb_tree_red))
  686.         return false;
  687.  
  688.     if (__L && _M_key_compare(_S_key(__x), _S_key(__L)))
  689.       return false;
  690.     if (__R && _M_key_compare(_S_key(__R), _S_key(__x)))
  691.       return false;
  692.  
  693.     if (!__L && !__R && __black_count(__x, _M_root()) != __len)
  694.       return false;
  695.   }
  696.  
  697.   if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
  698.     return false;
  699.   if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
  700.     return false;
  701.  
  702.   return true;
  703. }
  704. _STLP_END_NAMESPACE
  705.  
  706. # undef __iterator__        
  707. # undef iterator
  708. # undef __size_type__  
  709.  
  710. #endif /*  _STLP_TREE_C */
  711.  
  712. // Local Variables:
  713. // mode:C++
  714. // End:
  715.