177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner/* 277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner * 377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner * Copyright (c) 1994 477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner * Hewlett-Packard Company 577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner * 677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner * Copyright (c) 1996,1997 777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner * Silicon Graphics Computer Systems, Inc. 877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner * 977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner * Copyright (c) 1997 1077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner * Moscow Center for SPARC Technology 1177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner * 1277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner * Copyright (c) 1999 1377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner * Boris Fomitchev 1477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner * 1577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner * This material is provided "as is", with absolutely no warranty expressed 1677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner * or implied. Any use is at your own risk. 1777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner * 1877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner * Permission to use or copy this software for any purpose is hereby granted 1977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner * without fee, provided the above notices are retained on all copies. 2077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner * Permission to modify the code and to distribute modified code is granted, 2177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner * provided the above notices are retained, and a notice that the code was 2277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner * modified is included with the above copyright notice. 2377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner * 2477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner */ 2577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 2677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner/* NOTE: This is an internal header file, included by other STL headers. 2777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner * You should not attempt to use it directly. 2877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner */ 2977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 3077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#ifndef _STLP_INTERNAL_TREE_H 3177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#define _STLP_INTERNAL_TREE_H 3277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 3377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner/* 3477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 3577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' TurnerRed-black tree class, designed for use in implementing STL 3677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnerassociative containers (set, multiset, map, and multimap). The 3777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnerinsertion and deletion algorithms are based on those in Cormen, 3877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' TurnerLeiserson, and Rivest, Introduction to Algorithms (MIT Press, 1990), 3977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnerexcept that 4077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 4177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner(1) the header cell is maintained with links not only to the root 4277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnerbut also to the leftmost node of the tree, to enable constant time 4377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnerbegin(), and to the rightmost node of the tree, to enable linear time 4477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnerperformance when used with the generic set algorithms (set_union, 4577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turneretc.); 4677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 4777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner(2) when a node being deleted has two children its successor node is 4877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnerrelinked into its place, rather than copied, so that the only 4977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turneriterators invalidated are those referring to the deleted node. 5077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 5177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner*/ 5277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 5377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#ifndef _STLP_INTERNAL_ALGOBASE_H 5477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner# include <stl/_algobase.h> 5577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#endif 5677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 5777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#ifndef _STLP_INTERNAL_ALLOC_H 5877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner# include <stl/_alloc.h> 5977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#endif 6077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 6177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#ifndef _STLP_INTERNAL_ITERATOR_H 6277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner# include <stl/_iterator.h> 6377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#endif 6477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 6577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#ifndef _STLP_INTERNAL_CONSTRUCT_H 6677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner# include <stl/_construct.h> 6777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#endif 6877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 6977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#ifndef _STLP_INTERNAL_FUNCTION_BASE_H 7077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner# include <stl/_function_base.h> 7177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#endif 7277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 7377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner_STLP_BEGIN_NAMESPACE 7477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 7577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner_STLP_MOVE_TO_PRIV_NAMESPACE 7677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 7777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnertypedef bool _Rb_tree_Color_type; 7877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner//const _Rb_tree_Color_type _S_rb_tree_red = false; 7977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner//const _Rb_tree_Color_type _S_rb_tree_black = true; 8077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 8177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#define _S_rb_tree_red false 8277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#define _S_rb_tree_black true 8377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 8477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnerstruct _Rb_tree_node_base { 8577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner typedef _Rb_tree_Color_type _Color_type; 8677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner typedef _Rb_tree_node_base* _Base_ptr; 8777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 8877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Color_type _M_color; 8977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Base_ptr _M_parent; 9077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Base_ptr _M_left; 9177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Base_ptr _M_right; 9277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 9377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner static _Base_ptr _STLP_CALL _S_minimum(_Base_ptr __x) { 9477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner while (__x->_M_left != 0) __x = __x->_M_left; 9577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner return __x; 9677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 9777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 9877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner static _Base_ptr _STLP_CALL _S_maximum(_Base_ptr __x) { 9977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner while (__x->_M_right != 0) __x = __x->_M_right; 10077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner return __x; 10177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 10277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner}; 10377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 10477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnertemplate <class _Value> 10577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnerstruct _Rb_tree_node : public _Rb_tree_node_base { 10677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Value _M_value_field; 10777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner __TRIVIAL_STUFF(_Rb_tree_node) 10877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner}; 10977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 11077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnerstruct _Rb_tree_base_iterator; 11177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 11277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnertemplate <class _Dummy> 11377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnerclass _Rb_global { 11477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnerpublic: 11577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner typedef _Rb_tree_node_base* _Base_ptr; 11677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner // those used to be global functions 11777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner static void _STLP_CALL _Rebalance(_Base_ptr __x, _Base_ptr& __root); 11877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner static _Base_ptr _STLP_CALL _Rebalance_for_erase(_Base_ptr __z, 11977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Base_ptr& __root, 12077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Base_ptr& __leftmost, 12177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Base_ptr& __rightmost); 12277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner // those are from _Rb_tree_base_iterator - moved here to reduce code bloat 12377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner // moved here to reduce code bloat without templatizing _Rb_tree_base_iterator 12477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner static _Base_ptr _STLP_CALL _M_increment (_Base_ptr); 12577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner static _Base_ptr _STLP_CALL _M_decrement (_Base_ptr); 12677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner static void _STLP_CALL _Rotate_left (_Base_ptr __x, _Base_ptr& __root); 12777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner static void _STLP_CALL _Rotate_right(_Base_ptr __x, _Base_ptr& __root); 12877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner}; 12977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 13077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner# if defined (_STLP_USE_TEMPLATE_EXPORT) 13177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner_STLP_EXPORT_TEMPLATE_CLASS _Rb_global<bool>; 13277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner# endif 13377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 13477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnertypedef _Rb_global<bool> _Rb_global_inst; 13577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 13677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnerstruct _Rb_tree_base_iterator { 13777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner typedef _Rb_tree_node_base* _Base_ptr; 13877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner typedef bidirectional_iterator_tag iterator_category; 13977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner typedef ptrdiff_t difference_type; 14077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Base_ptr _M_node; 14177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Rb_tree_base_iterator() : _M_node(0) {} 14277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Rb_tree_base_iterator(_Base_ptr __x) : _M_node(__x) {} 14377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner}; 14477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 14577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnertemplate <class _Value, class _Traits> 14677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnerstruct _Rb_tree_iterator : public _Rb_tree_base_iterator { 14777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner typedef _Value value_type; 14877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner typedef typename _Traits::reference reference; 14977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner typedef typename _Traits::pointer pointer; 15077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner typedef _Rb_tree_iterator<_Value, _Traits> _Self; 15177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner typedef _Rb_tree_node_base* _Base_ptr; 15277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner typedef _Rb_tree_node<_Value>* _Link_type; 15377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 15477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner typedef typename _Traits::_NonConstTraits _NonConstTraits; 15577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner typedef _Rb_tree_iterator<_Value, _NonConstTraits> iterator; 15677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner typedef typename _Traits::_ConstTraits _ConstTraits; 15777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner typedef _Rb_tree_iterator<_Value, _ConstTraits> const_iterator; 15877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 15977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Rb_tree_iterator() {} 16077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#if !defined (_STLP_DEBUG) 16177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner /* In STL debug mode we need this constructor implicit for the pointer 16277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner * specialization implementation. 16377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner */ 16477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner explicit 16577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#endif 16677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Rb_tree_iterator(_Base_ptr __x) : _Rb_tree_base_iterator(__x) {} 16777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner //copy constructor for iterator and constructor from iterator for const_iterator 16877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Rb_tree_iterator(const iterator& __it) : _Rb_tree_base_iterator(__it._M_node) {} 16977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 17077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner reference operator*() const { 17177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner return __STATIC_CAST(_Link_type, _M_node)->_M_value_field; 17277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 17377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 17477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _STLP_DEFINE_ARROW_OPERATOR 17577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 17677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Self& operator++() { 17777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _M_node = _Rb_global_inst::_M_increment(_M_node); 17877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner return *this; 17977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 18077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Self operator++(int) { 18177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Self __tmp = *this; 18277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner ++(*this); 18377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner return __tmp; 18477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 18577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 18677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Self& operator--() { 18777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _M_node = _Rb_global_inst::_M_decrement(_M_node); 18877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner return *this; 18977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 19077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Self operator--(int) { 19177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Self __tmp = *this; 19277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner --(*this); 19377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner return __tmp; 19477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 19577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 19677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner bool operator == (const_iterator __rhs) const { 19777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner return _M_node == __rhs._M_node; 19877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 19977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner bool operator != (const_iterator __rhs) const { 20077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner return _M_node != __rhs._M_node; 20177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 20277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner}; 20377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 20477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) 20577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner_STLP_MOVE_TO_STD_NAMESPACE 20677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnertemplate <class _Value, class _Traits> 20777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnerstruct __type_traits<_STLP_PRIV _Rb_tree_iterator<_Value, _Traits> > { 20877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner typedef __false_type has_trivial_default_constructor; 20977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner typedef __true_type has_trivial_copy_constructor; 21077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner typedef __true_type has_trivial_assignment_operator; 21177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner typedef __true_type has_trivial_destructor; 21277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner typedef __false_type is_POD_type; 21377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner}; 21477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner_STLP_MOVE_TO_PRIV_NAMESPACE 21577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */ 21677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 21777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#if defined (_STLP_USE_OLD_HP_ITERATOR_QUERIES) 21877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner_STLP_MOVE_TO_STD_NAMESPACE 21977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnertemplate <class _Value, class _Traits> 22077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnerinline _Value* value_type(const _STLP_PRIV _Rb_tree_iterator<_Value, _Traits>&) 22177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner{ return (_Value*)0; } 22277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnerinline bidirectional_iterator_tag iterator_category(const _STLP_PRIV _Rb_tree_base_iterator&) 22377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner{ return bidirectional_iterator_tag(); } 22477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnerinline ptrdiff_t* distance_type(const _STLP_PRIV _Rb_tree_base_iterator&) 22577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner{ return (ptrdiff_t*) 0; } 22677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner_STLP_MOVE_TO_PRIV_NAMESPACE 22777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */ 22877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 22977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner// Base class to help EH 23077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 23177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnertemplate <class _Tp, class _Alloc> 23277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnerclass _Rb_tree_base { 23377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnerpublic: 23477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner typedef _Rb_tree_node_base _Node_base; 23577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner typedef _Rb_tree_node<_Tp> _Node; 23677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _STLP_FORCE_ALLOCATORS(_Tp, _Alloc) 23777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner typedef _Alloc allocator_type; 23877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnerprivate: 23977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner typedef _Rb_tree_base<_Tp, _Alloc> _Self; 24077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner typedef typename _Alloc_traits<_Node, _Alloc>::allocator_type _M_node_allocator_type; 24177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner typedef _STLP_alloc_proxy<_Node_base, _Node, _M_node_allocator_type> _AllocProxy; 24277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 24377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnerpublic: 24477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner allocator_type get_allocator() const { 24577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner return _STLP_CONVERT_ALLOCATOR(_M_header, _Tp); 24677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 24777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 24877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnerprotected: 24977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Rb_tree_base(const allocator_type& __a) : 25077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _M_header(_STLP_CONVERT_ALLOCATOR(__a, _Node), _Node_base() ) { 25177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _M_empty_initialize(); 25277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 25377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 25477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#if !defined (_STLP_NO_MOVE_SEMANTIC) 25577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Rb_tree_base(__move_source<_Self> src) : 25677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _M_header(__move_source<_AllocProxy>(src.get()._M_header)) { 25777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _M_rebind(&src.get()._M_header._M_data); 25877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner src.get()._M_empty_initialize(); 25977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 26077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#endif 26177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 26277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner void _M_empty_initialize() { 26377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _M_header._M_data._M_color = _S_rb_tree_red; // used to distinguish header from 26477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner // __root, in iterator.operator++ 26577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _M_header._M_data._M_parent = 0; 26677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _M_header._M_data._M_left = &_M_header._M_data; 26777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _M_header._M_data._M_right = &_M_header._M_data; 26877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 26977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 27077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner void _M_rebind(_Node_base *__static_node) { 27177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner if (_M_header._M_data._M_parent != 0) { 27277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _M_header._M_data._M_parent->_M_parent = &_M_header._M_data; 27377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 27477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner if (_M_header._M_data._M_right == __static_node) { 27577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _M_header._M_data._M_right = &_M_header._M_data; 27677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 27777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner if (_M_header._M_data._M_left == __static_node) { 27877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _M_header._M_data._M_left = &_M_header._M_data; 27977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 28077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 28177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 28277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _AllocProxy _M_header; 28377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner}; 28477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 28577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#if defined (_STLP_DEBUG) 28677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner# define _Rb_tree _STLP_NON_DBG_NAME(Rb_tree) 28777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#endif 28877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 28977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnertemplate <class _Key, class _Compare, 29077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner class _Value, class _KeyOfValue, class _Traits, 29177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _STLP_DFL_TMPL_PARAM(_Alloc, allocator<_Value>) > 29277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnerclass _Rb_tree : public _Rb_tree_base<_Value, _Alloc> { 29377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner typedef _Rb_tree_base<_Value, _Alloc> _Base; 29477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner typedef _Rb_tree<_Key, _Compare, _Value, _KeyOfValue, _Traits, _Alloc> _Self; 29577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnerprotected: 29677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner typedef _Rb_tree_node_base * _Base_ptr; 29777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner typedef _Rb_tree_node<_Value> _Node; 29877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner typedef _Node* _Link_type; 29977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner typedef _Rb_tree_Color_type _Color_type; 30077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnerpublic: 30177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner typedef _Key key_type; 30277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner typedef _Value value_type; 30377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner typedef typename _Traits::pointer pointer; 30477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner typedef const value_type* const_pointer; 30577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner typedef typename _Traits::reference reference; 30677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner typedef const value_type& const_reference; 30777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner typedef size_t size_type; 30877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner typedef ptrdiff_t difference_type; 30977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner typedef bidirectional_iterator_tag _Iterator_category; 31077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner typedef typename _Base::allocator_type allocator_type; 31177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 31277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnerprotected: 31377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 31477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _STLP_KEY_TYPE_FOR_CONT_EXT(key_type) 31577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Base_ptr _M_create_node(const value_type& __x) { 31677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Link_type __tmp = this->_M_header.allocate(1); 31777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _STLP_TRY { 31877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Copy_Construct(&__tmp->_M_value_field, __x); 31977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 32077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _STLP_UNWIND(this->_M_header.deallocate(__tmp,1)) 32177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _S_left(__tmp) = 0; 32277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _S_right(__tmp) = 0; 32377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner return __tmp; 32477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 32577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 32677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Base_ptr _M_clone_node(_Base_ptr __x) { 32777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Base_ptr __tmp = _M_create_node(_S_value(__x)); 32877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _S_color(__tmp) = _S_color(__x); 32977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner return __tmp; 33077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 33177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 33277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner size_type _M_node_count; // keeps track of size of tree 33377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Compare _M_key_compare; 33477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 33577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Base_ptr _M_root() const 33677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner { return this->_M_header._M_data._M_parent; } 33777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Base_ptr _M_leftmost() const 33877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner { return this->_M_header._M_data._M_left; } 33977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Base_ptr _M_rightmost() const 34077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner { return this->_M_header._M_data._M_right; } 34177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 34277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Base_ptr& _M_root() 34377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner { return this->_M_header._M_data._M_parent; } 34477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Base_ptr& _M_leftmost() 34577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner { return this->_M_header._M_data._M_left; } 34677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Base_ptr& _M_rightmost() 34777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner { return this->_M_header._M_data._M_right; } 34877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 34977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner static _Base_ptr& _STLP_CALL _S_left(_Base_ptr __x) 35077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner { return __x->_M_left; } 35177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner static _Base_ptr& _STLP_CALL _S_right(_Base_ptr __x) 35277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner { return __x->_M_right; } 35377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner static _Base_ptr& _STLP_CALL _S_parent(_Base_ptr __x) 35477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner { return __x->_M_parent; } 35577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner static value_type& _STLP_CALL _S_value(_Base_ptr __x) 35677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner { return __STATIC_CAST(_Link_type, __x)->_M_value_field; } 35777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner static const _Key& _STLP_CALL _S_key(_Base_ptr __x) 35877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner { return _KeyOfValue()(_S_value(__x));} 35977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner static _Color_type& _STLP_CALL _S_color(_Base_ptr __x) 36077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner { return (_Color_type&)(__x->_M_color); } 36177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 36277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner static _Base_ptr _STLP_CALL _S_minimum(_Base_ptr __x) 36377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner { return _Rb_tree_node_base::_S_minimum(__x); } 36477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 36577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner static _Base_ptr _STLP_CALL _S_maximum(_Base_ptr __x) 36677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner { return _Rb_tree_node_base::_S_maximum(__x); } 36777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 36877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnerpublic: 36977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner typedef typename _Traits::_NonConstTraits _NonConstTraits; 37077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner typedef typename _Traits::_ConstTraits _ConstTraits; 37177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner typedef _Rb_tree_iterator<value_type, _NonConstTraits> iterator; 37277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner typedef _Rb_tree_iterator<value_type, _ConstTraits> const_iterator; 37377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _STLP_DECLARE_BIDIRECTIONAL_REVERSE_ITERATORS; 37477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 37577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnerprivate: 37677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner iterator _M_insert(_Base_ptr __parent, const value_type& __val, _Base_ptr __on_left = 0, _Base_ptr __on_right = 0); 37777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Base_ptr _M_copy(_Base_ptr __x, _Base_ptr __p); 37877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner void _M_erase(_Base_ptr __x); 37977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 38077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnerpublic: 38177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner // allocation/deallocation 38277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Rb_tree() 38377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner : _Rb_tree_base<_Value, _Alloc>(allocator_type()), _M_node_count(0), _M_key_compare(_Compare()) 38477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner {} 38577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 38677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Rb_tree(const _Compare& __comp) 38777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner : _Rb_tree_base<_Value, _Alloc>(allocator_type()), _M_node_count(0), _M_key_compare(__comp) 38877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner {} 38977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 39077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Rb_tree(const _Compare& __comp, const allocator_type& __a) 39177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner : _Rb_tree_base<_Value, _Alloc>(__a), _M_node_count(0), _M_key_compare(__comp) 39277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner {} 39377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 39477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Rb_tree(const _Self& __x) 39577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner : _Rb_tree_base<_Value, _Alloc>(__x.get_allocator()), 39677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _M_node_count(0), _M_key_compare(__x._M_key_compare) { 39777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner if (__x._M_root() != 0) { 39877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _S_color(&this->_M_header._M_data) = _S_rb_tree_red; 39977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _M_root() = _M_copy(__x._M_root(), &this->_M_header._M_data); 40077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _M_leftmost() = _S_minimum(_M_root()); 40177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _M_rightmost() = _S_maximum(_M_root()); 40277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 40377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _M_node_count = __x._M_node_count; 40477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 40577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 40677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#if !defined (_STLP_NO_MOVE_SEMANTIC) 40777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Rb_tree(__move_source<_Self> src) 40877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner : _Rb_tree_base<_Value, _Alloc>(__move_source<_Base>(src.get())), 40977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _M_node_count(src.get()._M_node_count), 41077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _M_key_compare(_AsMoveSource(src.get()._M_key_compare)) 41177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner { src.get()._M_node_count = 0; } 41277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#endif 41377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 41477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner ~_Rb_tree() { clear(); } 41577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Self& operator=(const _Self& __x); 41677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 41777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnerpublic: 41877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner // accessors: 41977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Compare key_comp() const { return _M_key_compare; } 42077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 42177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner iterator begin() { return iterator(_M_leftmost()); } 42277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner const_iterator begin() const { return const_iterator(_M_leftmost()); } 42377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner iterator end() { return iterator(&this->_M_header._M_data); } 42477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner const_iterator end() const { return const_iterator(__CONST_CAST(_Base_ptr, &this->_M_header._M_data)); } 42577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 42677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner reverse_iterator rbegin() { return reverse_iterator(end()); } 42777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner const_reverse_iterator rbegin() const 42877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner { return const_reverse_iterator(end()); } 42977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner reverse_iterator rend() { return reverse_iterator(begin()); } 43077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner const_reverse_iterator rend() const 43177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner { return const_reverse_iterator(begin()); } 43277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner bool empty() const { return _M_node_count == 0; } 43377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner size_type size() const { return _M_node_count; } 43477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner size_type max_size() const { return size_type(-1); } 43577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 43677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner void swap(_Self& __t) { 43777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner if (__t.empty()) { 43877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner if (this->empty()) return; 43977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner __t._M_header.swap(this->_M_header); 44077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner __t._M_rebind(&this->_M_header._M_data); 44177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner this->_M_empty_initialize(); 44277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 44377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner else if (this->empty()) { 44477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner __t.swap(*this); 44577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner return; 44677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 44777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner else { 44877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner this->_M_header.swap(__t._M_header); 44977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner this->_M_rebind(&__t._M_header._M_data); 45077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner __t._M_rebind(&this->_M_header._M_data); 45177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 45277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _STLP_STD::swap(_M_node_count, __t._M_node_count); 45377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _STLP_STD::swap(_M_key_compare, __t._M_key_compare); 45477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 45577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 45677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnerpublic: 45777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner // insert/erase 45877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner pair<iterator,bool> insert_unique(const value_type& __x); 45977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner iterator insert_equal(const value_type& __x); 46077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 46177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner iterator insert_unique(iterator __pos, const value_type& __x); 46277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner iterator insert_equal(iterator __pos, const value_type& __x); 46377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 46477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#if defined (_STLP_MEMBER_TEMPLATES) 46577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner template<class _II> void insert_equal(_II __first, _II __last) { 46677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner for ( ; __first != __last; ++__first) 46777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner insert_equal(*__first); 46877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 46977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner template<class _II> void insert_unique(_II __first, _II __last) { 47077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner for ( ; __first != __last; ++__first) 47177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner insert_unique(*__first); 47277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 47377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#else 47477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner void insert_unique(const_iterator __first, const_iterator __last) { 47577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner for ( ; __first != __last; ++__first) 47677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner insert_unique(*__first); 47777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 47877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner void insert_unique(const value_type* __first, const value_type* __last) { 47977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner for ( ; __first != __last; ++__first) 48077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner insert_unique(*__first); 48177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 48277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner void insert_equal(const_iterator __first, const_iterator __last) { 48377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner for ( ; __first != __last; ++__first) 48477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner insert_equal(*__first); 48577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 48677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner void insert_equal(const value_type* __first, const value_type* __last) { 48777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner for ( ; __first != __last; ++__first) 48877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner insert_equal(*__first); 48977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 49077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#endif 49177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 49277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner void erase(iterator __pos) { 49377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Base_ptr __x = _Rb_global_inst::_Rebalance_for_erase(__pos._M_node, 49477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner this->_M_header._M_data._M_parent, 49577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner this->_M_header._M_data._M_left, 49677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner this->_M_header._M_data._M_right); 49777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _STLP_STD::_Destroy(&_S_value(__x)); 49877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner this->_M_header.deallocate(__STATIC_CAST(_Link_type, __x), 1); 49977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner --_M_node_count; 50077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 50177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 50277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner size_type erase(const key_type& __x) { 50377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner pair<iterator,iterator> __p = equal_range(__x); 50477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner size_type __n = _STLP_STD::distance(__p.first, __p.second); 50577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner erase(__p.first, __p.second); 50677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner return __n; 50777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 50877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 50977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner size_type erase_unique(const key_type& __x) { 51077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner iterator __i = find(__x); 51177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner if (__i._M_node != &this->_M_header._M_data) { 51277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner erase(__i); 51377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner return 1; 51477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 51577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner return 0; 51677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 51777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 51877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner void erase(iterator __first, iterator __last) { 51977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner if (__first._M_node == this->_M_header._M_data._M_left && // begin() 52077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner __last._M_node == &this->_M_header._M_data) // end() 52177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner clear(); 52277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner else 52377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner while (__first != __last) erase(__first++); 52477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 52577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 52677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner void erase(const key_type* __first, const key_type* __last) { 52777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner while (__first != __last) erase(*__first++); 52877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 52977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 53077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner void clear() { 53177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner if (_M_node_count != 0) { 53277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _M_erase(_M_root()); 53377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _M_leftmost() = &this->_M_header._M_data; 53477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _M_root() = 0; 53577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _M_rightmost() = &this->_M_header._M_data; 53677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _M_node_count = 0; 53777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 53877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 53977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 54077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnerpublic: 54177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner // set operations: 54277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _STLP_TEMPLATE_FOR_CONT_EXT 54377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner iterator find(const _KT& __k) { return iterator(_M_find(__k)); } 54477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _STLP_TEMPLATE_FOR_CONT_EXT 54577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner const_iterator find(const _KT& __k) const { return const_iterator(_M_find(__k)); } 54677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnerprivate: 54777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _STLP_TEMPLATE_FOR_CONT_EXT 54877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Base_ptr _M_find(const _KT& __k) const { 54977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Base_ptr __y = __CONST_CAST(_Base_ptr, &this->_M_header._M_data); // Last node which is not less than __k. 55077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Base_ptr __x = _M_root(); // Current node. 55177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 55277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner while (__x != 0) 55377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner if (!_M_key_compare(_S_key(__x), __k)) 55477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner __y = __x, __x = _S_left(__x); 55577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner else 55677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner __x = _S_right(__x); 55777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 55877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner if (__y != &this->_M_header._M_data) { 55977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner if (_M_key_compare(__k, _S_key(__y))) { 56077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner __y = __CONST_CAST(_Base_ptr, &this->_M_header._M_data); 56177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 56277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 56377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner return __y; 56477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 56577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 56677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _STLP_TEMPLATE_FOR_CONT_EXT 56777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Base_ptr _M_lower_bound(const _KT& __k) const { 56877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Base_ptr __y = __CONST_CAST(_Base_ptr, &this->_M_header._M_data); /* Last node which is not less than __k. */ 56977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Base_ptr __x = _M_root(); /* Current node. */ 57077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 57177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner while (__x != 0) 57277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner if (!_M_key_compare(_S_key(__x), __k)) 57377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner __y = __x, __x = _S_left(__x); 57477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner else 57577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner __x = _S_right(__x); 57677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 57777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner return __y; 57877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 57977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 58077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _STLP_TEMPLATE_FOR_CONT_EXT 58177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Base_ptr _M_upper_bound(const _KT& __k) const { 58277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Base_ptr __y = __CONST_CAST(_Base_ptr, &this->_M_header._M_data); /* Last node which is greater than __k. */ 58377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Base_ptr __x = _M_root(); /* Current node. */ 58477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 58577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner while (__x != 0) 58677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner if (_M_key_compare(__k, _S_key(__x))) 58777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner __y = __x, __x = _S_left(__x); 58877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner else 58977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner __x = _S_right(__x); 59077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 59177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner return __y; 59277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 59377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 59477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnerpublic: 59577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _STLP_TEMPLATE_FOR_CONT_EXT 59677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner size_type count(const _KT& __x) const { 59777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner pair<const_iterator, const_iterator> __p = equal_range(__x); 59877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner return _STLP_STD::distance(__p.first, __p.second); 59977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 60077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _STLP_TEMPLATE_FOR_CONT_EXT 60177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner iterator lower_bound(const _KT& __x) { return iterator(_M_lower_bound(__x)); } 60277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _STLP_TEMPLATE_FOR_CONT_EXT 60377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner const_iterator lower_bound(const _KT& __x) const { return const_iterator(_M_lower_bound(__x)); } 60477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _STLP_TEMPLATE_FOR_CONT_EXT 60577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner iterator upper_bound(const _KT& __x) { return iterator(_M_upper_bound(__x)); } 60677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _STLP_TEMPLATE_FOR_CONT_EXT 60777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner const_iterator upper_bound(const _KT& __x) const { return const_iterator(_M_upper_bound(__x)); } 60877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _STLP_TEMPLATE_FOR_CONT_EXT 60977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner pair<iterator,iterator> equal_range(const _KT& __x) 61077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner { return pair<iterator, iterator>(lower_bound(__x), upper_bound(__x)); } 61177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _STLP_TEMPLATE_FOR_CONT_EXT 61277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner pair<const_iterator, const_iterator> equal_range(const _KT& __x) const 61377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner { return pair<const_iterator, const_iterator>(lower_bound(__x), upper_bound(__x)); } 61477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _STLP_TEMPLATE_FOR_CONT_EXT 61577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner pair<iterator,iterator> equal_range_unique(const _KT& __x) { 61677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner pair<iterator, iterator> __p; 61777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner __p.second = lower_bound(__x); 61877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner if (__p.second._M_node != &this->_M_header._M_data && 61977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner !_M_key_compare(__x, _S_key(__p.second._M_node))) { 62077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner __p.first = __p.second++; 62177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 62277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner else { 62377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner __p.first = __p.second; 62477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 62577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner return __p; 62677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 62777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _STLP_TEMPLATE_FOR_CONT_EXT 62877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner pair<const_iterator, const_iterator> equal_range_unique(const _KT& __x) const { 62977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner pair<const_iterator, const_iterator> __p; 63077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner __p.second = lower_bound(__x); 63177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner if (__p.second._M_node != &this->_M_header._M_data && 63277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner !_M_key_compare(__x, _S_key(__p.second._M_node))) { 63377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner __p.first = __p.second++; 63477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 63577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner else { 63677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner __p.first = __p.second; 63777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 63877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner return __p; 63977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 64077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 64177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#if defined (_STLP_DEBUG) 64277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnerpublic: 64377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner // Debugging. 64477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner bool __rb_verify() const; 64577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#endif //_STLP_DEBUG 64677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner}; 64777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 64877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#if defined (_STLP_DEBUG) 64977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner# undef _Rb_tree 65077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#endif 65177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 65277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner_STLP_MOVE_TO_STD_NAMESPACE 65377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 65477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner_STLP_END_NAMESPACE 65577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 65677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#if !defined (_STLP_LINK_TIME_INSTANTIATION) 65777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner# include <stl/_tree.c> 65877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#endif 65977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 66077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#if defined (_STLP_DEBUG) 66177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner# include <stl/debug/_tree.h> 66277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#endif 66377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 66477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner_STLP_BEGIN_NAMESPACE 66577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 66677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#define _STLP_TEMPLATE_HEADER template <class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, class _Alloc> 66777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#define _STLP_TEMPLATE_CONTAINER _STLP_PRIV _Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc> 66877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#include <stl/_relops_cont.h> 66977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#undef _STLP_TEMPLATE_CONTAINER 67077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#undef _STLP_TEMPLATE_HEADER 67177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 67277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) && !defined (_STLP_NO_MOVE_SEMANTIC) 67377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnertemplate <class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, class _Alloc> 67477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnerstruct __move_traits<_STLP_PRIV _Rb_tree<_Key, _Compare, _Value, _KeyOfValue, _Traits, _Alloc> > 67577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner : _STLP_PRIV __move_traits_help2<_Compare, _Alloc> {}; 67677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#endif 67777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 67877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner_STLP_END_NAMESPACE 67977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 68077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#endif /* _STLP_INTERNAL_TREE_H */ 68177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 68277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner// Local Variables: 68377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner// mode:C++ 68477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner// End: 685