1.1 --- a/epoc32/include/stdapis/stlport/stl/_tree.c Tue Mar 16 16:12:26 2010 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,715 +0,0 @@
1.4 -/*
1.5 - *
1.6 - *
1.7 - * Copyright (c) 1994
1.8 - * Hewlett-Packard Company
1.9 - *
1.10 - * Copyright (c) 1996,1997
1.11 - * Silicon Graphics Computer Systems, Inc.
1.12 - *
1.13 - * Copyright (c) 1997
1.14 - * Moscow Center for SPARC Technology
1.15 - *
1.16 - * Copyright (c) 1999
1.17 - * Boris Fomitchev
1.18 - *
1.19 - * This material is provided "as is", with absolutely no warranty expressed
1.20 - * or implied. Any use is at your own risk.
1.21 - *
1.22 - * Permission to use or copy this software for any purpose is hereby granted
1.23 - * without fee, provided the above notices are retained on all copies.
1.24 - * Permission to modify the code and to distribute modified code is granted,
1.25 - * provided the above notices are retained, and a notice that the code was
1.26 - * modified is included with the above copyright notice.
1.27 - *
1.28 - * Modified CRP 7/10/00 for improved conformance / efficiency on insert_unique /
1.29 - * insert_equal with valid hint -- efficiency is improved all around, and it is
1.30 - * should now be standard conforming for complexity on insert point immediately
1.31 - * after hint (amortized constant time).
1.32 - *
1.33 - */
1.34 -#ifndef _STLP_TREE_C
1.35 -#define _STLP_TREE_C
1.36 -
1.37 -#ifndef _STLP_INTERNAL_TREE_H
1.38 -# include <stl/_tree.h>
1.39 -#endif
1.40 -
1.41 -// fbp: these defines are for outline methods definitions.
1.42 -// needed for definitions to be portable. Should not be used in method bodies.
1.43 -# if defined ( _STLP_NESTED_TYPE_PARAM_BUG )
1.44 -# define __iterator__ _Rb_tree_iterator<_Value, _Nonconst_traits<_Value> >
1.45 -# define __size_type__ size_t
1.46 -# define iterator __iterator__
1.47 -# else
1.48 -# define __iterator__ _STLP_TYPENAME_ON_RETURN_TYPE _Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc>::iterator
1.49 -# define __size_type__ _STLP_TYPENAME_ON_RETURN_TYPE _Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc>::size_type
1.50 -# endif
1.51 -
1.52 -#if defined ( _STLP_DEBUG)
1.53 -# define _Rb_tree __WORKAROUND_DBG_RENAME(Rb_tree)
1.54 -#endif
1.55 -
1.56 -_STLP_BEGIN_NAMESPACE
1.57 -
1.58 -# if defined (_STLP_EXPOSE_GLOBALS_IMPLEMENTATION)
1.59 -
1.60 -template <class _Dummy> void _STLP_CALL
1.61 -_Rb_global<_Dummy>::_Rotate_left(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root)
1.62 -{
1.63 - _Rb_tree_node_base* __y = __x->_M_right;
1.64 - __x->_M_right = __y->_M_left;
1.65 - if (__y->_M_left !=0)
1.66 - __y->_M_left->_M_parent = __x;
1.67 - __y->_M_parent = __x->_M_parent;
1.68 -
1.69 - if (__x == __root)
1.70 - __root = __y;
1.71 - else if (__x == __x->_M_parent->_M_left)
1.72 - __x->_M_parent->_M_left = __y;
1.73 - else
1.74 - __x->_M_parent->_M_right = __y;
1.75 - __y->_M_left = __x;
1.76 - __x->_M_parent = __y;
1.77 -}
1.78 -
1.79 -template <class _Dummy> void _STLP_CALL
1.80 -_Rb_global<_Dummy>::_Rotate_right(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root)
1.81 -{
1.82 - _Rb_tree_node_base* __y = __x->_M_left;
1.83 - __x->_M_left = __y->_M_right;
1.84 - if (__y->_M_right != 0)
1.85 - __y->_M_right->_M_parent = __x;
1.86 - __y->_M_parent = __x->_M_parent;
1.87 -
1.88 - if (__x == __root)
1.89 - __root = __y;
1.90 - else if (__x == __x->_M_parent->_M_right)
1.91 - __x->_M_parent->_M_right = __y;
1.92 - else
1.93 - __x->_M_parent->_M_left = __y;
1.94 - __y->_M_right = __x;
1.95 - __x->_M_parent = __y;
1.96 -}
1.97 -
1.98 -template <class _Dummy> void _STLP_CALL
1.99 -_Rb_global<_Dummy>::_Rebalance(_Rb_tree_node_base* __x,
1.100 - _Rb_tree_node_base*& __root)
1.101 -{
1.102 - __x->_M_color = _S_rb_tree_red;
1.103 - while (__x != __root && __x->_M_parent->_M_color == _S_rb_tree_red) {
1.104 - if (__x->_M_parent == __x->_M_parent->_M_parent->_M_left) {
1.105 - _Rb_tree_node_base* __y = __x->_M_parent->_M_parent->_M_right;
1.106 - if (__y && __y->_M_color == _S_rb_tree_red) {
1.107 - __x->_M_parent->_M_color = _S_rb_tree_black;
1.108 - __y->_M_color = _S_rb_tree_black;
1.109 - __x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
1.110 - __x = __x->_M_parent->_M_parent;
1.111 - }
1.112 - else {
1.113 - if (__x == __x->_M_parent->_M_right) {
1.114 - __x = __x->_M_parent;
1.115 - _Rotate_left(__x, __root);
1.116 - }
1.117 - __x->_M_parent->_M_color = _S_rb_tree_black;
1.118 - __x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
1.119 - _Rotate_right(__x->_M_parent->_M_parent, __root);
1.120 - }
1.121 - }
1.122 - else {
1.123 - _Rb_tree_node_base* __y = __x->_M_parent->_M_parent->_M_left;
1.124 - if (__y && __y->_M_color == _S_rb_tree_red) {
1.125 - __x->_M_parent->_M_color = _S_rb_tree_black;
1.126 - __y->_M_color = _S_rb_tree_black;
1.127 - __x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
1.128 - __x = __x->_M_parent->_M_parent;
1.129 - }
1.130 - else {
1.131 - if (__x == __x->_M_parent->_M_left) {
1.132 - __x = __x->_M_parent;
1.133 - _Rotate_right(__x, __root);
1.134 - }
1.135 - __x->_M_parent->_M_color = _S_rb_tree_black;
1.136 - __x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
1.137 - _Rotate_left(__x->_M_parent->_M_parent, __root);
1.138 - }
1.139 - }
1.140 - }
1.141 - __root->_M_color = _S_rb_tree_black;
1.142 -}
1.143 -
1.144 -template <class _Dummy> _Rb_tree_node_base* _STLP_CALL
1.145 -_Rb_global<_Dummy>::_Rebalance_for_erase(_Rb_tree_node_base* __z,
1.146 - _Rb_tree_node_base*& __root,
1.147 - _Rb_tree_node_base*& __leftmost,
1.148 - _Rb_tree_node_base*& __rightmost)
1.149 -{
1.150 - _Rb_tree_node_base* __y = __z;
1.151 - _Rb_tree_node_base* __x = 0;
1.152 - _Rb_tree_node_base* __x_parent = 0;
1.153 - if (__y->_M_left == 0) // __z has at most one non-null child. y == z.
1.154 - __x = __y->_M_right; // __x might be null.
1.155 - else
1.156 - if (__y->_M_right == 0) // __z has exactly one non-null child. y == z.
1.157 - __x = __y->_M_left; // __x is not null.
1.158 - else { // __z has two non-null children. Set __y to
1.159 - __y = __y->_M_right; // __z's successor. __x might be null.
1.160 - while (__y->_M_left != 0)
1.161 - __y = __y->_M_left;
1.162 - __x = __y->_M_right;
1.163 - }
1.164 - if (__y != __z) { // relink y in place of z. y is z's successor
1.165 - __z->_M_left->_M_parent = __y;
1.166 - __y->_M_left = __z->_M_left;
1.167 - if (__y != __z->_M_right) {
1.168 - __x_parent = __y->_M_parent;
1.169 - if (__x) __x->_M_parent = __y->_M_parent;
1.170 - __y->_M_parent->_M_left = __x; // __y must be a child of _M_left
1.171 - __y->_M_right = __z->_M_right;
1.172 - __z->_M_right->_M_parent = __y;
1.173 - }
1.174 - else
1.175 - __x_parent = __y;
1.176 - if (__root == __z)
1.177 - __root = __y;
1.178 - else if (__z->_M_parent->_M_left == __z)
1.179 - __z->_M_parent->_M_left = __y;
1.180 - else
1.181 - __z->_M_parent->_M_right = __y;
1.182 - __y->_M_parent = __z->_M_parent;
1.183 - _STLP_STD::swap(__y->_M_color, __z->_M_color);
1.184 - __y = __z;
1.185 - // __y now points to node to be actually deleted
1.186 - }
1.187 - else { // __y == __z
1.188 - __x_parent = __y->_M_parent;
1.189 - if (__x) __x->_M_parent = __y->_M_parent;
1.190 - if (__root == __z)
1.191 - __root = __x;
1.192 - else
1.193 - if (__z->_M_parent->_M_left == __z)
1.194 - __z->_M_parent->_M_left = __x;
1.195 - else
1.196 - __z->_M_parent->_M_right = __x;
1.197 - if (__leftmost == __z)
1.198 - if (__z->_M_right == 0) // __z->_M_left must be null also
1.199 - __leftmost = __z->_M_parent;
1.200 - // makes __leftmost == _M_header if __z == __root
1.201 - else
1.202 - __leftmost = _Rb_tree_node_base::_S_minimum(__x);
1.203 - if (__rightmost == __z)
1.204 - if (__z->_M_left == 0) // __z->_M_right must be null also
1.205 - __rightmost = __z->_M_parent;
1.206 - // makes __rightmost == _M_header if __z == __root
1.207 - else // __x == __z->_M_left
1.208 - __rightmost = _Rb_tree_node_base::_S_maximum(__x);
1.209 - }
1.210 - if (__y->_M_color != _S_rb_tree_red) {
1.211 - while (__x != __root && (__x == 0 || __x->_M_color == _S_rb_tree_black))
1.212 - if (__x == __x_parent->_M_left) {
1.213 - _Rb_tree_node_base* __w = __x_parent->_M_right;
1.214 - if (__w->_M_color == _S_rb_tree_red) {
1.215 - __w->_M_color = _S_rb_tree_black;
1.216 - __x_parent->_M_color = _S_rb_tree_red;
1.217 - _Rotate_left(__x_parent, __root);
1.218 - __w = __x_parent->_M_right;
1.219 - }
1.220 - if ((__w->_M_left == 0 ||
1.221 - __w->_M_left->_M_color == _S_rb_tree_black) && (__w->_M_right == 0 ||
1.222 - __w->_M_right->_M_color == _S_rb_tree_black)) {
1.223 - __w->_M_color = _S_rb_tree_red;
1.224 - __x = __x_parent;
1.225 - __x_parent = __x_parent->_M_parent;
1.226 - } else {
1.227 - if (__w->_M_right == 0 ||
1.228 - __w->_M_right->_M_color == _S_rb_tree_black) {
1.229 - if (__w->_M_left) __w->_M_left->_M_color = _S_rb_tree_black;
1.230 - __w->_M_color = _S_rb_tree_red;
1.231 - _Rotate_right(__w, __root);
1.232 - __w = __x_parent->_M_right;
1.233 - }
1.234 - __w->_M_color = __x_parent->_M_color;
1.235 - __x_parent->_M_color = _S_rb_tree_black;
1.236 - if (__w->_M_right) __w->_M_right->_M_color = _S_rb_tree_black;
1.237 - _Rotate_left(__x_parent, __root);
1.238 - break;
1.239 - }
1.240 - } else { // same as above, with _M_right <-> _M_left.
1.241 - _Rb_tree_node_base* __w = __x_parent->_M_left;
1.242 - if (__w->_M_color == _S_rb_tree_red) {
1.243 - __w->_M_color = _S_rb_tree_black;
1.244 - __x_parent->_M_color = _S_rb_tree_red;
1.245 - _Rotate_right(__x_parent, __root);
1.246 - __w = __x_parent->_M_left;
1.247 - }
1.248 - if ((__w->_M_right == 0 ||
1.249 - __w->_M_right->_M_color == _S_rb_tree_black) && (__w->_M_left == 0 ||
1.250 - __w->_M_left->_M_color == _S_rb_tree_black)) {
1.251 - __w->_M_color = _S_rb_tree_red;
1.252 - __x = __x_parent;
1.253 - __x_parent = __x_parent->_M_parent;
1.254 - } else {
1.255 - if (__w->_M_left == 0 ||
1.256 - __w->_M_left->_M_color == _S_rb_tree_black) {
1.257 - if (__w->_M_right) __w->_M_right->_M_color = _S_rb_tree_black;
1.258 - __w->_M_color = _S_rb_tree_red;
1.259 - _Rotate_left(__w, __root);
1.260 - __w = __x_parent->_M_left;
1.261 - }
1.262 - __w->_M_color = __x_parent->_M_color;
1.263 - __x_parent->_M_color = _S_rb_tree_black;
1.264 - if (__w->_M_left) __w->_M_left->_M_color = _S_rb_tree_black;
1.265 - _Rotate_right(__x_parent, __root);
1.266 - break;
1.267 - }
1.268 - }
1.269 - if (__x) __x->_M_color = _S_rb_tree_black;
1.270 - }
1.271 - return __y;
1.272 -}
1.273 -
1.274 -template <class _Dummy> _Rb_tree_node_base* _STLP_CALL
1.275 -_Rb_global<_Dummy>::_M_decrement(_Rb_tree_node_base* _M_node)
1.276 -{
1.277 - if (_M_node->_M_color == _S_rb_tree_red && _M_node->_M_parent->_M_parent == _M_node)
1.278 - _M_node = _M_node->_M_right;
1.279 - else if (_M_node->_M_left != 0) {
1.280 - _Base_ptr __y = _M_node->_M_left;
1.281 - while (__y->_M_right != 0)
1.282 - __y = __y->_M_right;
1.283 - _M_node = __y;
1.284 - }
1.285 - else {
1.286 - _Base_ptr __y = _M_node->_M_parent;
1.287 - while (_M_node == __y->_M_left) {
1.288 - _M_node = __y;
1.289 - __y = __y->_M_parent;
1.290 - }
1.291 - _M_node = __y;
1.292 - }
1.293 - return _M_node;
1.294 -}
1.295 -
1.296 -template <class _Dummy> _Rb_tree_node_base* _STLP_CALL
1.297 -_Rb_global<_Dummy>::_M_increment(_Rb_tree_node_base* _M_node)
1.298 -{
1.299 - if (_M_node->_M_right != 0) {
1.300 - _M_node = _M_node->_M_right;
1.301 - while (_M_node->_M_left != 0)
1.302 - _M_node = _M_node->_M_left;
1.303 - }
1.304 - else {
1.305 - _Base_ptr __y = _M_node->_M_parent;
1.306 - while (_M_node == __y->_M_right) {
1.307 - _M_node = __y;
1.308 - __y = __y->_M_parent;
1.309 - }
1.310 - if (_M_node->_M_right != __y)
1.311 - _M_node = __y;
1.312 - }
1.313 - return _M_node;
1.314 -}
1.315 -
1.316 -#endif /* defined (__BUILDING_STLPORT) || ! defined (_STLP_OWN_IOSTREAMS) */
1.317 -
1.318 -
1.319 -template <class _Key, class _Value, class _KeyOfValue,
1.320 - 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)
1.321 -{
1.322 - if (this != &__x) {
1.323 - // Note that _Key may be a constant type.
1.324 - clear();
1.325 - _M_node_count = 0;
1.326 - _M_key_compare = __x._M_key_compare;
1.327 - if (__x._M_root() == 0) {
1.328 - _M_root() = 0;
1.329 - _M_leftmost() = this->_M_header._M_data;
1.330 - _M_rightmost() = this->_M_header._M_data;
1.331 - }
1.332 - else {
1.333 - _M_root() = _M_copy(__x._M_root(), this->_M_header._M_data);
1.334 - _M_leftmost() = _S_minimum(_M_root());
1.335 - _M_rightmost() = _S_maximum(_M_root());
1.336 - _M_node_count = __x._M_node_count;
1.337 - }
1.338 - }
1.339 - return *this;
1.340 -}
1.341 -
1.342 -// CRP 7/10/00 inserted argument __w_, which is another hint (meant to
1.343 -// act like __x_ and ignore a portion of the if conditions -- specify
1.344 -// __w_ != 0 to bypass comparison as false or __x_ != 0 to bypass
1.345 -// comparison as true)
1.346 -template <class _Key, class _Value, class _KeyOfValue,
1.347 - class _Compare, class _Alloc> __iterator__
1.348 -_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> ::_M_insert(_Rb_tree_node_base* __x_, _Rb_tree_node_base* __y_, const _Value& __v,
1.349 - _Rb_tree_node_base* __w_)
1.350 -{
1.351 - _Link_type __w = (_Link_type) __w_;
1.352 - _Link_type __x = (_Link_type) __x_;
1.353 - _Link_type __y = (_Link_type) __y_;
1.354 - _Link_type __z;
1.355 -
1.356 - if ( __y == this->_M_header._M_data ||
1.357 - ( __w == 0 && // If w != 0, the remainder fails to false
1.358 - ( __x != 0 || // If x != 0, the remainder succeeds to true
1.359 - _M_key_compare( _KeyOfValue()(__v), _S_key(__y) ) )
1.360 - )
1.361 - ) {
1.362 -
1.363 - __z = _M_create_node(__v);
1.364 - _S_left(__y) = __z; // also makes _M_leftmost() = __z
1.365 - // when __y == _M_header
1.366 - if (__y == this->_M_header._M_data) {
1.367 - _M_root() = __z;
1.368 - _M_rightmost() = __z;
1.369 - }
1.370 - else if (__y == _M_leftmost())
1.371 - _M_leftmost() = __z; // maintain _M_leftmost() pointing to min node
1.372 - }
1.373 - else {
1.374 - __z = _M_create_node(__v);
1.375 - _S_right(__y) = __z;
1.376 - if (__y == _M_rightmost())
1.377 - _M_rightmost() = __z; // maintain _M_rightmost() pointing to max node
1.378 - }
1.379 - _S_parent(__z) = __y;
1.380 - _S_left(__z) = 0;
1.381 - _S_right(__z) = 0;
1.382 - _Rb_global_inst::_Rebalance(__z, this->_M_header._M_data->_M_parent);
1.383 - ++_M_node_count;
1.384 - return iterator(__z);
1.385 -}
1.386 -
1.387 -template <class _Key, class _Value, class _KeyOfValue,
1.388 - class _Compare, class _Alloc> __iterator__
1.389 -_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> ::insert_equal(const _Value& __v)
1.390 -{
1.391 - _Link_type __y = this->_M_header._M_data;
1.392 - _Link_type __x = _M_root();
1.393 - while (__x != 0) {
1.394 - __y = __x;
1.395 - __x = _M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
1.396 - _S_left(__x) : _S_right(__x);
1.397 - }
1.398 - return _M_insert(__x, __y, __v);
1.399 -}
1.400 -
1.401 -
1.402 -template <class _Key, class _Value, class _KeyOfValue,
1.403 - 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)
1.404 -{
1.405 - _Link_type __y = this->_M_header._M_data;
1.406 - _Link_type __x = _M_root();
1.407 - bool __comp = true;
1.408 - while (__x != 0) {
1.409 - __y = __x;
1.410 - __comp = _M_key_compare(_KeyOfValue()(__v), _S_key(__x));
1.411 - __x = __comp ? _S_left(__x) : _S_right(__x);
1.412 - }
1.413 - iterator __j = iterator(__y);
1.414 - if (__comp)
1.415 - if (__j == begin())
1.416 - return pair<iterator,bool>(_M_insert(/* __x*/ __y, __y, __v), true);
1.417 - else
1.418 - --__j;
1.419 - if (_M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
1.420 - return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
1.421 - return pair<iterator,bool>(__j, false);
1.422 -}
1.423 -
1.424 -// Modifications CRP 7/10/00 as noted to improve conformance and
1.425 -// efficiency.
1.426 -template <class _Key, class _Value, class _KeyOfValue,
1.427 - class _Compare, class _Alloc> __iterator__
1.428 -_Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc> ::insert_unique(iterator __position, const _Value& __v)
1.429 -{
1.430 - if (__position._M_node == this->_M_header._M_data->_M_left) { // begin()
1.431 -
1.432 - // if the container is empty, fall back on insert_unique.
1.433 - if (size() <= 0)
1.434 - return insert_unique(__v).first;
1.435 -
1.436 - if ( _M_key_compare(_KeyOfValue()(__v), _S_key(__position._M_node)))
1.437 - return _M_insert(__position._M_node, __position._M_node, __v);
1.438 - // first argument just needs to be non-null
1.439 - else
1.440 - {
1.441 - bool __comp_pos_v = _M_key_compare( _S_key(__position._M_node), _KeyOfValue()(__v) );
1.442 -
1.443 - if (__comp_pos_v == false) // compare > and compare < both false so compare equal
1.444 - return __position;
1.445 - //Below __comp_pos_v == true
1.446 -
1.447 - // Standard-conformance - does the insertion point fall immediately AFTER
1.448 - // the hint?
1.449 - iterator __after = __position;
1.450 - ++__after;
1.451 -
1.452 - // Check for only one member -- in that case, __position points to itself,
1.453 - // and attempting to increment will cause an infinite loop.
1.454 - if (__after._M_node == this->_M_header._M_data)
1.455 - // Check guarantees exactly one member, so comparison was already
1.456 - // performed and we know the result; skip repeating it in _M_insert
1.457 - // by specifying a non-zero fourth argument.
1.458 - return _M_insert(0, __position._M_node, __v, __position._M_node);
1.459 -
1.460 -
1.461 - // All other cases:
1.462 -
1.463 - // Optimization to catch insert-equivalent -- save comparison results,
1.464 - // and we get this for free.
1.465 - if(_M_key_compare( _KeyOfValue()(__v), _S_key(__after._M_node) )) {
1.466 - if (_S_right(__position._M_node) == 0)
1.467 - return _M_insert(0, __position._M_node, __v, __position._M_node);
1.468 - else
1.469 - return _M_insert(__after._M_node, __after._M_node, __v);
1.470 - } else {
1.471 - return insert_unique(__v).first;
1.472 - }
1.473 - }
1.474 -
1.475 - } else if (__position._M_node == this->_M_header._M_data) { // end()
1.476 - if (_M_key_compare(_S_key(_M_rightmost()), _KeyOfValue()(__v)))
1.477 - // pass along to _M_insert that it can skip comparing
1.478 - // v, Key ; since compare Key, v was true, compare v, Key must be false.
1.479 - return _M_insert(0, _M_rightmost(), __v, __position._M_node); // Last argument only needs to be non-null
1.480 - else
1.481 - return insert_unique(__v).first;
1.482 - } else {
1.483 - iterator __before = __position;
1.484 - --__before;
1.485 -
1.486 - bool __comp_v_pos = _M_key_compare(_KeyOfValue()(__v), _S_key(__position._M_node));
1.487 -
1.488 - if (__comp_v_pos
1.489 - && _M_key_compare( _S_key(__before._M_node), _KeyOfValue()(__v) )) {
1.490 -
1.491 - if (_S_right(__before._M_node) == 0)
1.492 - return _M_insert(0, __before._M_node, __v, __before._M_node); // Last argument only needs to be non-null
1.493 - else
1.494 - return _M_insert(__position._M_node, __position._M_node, __v);
1.495 - // first argument just needs to be non-null
1.496 - } else
1.497 - {
1.498 - // Does the insertion point fall immediately AFTER the hint?
1.499 - iterator __after = __position;
1.500 - ++__after;
1.501 -
1.502 - // Optimization to catch equivalent cases and avoid unnecessary comparisons
1.503 - bool __comp_pos_v = !__comp_v_pos; // Stored this result earlier
1.504 - // If the earlier comparison was true, this comparison doesn't need to be
1.505 - // performed because it must be false. However, if the earlier comparison
1.506 - // was false, we need to perform this one because in the equal case, both will
1.507 - // be false.
1.508 - if (!__comp_v_pos) __comp_pos_v = _M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__v));
1.509 -
1.510 - if ( (!__comp_v_pos) // comp_v_pos true implies comp_v_pos false
1.511 - && __comp_pos_v
1.512 - && (__after._M_node == this->_M_header._M_data ||
1.513 - _M_key_compare( _KeyOfValue()(__v), _S_key(__after._M_node) ))) {
1.514 -
1.515 - if (_S_right(__position._M_node) == 0)
1.516 - return _M_insert(0, __position._M_node, __v, __position._M_node);
1.517 - else
1.518 - return _M_insert(__after._M_node, __after._M_node, __v);
1.519 - } else {
1.520 - // Test for equivalent case
1.521 - if (__comp_v_pos == __comp_pos_v)
1.522 - return __position;
1.523 - else
1.524 - return insert_unique(__v).first;
1.525 - }
1.526 - }
1.527 - }
1.528 -}
1.529 -
1.530 -
1.531 -template <class _Key, class _Value, class _KeyOfValue,
1.532 - class _Compare, class _Alloc> __iterator__
1.533 -_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> ::insert_equal(iterator __position, const _Value& __v)
1.534 -{
1.535 - if (__position._M_node == this->_M_header._M_data->_M_left) { // begin()
1.536 -
1.537 - // Check for zero members
1.538 - if (size() <= 0)
1.539 - return insert_equal(__v);
1.540 -
1.541 - if (!_M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__v)))
1.542 - return _M_insert(__position._M_node, __position._M_node, __v);
1.543 - else {
1.544 - // Check for only one member
1.545 - if (__position._M_node->_M_left == __position._M_node)
1.546 - // Unlike insert_unique, can't avoid doing a comparison here.
1.547 - return _M_insert(0, __position._M_node, __v);
1.548 -
1.549 - // All other cases:
1.550 - // Standard-conformance - does the insertion point fall immediately AFTER
1.551 - // the hint?
1.552 - iterator __after = __position;
1.553 - ++__after;
1.554 -
1.555 - // Already know that compare(pos, v) must be true!
1.556 - // Therefore, we want to know if compare(after, v) is false.
1.557 - // (i.e., we now pos < v, now we want to know if v <= after)
1.558 - // If not, invalid hint.
1.559 - if ( __after._M_node==this->_M_header._M_data ||
1.560 - !_M_key_compare( _S_key(__after._M_node), _KeyOfValue()(__v) ) ) {
1.561 - if (_S_right(__position._M_node) == 0)
1.562 - return _M_insert(0, __position._M_node, __v, __position._M_node);
1.563 - else
1.564 - return _M_insert(__after._M_node, __after._M_node, __v);
1.565 - } else // Invalid hint
1.566 - return insert_equal(__v);
1.567 - }
1.568 - } else if (__position._M_node == this->_M_header._M_data) {// end()
1.569 - if (!_M_key_compare(_KeyOfValue()(__v), _S_key(_M_rightmost())))
1.570 - return _M_insert(0, _M_rightmost(), __v, __position._M_node); // Last argument only needs to be non-null
1.571 - else
1.572 - return insert_equal(__v);
1.573 - } else {
1.574 - iterator __before = __position;
1.575 - --__before;
1.576 - // store the result of the comparison between pos and v so
1.577 - // that we don't have to do it again later. Note that this reverses the shortcut
1.578 - // on the if, possibly harming efficiency in comparisons; I think the harm will
1.579 - // be negligible, and to do what I want to do (save the result of a comparison so
1.580 - // that it can be re-used) there is no alternative. Test here is for before <= v <= pos.
1.581 - bool __comp_pos_v = _M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__v));
1.582 - if (!__comp_pos_v
1.583 - && !_M_key_compare(_KeyOfValue()(__v), _S_key(__before._M_node))) {
1.584 - if (_S_right(__before._M_node) == 0)
1.585 - return _M_insert(0, __before._M_node, __v, __before._M_node); // Last argument only needs to be non-null
1.586 - else
1.587 - return _M_insert(__position._M_node, __position._M_node, __v);
1.588 - } else {
1.589 - // Does the insertion point fall immediately AFTER the hint?
1.590 - // Test for pos < v <= after
1.591 - iterator __after = __position;
1.592 - ++__after;
1.593 -
1.594 - if (__comp_pos_v
1.595 - && ( __after._M_node==this->_M_header._M_data
1.596 - || !_M_key_compare( _S_key(__after._M_node), _KeyOfValue()(__v) ) ) ) {
1.597 - if (_S_right(__position._M_node) == 0)
1.598 - return _M_insert(0, __position._M_node, __v, __position._M_node);
1.599 - else
1.600 - return _M_insert(__after._M_node, __after._M_node, __v);
1.601 - } else // Invalid hint
1.602 - return insert_equal(__v);
1.603 - }
1.604 - }
1.605 -}
1.606 -
1.607 -template <class _Key, class _Value, class _KeyOfValue, class _Compare, class _Alloc> _Rb_tree_node<_Value>*
1.608 -_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> ::_M_copy(_Rb_tree_node<_Value>* __x, _Rb_tree_node<_Value>* __p)
1.609 -{
1.610 - // structural copy. __x and __p must be non-null.
1.611 - _STLP_LEAVE_VOLATILE _Link_type __top = _M_clone_node(__x);
1.612 - __top->_M_parent = __p;
1.613 -
1.614 - _STLP_TRY {
1.615 - if (__x->_M_right)
1.616 - __top->_M_right = _M_copy(_S_right(__x), __top);
1.617 - __p = __top;
1.618 - __x = _S_left(__x);
1.619 -
1.620 - while (__x != 0) {
1.621 - _Link_type __y = _M_clone_node(__x);
1.622 - __p->_M_left = __y;
1.623 - __y->_M_parent = __p;
1.624 - if (__x->_M_right)
1.625 - __y->_M_right = _M_copy(_S_right(__x), __y);
1.626 - __p = __y;
1.627 - __x = _S_left(__x);
1.628 - }
1.629 - }
1.630 - _STLP_UNWIND(_M_erase(__top));
1.631 -
1.632 - return __top;
1.633 -}
1.634 -
1.635 -// this has to stay out-of-line : it's recursive
1.636 -template <class _Key, class _Value, class _KeyOfValue,
1.637 - class _Compare, class _Alloc> void
1.638 -_Rb_tree<_Key,_Value,_KeyOfValue,
1.639 - _Compare,_Alloc>::_M_erase(_Rb_tree_node<_Value>* __x)
1.640 -{
1.641 - // erase without rebalancing
1.642 - while (__x != 0) {
1.643 - _M_erase(_S_right(__x));
1.644 - _Link_type __y = _S_left(__x);
1.645 - _STLP_STD::_Destroy(&__x->_M_value_field);
1.646 - this->_M_header.deallocate(__x,1);
1.647 - __x = __y;
1.648 - }
1.649 -}
1.650 -
1.651 -template <class _Key, class _Value, class _KeyOfValue,
1.652 - class _Compare, class _Alloc> __size_type__
1.653 -_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> ::count(const _Key& __k) const
1.654 -{
1.655 - pair<const_iterator, const_iterator> __p = equal_range(__k);
1.656 - size_type __n = distance(__p.first, __p.second);
1.657 - return __n;
1.658 -}
1.659 -
1.660 -inline int
1.661 -__black_count(_Rb_tree_node_base* __node, _Rb_tree_node_base* __root)
1.662 -{
1.663 - if (__node == 0)
1.664 - return 0;
1.665 - else {
1.666 - int __bc = __node->_M_color == _S_rb_tree_black ? 1 : 0;
1.667 - if (__node == __root)
1.668 - return __bc;
1.669 - else
1.670 - return __bc + __black_count(__node->_M_parent, __root);
1.671 - }
1.672 -}
1.673 -
1.674 -template <class _Key, class _Value, class _KeyOfValue,
1.675 - class _Compare, class _Alloc> bool _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
1.676 -{
1.677 - if (_M_node_count == 0 || begin() == end())
1.678 - return _M_node_count == 0 && begin() == end() && this->_M_header._M_data->_M_left == this->_M_header._M_data
1.679 - && this->_M_header._M_data->_M_right == this->_M_header._M_data;
1.680 -
1.681 - int __len = __black_count(_M_leftmost(), _M_root());
1.682 - for (const_iterator __it = begin(); __it != end(); ++__it) {
1.683 - _Link_type __x = (_Link_type) __it._M_node;
1.684 - _Link_type __L = _S_left(__x);
1.685 - _Link_type __R = _S_right(__x);
1.686 -
1.687 - if (__x->_M_color == _S_rb_tree_red)
1.688 - if ((__L && __L->_M_color == _S_rb_tree_red) ||
1.689 - (__R && __R->_M_color == _S_rb_tree_red))
1.690 - return false;
1.691 -
1.692 - if (__L && _M_key_compare(_S_key(__x), _S_key(__L)))
1.693 - return false;
1.694 - if (__R && _M_key_compare(_S_key(__R), _S_key(__x)))
1.695 - return false;
1.696 -
1.697 - if (!__L && !__R && __black_count(__x, _M_root()) != __len)
1.698 - return false;
1.699 - }
1.700 -
1.701 - if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
1.702 - return false;
1.703 - if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
1.704 - return false;
1.705 -
1.706 - return true;
1.707 -}
1.708 -_STLP_END_NAMESPACE
1.709 -
1.710 -# undef __iterator__
1.711 -# undef iterator
1.712 -# undef __size_type__
1.713 -
1.714 -#endif /* _STLP_TREE_C */
1.715 -
1.716 -// Local Variables:
1.717 -// mode:C++
1.718 -// End: