1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/tools/stlport/stl/_tree.h Wed Mar 31 12:33:34 2010 +0100
1.3 @@ -0,0 +1,679 @@
1.4 +/*
1.5 + *
1.6 + * Copyright (c) 1994
1.7 + * Hewlett-Packard Company
1.8 + *
1.9 + * Copyright (c) 1996,1997
1.10 + * Silicon Graphics Computer Systems, Inc.
1.11 + *
1.12 + * Copyright (c) 1997
1.13 + * Moscow Center for SPARC Technology
1.14 + *
1.15 + * Copyright (c) 1999
1.16 + * Boris Fomitchev
1.17 + *
1.18 + * This material is provided "as is", with absolutely no warranty expressed
1.19 + * or implied. Any use is at your own risk.
1.20 + *
1.21 + * Permission to use or copy this software for any purpose is hereby granted
1.22 + * without fee, provided the above notices are retained on all copies.
1.23 + * Permission to modify the code and to distribute modified code is granted,
1.24 + * provided the above notices are retained, and a notice that the code was
1.25 + * modified is included with the above copyright notice.
1.26 + *
1.27 + */
1.28 +
1.29 +/* NOTE: This is an internal header file, included by other STL headers.
1.30 + * You should not attempt to use it directly.
1.31 + */
1.32 +
1.33 +#ifndef _STLP_INTERNAL_TREE_H
1.34 +#define _STLP_INTERNAL_TREE_H
1.35 +
1.36 +/*
1.37 +
1.38 +Red-black tree class, designed for use in implementing STL
1.39 +associative containers (set, multiset, map, and multimap). The
1.40 +insertion and deletion algorithms are based on those in Cormen,
1.41 +Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 1990),
1.42 +except that
1.43 +
1.44 +(1) the header cell is maintained with links not only to the root
1.45 +but also to the leftmost node of the tree, to enable constant time
1.46 +begin(), and to the rightmost node of the tree, to enable linear time
1.47 +performance when used with the generic set algorithms (set_union,
1.48 +etc.);
1.49 +
1.50 +(2) when a node being deleted has two children its successor node is
1.51 +relinked into its place, rather than copied, so that the only
1.52 +iterators invalidated are those referring to the deleted node.
1.53 +
1.54 +*/
1.55 +
1.56 +#ifndef _STLP_INTERNAL_ALGOBASE_H
1.57 +# include <stl/_algobase.h>
1.58 +#endif
1.59 +
1.60 +#ifndef _STLP_INTERNAL_ALLOC_H
1.61 +# include <stl/_alloc.h>
1.62 +#endif
1.63 +
1.64 +#ifndef _STLP_INTERNAL_ITERATOR_H
1.65 +# include <stl/_iterator.h>
1.66 +#endif
1.67 +
1.68 +#ifndef _STLP_INTERNAL_CONSTRUCT_H
1.69 +# include <stl/_construct.h>
1.70 +#endif
1.71 +
1.72 +#ifndef _STLP_INTERNAL_FUNCTION_BASE_H
1.73 +# include <stl/_function_base.h>
1.74 +#endif
1.75 +
1.76 +_STLP_BEGIN_NAMESPACE
1.77 +
1.78 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.79 +
1.80 +typedef bool _Rb_tree_Color_type;
1.81 +//const _Rb_tree_Color_type _S_rb_tree_red = false;
1.82 +//const _Rb_tree_Color_type _S_rb_tree_black = true;
1.83 +
1.84 +#define _S_rb_tree_red false
1.85 +#define _S_rb_tree_black true
1.86 +
1.87 +struct _Rb_tree_node_base {
1.88 + typedef _Rb_tree_Color_type _Color_type;
1.89 + typedef _Rb_tree_node_base* _Base_ptr;
1.90 +
1.91 + _Color_type _M_color;
1.92 + _Base_ptr _M_parent;
1.93 + _Base_ptr _M_left;
1.94 + _Base_ptr _M_right;
1.95 +
1.96 + static _Base_ptr _STLP_CALL _S_minimum(_Base_ptr __x) {
1.97 + while (__x->_M_left != 0) __x = __x->_M_left;
1.98 + return __x;
1.99 + }
1.100 +
1.101 + static _Base_ptr _STLP_CALL _S_maximum(_Base_ptr __x) {
1.102 + while (__x->_M_right != 0) __x = __x->_M_right;
1.103 + return __x;
1.104 + }
1.105 +};
1.106 +
1.107 +template <class _Value>
1.108 +struct _Rb_tree_node : public _Rb_tree_node_base {
1.109 + _Value _M_value_field;
1.110 + __TRIVIAL_STUFF(_Rb_tree_node)
1.111 +};
1.112 +
1.113 +struct _Rb_tree_base_iterator;
1.114 +
1.115 +template <class _Dummy>
1.116 +class _Rb_global {
1.117 +public:
1.118 + typedef _Rb_tree_node_base* _Base_ptr;
1.119 + // those used to be global functions
1.120 + static void _STLP_CALL _Rebalance(_Base_ptr __x, _Base_ptr& __root);
1.121 + static _Base_ptr _STLP_CALL _Rebalance_for_erase(_Base_ptr __z,
1.122 + _Base_ptr& __root,
1.123 + _Base_ptr& __leftmost,
1.124 + _Base_ptr& __rightmost);
1.125 + // those are from _Rb_tree_base_iterator - moved here to reduce code bloat
1.126 + // moved here to reduce code bloat without templatizing _Rb_tree_base_iterator
1.127 + static _Base_ptr _STLP_CALL _M_increment (_Base_ptr);
1.128 + static _Base_ptr _STLP_CALL _M_decrement (_Base_ptr);
1.129 + static void _STLP_CALL _Rotate_left (_Base_ptr __x, _Base_ptr& __root);
1.130 + static void _STLP_CALL _Rotate_right(_Base_ptr __x, _Base_ptr& __root);
1.131 +};
1.132 +
1.133 +# if defined (_STLP_USE_TEMPLATE_EXPORT)
1.134 +_STLP_EXPORT_TEMPLATE_CLASS _Rb_global<bool>;
1.135 +# endif
1.136 +
1.137 +typedef _Rb_global<bool> _Rb_global_inst;
1.138 +
1.139 +struct _Rb_tree_base_iterator {
1.140 + typedef _Rb_tree_node_base* _Base_ptr;
1.141 + typedef bidirectional_iterator_tag iterator_category;
1.142 + typedef ptrdiff_t difference_type;
1.143 + _Base_ptr _M_node;
1.144 + _Rb_tree_base_iterator() : _M_node(0) {}
1.145 + _Rb_tree_base_iterator(_Base_ptr __x) : _M_node(__x) {}
1.146 +};
1.147 +
1.148 +template <class _Value, class _Traits>
1.149 +struct _Rb_tree_iterator : public _Rb_tree_base_iterator {
1.150 + typedef _Value value_type;
1.151 + typedef typename _Traits::reference reference;
1.152 + typedef typename _Traits::pointer pointer;
1.153 + typedef _Rb_tree_iterator<_Value, _Traits> _Self;
1.154 + typedef _Rb_tree_node_base* _Base_ptr;
1.155 + typedef _Rb_tree_node<_Value>* _Link_type;
1.156 +
1.157 + typedef typename _Traits::_NonConstTraits _NonConstTraits;
1.158 + typedef _Rb_tree_iterator<_Value, _NonConstTraits> iterator;
1.159 + typedef typename _Traits::_ConstTraits _ConstTraits;
1.160 + typedef _Rb_tree_iterator<_Value, _ConstTraits> const_iterator;
1.161 +
1.162 + _Rb_tree_iterator() {}
1.163 +#if !defined (_STLP_DEBUG)
1.164 + /* In STL debug mode we need this constructor implicit for the pointer
1.165 + * specialization implementation.
1.166 + */
1.167 + explicit
1.168 +#endif
1.169 + _Rb_tree_iterator(_Base_ptr __x) : _Rb_tree_base_iterator(__x) {}
1.170 + //copy constructor for iterator and constructor from iterator for const_iterator
1.171 + _Rb_tree_iterator(const iterator& __it) : _Rb_tree_base_iterator(__it._M_node) {}
1.172 +
1.173 + reference operator*() const {
1.174 + return __STATIC_CAST(_Link_type, _M_node)->_M_value_field;
1.175 + }
1.176 +
1.177 + _STLP_DEFINE_ARROW_OPERATOR
1.178 +
1.179 + _Self& operator++() {
1.180 + _M_node = _Rb_global_inst::_M_increment(_M_node);
1.181 + return *this;
1.182 + }
1.183 + _Self operator++(int) {
1.184 + _Self __tmp = *this;
1.185 + ++(*this);
1.186 + return __tmp;
1.187 + }
1.188 +
1.189 + _Self& operator--() {
1.190 + _M_node = _Rb_global_inst::_M_decrement(_M_node);
1.191 + return *this;
1.192 + }
1.193 + _Self operator--(int) {
1.194 + _Self __tmp = *this;
1.195 + --(*this);
1.196 + return __tmp;
1.197 + }
1.198 +
1.199 + bool operator == (const_iterator __rhs) const {
1.200 + return _M_node == __rhs._M_node;
1.201 + }
1.202 + bool operator != (const_iterator __rhs) const {
1.203 + return _M_node != __rhs._M_node;
1.204 + }
1.205 +};
1.206 +
1.207 +#if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
1.208 +_STLP_MOVE_TO_STD_NAMESPACE
1.209 +template <class _Value, class _Traits>
1.210 +struct __type_traits<_STLP_PRIV _Rb_tree_iterator<_Value, _Traits> > {
1.211 + typedef __false_type has_trivial_default_constructor;
1.212 + typedef __true_type has_trivial_copy_constructor;
1.213 + typedef __true_type has_trivial_assignment_operator;
1.214 + typedef __true_type has_trivial_destructor;
1.215 + typedef __false_type is_POD_type;
1.216 +};
1.217 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.218 +#endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
1.219 +
1.220 +#if defined (_STLP_USE_OLD_HP_ITERATOR_QUERIES)
1.221 +_STLP_MOVE_TO_STD_NAMESPACE
1.222 +template <class _Value, class _Traits>
1.223 +inline _Value* value_type(const _STLP_PRIV _Rb_tree_iterator<_Value, _Traits>&)
1.224 +{ return (_Value*)0; }
1.225 +inline bidirectional_iterator_tag iterator_category(const _STLP_PRIV _Rb_tree_base_iterator&)
1.226 +{ return bidirectional_iterator_tag(); }
1.227 +inline ptrdiff_t* distance_type(const _STLP_PRIV _Rb_tree_base_iterator&)
1.228 +{ return (ptrdiff_t*) 0; }
1.229 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.230 +#endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
1.231 +
1.232 +// Base class to help EH
1.233 +
1.234 +template <class _Tp, class _Alloc>
1.235 +class _Rb_tree_base {
1.236 +public:
1.237 + typedef _Rb_tree_node_base _Node_base;
1.238 + typedef _Rb_tree_node<_Tp> _Node;
1.239 + _STLP_FORCE_ALLOCATORS(_Tp, _Alloc)
1.240 + typedef typename _Alloc_traits<_Tp, _Alloc>::allocator_type allocator_type;
1.241 +private:
1.242 + typedef _Rb_tree_base<_Tp, _Alloc> _Self;
1.243 + typedef typename _Alloc_traits<_Node, _Alloc>::allocator_type _M_node_allocator_type;
1.244 + typedef _STLP_alloc_proxy<_Node_base, _Node, _M_node_allocator_type> _AllocProxy;
1.245 +
1.246 +public:
1.247 + allocator_type get_allocator() const {
1.248 + return _STLP_CONVERT_ALLOCATOR(_M_header, _Tp);
1.249 + }
1.250 +
1.251 +protected:
1.252 + _Rb_tree_base(const allocator_type& __a) :
1.253 + _M_header(_STLP_CONVERT_ALLOCATOR(__a, _Node), _Node_base() ) {
1.254 + _M_empty_initialize();
1.255 + }
1.256 + _Rb_tree_base(__move_source<_Self> src) :
1.257 + _M_header(__move_source<_AllocProxy>(src.get()._M_header)) {
1.258 + _M_rebind(&src.get()._M_header._M_data);
1.259 + src.get()._M_empty_initialize();
1.260 + }
1.261 + void _M_empty_initialize() {
1.262 + _M_header._M_data._M_color = _S_rb_tree_red; // used to distinguish header from
1.263 + // __root, in iterator.operator++
1.264 + _M_header._M_data._M_parent = 0;
1.265 + _M_header._M_data._M_left = &_M_header._M_data;
1.266 + _M_header._M_data._M_right = &_M_header._M_data;
1.267 + }
1.268 +
1.269 + void _M_rebind(_Node_base *__static_node) {
1.270 + if (_M_header._M_data._M_parent != 0) {
1.271 + _M_header._M_data._M_parent->_M_parent = &_M_header._M_data;
1.272 + }
1.273 + if (_M_header._M_data._M_right == __static_node) {
1.274 + _M_header._M_data._M_right = &_M_header._M_data;
1.275 + }
1.276 + if (_M_header._M_data._M_left == __static_node) {
1.277 + _M_header._M_data._M_left = &_M_header._M_data;
1.278 + }
1.279 + }
1.280 +
1.281 + _AllocProxy _M_header;
1.282 +};
1.283 +
1.284 +#if defined (_STLP_DEBUG)
1.285 +# define _Rb_tree _STLP_NON_DBG_NAME(Rb_tree)
1.286 +#endif
1.287 +
1.288 +template <class _Key, class _Compare,
1.289 + class _Value, class _KeyOfValue, class _Traits,
1.290 + _STLP_DEFAULT_ALLOCATOR_SELECT(_Value) >
1.291 +class _Rb_tree : public _Rb_tree_base<_Value, _Alloc> {
1.292 + typedef _Rb_tree_base<_Value, _Alloc> _Base;
1.293 + typedef _Rb_tree<_Key, _Compare, _Value, _KeyOfValue, _Traits, _Alloc> _Self;
1.294 +protected:
1.295 + typedef _Rb_tree_node_base * _Base_ptr;
1.296 + typedef _Rb_tree_node<_Value> _Node;
1.297 + typedef _Node* _Link_type;
1.298 + typedef _Rb_tree_Color_type _Color_type;
1.299 +public:
1.300 + typedef _Key key_type;
1.301 + typedef _Value value_type;
1.302 + typedef typename _Traits::pointer pointer;
1.303 + typedef const value_type* const_pointer;
1.304 + typedef typename _Traits::reference reference;
1.305 + typedef const value_type& const_reference;
1.306 + typedef size_t size_type;
1.307 + typedef ptrdiff_t difference_type;
1.308 + typedef bidirectional_iterator_tag _Iterator_category;
1.309 + typedef typename _Base::allocator_type allocator_type;
1.310 +
1.311 +protected:
1.312 +
1.313 + _STLP_KEY_TYPE_FOR_CONT_EXT(key_type)
1.314 + _Base_ptr _M_create_node(const value_type& __x) {
1.315 + _Link_type __tmp = this->_M_header.allocate(1);
1.316 + _STLP_TRY {
1.317 + _Copy_Construct(&__tmp->_M_value_field, __x);
1.318 + }
1.319 + _STLP_UNWIND(this->_M_header.deallocate(__tmp,1))
1.320 + _S_left(__tmp) = 0;
1.321 + _S_right(__tmp) = 0;
1.322 + return __tmp;
1.323 + }
1.324 +
1.325 + _Base_ptr _M_clone_node(_Base_ptr __x) {
1.326 + _Base_ptr __tmp = _M_create_node(_S_value(__x));
1.327 + _S_color(__tmp) = _S_color(__x);
1.328 + return __tmp;
1.329 + }
1.330 +
1.331 + size_type _M_node_count; // keeps track of size of tree
1.332 + _Compare _M_key_compare;
1.333 +
1.334 + _Base_ptr _M_root() const
1.335 + { return this->_M_header._M_data._M_parent; }
1.336 + _Base_ptr _M_leftmost() const
1.337 + { return this->_M_header._M_data._M_left; }
1.338 + _Base_ptr _M_rightmost() const
1.339 + { return this->_M_header._M_data._M_right; }
1.340 +
1.341 + _Base_ptr& _M_root()
1.342 + { return this->_M_header._M_data._M_parent; }
1.343 + _Base_ptr& _M_leftmost()
1.344 + { return this->_M_header._M_data._M_left; }
1.345 + _Base_ptr& _M_rightmost()
1.346 + { return this->_M_header._M_data._M_right; }
1.347 +
1.348 + static _Base_ptr& _STLP_CALL _S_left(_Base_ptr __x)
1.349 + { return __x->_M_left; }
1.350 + static _Base_ptr& _STLP_CALL _S_right(_Base_ptr __x)
1.351 + { return __x->_M_right; }
1.352 + static _Base_ptr& _STLP_CALL _S_parent(_Base_ptr __x)
1.353 + { return __x->_M_parent; }
1.354 + static value_type& _STLP_CALL _S_value(_Base_ptr __x)
1.355 + { return __STATIC_CAST(_Link_type, __x)->_M_value_field; }
1.356 + static const _Key& _STLP_CALL _S_key(_Base_ptr __x)
1.357 + { return _KeyOfValue()(_S_value(__x));}
1.358 + static _Color_type& _STLP_CALL _S_color(_Base_ptr __x)
1.359 + { return (_Color_type&)(__x->_M_color); }
1.360 +
1.361 + static _Base_ptr _STLP_CALL _S_minimum(_Base_ptr __x)
1.362 + { return _Rb_tree_node_base::_S_minimum(__x); }
1.363 +
1.364 + static _Base_ptr _STLP_CALL _S_maximum(_Base_ptr __x)
1.365 + { return _Rb_tree_node_base::_S_maximum(__x); }
1.366 +
1.367 +public:
1.368 + typedef typename _Traits::_NonConstTraits _NonConstTraits;
1.369 + typedef typename _Traits::_ConstTraits _ConstTraits;
1.370 + typedef _Rb_tree_iterator<value_type, _NonConstTraits> iterator;
1.371 + typedef _Rb_tree_iterator<value_type, _ConstTraits> const_iterator;
1.372 + _STLP_DECLARE_BIDIRECTIONAL_REVERSE_ITERATORS;
1.373 +
1.374 +private:
1.375 + iterator _M_insert(_Base_ptr __parent, const value_type& __val, _Base_ptr __on_left = 0, _Base_ptr __on_right = 0);
1.376 + _Base_ptr _M_copy(_Base_ptr __x, _Base_ptr __p);
1.377 + void _M_erase(_Base_ptr __x);
1.378 +
1.379 +public:
1.380 + // allocation/deallocation
1.381 + _Rb_tree()
1.382 + : _Rb_tree_base<_Value, _Alloc>(allocator_type()), _M_node_count(0), _M_key_compare(_Compare())
1.383 + {}
1.384 +
1.385 + _Rb_tree(const _Compare& __comp)
1.386 + : _Rb_tree_base<_Value, _Alloc>(allocator_type()), _M_node_count(0), _M_key_compare(__comp)
1.387 + {}
1.388 +
1.389 + _Rb_tree(const _Compare& __comp, const allocator_type& __a)
1.390 + : _Rb_tree_base<_Value, _Alloc>(__a), _M_node_count(0), _M_key_compare(__comp)
1.391 + {}
1.392 +
1.393 + _Rb_tree(const _Self& __x)
1.394 + : _Rb_tree_base<_Value, _Alloc>(__x.get_allocator()),
1.395 + _M_node_count(0), _M_key_compare(__x._M_key_compare) {
1.396 + if (__x._M_root() != 0) {
1.397 + _S_color(&this->_M_header._M_data) = _S_rb_tree_red;
1.398 + _M_root() = _M_copy(__x._M_root(), &this->_M_header._M_data);
1.399 + _M_leftmost() = _S_minimum(_M_root());
1.400 + _M_rightmost() = _S_maximum(_M_root());
1.401 + }
1.402 + _M_node_count = __x._M_node_count;
1.403 + }
1.404 +
1.405 + _Rb_tree(__move_source<_Self> src)
1.406 + : _Rb_tree_base<_Value, _Alloc>(__move_source<_Base>(src.get())),
1.407 + _M_node_count(src.get()._M_node_count),
1.408 + _M_key_compare(_AsMoveSource(src.get()._M_key_compare)) {
1.409 + src.get()._M_node_count = 0;
1.410 + }
1.411 +
1.412 + ~_Rb_tree() { clear(); }
1.413 + _Self& operator=(const _Self& __x);
1.414 +
1.415 +public:
1.416 + // accessors:
1.417 + _Compare key_comp() const { return _M_key_compare; }
1.418 +
1.419 + iterator begin() { return iterator(_M_leftmost()); }
1.420 + const_iterator begin() const { return const_iterator(_M_leftmost()); }
1.421 + iterator end() { return iterator(&this->_M_header._M_data); }
1.422 + const_iterator end() const { return const_iterator(__CONST_CAST(_Base_ptr, &this->_M_header._M_data)); }
1.423 +
1.424 + reverse_iterator rbegin() { return reverse_iterator(end()); }
1.425 + const_reverse_iterator rbegin() const
1.426 + { return const_reverse_iterator(end()); }
1.427 + reverse_iterator rend() { return reverse_iterator(begin()); }
1.428 + const_reverse_iterator rend() const
1.429 + { return const_reverse_iterator(begin()); }
1.430 + bool empty() const { return _M_node_count == 0; }
1.431 + size_type size() const { return _M_node_count; }
1.432 + size_type max_size() const { return size_type(-1); }
1.433 +
1.434 + void swap(_Self& __t) {
1.435 + if (__t.empty()) {
1.436 + if (this->empty()) return;
1.437 + __t._M_header.swap(this->_M_header);
1.438 + __t._M_rebind(&this->_M_header._M_data);
1.439 + this->_M_empty_initialize();
1.440 + }
1.441 + else if (this->empty()) {
1.442 + __t.swap(*this);
1.443 + return;
1.444 + }
1.445 + else {
1.446 + this->_M_header.swap(__t._M_header);
1.447 + this->_M_rebind(&__t._M_header._M_data);
1.448 + __t._M_rebind(&this->_M_header._M_data);
1.449 + }
1.450 + _STLP_STD::swap(_M_node_count, __t._M_node_count);
1.451 + _STLP_STD::swap(_M_key_compare, __t._M_key_compare);
1.452 + }
1.453 +
1.454 +public:
1.455 + // insert/erase
1.456 + pair<iterator,bool> insert_unique(const value_type& __x);
1.457 + iterator insert_equal(const value_type& __x);
1.458 +
1.459 + iterator insert_unique(iterator __pos, const value_type& __x);
1.460 + iterator insert_equal(iterator __pos, const value_type& __x);
1.461 +
1.462 +#if defined (_STLP_MEMBER_TEMPLATES)
1.463 + template<class _II> void insert_equal(_II __first, _II __last) {
1.464 + for ( ; __first != __last; ++__first)
1.465 + insert_equal(*__first);
1.466 + }
1.467 + template<class _II> void insert_unique(_II __first, _II __last) {
1.468 + for ( ; __first != __last; ++__first)
1.469 + insert_unique(*__first);
1.470 + }
1.471 +#else
1.472 + void insert_unique(const_iterator __first, const_iterator __last) {
1.473 + for ( ; __first != __last; ++__first)
1.474 + insert_unique(*__first);
1.475 + }
1.476 + void insert_unique(const value_type* __first, const value_type* __last) {
1.477 + for ( ; __first != __last; ++__first)
1.478 + insert_unique(*__first);
1.479 + }
1.480 + void insert_equal(const_iterator __first, const_iterator __last) {
1.481 + for ( ; __first != __last; ++__first)
1.482 + insert_equal(*__first);
1.483 + }
1.484 + void insert_equal(const value_type* __first, const value_type* __last) {
1.485 + for ( ; __first != __last; ++__first)
1.486 + insert_equal(*__first);
1.487 + }
1.488 +#endif
1.489 +
1.490 + void erase(iterator __pos) {
1.491 + _Base_ptr __x = _Rb_global_inst::_Rebalance_for_erase(__pos._M_node,
1.492 + this->_M_header._M_data._M_parent,
1.493 + this->_M_header._M_data._M_left,
1.494 + this->_M_header._M_data._M_right);
1.495 + _STLP_STD::_Destroy(&_S_value(__x));
1.496 + this->_M_header.deallocate(__STATIC_CAST(_Link_type, __x), 1);
1.497 + --_M_node_count;
1.498 + }
1.499 +
1.500 + size_type erase(const key_type& __x) {
1.501 + pair<iterator,iterator> __p = equal_range(__x);
1.502 + size_type __n = distance(__p.first, __p.second);
1.503 + erase(__p.first, __p.second);
1.504 + return __n;
1.505 + }
1.506 +
1.507 + size_type erase_unique(const key_type& __x) {
1.508 + iterator __i = find(__x);
1.509 + if (__i._M_node != &this->_M_header._M_data) {
1.510 + erase(__i);
1.511 + return 1;
1.512 + }
1.513 + return 0;
1.514 + }
1.515 +
1.516 + void erase(iterator __first, iterator __last) {
1.517 + if (__first._M_node == this->_M_header._M_data._M_left && // begin()
1.518 + __last._M_node == &this->_M_header._M_data) // end()
1.519 + clear();
1.520 + else
1.521 + while (__first != __last) erase(__first++);
1.522 + }
1.523 +
1.524 + void erase(const key_type* __first, const key_type* __last) {
1.525 + while (__first != __last) erase(*__first++);
1.526 + }
1.527 +
1.528 + void clear() {
1.529 + if (_M_node_count != 0) {
1.530 + _M_erase(_M_root());
1.531 + _M_leftmost() = &this->_M_header._M_data;
1.532 + _M_root() = 0;
1.533 + _M_rightmost() = &this->_M_header._M_data;
1.534 + _M_node_count = 0;
1.535 + }
1.536 + }
1.537 +
1.538 +public:
1.539 + // set operations:
1.540 + _STLP_TEMPLATE_FOR_CONT_EXT
1.541 + iterator find(const _KT& __k) { return iterator(_M_find(__k)); }
1.542 + _STLP_TEMPLATE_FOR_CONT_EXT
1.543 + const_iterator find(const _KT& __k) const { return const_iterator(_M_find(__k)); }
1.544 +private:
1.545 + _STLP_TEMPLATE_FOR_CONT_EXT
1.546 + _Base_ptr _M_find(const _KT& __k) const {
1.547 + _Base_ptr __y = __CONST_CAST(_Base_ptr, &this->_M_header._M_data); // Last node which is not less than __k.
1.548 + _Base_ptr __x = _M_root(); // Current node.
1.549 +
1.550 + while (__x != 0)
1.551 + if (!_M_key_compare(_S_key(__x), __k))
1.552 + __y = __x, __x = _S_left(__x);
1.553 + else
1.554 + __x = _S_right(__x);
1.555 +
1.556 + if (__y != &this->_M_header._M_data) {
1.557 + if (_M_key_compare(__k, _S_key(__y))) {
1.558 + __y = __CONST_CAST(_Base_ptr, &this->_M_header._M_data);
1.559 + }
1.560 + }
1.561 + return __y;
1.562 + }
1.563 +
1.564 + _STLP_TEMPLATE_FOR_CONT_EXT
1.565 + _Base_ptr _M_lower_bound(const _KT& __k) const {
1.566 + _Base_ptr __y = __CONST_CAST(_Base_ptr, &this->_M_header._M_data); /* Last node which is not less than __k. */
1.567 + _Base_ptr __x = _M_root(); /* Current node. */
1.568 +
1.569 + while (__x != 0)
1.570 + if (!_M_key_compare(_S_key(__x), __k))
1.571 + __y = __x, __x = _S_left(__x);
1.572 + else
1.573 + __x = _S_right(__x);
1.574 +
1.575 + return __y;
1.576 + }
1.577 +
1.578 + _STLP_TEMPLATE_FOR_CONT_EXT
1.579 + _Base_ptr _M_upper_bound(const _KT& __k) const {
1.580 + _Base_ptr __y = __CONST_CAST(_Base_ptr, &this->_M_header._M_data); /* Last node which is greater than __k. */
1.581 + _Base_ptr __x = _M_root(); /* Current node. */
1.582 +
1.583 + while (__x != 0)
1.584 + if (_M_key_compare(__k, _S_key(__x)))
1.585 + __y = __x, __x = _S_left(__x);
1.586 + else
1.587 + __x = _S_right(__x);
1.588 +
1.589 + return __y;
1.590 + }
1.591 +
1.592 +public:
1.593 + _STLP_TEMPLATE_FOR_CONT_EXT
1.594 + size_type count(const _KT& __x) const {
1.595 + pair<const_iterator, const_iterator> __p = equal_range(__x);
1.596 + return distance(__p.first, __p.second);
1.597 + }
1.598 + _STLP_TEMPLATE_FOR_CONT_EXT
1.599 + iterator lower_bound(const _KT& __x) { return iterator(_M_lower_bound(__x)); }
1.600 + _STLP_TEMPLATE_FOR_CONT_EXT
1.601 + const_iterator lower_bound(const _KT& __x) const { return const_iterator(_M_lower_bound(__x)); }
1.602 + _STLP_TEMPLATE_FOR_CONT_EXT
1.603 + iterator upper_bound(const _KT& __x) { return iterator(_M_upper_bound(__x)); }
1.604 + _STLP_TEMPLATE_FOR_CONT_EXT
1.605 + const_iterator upper_bound(const _KT& __x) const { return const_iterator(_M_upper_bound(__x)); }
1.606 + _STLP_TEMPLATE_FOR_CONT_EXT
1.607 + pair<iterator,iterator> equal_range(const _KT& __x)
1.608 + { return pair<iterator, iterator>(lower_bound(__x), upper_bound(__x)); }
1.609 + _STLP_TEMPLATE_FOR_CONT_EXT
1.610 + pair<const_iterator, const_iterator> equal_range(const _KT& __x) const
1.611 + { return pair<const_iterator, const_iterator>(lower_bound(__x), upper_bound(__x)); }
1.612 + _STLP_TEMPLATE_FOR_CONT_EXT
1.613 + pair<iterator,iterator> equal_range_unique(const _KT& __x) {
1.614 + pair<iterator, iterator> __p;
1.615 + __p.second = lower_bound(__x);
1.616 + if (__p.second._M_node != &this->_M_header._M_data &&
1.617 + !_M_key_compare(__x, _S_key(__p.second._M_node))) {
1.618 + __p.first = __p.second++;
1.619 + }
1.620 + else {
1.621 + __p.first = __p.second;
1.622 + }
1.623 + return __p;
1.624 + }
1.625 + _STLP_TEMPLATE_FOR_CONT_EXT
1.626 + pair<const_iterator, const_iterator> equal_range_unique(const _KT& __x) const {
1.627 + pair<const_iterator, const_iterator> __p;
1.628 + __p.second = lower_bound(__x);
1.629 + if (__p.second._M_node != &this->_M_header._M_data &&
1.630 + !_M_key_compare(__x, _S_key(__p.second._M_node))) {
1.631 + __p.first = __p.second++;
1.632 + }
1.633 + else {
1.634 + __p.first = __p.second;
1.635 + }
1.636 + return __p;
1.637 + }
1.638 +
1.639 +#if defined (_STLP_DEBUG)
1.640 +public:
1.641 + // Debugging.
1.642 + bool __rb_verify() const;
1.643 +#endif //_STLP_DEBUG
1.644 +};
1.645 +
1.646 +#if defined (_STLP_DEBUG)
1.647 +# undef _Rb_tree
1.648 +#endif
1.649 +
1.650 +_STLP_MOVE_TO_STD_NAMESPACE
1.651 +
1.652 +_STLP_END_NAMESPACE
1.653 +
1.654 +#if !defined (_STLP_LINK_TIME_INSTANTIATION)
1.655 +# include <stl/_tree.c>
1.656 +#endif
1.657 +
1.658 +#if defined (_STLP_DEBUG)
1.659 +# include <stl/debug/_tree.h>
1.660 +#endif
1.661 +
1.662 +_STLP_BEGIN_NAMESPACE
1.663 +
1.664 +#define _STLP_TEMPLATE_HEADER template <class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, class _Alloc>
1.665 +#define _STLP_TEMPLATE_CONTAINER _STLP_PRIV _Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc>
1.666 +#include <stl/_relops_cont.h>
1.667 +#undef _STLP_TEMPLATE_CONTAINER
1.668 +#undef _STLP_TEMPLATE_HEADER
1.669 +
1.670 +#if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
1.671 +template <class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, class _Alloc>
1.672 +struct __move_traits<_STLP_PRIV _Rb_tree<_Key, _Compare, _Value, _KeyOfValue, _Traits, _Alloc> >
1.673 + : _STLP_PRIV __move_traits_help2<_Compare, _Alloc> {};
1.674 +#endif
1.675 +
1.676 +_STLP_END_NAMESPACE
1.677 +
1.678 +#endif /* _STLP_INTERNAL_TREE_H */
1.679 +
1.680 +// Local Variables:
1.681 +// mode:C++
1.682 +// End: