#ifndef __TREE_H #define __TREE_H #pragma option push -b -a8 -pc -Vx- -Ve- -w-inl -w-aus -w-sig // -*- C++ -*- #ifndef __STD_TREE__ #define __STD_TREE__ /*************************************************************************** * * tree - Declarations for the Standard Library tree classes * *************************************************************************** * * Copyright (c) 1994 * Hewlett-Packard Company * * Permission to use, copy, modify, distribute and sell this software * and its documentation for any purpose is hereby granted without fee, * provided that the above copyright notice appear in all copies and * that both that copyright notice and this permission notice appear * in supporting documentation. Hewlett-Packard Company makes no * representations about the suitability of this software for any * purpose. It is provided "as is" without express or implied warranty. * * *************************************************************************** * * Copyright (c) 1994-1999 Rogue Wave Software, Inc. All Rights Reserved. * * This computer software is owned by Rogue Wave Software, Inc. and is * protected by U.S. copyright laws and other laws and by international * treaties. This computer software is furnished by Rogue Wave Software, * Inc. pursuant to a written license agreement and may be used, copied, * transmitted, and stored only in accordance with the terms of such * license and with the inclusion of the above copyright notice. This * computer software or any other copies thereof may not be provided or * otherwise made available to any other person. * * U.S. Government Restricted Rights. This computer software is provided * with Restricted Rights. Use, duplication, or disclosure by the * Government is subject to restrictions as set forth in subparagraph (c) * (1) (ii) of The Rights in Technical Data and Computer Software clause * at DFARS 252.227-7013 or subparagraphs (c) (1) and (2) of the * Commercial Computer Software – Restricted Rights at 48 CFR 52.227-19, * as applicable. Manufacturer is Rogue Wave Software, Inc., 5500 * Flatiron Parkway, Boulder, Colorado 80301 USA. * **************************************************************************/ /* ** ** Red-black tree class, designed for use in implementing STL ** associative containers (set, multiset, map, and multimap). The ** insertion and deletion algorithms are based on those in Cormen, ** Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 1990), ** except that: ** ** (1) the header cell is maintained with links not only to the root ** but also to the leftmost node of the tree, to enable constant time ** begin(), and to the rightmost node of the tree, to enable linear time ** performance when used with the generic set algorithms (set_union, ** etc.); ** ** (2) when a node being deleted has two children its successor node is ** relinked into its place, rather than copied, so that the only ** iterators invalidated are those referring to the deleted node. ** */ #include #include #include #ifndef _RWSTD_NO_NAMESPACE namespace __rwstd { #endif #ifndef __rb_tree #define __rb_tree __rb_tree #endif template class __rb_tree { protected: enum __color_type { __rb_red, __rb_black }; struct __rb_tree_node; friend struct __rb_tree_node; #ifdef _RWSTD_ALLOCATOR typedef _TYPENAME _Alloc::template rebind<_Val>::other __value_alloc_type; typedef _TYPENAME _Alloc::template rebind<_Key>::other __key_alloc_type; typedef _TYPENAME _Alloc::template rebind<__rb_tree_node>::other __node_alloc_type; #else typedef _RW_STD::allocator_interface<_Alloc,_Val> __value_alloc_type; typedef _RW_STD::allocator_interface<_Alloc,_Key> __key_alloc_type; typedef _RW_STD::allocator_interface<_Alloc,__rb_tree_node> __node_alloc_type; #endif typedef _TYPENAME __node_alloc_type::pointer __link_type; struct __rb_tree_node { __color_type color_field; __link_type parent_link; __link_type left_link; __link_type right_link; _Val value_field; }; typedef _TYPENAME __key_alloc_type::const_reference const_key_reference; public: typedef _Key key_type; typedef _Val value_type; typedef _Alloc allocator_type; typedef _TYPENAME __value_alloc_type::pointer pointer; typedef _TYPENAME __value_alloc_type::const_pointer const_pointer; #ifndef _RWSTD_NO_COMPLICATED_TYPEDEF typedef _TYPENAME _Alloc::size_type size_type; typedef _TYPENAME _Alloc::size_type difference_type; typedef _TYPENAME __value_alloc_type::reference reference; typedef _TYPENAME __value_alloc_type::const_reference const_reference; #else typedef size_t size_type; typedef ptrdiff_t difference_type; typedef _Val& reference; typedef const _Val& const_reference; #endif //_RWSTD_NO_COMPLICATED_TYPEDEF protected: size_type __buffer_size; struct __rb_tree_node_buffer; friend struct __rb_tree_node_buffer; #ifdef _RWSTD_ALLOCATOR typedef _TYPENAME allocator_type::template rebind<__rb_tree_node_buffer>::other __buffer_alloc_type; #else typedef _RW_STD::allocator_interface<_Alloc,__rb_tree_node_buffer> __buffer_alloc_type; #endif typedef _TYPENAME __buffer_alloc_type::pointer __buffer_pointer; struct __rb_tree_node_buffer { __buffer_pointer next_buffer; size_type size; __link_type buffer; }; __RWSTD::__rw_basis<__buffer_pointer,allocator_type> __buffer_list; __link_type __free_list; __link_type __next_avail; __link_type __last; static bool __isNil(const __link_type& l) { return l == __nil(); } void __add_new_buffer () { __buffer_pointer tmp = __buffer_alloc_type(__buffer_list).allocate(_RWSTD_STATIC_CAST(size_type,1),__buffer_list.data()); #ifndef _RWSTD_NO_EXCEPTIONS try { tmp->buffer = __node_alloc_type(__buffer_list).allocate(__buffer_size,__last); } catch(...) { __buffer_alloc_type(__buffer_list).deallocate(tmp,1); throw; } #else tmp->buffer = __node_alloc_type(__buffer_list).allocate(__buffer_size,__last); #endif // _RWSTD_NO_EXCEPTIONS tmp->next_buffer = __buffer_list; tmp->size = __buffer_size; __buffer_list = tmp; __next_avail = __buffer_list.data()->buffer; __last = __next_avail + __buffer_size; } void __deallocate_buffers (); // // Return a node from the free list or new storage // __link_type __get_link() { __link_type tmp = __free_list; __link_type tmp2 = __free_list ? (__free_list = _RWSTD_STATIC_CAST(__link_type,(__free_list->right_link)), tmp) : (__next_avail == __last ? (__add_new_buffer(), __next_avail++) : __next_avail++); tmp2->parent_link = __nil(); tmp2->left_link = __nil(); tmp2->right_link = __nil(); tmp2->color_field = __rb_red; return tmp2; } // // Return a node from the free list or new storage with // the _Val v constructed on it. Every call to __get_node // must eventually be followed by a call to __put_node. // __link_type __get_node (const _Val& v) { __link_type tmp2 = __get_link(); __value_alloc_type va(__buffer_list); #ifndef _RWSTD_NO_EXCEPTIONS try { va.construct(va.address(__value(tmp2)),v); } catch(...) { __put_node(tmp2,false); throw; } #else va.construct(va.address(__value(tmp2)),v); #endif // _RWSTD_NO_EXCEPTIONS return tmp2; } __link_type __get_node () { return __get_link(); } // // Return a node to the free list and destroy the value in it. // void __put_node (__link_type p, bool do_destroy = true) { p->right_link = __free_list; if (do_destroy) { __value_alloc_type va(__buffer_list); va.destroy(va.address(__value(p))); } __free_list = p; } protected: __link_type __header; __link_type& __root () { return __parent(__header); } __link_type& __root () const { return __parent(__header); } __link_type& __leftmost () { return __left(__header); } __link_type& __leftmost () const { return __left(__header); } __link_type& __rightmost () { return __right(__header); } __link_type& __rightmost () const { return __right(__header); } size_type __node_count; // Keeps track of size of tree. bool __insert_always; // Controls whether an element already in the // tree is inserted again. _Comp __key_compare; static __link_type __nil () { return NULL; } static __link_type& __left (__link_type x) { return _RWSTD_REINTERPRET_CAST(__link_type&,((*x).left_link)); } static __link_type& __right (__link_type x) { return _RWSTD_REINTERPRET_CAST(__link_type&,((*x).right_link)); } static __link_type& __parent (__link_type x) { return _RWSTD_REINTERPRET_CAST(__link_type&,((*x).parent_link)); } static reference __value (__link_type x) { return (*x).value_field; } static const_key_reference __key (__link_type x) { return _KeyOf()(__value(x)); } static __color_type& __color (__link_type x) { return _RWSTD_STATIC_CAST(__color_type&,(*x).color_field); } static __link_type __minimum (__link_type x) { while (!__isNil(__left(x))) x = __left(x); return x; } static __link_type __maximum (__link_type x) { while (!__isNil(__right(x))) x = __right(x); return x; } typedef _RW_STD::iterator<_RW_STD::bidirectional_iterator_tag, value_type, difference_type, pointer,reference> __it; typedef _RW_STD::iterator<_RW_STD::bidirectional_iterator_tag, value_type, difference_type, const_pointer, const_reference> __cit; public: class iterator; friend class iterator; class const_iterator; friend class const_iterator; class iterator : public __it { friend class __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>; friend class const_iterator; protected: __link_type node; iterator (__link_type x) : node(x) {} public: iterator () {} bool operator== (const iterator& y) const { return node == y.node; } bool operator!= (const iterator& y) const { return node != y.node; } reference operator* () const { return __value(node); } #ifndef _RWSTD_NO_NONCLASS_ARROW_RETURN pointer operator-> () const { return &(node->value_field); } #endif iterator& operator++ () { if (!__isNil(__right(node))) { node = __right(node); while (!__isNil(__left(node))) node = __left(node); } else { __link_type y = __parent(node); while (node == __right(y)) { node = y; y = __parent(y); } if (__right(node) != y) // Necessary because of rightmost. node = y; } return *this; } iterator operator++ (int) { iterator tmp = *this; ++*this; return tmp; } iterator& operator-- () { if (__color(node) == __rb_red && __parent(__parent(node)) == node) // // Check for header. // node = __right(node); // Return rightmost. else if (!__isNil(__left(node))) { __link_type y = __left(node); while (!__isNil(__right(y))) y = __right(y); node = y; } else { __link_type y = __parent(node); while (node == __left(y)) { node = y; y = __parent(y); } node = y; } return *this; } iterator operator-- (int) { iterator tmp = *this; --*this; return tmp; } }; // End of definition of iterator. class const_iterator : public __cit { friend class __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>; friend class iterator; protected: __link_type node; const_iterator (__link_type x) : node(x) {} public: const_iterator () {} #if !defined(_MSC_VER) || defined(__BORLANDC__) const_iterator (const _TYPENAME __rb_tree<_Key,_Val,_KeyOf,_Comp,_Alloc>::iterator& x) : node(x.node) {} #else const_iterator (const iterator& x) : node(x.node) {} #endif bool operator== (const const_iterator& y) const { return node == y.node; } bool operator!= (const const_iterator& y) const { return node != y.node; } const_reference operator* () const { return __value(node); } #ifndef _RWSTD_NO_NONCLASS_ARROW_RETURN const_pointer operator-> () const { return &(node->value_field); } #endif const_iterator& operator++ () { if (!__isNil(__right(node))) { node = __right(node); while (!__isNil(__left(node))) node = __left(node); } else { __link_type y = __parent(node); while (node == __right(y)) { node = y; y = __parent(y); } if (__right(node) != y) // Necessary because of rightmost. node = y; } return *this; } const_iterator operator++ (int) { const_iterator tmp = *this; ++*this; return tmp; } const_iterator& operator-- () { if (__color(node) == __rb_red && __parent(__parent(node)) == node) // // Check for header. // node = __right(node); // return rightmost else if (!__isNil(__left(node))) { __link_type y = __left(node); while (!__isNil(__right(y))) y = __right(y); node = y; } else { __link_type y = __parent(node); while (node == __left(y)) { node = y; y = __parent(y); } node = y; } return *this; } const_iterator operator-- (int) { const_iterator tmp = *this; --*this; return tmp; } }; // End of definition of const_iterator. #ifndef _RWSTD_NO_CLASS_PARTIAL_SPEC typedef _RW_STD::reverse_iterator const_reverse_iterator; typedef _RW_STD::reverse_iterator reverse_iterator; #else typedef _RW_STD::__reverse_bi_iterator const_reverse_iterator; typedef _RW_STD::__reverse_bi_iterator reverse_iterator; #endif private: iterator __insert (__link_type x, __link_type y, const value_type& v); __link_type __copy (__link_type x, __link_type p); void __erase (__link_type x); inline void __erase_leaf (__link_type x); void init () { __buffer_size = 1; __buffer_list = 0; __free_list = __next_avail = __last = 0; __header = __get_node(); __root() = __nil(); __leftmost() = __header; __rightmost() = __header; __buffer_size = 1 >__RWSTD::__rw_allocation_size((value_type*)0,(size_type)0,(size_type)0) ? 1 : __RWSTD::__rw_allocation_size((value_type*)0,(size_type)0,(size_type)0); } public: __rb_tree (const _Comp& _RWSTD_COMP _RWSTD_DEFAULT_ARG(_Comp()), bool always _RWSTD_DEFAULT_ARG(true), const _Alloc& alloc _RWSTD_DEFAULT_ARG(_Alloc())) : __node_count(0), __header(0), __key_compare(_RWSTD_COMP), __insert_always(always), __buffer_list(0,alloc) { init(); } #ifdef _RWSTD_NO_DEFAULT_TEMPLATE_ARGS __rb_tree (void) : __node_count(0), __header(0), __key_compare(_Comp()), __insert_always(true), __buffer_list(0,_Alloc()) { init(); } __rb_tree (const _Comp& _RWSTD_COMP) : __node_count(0), __header(0), __key_compare(_RWSTD_COMP), __insert_always(true), __buffer_list(0,_Alloc()) { init(); } __rb_tree (const _Comp& _RWSTD_COMP , bool always = true) : __node_count(0), __header(0), __key_compare(_RWSTD_COMP), __insert_always(always), __buffer_list(0,_Alloc()) { init(); } #endif #ifndef _RWSTD_NO_MEMBER_TEMPLATES template __rb_tree (InputIterator first, InputIterator last, const _Comp& comp = _Comp(), bool always = true, const _Alloc& alloc = _Alloc()) : __node_count(0), __header(0), __key_compare(comp), __insert_always(always), __buffer_list(0,alloc) { init(); #ifndef _RWSTD_NO_EXCEPTIONS try { insert(first, last); } catch(...) { __deallocate_buffers(); throw; } #else insert(first, last); #endif // _RWSTD_NO_EXCEPTIONS } #else __rb_tree (const value_type* first, const value_type* last, const _Comp& _RWSTD_COMP _RWSTD_DEFAULT_ARG(_Comp()), bool always _RWSTD_DEFAULT_ARG(true), const _Alloc& alloc _RWSTD_DEFAULT_ARG(_Alloc())) : __node_count(0), __header(0), __key_compare(_RWSTD_COMP), __insert_always(always), __buffer_list(0,alloc) { init(); #ifndef _RWSTD_NO_EXCEPTIONS try { insert(first, last); } catch(...) { __deallocate_buffers(); throw; } #else insert(first, last); #endif // _RWSTD_NO_EXCEPTIONS } __rb_tree (const_iterator first, const_iterator last, const _Comp& _RWSTD_COMP _RWSTD_DEFAULT_ARG(_Comp()), bool always _RWSTD_DEFAULT_ARG(true), const _Alloc& alloc _RWSTD_DEFAULT_ARG(_Alloc())) : __node_count(0), __header(0), __key_compare(_RWSTD_COMP), __insert_always(always), __buffer_list(0,alloc) { init(); #ifndef _RWSTD_NO_EXCEPTIONS try { insert(first, last); } catch(...) { __deallocate_buffers(); throw; } #else insert(first, last); #endif // _RWSTD_NO_EXCEPTIONS } #ifdef _RWSTD_NO_DEFAULT_TEMPLATE_ARGS __rb_tree (const value_type* first, const value_type* last, const _Comp& _RWSTD_COMP _RWSTD_DEFAULT_ARG(_Comp())) : __node_count(0), __header(0), __key_compare(_RWSTD_COMP), __insert_always(true), __buffer_list(0,_Alloc()) { init(); #ifndef _RWSTD_NO_EXCEPTIONS try { insert(first, last); } catch(...) { __deallocate_buffers(); throw; } #else insert(first, last); #endif // _RWSTD_NO_EXCEPTIONS } __rb_tree (const value_type* first, const value_type* last, const _Comp& _RWSTD_COMP _RWSTD_DEFAULT_ARG(_Comp()), bool always _RWSTD_DEFAULT_ARG(true)) : __node_count(0), __header(0), __key_compare(_RWSTD_COMP), __insert_always(always), the__Alloc(_Alloc()) { init(); #ifndef _RWSTD_NO_EXCEPTIONS try { insert(first, last); } catch(...) { __deallocate_buffers(); throw; } #else insert(first, last); #endif // _RWSTD_NO_EXCEPTIONS } __rb_tree (const_iterator first, const_iterator last, const _Comp& _RWSTD_COMP _RWSTD_DEFAULT_ARG(_Comp())) : __node_count(0), __header(0), __key_compare(_RWSTD_COMP), __insert_always(true), __buffer_list(0,_Alloc()) { init(); #ifndef _RWSTD_NO_EXCEPTIONS try { insert(first, last); } catch(...) { __deallocate_buffers(); throw; } #else insert(first, last); #endif // _RWSTD_NO_EXCEPTIONS } __rb_tree (const_iterator first, const_iterator last, const _Comp& _RWSTD_COMP _RWSTD_DEFAULT_ARG(_Comp()), bool always _RWSTD_DEFAULT_ARG(true)) : __node_count(0), __header(0), __key_compare(_RWSTD_COMP), __insert_always(always), __buffer_list(0,_Alloc()) { init(); #ifndef _RWSTD_NO_EXCEPTIONS try { insert(first, last); } catch(...) { __deallocate_buffers(); throw; } #else insert(first, last); #endif // _RWSTD_NO_EXCEPTIONS } #endif #ifdef _RWSTD_NO_DEFAULT_TEMPLATE_ARGS __rb_tree (const value_type* first, const value_type* last) : __node_count(0), __header(0), __key_compare(_Comp()), __insert_always(true), __buffer_list(0,_Alloc()) { init(); #ifndef _RWSTD_NO_EXCEPTIONS try { insert(first, last); } catch(...) { __deallocate_buffers(); throw; } #else insert(first, last); #endif // _RWSTD_NO_EXCEPTIONS } __rb_tree (const_iterator first, const_iterator last) : __node_count(0), __header(0), __key_compare(_Comp()), __insert_always(true), __buffer_list(0,_Alloc()) { init(); #ifndef _RWSTD_NO_EXCEPTIONS try { insert(first, last); } catch(...) { __deallocate_buffers(); throw; } #else insert(first, last); #endif // _RWSTD_NO_EXCEPTIONS } #endif #endif __rb_tree (const __rb_tree<_Key,_Val,_KeyOf,_Comp,_Alloc>& x, bool always = true) : __node_count(x.__node_count), __header(0), __key_compare(x.__key_compare), __insert_always(always), __buffer_list(0,x.get_allocator()) { __buffer_size = 1; __free_list = __next_avail = __last = 0; __header = __get_node(); __buffer_size = 1 > __RWSTD::__rw_allocation_size((value_type*)0,(size_type)0,(size_type)0) ? 1 : __RWSTD::__rw_allocation_size((value_type*)0,(size_type)0,(size_type)0); __color(__header) = __rb_red; __root() = __copy(x.__root(), __header); if (__isNil(__root())) { __leftmost() = __header; __rightmost() = __header; } else { __leftmost() = __minimum(__root()); __rightmost() = __maximum(__root()); } } ~__rb_tree () { if (__header) { erase(begin(), end()); __put_node(__header,false); __deallocate_buffers(); } } __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>& operator= (const __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>& x); _Comp key_comp () const { return __key_compare; } allocator_type get_allocator() const { return (allocator_type)__buffer_list; } iterator begin () const { return __leftmost(); } iterator end () const { return __header; } reverse_iterator rbegin () { reverse_iterator tmp(end()); return tmp; } reverse_iterator rend () { reverse_iterator tmp(begin()); return tmp; } const_reverse_iterator rbegin () const { const_reverse_iterator tmp(end()); return tmp; } const_reverse_iterator rend () const { const_reverse_iterator tmp(begin()); return tmp; } bool empty () const { return __node_count == 0; } size_type size () const { return __node_count; } size_type max_size () const { return __node_alloc_type(__buffer_list).max_size(); } void swap (__rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>& t) { if((allocator_type)__buffer_list==(allocator_type)t.__buffer_list) { #ifndef _RWSTD_NO_NAMESPACE std::swap(__buffer_list, t.__buffer_list); std::swap(__free_list, t.__free_list); std::swap(__next_avail, t.__next_avail); std::swap(__last, t.__last); std::swap(__header, t.__header); std::swap(__node_count, t.__node_count); std::swap(__insert_always, t.__insert_always); std::swap(__key_compare, t.__key_compare); #else ::swap(__buffer_list, t.__buffer_list); ::swap(__free_list, t.__free_list); ::swap(__next_avail, t.__next_avail); ::swap(__last, t.__last); ::swap(__header, t.__header); ::swap(__node_count, t.__node_count); ::swap(__insert_always, t.__insert_always); ::swap(__key_compare, t.__key_compare); #endif } else { __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc> _x = *this; *this = t; t = _x; } } typedef _RW_STD::pair pair_iterator_bool; // // typedef done to get around compiler bug. // #ifndef _RWSTD_NO_RET_TEMPLATE _RW_STD::pair insert (const value_type& x); #else pair_iterator_bool insert (const value_type& x); #endif iterator insert (iterator position, const value_type& x); #ifndef _RWSTD_NO_MEMBER_TEMPLATES template void insert (Iterator first, Iterator last); #else void insert (const_iterator first, const_iterator last); void insert (const value_type* first, const value_type* last); #endif iterator erase (iterator position); size_type erase (const key_type& x); iterator erase (iterator first, iterator last); void erase (const key_type* first, const key_type* last); iterator find (const key_type& x) const; size_type count (const key_type& x) const; iterator lower_bound (const key_type& x) const; iterator upper_bound (const key_type& x) const; typedef _RW_STD::pair pair_iterator_iterator; // // typedef done to get around compiler bug. // #ifndef _RWSTD_NO_RET_TEMPLATE _RW_STD::pair equal_range (const key_type& x) const; #else pair_iterator_iterator equal_range (const key_type& x) const; #endif inline void __rotate_left (__link_type x); inline void __rotate_right (__link_type x); // Query and set the allocation size size_type allocation_size() { return __buffer_size; } size_type allocation_size(size_type new_size) { size_type tmp = __buffer_size; __buffer_size = 1 > new_size ? 1 : new_size; //max((size_type)1,new_size); return tmp; } }; // // Inline functions // template inline bool operator== (const __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>& x, const __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>& y) { return x.size() == y.size() && _RW_STD::equal(x.begin(), x.end(), y.begin()); } template inline bool operator< (const __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>& x, const __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>& y) { return _RW_STD::lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); } template inline void __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::__erase_leaf (__link_type x) { // Remove a leaf node from the tree __link_type y = __parent(x); if (y == __header) { __leftmost() = __rightmost() = y; __root() = __nil(); } else if (__left(y) == x) { __left(y) = __nil(); if (__leftmost() == x) __leftmost() = y; } else { __right(y) = __nil(); if (__rightmost() == x) __rightmost() = y; } } template inline void __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::__rotate_left (__link_type x) { __link_type y = __right(x); __right(x) = __left(y); if (!__isNil(__left(y))) __parent(__left(y)) = x; __parent(y) = __parent(x); if (x == __root()) __root() = y; else if (x == __left(__parent(x))) __left(__parent(x)) = y; else __right(__parent(x)) = y; __left(y) = x; __parent(x) = y; } template inline void __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::__rotate_right (__link_type x) { __link_type y = __left(x); __left(x) = __right(y); if (!__isNil(__right(y))) __parent(__right(y)) = x; __parent(y) = __parent(x); if (x == __root()) __root() = y; else if (x == __right(__parent(x))) __right(__parent(x)) = y; else __left(__parent(x)) = y; __right(y) = x; __parent(x) = y; } #ifndef _RWSTD_NO_NAMESPACE } #endif #ifdef _RWSTD_NO_TEMPLATE_REPOSITORY #include #endif #endif /* __STD_TREE__ */ #pragma option pop #endif /* __TREE_H */