/home/ntakagi/work/STLport-5.1.5/stlport/stl/_tree.c

Go to the documentation of this file.
00001 /*
00002  *
00003  *
00004  * Copyright (c) 1994
00005  * Hewlett-Packard Company
00006  *
00007  * Copyright (c) 1996,1997
00008  * Silicon Graphics Computer Systems, Inc.
00009  *
00010  * Copyright (c) 1997
00011  * Moscow Center for SPARC Technology
00012  *
00013  * Copyright (c) 1999
00014  * Boris Fomitchev
00015  *
00016  * This material is provided "as is", with absolutely no warranty expressed
00017  * or implied. Any use is at your own risk.
00018  *
00019  * Permission to use or copy this software for any purpose is hereby granted
00020  * without fee, provided the above notices are retained on all copies.
00021  * Permission to modify the code and to distribute modified code is granted,
00022  * provided the above notices are retained, and a notice that the code was
00023  * modified is included with the above copyright notice.
00024  *
00025  * Modified CRP 7/10/00 for improved conformance / efficiency on insert_unique /
00026  * insert_equal with valid hint -- efficiency is improved all around, and it is
00027  * should now be standard conforming for complexity on insert point immediately
00028  * after hint (amortized constant time).
00029  *
00030  */
00031 #ifndef _STLP_TREE_C
00032 #define _STLP_TREE_C
00033 
00034 #ifndef _STLP_INTERNAL_TREE_H
00035 #  include <stl/_tree.h>
00036 #endif
00037 
00038 #if defined (_STLP_DEBUG)
00039 #  define _Rb_tree _STLP_NON_DBG_NAME(Rb_tree)
00040 #endif
00041 
00042 // fbp: these defines are for outline methods definitions.
00043 // needed for definitions to be portable. Should not be used in method bodies.
00044 #if defined (_STLP_NESTED_TYPE_PARAM_BUG)
00045 #  define __iterator__  _Rb_tree_iterator<_Value, _STLP_HEADER_TYPENAME _Traits::_NonConstTraits>
00046 #  define __size_type__ size_t
00047 #  define iterator __iterator__
00048 #else
00049 #  define __iterator__  _STLP_TYPENAME_ON_RETURN_TYPE _Rb_tree<_Key, _Compare, _Value, _KeyOfValue, _Traits, _Alloc>::iterator
00050 #  define __size_type__  _STLP_TYPENAME_ON_RETURN_TYPE _Rb_tree<_Key, _Compare, _Value, _KeyOfValue, _Traits, _Alloc>::size_type
00051 #endif
00052 
00053 _STLP_BEGIN_NAMESPACE
00054 
00055 _STLP_MOVE_TO_PRIV_NAMESPACE
00056 
00057 #if defined (_STLP_EXPOSE_GLOBALS_IMPLEMENTATION)
00058 
00059 template <class _Dummy> void _STLP_CALL
00060 _Rb_global<_Dummy>::_Rotate_left(_Rb_tree_node_base* __x,
00061                                  _Rb_tree_node_base*& __root) {
00062   _Rb_tree_node_base* __y = __x->_M_right;
00063   __x->_M_right = __y->_M_left;
00064   if (__y->_M_left != 0)
00065     __y->_M_left->_M_parent = __x;
00066   __y->_M_parent = __x->_M_parent;
00067 
00068   if (__x == __root)
00069     __root = __y;
00070   else if (__x == __x->_M_parent->_M_left)
00071     __x->_M_parent->_M_left = __y;
00072   else
00073     __x->_M_parent->_M_right = __y;
00074   __y->_M_left = __x;
00075   __x->_M_parent = __y;
00076 }
00077 
00078 template <class _Dummy> void _STLP_CALL
00079 _Rb_global<_Dummy>::_Rotate_right(_Rb_tree_node_base* __x,
00080                                   _Rb_tree_node_base*& __root) {
00081   _Rb_tree_node_base* __y = __x->_M_left;
00082   __x->_M_left = __y->_M_right;
00083   if (__y->_M_right != 0)
00084     __y->_M_right->_M_parent = __x;
00085   __y->_M_parent = __x->_M_parent;
00086 
00087   if (__x == __root)
00088     __root = __y;
00089   else if (__x == __x->_M_parent->_M_right)
00090     __x->_M_parent->_M_right = __y;
00091   else
00092     __x->_M_parent->_M_left = __y;
00093   __y->_M_right = __x;
00094   __x->_M_parent = __y;
00095 }
00096 
00097 template <class _Dummy> void _STLP_CALL
00098 _Rb_global<_Dummy>::_Rebalance(_Rb_tree_node_base* __x,
00099                                _Rb_tree_node_base*& __root) {
00100   __x->_M_color = _S_rb_tree_red;
00101   while (__x != __root && __x->_M_parent->_M_color == _S_rb_tree_red) {
00102     if (__x->_M_parent == __x->_M_parent->_M_parent->_M_left) {
00103       _Rb_tree_node_base* __y = __x->_M_parent->_M_parent->_M_right;
00104       if (__y && __y->_M_color == _S_rb_tree_red) {
00105         __x->_M_parent->_M_color = _S_rb_tree_black;
00106         __y->_M_color = _S_rb_tree_black;
00107         __x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
00108         __x = __x->_M_parent->_M_parent;
00109       }
00110       else {
00111         if (__x == __x->_M_parent->_M_right) {
00112           __x = __x->_M_parent;
00113           _Rotate_left(__x, __root);
00114         }
00115         __x->_M_parent->_M_color = _S_rb_tree_black;
00116         __x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
00117         _Rotate_right(__x->_M_parent->_M_parent, __root);
00118       }
00119     }
00120     else {
00121       _Rb_tree_node_base* __y = __x->_M_parent->_M_parent->_M_left;
00122       if (__y && __y->_M_color == _S_rb_tree_red) {
00123         __x->_M_parent->_M_color = _S_rb_tree_black;
00124         __y->_M_color = _S_rb_tree_black;
00125         __x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
00126         __x = __x->_M_parent->_M_parent;
00127       }
00128       else {
00129         if (__x == __x->_M_parent->_M_left) {
00130           __x = __x->_M_parent;
00131           _Rotate_right(__x, __root);
00132         }
00133         __x->_M_parent->_M_color = _S_rb_tree_black;
00134         __x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
00135         _Rotate_left(__x->_M_parent->_M_parent, __root);
00136       }
00137     }
00138   }
00139   __root->_M_color = _S_rb_tree_black;
00140 }
00141 
00142 template <class _Dummy> _Rb_tree_node_base* _STLP_CALL
00143 _Rb_global<_Dummy>::_Rebalance_for_erase(_Rb_tree_node_base* __z,
00144                                          _Rb_tree_node_base*& __root,
00145                                          _Rb_tree_node_base*& __leftmost,
00146                                          _Rb_tree_node_base*& __rightmost) {
00147   _Rb_tree_node_base* __y = __z;
00148   _Rb_tree_node_base* __x;
00149   _Rb_tree_node_base* __x_parent;
00150 
00151   if (__y->_M_left == 0)     // __z has at most one non-null child. y == z.
00152     __x = __y->_M_right;     // __x might be null.
00153   else {
00154     if (__y->_M_right == 0)  // __z has exactly one non-null child. y == z.
00155       __x = __y->_M_left;    // __x is not null.
00156     else {                   // __z has two non-null children.  Set __y to
00157       __y = _Rb_tree_node_base::_S_minimum(__y->_M_right);   //   __z's successor.  __x might be null.
00158       __x = __y->_M_right;
00159     }
00160   }
00161 
00162   if (__y != __z) {          // relink y in place of z.  y is z's successor
00163     __z->_M_left->_M_parent = __y;
00164     __y->_M_left = __z->_M_left;
00165     if (__y != __z->_M_right) {
00166       __x_parent = __y->_M_parent;
00167       if (__x) __x->_M_parent = __y->_M_parent;
00168       __y->_M_parent->_M_left = __x;      // __y must be a child of _M_left
00169       __y->_M_right = __z->_M_right;
00170       __z->_M_right->_M_parent = __y;
00171     }
00172     else
00173       __x_parent = __y;
00174     if (__root == __z)
00175       __root = __y;
00176     else if (__z->_M_parent->_M_left == __z)
00177       __z->_M_parent->_M_left = __y;
00178     else
00179       __z->_M_parent->_M_right = __y;
00180     __y->_M_parent = __z->_M_parent;
00181     _STLP_STD::swap(__y->_M_color, __z->_M_color);
00182     __y = __z;
00183     // __y now points to node to be actually deleted
00184   }
00185   else {                        // __y == __z
00186     __x_parent = __y->_M_parent;
00187     if (__x) __x->_M_parent = __y->_M_parent;
00188     if (__root == __z)
00189       __root = __x;
00190     else {
00191       if (__z->_M_parent->_M_left == __z)
00192         __z->_M_parent->_M_left = __x;
00193       else
00194         __z->_M_parent->_M_right = __x;
00195     }
00196 
00197     if (__leftmost == __z) {
00198       if (__z->_M_right == 0)        // __z->_M_left must be null also
00199         __leftmost = __z->_M_parent;
00200     // makes __leftmost == _M_header if __z == __root
00201       else
00202         __leftmost = _Rb_tree_node_base::_S_minimum(__x);
00203     }
00204     if (__rightmost == __z) {
00205       if (__z->_M_left == 0)         // __z->_M_right must be null also
00206         __rightmost = __z->_M_parent;
00207     // makes __rightmost == _M_header if __z == __root
00208       else                      // __x == __z->_M_left
00209         __rightmost = _Rb_tree_node_base::_S_maximum(__x);
00210     }
00211   }
00212 
00213   if (__y->_M_color != _S_rb_tree_red) {
00214     while (__x != __root && (__x == 0 || __x->_M_color == _S_rb_tree_black))
00215       if (__x == __x_parent->_M_left) {
00216         _Rb_tree_node_base* __w = __x_parent->_M_right;
00217         if (__w->_M_color == _S_rb_tree_red) {
00218           __w->_M_color = _S_rb_tree_black;
00219           __x_parent->_M_color = _S_rb_tree_red;
00220           _Rotate_left(__x_parent, __root);
00221           __w = __x_parent->_M_right;
00222         }
00223         if ((__w->_M_left == 0 ||
00224              __w->_M_left->_M_color == _S_rb_tree_black) && (__w->_M_right == 0 ||
00225              __w->_M_right->_M_color == _S_rb_tree_black)) {
00226           __w->_M_color = _S_rb_tree_red;
00227           __x = __x_parent;
00228           __x_parent = __x_parent->_M_parent;
00229         } else {
00230           if (__w->_M_right == 0 ||
00231               __w->_M_right->_M_color == _S_rb_tree_black) {
00232             if (__w->_M_left) __w->_M_left->_M_color = _S_rb_tree_black;
00233             __w->_M_color = _S_rb_tree_red;
00234             _Rotate_right(__w, __root);
00235             __w = __x_parent->_M_right;
00236           }
00237           __w->_M_color = __x_parent->_M_color;
00238           __x_parent->_M_color = _S_rb_tree_black;
00239           if (__w->_M_right) __w->_M_right->_M_color = _S_rb_tree_black;
00240           _Rotate_left(__x_parent, __root);
00241           break;
00242         }
00243       } else {                  // same as above, with _M_right <-> _M_left.
00244         _Rb_tree_node_base* __w = __x_parent->_M_left;
00245         if (__w->_M_color == _S_rb_tree_red) {
00246           __w->_M_color = _S_rb_tree_black;
00247           __x_parent->_M_color = _S_rb_tree_red;
00248           _Rotate_right(__x_parent, __root);
00249           __w = __x_parent->_M_left;
00250         }
00251         if ((__w->_M_right == 0 ||
00252              __w->_M_right->_M_color == _S_rb_tree_black) && (__w->_M_left == 0 ||
00253              __w->_M_left->_M_color == _S_rb_tree_black)) {
00254           __w->_M_color = _S_rb_tree_red;
00255           __x = __x_parent;
00256           __x_parent = __x_parent->_M_parent;
00257         } else {
00258           if (__w->_M_left == 0 ||
00259               __w->_M_left->_M_color == _S_rb_tree_black) {
00260             if (__w->_M_right) __w->_M_right->_M_color = _S_rb_tree_black;
00261             __w->_M_color = _S_rb_tree_red;
00262             _Rotate_left(__w, __root);
00263             __w = __x_parent->_M_left;
00264           }
00265           __w->_M_color = __x_parent->_M_color;
00266           __x_parent->_M_color = _S_rb_tree_black;
00267           if (__w->_M_left) __w->_M_left->_M_color = _S_rb_tree_black;
00268           _Rotate_right(__x_parent, __root);
00269           break;
00270         }
00271       }
00272     if (__x) __x->_M_color = _S_rb_tree_black;
00273   }
00274   return __y;
00275 }
00276 
00277 template <class _Dummy> _Rb_tree_node_base* _STLP_CALL
00278 _Rb_global<_Dummy>::_M_decrement(_Rb_tree_node_base* _M_node) {
00279   if (_M_node->_M_color == _S_rb_tree_red && _M_node->_M_parent->_M_parent == _M_node)
00280     _M_node = _M_node->_M_right;
00281   else if (_M_node->_M_left != 0) {
00282     _M_node = _Rb_tree_node_base::_S_maximum(_M_node->_M_left);
00283   }
00284   else {
00285     _Base_ptr __y = _M_node->_M_parent;
00286     while (_M_node == __y->_M_left) {
00287       _M_node = __y;
00288       __y = __y->_M_parent;
00289     }
00290     _M_node = __y;
00291   }
00292   return _M_node;
00293 }
00294 
00295 template <class _Dummy> _Rb_tree_node_base* _STLP_CALL
00296 _Rb_global<_Dummy>::_M_increment(_Rb_tree_node_base* _M_node) {
00297   if (_M_node->_M_right != 0) {
00298     _M_node = _Rb_tree_node_base::_S_minimum(_M_node->_M_right);
00299   }
00300   else {
00301     _Base_ptr __y = _M_node->_M_parent;
00302     while (_M_node == __y->_M_right) {
00303       _M_node = __y;
00304       __y = __y->_M_parent;
00305     }
00306     // check special case: This is necessary if _M_node is the
00307     // _M_head and the tree contains only a single node __y. In
00308     // that case parent, left and right all point to __y!
00309     if (_M_node->_M_right != __y)
00310       _M_node = __y;
00311   }
00312   return _M_node;
00313 }
00314 
00315 #endif /* _STLP_EXPOSE_GLOBALS_IMPLEMENTATION */
00316 
00317 
00318 template <class _Key, class _Compare,
00319           class _Value, class _KeyOfValue, class _Traits, class _Alloc>
00320 _Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc>&
00321 _Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc> ::operator=(
00322   const _Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc>& __x) {
00323   if (this != &__x) {
00324     // Note that _Key may be a constant type.
00325     clear();
00326     _M_node_count = 0;
00327     _M_key_compare = __x._M_key_compare;
00328     if (__x._M_root() == 0) {
00329       _M_root() = 0;
00330       _M_leftmost() = &this->_M_header._M_data;
00331       _M_rightmost() = &this->_M_header._M_data;
00332     }
00333     else {
00334       _M_root() = _M_copy(__x._M_root(), &this->_M_header._M_data);
00335       _M_leftmost() = _S_minimum(_M_root());
00336       _M_rightmost() = _S_maximum(_M_root());
00337       _M_node_count = __x._M_node_count;
00338     }
00339   }
00340   return *this;
00341 }
00342 
00343 // CRP 7/10/00 inserted argument __on_right, which is another hint (meant to
00344 // act like __on_left and ignore a portion of the if conditions -- specify
00345 // __on_right != 0 to bypass comparison as false or __on_left != 0 to bypass
00346 // comparison as true)
00347 template <class _Key, class _Compare,
00348           class _Value, class _KeyOfValue, class _Traits, class _Alloc>
00349 __iterator__
00350 _Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc> ::_M_insert(_Rb_tree_node_base * __parent,
00351                                                                       const _Value& __val,
00352                                                                       _Rb_tree_node_base * __on_left,
00353                                                                       _Rb_tree_node_base * __on_right) {
00354   // We do not create the node here as, depending on tests, we might call
00355   // _M_key_compare that can throw an exception.
00356   _Base_ptr __new_node;
00357 
00358   if ( __parent == &this->_M_header._M_data ) {
00359     __new_node = _M_create_node(__val);
00360     _S_left(__parent) = __new_node;   // also makes _M_leftmost() = __new_node
00361     _M_root() = __new_node;
00362     _M_rightmost() = __new_node;
00363   }
00364   else if ( __on_right == 0 &&     // If __on_right != 0, the remainder fails to false
00365            ( __on_left != 0 ||     // If __on_left != 0, the remainder succeeds to true
00366              _M_key_compare( _KeyOfValue()(__val), _S_key(__parent) ) ) ) {
00367     __new_node = _M_create_node(__val);
00368     _S_left(__parent) = __new_node;
00369     if (__parent == _M_leftmost())
00370       _M_leftmost() = __new_node;   // maintain _M_leftmost() pointing to min node
00371   }
00372   else {
00373     __new_node = _M_create_node(__val);
00374     _S_right(__parent) = __new_node;
00375     if (__parent == _M_rightmost())
00376       _M_rightmost() = __new_node;  // maintain _M_rightmost() pointing to max node
00377   }
00378   _S_parent(__new_node) = __parent;
00379   _Rb_global_inst::_Rebalance(__new_node, this->_M_header._M_data._M_parent);
00380   ++_M_node_count;
00381   return iterator(__new_node);
00382 }
00383 
00384 template <class _Key, class _Compare,
00385           class _Value, class _KeyOfValue, class _Traits, class _Alloc>
00386 __iterator__
00387 _Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc> ::insert_equal(const _Value& __val) {
00388   _Base_ptr __y = &this->_M_header._M_data;
00389   _Base_ptr __x = _M_root();
00390   while (__x != 0) {
00391     __y = __x;
00392     if (_M_key_compare(_KeyOfValue()(__val), _S_key(__x))) {
00393       __x = _S_left(__x);
00394     }
00395     else
00396       __x = _S_right(__x);
00397   }
00398   return _M_insert(__y, __val, __x);
00399 }
00400 
00401 
00402 template <class _Key, class _Compare,
00403           class _Value, class _KeyOfValue, class _Traits, class _Alloc>
00404 pair<__iterator__, bool>
00405 _Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc> ::insert_unique(const _Value& __val) {
00406   _Base_ptr __y = &this->_M_header._M_data;
00407   _Base_ptr __x = _M_root();
00408   bool __comp = true;
00409   while (__x != 0) {
00410     __y = __x;
00411     __comp = _M_key_compare(_KeyOfValue()(__val), _S_key(__x));
00412     __x = __comp ? _S_left(__x) : _S_right(__x);
00413   }
00414   iterator __j = iterator(__y);
00415   if (__comp) {
00416     if (__j == begin())
00417       return pair<iterator,bool>(_M_insert(__y, __val, /* __x*/ __y), true);
00418     else
00419       --__j;
00420   }
00421   if (_M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__val))) {
00422     return pair<iterator,bool>(_M_insert(__y, __val, __x), true);
00423   }
00424   return pair<iterator,bool>(__j, false);
00425 }
00426 
00427 // Modifications CRP 7/10/00 as noted to improve conformance and
00428 // efficiency.
00429 template <class _Key, class _Compare,
00430           class _Value, class _KeyOfValue, class _Traits, class _Alloc>
00431 __iterator__
00432 _Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc> ::insert_unique(iterator __position,
00433                                                                           const _Value& __val) {
00434   if (__position._M_node == this->_M_header._M_data._M_left) { // begin()
00435 
00436     // if the container is empty, fall back on insert_unique.
00437     if (empty())
00438       return insert_unique(__val).first;
00439 
00440     if (_M_key_compare(_KeyOfValue()(__val), _S_key(__position._M_node))) {
00441       return _M_insert(__position._M_node, __val, __position._M_node);
00442     }
00443     // first argument just needs to be non-null
00444     else {
00445       bool __comp_pos_v = _M_key_compare( _S_key(__position._M_node), _KeyOfValue()(__val) );
00446 
00447       if (__comp_pos_v == false)  // compare > and compare < both false so compare equal
00448         return __position;
00449       //Below __comp_pos_v == true
00450 
00451       // Standard-conformance - does the insertion point fall immediately AFTER
00452       // the hint?
00453       iterator __after = __position;
00454       ++__after;
00455 
00456       // Check for only one member -- in that case, __position points to itself,
00457       // and attempting to increment will cause an infinite loop.
00458       if (__after._M_node == &this->_M_header._M_data)
00459         // Check guarantees exactly one member, so comparison was already
00460         // performed and we know the result; skip repeating it in _M_insert
00461         // by specifying a non-zero fourth argument.
00462         return _M_insert(__position._M_node, __val, 0, __position._M_node);
00463 
00464       // All other cases:
00465 
00466       // Optimization to catch insert-equivalent -- save comparison results,
00467       // and we get this for free.
00468       if (_M_key_compare( _KeyOfValue()(__val), _S_key(__after._M_node) )) {
00469         if (_S_right(__position._M_node) == 0)
00470           return _M_insert(__position._M_node, __val, 0, __position._M_node);
00471         else
00472           return _M_insert(__after._M_node, __val, __after._M_node);
00473       }
00474       else {
00475         return insert_unique(__val).first;
00476       }
00477     }
00478   }
00479   else if (__position._M_node == &this->_M_header._M_data) { // end()
00480     if (_M_key_compare(_S_key(_M_rightmost()), _KeyOfValue()(__val))) {
00481         // pass along to _M_insert that it can skip comparing
00482         // v, Key ; since compare Key, v was true, compare v, Key must be false.
00483         return _M_insert(_M_rightmost(), __val, 0, __position._M_node); // Last argument only needs to be non-null
00484     }
00485     else
00486       return insert_unique(__val).first;
00487   }
00488   else {
00489     iterator __before = __position;
00490     --__before;
00491 
00492     bool __comp_v_pos = _M_key_compare(_KeyOfValue()(__val), _S_key(__position._M_node));
00493 
00494     if (__comp_v_pos
00495         && _M_key_compare( _S_key(__before._M_node), _KeyOfValue()(__val) )) {
00496 
00497       if (_S_right(__before._M_node) == 0)
00498         return _M_insert(__before._M_node, __val, 0, __before._M_node); // Last argument only needs to be non-null
00499       else
00500         return _M_insert(__position._M_node, __val, __position._M_node);
00501       // first argument just needs to be non-null
00502     }
00503     else {
00504       // Does the insertion point fall immediately AFTER the hint?
00505       iterator __after = __position;
00506       ++__after;
00507       // Optimization to catch equivalent cases and avoid unnecessary comparisons
00508       bool __comp_pos_v = !__comp_v_pos;  // Stored this result earlier
00509       // If the earlier comparison was true, this comparison doesn't need to be
00510       // performed because it must be false.  However, if the earlier comparison
00511       // was false, we need to perform this one because in the equal case, both will
00512       // be false.
00513       if (!__comp_v_pos) {
00514         __comp_pos_v = _M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__val));
00515       }
00516 
00517       if ( (!__comp_v_pos) // comp_v_pos true implies comp_v_pos false
00518           && __comp_pos_v
00519           && (__after._M_node == &this->_M_header._M_data ||
00520               _M_key_compare( _KeyOfValue()(__val), _S_key(__after._M_node) ))) {
00521         if (_S_right(__position._M_node) == 0)
00522           return _M_insert(__position._M_node, __val, 0, __position._M_node);
00523         else
00524           return _M_insert(__after._M_node, __val, __after._M_node);
00525       } else {
00526         // Test for equivalent case
00527         if (__comp_v_pos == __comp_pos_v)
00528           return __position;
00529         else
00530           return insert_unique(__val).first;
00531       }
00532     }
00533   }
00534 }
00535 
00536 template <class _Key, class _Compare,
00537           class _Value, class _KeyOfValue, class _Traits, class _Alloc>
00538 __iterator__
00539 _Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc> ::insert_equal(iterator __position,
00540                                                                          const _Value& __val) {
00541   if (__position._M_node == this->_M_header._M_data._M_left) { // begin()
00542 
00543     // Check for zero members
00544     if (size() <= 0)
00545         return insert_equal(__val);
00546 
00547     if (!_M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__val)))
00548       return _M_insert(__position._M_node, __val, __position._M_node);
00549     else {
00550       // Check for only one member
00551       if (__position._M_node->_M_left == __position._M_node)
00552         // Unlike insert_unique, can't avoid doing a comparison here.
00553         return _M_insert(__position._M_node, __val);
00554 
00555       // All other cases:
00556       // Standard-conformance - does the insertion point fall immediately AFTER
00557       // the hint?
00558       iterator __after = __position;
00559       ++__after;
00560 
00561       // Already know that compare(pos, v) must be true!
00562       // Therefore, we want to know if compare(after, v) is false.
00563       // (i.e., we now pos < v, now we want to know if v <= after)
00564       // If not, invalid hint.
00565       if ( __after._M_node == &this->_M_header._M_data ||
00566            !_M_key_compare( _S_key(__after._M_node), _KeyOfValue()(__val) ) ) {
00567         if (_S_right(__position._M_node) == 0)
00568           return _M_insert(__position._M_node, __val, 0, __position._M_node);
00569         else
00570           return _M_insert(__after._M_node, __val, __after._M_node);
00571       }
00572       else { // Invalid hint
00573         return insert_equal(__val);
00574       }
00575     }
00576   }
00577   else if (__position._M_node == &this->_M_header._M_data) { // end()
00578     if (!_M_key_compare(_KeyOfValue()(__val), _S_key(_M_rightmost())))
00579       return _M_insert(_M_rightmost(), __val, 0, __position._M_node); // Last argument only needs to be non-null
00580     else {
00581       return insert_equal(__val);
00582     }
00583   }
00584   else {
00585     iterator __before = __position;
00586     --__before;
00587     // store the result of the comparison between pos and v so
00588     // that we don't have to do it again later.  Note that this reverses the shortcut
00589     // on the if, possibly harming efficiency in comparisons; I think the harm will
00590     // be negligible, and to do what I want to do (save the result of a comparison so
00591     // that it can be re-used) there is no alternative.  Test here is for before <= v <= pos.
00592     bool __comp_pos_v = _M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__val));
00593     if (!__comp_pos_v &&
00594         !_M_key_compare(_KeyOfValue()(__val), _S_key(__before._M_node))) {
00595       if (_S_right(__before._M_node) == 0)
00596         return _M_insert(__before._M_node, __val, 0, __before._M_node); // Last argument only needs to be non-null
00597       else
00598         return _M_insert(__position._M_node, __val, __position._M_node);
00599     }
00600     else {
00601       // Does the insertion point fall immediately AFTER the hint?
00602       // Test for pos < v <= after
00603       iterator __after = __position;
00604       ++__after;
00605 
00606       if (__comp_pos_v &&
00607           ( __after._M_node == &this->_M_header._M_data ||
00608             !_M_key_compare( _S_key(__after._M_node), _KeyOfValue()(__val) ) ) ) {
00609         if (_S_right(__position._M_node) == 0)
00610           return _M_insert(__position._M_node, __val, 0, __position._M_node);
00611         else
00612           return _M_insert(__after._M_node, __val, __after._M_node);
00613       }
00614       else { // Invalid hint
00615         return insert_equal(__val);
00616       }
00617     }
00618   }
00619 }
00620 
00621 template <class _Key, class _Compare,
00622           class _Value, class _KeyOfValue, class _Traits, class _Alloc>
00623 _Rb_tree_node_base*
00624 _Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc> ::_M_copy(_Rb_tree_node_base* __x,
00625                                                                     _Rb_tree_node_base* __p) {
00626   // structural copy.  __x and __p must be non-null.
00627   _Base_ptr __top = _M_clone_node(__x);
00628   _S_parent(__top) = __p;
00629 
00630   _STLP_TRY {
00631     if (_S_right(__x))
00632       _S_right(__top) = _M_copy(_S_right(__x), __top);
00633     __p = __top;
00634     __x = _S_left(__x);
00635 
00636     while (__x != 0) {
00637       _Base_ptr __y = _M_clone_node(__x);
00638       _S_left(__p) = __y;
00639       _S_parent(__y) = __p;
00640       if (_S_right(__x))
00641         _S_right(__y) = _M_copy(_S_right(__x), __y);
00642       __p = __y;
00643       __x = _S_left(__x);
00644     }
00645   }
00646   _STLP_UNWIND(_M_erase(__top))
00647 
00648   return __top;
00649 }
00650 
00651 // this has to stay out-of-line : it's recursive
00652 template <class _Key, class _Compare,
00653           class _Value, class _KeyOfValue, class _Traits, class _Alloc>
00654 void
00655 _Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc>::_M_erase(_Rb_tree_node_base *__x) {
00656   // erase without rebalancing
00657   while (__x != 0) {
00658     _M_erase(_S_right(__x));
00659     _Base_ptr __y = _S_left(__x);
00660     _STLP_STD::_Destroy(&_S_value(__x));
00661     this->_M_header.deallocate(__STATIC_CAST(_Link_type, __x),1);
00662     __x = __y;
00663   }
00664 }
00665 
00666 #if defined (_STLP_DEBUG)
00667 inline int
00668 __black_count(_Rb_tree_node_base* __node, _Rb_tree_node_base* __root) {
00669   if (__node == 0)
00670     return 0;
00671   else {
00672     int __bc = __node->_M_color == _S_rb_tree_black ? 1 : 0;
00673     if (__node == __root)
00674       return __bc;
00675     else
00676       return __bc + __black_count(__node->_M_parent, __root);
00677   }
00678 }
00679 
00680 template <class _Key, class _Compare,
00681           class _Value, class _KeyOfValue, class _Traits, class _Alloc>
00682 bool _Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc>::__rb_verify() const {
00683   if (_M_node_count == 0 || begin() == end())
00684     return ((_M_node_count == 0) &&
00685             (begin() == end()) &&
00686             (this->_M_header._M_data._M_left == &this->_M_header._M_data) &&
00687             (this->_M_header._M_data._M_right == &this->_M_header._M_data));
00688 
00689   int __len = __black_count(_M_leftmost(), _M_root());
00690   for (const_iterator __it = begin(); __it != end(); ++__it) {
00691     _Base_ptr __x = __it._M_node;
00692     _Base_ptr __L = _S_left(__x);
00693     _Base_ptr __R = _S_right(__x);
00694 
00695     if (__x->_M_color == _S_rb_tree_red)
00696       if ((__L && __L->_M_color == _S_rb_tree_red) ||
00697           (__R && __R->_M_color == _S_rb_tree_red))
00698         return false;
00699 
00700     if (__L && _M_key_compare(_S_key(__x), _S_key(__L)))
00701       return false;
00702     if (__R && _M_key_compare(_S_key(__R), _S_key(__x)))
00703       return false;
00704 
00705     if (!__L && !__R && __black_count(__x, _M_root()) != __len)
00706       return false;
00707   }
00708 
00709   if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
00710     return false;
00711   if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
00712     return false;
00713 
00714   return true;
00715 }
00716 #endif /* _STLP_DEBUG */
00717 
00718 _STLP_MOVE_TO_STD_NAMESPACE
00719 _STLP_END_NAMESPACE
00720 
00721 #undef _Rb_tree
00722 #undef __iterator__
00723 #undef iterator
00724 #undef __size_type__
00725 
00726 #endif /*  _STLP_TREE_C */
00727 
00728 // Local Variables:
00729 // mode:C++
00730 // End:



Generated on Mon Mar 10 15:32:42 2008 by  doxygen 1.5.1