111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert/* 211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * 311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * Copyright (c) 1994 411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * Hewlett-Packard Company 511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * 611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * Copyright (c) 1996,1997 711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * Silicon Graphics Computer Systems, Inc. 811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * 911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * Copyright (c) 1997 1011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * Moscow Center for SPARC Technology 1111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * 1211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * Copyright (c) 1999 1311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * Boris Fomitchev 1411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * 1511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * This material is provided "as is", with absolutely no warranty expressed 1611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * or implied. Any use is at your own risk. 1711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * 1811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * Permission to use or copy this software for any purpose is hereby granted 1911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * without fee, provided the above notices are retained on all copies. 2011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * Permission to modify the code and to distribute modified code is granted, 2111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * provided the above notices are retained, and a notice that the code was 2211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * modified is included with the above copyright notice. 2311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * 2411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert */ 2511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 2611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert/* NOTE: This is an internal header file, included by other STL headers. 2711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * You should not attempt to use it directly. 2811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert */ 2911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 3011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifndef _STLP_INTERNAL_DBG_TREE_H 3111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#define _STLP_INTERNAL_DBG_TREE_H 3211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 3311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifndef _STLP_DBG_ITERATOR_H 3411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert# include <stl/debug/_iterator.h> 3511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 3611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 3711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifndef _STLP_INTERNAL_FUNCTION_BASE_H 3811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert# include <stl/_function_base.h> 3911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 4011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 4111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifndef _STLP_INTERNAL_ALLOC_H 4211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert# include <stl/_alloc.h> 4311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 4411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 4511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert_STLP_BEGIN_NAMESPACE 4611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 4711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert_STLP_MOVE_TO_PRIV_NAMESPACE 4811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 4911cd02dfb91661c65134cac258cf5924270e9d2Dan Alberttemplate <class _Key, class _Compare> 5011cd02dfb91661c65134cac258cf5924270e9d2Dan Albertclass _DbgCompare { 5111cd02dfb91661c65134cac258cf5924270e9d2Dan Albertpublic: 5211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _DbgCompare() {} 5311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _DbgCompare(const _Compare& __cmp) : _M_non_dbg_cmp(__cmp) {} 5411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _DbgCompare(const _DbgCompare& __cmp) : _M_non_dbg_cmp(__cmp._M_non_dbg_cmp) {} 5511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 5611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#if !defined (_STLP_USE_CONTAINERS_EXTENSION) 5711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool operator () (const _Key& __lhs, const _Key& __rhs) const { 5811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#else 5911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template <class _Kp1, class _Kp2> 6011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool operator () (const _Kp1& __lhs, const _Kp2& __rhs) const { 6111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 6211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (_M_non_dbg_cmp(__lhs, __rhs)) { 6311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return true; 6411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 6511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return false; 6611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 6711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 6811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Compare non_dbg_key_comp() const { return _M_non_dbg_cmp; } 6911cd02dfb91661c65134cac258cf5924270e9d2Dan Albertprivate: 7011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Compare _M_non_dbg_cmp; 7111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert}; 7211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 7311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#define _STLP_NON_DBG_TREE _STLP_PRIV _STLP_NON_DBG_NAME(Rb_tree) <_Key, _STLP_PRIV _DbgCompare<_Key, _Compare>, _Value, _KeyOfValue, _Traits, _Alloc> 7411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 7511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#if defined (_STLP_DEBUG_USE_DISTINCT_VALUE_TYPE_HELPERS) 7611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert_STLP_MOVE_TO_STD_NAMESPACE 7711cd02dfb91661c65134cac258cf5924270e9d2Dan Alberttemplate <class _Key, class _Compare, 7811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert class _Value, class _KeyOfValue, class _Traits, class _Alloc > 7911cd02dfb91661c65134cac258cf5924270e9d2Dan Albertinline _Value* 8011cd02dfb91661c65134cac258cf5924270e9d2Dan Albertvalue_type(const _STLP_PRIV _DBG_iter_base< _STLP_NON_DBG_TREE >&) 8111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert{ return (_Value*)0; } 8211cd02dfb91661c65134cac258cf5924270e9d2Dan Alberttemplate <class _Key, class _Compare, 8311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert class _Value, class _KeyOfValue, class _Traits, class _Alloc > 8411cd02dfb91661c65134cac258cf5924270e9d2Dan Albertinline bidirectional_iterator_tag 8511cd02dfb91661c65134cac258cf5924270e9d2Dan Albertiterator_category(const _STLP_PRIV _DBG_iter_base< _STLP_NON_DBG_TREE >&) 8611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert{ return bidirectional_iterator_tag(); } 8711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert_STLP_MOVE_TO_PRIV_NAMESPACE 8811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 8911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 9011cd02dfb91661c65134cac258cf5924270e9d2Dan Alberttemplate <class _Key, class _Compare, 9111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert class _Value, class _KeyOfValue, class _Traits, 9211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_DFL_TMPL_PARAM(_Alloc, allocator<_Value>) > 9311cd02dfb91661c65134cac258cf5924270e9d2Dan Albertclass _Rb_tree { 9411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef _STLP_NON_DBG_TREE _Base; 9511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef _Rb_tree<_Key, _Compare, _Value, _KeyOfValue, _Traits, _Alloc> _Self; 9611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Base _M_non_dbg_impl; 9711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_PRIV __owned_list _M_iter_list; 9811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 9911cd02dfb91661c65134cac258cf5924270e9d2Dan Albertpublic: 10011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __IMPORT_CONTAINER_TYPEDEFS(_Base) 10111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Base::key_type key_type; 10211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 10311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Traits::_NonConstTraits _NonConstIteTraits; 10411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Traits::_ConstTraits _ConstIteTraits; 10511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef _STLP_PRIV _DBG_iter<_Base, _STLP_PRIV _DbgTraits<_NonConstIteTraits> > iterator; 10611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef _STLP_PRIV _DBG_iter<_Base, _STLP_PRIV _DbgTraits<_ConstIteTraits> > const_iterator; 10711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 10811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_DECLARE_BIDIRECTIONAL_REVERSE_ITERATORS; 10911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 11011cd02dfb91661c65134cac258cf5924270e9d2Dan Albertprivate: 11111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_KEY_TYPE_FOR_CONT_EXT(key_type) 11211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void _Invalidate_iterator(const iterator& __it) 11311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { _STLP_PRIV __invalidate_iterator(&_M_iter_list,__it); } 11411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void _Invalidate_iterators(const iterator& __first, const iterator& __last) 11511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { _STLP_PRIV __invalidate_range(&_M_iter_list, __first, __last); } 11611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 11711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Base::iterator _Base_iterator; 11811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Base::const_iterator _Base_const_iterator; 11911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 12011cd02dfb91661c65134cac258cf5924270e9d2Dan Albertpublic: 12111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rb_tree() 12211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert : _M_non_dbg_impl(), _M_iter_list(&_M_non_dbg_impl) {} 12311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rb_tree(const _Compare& __comp) 12411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert : _M_non_dbg_impl(__comp), _M_iter_list(&_M_non_dbg_impl) {} 12511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rb_tree(const _Compare& __comp, const allocator_type& __a) 12611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert : _M_non_dbg_impl(__comp, __a), _M_iter_list(&_M_non_dbg_impl) {} 12711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rb_tree(const _Self& __x) 12811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert : _M_non_dbg_impl(__x._M_non_dbg_impl), _M_iter_list(&_M_non_dbg_impl) {} 12911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 13011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#if !defined (_STLP_NO_MOVE_SEMANTIC) 13111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rb_tree(__move_source<_Self> src): 13211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_non_dbg_impl(__move_source<_Base>(src.get()._M_non_dbg_impl)), 13311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_iter_list(&_M_non_dbg_impl) { 13411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert# if defined (_STLP_NO_EXTENSIONS) || (_STLP_DEBUG_LEVEL == _STLP_STANDARD_DBG_LEVEL) 13511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert src.get()._M_iter_list._Invalidate_all(); 13611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert# else 13711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert src.get()._M_iter_list._Set_owner(_M_iter_list); 13811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert# endif 13911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 14011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 14111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 14211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert ~_Rb_tree() {} 14311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 14411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Self& operator=(const _Self& __x) { 14511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (this != &__x) { 14611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert //Should not invalidate end iterator: 14711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Invalidate_iterators(begin(), end()); 14811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_non_dbg_impl = __x._M_non_dbg_impl; 14911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 15011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return *this; 15111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 15211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 15311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert allocator_type get_allocator() const { return _M_non_dbg_impl.get_allocator(); } 15411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Compare key_comp() const { return _M_non_dbg_impl.key_comp().non_dbg_key_comp(); } 15511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 15611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert iterator begin() { return iterator(&_M_iter_list, _M_non_dbg_impl.begin()); } 15711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const_iterator begin() const { return const_iterator(&_M_iter_list, _M_non_dbg_impl.begin()); } 15811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert iterator end() { return iterator(&_M_iter_list, _M_non_dbg_impl.end()); } 15911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const_iterator end() const { return const_iterator(&_M_iter_list, _M_non_dbg_impl.end()); } 16011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 16111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert reverse_iterator rbegin() { return reverse_iterator(end()); } 16211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); } 16311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert reverse_iterator rend() { return reverse_iterator(begin()); } 16411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const_reverse_iterator rend() const { return const_reverse_iterator(begin()); } 16511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 16611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool empty() const { return _M_non_dbg_impl.empty(); } 16711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_type size() const { return _M_non_dbg_impl.size(); } 16811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_type max_size() const { return _M_non_dbg_impl.max_size(); } 16911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_TEMPLATE_FOR_CONT_EXT 17011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_type count(const _KT& __x) const { return _M_non_dbg_impl.count(__x); } 17111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 17211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void swap(_Self& __t) { 17311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_non_dbg_impl.swap(__t._M_non_dbg_impl); 17411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_iter_list._Swap_owners(__t._M_iter_list); 17511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 17611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 17711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_TEMPLATE_FOR_CONT_EXT 17811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert iterator find(const _KT& __k) 17911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return iterator(&_M_iter_list, _M_non_dbg_impl.find(__k)); } 18011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_TEMPLATE_FOR_CONT_EXT 18111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const_iterator find(const _KT& __k) const 18211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return const_iterator(&_M_iter_list, _M_non_dbg_impl.find(__k)); } 18311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 18411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_TEMPLATE_FOR_CONT_EXT 18511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert iterator lower_bound(const _KT& __x) 18611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return iterator(&_M_iter_list, _M_non_dbg_impl.lower_bound(__x)); } 18711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_TEMPLATE_FOR_CONT_EXT 18811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const_iterator lower_bound(const _KT& __x) const 18911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return const_iterator(&_M_iter_list, _M_non_dbg_impl.lower_bound(__x)); } 19011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 19111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_TEMPLATE_FOR_CONT_EXT 19211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert iterator upper_bound(const _KT& __x) 19311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return iterator(&_M_iter_list, _M_non_dbg_impl.upper_bound(__x)); } 19411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_TEMPLATE_FOR_CONT_EXT 19511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const_iterator upper_bound(const _KT& __x) const 19611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return const_iterator(&_M_iter_list, _M_non_dbg_impl.upper_bound(__x)); } 19711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 19811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_TEMPLATE_FOR_CONT_EXT 19911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert pair<iterator,iterator> equal_range(const _KT& __x) { 20011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return pair<iterator, iterator>(iterator(&_M_iter_list, _M_non_dbg_impl.lower_bound(__x)), 20111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert iterator(&_M_iter_list, _M_non_dbg_impl.upper_bound(__x))); 20211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 20311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_TEMPLATE_FOR_CONT_EXT 20411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert pair<const_iterator, const_iterator> equal_range(const _KT& __x) const { 20511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return pair<const_iterator,const_iterator>(const_iterator(&_M_iter_list, _M_non_dbg_impl.lower_bound(__x)), 20611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const_iterator(&_M_iter_list, _M_non_dbg_impl.upper_bound(__x))); 20711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 20811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 20911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_TEMPLATE_FOR_CONT_EXT 21011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert pair<iterator,iterator> equal_range_unique(const _KT& __x) { 21111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_STD::pair<_Base_iterator, _Base_iterator> __p; 21211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __p = _M_non_dbg_impl.equal_range_unique(__x); 21311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return pair<iterator, iterator>(iterator(&_M_iter_list, __p.first), iterator(&_M_iter_list, __p.second)); 21411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 21511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_TEMPLATE_FOR_CONT_EXT 21611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert pair<const_iterator, const_iterator> equal_range_unique(const _KT& __x) const { 21711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_STD::pair<_Base_const_iterator, _Base_const_iterator> __p; 21811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __p = _M_non_dbg_impl.equal_range_unique(__x); 21911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return pair<const_iterator, const_iterator>(const_iterator(&_M_iter_list, __p.first), 22011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const_iterator(&_M_iter_list, __p.second)); 22111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 22211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 22311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert pair<iterator,bool> insert_unique(const value_type& __x) { 22411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_STD::pair<_Base_iterator, bool> __res = _M_non_dbg_impl.insert_unique(__x); 22511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return pair<iterator, bool>(iterator(&_M_iter_list, __res.first), __res.second); 22611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 22711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert iterator insert_equal(const value_type& __x) 22811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return iterator(&_M_iter_list, _M_non_dbg_impl.insert_equal(__x)); } 22911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 23011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert iterator insert_unique(iterator __pos, const value_type& __x) { 23111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_DEBUG_CHECK(__check_if_owner(&_M_iter_list,__pos)) 23211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return iterator(&_M_iter_list, _M_non_dbg_impl.insert_unique(__pos._M_iterator, __x)); 23311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 23411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert iterator insert_equal(iterator __pos, const value_type& __x) { 23511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_DEBUG_CHECK(__check_if_owner(&_M_iter_list, __pos)) 23611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return iterator(&_M_iter_list, _M_non_dbg_impl.insert_equal(__pos._M_iterator, __x)); 23711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 23811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 23911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#if defined (_STLP_MEMBER_TEMPLATES) 24011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<class _InputIterator> 24111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void insert_equal(_InputIterator __first, _InputIterator __last) { 24211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_DEBUG_CHECK(__check_range(__first,__last)) 24311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_non_dbg_impl.insert_equal(_STLP_PRIV _Non_Dbg_iter(__first), _STLP_PRIV _Non_Dbg_iter(__last)); 24411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 24511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<class _InputIterator> 24611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void insert_unique(_InputIterator __first, _InputIterator __last) { 24711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_DEBUG_CHECK(__check_range(__first,__last)) 24811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_non_dbg_impl.insert_unique(_STLP_PRIV _Non_Dbg_iter(__first), _STLP_PRIV _Non_Dbg_iter(__last)); 24911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 25011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#else 25111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void insert_unique(const_iterator __first, const_iterator __last) { 25211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_DEBUG_CHECK(__check_range(__first,__last)) 25311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_non_dbg_impl.insert_unique(__first._M_iterator, __last._M_iterator); 25411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 25511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void insert_unique(const value_type* __first, const value_type* __last) { 25611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_DEBUG_CHECK(__check_ptr_range(__first,__last)) 25711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_non_dbg_impl.insert_unique(__first, __last); 25811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 25911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void insert_equal(const_iterator __first, const_iterator __last) { 26011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_DEBUG_CHECK(__check_range(__first,__last)) 26111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_non_dbg_impl.insert_equal(__first._M_iterator, __last._M_iterator); 26211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 26311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void insert_equal(const value_type* __first, const value_type* __last) { 26411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_DEBUG_CHECK(__check_ptr_range(__first,__last)) 26511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_non_dbg_impl.insert_equal(__first, __last); 26611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 26711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 26811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 26911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void erase(iterator __pos) { 27011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_DEBUG_CHECK(__check_if_owner(&_M_iter_list,__pos)) 27111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_DEBUG_CHECK(_Dereferenceable(__pos)) 27211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Invalidate_iterator(__pos); 27311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_non_dbg_impl.erase(__pos._M_iterator); 27411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 27511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_type erase(const key_type& __x) { 27611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert pair<iterator, iterator> __p = equal_range(__x); 27711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_type __n = _STLP_STD::distance(__p.first._M_iterator, __p.second._M_iterator); 27811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Invalidate_iterators(__p.first, __p.second); 27911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_non_dbg_impl.erase(__p.first._M_iterator, __p.second._M_iterator); 28011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __n; 28111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 28211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_type erase_unique(const key_type& __x) { 28311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Base_iterator __i = _M_non_dbg_impl.find(__x); 28411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__i != _M_non_dbg_impl.end()) { 28511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Invalidate_iterator(iterator(&_M_iter_list, __i)); 28611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_non_dbg_impl.erase(__i); 28711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return 1; 28811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 28911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return 0; 29011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 29111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 29211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void erase(iterator __first, iterator __last) { 29311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _STLP_DEBUG_CHECK(__check_range(__first, __last, begin(), end())) 29411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Invalidate_iterators(__first, __last); 29511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_non_dbg_impl.erase(__first._M_iterator, __last._M_iterator); 29611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 29711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void erase(const key_type* __first, const key_type* __last) { 29811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert while (__first != __last) erase(*__first++); 29911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 30011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 30111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void clear() { 30211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert //should not invalidate end: 30311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Invalidate_iterators(begin(), end()); 30411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_non_dbg_impl.clear(); 30511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 30611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert}; 30711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 30811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert_STLP_MOVE_TO_STD_NAMESPACE 30911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert_STLP_END_NAMESPACE 31011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 31111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#undef _STLP_NON_DBG_TREE 31211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 31311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif /* _STLP_INTERNAL_DBG_TREE_H */ 31411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 31511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Local Variables: 31611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// mode:C++ 31711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// End: 318