stl_tree.h

Go to the documentation of this file.
00001 // RB tree implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 2, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // You should have received a copy of the GNU General Public License along
00017 // with this library; see the file COPYING.  If not, write to the Free
00018 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
00019 // USA.
00020 
00021 // As a special exception, you may use this file as part of a free software
00022 // library without restriction.  Specifically, if other files instantiate
00023 // templates or use macros or inline functions from this file, or you compile
00024 // this file and link it with other files to produce an executable, this
00025 // file does not by itself cause the resulting executable to be covered by
00026 // the GNU General Public License.  This exception does not however
00027 // invalidate any other reasons why the executable file might be covered by
00028 // the GNU General Public License.
00029 
00030 /*
00031  *
00032  * Copyright (c) 1996,1997
00033  * Silicon Graphics Computer Systems, Inc.
00034  *
00035  * Permission to use, copy, modify, distribute and sell this software
00036  * and its documentation for any purpose is hereby granted without fee,
00037  * provided that the above copyright notice appear in all copies and
00038  * that both that copyright notice and this permission notice appear
00039  * in supporting documentation.  Silicon Graphics makes no
00040  * representations about the suitability of this software for any
00041  * purpose.  It is provided "as is" without express or implied warranty.
00042  *
00043  *
00044  * Copyright (c) 1994
00045  * Hewlett-Packard Company
00046  *
00047  * Permission to use, copy, modify, distribute and sell this software
00048  * and its documentation for any purpose is hereby granted without fee,
00049  * provided that the above copyright notice appear in all copies and
00050  * that both that copyright notice and this permission notice appear
00051  * in supporting documentation.  Hewlett-Packard Company makes no
00052  * representations about the suitability of this software for any
00053  * purpose.  It is provided "as is" without express or implied warranty.
00054  *
00055  *
00056  */
00057 
00058 /** @file stl_tree.h
00059  *  This is an internal header file, included by other library headers.
00060  *  You should not attempt to use it directly.
00061  */
00062 
00063 #ifndef _TREE_H
00064 #define _TREE_H 1
00065 
00066 #include <bits/stl_algobase.h>
00067 #include <bits/allocator.h>
00068 #include <bits/stl_construct.h>
00069 #include <bits/stl_function.h>
00070 #include <bits/cpp_type_traits.h>
00071 
00072 namespace std
00073 {
00074   // Red-black tree class, designed for use in implementing STL
00075   // associative containers (set, multiset, map, and multimap). The
00076   // insertion and deletion algorithms are based on those in Cormen,
00077   // Leiserson, and Rivest, Introduction to Algorithms (MIT Press,
00078   // 1990), except that
00079   //
00080   // (1) the header cell is maintained with links not only to the root
00081   // but also to the leftmost node of the tree, to enable constant
00082   // time begin(), and to the rightmost node of the tree, to enable
00083   // linear time performance when used with the generic set algorithms
00084   // (set_union, etc.)
00085   // 
00086   // (2) when a node being deleted has two children its successor node
00087   // is relinked into its place, rather than copied, so that the only
00088   // iterators invalidated are those referring to the deleted node.
00089 
00090   enum _Rb_tree_color { _S_red = false, _S_black = true };
00091 
00092   struct _Rb_tree_node_base
00093   {
00094     typedef _Rb_tree_node_base* _Base_ptr;
00095     typedef const _Rb_tree_node_base* _Const_Base_ptr;
00096 
00097     _Rb_tree_color  _M_color;
00098     _Base_ptr       _M_parent;
00099     _Base_ptr       _M_left;
00100     _Base_ptr       _M_right;
00101 
00102     static _Base_ptr
00103     _S_minimum(_Base_ptr __x)
00104     {
00105       while (__x->_M_left != 0) __x = __x->_M_left;
00106       return __x;
00107     }
00108 
00109     static _Const_Base_ptr
00110     _S_minimum(_Const_Base_ptr __x)
00111     {
00112       while (__x->_M_left != 0) __x = __x->_M_left;
00113       return __x;
00114     }
00115 
00116     static _Base_ptr
00117     _S_maximum(_Base_ptr __x)
00118     {
00119       while (__x->_M_right != 0) __x = __x->_M_right;
00120       return __x;
00121     }
00122 
00123     static _Const_Base_ptr
00124     _S_maximum(_Const_Base_ptr __x)
00125     {
00126       while (__x->_M_right != 0) __x = __x->_M_right;
00127       return __x;
00128     }
00129   };
00130 
00131   template<typename _Val>
00132     struct _Rb_tree_node : public _Rb_tree_node_base
00133     {
00134       typedef _Rb_tree_node<_Val>* _Link_type;
00135       _Val _M_value_field;
00136     };
00137 
00138   _Rb_tree_node_base*
00139   _Rb_tree_increment(_Rb_tree_node_base* __x);
00140 
00141   const _Rb_tree_node_base*
00142   _Rb_tree_increment(const _Rb_tree_node_base* __x);
00143 
00144   _Rb_tree_node_base*
00145   _Rb_tree_decrement(_Rb_tree_node_base* __x);
00146 
00147   const _Rb_tree_node_base*
00148   _Rb_tree_decrement(const _Rb_tree_node_base* __x);
00149 
00150   template<typename _Tp>
00151     struct _Rb_tree_iterator
00152     {
00153       typedef _Tp  value_type;
00154       typedef _Tp& reference;
00155       typedef _Tp* pointer;
00156 
00157       typedef bidirectional_iterator_tag iterator_category;
00158       typedef ptrdiff_t                  difference_type;
00159 
00160       typedef _Rb_tree_iterator<_Tp>        _Self;
00161       typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
00162       typedef _Rb_tree_node<_Tp>*           _Link_type;
00163 
00164       _Rb_tree_iterator()
00165       : _M_node() { }
00166 
00167       _Rb_tree_iterator(_Link_type __x)
00168       : _M_node(__x) { }
00169 
00170       reference
00171       operator*() const
00172       { return static_cast<_Link_type>(_M_node)->_M_value_field; }
00173 
00174       pointer
00175       operator->() const
00176       { return &static_cast<_Link_type>(_M_node)->_M_value_field; }
00177 
00178       _Self&
00179       operator++()
00180       {
00181     _M_node = _Rb_tree_increment(_M_node);
00182     return *this;
00183       }
00184 
00185       _Self
00186       operator++(int)
00187       {
00188     _Self __tmp = *this;
00189     _M_node = _Rb_tree_increment(_M_node);
00190     return __tmp;
00191       }
00192 
00193       _Self&
00194       operator--()
00195       {
00196     _M_node = _Rb_tree_decrement(_M_node);
00197     return *this;
00198       }
00199 
00200       _Self
00201       operator--(int)
00202       {
00203     _Self __tmp = *this;
00204     _M_node = _Rb_tree_decrement(_M_node);
00205     return __tmp;
00206       }
00207 
00208       bool
00209       operator==(const _Self& __x) const
00210       { return _M_node == __x._M_node; }
00211 
00212       bool
00213       operator!=(const _Self& __x) const
00214       { return _M_node != __x._M_node; }
00215 
00216       _Base_ptr _M_node;
00217   };
00218 
00219   template<typename _Tp>
00220     struct _Rb_tree_const_iterator
00221     {
00222       typedef _Tp        value_type;
00223       typedef const _Tp& reference;
00224       typedef const _Tp* pointer;
00225 
00226       typedef _Rb_tree_iterator<_Tp> iterator;
00227 
00228       typedef bidirectional_iterator_tag iterator_category;
00229       typedef ptrdiff_t                  difference_type;
00230 
00231       typedef _Rb_tree_const_iterator<_Tp>        _Self;
00232       typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr;
00233       typedef const _Rb_tree_node<_Tp>*           _Link_type;
00234 
00235       _Rb_tree_const_iterator()
00236       : _M_node() { }
00237 
00238       _Rb_tree_const_iterator(_Link_type __x)
00239       : _M_node(__x) { }
00240 
00241       _Rb_tree_const_iterator(const iterator& __it)
00242       : _M_node(__it._M_node) { }
00243 
00244       reference
00245       operator*() const
00246       { return static_cast<_Link_type>(_M_node)->_M_value_field; }
00247 
00248       pointer
00249       operator->() const
00250       { return &static_cast<_Link_type>(_M_node)->_M_value_field; }
00251 
00252       _Self&
00253       operator++()
00254       {
00255     _M_node = _Rb_tree_increment(_M_node);
00256     return *this;
00257       }
00258 
00259       _Self
00260       operator++(int)
00261       {
00262     _Self __tmp = *this;
00263     _M_node = _Rb_tree_increment(_M_node);
00264     return __tmp;
00265       }
00266 
00267       _Self&
00268       operator--()
00269       {
00270     _M_node = _Rb_tree_decrement(_M_node);
00271     return *this;
00272       }
00273 
00274       _Self
00275       operator--(int)
00276       {
00277     _Self __tmp = *this;
00278     _M_node = _Rb_tree_decrement(_M_node);
00279     return __tmp;
00280       }
00281 
00282       bool
00283       operator==(const _Self& __x) const
00284       { return _M_node == __x._M_node; }
00285 
00286       bool
00287       operator!=(const _Self& __x) const
00288       { return _M_node != __x._M_node; }
00289 
00290       _Base_ptr _M_node;
00291     };
00292 
00293   template<typename _Val>
00294     inline bool
00295     operator==(const _Rb_tree_iterator<_Val>& __x,
00296                const _Rb_tree_const_iterator<_Val>& __y)
00297     { return __x._M_node == __y._M_node; }
00298 
00299   template<typename _Val>
00300     inline bool
00301     operator!=(const _Rb_tree_iterator<_Val>& __x,
00302                const _Rb_tree_const_iterator<_Val>& __y)
00303     { return __x._M_node != __y._M_node; }
00304 
00305   void
00306   _Rb_tree_rotate_left(_Rb_tree_node_base* const __x,
00307                        _Rb_tree_node_base*& __root);
00308 
00309   void
00310   _Rb_tree_rotate_right(_Rb_tree_node_base* const __x,
00311                         _Rb_tree_node_base*& __root);
00312 
00313   void
00314   _Rb_tree_insert_and_rebalance(const bool __insert_left,
00315                                 _Rb_tree_node_base* __x,
00316                                 _Rb_tree_node_base* __p,
00317                                 _Rb_tree_node_base& __header);
00318 
00319   _Rb_tree_node_base*
00320   _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
00321                    _Rb_tree_node_base& __header);
00322 
00323 
00324   template<typename _Key, typename _Val, typename _KeyOfValue,
00325            typename _Compare, typename _Alloc = allocator<_Val> >
00326     class _Rb_tree
00327     {
00328       typedef typename _Alloc::template rebind<_Rb_tree_node<_Val> >::other
00329               _Node_allocator;
00330 
00331     protected:
00332       typedef _Rb_tree_node_base* _Base_ptr;
00333       typedef const _Rb_tree_node_base* _Const_Base_ptr;
00334       typedef _Rb_tree_node<_Val> _Rb_tree_node;
00335 
00336     public:
00337       typedef _Key key_type;
00338       typedef _Val value_type;
00339       typedef value_type* pointer;
00340       typedef const value_type* const_pointer;
00341       typedef value_type& reference;
00342       typedef const value_type& const_reference;
00343       typedef _Rb_tree_node* _Link_type;
00344       typedef const _Rb_tree_node* _Const_Link_type;
00345       typedef size_t size_type;
00346       typedef ptrdiff_t difference_type;
00347       typedef _Alloc allocator_type;
00348 
00349       allocator_type 
00350       get_allocator() const
00351       { return *static_cast<const _Node_allocator*>(&this->_M_impl); }
00352 
00353     protected:
00354       _Rb_tree_node*
00355       _M_get_node()
00356       { return _M_impl._Node_allocator::allocate(1); }
00357 
00358       void
00359       _M_put_node(_Rb_tree_node* __p)
00360       { _M_impl._Node_allocator::deallocate(__p, 1); }
00361 
00362       _Link_type
00363       _M_create_node(const value_type& __x)
00364       {
00365     _Link_type __tmp = _M_get_node();
00366     try
00367       { get_allocator().construct(&__tmp->_M_value_field, __x); }
00368     catch(...)
00369       {
00370         _M_put_node(__tmp);
00371         __throw_exception_again;
00372       }
00373     return __tmp;
00374       }
00375 
00376       _Link_type
00377       _M_clone_node(_Const_Link_type __x)
00378       {
00379     _Link_type __tmp = _M_create_node(__x->_M_value_field);
00380     __tmp->_M_color = __x->_M_color;
00381     __tmp->_M_left = 0;
00382     __tmp->_M_right = 0;
00383     return __tmp;
00384       }
00385 
00386       void
00387       destroy_node(_Link_type __p)
00388       {
00389     get_allocator().destroy(&__p->_M_value_field);
00390     _M_put_node(__p);
00391       }
00392 
00393     protected:
00394       template<typename _Key_compare, 
00395            bool _Is_pod_comparator = std::__is_pod<_Key_compare>::__value>
00396         struct _Rb_tree_impl : public _Node_allocator
00397         {
00398       _Key_compare      _M_key_compare;
00399       _Rb_tree_node_base    _M_header;
00400       size_type         _M_node_count; // Keeps track of size of tree.
00401 
00402       _Rb_tree_impl(const _Node_allocator& __a = _Node_allocator(),
00403             const _Key_compare& __comp = _Key_compare())
00404       : _Node_allocator(__a), _M_key_compare(__comp), _M_node_count(0)
00405       {
00406         this->_M_header._M_color = _S_red;
00407         this->_M_header._M_parent = 0;
00408         this->_M_header._M_left = &this->_M_header;
00409         this->_M_header._M_right = &this->_M_header;
00410       }
00411     };
00412 
00413       // Specialization for _Comparison types that are not capable of
00414       // being base classes / super classes.
00415       template<typename _Key_compare>
00416         struct _Rb_tree_impl<_Key_compare, true> : public _Node_allocator 
00417     {
00418       _Key_compare      _M_key_compare;
00419       _Rb_tree_node_base    _M_header;
00420       size_type         _M_node_count; // Keeps track of size of tree.
00421 
00422       _Rb_tree_impl(const _Node_allocator& __a = _Node_allocator(),
00423             const _Key_compare& __comp = _Key_compare())
00424       : _Node_allocator(__a), _M_key_compare(__comp), _M_node_count(0)
00425       { 
00426         this->_M_header._M_color = _S_red;
00427         this->_M_header._M_parent = 0;
00428         this->_M_header._M_left = &this->_M_header;
00429         this->_M_header._M_right = &this->_M_header;
00430       }
00431     };
00432 
00433       _Rb_tree_impl<_Compare> _M_impl;
00434 
00435     protected:
00436       _Base_ptr&
00437       _M_root()
00438       { return this->_M_impl._M_header._M_parent; }
00439 
00440       _Const_Base_ptr
00441       _M_root() const
00442       { return this->_M_impl._M_header._M_parent; }
00443 
00444       _Base_ptr&
00445       _M_leftmost()
00446       { return this->_M_impl._M_header._M_left; }
00447 
00448       _Const_Base_ptr
00449       _M_leftmost() const
00450       { return this->_M_impl._M_header._M_left; }
00451 
00452       _Base_ptr&
00453       _M_rightmost()
00454       { return this->_M_impl._M_header._M_right; }
00455 
00456       _Const_Base_ptr
00457       _M_rightmost() const
00458       { return this->_M_impl._M_header._M_right; }
00459 
00460       _Link_type
00461       _M_begin()
00462       { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
00463 
00464       _Const_Link_type
00465       _M_begin() const
00466       {
00467     return static_cast<_Const_Link_type>
00468       (this->_M_impl._M_header._M_parent);
00469       }
00470 
00471       _Link_type
00472       _M_end()
00473       { return static_cast<_Link_type>(&this->_M_impl._M_header); }
00474 
00475       _Const_Link_type
00476       _M_end() const
00477       { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); }
00478 
00479       static const_reference
00480       _S_value(_Const_Link_type __x)
00481       { return __x->_M_value_field; }
00482 
00483       static const _Key&
00484       _S_key(_Const_Link_type __x)
00485       { return _KeyOfValue()(_S_value(__x)); }
00486 
00487       static _Link_type
00488       _S_left(_Base_ptr __x)
00489       { return static_cast<_Link_type>(__x->_M_left); }
00490 
00491       static _Const_Link_type
00492       _S_left(_Const_Base_ptr __x)
00493       { return static_cast<_Const_Link_type>(__x->_M_left); }
00494 
00495       static _Link_type
00496       _S_right(_Base_ptr __x)
00497       { return static_cast<_Link_type>(__x->_M_right); }
00498 
00499       static _Const_Link_type
00500       _S_right(_Const_Base_ptr __x)
00501       { return static_cast<_Const_Link_type>(__x->_M_right); }
00502 
00503       static const_reference
00504       _S_value(_Const_Base_ptr __x)
00505       { return static_cast<_Const_Link_type>(__x)->_M_value_field; }
00506 
00507       static const _Key&
00508       _S_key(_Const_Base_ptr __x)
00509       { return _KeyOfValue()(_S_value(__x)); }
00510 
00511       static _Base_ptr
00512       _S_minimum(_Base_ptr __x)
00513       { return _Rb_tree_node_base::_S_minimum(__x); }
00514 
00515       static _Const_Base_ptr
00516       _S_minimum(_Const_Base_ptr __x)
00517       { return _Rb_tree_node_base::_S_minimum(__x); }
00518 
00519       static _Base_ptr
00520       _S_maximum(_Base_ptr __x)
00521       { return _Rb_tree_node_base::_S_maximum(__x); }
00522 
00523       static _Const_Base_ptr
00524       _S_maximum(_Const_Base_ptr __x)
00525       { return _Rb_tree_node_base::_S_maximum(__x); }
00526 
00527     public:
00528       typedef _Rb_tree_iterator<value_type>       iterator;
00529       typedef _Rb_tree_const_iterator<value_type> const_iterator;
00530 
00531       typedef std::reverse_iterator<iterator>       reverse_iterator;
00532       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
00533 
00534     private:
00535       iterator
00536       _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v);
00537 
00538       _Link_type
00539       _M_copy(_Const_Link_type __x, _Link_type __p);
00540 
00541       void
00542       _M_erase(_Link_type __x);
00543 
00544     public:
00545       // allocation/deallocation
00546       _Rb_tree()
00547       { }
00548 
00549       _Rb_tree(const _Compare& __comp)
00550       : _M_impl(allocator_type(), __comp)
00551       { }
00552 
00553       _Rb_tree(const _Compare& __comp, const allocator_type& __a)
00554       : _M_impl(__a, __comp)
00555       { }
00556 
00557       _Rb_tree(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x)
00558       : _M_impl(__x.get_allocator(), __x._M_impl._M_key_compare)
00559       {
00560     if (__x._M_root() != 0)
00561       {
00562         _M_root() = _M_copy(__x._M_begin(), _M_end());
00563         _M_leftmost() = _S_minimum(_M_root());
00564         _M_rightmost() = _S_maximum(_M_root());
00565         _M_impl._M_node_count = __x._M_impl._M_node_count;
00566       }
00567       }
00568 
00569       ~_Rb_tree()
00570       { _M_erase(_M_begin()); }
00571 
00572       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
00573       operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x);
00574 
00575       // Accessors.
00576       _Compare
00577       key_comp() const
00578       { return _M_impl._M_key_compare; }
00579 
00580       iterator
00581       begin()
00582       { return static_cast<_Link_type>(this->_M_impl._M_header._M_left); }
00583 
00584       const_iterator
00585       begin() const
00586       {
00587     return static_cast<_Const_Link_type>
00588       (this->_M_impl._M_header._M_left);
00589       }
00590 
00591       iterator
00592       end()
00593       { return static_cast<_Link_type>(&this->_M_impl._M_header); }
00594 
00595       const_iterator
00596       end() const
00597       { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); }
00598 
00599       reverse_iterator
00600       rbegin()
00601       { return reverse_iterator(end()); }
00602 
00603       const_reverse_iterator
00604       rbegin() const
00605       { return const_reverse_iterator(end()); }
00606 
00607       reverse_iterator
00608       rend()
00609       { return reverse_iterator(begin()); }
00610 
00611       const_reverse_iterator
00612       rend() const
00613       { return const_reverse_iterator(begin()); }
00614 
00615       bool
00616       empty() const
00617       { return _M_impl._M_node_count == 0; }
00618 
00619       size_type
00620       size() const
00621       { return _M_impl._M_node_count; }
00622 
00623       size_type
00624       max_size() const
00625       { return size_type(-1); }
00626 
00627       void
00628       swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t);
00629 
00630       // Insert/erase.
00631       pair<iterator,bool>
00632       insert_unique(const value_type& __x);
00633 
00634       iterator
00635       insert_equal(const value_type& __x);
00636 
00637       iterator
00638       insert_unique(iterator __position, const value_type& __x);
00639 
00640       iterator
00641       insert_equal(iterator __position, const value_type& __x);
00642 
00643       template<typename _InputIterator>
00644       void
00645       insert_unique(_InputIterator __first, _InputIterator __last);
00646 
00647       template<typename _InputIterator>
00648       void
00649       insert_equal(_InputIterator __first, _InputIterator __last);
00650 
00651       void
00652       erase(iterator __position);
00653 
00654       size_type
00655       erase(const key_type& __x);
00656 
00657       void
00658       erase(iterator __first, iterator __last);
00659 
00660       void
00661       erase(const key_type* __first, const key_type* __last);
00662 
00663       void
00664       clear()
00665       {
00666         _M_erase(_M_begin());
00667         _M_leftmost() = _M_end();
00668         _M_root() = 0;
00669         _M_rightmost() = _M_end();
00670         _M_impl._M_node_count = 0;
00671       }
00672 
00673       // Set operations.
00674       iterator
00675       find(const key_type& __x);
00676 
00677       const_iterator
00678       find(const key_type& __x) const;
00679 
00680       size_type
00681       count(const key_type& __x) const;
00682 
00683       iterator
00684       lower_bound(const key_type& __x);
00685 
00686       const_iterator
00687       lower_bound(const key_type& __x) const;
00688 
00689       iterator
00690       upper_bound(const key_type& __x);
00691 
00692       const_iterator
00693       upper_bound(const key_type& __x) const;
00694 
00695       pair<iterator,iterator>
00696       equal_range(const key_type& __x);
00697 
00698       pair<const_iterator, const_iterator>
00699       equal_range(const key_type& __x) const;
00700 
00701       // Debugging.
00702       bool
00703       __rb_verify() const;
00704     };
00705 
00706   template<typename _Key, typename _Val, typename _KeyOfValue,
00707            typename _Compare, typename _Alloc>
00708     inline bool
00709     operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00710            const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00711     {
00712       return __x.size() == __y.size()
00713          && std::equal(__x.begin(), __x.end(), __y.begin());
00714     }
00715 
00716   template<typename _Key, typename _Val, typename _KeyOfValue,
00717            typename _Compare, typename _Alloc>
00718     inline bool
00719     operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00720           const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00721     {
00722       return std::lexicographical_compare(__x.begin(), __x.end(), 
00723                       __y.begin(), __y.end());
00724     }
00725 
00726   template<typename _Key, typename _Val, typename _KeyOfValue,
00727            typename _Compare, typename _Alloc>
00728     inline bool
00729     operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00730            const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00731     { return !(__x == __y); }
00732 
00733   template<typename _Key, typename _Val, typename _KeyOfValue,
00734            typename _Compare, typename _Alloc>
00735     inline bool
00736     operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00737           const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00738     { return __y < __x; }
00739 
00740   template<typename _Key, typename _Val, typename _KeyOfValue,
00741            typename _Compare, typename _Alloc>
00742     inline bool
00743     operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00744            const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00745     { return !(__y < __x); }
00746 
00747   template<typename _Key, typename _Val, typename _KeyOfValue,
00748            typename _Compare, typename _Alloc>
00749     inline bool
00750     operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00751            const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00752     { return !(__x < __y); }
00753 
00754   template<typename _Key, typename _Val, typename _KeyOfValue,
00755            typename _Compare, typename _Alloc>
00756     inline void
00757     swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00758      _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00759     { __x.swap(__y); }
00760 
00761   template<typename _Key, typename _Val, typename _KeyOfValue,
00762            typename _Compare, typename _Alloc>
00763     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
00764     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00765     operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x)
00766     {
00767       if (this != &__x)
00768     {
00769       // Note that _Key may be a constant type.
00770       clear();
00771       _M_impl._M_key_compare = __x._M_impl._M_key_compare;
00772       if (__x._M_root() != 0)
00773         {
00774           _M_root() = _M_copy(__x._M_begin(), _M_end());
00775           _M_leftmost() = _S_minimum(_M_root());
00776           _M_rightmost() = _S_maximum(_M_root());
00777           _M_impl._M_node_count = __x._M_impl._M_node_count;
00778         }
00779     }
00780       return *this;
00781     }
00782 
00783   template<typename _Key, typename _Val, typename _KeyOfValue,
00784            typename _Compare, typename _Alloc>
00785     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
00786     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00787     _M_insert(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
00788     {
00789       _Link_type __z = _M_create_node(__v);
00790       bool __insert_left;
00791 
00792       __insert_left = (__x != 0 || __p == _M_end()
00793                || _M_impl._M_key_compare(_KeyOfValue()(__v), 
00794                          _S_key(__p)));
00795 
00796       _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,  
00797                     this->_M_impl._M_header);
00798       ++_M_impl._M_node_count;
00799       return iterator(__z);
00800     }
00801 
00802   template<typename _Key, typename _Val, typename _KeyOfValue,
00803            typename _Compare, typename _Alloc>
00804     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
00805     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00806     insert_equal(const _Val& __v)
00807     {
00808       _Link_type __x = _M_begin();
00809       _Link_type __y = _M_end();
00810       while (__x != 0)
00811     {
00812       __y = __x;
00813       __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
00814             _S_left(__x) : _S_right(__x);
00815     }
00816       return _M_insert(__x, __y, __v);
00817     }
00818 
00819   template<typename _Key, typename _Val, typename _KeyOfValue,
00820            typename _Compare, typename _Alloc>
00821     void
00822     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00823     swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t)
00824     {
00825       if (_M_root() == 0)
00826       {
00827     if (__t._M_root() != 0)
00828     {
00829       _M_root() = __t._M_root();
00830       _M_leftmost() = __t._M_leftmost();
00831       _M_rightmost() = __t._M_rightmost();
00832           _M_root()->_M_parent = _M_end();
00833 
00834       __t._M_root() = 0;
00835       __t._M_leftmost() = __t._M_end();
00836       __t._M_rightmost() = __t._M_end();
00837     }
00838       }
00839       else if (__t._M_root() == 0)
00840       {
00841     __t._M_root() = _M_root();
00842     __t._M_leftmost() = _M_leftmost();
00843     __t._M_rightmost() = _M_rightmost();
00844         __t._M_root()->_M_parent = __t._M_end();
00845 
00846     _M_root() = 0;
00847     _M_leftmost() = _M_end();
00848     _M_rightmost() = _M_end();
00849       }
00850       else
00851       {
00852     std::swap(_M_root(),__t._M_root());
00853     std::swap(_M_leftmost(),__t._M_leftmost());
00854     std::swap(_M_rightmost(),__t._M_rightmost());
00855 
00856     _M_root()->_M_parent = _M_end();
00857     __t._M_root()->_M_parent = __t._M_end();
00858       }
00859       // No need to swap header's color as it does not change.
00860       std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
00861       std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
00862     }
00863 
00864   template<typename _Key, typename _Val, typename _KeyOfValue,
00865            typename _Compare, typename _Alloc>
00866     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
00867                _Compare, _Alloc>::iterator, bool>
00868     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00869     insert_unique(const _Val& __v)
00870     {
00871       _Link_type __x = _M_begin();
00872       _Link_type __y = _M_end();
00873       bool __comp = true;
00874       while (__x != 0)
00875     {
00876       __y = __x;
00877       __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x));
00878       __x = __comp ? _S_left(__x) : _S_right(__x);
00879     }
00880       iterator __j = iterator(__y);
00881       if (__comp)
00882     if (__j == begin())
00883       return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
00884     else
00885       --__j;
00886       if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
00887     return pair<iterator, bool>(_M_insert(__x, __y, __v), true);
00888       return pair<iterator, bool>(__j, false);
00889     }
00890 
00891   template<typename _Key, typename _Val, typename _KeyOfValue,
00892            typename _Compare, typename _Alloc>
00893     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
00894     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00895     insert_unique(iterator __position, const _Val& __v)
00896     {
00897       if (__position._M_node == _M_end()
00898       || __position._M_node == _M_rightmost())
00899     {
00900       if (size() > 0
00901           && _M_impl._M_key_compare(_S_key(_M_rightmost()), 
00902                     _KeyOfValue()(__v)))
00903         return _M_insert(0, _M_rightmost(), __v);
00904       else
00905         return insert_unique(__v).first;
00906     }
00907       else
00908     {
00909       iterator __after = __position;
00910       ++__after;
00911       if (_M_impl._M_key_compare(_S_key(__position._M_node), 
00912                      _KeyOfValue()(__v))
00913           && _M_impl._M_key_compare(_KeyOfValue()(__v),
00914                     _S_key(__after._M_node)))
00915         {
00916           if (_S_right(__position._M_node) == 0)
00917         return _M_insert(0, __position._M_node, __v);
00918           else
00919         return _M_insert(__after._M_node, __after._M_node, __v);
00920           // First argument just needs to be non-null.
00921         }
00922       else
00923         return insert_unique(__v).first;
00924     }
00925     }
00926 
00927   template<typename _Key, typename _Val, typename _KeyOfValue,
00928            typename _Compare, typename _Alloc>
00929     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
00930     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00931     insert_equal(iterator __position, const _Val& __v)
00932     {
00933       if (__position._M_node == _M_end()
00934       || __position._M_node == _M_rightmost())
00935     {
00936       if (size() > 0
00937           && !_M_impl._M_key_compare(_KeyOfValue()(__v), 
00938                      _S_key(_M_rightmost())))
00939         return _M_insert(0, _M_rightmost(), __v);
00940       else
00941         return insert_equal(__v);
00942     }
00943       else
00944     {
00945       iterator __after = __position;
00946       ++__after;
00947       if (!_M_impl._M_key_compare(_KeyOfValue()(__v), 
00948                       _S_key(__position._M_node))
00949           && !_M_impl._M_key_compare(_S_key(__after._M_node),
00950                      _KeyOfValue()(__v)))
00951         {
00952           if (_S_right(__position._M_node) == 0)
00953         return _M_insert(0, __position._M_node, __v);
00954           else
00955         return _M_insert(__after._M_node, __after._M_node, __v);
00956           // First argument just needs to be non-null.
00957         }
00958       else
00959         return insert_equal(__v);
00960     }
00961     }
00962 
00963   template<typename _Key, typename _Val, typename _KoV,
00964            typename _Cmp, typename _Alloc>
00965     template<class _II>
00966       void
00967       _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
00968       insert_equal(_II __first, _II __last)
00969       {
00970     for (; __first != __last; ++__first)
00971       insert_equal(end(), *__first);
00972       }
00973 
00974   template<typename _Key, typename _Val, typename _KoV,
00975            typename _Cmp, typename _Alloc>
00976     template<class _II>
00977     void
00978     _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
00979     insert_unique(_II __first, _II __last)
00980     {
00981       for (; __first != __last; ++__first)
00982     insert_unique(end(), *__first);
00983     }
00984 
00985   template<typename _Key, typename _Val, typename _KeyOfValue,
00986            typename _Compare, typename _Alloc>
00987     inline void
00988     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00989     erase(iterator __position)
00990     {
00991       _Link_type __y =
00992     static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
00993                 (__position._M_node,
00994                  this->_M_impl._M_header));
00995       destroy_node(__y);
00996       --_M_impl._M_node_count;
00997     }
00998 
00999   template<typename _Key, typename _Val, typename _KeyOfValue,
01000            typename _Compare, typename _Alloc>
01001     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
01002     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01003     erase(const _Key& __x)
01004     {
01005       pair<iterator,iterator> __p = equal_range(__x);
01006       size_type __n = std::distance(__p.first, __p.second);
01007       erase(__p.first, __p.second);
01008       return __n;
01009     }
01010 
01011   template<typename _Key, typename _Val, typename _KoV,
01012            typename _Compare, typename _Alloc>
01013     typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
01014     _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
01015     _M_copy(_Const_Link_type __x, _Link_type __p)
01016     {
01017       // Structural copy.  __x and __p must be non-null.
01018       _Link_type __top = _M_clone_node(__x);
01019       __top->_M_parent = __p;
01020 
01021       try
01022     {
01023       if (__x->_M_right)
01024         __top->_M_right = _M_copy(_S_right(__x), __top);
01025       __p = __top;
01026       __x = _S_left(__x);
01027 
01028       while (__x != 0)
01029         {
01030           _Link_type __y = _M_clone_node(__x);
01031           __p->_M_left = __y;
01032           __y->_M_parent = __p;
01033           if (__x->_M_right)
01034         __y->_M_right = _M_copy(_S_right(__x), __y);
01035           __p = __y;
01036           __x = _S_left(__x);
01037         }
01038     }
01039       catch(...)
01040     {
01041       _M_erase(__top);
01042       __throw_exception_again;
01043     }
01044       return __top;
01045     }
01046 
01047   template<typename _Key, typename _Val, typename _KeyOfValue,
01048            typename _Compare, typename _Alloc>
01049     void
01050     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01051     _M_erase(_Link_type __x)
01052     {
01053       // Erase without rebalancing.
01054       while (__x != 0)
01055     {
01056       _M_erase(_S_right(__x));
01057       _Link_type __y = _S_left(__x);
01058       destroy_node(__x);
01059       __x = __y;
01060     }
01061     }
01062 
01063   template<typename _Key, typename _Val, typename _KeyOfValue,
01064            typename _Compare, typename _Alloc>
01065     void
01066     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01067     erase(iterator __first, iterator __last)
01068     {
01069       if (__first == begin() && __last == end())
01070     clear();
01071       else
01072     while (__first != __last)
01073       erase(__first++);
01074     }
01075 
01076   template<typename _Key, typename _Val, typename _KeyOfValue,
01077            typename _Compare, typename _Alloc>
01078     void
01079     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01080     erase(const _Key* __first, const _Key* __last)
01081     {
01082       while (__first != __last)
01083     erase(*__first++);
01084     }
01085 
01086   template<typename _Key, typename _Val, typename _KeyOfValue,
01087            typename _Compare, typename _Alloc>
01088     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
01089     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01090     find(const _Key& __k)
01091     {
01092       _Link_type __x = _M_begin(); // Current node.
01093       _Link_type __y = _M_end(); // Last node which is not less than __k.
01094 
01095       while (__x != 0)
01096     if (!_M_impl._M_key_compare(_S_key(__x), __k))
01097       __y = __x, __x = _S_left(__x);
01098     else
01099       __x = _S_right(__x);
01100 
01101       iterator __j = iterator(__y);
01102       return (__j == end()
01103           || _M_impl._M_key_compare(__k,
01104                     _S_key(__j._M_node))) ? end() : __j;
01105     }
01106 
01107   template<typename _Key, typename _Val, typename _KeyOfValue,
01108            typename _Compare, typename _Alloc>
01109     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
01110     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01111     find(const _Key& __k) const
01112     {
01113       _Const_Link_type __x = _M_begin(); // Current node.
01114       _Const_Link_type __y = _M_end(); // Last node which is not less than __k.
01115 
01116      while (__x != 0)
01117        {
01118      if (!_M_impl._M_key_compare(_S_key(__x), __k))
01119        __y = __x, __x = _S_left(__x);
01120      else
01121        __x = _S_right(__x);
01122        }
01123      const_iterator __j = const_iterator(__y);
01124      return (__j == end()
01125          || _M_impl._M_key_compare(__k, 
01126                        _S_key(__j._M_node))) ? end() : __j;
01127     }
01128 
01129   template<typename _Key, typename _Val, typename _KeyOfValue,
01130            typename _Compare, typename _Alloc>
01131     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
01132     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01133     count(const _Key& __k) const
01134     {
01135       pair<const_iterator, const_iterator> __p = equal_range(__k);
01136       const size_type __n = std::distance(__p.first, __p.second);
01137       return __n;
01138     }
01139 
01140   template<typename _Key, typename _Val, typename _KeyOfValue,
01141            typename _Compare, typename _Alloc>
01142     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
01143     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01144     lower_bound(const _Key& __k)
01145     {
01146       _Link_type __x = _M_begin(); // Current node.
01147       _Link_type __y = _M_end(); // Last node which is not less than __k.
01148 
01149       while (__x != 0)
01150     if (!_M_impl._M_key_compare(_S_key(__x), __k))
01151       __y = __x, __x = _S_left(__x);
01152     else
01153       __x = _S_right(__x);
01154 
01155       return iterator(__y);
01156     }
01157 
01158   template<typename _Key, typename _Val, typename _KeyOfValue,
01159            typename _Compare, typename _Alloc>
01160     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
01161     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01162     lower_bound(const _Key& __k) const
01163     {
01164       _Const_Link_type __x = _M_begin(); // Current node.
01165       _Const_Link_type __y = _M_end(); // Last node which is not less than __k.
01166 
01167       while (__x != 0)
01168     if (!_M_impl._M_key_compare(_S_key(__x), __k))
01169       __y = __x, __x = _S_left(__x);
01170     else
01171       __x = _S_right(__x);
01172 
01173       return const_iterator(__y);
01174     }
01175 
01176   template<typename _Key, typename _Val, typename _KeyOfValue,
01177            typename _Compare, typename _Alloc>
01178     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
01179     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01180     upper_bound(const _Key& __k)
01181     {
01182       _Link_type __x = _M_begin(); // Current node.
01183       _Link_type __y = _M_end(); // Last node which is greater than __k.
01184 
01185       while (__x != 0)
01186     if (_M_impl._M_key_compare(__k, _S_key(__x)))
01187       __y = __x, __x = _S_left(__x);
01188     else
01189       __x = _S_right(__x);
01190 
01191       return iterator(__y);
01192     }
01193 
01194   template<typename _Key, typename _Val, typename _KeyOfValue,
01195            typename _Compare, typename _Alloc>
01196     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
01197     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01198     upper_bound(const _Key& __k) const
01199     {
01200       _Const_Link_type __x = _M_begin(); // Current node.
01201       _Const_Link_type __y = _M_end(); // Last node which is greater than __k.
01202 
01203       while (__x != 0)
01204     if (_M_impl._M_key_compare(__k, _S_key(__x)))
01205       __y = __x, __x = _S_left(__x);
01206     else
01207       __x = _S_right(__x);
01208 
01209       return const_iterator(__y);
01210     }
01211 
01212   template<typename _Key, typename _Val, typename _KeyOfValue,
01213            typename _Compare, typename _Alloc>
01214     inline
01215     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
01216                _Compare, _Alloc>::iterator,
01217      typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator>
01218     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01219     equal_range(const _Key& __k)
01220     { return pair<iterator, iterator>(lower_bound(__k), upper_bound(__k)); }
01221 
01222   template<typename _Key, typename _Val, typename _KoV,
01223            typename _Compare, typename _Alloc>
01224     inline
01225     pair<typename _Rb_tree<_Key, _Val, _KoV,
01226                _Compare, _Alloc>::const_iterator,
01227      typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::const_iterator>
01228     _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
01229     equal_range(const _Key& __k) const
01230     { return pair<const_iterator, const_iterator>(lower_bound(__k),
01231                           upper_bound(__k)); }
01232 
01233   unsigned int
01234   _Rb_tree_black_count(const _Rb_tree_node_base* __node,
01235                        const _Rb_tree_node_base* __root);
01236 
01237   template<typename _Key, typename _Val, typename _KeyOfValue,
01238            typename _Compare, typename _Alloc>
01239     bool
01240     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
01241     {
01242       if (_M_impl._M_node_count == 0 || begin() == end())
01243     return _M_impl._M_node_count == 0 && begin() == end()
01244            && this->_M_impl._M_header._M_left == _M_end()
01245            && this->_M_impl._M_header._M_right == _M_end();
01246 
01247       unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
01248       for (const_iterator __it = begin(); __it != end(); ++__it)
01249     {
01250       _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
01251       _Const_Link_type __L = _S_left(__x);
01252       _Const_Link_type __R = _S_right(__x);
01253 
01254       if (__x->_M_color == _S_red)
01255         if ((__L && __L->_M_color == _S_red)
01256         || (__R && __R->_M_color == _S_red))
01257           return false;
01258 
01259       if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
01260         return false;
01261       if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
01262         return false;
01263 
01264       if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
01265         return false;
01266     }
01267 
01268       if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
01269     return false;
01270       if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
01271     return false;
01272       return true;
01273     }
01274 } // namespace std
01275 
01276 #endif

Generated on Sat Apr 2 13:54:44 2005 for libstdc++ source by  doxygen 1.4.0