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

Go to the documentation of this file.
00001 /*
00002  *
00003  * Copyright (c) 1994
00004  * Hewlett-Packard Company
00005  *
00006  * Copyright (c) 1996,1997
00007  * Silicon Graphics Computer Systems, Inc.
00008  *
00009  * Copyright (c) 1997
00010  * Moscow Center for SPARC Technology
00011  *
00012  * Copyright (c) 1999
00013  * Boris Fomitchev
00014  *
00015  * This material is provided "as is", with absolutely no warranty expressed
00016  * or implied. Any use is at your own risk.
00017  *
00018  * Permission to use or copy this software for any purpose is hereby granted
00019  * without fee, provided the above notices are retained on all copies.
00020  * Permission to modify the code and to distribute modified code is granted,
00021  * provided the above notices are retained, and a notice that the code was
00022  * modified is included with the above copyright notice.
00023  *
00024  */
00025 
00026 /* NOTE: This is an internal header file, included by other STL headers.
00027  *   You should not attempt to use it directly.
00028  */
00029 
00030 #ifndef _STLP_INTERNAL_TREE_H
00031 #define _STLP_INTERNAL_TREE_H
00032 
00033 /*
00034 
00035 Red-black tree class, designed for use in implementing STL
00036 associative containers (set, multiset, map, and multimap). The
00037 insertion and deletion algorithms are based on those in Cormen,
00038 Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 1990),
00039 except that
00040 
00041 (1) the header cell is maintained with links not only to the root
00042 but also to the leftmost node of the tree, to enable constant time
00043 begin(), and to the rightmost node of the tree, to enable linear time
00044 performance when used with the generic set algorithms (set_union,
00045 etc.);
00046 
00047 (2) when a node being deleted has two children its successor node is
00048 relinked into its place, rather than copied, so that the only
00049 iterators invalidated are those referring to the deleted node.
00050 
00051 */
00052 
00053 #ifndef _STLP_INTERNAL_ALGOBASE_H
00054 #  include <stl/_algobase.h>
00055 #endif
00056 
00057 #ifndef _STLP_INTERNAL_ALLOC_H
00058 #  include <stl/_alloc.h>
00059 #endif
00060 
00061 #ifndef _STLP_INTERNAL_ITERATOR_H
00062 #  include <stl/_iterator.h>
00063 #endif
00064 
00065 #ifndef _STLP_INTERNAL_CONSTRUCT_H
00066 #  include <stl/_construct.h>
00067 #endif
00068 
00069 #ifndef _STLP_INTERNAL_FUNCTION_BASE_H
00070 #  include <stl/_function_base.h>
00071 #endif
00072 
00073 _STLP_BEGIN_NAMESPACE
00074 
00075 _STLP_MOVE_TO_PRIV_NAMESPACE
00076 
00077 typedef bool _Rb_tree_Color_type;
00078 //const _Rb_tree_Color_type _S_rb_tree_red = false;
00079 //const _Rb_tree_Color_type _S_rb_tree_black = true;
00080 
00081 #define _S_rb_tree_red false
00082 #define _S_rb_tree_black true
00083 
00084 struct _Rb_tree_node_base {
00085   typedef _Rb_tree_Color_type _Color_type;
00086   typedef _Rb_tree_node_base* _Base_ptr;
00087 
00088   _Color_type _M_color;
00089   _Base_ptr _M_parent;
00090   _Base_ptr _M_left;
00091   _Base_ptr _M_right;
00092 
00093   static _Base_ptr _STLP_CALL _S_minimum(_Base_ptr __x) {
00094     while (__x->_M_left != 0) __x = __x->_M_left;
00095     return __x;
00096   }
00097 
00098   static _Base_ptr _STLP_CALL _S_maximum(_Base_ptr __x) {
00099     while (__x->_M_right != 0) __x = __x->_M_right;
00100     return __x;
00101   }
00102 };
00103 
00104 template <class _Value>
00105 struct _Rb_tree_node : public _Rb_tree_node_base {
00106   _Value _M_value_field;
00107   __TRIVIAL_STUFF(_Rb_tree_node)
00108 };
00109 
00110 struct _Rb_tree_base_iterator;
00111 
00112 template <class _Dummy>
00113 class _Rb_global {
00114 public:
00115   typedef _Rb_tree_node_base* _Base_ptr;
00116   // those used to be global functions
00117   static void _STLP_CALL _Rebalance(_Base_ptr __x, _Base_ptr& __root);
00118   static _Base_ptr _STLP_CALL _Rebalance_for_erase(_Base_ptr __z,
00119                                                    _Base_ptr& __root,
00120                                                    _Base_ptr& __leftmost,
00121                                                    _Base_ptr& __rightmost);
00122   // those are from _Rb_tree_base_iterator - moved here to reduce code bloat
00123   // moved here to reduce code bloat without templatizing _Rb_tree_base_iterator
00124   static _Base_ptr  _STLP_CALL _M_increment (_Base_ptr);
00125   static _Base_ptr  _STLP_CALL _M_decrement (_Base_ptr);
00126   static void       _STLP_CALL _Rotate_left (_Base_ptr __x, _Base_ptr& __root);
00127   static void       _STLP_CALL _Rotate_right(_Base_ptr __x, _Base_ptr& __root);
00128 };
00129 
00130 # if defined (_STLP_USE_TEMPLATE_EXPORT)
00131 _STLP_EXPORT_TEMPLATE_CLASS _Rb_global<bool>;
00132 # endif
00133 
00134 typedef _Rb_global<bool> _Rb_global_inst;
00135 
00136 struct _Rb_tree_base_iterator {
00137   typedef _Rb_tree_node_base*        _Base_ptr;
00138   typedef bidirectional_iterator_tag iterator_category;
00139   typedef ptrdiff_t                  difference_type;
00140   _Base_ptr _M_node;
00141   _Rb_tree_base_iterator() : _M_node(0) {}
00142   _Rb_tree_base_iterator(_Base_ptr __x) : _M_node(__x) {}
00143 };
00144 
00145 template <class _Value, class _Traits>
00146 struct _Rb_tree_iterator : public _Rb_tree_base_iterator {
00147   typedef _Value value_type;
00148   typedef typename _Traits::reference  reference;
00149   typedef typename _Traits::pointer    pointer;
00150   typedef _Rb_tree_iterator<_Value, _Traits> _Self;
00151   typedef _Rb_tree_node_base*    _Base_ptr;
00152   typedef _Rb_tree_node<_Value>* _Link_type;
00153 
00154   typedef typename _Traits::_NonConstTraits _NonConstTraits;
00155   typedef _Rb_tree_iterator<_Value, _NonConstTraits> iterator;
00156   typedef typename _Traits::_ConstTraits _ConstTraits;
00157   typedef _Rb_tree_iterator<_Value, _ConstTraits> const_iterator;
00158 
00159   _Rb_tree_iterator() {}
00160 #if !defined (_STLP_DEBUG)
00161   /* In STL debug mode we need this constructor implicit for the pointer
00162    * specialization implementation.
00163    */
00164   explicit
00165 #endif
00166   _Rb_tree_iterator(_Base_ptr __x) : _Rb_tree_base_iterator(__x) {}
00167   //copy constructor for iterator and constructor from iterator for const_iterator
00168   _Rb_tree_iterator(const iterator& __it) : _Rb_tree_base_iterator(__it._M_node) {}
00169 
00170   reference operator*() const {
00171     return __STATIC_CAST(_Link_type, _M_node)->_M_value_field;
00172   }
00173 
00174   _STLP_DEFINE_ARROW_OPERATOR
00175 
00176   _Self& operator++() {
00177     _M_node = _Rb_global_inst::_M_increment(_M_node);
00178     return *this;
00179   }
00180   _Self operator++(int) {
00181     _Self __tmp = *this;
00182     ++(*this);
00183     return __tmp;
00184   }
00185 
00186   _Self& operator--() {
00187     _M_node = _Rb_global_inst::_M_decrement(_M_node);
00188     return *this;
00189   }
00190   _Self operator--(int) {
00191     _Self __tmp = *this;
00192     --(*this);
00193     return __tmp;
00194   }
00195 
00196   bool operator == (const_iterator __rhs) const {
00197     return _M_node == __rhs._M_node;
00198   }
00199   bool operator != (const_iterator __rhs) const {
00200     return _M_node != __rhs._M_node;
00201   }
00202 };
00203 
00204 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
00205 _STLP_MOVE_TO_STD_NAMESPACE
00206 template <class _Value, class _Traits>
00207 struct __type_traits<_STLP_PRIV _Rb_tree_iterator<_Value, _Traits> > {
00208   typedef __false_type   has_trivial_default_constructor;
00209   typedef __true_type    has_trivial_copy_constructor;
00210   typedef __true_type    has_trivial_assignment_operator;
00211   typedef __true_type    has_trivial_destructor;
00212   typedef __false_type   is_POD_type;
00213 };
00214 _STLP_MOVE_TO_PRIV_NAMESPACE
00215 #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
00216 
00217 #if defined (_STLP_USE_OLD_HP_ITERATOR_QUERIES)
00218 _STLP_MOVE_TO_STD_NAMESPACE
00219 template <class _Value, class _Traits>
00220 inline _Value* value_type(const _STLP_PRIV _Rb_tree_iterator<_Value, _Traits>&)
00221 { return (_Value*)0; }
00222 inline bidirectional_iterator_tag iterator_category(const _STLP_PRIV _Rb_tree_base_iterator&)
00223 { return bidirectional_iterator_tag(); }
00224 inline ptrdiff_t* distance_type(const _STLP_PRIV _Rb_tree_base_iterator&)
00225 { return (ptrdiff_t*) 0; }
00226 _STLP_MOVE_TO_PRIV_NAMESPACE
00227 #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
00228 
00229 // Base class to help EH
00230 
00231 template <class _Tp, class _Alloc>
00232 class _Rb_tree_base {
00233 public:
00234   typedef _Rb_tree_node_base _Node_base;
00235   typedef _Rb_tree_node<_Tp> _Node;
00236   _STLP_FORCE_ALLOCATORS(_Tp, _Alloc)
00237   typedef typename _Alloc_traits<_Tp, _Alloc>::allocator_type allocator_type;
00238 private:
00239   typedef _Rb_tree_base<_Tp, _Alloc> _Self;
00240   typedef typename _Alloc_traits<_Node, _Alloc>::allocator_type _M_node_allocator_type;
00241   typedef _STLP_alloc_proxy<_Node_base, _Node, _M_node_allocator_type> _AllocProxy;
00242 
00243 public:
00244   allocator_type get_allocator() const {
00245     return _STLP_CONVERT_ALLOCATOR(_M_header, _Tp);
00246   }
00247 
00248 protected:
00249   _Rb_tree_base(const allocator_type& __a) :
00250     _M_header(_STLP_CONVERT_ALLOCATOR(__a, _Node), _Node_base() ) {
00251     _M_empty_initialize();
00252   }
00253   _Rb_tree_base(__move_source<_Self> src) :
00254     _M_header(__move_source<_AllocProxy>(src.get()._M_header)) {
00255     _M_rebind(&src.get()._M_header._M_data);
00256     src.get()._M_empty_initialize();
00257   }
00258   void _M_empty_initialize() {
00259     _M_header._M_data._M_color = _S_rb_tree_red; // used to distinguish header from
00260                                                  // __root, in iterator.operator++
00261     _M_header._M_data._M_parent = 0;
00262     _M_header._M_data._M_left = &_M_header._M_data;
00263     _M_header._M_data._M_right = &_M_header._M_data;
00264   }
00265 
00266   void _M_rebind(_Node_base *__static_node) {
00267     if (_M_header._M_data._M_parent != 0) {
00268       _M_header._M_data._M_parent->_M_parent = &_M_header._M_data;
00269     }
00270     if (_M_header._M_data._M_right == __static_node) {
00271       _M_header._M_data._M_right = &_M_header._M_data;
00272     }
00273     if (_M_header._M_data._M_left == __static_node) {
00274       _M_header._M_data._M_left = &_M_header._M_data;
00275     }
00276   }
00277 
00278   _AllocProxy _M_header;
00279 };
00280 
00281 #if defined (_STLP_DEBUG)
00282 #  define _Rb_tree _STLP_NON_DBG_NAME(Rb_tree)
00283 #endif
00284 
00285 template <class _Key, class _Compare,
00286           class _Value, class _KeyOfValue, class _Traits,
00287           _STLP_DEFAULT_ALLOCATOR_SELECT(_Value) >
00288 class _Rb_tree : public _Rb_tree_base<_Value, _Alloc> {
00289   typedef _Rb_tree_base<_Value, _Alloc> _Base;
00290   typedef _Rb_tree<_Key, _Compare, _Value, _KeyOfValue, _Traits, _Alloc> _Self;
00291 protected:
00292   typedef _Rb_tree_node_base * _Base_ptr;
00293   typedef _Rb_tree_node<_Value> _Node;
00294   typedef _Node* _Link_type;
00295   typedef _Rb_tree_Color_type _Color_type;
00296 public:
00297   typedef _Key key_type;
00298   typedef _Value value_type;
00299   typedef typename _Traits::pointer pointer;
00300   typedef const value_type* const_pointer;
00301   typedef typename _Traits::reference reference;
00302   typedef const value_type& const_reference;
00303   typedef size_t size_type;
00304   typedef ptrdiff_t difference_type;
00305   typedef bidirectional_iterator_tag _Iterator_category;
00306   typedef typename _Base::allocator_type allocator_type;
00307 
00308 protected:
00309 
00310   _STLP_KEY_TYPE_FOR_CONT_EXT(key_type)
00311   _Base_ptr _M_create_node(const value_type& __x) {
00312     _Link_type __tmp = this->_M_header.allocate(1);
00313     _STLP_TRY {
00314       _Copy_Construct(&__tmp->_M_value_field, __x);
00315     }
00316     _STLP_UNWIND(this->_M_header.deallocate(__tmp,1))
00317     _S_left(__tmp) = 0;
00318     _S_right(__tmp) = 0;
00319     return __tmp;
00320   }
00321 
00322   _Base_ptr _M_clone_node(_Base_ptr __x) {
00323     _Base_ptr __tmp = _M_create_node(_S_value(__x));
00324     _S_color(__tmp) = _S_color(__x);
00325     return __tmp;
00326   }
00327 
00328   size_type _M_node_count; // keeps track of size of tree
00329   _Compare _M_key_compare;
00330 
00331   _Base_ptr _M_root() const
00332   { return this->_M_header._M_data._M_parent; }
00333   _Base_ptr _M_leftmost() const
00334   { return this->_M_header._M_data._M_left; }
00335   _Base_ptr _M_rightmost() const
00336   { return this->_M_header._M_data._M_right; }
00337 
00338   _Base_ptr& _M_root()
00339   { return this->_M_header._M_data._M_parent; }
00340   _Base_ptr& _M_leftmost()
00341   { return this->_M_header._M_data._M_left; }
00342   _Base_ptr& _M_rightmost()
00343   { return this->_M_header._M_data._M_right; }
00344 
00345   static _Base_ptr& _STLP_CALL _S_left(_Base_ptr __x)
00346   { return __x->_M_left; }
00347   static _Base_ptr& _STLP_CALL _S_right(_Base_ptr __x)
00348   { return __x->_M_right; }
00349   static _Base_ptr& _STLP_CALL _S_parent(_Base_ptr __x)
00350   { return __x->_M_parent; }
00351   static value_type& _STLP_CALL _S_value(_Base_ptr __x)
00352   { return __STATIC_CAST(_Link_type, __x)->_M_value_field; }
00353   static const _Key& _STLP_CALL _S_key(_Base_ptr __x)
00354   { return _KeyOfValue()(_S_value(__x));}
00355   static _Color_type& _STLP_CALL _S_color(_Base_ptr __x)
00356   { return (_Color_type&)(__x->_M_color); }
00357 
00358   static _Base_ptr _STLP_CALL _S_minimum(_Base_ptr __x)
00359   { return _Rb_tree_node_base::_S_minimum(__x); }
00360 
00361   static _Base_ptr _STLP_CALL _S_maximum(_Base_ptr __x)
00362   { return _Rb_tree_node_base::_S_maximum(__x); }
00363 
00364 public:
00365   typedef typename _Traits::_NonConstTraits _NonConstTraits;
00366   typedef typename _Traits::_ConstTraits _ConstTraits;
00367   typedef _Rb_tree_iterator<value_type, _NonConstTraits> iterator;
00368   typedef _Rb_tree_iterator<value_type, _ConstTraits> const_iterator;
00369   _STLP_DECLARE_BIDIRECTIONAL_REVERSE_ITERATORS;
00370 
00371 private:
00372   iterator _M_insert(_Base_ptr __parent, const value_type& __val, _Base_ptr __on_left = 0, _Base_ptr __on_right = 0);
00373   _Base_ptr _M_copy(_Base_ptr __x, _Base_ptr __p);
00374   void _M_erase(_Base_ptr __x);
00375 
00376 public:
00377                                 // allocation/deallocation
00378   _Rb_tree()
00379     : _Rb_tree_base<_Value, _Alloc>(allocator_type()), _M_node_count(0), _M_key_compare(_Compare())
00380     {}
00381 
00382   _Rb_tree(const _Compare& __comp)
00383     : _Rb_tree_base<_Value, _Alloc>(allocator_type()), _M_node_count(0), _M_key_compare(__comp)
00384     {}
00385 
00386   _Rb_tree(const _Compare& __comp, const allocator_type& __a)
00387     : _Rb_tree_base<_Value, _Alloc>(__a), _M_node_count(0), _M_key_compare(__comp)
00388     {}
00389 
00390   _Rb_tree(const _Self& __x)
00391     : _Rb_tree_base<_Value, _Alloc>(__x.get_allocator()),
00392       _M_node_count(0), _M_key_compare(__x._M_key_compare) {
00393     if (__x._M_root() != 0) {
00394       _S_color(&this->_M_header._M_data) = _S_rb_tree_red;
00395       _M_root() = _M_copy(__x._M_root(), &this->_M_header._M_data);
00396       _M_leftmost() = _S_minimum(_M_root());
00397       _M_rightmost() = _S_maximum(_M_root());
00398     }
00399     _M_node_count = __x._M_node_count;
00400   }
00401 
00402   _Rb_tree(__move_source<_Self> src)
00403     : _Rb_tree_base<_Value, _Alloc>(__move_source<_Base>(src.get())),
00404       _M_node_count(src.get()._M_node_count),
00405       _M_key_compare(_AsMoveSource(src.get()._M_key_compare)) {
00406     src.get()._M_node_count = 0;
00407   }
00408 
00409   ~_Rb_tree() { clear(); }
00410   _Self& operator=(const _Self& __x);
00411 
00412 public:
00413                                 // accessors:
00414   _Compare key_comp() const { return _M_key_compare; }
00415 
00416   iterator begin() { return iterator(_M_leftmost()); }
00417   const_iterator begin() const { return const_iterator(_M_leftmost()); }
00418   iterator end() { return iterator(&this->_M_header._M_data); }
00419   const_iterator end() const { return const_iterator(__CONST_CAST(_Base_ptr, &this->_M_header._M_data)); }
00420 
00421   reverse_iterator rbegin() { return reverse_iterator(end()); }
00422   const_reverse_iterator rbegin() const
00423   { return const_reverse_iterator(end()); }
00424   reverse_iterator rend() { return reverse_iterator(begin()); }
00425   const_reverse_iterator rend() const
00426   { return const_reverse_iterator(begin()); }
00427   bool empty() const { return _M_node_count == 0; }
00428   size_type size() const { return _M_node_count; }
00429   size_type max_size() const { return size_type(-1); }
00430 
00431   void swap(_Self& __t) {
00432     if (__t.empty()) {
00433       if (this->empty()) return;
00434       __t._M_header.swap(this->_M_header);
00435       __t._M_rebind(&this->_M_header._M_data);
00436       this->_M_empty_initialize();
00437     }
00438     else if (this->empty()) {
00439       __t.swap(*this);
00440       return;
00441     }
00442     else {
00443       this->_M_header.swap(__t._M_header);
00444       this->_M_rebind(&__t._M_header._M_data);
00445       __t._M_rebind(&this->_M_header._M_data);
00446     }
00447     _STLP_STD::swap(_M_node_count, __t._M_node_count);
00448     _STLP_STD::swap(_M_key_compare, __t._M_key_compare);
00449   }
00450 
00451 public:
00452                                 // insert/erase
00453   pair<iterator,bool> insert_unique(const value_type& __x);
00454   iterator insert_equal(const value_type& __x);
00455 
00456   iterator insert_unique(iterator __pos, const value_type& __x);
00457   iterator insert_equal(iterator __pos, const value_type& __x);
00458 
00459 #if defined (_STLP_MEMBER_TEMPLATES)
00460   template<class _II> void insert_equal(_II __first, _II __last) {
00461     for ( ; __first != __last; ++__first)
00462       insert_equal(*__first);
00463   }
00464   template<class _II> void insert_unique(_II __first, _II __last) {
00465     for ( ; __first != __last; ++__first)
00466       insert_unique(*__first);
00467   }
00468 #else
00469   void insert_unique(const_iterator __first, const_iterator __last) {
00470     for ( ; __first != __last; ++__first)
00471       insert_unique(*__first);
00472   }
00473   void insert_unique(const value_type* __first, const value_type* __last) {
00474     for ( ; __first != __last; ++__first)
00475       insert_unique(*__first);
00476   }
00477   void insert_equal(const_iterator __first, const_iterator __last) {
00478     for ( ; __first != __last; ++__first)
00479       insert_equal(*__first);
00480   }
00481   void insert_equal(const value_type* __first, const value_type* __last) {
00482     for ( ; __first != __last; ++__first)
00483       insert_equal(*__first);
00484   }
00485 #endif
00486 
00487   void erase(iterator __pos) {
00488     _Base_ptr __x = _Rb_global_inst::_Rebalance_for_erase(__pos._M_node,
00489                                                           this->_M_header._M_data._M_parent,
00490                                                           this->_M_header._M_data._M_left,
00491                                                           this->_M_header._M_data._M_right);
00492     _STLP_STD::_Destroy(&_S_value(__x));
00493     this->_M_header.deallocate(__STATIC_CAST(_Link_type, __x), 1);
00494     --_M_node_count;
00495   }
00496 
00497   size_type erase(const key_type& __x) {
00498     pair<iterator,iterator> __p = equal_range(__x);
00499     size_type __n = distance(__p.first, __p.second);
00500     erase(__p.first, __p.second);
00501     return __n;
00502   }
00503 
00504   size_type erase_unique(const key_type& __x) {
00505     iterator __i = find(__x);
00506     if (__i._M_node != &this->_M_header._M_data) {
00507       erase(__i);
00508       return 1;
00509     }
00510     return 0;
00511   }
00512 
00513   void erase(iterator __first, iterator __last) {
00514     if (__first._M_node == this->_M_header._M_data._M_left && // begin()
00515         __last._M_node == &this->_M_header._M_data)           // end()
00516       clear();
00517     else
00518       while (__first != __last) erase(__first++);
00519   }
00520 
00521   void erase(const key_type* __first, const key_type* __last) {
00522     while (__first != __last) erase(*__first++);
00523   }
00524 
00525   void clear() {
00526     if (_M_node_count != 0) {
00527       _M_erase(_M_root());
00528       _M_leftmost() = &this->_M_header._M_data;
00529       _M_root() = 0;
00530       _M_rightmost() = &this->_M_header._M_data;
00531       _M_node_count = 0;
00532     }
00533   }
00534 
00535 public:
00536                                 // set operations:
00537   _STLP_TEMPLATE_FOR_CONT_EXT
00538   iterator find(const _KT& __k) { return iterator(_M_find(__k)); }
00539   _STLP_TEMPLATE_FOR_CONT_EXT
00540   const_iterator find(const _KT& __k) const { return const_iterator(_M_find(__k)); }
00541 private:
00542   _STLP_TEMPLATE_FOR_CONT_EXT
00543   _Base_ptr _M_find(const _KT& __k) const {
00544     _Base_ptr __y = __CONST_CAST(_Base_ptr, &this->_M_header._M_data);      // Last node which is not less than __k.
00545     _Base_ptr __x = _M_root();      // Current node.
00546 
00547     while (__x != 0)
00548       if (!_M_key_compare(_S_key(__x), __k))
00549         __y = __x, __x = _S_left(__x);
00550       else
00551         __x = _S_right(__x);
00552 
00553     if (__y != &this->_M_header._M_data) {
00554       if (_M_key_compare(__k, _S_key(__y))) {
00555         __y = __CONST_CAST(_Base_ptr, &this->_M_header._M_data);
00556       }
00557     }
00558     return __y;
00559   }
00560 
00561   _STLP_TEMPLATE_FOR_CONT_EXT
00562   _Base_ptr _M_lower_bound(const _KT& __k) const {
00563     _Base_ptr __y = __CONST_CAST(_Base_ptr, &this->_M_header._M_data); /* Last node which is not less than __k. */
00564     _Base_ptr __x = _M_root(); /* Current node. */
00565 
00566     while (__x != 0)
00567       if (!_M_key_compare(_S_key(__x), __k))
00568         __y = __x, __x = _S_left(__x);
00569       else
00570         __x = _S_right(__x);
00571 
00572     return __y;
00573   }
00574 
00575   _STLP_TEMPLATE_FOR_CONT_EXT
00576   _Base_ptr _M_upper_bound(const _KT& __k) const {
00577     _Base_ptr __y = __CONST_CAST(_Base_ptr, &this->_M_header._M_data); /* Last node which is greater than __k. */
00578     _Base_ptr __x = _M_root(); /* Current node. */
00579 
00580     while (__x != 0)
00581       if (_M_key_compare(__k, _S_key(__x)))
00582         __y = __x, __x = _S_left(__x);
00583       else
00584         __x = _S_right(__x);
00585 
00586     return __y;
00587   }
00588 
00589 public:
00590   _STLP_TEMPLATE_FOR_CONT_EXT
00591   size_type count(const _KT& __x) const {
00592     pair<const_iterator, const_iterator> __p = equal_range(__x);
00593     return distance(__p.first, __p.second);
00594   }
00595   _STLP_TEMPLATE_FOR_CONT_EXT
00596   iterator lower_bound(const _KT& __x) { return iterator(_M_lower_bound(__x)); }
00597   _STLP_TEMPLATE_FOR_CONT_EXT
00598   const_iterator lower_bound(const _KT& __x) const { return const_iterator(_M_lower_bound(__x)); }
00599   _STLP_TEMPLATE_FOR_CONT_EXT
00600   iterator upper_bound(const _KT& __x) { return iterator(_M_upper_bound(__x)); }
00601   _STLP_TEMPLATE_FOR_CONT_EXT
00602   const_iterator upper_bound(const _KT& __x) const { return const_iterator(_M_upper_bound(__x)); }
00603   _STLP_TEMPLATE_FOR_CONT_EXT
00604   pair<iterator,iterator> equal_range(const _KT& __x)
00605   { return pair<iterator, iterator>(lower_bound(__x), upper_bound(__x)); }
00606   _STLP_TEMPLATE_FOR_CONT_EXT
00607   pair<const_iterator, const_iterator> equal_range(const _KT& __x) const
00608   { return pair<const_iterator, const_iterator>(lower_bound(__x), upper_bound(__x)); }
00609   _STLP_TEMPLATE_FOR_CONT_EXT
00610   pair<iterator,iterator> equal_range_unique(const _KT& __x) {
00611     pair<iterator, iterator> __p;
00612     __p.second = lower_bound(__x);
00613     if (__p.second._M_node != &this->_M_header._M_data &&
00614         !_M_key_compare(__x, _S_key(__p.second._M_node))) {
00615       __p.first = __p.second++;
00616     }
00617     else {
00618       __p.first = __p.second;
00619     }
00620     return __p;
00621   }
00622   _STLP_TEMPLATE_FOR_CONT_EXT
00623   pair<const_iterator, const_iterator> equal_range_unique(const _KT& __x) const {
00624     pair<const_iterator, const_iterator> __p;
00625     __p.second = lower_bound(__x);
00626     if (__p.second._M_node != &this->_M_header._M_data &&
00627         !_M_key_compare(__x, _S_key(__p.second._M_node))) {
00628       __p.first = __p.second++;
00629     }
00630     else {
00631       __p.first = __p.second;
00632     }
00633     return __p;
00634   }
00635 
00636 #if defined (_STLP_DEBUG)
00637 public:
00638   // Debugging.
00639   bool __rb_verify() const;
00640 #endif //_STLP_DEBUG
00641 };
00642 
00643 #if defined (_STLP_DEBUG)
00644 #  undef _Rb_tree
00645 #endif
00646 
00647 _STLP_MOVE_TO_STD_NAMESPACE
00648 
00649 _STLP_END_NAMESPACE
00650 
00651 #if !defined (_STLP_LINK_TIME_INSTANTIATION)
00652 #  include <stl/_tree.c>
00653 #endif
00654 
00655 #if defined (_STLP_DEBUG)
00656 #  include <stl/debug/_tree.h>
00657 #endif
00658 
00659 _STLP_BEGIN_NAMESPACE
00660 
00661 #define _STLP_TEMPLATE_HEADER template <class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, class _Alloc>
00662 #define _STLP_TEMPLATE_CONTAINER _STLP_PRIV _Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc>
00663 #include <stl/_relops_cont.h>
00664 #undef _STLP_TEMPLATE_CONTAINER
00665 #undef _STLP_TEMPLATE_HEADER
00666 
00667 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
00668 template <class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, class _Alloc>
00669 struct __move_traits<_STLP_PRIV _Rb_tree<_Key, _Compare, _Value, _KeyOfValue, _Traits, _Alloc> >
00670   : _STLP_PRIV __move_traits_help2<_Compare, _Alloc> {};
00671 #endif
00672 
00673 _STLP_END_NAMESPACE
00674 
00675 #endif /* _STLP_INTERNAL_TREE_H */
00676 
00677 // Local Variables:
00678 // mode:C++
00679 // End:



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