boost/intrusive/detail/irbtree.hpp

   1 /////////////////////////////////////////////////////////////////////////////\r
   2 //\r
   3 // (C) Copyright Ion Gaztañaga  2006-2007\r
   4 //\r
   5 // Distributed under the Boost Software License, Version 1.0.\r
   6 //    (See accompanying file LICENSE_1_0.txt or copy at\r
   7 //          http://www.boost.org/LICENSE_1_0.txt)\r
   8 //\r
   9 // See http://www.boost.org/libs/intrusive for documentation.\r
  10 //\r
  11 /////////////////////////////////////////////////////////////////////////////\r
  12 #ifndef BOOST_INTRUSIVE_IRBTREE_HPP\r
  13 #define BOOST_INTRUSIVE_IRBTREE_HPP\r
  14 \r
  15 #include <boost/intrusive/detail/config_begin.hpp>\r
  16 #include <functional>\r
  17 #include <iterator>\r
  18 #include <boost/utility.hpp>\r
  19 #include <boost/compressed_pair.hpp>\r
  20 #include <utility>\r
  21 #include <boost/assert.hpp>\r
  22 #include <boost/static_assert.hpp>\r
  23 #include <boost/intrusive/detail/pointer_type.hpp>\r
  24 #include <boost/intrusive/detail/pointer_to_other.hpp>\r
  25 #include <boost/intrusive/iset_hook.hpp>\r
  26 #include <boost/intrusive/detail/rbtree_node.hpp>\r
  27 #include <boost/intrusive/detail/ebo_holder.hpp>\r
  28 #include <boost/intrusive/rbtree_algorithms.hpp>\r
  29 #include <boost/intrusive/linking_policy.hpp>\r
  30 #include <cstddef>\r
  31 #include <iterator>\r
  32 \r
  33 namespace boost {\r
  34 namespace intrusive {\r
  35 namespace detail {\r
  36 \r
  37 //! The class template irbtree is an intrusive red-black tree container, that\r
  38 //! is used to construct intrusive set and tree containers. The no-throw \r
  39 //! guarantee holds only, if the Compare object \r
  40 //! doesn't throw.\r
  41 template < class ValueTraits\r
  42          , class Compare         = std::less<typename ValueTraits::value_type>\r
  43          , bool ConstantTimeSize = true\r
  44          , class SizeType = std::size_t\r
  45          >\r
  46 class irbtree\r
  47    :  private detail::size_holder<ConstantTimeSize, SizeType>\r
  48 {\r
  49    private:\r
  50    typedef irbtree<ValueTraits, Compare\r
  51                   ,ConstantTimeSize, SizeType>              this_type; \r
  52    typedef typename ValueTraits::node_traits                node_traits;\r
  53    typedef detail::size_holder<ConstantTimeSize, SizeType>    size_traits;\r
  54 \r
  55    //noncopyable\r
  56    irbtree (const irbtree&);\r
  57    irbtree operator =(const irbtree&);\r
  58 \r
  59    public:\r
  60    typedef typename ValueTraits::value_type        value_type;\r
  61    typedef typename ValueTraits::pointer           pointer;\r
  62    typedef typename ValueTraits::const_pointer     const_pointer;\r
  63    typedef value_type&                             reference;\r
  64    typedef const value_type&                       const_reference;\r
  65    typedef SizeType                                size_type;\r
  66    typedef typename std::iterator_traits\r
  67       <pointer>::difference_type                   difference_type;\r
  68    typedef value_type                              key_type;\r
  69    typedef Compare                                 value_compare;\r
  70    class iterator;\r
  71    class const_iterator;\r
  72    friend class iterator;\r
  73    friend class const_iterator;\r
  74 \r
  75    private:\r
  76    typedef typename node_traits::node              node;\r
  77    typedef typename boost::pointer_to_other\r
  78       <pointer, node>::type                        node_ptr;\r
  79    typedef typename boost::pointer_to_other\r
  80       <node_ptr, const node>::type                 const_node_ptr;\r
  81    typedef rbtree_algorithms<node_traits>          node_algorithms;\r
  82    enum { safemode_or_autounlink  = \r
  83             (int)ValueTraits::linking_policy == (int)auto_unlink   ||\r
  84             (int)ValueTraits::linking_policy == (int)safe_mode_link     };\r
  85 \r
  86    //Constant-time size is incompatible with auto-unlink hooks!\r
  87    BOOST_STATIC_ASSERT(!(ConstantTimeSize && ((int)ValueTraits::linking_policy == (int)auto_unlink)));\r
  88 \r
  89    template<class KeyValueCompare>\r
  90    struct key_node_ptr_compare\r
  91       :  private ebo_holder<KeyValueCompare>\r
  92    {\r
  93       typedef ebo_holder<KeyValueCompare> base_t;\r
  94       key_node_ptr_compare(KeyValueCompare kcomp)\r
  95          :  base_t(kcomp)\r
  96       {}\r
  97 \r
  98       template<class KeyType>\r
  99       bool operator()(node_ptr node, const KeyType &key) const\r
 100       {  return base_t::get()(*ValueTraits::to_value_ptr(node), key); }\r
 101 \r
 102       template<class KeyType>\r
 103       bool operator()(const KeyType &key, node_ptr node) const\r
 104       {  return base_t::get()(key, *ValueTraits::to_value_ptr(node)); }\r
 105 \r
 106       bool operator()(node_ptr node1, node_ptr node2) const\r
 107       {\r
 108          return base_t::get()\r
 109             (*ValueTraits::to_value_ptr(node1), *ValueTraits::to_value_ptr(node2)); \r
 110       }\r
 111    };\r
 112 \r
 113    //Use boost::compressed_pair to get EBO if possible\r
 114    boost::compressed_pair<node, Compare> members_;\r
 115    \r
 116    const Compare &priv_comp() const\r
 117    {  return members_.second();  }\r
 118 \r
 119    Compare &priv_comp()\r
 120    {  return members_.second();  }\r
 121 \r
 122    const node &priv_header() const\r
 123    {  return members_.first();  }\r
 124 \r
 125    node &priv_header()\r
 126    {  return members_.first();  }\r
 127 \r
 128    template<class F>\r
 129    struct value_to_node_cloner\r
 130       :  private ebo_holder<F>\r
 131    {\r
 132       typedef ebo_holder<F> base_t;\r
 133       value_to_node_cloner(F f)\r
 134          :  base_t(f)\r
 135       {}\r
 136       \r
 137       node_ptr operator()(node_ptr p)\r
 138       {  return ValueTraits::to_node_ptr(*base_t::get()(*ValueTraits::to_value_ptr(p))); }\r
 139    };\r
 140 \r
 141    template<class F>\r
 142    struct value_to_node_destroyer\r
 143       :  private ebo_holder<F>\r
 144    {\r
 145       typedef ebo_holder<F> base_t;\r
 146       value_to_node_destroyer(F f)\r
 147          :  base_t(f)\r
 148       {}\r
 149 \r
 150       void operator()(node_ptr p)\r
 151       {  base_t::get()(ValueTraits::to_value_ptr(p));   }\r
 152    };\r
 153 \r
 154    static node_ptr uncast(const_node_ptr ptr)\r
 155    {\r
 156       using boost::get_pointer;\r
 157       return node_ptr(const_cast<node*>(get_pointer(ptr)));\r
 158    }\r
 159 \r
 160    public:\r
 161    typedef typename node_algorithms::insert_commit_data insert_commit_data;\r
 162 \r
 163    class iterator\r
 164       :  public detail::rbtree_iterator <value_type, iterator, node_traits>\r
 165     {\r
 166       private:\r
 167       typedef typename irbtree<ValueTraits, Compare, ConstantTimeSize, SizeType>::value_type   private_vt;\r
 168       typedef typename irbtree<ValueTraits, Compare, ConstantTimeSize, SizeType>::pointer      private_pointer;\r
 169       typedef typename irbtree<ValueTraits, Compare, ConstantTimeSize, SizeType>::reference    private_reference;\r
 170       typedef detail::rbtree_iterator<private_vt, iterator, node_traits>   inherited;\r
 171 \r
 172       public:\r
 173       iterator ()\r
 174       {}\r
 175 \r
 176       private_pointer operator->() const\r
 177       { return  ValueTraits::to_value_ptr(this->tree_node()); }\r
 178 \r
 179       private_reference operator*() const\r
 180       { return *ValueTraits::to_value_ptr(this->tree_node()); }\r
 181 \r
 182       private:\r
 183       explicit iterator(node_ptr node)\r
 184          :  inherited(node)\r
 185       {}\r
 186       \r
 187       friend class irbtree<ValueTraits, Compare, ConstantTimeSize, SizeType>; \r
 188       friend class detail::rbtree_iterator<private_vt, iterator, node_traits>;\r
 189       friend class const_iterator;\r
 190    };\r
 191 \r
 192    class const_iterator\r
 193       :  public detail::rbtree_iterator<const value_type, const_iterator, node_traits>\r
 194    {\r
 195       private:\r
 196       typedef const typename irbtree<ValueTraits, Compare, ConstantTimeSize, SizeType>::value_type private_vt;\r
 197       typedef typename irbtree<ValueTraits, Compare, ConstantTimeSize, SizeType>::const_pointer    private_pointer;\r
 198       typedef typename irbtree<ValueTraits, Compare, ConstantTimeSize, SizeType>::const_reference  private_reference;\r
 199       typedef detail::rbtree_iterator<private_vt, const_iterator, node_traits>   inherited;\r
 200 \r
 201       public:\r
 202       const_iterator ()\r
 203       {}\r
 204 \r
 205       const_iterator(const typename irbtree::iterator& it)\r
 206          :  inherited (it.tree_node())\r
 207       {}\r
 208 \r
 209       const_iterator & operator=(const typename irbtree::iterator& it)\r
 210       {  return inherited::operator=(it.tree_node());  }\r
 211 \r
 212       private_pointer   operator->()\r
 213       { return  ValueTraits::to_value_ptr(this->tree_node()); }\r
 214 \r
 215       private_reference operator*()\r
 216       { return *ValueTraits::to_value_ptr(this->tree_node()); }\r
 217 \r
 218       private:\r
 219       explicit const_iterator (const_node_ptr p)\r
 220          :  inherited (uncast(p))\r
 221       {}\r
 222 \r
 223       friend class irbtree<ValueTraits, Compare, ConstantTimeSize, SizeType>; \r
 224       friend class detail::rbtree_iterator<private_vt, const_iterator, node_traits>;\r
 225    };\r
 226 \r
 227    typedef std::reverse_iterator<iterator>         reverse_iterator;\r
 228    typedef std::reverse_iterator<const_iterator>   const_reverse_iterator;\r
 229 \r
 230    public:\r
 231 \r
 232    //! <b>Effects</b>: Constructs an empty tree. \r
 233    //!   \r
 234    //! <b>Complexity</b>: Constant. \r
 235    //! \r
 236    //! <b>Throws</b>: Nothing unless the copy constructor of the Compare object throws. \r
 237    irbtree(Compare cmp = Compare()) \r
 238       :  members_(cmp)\r
 239    {  \r
 240       node_algorithms::init_header(&priv_header());  \r
 241       size_traits::set_size(size_type(0));\r
 242    }\r
 243 \r
 244    //! <b>Requires</b>: Dereferencing iterator must yield an lvalue of type value_type. \r
 245    //!   cmp must be a comparison function that induces a strict weak ordering.\r
 246    //! \r
 247    //! <b>Effects</b>: Constructs an empty tree and inserts elements from \r
 248    //!   [b, e).\r
 249    //! \r
 250    //! <b>Complexity</b>: Linear in N if [b, e) is already sorted using \r
 251    //!   comp and otherwise N * log N, where N is last  first.\r
 252    //! \r
 253    //! <b>Throws</b>: Nothing unless the copy constructor of the Compare object throws. \r
 254    template<class Iterator>\r
 255    irbtree(bool unique, Iterator b, Iterator e, Compare cmp = Compare())\r
 256       : members_(cmp)\r
 257    {\r
 258       node_algorithms::init_header(&priv_header());\r
 259       size_traits::set_size(size_type(0));\r
 260       if(unique)\r
 261          this->insert_unique(b, e);\r
 262       else\r
 263          this->insert_equal(b, e);\r
 264    }\r
 265 \r
 266    //! <b>Effects</b>: Detaches all elements from this. The objects in the set \r
 267    //!   are not deleted (i.e. no destructors are called), but the nodes according to \r
 268    //!   the ValueTraits template parameter are reinitialized and thus can be reused. \r
 269    //! \r
 270    //! <b>Complexity</b>: Linear to elements contained in *this. \r
 271    //! \r
 272    //! <b>Throws</b>: Nothing.\r
 273    ~irbtree() \r
 274    {  this->clear(); }\r
 275 \r
 276    //! <b>Effects</b>: Returns an iterator pointing to the beginning of the tree.\r
 277    //! \r
 278    //! <b>Complexity</b>: Constant.\r
 279    //! \r
 280    //! <b>Throws</b>: Nothing.\r
 281    iterator begin()\r
 282    {  return iterator (node_traits::get_left(node_ptr(&priv_header())));   }\r
 283 \r
 284    //! <b>Effects</b>: Returns a const_iterator pointing to the beginning of the tree.\r
 285    //! \r
 286    //! <b>Complexity</b>: Constant.\r
 287    //! \r
 288    //! <b>Throws</b>: Nothing.\r
 289    const_iterator begin() const\r
 290    {  return const_iterator (node_traits::get_left(const_node_ptr(&priv_header())));   }\r
 291 \r
 292    //! <b>Effects</b>: Returns an iterator pointing to the end of the tree.\r
 293    //! \r
 294    //! <b>Complexity</b>: Constant.\r
 295    //! \r
 296    //! <b>Throws</b>: Nothing.\r
 297    iterator end()\r
 298    {  return iterator (node_ptr(&priv_header()));  }\r
 299 \r
 300    //! <b>Effects</b>: Returns a const_iterator pointing to the end of the tree.\r
 301    //! \r
 302    //! <b>Complexity</b>: Constant.\r
 303    //! \r
 304    //! <b>Throws</b>: Nothing.\r
 305    const_iterator end() const\r
 306    {  return const_iterator (const_node_ptr(&priv_header()));  }\r
 307 \r
 308    //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning of the\r
 309    //!    reversed tree.\r
 310    //! \r
 311    //! <b>Complexity</b>: Constant.\r
 312    //! \r
 313    //! <b>Throws</b>: Nothing.\r
 314    reverse_iterator rbegin()\r
 315    {  return reverse_iterator(end());  }\r
 316 \r
 317    //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning\r
 318    //!    of the reversed tree.\r
 319    //! \r
 320    //! <b>Complexity</b>: Constant.\r
 321    //! \r
 322    //! <b>Throws</b>: Nothing.\r
 323    const_reverse_iterator rbegin() const\r
 324    {  return const_reverse_iterator(end());  }\r
 325 \r
 326    //! <b>Effects</b>: Returns a reverse_iterator pointing to the end\r
 327    //!    of the reversed tree.\r
 328    //! \r
 329    //! <b>Complexity</b>: Constant.\r
 330    //! \r
 331    //! <b>Throws</b>: Nothing.\r
 332    reverse_iterator rend()\r
 333    {  return reverse_iterator(begin());   }\r
 334 \r
 335    //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end\r
 336    //!    of the reversed tree.\r
 337    //! \r
 338    //! <b>Complexity</b>: Constant.\r
 339    //! \r
 340    //! <b>Throws</b>: Nothing.\r
 341    const_reverse_iterator rend() const\r
 342    {  return const_reverse_iterator(begin());   }\r
 343 \r
 344    //! <b>Effects</b>: Returns the value_compare object used by the tree.\r
 345    //! \r
 346    //! <b>Complexity</b>: Constant.\r
 347    //! \r
 348    //! <b>Throws</b>: If value_compare copy-constructor throws.\r
 349    value_compare value_comp() const\r
 350    {  return priv_comp();   }\r
 351 \r
 352    //! <b>Effects</b>: Returns true is the container is empty.\r
 353    //! \r
 354    //! <b>Complexity</b>: Constant.\r
 355    //! \r
 356    //! <b>Throws</b>: Nothing.\r
 357    bool empty() const\r
 358    {  return node_algorithms::unique(const_node_ptr(&priv_header()));   }\r
 359 \r
 360    //! <b>Effects</b>: Returns the number of elements stored in the tree.\r
 361    //! \r
 362    //! <b>Complexity</b>: Linear to elements contained in *this.\r
 363    //! \r
 364    //! <b>Throws</b>: Nothing.\r
 365    size_type size() const\r
 366    {\r
 367       if(ConstantTimeSize)\r
 368          return size_traits::get_size();\r
 369       else\r
 370          return empty() ? 0 : node_algorithms::count(node_traits::get_parent(const_node_ptr(&priv_header())));\r
 371    }\r
 372 \r
 373    //! <b>Effects</b>: Swaps the contents of two multisets.\r
 374    //! \r
 375    //! <b>Complexity</b>: Constant.\r
 376    //! \r
 377    //! <b>Throws</b>: If the comparison functor's unspecified swap call throws.\r
 378    void swap(irbtree& other)\r
 379    {\r
 380       //This can throw\r
 381       using std::swap;\r
 382       swap(priv_comp(), priv_comp());\r
 383       //These can't throw\r
 384       node_algorithms::swap_tree(node_ptr(&priv_header()), node_ptr(&other.priv_header()));\r
 385       if(ConstantTimeSize){\r
 386          size_type backup = size_traits::get_size();\r
 387          size_traits::set_size(other.get_size());\r
 388          other.set_size(backup);\r
 389       }\r
 390    }\r
 391 \r
 392    //! <b>Requires</b>: value must be an lvalue\r
 393    //! \r
 394    //! <b>Effects</b>: Inserts value into the tree before the upper bound.\r
 395    //! \r
 396    //! <b>Complexity</b>: Average complexity for insert element is at\r
 397    //!   most logarithmic.\r
 398    //! \r
 399    //! <b>Throws</b>: Nothing.\r
 400    //! \r
 401    //! <b>Note</b>: Does not affect the validity of iterators and references.\r
 402    //!   No copy-constructors are called.\r
 403    iterator insert_equal_upper_bound(value_type &value)\r
 404    {\r
 405       key_node_ptr_compare<value_compare> key_node_comp(priv_comp());\r
 406       node_ptr to_insert(ValueTraits::to_node_ptr(value));\r
 407       if(safemode_or_autounlink)\r
 408          BOOST_ASSERT(node_algorithms::unique(to_insert));\r
 409       size_traits::increment();\r
 410       return iterator(node_algorithms::insert_equal_upper_bound\r
 411          (node_ptr(&priv_header()), to_insert, key_node_comp));\r
 412    }\r
 413 \r
 414    //! <b>Requires</b>: value must be an lvalue\r
 415    //! \r
 416    //! <b>Effects</b>: Inserts value into the tree before the lower bound.\r
 417    //! \r
 418    //! <b>Complexity</b>: Average complexity for insert element is at\r
 419    //!   most logarithmic.\r
 420    //! \r
 421    //! <b>Throws</b>: Nothing.\r
 422    //! \r
 423    //! <b>Note</b>: Does not affect the validity of iterators and references.\r
 424    //!   No copy-constructors are called.\r
 425    iterator insert_equal_lower_bound(value_type &value)\r
 426    {\r
 427       key_node_ptr_compare<value_compare> key_node_comp(priv_comp());\r
 428       node_ptr to_insert(ValueTraits::to_node_ptr(value));\r
 429       if(safemode_or_autounlink)\r
 430          BOOST_ASSERT(node_algorithms::unique(to_insert));\r
 431       size_traits::increment();\r
 432       return iterator(node_algorithms::insert_equal_lower_bound\r
 433          (node_ptr(&priv_header()), to_insert, key_node_comp));\r
 434    }\r
 435 \r
 436    //! <b>Requires</b>: value must be an lvalue, and "hint" must be\r
 437    //!   a valid iterator.\r
 438    //! \r
 439    //! <b>Effects</b>: Inserts x into the tree, using "hint" as a hint to\r
 440    //!   where it will be inserted. If "hint" is the upper_bound\r
 441    //!   the insertion takes constant time (two comparisons in the worst case)\r
 442    //! \r
 443    //! <b>Complexity</b>: Logarithmic in general, but it is amortized\r
 444    //!   constant time if t is inserted immediately before hint.\r
 445    //! \r
 446    //! <b>Throws</b>: Nothing.\r
 447    //! \r
 448    //! <b>Note</b>: Does not affect the validity of iterators and references.\r
 449    //!   No copy-constructors are called.\r
 450    iterator insert_equal(const_iterator hint, value_type &value)\r
 451    {\r
 452       key_node_ptr_compare<value_compare> key_node_comp(priv_comp());\r
 453       node_ptr to_insert(ValueTraits::to_node_ptr(value));\r
 454       if(safemode_or_autounlink)\r
 455          BOOST_ASSERT(node_algorithms::unique(to_insert));\r
 456       size_traits::increment();\r
 457       return iterator(node_algorithms::insert_equal\r
 458          (node_ptr(&priv_header()), hint.tree_node(), to_insert, key_node_comp));\r
 459    }\r
 460 \r
 461    //! <b>Requires</b>: Dereferencing iterator must yield an lvalue \r
 462    //!   of type value_type.\r
 463    //! \r
 464    //! <b>Effects</b>: Inserts a each element of a range into the tree\r
 465    //!   before the upper bound of the key of each element.\r
 466    //! \r
 467    //! <b>Complexity</b>: Insert range is in general O(N * log(N)), where N is the \r
 468    //!   size of the range. However, it is linear in N if the range is already sorted \r
 469    //!   by value_comp().\r
 470    //! \r
 471    //! <b>Throws</b>: Nothing.\r
 472    //! \r
 473    //! <b>Note</b>: Does not affect the validity of iterators and references.\r
 474    //!   No copy-constructors are called.\r
 475    template<class Iterator>\r
 476    void insert_equal(Iterator b, Iterator e)\r
 477    {\r
 478       if(this->empty()){\r
 479          iterator end(this->end());\r
 480          for (; b != e; ++b)\r
 481             this->insert_equal(end, *b);\r
 482       }\r
 483       else{\r
 484          for (; b != e; ++b)\r
 485             this->insert_equal_upper_bound(*b);\r
 486       }\r
 487    }\r
 488 \r
 489    //! <b>Requires</b>: value must be an lvalue\r
 490    //! \r
 491    //! <b>Effects</b>: Inserts value into the tree if the value\r
 492    //!   is not already present.\r
 493    //! \r
 494    //! <b>Complexity</b>: Average complexity for insert element is at\r
 495    //!   most logarithmic.\r
 496    //! \r
 497    //! <b>Throws</b>: Nothing.\r
 498    //! \r
 499    //! <b>Note</b>: Does not affect the validity of iterators and references.\r
 500    //!   No copy-constructors are called.\r
 501    std::pair<iterator, bool> insert_unique(value_type &value)\r
 502    {\r
 503       insert_commit_data commit_data;\r
 504       std::pair<iterator, bool> ret = insert_unique_check(value, commit_data);\r
 505       if(!ret.second)\r
 506          return ret;\r
 507       return std::pair<iterator, bool> (insert_unique_commit(value, commit_data), true);\r
 508    }\r
 509 \r
 510    //! <b>Requires</b>: value must be an lvalue, and "hint" must be\r
 511    //!   a valid iterator\r
 512    //! \r
 513    //! <b>Effects</b>: Tries to insert x into the tree, using "hint" as a hint\r
 514    //!   to where it will be inserted.\r
 515    //! \r
 516    //! <b>Complexity</b>: Logarithmic in general, but it is amortized\r
 517    //!   constant time (two comparisons in the worst case)\r
 518    //!   if t is inserted immediately before hint.\r
 519    //! \r
 520    //! <b>Throws</b>: Nothing.\r
 521    //! \r
 522    //! <b>Note</b>: Does not affect the validity of iterators and references.\r
 523    //!   No copy-constructors are called.\r
 524    iterator insert_unique(const_iterator hint, value_type &value)\r
 525    {\r
 526       insert_commit_data commit_data;\r
 527       std::pair<iterator, bool> ret = insert_unique_check(hint, value, commit_data);\r
 528       if(!ret.second)\r
 529          return ret.first;\r
 530       return insert_unique_commit(value, commit_data);\r
 531    }\r
 532 \r
 533    //! <b>Requires</b>: Dereferencing iterator must yield an lvalue \r
 534    //!   of type value_type.\r
 535    //! \r
 536    //! <b>Effects</b>: Tries to insert each element of a range into the tree.\r
 537    //! \r
 538    //! <b>Complexity</b>: Insert range is in general O(N * log(N)), where N is the \r
 539    //!   size of the range. However, it is linear in N if the range is already sorted \r
 540    //!   by value_comp().\r
 541    //! \r
 542    //! <b>Throws</b>: Nothing.\r
 543    //! \r
 544    //! <b>Note</b>: Does not affect the validity of iterators and references.\r
 545    //!   No copy-constructors are called.\r
 546    template<class Iterator>\r
 547    void insert_unique(Iterator b, Iterator e)\r
 548    {\r
 549       if(this->empty()){\r
 550          iterator end(this->end());\r
 551          for (; b != e; ++b)\r
 552             this->insert_unique(end, *b);\r
 553       }\r
 554       else{\r
 555          for (; b != e; ++b)\r
 556             this->insert_unique(*b);\r
 557       }\r
 558    }\r
 559 \r
 560    std::pair<iterator, bool> insert_unique_check\r
 561       (const value_type &value, insert_commit_data &commit_data)\r
 562    {  return insert_unique_check(value, priv_comp(), commit_data); }\r
 563 \r
 564    template<class KeyType, class KeyValueCompare>\r
 565    std::pair<iterator, bool> insert_unique_check\r
 566       (const KeyType &key, KeyValueCompare key_value_comp, insert_commit_data &commit_data)\r
 567    {\r
 568       key_node_ptr_compare<KeyValueCompare> comp(key_value_comp);\r
 569       std::pair<node_ptr, bool> ret = \r
 570          (node_algorithms::insert_unique_check\r
 571             (node_ptr(&priv_header()), key, comp, commit_data));\r
 572       return std::pair<iterator, bool>(iterator(ret.first), ret.second);\r
 573    }\r
 574 \r
 575    std::pair<iterator, bool> insert_unique_check\r
 576       (const_iterator hint, const value_type &value, insert_commit_data &commit_data)\r
 577    {  return insert_unique_check(hint, value, priv_comp(), commit_data); }\r
 578 \r
 579    template<class KeyType, class KeyValueCompare>\r
 580    std::pair<iterator, bool> insert_unique_check\r
 581       (const_iterator hint, const KeyType &key\r
 582       ,KeyValueCompare key_value_comp, insert_commit_data &commit_data)\r
 583    {\r
 584       key_node_ptr_compare<KeyValueCompare> comp(key_value_comp);\r
 585       std::pair<node_ptr, bool> ret = \r
 586          (node_algorithms::insert_unique_check\r
 587             (node_ptr(&priv_header()), hint.tree_node(), key, comp, commit_data));\r
 588       return std::pair<iterator, bool>(iterator(ret.first), ret.second);\r
 589    }\r
 590 \r
 591    iterator insert_unique_commit(value_type &value, const insert_commit_data &commit_data)\r
 592    {\r
 593       node_ptr to_insert(ValueTraits::to_node_ptr(value));\r
 594       if(safemode_or_autounlink)\r
 595          BOOST_ASSERT(node_algorithms::unique(to_insert));\r
 596       size_traits::increment();\r
 597       node_algorithms::insert_unique_commit\r
 598                (node_ptr(&priv_header()), to_insert, commit_data);\r
 599       return iterator(to_insert);\r
 600    }\r
 601 \r
 602    //! <b>Effects</b>: Erases the element pointed to by pos. \r
 603    //! \r
 604    //! <b>Complexity</b>: Average complexity for erase element is constant time. \r
 605    //! \r
 606    //! <b>Throws</b>: Nothing.\r
 607    //! \r
 608    //! <b>Note</b>: Invalidates the iterators (but not the references)\r
 609    //!    to the erased elements. No destructors are called.\r
 610    iterator erase(iterator i)\r
 611    {\r
 612       iterator ret(i);\r
 613       ++ret;\r
 614       node_ptr to_erase(i.tree_node());\r
 615       if(safemode_or_autounlink)\r
 616          BOOST_ASSERT(!node_algorithms::unique(to_erase));\r
 617       node_algorithms::erase(&priv_header(), to_erase);\r
 618       size_traits::decrement();\r
 619       if(safemode_or_autounlink)\r
 620          node_algorithms::init(to_erase);\r
 621       return ret;\r
 622    }\r
 623 \r
 624    //! <b>Effects</b>: Erases the range pointed to by b end e. \r
 625    //! \r
 626    //! <b>Complexity</b>: Average complexity for erase range is at most \r
 627    //!   O(log(size() + N)), where N is the number of elements in the range.\r
 628    //! \r
 629    //! <b>Throws</b>: Nothing.\r
 630    //! \r
 631    //! <b>Note</b>: Invalidates the iterators (but not the references)\r
 632    //!    to the erased elements. No destructors are called.\r
 633    iterator erase(iterator b, iterator e)\r
 634    {  size_type n;   return private_erase(b, e, n);   }\r
 635 \r
 636    //! <b>Effects</b>: Erases all the elements with the given value.\r
 637    //! \r
 638    //! <b>Returns</b>: The number of erased elements.\r
 639    //! \r
 640    //! <b>Complexity</b>: O(log(size() + N).\r
 641    //! \r
 642    //! <b>Throws</b>: Nothing.\r
 643    //! \r
 644    //! <b>Note</b>: Invalidates the iterators (but not the references)\r
 645    //!    to the erased elements. No destructors are called.\r
 646    size_type erase(const value_type &value)\r
 647    {  return this->erase(value, priv_comp());   }\r
 648 \r
 649    //! <b>Effects</b>: Erases all the elements with the given key.\r
 650    //!   according to the comparison functor "comp".\r
 651    //!\r
 652    //! <b>Returns</b>: The number of erased elements.\r
 653    //! \r
 654    //! <b>Complexity</b>: O(log(size() + N).\r
 655    //! \r
 656    //! <b>Throws</b>: Nothing.\r
 657    //! \r
 658    //! <b>Note</b>: Invalidates the iterators (but not the references)\r
 659    //!    to the erased elements. No destructors are called.\r
 660    template<class KeyType, class KeyValueCompare>\r
 661    size_type erase(const KeyType& key, KeyValueCompare comp)\r
 662    {\r
 663       std::pair<iterator,iterator> p = this->equal_range(key, comp);\r
 664       size_type n;\r
 665       private_erase(p.first, p.second, n);\r
 666       return n;\r
 667    }\r
 668 \r
 669    //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
 670    //!\r
 671    //! <b>Effects</b>: Erases the element pointed to by pos. \r
 672    //!   Destroyer::operator()(pointer) is called for the removed element.\r
 673    //! \r
 674    //! <b>Complexity</b>: Average complexity for erase element is constant time. \r
 675    //! \r
 676    //! <b>Throws</b>: Nothing.\r
 677    //! \r
 678    //! <b>Note</b>: Invalidates the iterators \r
 679    //!    to the erased elements.\r
 680    template<class Destroyer>\r
 681    iterator erase_and_destroy(iterator i, Destroyer destroyer)\r
 682    {\r
 683       node_ptr to_erase(i.tree_node());\r
 684       iterator ret(this->erase(i));\r
 685       destroyer(ValueTraits::to_value_ptr(to_erase));\r
 686       return ret;\r
 687    }\r
 688 \r
 689    //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
 690    //!\r
 691    //! <b>Effects</b>: Erases the range pointed to by b end e.\r
 692    //!   Destroyer::operator()(pointer) is called for the removed elements.\r
 693    //! \r
 694    //! <b>Complexity</b>: Average complexity for erase range is at most \r
 695    //!   O(log(size() + N)), where N is the number of elements in the range.\r
 696    //! \r
 697    //! <b>Throws</b>: Nothing.\r
 698    //! \r
 699    //! <b>Note</b>: Invalidates the iterators\r
 700    //!    to the erased elements.\r
 701    template<class Destroyer>\r
 702    iterator erase_and_destroy(iterator b, iterator e, Destroyer destroyer)\r
 703    {  size_type n;   return private_erase(b, e, n, destroyer);   }\r
 704 \r
 705    //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
 706    //!\r
 707    //! <b>Effects</b>: Erases all the elements with the given value.\r
 708    //!   Destroyer::operator()(pointer) is called for the removed elements.\r
 709    //! \r
 710    //! <b>Returns</b>: The number of erased elements.\r
 711    //! \r
 712    //! <b>Complexity</b>: O(log(size() + N).\r
 713    //! \r
 714    //! <b>Throws</b>: Nothing.\r
 715    //! \r
 716    //! <b>Note</b>: Invalidates the iterators (but not the references)\r
 717    //!    to the erased elements. No destructors are called.\r
 718    template<class Destroyer>\r
 719    size_type erase_and_destroy(const value_type &value, Destroyer destroyer)\r
 720    {\r
 721       std::pair<iterator,iterator> p = this->equal_range(value);\r
 722       size_type n;\r
 723       private_erase(p.first, p.second, n, destroyer);\r
 724       return n;\r
 725    }\r
 726 \r
 727    //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
 728    //!\r
 729    //! <b>Effects</b>: Erases all the elements with the given key.\r
 730    //!   according to the comparison functor "comp".\r
 731    //!   Destroyer::operator()(pointer) is called for the removed elements.\r
 732    //!\r
 733    //! <b>Returns</b>: The number of erased elements.\r
 734    //! \r
 735    //! <b>Complexity</b>: O(log(size() + N).\r
 736    //! \r
 737    //! <b>Throws</b>: Nothing.\r
 738    //! \r
 739    //! <b>Note</b>: Invalidates the iterators\r
 740    //!    to the erased elements.\r
 741    template<class KeyType, class KeyValueCompare, class Destroyer>\r
 742    size_type erase_and_destroy(const KeyType& key, KeyValueCompare comp, Destroyer destroyer)\r
 743    {\r
 744       std::pair<iterator,iterator> p = this->equal_range(key, comp);\r
 745       size_type n;\r
 746       private_erase(p.first, p.second, n, destroyer);\r
 747       return n;\r
 748    }\r
 749 \r
 750    //! <b>Effects</b>: Erases all of the elements. \r
 751    //! \r
 752    //! <b>Complexity</b>: Linear to the number of elements on the container.\r
 753    //!   if it's a safe-mode or auto-unlink value_type. Constant time otherwise.\r
 754    //! \r
 755    //! <b>Throws</b>: Nothing.\r
 756    //! \r
 757    //! <b>Note</b>: Invalidates the iterators (but not the references)\r
 758    //!    to the erased elements. No destructors are called.\r
 759    void clear()\r
 760    {\r
 761       if(safemode_or_autounlink){\r
 762          while(1){\r
 763             node_ptr leftmost\r
 764                (node_algorithms::unlink_leftmost_without_rebalance\r
 765                   (node_ptr(&priv_header())));\r
 766             if(!leftmost)\r
 767                break;\r
 768             size_traits::decrement();\r
 769             if(safemode_or_autounlink)\r
 770                node_algorithms::init(leftmost);\r
 771          }\r
 772       }\r
 773       else{\r
 774          node_algorithms::init_header(&priv_header());\r
 775          size_traits::set_size(0);\r
 776       }\r
 777    }\r
 778 \r
 779    //! <b>Effects</b>: Erases all of the elements calling destroyer(p) for\r
 780    //!   each node to be erased.\r
 781    //! <b>Complexity</b>: Average complexity for is at most O(log(size() + N)),\r
 782    //!   where N is the number of elements in the container.\r
 783    //! \r
 784    //! <b>Throws</b>: Nothing.\r
 785    //! \r
 786    //! <b>Note</b>: Invalidates the iterators (but not the references)\r
 787    //!    to the erased elements. Calls N times to destroyer functor.\r
 788    template<class Destroyer>\r
 789    void clear_and_destroy(Destroyer destroyer)\r
 790    {\r
 791       while(1){\r
 792          node_ptr leftmost\r
 793             (node_algorithms::unlink_leftmost_without_rebalance\r
 794                (node_ptr(&priv_header())));\r
 795          if(!leftmost)\r
 796             break;\r
 797          size_traits::decrement();\r
 798          if(safemode_or_autounlink)\r
 799             node_algorithms::init(leftmost);\r
 800          destroyer(ValueTraits::to_value_ptr(leftmost));\r
 801       }\r
 802    }\r
 803 \r
 804    //! <b>Effects</b>: Returns the number of contained elements with the given value\r
 805    //! \r
 806    //! <b>Complexity</b>: Logarithmic to the number of elements contained plus lineal\r
 807    //!   to number of objects with the given value.\r
 808    //! \r
 809    //! <b>Throws</b>: Nothing.\r
 810    size_type count(const value_type &value) const\r
 811    {  return this->count(value, priv_comp());   }\r
 812 \r
 813    //! <b>Effects</b>: Returns the number of contained elements with the given key\r
 814    //! \r
 815    //! <b>Complexity</b>: Logarithmic to the number of elements contained plus lineal\r
 816    //!   to number of objects with the given key.\r
 817    //! \r
 818    //! <b>Throws</b>: Nothing.\r
 819    template<class KeyType, class KeyValueCompare>\r
 820    size_type count(const KeyType &key, KeyValueCompare comp) const\r
 821    {\r
 822       std::pair<const_iterator, const_iterator> ret = this->equal_range(key, comp);\r
 823       return std::distance(ret.first, ret.second);\r
 824    }\r
 825 \r
 826    //! <b>Effects</b>: Returns an iterator to the first element whose\r
 827    //!   key is not less than k or end() if that element does not exist.\r
 828    //! \r
 829    //! <b>Complexity</b>: Logarithmic.\r
 830    //! \r
 831    //! <b>Throws</b>: Nothing.\r
 832    iterator lower_bound(const value_type &value)\r
 833    {  return this->lower_bound(value, priv_comp());   }\r
 834 \r
 835    //! <b>Effects</b>: Returns an iterator to the first element whose\r
 836    //!   key is not less than k or end() if that element does not exist.\r
 837    //! \r
 838    //! <b>Complexity</b>: Logarithmic.\r
 839    //! \r
 840    //! <b>Throws</b>: Nothing.\r
 841    const_iterator lower_bound(const value_type &value) const\r
 842    {  return this->lower_bound(value, priv_comp());   }\r
 843 \r
 844    //! <b>Effects</b>: Returns an iterator to the first element whose\r
 845    //!   key is not less than k or end() if that element does not exist.\r
 846    //! \r
 847    //! <b>Complexity</b>: Logarithmic.\r
 848    //! \r
 849    //! <b>Throws</b>: Nothing.\r
 850    template<class KeyType, class KeyValueCompare>\r
 851    iterator lower_bound(const KeyType &key, KeyValueCompare comp)\r
 852    {\r
 853       key_node_ptr_compare<KeyValueCompare> key_node_comp(comp);\r
 854       return iterator(node_algorithms::lower_bound\r
 855          (const_node_ptr(&priv_header()), key, key_node_comp));\r
 856    }\r
 857 \r
 858    //! <b>Effects</b>: Returns a const iterator to the first element whose\r
 859    //!   key is not less than k or end() if that element does not exist.\r
 860    //! \r
 861    //! <b>Complexity</b>: Logarithmic.\r
 862    //! \r
 863    //! <b>Throws</b>: Nothing.\r
 864    template<class KeyType, class KeyValueCompare>\r
 865    const_iterator lower_bound(const KeyType &key, KeyValueCompare comp) const\r
 866    {\r
 867       key_node_ptr_compare<KeyValueCompare> key_node_comp(comp);\r
 868       return const_iterator(node_algorithms::lower_bound\r
 869          (const_node_ptr(&priv_header()), key, key_node_comp));\r
 870    }\r
 871 \r
 872    //! <b>Effects</b>: Returns an iterator to the first element whose\r
 873    //!   key is greater than k or end() if that element does not exist.\r
 874    //! \r
 875    //! <b>Complexity</b>: Logarithmic.\r
 876    //! \r
 877    //! <b>Throws</b>: Nothing.\r
 878    iterator upper_bound(const value_type &value)\r
 879    {  return this->upper_bound(value, priv_comp());   }\r
 880 \r
 881    //! <b>Effects</b>: Returns an iterator to the first element whose\r
 882    //!   key is greater than k according to comp or end() if that element\r
 883    //!   does not exist.\r
 884    //!\r
 885    //! <b>Complexity</b>: Logarithmic.\r
 886    //! \r
 887    //! <b>Throws</b>: Nothing.\r
 888    template<class KeyType, class KeyValueCompare>\r
 889    iterator upper_bound(const KeyType &key, KeyValueCompare comp)\r
 890    {\r
 891       key_node_ptr_compare<KeyValueCompare> key_node_comp(comp);\r
 892       return iterator(node_algorithms::upper_bound\r
 893          (const_node_ptr(&priv_header()), key, key_node_comp));\r
 894    }\r
 895 \r
 896    //! <b>Effects</b>: Returns an iterator to the first element whose\r
 897    //!   key is greater than k or end() if that element does not exist.\r
 898    //! \r
 899    //! <b>Complexity</b>: Logarithmic.\r
 900    //! \r
 901    //! <b>Throws</b>: Nothing.\r
 902    const_iterator upper_bound(const value_type &value) const\r
 903    {  return this->upper_bound(value, priv_comp());   }\r
 904 \r
 905    //! <b>Effects</b>: Returns an iterator to the first element whose\r
 906    //!   key is greater than k according to comp or end() if that element\r
 907    //!   does not exist.\r
 908    //!\r
 909    //! <b>Complexity</b>: Logarithmic.\r
 910    //! \r
 911    //! <b>Throws</b>: Nothing.\r
 912    template<class KeyType, class KeyValueCompare>\r
 913    const_iterator upper_bound(const KeyType &key, KeyValueCompare comp) const\r
 914    {\r
 915       key_node_ptr_compare<KeyValueCompare> key_node_comp(comp);\r
 916       return const_iterator(node_algorithms::upper_bound\r
 917          (const_node_ptr(&priv_header()), key, key_node_comp));\r
 918    }\r
 919 \r
 920    //! <b>Effects</b>: Finds an iterator to the first element whose key is \r
 921    //!   k or end() if that element does not exist.\r
 922    //!\r
 923    //! <b>Complexity</b>: Logarithmic.\r
 924    //! \r
 925    //! <b>Throws</b>: Nothing.\r
 926    iterator find(const value_type &value)\r
 927    {  return this->find(value, priv_comp()); }\r
 928 \r
 929    //! <b>Effects</b>: Finds an iterator to the first element whose key is \r
 930    //!   k or end() if that element does not exist.\r
 931    //!\r
 932    //! <b>Complexity</b>: Logarithmic.\r
 933    //! \r
 934    //! <b>Throws</b>: Nothing.\r
 935    template<class KeyType, class KeyValueCompare>\r
 936    iterator find(const KeyType &key, KeyValueCompare comp)\r
 937    {\r
 938       key_node_ptr_compare<KeyValueCompare> key_node_comp(comp);\r
 939       return iterator\r
 940          (node_algorithms::find(const_node_ptr(&priv_header()), key, key_node_comp));\r
 941    }\r
 942 \r
 943    //! <b>Effects</b>: Finds a const_iterator to the first element whose key is \r
 944    //!   k or end() if that element does not exist.\r
 945    //! \r
 946    //! <b>Complexity</b>: Logarithmic.\r
 947    //! \r
 948    //! <b>Throws</b>: Nothing.\r
 949    const_iterator find(const value_type &value) const\r
 950    {  return this->find(value, priv_comp()); }\r
 951 \r
 952    //! <b>Effects</b>: Finds a const_iterator to the first element whose key is \r
 953    //!   k or end() if that element does not exist.\r
 954    //! \r
 955    //! <b>Complexity</b>: Logarithmic.\r
 956    //! \r
 957    //! <b>Throws</b>: Nothing.\r
 958    template<class KeyType, class KeyValueCompare>\r
 959    const_iterator find(const KeyType &key, KeyValueCompare comp) const\r
 960    {\r
 961       key_node_ptr_compare<KeyValueCompare> key_node_comp(comp);\r
 962       return const_iterator\r
 963          (node_algorithms::find(const_node_ptr(&priv_header()), key, key_node_comp));\r
 964    }\r
 965 \r
 966    //! <b>Effects</b>: Finds a range containing all elements whose key is k or\r
 967    //!   an empty range that indicates the position where those elements would be\r
 968    //!   if they there is no elements with key k.\r
 969    //! \r
 970    //! <b>Complexity</b>: Logarithmic.\r
 971    //! \r
 972    //! <b>Throws</b>: Nothing.\r
 973    std::pair<iterator,iterator> equal_range(const value_type &value)\r
 974    {  return this->equal_range(value, priv_comp());   }\r
 975 \r
 976    //! <b>Effects</b>: Finds a range containing all elements whose key is k or\r
 977    //!   an empty range that indicates the position where those elements would be\r
 978    //!   if they there is no elements with key k.\r
 979    //! \r
 980    //! <b>Complexity</b>: Logarithmic.\r
 981    //! \r
 982    //! <b>Throws</b>: Nothing.\r
 983    template<class KeyType, class KeyValueCompare>\r
 984    std::pair<iterator,iterator> equal_range(const KeyType &key, KeyValueCompare comp)\r
 985    {\r
 986       key_node_ptr_compare<KeyValueCompare> key_node_comp(comp);\r
 987       std::pair<node_ptr, node_ptr> ret\r
 988          (node_algorithms::equal_range(const_node_ptr(&priv_header()), key, key_node_comp));\r
 989       return std::pair<iterator, iterator>(iterator(ret.first), iterator(ret.second));\r
 990    }\r
 991 \r
 992    //! <b>Effects</b>: Finds a range containing all elements whose key is k or\r
 993    //!   an empty range that indicates the position where those elements would be\r
 994    //!   if they there is no elements with key k.\r
 995    //! \r
 996    //! <b>Complexity</b>: Logarithmic.\r
 997    //! \r
 998    //! <b>Throws</b>: Nothing.\r
 999    std::pair<const_iterator, const_iterator>\r
1000       equal_range(const value_type &value) const\r
1001    {  return this->equal_range(value, priv_comp());   }\r
1002 \r
1003    //! <b>Effects</b>: Finds a range containing all elements whose key is k or\r
1004    //!   an empty range that indicates the position where those elements would be\r
1005    //!   if they there is no elements with key k.\r
1006    //! \r
1007    //! <b>Complexity</b>: Logarithmic.\r
1008    //! \r
1009    //! <b>Throws</b>: Nothing.\r
1010    template<class KeyType, class KeyValueCompare>\r
1011    std::pair<const_iterator, const_iterator>\r
1012       equal_range(const KeyType &key, KeyValueCompare comp) const\r
1013    {\r
1014       key_node_ptr_compare<KeyValueCompare> key_node_comp(comp);\r
1015       std::pair<node_ptr, node_ptr> ret\r
1016          (node_algorithms::equal_range(const_node_ptr(&priv_header()), key, key_node_comp));\r
1017       return std::pair<const_iterator, const_iterator>(const_iterator(ret.first), const_iterator(ret.second));\r
1018    }\r
1019 \r
1020    template <class Cloner, class Destroyer>\r
1021    void clone_from(const irbtree &src, Cloner cloner, Destroyer destroyer)\r
1022    {\r
1023       this->clear_and_destroy(destroyer);\r
1024       if(!src.empty()){\r
1025          node_algorithms::clone_tree\r
1026             (const_node_ptr(&src.priv_header())\r
1027             ,node_ptr(&this->priv_header())\r
1028             ,value_to_node_cloner<Cloner>(cloner)\r
1029             ,value_to_node_destroyer<Destroyer>(destroyer));\r
1030          size_traits::set_size(src.get_size());\r
1031       }\r
1032    }\r
1033 \r
1034    pointer unlink_leftmost_without_rebalance()\r
1035    {\r
1036       node_ptr to_destroy(node_algorithms::unlink_leftmost_without_rebalance\r
1037                            (node_ptr(&priv_header())));\r
1038       if(!to_destroy)\r
1039          return 0;\r
1040       size_traits::decrement();\r
1041       if(safemode_or_autounlink)\r
1042          node_algorithms::init(to_destroy);\r
1043       return ValueTraits::to_value_ptr(to_destroy);\r
1044    }\r
1045 \r
1046    //! <b>Requires</b>: value must be an lvalue and shall be in a set of\r
1047    //!   appropriate type. Otherwise the behavior is undefined.\r
1048    //! \r
1049    //! <b>Effects</b>: Returns: a valid iterator i belonging to the set\r
1050    //!   that points to the value\r
1051    //! \r
1052    //! <b>Complexity</b>: Constant.\r
1053    //! \r
1054    //! <b>Throws</b>: Nothing.\r
1055    static iterator current(value_type &value)\r
1056    {  return iterator (ValueTraits::to_node_ptr(value));  }\r
1057 \r
1058    //! <b>Requires</b>: value must be an lvalue and shall be in a set of\r
1059    //!   appropriate type. Otherwise the behavior is undefined.\r
1060    //! \r
1061    //! <b>Effects</b>: Returns: a valid const_iterator i belonging to the\r
1062    //!   set that points to the value\r
1063    //! \r
1064    //! <b>Complexity</b>: Constant.\r
1065    //! \r
1066    //! <b>Throws</b>: Nothing.\r
1067    static const_iterator current(const value_type &value) \r
1068    {  return const_iterator (ValueTraits::to_node_ptr(const_cast<value_type&> (value))); }\r
1069 /*\r
1070    //! <b>Requires</b>: value shall not be in a tree of the appropriate type.\r
1071    //! \r
1072    //! <b>Effects</b>: init_node post-constructs the node data in x used by multisets of \r
1073    //! the appropriate type. For the accessors multiset_derived_node and multiset_member_node \r
1074    //! init_node has no effect, since the constructors of multiset_node_d and multiset_node_m \r
1075    //! have already initialized the node data. \r
1076    //! \r
1077    //! <b>Throws</b>: Nothing.\r
1078    //! \r
1079    //! <b>Complexity</b>: Constant time.\r
1080    //! \r
1081    //! <b>Note</b>: This function is meant to be used mainly with the member value_traits, \r
1082    //! where no implicit node initialization during construction occurs.\r
1083    static void init_node(reference value)\r
1084    { node_algorithms::init(node_ptr(&*ValueTraits::to_node_ptr(value))); }\r
1085 \r
1086    //! <b>Effects</b>: removes x from a tree of the appropriate type. It has no effect,\r
1087    //! if x is not in such a tree. \r
1088    //! \r
1089    //! <b>Throws</b>: Nothing.\r
1090    //! \r
1091    //! <b>Complexity</b>: Constant time.\r
1092    //! \r
1093    //! <b>Note</b>: This static function is only usable with the "safe mode"\r
1094    //! hook and non-constant time size lists. Otherwise, the user must use\r
1095    //! the non-static "erase(value_type &)" member. If the user calls\r
1096    //! this function with a non "safe mode" or constant time size list\r
1097    //! a compilation error will be issued.\r
1098    template<class T>\r
1099    static void remove_node(T& value)\r
1100    {\r
1101       //This function is only usable for safe mode hooks and non-constant\r
1102       //time lists. \r
1103       //BOOST_STATIC_ASSERT((!(safemode_or_autounlink && ConstantTimeSize)));\r
1104       BOOST_STATIC_ASSERT((!ConstantTimeSize));\r
1105       BOOST_STATIC_ASSERT((boost::is_convertible<T, value_type>::value));\r
1106       node_ptr to_remove(ValueTraits::to_node_ptr(value));\r
1107       node_algorithms::unlink_and_rebalance(to_remove);\r
1108       if(safemode_or_autounlink)\r
1109          node_algorithms::init(to_remove);\r
1110    }\r
1111 */\r
1112    private:\r
1113    template<class Destroyer>\r
1114    iterator private_erase(iterator b, iterator e, size_type &n, Destroyer destroyer)\r
1115    {\r
1116       for(n = 0; b != e; ++n)\r
1117         this->erase_and_destroy(b++, destroyer);\r
1118       return b;\r
1119    }\r
1120 \r
1121    iterator private_erase(iterator b, iterator e, size_type &n)\r
1122    {\r
1123       for(n = 0; b != e; ++n)\r
1124         this->erase(b++);\r
1125       return b;\r
1126    }\r
1127 };\r
1128 \r
1129 template <class V, class P, bool C, class S>\r
1130 inline bool operator==(const irbtree<V, P, C, S>& x, const irbtree<V, P, C, S>& y)\r
1131 {\r
1132    if(C && x.size() != y.size()){\r
1133       return false;\r
1134    }\r
1135    typedef typename irbtree<V, P, C, S>::const_iterator const_iterator;\r
1136    const_iterator end1 = x.end();\r
1137 \r
1138    const_iterator i1 = x.begin();\r
1139    const_iterator i2 = y.begin();\r
1140    if(C){\r
1141       while (i1 != end1 && *i1 == *i2) {\r
1142          ++i1;\r
1143          ++i2;\r
1144       }\r
1145       return i1 == end1;\r
1146    }\r
1147    else{\r
1148       const_iterator end2 = y.end();\r
1149       while (i1 != end1 && i2 != end2 && *i1 == *i2) {\r
1150          ++i1;\r
1151          ++i2;\r
1152       }\r
1153       return i1 == end1 && i2 == end2;\r
1154    }\r
1155 }\r
1156 \r
1157 template <class V, class P, bool C, class S>\r
1158 inline bool operator<(const irbtree<V, P, C, S>& x,\r
1159                       const irbtree<V, P, C, S>& y)\r
1160 {  return std::lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());  }\r
1161 \r
1162 template <class V, class P, bool C, class S>\r
1163 inline bool operator!=(const irbtree<V, P, C, S>& x, const irbtree<V, P, C, S>& y) \r
1164 {  return !(x == y); }\r
1165 \r
1166 template <class V, class P, bool C, class S>\r
1167 inline bool operator>(const irbtree<V, P, C, S>& x, const irbtree<V, P, C, S>& y) \r
1168 {  return y < x;  }\r
1169 \r
1170 template <class V, class P, bool C, class S>\r
1171 inline bool operator<=(const irbtree<V, P, C, S>& x, const irbtree<V, P, C, S>& y) \r
1172 {  return !(y < x);  }\r
1173 \r
1174 template <class V, class P, bool C, class S>\r
1175 inline bool operator>=(const irbtree<V, P, C, S>& x, const irbtree<V, P, C, S>& y) \r
1176 {  return !(x < y);  }\r
1177 \r
1178 template <class V, class P, bool C, class S>\r
1179 inline void swap(irbtree<V, P, C, S>& x, irbtree<V, P, C, S>& y)\r
1180 {  x.swap(y);  }\r
1181 \r
1182 } //namespace detail\r
1183 } //namespace intrusive \r
1184 } //namespace boost \r
1185 \r
1186 #include <boost/intrusive/detail/config_end.hpp>\r
1187 \r
1188 #endif //BOOST_INTRUSIVE_IRBTREE_HPP\r