19720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block/* 29720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * 39720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Copyright (c) 1994 49720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Hewlett-Packard Company 59720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * 69720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Copyright (c) 1996,1997 79720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Silicon Graphics Computer Systems, Inc. 89720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * 99720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Copyright (c) 1997 109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Moscow Center for SPARC Technology 119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * 129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Copyright (c) 1999 139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Boris Fomitchev 149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * 159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * This material is provided "as is", with absolutely no warranty expressed 169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * or implied. Any use is at your own risk. 179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * 189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Permission to use or copy this software for any purpose is hereby granted 199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * without fee, provided the above notices are retained on all copies. 209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Permission to modify the code and to distribute modified code is granted, 219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * provided the above notices are retained, and a notice that the code was 229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * modified is included with the above copyright notice. 239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * 249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block */ 259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block/* NOTE: This is an internal header file, included by other STL headers. 279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * You should not attempt to use it directly. 289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block */ 299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#ifndef _STLP_INTERNAL_TREE_H 319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#define _STLP_INTERNAL_TREE_H 329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block/* 349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve BlockRed-black tree class, designed for use in implementing STL 369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockassociative containers (set, multiset, map, and multimap). The 379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinsertion and deletion algorithms are based on those in Cormen, 389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve BlockLeiserson, and Rivest, Introduction to Algorithms (MIT Press, 1990), 399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockexcept that 409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block(1) the header cell is maintained with links not only to the root 429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockbut also to the leftmost node of the tree, to enable constant time 439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockbegin(), and to the rightmost node of the tree, to enable linear time 449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockperformance when used with the generic set algorithms (set_union, 459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocketc.); 469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block(2) when a node being deleted has two children its successor node is 489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockrelinked into its place, rather than copied, so that the only 499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockiterators invalidated are those referring to the deleted node. 509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block*/ 529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#ifndef _STLP_INTERNAL_ALGOBASE_H 549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# include <stl/_algobase.h> 559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#ifndef _STLP_INTERNAL_ALLOC_H 589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# include <stl/_alloc.h> 599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#ifndef _STLP_INTERNAL_ITERATOR_H 629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# include <stl/_iterator.h> 639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#ifndef _STLP_INTERNAL_CONSTRUCT_H 669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# include <stl/_construct.h> 679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#ifndef _STLP_INTERNAL_FUNCTION_BASE_H 709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# include <stl/_function_base.h> 719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_BEGIN_NAMESPACE 749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_PRIV_NAMESPACE 769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktypedef bool _Rb_tree_Color_type; 789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block//const _Rb_tree_Color_type _S_rb_tree_red = false; 799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block//const _Rb_tree_Color_type _S_rb_tree_black = true; 809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#define _S_rb_tree_red false 829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#define _S_rb_tree_black true 839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockstruct _Rb_tree_node_base { 859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef _Rb_tree_Color_type _Color_type; 869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef _Rb_tree_node_base* _Base_ptr; 879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Color_type _M_color; 899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Base_ptr _M_parent; 909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Base_ptr _M_left; 919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Base_ptr _M_right; 929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block static _Base_ptr _STLP_CALL _S_minimum(_Base_ptr __x) { 949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (__x->_M_left != 0) __x = __x->_M_left; 959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __x; 969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block static _Base_ptr _STLP_CALL _S_maximum(_Base_ptr __x) { 999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (__x->_M_right != 0) __x = __x->_M_right; 1009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __x; 1019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 1029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block}; 1039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _Value> 1059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockstruct _Rb_tree_node : public _Rb_tree_node_base { 1069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Value _M_value_field; 1079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __TRIVIAL_STUFF(_Rb_tree_node) 1089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block}; 1099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockstruct _Rb_tree_base_iterator; 1119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _Dummy> 1139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockclass _Rb_global { 1149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic: 1159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef _Rb_tree_node_base* _Base_ptr; 1169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // those used to be global functions 1179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block static void _STLP_CALL _Rebalance(_Base_ptr __x, _Base_ptr& __root); 1189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block static _Base_ptr _STLP_CALL _Rebalance_for_erase(_Base_ptr __z, 1199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Base_ptr& __root, 1209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Base_ptr& __leftmost, 1219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Base_ptr& __rightmost); 1229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // those are from _Rb_tree_base_iterator - moved here to reduce code bloat 1239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // moved here to reduce code bloat without templatizing _Rb_tree_base_iterator 1249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block static _Base_ptr _STLP_CALL _M_increment (_Base_ptr); 1259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block static _Base_ptr _STLP_CALL _M_decrement (_Base_ptr); 1269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block static void _STLP_CALL _Rotate_left (_Base_ptr __x, _Base_ptr& __root); 1279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block static void _STLP_CALL _Rotate_right(_Base_ptr __x, _Base_ptr& __root); 1289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block}; 1299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# if defined (_STLP_USE_TEMPLATE_EXPORT) 1319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_EXPORT_TEMPLATE_CLASS _Rb_global<bool>; 1329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# endif 1339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktypedef _Rb_global<bool> _Rb_global_inst; 1359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockstruct _Rb_tree_base_iterator { 1379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef _Rb_tree_node_base* _Base_ptr; 1389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef bidirectional_iterator_tag iterator_category; 1399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef ptrdiff_t difference_type; 1409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Base_ptr _M_node; 1419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Rb_tree_base_iterator() : _M_node(0) {} 1429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Rb_tree_base_iterator(_Base_ptr __x) : _M_node(__x) {} 1439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block}; 1449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _Value, class _Traits> 1469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockstruct _Rb_tree_iterator : public _Rb_tree_base_iterator { 1479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef _Value value_type; 1489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef typename _Traits::reference reference; 1499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef typename _Traits::pointer pointer; 1509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef _Rb_tree_iterator<_Value, _Traits> _Self; 1519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef _Rb_tree_node_base* _Base_ptr; 1529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef _Rb_tree_node<_Value>* _Link_type; 1539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef typename _Traits::_NonConstTraits _NonConstTraits; 1559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef _Rb_tree_iterator<_Value, _NonConstTraits> iterator; 1569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef typename _Traits::_ConstTraits _ConstTraits; 1579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef _Rb_tree_iterator<_Value, _ConstTraits> const_iterator; 1589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Rb_tree_iterator() {} 1609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if !defined (_STLP_DEBUG) 1619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block /* In STL debug mode we need this constructor implicit for the pointer 1629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * specialization implementation. 1639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block */ 1649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block explicit 1659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 1669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Rb_tree_iterator(_Base_ptr __x) : _Rb_tree_base_iterator(__x) {} 1679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block //copy constructor for iterator and constructor from iterator for const_iterator 1689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Rb_tree_iterator(const iterator& __it) : _Rb_tree_base_iterator(__it._M_node) {} 1699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block reference operator*() const { 1719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __STATIC_CAST(_Link_type, _M_node)->_M_value_field; 1729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 1739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEFINE_ARROW_OPERATOR 1759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Self& operator++() { 1779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_node = _Rb_global_inst::_M_increment(_M_node); 1789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return *this; 1799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 1809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Self operator++(int) { 1819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Self __tmp = *this; 1829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++(*this); 1839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __tmp; 1849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 1859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Self& operator--() { 1879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_node = _Rb_global_inst::_M_decrement(_M_node); 1889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return *this; 1899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 1909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Self operator--(int) { 1919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Self __tmp = *this; 1929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block --(*this); 1939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __tmp; 1949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 1959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block bool operator == (const_iterator __rhs) const { 1979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _M_node == __rhs._M_node; 1989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 1999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block bool operator != (const_iterator __rhs) const { 2009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _M_node != __rhs._M_node; 2019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block}; 2039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) 2059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_STD_NAMESPACE 2069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _Value, class _Traits> 2079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockstruct __type_traits<_STLP_PRIV _Rb_tree_iterator<_Value, _Traits> > { 2089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef __false_type has_trivial_default_constructor; 2099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef __true_type has_trivial_copy_constructor; 2109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef __true_type has_trivial_assignment_operator; 2119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef __true_type has_trivial_destructor; 2129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef __false_type is_POD_type; 2139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block}; 2149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_PRIV_NAMESPACE 2159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */ 2169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if defined (_STLP_USE_OLD_HP_ITERATOR_QUERIES) 2189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_STD_NAMESPACE 2199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _Value, class _Traits> 2209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline _Value* value_type(const _STLP_PRIV _Rb_tree_iterator<_Value, _Traits>&) 2219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block{ return (_Value*)0; } 2229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline bidirectional_iterator_tag iterator_category(const _STLP_PRIV _Rb_tree_base_iterator&) 2239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block{ return bidirectional_iterator_tag(); } 2249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline ptrdiff_t* distance_type(const _STLP_PRIV _Rb_tree_base_iterator&) 2259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block{ return (ptrdiff_t*) 0; } 2269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_PRIV_NAMESPACE 2279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */ 2289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// Base class to help EH 2309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _Tp, class _Alloc> 2329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockclass _Rb_tree_base { 2339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic: 2349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef _Rb_tree_node_base _Node_base; 2359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef _Rb_tree_node<_Tp> _Node; 2369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_FORCE_ALLOCATORS(_Tp, _Alloc) 237e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott typedef _Alloc allocator_type; 2389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockprivate: 2399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef _Rb_tree_base<_Tp, _Alloc> _Self; 2409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef typename _Alloc_traits<_Node, _Alloc>::allocator_type _M_node_allocator_type; 2419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef _STLP_alloc_proxy<_Node_base, _Node, _M_node_allocator_type> _AllocProxy; 2429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic: 2449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block allocator_type get_allocator() const { 2459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _STLP_CONVERT_ALLOCATOR(_M_header, _Tp); 2469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockprotected: 2499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Rb_tree_base(const allocator_type& __a) : 2509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_header(_STLP_CONVERT_ALLOCATOR(__a, _Node), _Node_base() ) { 2519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_empty_initialize(); 2529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 253e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 254e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#if !defined (_STLP_NO_MOVE_SEMANTIC) 2559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Rb_tree_base(__move_source<_Self> src) : 2569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_header(__move_source<_AllocProxy>(src.get()._M_header)) { 2579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_rebind(&src.get()._M_header._M_data); 2589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block src.get()._M_empty_initialize(); 2599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 260e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#endif 261e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 2629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block void _M_empty_initialize() { 2639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_header._M_data._M_color = _S_rb_tree_red; // used to distinguish header from 2649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // __root, in iterator.operator++ 2659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_header._M_data._M_parent = 0; 2669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_header._M_data._M_left = &_M_header._M_data; 2679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_header._M_data._M_right = &_M_header._M_data; 2689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block void _M_rebind(_Node_base *__static_node) { 2719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (_M_header._M_data._M_parent != 0) { 2729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_header._M_data._M_parent->_M_parent = &_M_header._M_data; 2739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (_M_header._M_data._M_right == __static_node) { 2759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_header._M_data._M_right = &_M_header._M_data; 2769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (_M_header._M_data._M_left == __static_node) { 2789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_header._M_data._M_left = &_M_header._M_data; 2799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _AllocProxy _M_header; 2839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block}; 2849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if defined (_STLP_DEBUG) 2869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# define _Rb_tree _STLP_NON_DBG_NAME(Rb_tree) 2879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 2889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _Key, class _Compare, 2909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _Value, class _KeyOfValue, class _Traits, 291e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_DFL_TMPL_PARAM(_Alloc, allocator<_Value>) > 2929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockclass _Rb_tree : public _Rb_tree_base<_Value, _Alloc> { 2939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef _Rb_tree_base<_Value, _Alloc> _Base; 2949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef _Rb_tree<_Key, _Compare, _Value, _KeyOfValue, _Traits, _Alloc> _Self; 2959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockprotected: 2969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef _Rb_tree_node_base * _Base_ptr; 2979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef _Rb_tree_node<_Value> _Node; 2989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef _Node* _Link_type; 2999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef _Rb_tree_Color_type _Color_type; 3009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic: 3019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef _Key key_type; 3029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef _Value value_type; 3039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef typename _Traits::pointer pointer; 3049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef const value_type* const_pointer; 3059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef typename _Traits::reference reference; 3069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef const value_type& const_reference; 3079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef size_t size_type; 3089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef ptrdiff_t difference_type; 3099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef bidirectional_iterator_tag _Iterator_category; 3109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef typename _Base::allocator_type allocator_type; 3119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockprotected: 3139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_KEY_TYPE_FOR_CONT_EXT(key_type) 3159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Base_ptr _M_create_node(const value_type& __x) { 3169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Link_type __tmp = this->_M_header.allocate(1); 3179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_TRY { 3189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Copy_Construct(&__tmp->_M_value_field, __x); 3199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 3209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_UNWIND(this->_M_header.deallocate(__tmp,1)) 3219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _S_left(__tmp) = 0; 3229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _S_right(__tmp) = 0; 3239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __tmp; 3249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 3259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Base_ptr _M_clone_node(_Base_ptr __x) { 3279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Base_ptr __tmp = _M_create_node(_S_value(__x)); 3289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _S_color(__tmp) = _S_color(__x); 3299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __tmp; 3309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 3319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_type _M_node_count; // keeps track of size of tree 3339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Compare _M_key_compare; 3349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Base_ptr _M_root() const 3369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { return this->_M_header._M_data._M_parent; } 3379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Base_ptr _M_leftmost() const 3389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { return this->_M_header._M_data._M_left; } 3399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Base_ptr _M_rightmost() const 3409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { return this->_M_header._M_data._M_right; } 3419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Base_ptr& _M_root() 3439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { return this->_M_header._M_data._M_parent; } 3449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Base_ptr& _M_leftmost() 3459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { return this->_M_header._M_data._M_left; } 3469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Base_ptr& _M_rightmost() 3479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { return this->_M_header._M_data._M_right; } 3489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block static _Base_ptr& _STLP_CALL _S_left(_Base_ptr __x) 3509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { return __x->_M_left; } 3519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block static _Base_ptr& _STLP_CALL _S_right(_Base_ptr __x) 3529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { return __x->_M_right; } 3539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block static _Base_ptr& _STLP_CALL _S_parent(_Base_ptr __x) 3549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { return __x->_M_parent; } 3559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block static value_type& _STLP_CALL _S_value(_Base_ptr __x) 3569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { return __STATIC_CAST(_Link_type, __x)->_M_value_field; } 3579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block static const _Key& _STLP_CALL _S_key(_Base_ptr __x) 3589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { return _KeyOfValue()(_S_value(__x));} 3599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block static _Color_type& _STLP_CALL _S_color(_Base_ptr __x) 3609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { return (_Color_type&)(__x->_M_color); } 3619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block static _Base_ptr _STLP_CALL _S_minimum(_Base_ptr __x) 3639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { return _Rb_tree_node_base::_S_minimum(__x); } 3649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block static _Base_ptr _STLP_CALL _S_maximum(_Base_ptr __x) 3669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { return _Rb_tree_node_base::_S_maximum(__x); } 3679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic: 3699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef typename _Traits::_NonConstTraits _NonConstTraits; 3709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef typename _Traits::_ConstTraits _ConstTraits; 3719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef _Rb_tree_iterator<value_type, _NonConstTraits> iterator; 3729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef _Rb_tree_iterator<value_type, _ConstTraits> const_iterator; 3739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DECLARE_BIDIRECTIONAL_REVERSE_ITERATORS; 3749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockprivate: 3769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block iterator _M_insert(_Base_ptr __parent, const value_type& __val, _Base_ptr __on_left = 0, _Base_ptr __on_right = 0); 3779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Base_ptr _M_copy(_Base_ptr __x, _Base_ptr __p); 3789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block void _M_erase(_Base_ptr __x); 3799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic: 3819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // allocation/deallocation 3829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Rb_tree() 3839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block : _Rb_tree_base<_Value, _Alloc>(allocator_type()), _M_node_count(0), _M_key_compare(_Compare()) 3849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block {} 3859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Rb_tree(const _Compare& __comp) 3879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block : _Rb_tree_base<_Value, _Alloc>(allocator_type()), _M_node_count(0), _M_key_compare(__comp) 3889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block {} 3899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Rb_tree(const _Compare& __comp, const allocator_type& __a) 3919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block : _Rb_tree_base<_Value, _Alloc>(__a), _M_node_count(0), _M_key_compare(__comp) 3929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block {} 3939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Rb_tree(const _Self& __x) 3959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block : _Rb_tree_base<_Value, _Alloc>(__x.get_allocator()), 3969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_node_count(0), _M_key_compare(__x._M_key_compare) { 3979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__x._M_root() != 0) { 3989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _S_color(&this->_M_header._M_data) = _S_rb_tree_red; 3999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_root() = _M_copy(__x._M_root(), &this->_M_header._M_data); 4009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_leftmost() = _S_minimum(_M_root()); 4019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_rightmost() = _S_maximum(_M_root()); 4029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 4039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_node_count = __x._M_node_count; 4049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 4059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 406e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#if !defined (_STLP_NO_MOVE_SEMANTIC) 4079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Rb_tree(__move_source<_Self> src) 4089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block : _Rb_tree_base<_Value, _Alloc>(__move_source<_Base>(src.get())), 4099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_node_count(src.get()._M_node_count), 410e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _M_key_compare(_AsMoveSource(src.get()._M_key_compare)) 411e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott { src.get()._M_node_count = 0; } 412e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#endif 4139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ~_Rb_tree() { clear(); } 4159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Self& operator=(const _Self& __x); 4169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic: 4189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // accessors: 4199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Compare key_comp() const { return _M_key_compare; } 4209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block iterator begin() { return iterator(_M_leftmost()); } 4229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const_iterator begin() const { return const_iterator(_M_leftmost()); } 4239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block iterator end() { return iterator(&this->_M_header._M_data); } 4249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const_iterator end() const { return const_iterator(__CONST_CAST(_Base_ptr, &this->_M_header._M_data)); } 4259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block reverse_iterator rbegin() { return reverse_iterator(end()); } 4279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const_reverse_iterator rbegin() const 4289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { return const_reverse_iterator(end()); } 4299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block reverse_iterator rend() { return reverse_iterator(begin()); } 4309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const_reverse_iterator rend() const 4319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { return const_reverse_iterator(begin()); } 4329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block bool empty() const { return _M_node_count == 0; } 4339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_type size() const { return _M_node_count; } 4349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_type max_size() const { return size_type(-1); } 4359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block void swap(_Self& __t) { 4379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__t.empty()) { 4389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (this->empty()) return; 4399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __t._M_header.swap(this->_M_header); 4409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __t._M_rebind(&this->_M_header._M_data); 4419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block this->_M_empty_initialize(); 4429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 4439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else if (this->empty()) { 4449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __t.swap(*this); 4459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return; 4469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 4479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else { 4489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block this->_M_header.swap(__t._M_header); 4499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block this->_M_rebind(&__t._M_header._M_data); 4509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __t._M_rebind(&this->_M_header._M_data); 4519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 4529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_STD::swap(_M_node_count, __t._M_node_count); 4539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_STD::swap(_M_key_compare, __t._M_key_compare); 4549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 4559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic: 4579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // insert/erase 4589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block pair<iterator,bool> insert_unique(const value_type& __x); 4599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block iterator insert_equal(const value_type& __x); 4609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block iterator insert_unique(iterator __pos, const value_type& __x); 4629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block iterator insert_equal(iterator __pos, const value_type& __x); 4639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if defined (_STLP_MEMBER_TEMPLATES) 4659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block template<class _II> void insert_equal(_II __first, _II __last) { 4669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for ( ; __first != __last; ++__first) 4679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block insert_equal(*__first); 4689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 4699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block template<class _II> void insert_unique(_II __first, _II __last) { 4709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for ( ; __first != __last; ++__first) 4719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block insert_unique(*__first); 4729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 4739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#else 4749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block void insert_unique(const_iterator __first, const_iterator __last) { 4759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for ( ; __first != __last; ++__first) 4769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block insert_unique(*__first); 4779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 4789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block void insert_unique(const value_type* __first, const value_type* __last) { 4799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for ( ; __first != __last; ++__first) 4809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block insert_unique(*__first); 4819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 4829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block void insert_equal(const_iterator __first, const_iterator __last) { 4839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for ( ; __first != __last; ++__first) 4849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block insert_equal(*__first); 4859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 4869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block void insert_equal(const value_type* __first, const value_type* __last) { 4879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for ( ; __first != __last; ++__first) 4889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block insert_equal(*__first); 4899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 4909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 4919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block void erase(iterator __pos) { 4939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Base_ptr __x = _Rb_global_inst::_Rebalance_for_erase(__pos._M_node, 4949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block this->_M_header._M_data._M_parent, 4959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block this->_M_header._M_data._M_left, 4969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block this->_M_header._M_data._M_right); 4979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_STD::_Destroy(&_S_value(__x)); 4989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block this->_M_header.deallocate(__STATIC_CAST(_Link_type, __x), 1); 4999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block --_M_node_count; 5009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 5019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_type erase(const key_type& __x) { 5039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block pair<iterator,iterator> __p = equal_range(__x); 504e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott size_type __n = _STLP_STD::distance(__p.first, __p.second); 5059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block erase(__p.first, __p.second); 5069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __n; 5079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 5089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_type erase_unique(const key_type& __x) { 5109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block iterator __i = find(__x); 5119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__i._M_node != &this->_M_header._M_data) { 5129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block erase(__i); 5139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return 1; 5149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 5159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return 0; 5169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 5179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block void erase(iterator __first, iterator __last) { 5199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__first._M_node == this->_M_header._M_data._M_left && // begin() 5209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __last._M_node == &this->_M_header._M_data) // end() 5219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block clear(); 5229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else 5239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (__first != __last) erase(__first++); 5249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 5259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block void erase(const key_type* __first, const key_type* __last) { 5279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (__first != __last) erase(*__first++); 5289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 5299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block void clear() { 5319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (_M_node_count != 0) { 5329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_erase(_M_root()); 5339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_leftmost() = &this->_M_header._M_data; 5349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_root() = 0; 5359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_rightmost() = &this->_M_header._M_data; 5369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_node_count = 0; 5379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 5389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 5399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic: 5419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // set operations: 5429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_TEMPLATE_FOR_CONT_EXT 5439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block iterator find(const _KT& __k) { return iterator(_M_find(__k)); } 5449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_TEMPLATE_FOR_CONT_EXT 5459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const_iterator find(const _KT& __k) const { return const_iterator(_M_find(__k)); } 5469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockprivate: 5479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_TEMPLATE_FOR_CONT_EXT 5489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Base_ptr _M_find(const _KT& __k) const { 5499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Base_ptr __y = __CONST_CAST(_Base_ptr, &this->_M_header._M_data); // Last node which is not less than __k. 5509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Base_ptr __x = _M_root(); // Current node. 5519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (__x != 0) 5539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (!_M_key_compare(_S_key(__x), __k)) 5549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __y = __x, __x = _S_left(__x); 5559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else 5569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __x = _S_right(__x); 5579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__y != &this->_M_header._M_data) { 5599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (_M_key_compare(__k, _S_key(__y))) { 5609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __y = __CONST_CAST(_Base_ptr, &this->_M_header._M_data); 5619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 5629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 5639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __y; 5649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 5659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_TEMPLATE_FOR_CONT_EXT 5679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Base_ptr _M_lower_bound(const _KT& __k) const { 5689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Base_ptr __y = __CONST_CAST(_Base_ptr, &this->_M_header._M_data); /* Last node which is not less than __k. */ 5699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Base_ptr __x = _M_root(); /* Current node. */ 5709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (__x != 0) 5729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (!_M_key_compare(_S_key(__x), __k)) 5739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __y = __x, __x = _S_left(__x); 5749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else 5759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __x = _S_right(__x); 5769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __y; 5789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 5799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_TEMPLATE_FOR_CONT_EXT 5819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Base_ptr _M_upper_bound(const _KT& __k) const { 5829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Base_ptr __y = __CONST_CAST(_Base_ptr, &this->_M_header._M_data); /* Last node which is greater than __k. */ 5839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Base_ptr __x = _M_root(); /* Current node. */ 5849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (__x != 0) 5869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (_M_key_compare(__k, _S_key(__x))) 5879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __y = __x, __x = _S_left(__x); 5889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else 5899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __x = _S_right(__x); 5909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __y; 5929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 5939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic: 5959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_TEMPLATE_FOR_CONT_EXT 5969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_type count(const _KT& __x) const { 5979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block pair<const_iterator, const_iterator> __p = equal_range(__x); 598e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott return _STLP_STD::distance(__p.first, __p.second); 5999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 6009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_TEMPLATE_FOR_CONT_EXT 6019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block iterator lower_bound(const _KT& __x) { return iterator(_M_lower_bound(__x)); } 6029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_TEMPLATE_FOR_CONT_EXT 6039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const_iterator lower_bound(const _KT& __x) const { return const_iterator(_M_lower_bound(__x)); } 6049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_TEMPLATE_FOR_CONT_EXT 6059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block iterator upper_bound(const _KT& __x) { return iterator(_M_upper_bound(__x)); } 6069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_TEMPLATE_FOR_CONT_EXT 6079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const_iterator upper_bound(const _KT& __x) const { return const_iterator(_M_upper_bound(__x)); } 6089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_TEMPLATE_FOR_CONT_EXT 6099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block pair<iterator,iterator> equal_range(const _KT& __x) 6109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { return pair<iterator, iterator>(lower_bound(__x), upper_bound(__x)); } 6119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_TEMPLATE_FOR_CONT_EXT 6129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block pair<const_iterator, const_iterator> equal_range(const _KT& __x) const 6139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { return pair<const_iterator, const_iterator>(lower_bound(__x), upper_bound(__x)); } 6149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_TEMPLATE_FOR_CONT_EXT 6159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block pair<iterator,iterator> equal_range_unique(const _KT& __x) { 6169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block pair<iterator, iterator> __p; 6179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __p.second = lower_bound(__x); 6189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__p.second._M_node != &this->_M_header._M_data && 6199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block !_M_key_compare(__x, _S_key(__p.second._M_node))) { 6209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __p.first = __p.second++; 6219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 6229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else { 6239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __p.first = __p.second; 6249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 6259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __p; 6269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 6279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_TEMPLATE_FOR_CONT_EXT 6289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block pair<const_iterator, const_iterator> equal_range_unique(const _KT& __x) const { 6299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block pair<const_iterator, const_iterator> __p; 6309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __p.second = lower_bound(__x); 6319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__p.second._M_node != &this->_M_header._M_data && 6329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block !_M_key_compare(__x, _S_key(__p.second._M_node))) { 6339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __p.first = __p.second++; 6349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 6359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else { 6369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __p.first = __p.second; 6379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 6389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __p; 6399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 6409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if defined (_STLP_DEBUG) 6429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic: 6439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // Debugging. 6449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block bool __rb_verify() const; 6459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif //_STLP_DEBUG 6469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block}; 6479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if defined (_STLP_DEBUG) 6499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# undef _Rb_tree 6509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 6519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_STD_NAMESPACE 6539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_END_NAMESPACE 6559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if !defined (_STLP_LINK_TIME_INSTANTIATION) 6579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# include <stl/_tree.c> 6589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 6599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if defined (_STLP_DEBUG) 6619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# include <stl/debug/_tree.h> 6629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 6639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_BEGIN_NAMESPACE 6659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#define _STLP_TEMPLATE_HEADER template <class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, class _Alloc> 6679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#define _STLP_TEMPLATE_CONTAINER _STLP_PRIV _Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc> 6689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#include <stl/_relops_cont.h> 6699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#undef _STLP_TEMPLATE_CONTAINER 6709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#undef _STLP_TEMPLATE_HEADER 6719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 672e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) && !defined (_STLP_NO_MOVE_SEMANTIC) 6739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, class _Alloc> 6749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockstruct __move_traits<_STLP_PRIV _Rb_tree<_Key, _Compare, _Value, _KeyOfValue, _Traits, _Alloc> > 6759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block : _STLP_PRIV __move_traits_help2<_Compare, _Alloc> {}; 6769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 6779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_END_NAMESPACE 6799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif /* _STLP_INTERNAL_TREE_H */ 6819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// Local Variables: 6839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// mode:C++ 6849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// End: 685