boost/intrusive/islist.hpp

   1 /////////////////////////////////////////////////////////////////////////////\r
   2 //\r
   3 // (C) Copyright Olaf Krzikalla 2004-2006.\r
   4 // (C) Copyright Ion Gaztañaga  2006-2007\r
   5 //\r
   6 // Distributed under the Boost Software License, Version 1.0.\r
   7 //    (See accompanying file LICENSE_1_0.txt or copy at\r
   8 //          http://www.boost.org/LICENSE_1_0.txt)\r
   9 //\r
  10 // See http://www.boost.org/libs/intrusive for documentation.\r
  11 //\r
  12 /////////////////////////////////////////////////////////////////////////////\r
  13 \r
  14 #ifndef BOOST_INTRUSIVE_ISLIST_HPP\r
  15 #define BOOST_INTRUSIVE_ISLIST_HPP\r
  16 \r
  17 #include <boost/intrusive/detail/config_begin.hpp>\r
  18 #include <boost/utility.hpp>\r
  19 #include <boost/static_assert.hpp>\r
  20 #include <boost/assert.hpp>\r
  21 #include <boost/type_traits/is_convertible.hpp>\r
  22 #include <boost/intrusive/islist_hook.hpp>\r
  23 #include <boost/intrusive/slist_algorithms.hpp>\r
  24 #include <boost/intrusive/detail/pointer_type.hpp>\r
  25 #include <boost/intrusive/detail/pointer_to_other.hpp>\r
  26 #include <boost/intrusive/linking_policy.hpp>\r
  27 #include <iterator>\r
  28 #include <cstddef>\r
  29 \r
  30 namespace boost {\r
  31 namespace intrusive {\r
  32 \r
  33 //! The class template islist is an intrusive container, that encapsulates \r
  34 //! a singly-linked list. You can use such a list to squeeze the last bit \r
  35 //! of performance from your application. Unfortunately, the little gains \r
  36 //! come with some huge drawbacks. A lot of member functions can't be \r
  37 //! implemented as efficiently as for standard containers. To overcome \r
  38 //! this limitation some other member functions with rather unusual semantics \r
  39 //! have to be introduced.\r
  40 //!\r
  41 //! The template parameter ValueTraits is called "value traits". It stores\r
  42 //! information and operations about the type to be stored in the container.\r
  43 //!\r
  44 //! If the user specifies ConstantTimeSize as "true", a member of type SizeType\r
  45 //! will be embedded in the class, that will keep track of the number of stored objects.\r
  46 //! This will allow constant-time O(1) size() member, instead of default O(N) size.\r
  47 //! \r
  48 //! The iterators of islist are forward iterators. islist provides a static \r
  49 //! function called "previous" to compute the previous iterator of a given iterator. \r
  50 //! This function has linear complexity. To improve the usability esp. with \r
  51 //! the '*_after' functions, ++end() == begin() and previous(begin()) == end() \r
  52 //! are defined. In addition, whenever you have an end iterator, 'after this \r
  53 //! iterator' means 'at the beginning of the list'. To improve the self-documentation\r
  54 //! a "before_begin()" function is defined, returning the end() iterator.\r
  55 template < class ValueTraits\r
  56          , bool ConstantTimeSize = true\r
  57          , class SizeType        = std::size_t>\r
  58 class islist\r
  59    :  private detail::size_holder<ConstantTimeSize, SizeType>\r
  60 {\r
  61    private:\r
  62    typedef islist<ValueTraits, ConstantTimeSize, SizeType>  this_type; \r
  63    typedef typename ValueTraits::node_traits                node_traits;\r
  64    typedef detail::size_holder<ConstantTimeSize, SizeType>  size_traits;\r
  65 \r
  66    //! This class is\r
  67    //! non-copyable\r
  68    islist (const islist&);\r
  69 \r
  70    //! This class is\r
  71    //! non-asignable\r
  72    islist &operator =(const islist&);\r
  73 \r
  74    //Public typedefs\r
  75    public:\r
  76    typedef typename ValueTraits::value_type        value_type;\r
  77    typedef typename ValueTraits::pointer           pointer;\r
  78    typedef typename ValueTraits::const_pointer     const_pointer;\r
  79    typedef value_type&                             reference;\r
  80    typedef const value_type&                       const_reference;\r
  81    typedef SizeType                                size_type;\r
  82    typedef typename std::iterator_traits\r
  83       <pointer>::difference_type                   difference_type;\r
  84 \r
  85    class iterator;\r
  86    class const_iterator;\r
  87    friend class iterator;\r
  88    friend class const_iterator;\r
  89 \r
  90    private:\r
  91    typedef typename node_traits::node              node;\r
  92    typedef typename boost::pointer_to_other\r
  93       <pointer, node>::type                        node_ptr;\r
  94    typedef typename boost::pointer_to_other\r
  95       <pointer, const node>::type                  const_node_ptr;\r
  96    typedef slist_algorithms<node_traits>  node_algorithms;\r
  97    enum { safemode_or_autounlink  = \r
  98             (int)ValueTraits::linking_policy == (int)auto_unlink   ||\r
  99             (int)ValueTraits::linking_policy == (int)safe_mode_link     };\r
 100 \r
 101    //Constant-time size is incompatible with auto-unlink hooks!\r
 102    BOOST_STATIC_ASSERT(!(ConstantTimeSize && ((int)ValueTraits::linking_policy == (int)auto_unlink)));\r
 103 \r
 104    node root;\r
 105 \r
 106    node_ptr get_root_node()\r
 107    {  return node_ptr(&root);  }\r
 108 \r
 109    const_node_ptr get_root_node() const\r
 110    {  return const_node_ptr(&root);  }\r
 111 \r
 112    static node_ptr uncast(const_node_ptr ptr)\r
 113    {\r
 114       using boost::get_pointer;\r
 115       return node_ptr(const_cast<node*>(get_pointer(ptr)));\r
 116    }\r
 117 \r
 118    static iterator previous_node(iterator beg, iterator i)\r
 119    {\r
 120       return iterator\r
 121          (node_algorithms::get_previous_node(beg.list_node(), i.list_node()));\r
 122    }\r
 123 \r
 124    static const_iterator previous_node(const_iterator beg, const_iterator i)\r
 125    {\r
 126       return const_iterator\r
 127          (node_algorithms::get_previous_node(beg.list_node(), i.list_node()));\r
 128    }\r
 129 \r
 130    //This functor compares a stored value\r
 131    //and the one passed as an argument\r
 132    class equal_to_value\r
 133    {\r
 134       const value_type &t_;\r
 135 \r
 136       public:\r
 137       equal_to_value(const value_type &t)\r
 138          :  t_(t)\r
 139       {}\r
 140 \r
 141       bool operator()(const value_type &t)const\r
 142       {  return t_ == t;   }\r
 143    };\r
 144 \r
 145    public:\r
 146 \r
 147    //!The forward iterator of the container\r
 148    class iterator\r
 149       :  public detail::slist_iterator<value_type, iterator, node_traits>\r
 150    {\r
 151       private:\r
 152       // gcc warns about an ambiguity between iterator::value_type and\r
 153       // islist<ValueTraits>::value_type, thus I introduce a unique name:\r
 154       typedef typename islist<ValueTraits, ConstantTimeSize, SizeType>::value_type private_vt;\r
 155       typedef typename islist<ValueTraits, ConstantTimeSize, SizeType>::pointer    private_pointer;\r
 156       typedef typename islist<ValueTraits, ConstantTimeSize, SizeType>::reference  private_reference;\r
 157       typedef detail::slist_iterator<private_vt, iterator, node_traits>  inherited;\r
 158 \r
 159       public:\r
 160       iterator ()\r
 161       {}\r
 162 \r
 163       private_pointer     operator->() const\r
 164       { return  ValueTraits::to_value_ptr(this->list_node()); }\r
 165 \r
 166       private_reference   operator*() const\r
 167       { return *ValueTraits::to_value_ptr(this->list_node()); }\r
 168 \r
 169       node_ptr list_node()const\r
 170       {  return inherited::list_node();   }\r
 171 \r
 172       private:\r
 173       explicit iterator (node_ptr node)\r
 174          :  inherited (node)\r
 175       {}\r
 176 \r
 177       friend class islist<ValueTraits, ConstantTimeSize, SizeType>;\r
 178       friend class detail::slist_iterator<private_vt, iterator, node_traits>;\r
 179       friend class const_iterator;\r
 180    };\r
 181 \r
 182    //!The forward const_iterator of the container\r
 183    class const_iterator\r
 184       :  public detail::slist_iterator<const value_type, const_iterator, node_traits>\r
 185    {\r
 186       private:\r
 187       typedef const typename islist<ValueTraits, ConstantTimeSize, SizeType>::value_type private_vt;\r
 188       typedef typename islist<ValueTraits, ConstantTimeSize, SizeType>::const_pointer    private_pointer;\r
 189       typedef typename islist<ValueTraits, ConstantTimeSize, SizeType>::const_reference  private_reference;\r
 190       typedef detail::slist_iterator<private_vt, const_iterator, node_traits>  inherited;\r
 191       \r
 192       public: \r
 193       const_iterator()\r
 194       {}\r
 195 \r
 196       const_iterator(const typename islist::iterator& it)\r
 197          :  inherited (it.list_node())\r
 198       {}\r
 199 \r
 200       const_iterator & operator=(const typename islist::iterator& it)\r
 201       {  return inherited::operator=(it.list_node());  }\r
 202 \r
 203       private_pointer   operator->()\r
 204       { return  ValueTraits::to_value_ptr(this->list_node()); }\r
 205 \r
 206       private_reference operator*()\r
 207       { return *ValueTraits::to_value_ptr(this->list_node()); }\r
 208       \r
 209       private:\r
 210       explicit const_iterator (const_node_ptr node)\r
 211          :  inherited (uncast(node))\r
 212       {}\r
 213 \r
 214       friend class islist<ValueTraits, ConstantTimeSize, SizeType>;\r
 215       friend class detail::slist_iterator<private_vt, const_iterator, node_traits>;\r
 216    };\r
 217 \r
 218    public:\r
 219 \r
 220    //! <b>Effects</b>: constructs an empty list. \r
 221    //! \r
 222    //! <b>Complexity</b>: Constant \r
 223    //! \r
 224    //! <b>Throws</b>: If value_traits::node_traits::node\r
 225    //!   constructor throws (this does not happen with predefined Boost.Intrusive hooks).\r
 226    islist()\r
 227    {\r
 228       size_traits::set_size(size_type(0));\r
 229       node_algorithms::init(node_ptr(&root)); \r
 230    }\r
 231 \r
 232    //! <b>Requires</b>: Dereferencing iterator must yield an lvalue of type value_type.\r
 233    //! \r
 234    //! <b>Effects</b>: Constructs a list equal to [first,last).\r
 235    //! \r
 236    //! <b>Complexity</b>: Linear in std::distance(b, e). No copy constructors are called.  \r
 237    //! \r
 238    //! <b>Throws</b>: If value_traits::node_traits::node\r
 239    //!   constructor throws (this does not happen with predefined Boost.Intrusive hooks).\r
 240    template<class Iterator>\r
 241    islist(Iterator b, Iterator e)\r
 242    {\r
 243       size_traits::set_size(size_type(0));\r
 244       node_algorithms::init(node_ptr(&root));\r
 245       insert_after(before_begin(), b, e);\r
 246    }\r
 247 \r
 248    //! <b>Effects</b>: If it's a safe-mode\r
 249    //!   or auto-unlink value, the destructor does nothing\r
 250    //!   (ie. no code is generated). Otherwise it detaches all elements from this. \r
 251    //!   In this case the objects in the list are not deleted (i.e. no destructors \r
 252    //!   are called), but the hooks according to the ValueTraits template parameter\r
 253    //!   are set to their default value.\r
 254    //! \r
 255    //! <b>Complexity</b>: Linear to the number of elements in the list, if \r
 256    //!   it's a safe-mode or auto-unlink value. Otherwise constant.\r
 257    ~islist()\r
 258    {  this->clear(); }\r
 259 \r
 260    //! <b>Effects</b>: Erases all the elements of the container.\r
 261    //! \r
 262    //! <b>Throws</b>: Nothing.\r
 263    //! \r
 264    //! <b>Complexity</b>: Linear to the number of elements of the list.\r
 265    //!   if it's a safe-mode or auto-unlink value_type. Constant time otherwise.\r
 266    //! \r
 267    //! <b>Note</b>: Invalidates the iterators (but not the references) to the erased elements.\r
 268    void clear()\r
 269    {\r
 270       if(safemode_or_autounlink){\r
 271          this->erase_after(this->before_begin(), this->end()); \r
 272       }\r
 273       else{\r
 274          node_algorithms::init(node_ptr(&root));\r
 275          size_traits::set_size(size_type(0));\r
 276       }\r
 277    }\r
 278 \r
 279    //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
 280    //!\r
 281    //! <b>Effects</b>: Erases all the elements of the container\r
 282    //!   Destroyer::operator()(pointer) is called for the removed elements.\r
 283    //! \r
 284    //! <b>Throws</b>: Nothing.\r
 285    //! \r
 286    //! <b>Complexity</b>: Linear to the number of elements of the list.\r
 287    //! \r
 288    //! <b>Note</b>: Invalidates the iterators to the erased elements.\r
 289    template <class Destroyer>\r
 290    void clear_and_destroy(Destroyer destroyer)\r
 291    {  this->erase_after_and_destroy(this->before_begin(), this->end(), destroyer);   }\r
 292 \r
 293    //! <b>Requires</b>: value must be an lvalue.\r
 294    //! \r
 295    //! <b>Effects</b>: Inserts the value in the front of the list.\r
 296    //!   No copy constructors are called.\r
 297    //! \r
 298    //! <b>Throws</b>: Nothing.\r
 299    //! \r
 300    //! <b>Complexity</b>: Constant.\r
 301    //! \r
 302    //! <b>Note</b>: Does not affect the validity of iterators and references.\r
 303    void push_front(value_type &value) \r
 304    {\r
 305       node_ptr to_insert(ValueTraits::to_node_ptr(value));\r
 306       if(safemode_or_autounlink)\r
 307          BOOST_ASSERT(node_algorithms::unique(to_insert));\r
 308       node_algorithms::link_after(get_root_node(), to_insert); \r
 309       size_traits::increment();\r
 310    }\r
 311 \r
 312    //! <b>Effects</b>: Erases the first element of the list.\r
 313    //!   No destructors are called.\r
 314    //! \r
 315    //! <b>Throws</b>: Nothing.\r
 316    //! \r
 317    //! <b>Complexity</b>: Constant.\r
 318    //! \r
 319    //! <b>Note</b>: Invalidates the iterators (but not the references) to the erased element.\r
 320    void pop_front() \r
 321    {\r
 322       node_ptr to_erase = node_traits::get_next(get_root_node());\r
 323       node_algorithms::unlink_after(get_root_node());\r
 324       size_traits::decrement();\r
 325       if(safemode_or_autounlink)\r
 326          node_algorithms::init(to_erase);\r
 327    }\r
 328 \r
 329    //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
 330    //!\r
 331    //! <b>Effects</b>: Erases the first element of the list.\r
 332    //!   Destroyer::operator()(pointer) is called for the removed element.\r
 333    //! \r
 334    //! <b>Throws</b>: Nothing.\r
 335    //! \r
 336    //! <b>Complexity</b>: Constant.\r
 337    //! \r
 338    //! <b>Note</b>: Invalidates the iterators to the erased element.\r
 339    template<class Destroyer>\r
 340    void pop_front_and_destroy(Destroyer destroyer)\r
 341    {\r
 342       node_ptr to_erase = node_traits::get_next(get_root_node());\r
 343       this->pop_front();\r
 344       destroyer(ValueTraits::to_value_ptr(to_erase));\r
 345    }\r
 346 \r
 347    //! <b>Effects</b>: Returns a reference to the first element of the list.\r
 348    //! \r
 349    //! <b>Throws</b>: Nothing.\r
 350    //! \r
 351    //! <b>Complexity</b>: Constant.\r
 352    reference front()\r
 353    { return *ValueTraits::to_value_ptr(node_traits::get_next(get_root_node())); }\r
 354 \r
 355    //! <b>Effects</b>: Returns a const_reference to the first element of the list.\r
 356    //! \r
 357    //! <b>Throws</b>: Nothing.\r
 358    //! \r
 359    //! <b>Complexity</b>: Constant.\r
 360    const_reference front() const\r
 361    { return *ValueTraits::to_value_ptr(uncast(node_traits::get_next(const_node_ptr(&root)))); }\r
 362 \r
 363    //! <b>Effects</b>: Returns an iterator to the first element contained in the list.\r
 364    //! \r
 365    //! <b>Throws</b>: Nothing.\r
 366    //! \r
 367    //! <b>Complexity</b>: Constant.\r
 368    iterator begin() \r
 369    { return iterator (node_traits::get_next(get_root_node())); }\r
 370 \r
 371    //! <b>Effects</b>: Returns a const_iterator to the first element contained in the list.\r
 372    //! \r
 373    //! <b>Throws</b>: Nothing.\r
 374    //! \r
 375    //! <b>Complexity</b>: Constant.\r
 376    const_iterator begin() const \r
 377    { return const_iterator (node_traits::get_next(get_root_node())); }\r
 378 \r
 379    //! <b>Effects</b>: Returns an iterator to the end of the list.\r
 380    //! \r
 381    //! <b>Throws</b>: Nothing.\r
 382    //! \r
 383    //! <b>Complexity</b>: Constant.\r
 384    iterator end() \r
 385    { return iterator (get_root_node()); }\r
 386 \r
 387    //! <b>Effects</b>: Returns a const_iterator to the end of the list.\r
 388    //! \r
 389    //! <b>Throws</b>: Nothing.\r
 390    //! \r
 391    //! <b>Complexity</b>: Constant.\r
 392    const_iterator end() const \r
 393    { return const_iterator (get_root_node()); }\r
 394 \r
 395    //! <b>Effects</b>: Returns an iterator that points to a position\r
 396    //!   before the first element. Equivalent to "end()"\r
 397    //! \r
 398    //! <b>Throws</b>: Nothing.\r
 399    //! \r
 400    //! <b>Complexity</b>: Constant.\r
 401    iterator before_begin() \r
 402    { return end(); }\r
 403 \r
 404    //! <b>Effects</b>: Returns an iterator that points to a position\r
 405    //!   before the first element. Equivalent to "end()"\r
 406    //! \r
 407    //! <b>Throws</b>: Nothing.\r
 408    //! \r
 409    //! <b>Complexity</b>: Constant.\r
 410    const_iterator before_begin() const \r
 411    { return end(); }\r
 412 \r
 413    //! <b>Effects</b>: Returns the number of the elements contained in the list.\r
 414    //! \r
 415    //! <b>Throws</b>: Nothing.\r
 416    //! \r
 417    //! <b>Complexity</b>: Linear to the number of elements contained in the list.\r
 418    //!   if ConstantTimeSize is false. Constant time otherwise.\r
 419    //! \r
 420    //! <b>Note</b>: Does not affect the validity of iterators and references.\r
 421    size_type size() const\r
 422    {\r
 423       if(ConstantTimeSize)\r
 424          return size_traits::get_size();\r
 425       else\r
 426          return node_algorithms::count(const_node_ptr(&root)) - 1; \r
 427    }\r
 428 \r
 429    //! <b>Effects</b>: Returns true if the list contains no elements.\r
 430    //! \r
 431    //! <b>Throws</b>: Nothing.\r
 432    //! \r
 433    //! <b>Complexity</b>: Constant.\r
 434    //! \r
 435    //! <b>Note</b>: Does not affect the validity of iterators and references.\r
 436    bool empty() const\r
 437    { return node_algorithms::unique(get_root_node()); }\r
 438 \r
 439    //! <b>Effects</b>: Swaps the elements of x and *this.\r
 440    //! \r
 441    //! <b>Throws</b>: Nothing.\r
 442    //! \r
 443    //! <b>Complexity</b>: Linear to the number of elements of both lists.\r
 444    //! \r
 445    //! <b>Note</b>: Does not affect the validity of iterators and references.\r
 446    void swap(islist& other)\r
 447    {\r
 448       node_algorithms::swap_nodes(get_root_node(), &other.root);\r
 449       if(ConstantTimeSize){\r
 450          size_type backup = size_traits::get_size();\r
 451          size_traits::set_size(other.get_size());\r
 452          other.set_size(backup);\r
 453       }\r
 454    }\r
 455 \r
 456    //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
 457    //!\r
 458    //! <b>Effects</b>: Erases all the elements from *this\r
 459    //!   calling Destroyer::operator()(pointer), clones all the \r
 460    //!   elements from src calling Cloner::operator()(const value_type &)\r
 461    //!   and inserts them on *this.\r
 462    //!\r
 463    //!   If cloner throws, all cloned elements are unlinked and destroyed\r
 464    //!   calling Destroyer::operator()(pointer).\r
 465    //!   \r
 466    //! <b>Complexity</b>: Linear to erased plus inserted elements.\r
 467    //! \r
 468    //! <b>Throws</b>: If cloner throws.\r
 469    template <class Cloner, class Destroyer>\r
 470    void clone_from(const islist &src, Cloner cloner, Destroyer destroyer)\r
 471    {  \r
 472       clone_and_reverse_from(src, cloner, destroyer);\r
 473       this->reverse();\r
 474    }\r
 475 \r
 476    //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
 477    //!\r
 478    //! <b>Effects</b>: Erases all the elements from *this\r
 479    //!   calling Destroyer::operator()(pointer), clones all the \r
 480    //!   elements from src calling Cloner::operator()(const value_type &)\r
 481    //!   and inserts them on *this in the reverse order than\r
 482    //!   the original container.\r
 483    //!\r
 484    //!   If cloner throws, all cloned elements are unlinked and destroyed\r
 485    //!   calling Destroyer::operator()(pointer).\r
 486    //!   \r
 487    //! <b>Complexity</b>: Linear to erased plus inserted elements.\r
 488    //! \r
 489    //! <b>Throws</b>: If cloner throws.\r
 490    //! \r
 491    //! <b>Note</b>: This function is more efficient than "clone_from".\r
 492    template <class Cloner, class Destroyer>\r
 493    void clone_and_reverse_from(const islist &src, Cloner cloner, Destroyer destroyer)\r
 494    {\r
 495       this->clear_and_destroy(destroyer);\r
 496       try{\r
 497          const_iterator b(src.begin()), e(src.end());\r
 498          for(; b != e; ++b){\r
 499             this->push_front(*cloner(*b));\r
 500          }\r
 501       }\r
 502       catch(...){\r
 503          clear_and_destroy(destroyer);\r
 504          throw;\r
 505       }\r
 506    }\r
 507 \r
 508    //! <b>Requires</b>: value must be an lvalue and prev_p must point to an element\r
 509    //!   contained by the list or to end().\r
 510    //!\r
 511    //! <b>Effects</b>: Inserts the value after the position pointed by prev_p.\r
 512    //!    No copy constructor is called.\r
 513    //!\r
 514    //! <b>Returns</b>: An iterator to the inserted element.\r
 515    //! \r
 516    //! <b>Throws</b>: Nothing.\r
 517    //! \r
 518    //! <b>Complexity</b>: Constant.\r
 519    //! \r
 520    //! <b>Note</b>: Does not affect the validity of iterators and references.\r
 521    iterator insert_after(iterator prev_p, value_type &value)\r
 522    {\r
 523       node_ptr n = ValueTraits::to_node_ptr(value);\r
 524       if(safemode_or_autounlink)\r
 525          BOOST_ASSERT(node_algorithms::unique(n));\r
 526       node_algorithms::link_after(prev_p.list_node(), n);\r
 527       size_traits::increment();\r
 528       return iterator (n);\r
 529    }\r
 530 \r
 531    //! <b>Requires</b>: Dereferencing iterator must yield \r
 532    //!   an lvalue of type value_type and prev_p must point to an element\r
 533    //!   contained by the list or to the end node.\r
 534    //! \r
 535    //! <b>Effects</b>: Inserts the [first, last)\r
 536    //!   after the position prev_p.\r
 537    //! \r
 538    //! <b>Throws</b>: Nothing.\r
 539    //! \r
 540    //! <b>Complexity</b>: Linear to the number of elements inserted.\r
 541    //! \r
 542    //! <b>Note</b>: Does not affect the validity of iterators and references.\r
 543    template<class Iterator>\r
 544    void insert_after(iterator prev_p, Iterator first, Iterator last)\r
 545    {\r
 546       for (; first != last; ++first)\r
 547          prev_p = insert_after(prev_p, *first);\r
 548    }\r
 549 \r
 550    //! <b>Requires</b>: value must be an lvalue and p must point to an element\r
 551    //!   contained by the list or to end().\r
 552    //!\r
 553    //! <b>Effects</b>: Inserts the value before the position pointed by p.\r
 554    //!   No copy constructor is called.\r
 555    //! \r
 556    //! <b>Throws</b>: Nothing.\r
 557    //! \r
 558    //! <b>Complexity</b>: Linear to the number of elements before p. \r
 559    //! \r
 560    //! <b>Note</b>: Does not affect the validity of iterators and references.\r
 561    iterator insert(iterator p, value_type &value)\r
 562    {  return insert_after(this->previous(p), value);  }\r
 563 \r
 564    //! <b>Requires</b>: Dereferencing iterator must yield \r
 565    //!   an lvalue of type value_type and p must point to an element \r
 566    //!   contained by the list or to the end node.\r
 567    //! \r
 568    //! <b>Effects</b>: Inserts the pointed by b and e\r
 569    //!   before the position p. No copy constructors are called.\r
 570    //! \r
 571    //! <b>Throws</b>: Nothing.\r
 572    //! \r
 573    //! <b>Complexity</b>: Linear to the number of elements inserted plus linear\r
 574    //!   to the elements before b.\r
 575    //! \r
 576    //! <b>Note</b>: Does not affect the validity of iterators and references.\r
 577    template<class Iterator>\r
 578    void insert(iterator p, Iterator b, Iterator e)\r
 579    {  return insert_after(this->previous(p), b, e);  }\r
 580 \r
 581    //! <b>Effects</b>: Erases the element after the element pointed by prev of \r
 582    //!   the list. No destructors are called.\r
 583    //!\r
 584    //! <b>Returns</b>: the first element remaining beyond the removed elements,\r
 585    //!   or end() if no such element exists.\r
 586    //! \r
 587    //! <b>Throws</b>: Nothing.\r
 588    //! \r
 589    //! <b>Complexity</b>: Constant.\r
 590    //! \r
 591    //! <b>Note</b>: Invalidates the iterators (but not the references) to the\r
 592    //!   erased element.\r
 593    iterator erase_after(iterator prev)\r
 594    {\r
 595       iterator it(prev); ++it;\r
 596       node_ptr to_erase(it.list_node());\r
 597       node_algorithms::unlink_after(prev.list_node());\r
 598       size_traits::decrement();\r
 599       iterator ret(++prev);\r
 600       if(safemode_or_autounlink)\r
 601          node_algorithms::init(to_erase);\r
 602       return ret;\r
 603    }\r
 604 \r
 605    //! <b>Effects</b>: Erases the range (before_first, last) from\r
 606    //!   the list. No destructors are called.\r
 607    //!\r
 608    //! <b>Returns</b>: the first element remaining beyond the removed elements,\r
 609    //!   or end() if no such element exists.\r
 610    //! \r
 611    //! <b>Throws</b>: Nothing.\r
 612    //! \r
 613    //! <b>Complexity</b>: Lineal to the elements (last - before_first).\r
 614    //! \r
 615    //! <b>Note</b>: Invalidates the iterators (but not the references) to the\r
 616    //!   erased element.\r
 617    iterator erase_after(iterator before_first, iterator last)\r
 618    {\r
 619       iterator first;\r
 620       while(++(first = before_first) != last){\r
 621          this->erase_after(before_first);\r
 622       }\r
 623       return last;\r
 624    }\r
 625 \r
 626    //! <b>Effects</b>: Erases the element pointed by i of the list. \r
 627    //!   No destructors are called.\r
 628    //!\r
 629    //! <b>Returns</b>: the first element remaining beyond the removed element,\r
 630    //!   or end() if no such element exists.\r
 631    //! \r
 632    //! <b>Throws</b>: Nothing.\r
 633    //! \r
 634    //! <b>Complexity</b>: Linear to the elements before i.\r
 635    //! \r
 636    //! <b>Note</b>: Invalidates the iterators (but not the references) to the\r
 637    //!   erased element.\r
 638    iterator erase(iterator i)\r
 639    {  return this->erase_after(this->previous(i));  }\r
 640 \r
 641    //! <b>Requires</b>: first and last must be valid iterator to elements in *this.\r
 642    //! \r
 643    //! <b>Effects</b>: Erases the range pointed by b and e.\r
 644    //!   No destructors are called.\r
 645    //!\r
 646    //! <b>Returns</b>: the first element remaining beyond the removed elements,\r
 647    //!   or end() if no such element exists.\r
 648    //! \r
 649    //! <b>Throws</b>: Nothing.\r
 650    //! \r
 651    //! <b>Complexity</b>: Linear to the number of elements erased plus linear\r
 652    //!   to the elements before first.\r
 653    //! \r
 654    //! <b>Note</b>: Invalidates the iterators (but not the references) to the\r
 655    //!   erased elements.\r
 656    iterator erase(iterator first, iterator last)\r
 657    {  return erase_after(this->previous(first), last);  }\r
 658 \r
 659    //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
 660    //!\r
 661    //! <b>Effects</b>: Erases the element after the element pointed by prev of \r
 662    //!   the list.\r
 663    //!   Destroyer::operator()(pointer) is called for the removed element.\r
 664    //!\r
 665    //! <b>Returns</b>: the first element remaining beyond the removed elements,\r
 666    //!   or end() if no such element exists.\r
 667    //! \r
 668    //! <b>Throws</b>: Nothing.\r
 669    //! \r
 670    //! <b>Complexity</b>: Constant.\r
 671    //! \r
 672    //! <b>Note</b>: Invalidates the iterators to the erased element.\r
 673    template<class Destroyer>\r
 674    iterator erase_after_and_destroy(iterator prev, Destroyer destroyer)\r
 675    {\r
 676       iterator it(prev); ++it;\r
 677       node_ptr to_erase(it.list_node());\r
 678       iterator ret(this->erase_after(prev));\r
 679       destroyer(ValueTraits::to_value_ptr(to_erase));\r
 680       return ret;\r
 681    }\r
 682 \r
 683    //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
 684    //!\r
 685    //! <b>Effects</b>: Erases the range (before_first, last) from\r
 686    //!   the list.\r
 687    //!   Destroyer::operator()(pointer) is called for the removed elements.\r
 688    //!\r
 689    //! <b>Returns</b>: the first element remaining beyond the removed elements,\r
 690    //!   or end() if no such element exists.\r
 691    //! \r
 692    //! <b>Throws</b>: Nothing.\r
 693    //! \r
 694    //! <b>Complexity</b>: Lineal to the elements (last - before_first).\r
 695    //! \r
 696    //! <b>Note</b>: Invalidates the iterators to the erased element.\r
 697    template<class Destroyer>\r
 698    iterator erase_after_and_destroy(iterator before_first, iterator last, Destroyer destroyer)\r
 699    {\r
 700       iterator first;\r
 701       while(++(first = before_first) != last){\r
 702          this->erase_after_and_destroy(before_first, destroyer);\r
 703       }\r
 704       return last;\r
 705    }\r
 706 \r
 707    //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
 708    //!\r
 709    //! <b>Effects</b>: Erases the element pointed by i of the list. \r
 710    //!   No destructors are called.\r
 711    //!   Destroyer::operator()(pointer) is called for the removed element.\r
 712    //!\r
 713    //! <b>Returns</b>: the first element remaining beyond the removed element,\r
 714    //!   or end() if no such element exists.\r
 715    //! \r
 716    //! <b>Throws</b>: Nothing.\r
 717    //! \r
 718    //! <b>Complexity</b>: Linear to the elements before i.\r
 719    //! \r
 720    //! <b>Note</b>: Invalidates the iterators (but not the references) to the\r
 721    //!   erased element.\r
 722    template<class Destroyer>\r
 723    iterator erase_and_destroy(iterator i, Destroyer destroyer)\r
 724    {  return this->erase_after_and_destroy(this->previous(i), destroyer);  }\r
 725 \r
 726    //! <b>Requires</b>: first and last must be valid iterator to elements in *this.\r
 727    //!                  Destroyer::operator()(pointer) shouldn't throw.\r
 728    //! \r
 729    //! <b>Effects</b>: Erases the range pointed by b and e.\r
 730    //!   No destructors are called.\r
 731    //!   Destroyer::operator()(pointer) is called for the removed elements.\r
 732    //!\r
 733    //! <b>Returns</b>: the first element remaining beyond the removed elements,\r
 734    //!   or end() if no such element exists.\r
 735    //! \r
 736    //! <b>Throws</b>: Nothing.\r
 737    //! \r
 738    //! <b>Complexity</b>: Linear to the number of elements erased plus linear\r
 739    //!   to the elements before first.\r
 740    //! \r
 741    //! <b>Note</b>: Invalidates the iterators (but not the references) to the\r
 742    //!   erased elements.\r
 743    template<class Destroyer>\r
 744    iterator erase_and_destroy(iterator first, iterator last, Destroyer destroyer)\r
 745    {  return erase_after_and_destroy(this->previous(first), last, destroyer);  }\r
 746 \r
 747    //! <b>Requires</b>: Dereferencing iterator must yield \r
 748    //!   an lvalue of type value_type.\r
 749    //! \r
 750    //! <b>Effects</b>: Clears the list and inserts the range pointed by b and e.\r
 751    //!   No destructors or copy constructors are called.\r
 752    //! \r
 753    //! <b>Throws</b>: Nothing.\r
 754    //! \r
 755    //! <b>Complexity</b>: Linear to the number of elements inserted plus\r
 756    //!   linear to the elements contained in the list if it's a safe-mode\r
 757    //!   or auto-unlink value.\r
 758    //!   Linear to the number of elements inserted in the list otherwise.\r
 759    //! \r
 760    //! <b>Note</b>: Invalidates the iterators (but not the references)\r
 761    //!   to the erased elements.\r
 762    template<class Iterator>\r
 763    void assign(Iterator b, Iterator e)\r
 764    {\r
 765       this->clear();\r
 766       this->insert_after(before_begin(), b, e);\r
 767    }\r
 768 \r
 769    //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
 770    //!\r
 771    //! <b>Requires</b>: Dereferencing iterator must yield \r
 772    //!   an lvalue of type value_type.\r
 773    //! \r
 774    //! <b>Effects</b>: Clears the list and inserts the range pointed by b and e.\r
 775    //!   No destructors or copy constructors are called.\r
 776    //!   Destroyer::operator()(pointer) is called for the removed elements.\r
 777    //! \r
 778    //! <b>Throws</b>: Nothing.\r
 779    //! \r
 780    //! <b>Complexity</b>: Linear to the number of elements inserted plus\r
 781    //!   linear to the elements contained in the list.\r
 782    //! \r
 783    //! <b>Note</b>: Invalidates the iterators (but not the references)\r
 784    //!   to the erased elements.\r
 785    template<class Iterator, class Destroyer>\r
 786    void assign_and_destroy(Iterator b, Iterator e, Destroyer destroyer)\r
 787    {\r
 788       this->clear_and_destroy(destroyer);\r
 789       this->insert_after_and_destroy(before_begin(), b, e, destroyer);\r
 790    }\r
 791 \r
 792    //! <b>Requires</b>: prev is an iterator to an element or x.end()/x.before_begin() in x.\r
 793    //! \r
 794    //! <b>Effects</b>: Transfers all the elements of list x to this list, after the\r
 795    //! the element pointed by prev. No destructors or copy constructors are called.\r
 796    //! \r
 797    //! <b>Returns</b>: The last element inserted of x or prev if x is empty.\r
 798    //!   This iterator can be used as new "prev" iterator for a new splice_after call.\r
 799    //!   that will splice new values after the previously spliced values.\r
 800    //! \r
 801    //! <b>Throws</b>: Nothing.\r
 802    //!\r
 803    //! <b>Complexity</b>: Linear to the elements contained in x\r
 804    //! \r
 805    //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this\r
 806    //! list. Iterators of this list and all the references are not invalidated.\r
 807    iterator splice_after(iterator prev, islist &x)\r
 808    {\r
 809       if (!x.empty()){\r
 810          iterator last_x(x.previous(x.end()));\r
 811          node_algorithms::transfer_after\r
 812             ( prev.list_node()\r
 813             , x.end().list_node()\r
 814             , last_x.list_node());\r
 815          size_traits::set_size(size_traits::get_size() + x.get_size());\r
 816          x.set_size(size_type(0));\r
 817          return last_x;\r
 818       }\r
 819       else{\r
 820          return prev;\r
 821       }\r
 822    }\r
 823 \r
 824    //! <b>Requires</b>: prev must point to an element contained by this list or\r
 825    //!   to the before_begin() element. prev_ele must point to an element contained in list\r
 826    //!   x or must be x.before_begin().\r
 827    //! \r
 828    //! <b>Effects</b>: Transfers the element after prev_ele, from list x to this list, \r
 829    //!   after the element pointed by prev. No destructors or copy constructors are called.\r
 830    //! \r
 831    //! <b>Throws</b>: Nothing.\r
 832    //! \r
 833    //! <b>Complexity</b>: Constant.\r
 834    //! \r
 835    //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this\r
 836    //! list. Iterators of this list and all the references are not invalidated.\r
 837    void splice_after(iterator prev, islist &x, iterator prev_ele)\r
 838    {\r
 839       iterator nxt = prev_ele;\r
 840       ++nxt;\r
 841       if (nxt != prev && prev_ele != prev){\r
 842          node_algorithms::transfer_after\r
 843             (prev.list_node(), prev_ele.list_node(), nxt.list_node());\r
 844          size_traits::increment();\r
 845          x.decrement();\r
 846       }\r
 847    }\r
 848 \r
 849    //! <b>Requires</b>: prev_pos must be a dereferenceable iterator in *this or be\r
 850    //!   before_begin(), and before_first and before_last belong to x and\r
 851    //!   ++before_first != x.end() && before_last != x.end(). \r
 852    //! \r
 853    //! <b>Effects</b>: Transfers the range (before_first, before_last] from list x to this\r
 854    //!   list, after the element pointed by prev_pos.\r
 855    //!   No destructors or copy constructors are called.\r
 856    //! \r
 857    //! <b>Throws</b>: Nothing.\r
 858    //! \r
 859    //! <b>Complexity</b>: Linear to the number of elements transferred\r
 860    //!   if ConstantTimeSize is true. Constant-time otherwise.\r
 861    //! \r
 862    //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this\r
 863    //!   list. Iterators of this list and all the references are not invalidated.\r
 864    void splice_after(iterator prev_pos, islist &x, iterator before_first, iterator before_last)\r
 865    {\r
 866       if (before_first != before_last){\r
 867          if(ConstantTimeSize){\r
 868             size_type increment = std::distance(before_first, before_last);\r
 869             node_algorithms::transfer_after\r
 870                (prev_pos.list_node(), before_first.list_node(), before_last.list_node());\r
 871             size_traits::set_size(size_traits::get_size() + increment);\r
 872             x.set_size(x.get_size() - increment);\r
 873          }\r
 874          else{\r
 875             node_algorithms::transfer_after\r
 876                (prev_pos.list_node(), before_first.list_node(), before_last.list_node());\r
 877          }\r
 878       }\r
 879    }\r
 880 \r
 881    //! <b>Requires</b>: prev_pos must be a dereferenceable iterator in *this or be\r
 882    //!   before_begin(), and before_first and before_last belong to x and\r
 883    //!   ++before_first != x.end() && before_last != x.end() and\r
 884    //!   n == std::distance(before_first, before_last).\r
 885    //! \r
 886    //! <b>Effects</b>: Transfers the range (before_first, before_last] from list x to this\r
 887    //!   list, after the element pointed by p. No destructors or copy constructors are called.\r
 888    //! \r
 889    //! <b>Throws</b>: Nothing.\r
 890    //! \r
 891    //! <b>Complexity</b>: Constant time.\r
 892    //! \r
 893    //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this\r
 894    //!   list. Iterators of this list and all the references are not invalidated.\r
 895    void splice_after(iterator prev_pos, islist &x, iterator before_first, iterator before_last, difference_type n)\r
 896    {\r
 897       if(n){\r
 898          if(ConstantTimeSize){\r
 899             BOOST_ASSERT(std::distance(before_first, before_last) == n);\r
 900             node_algorithms::transfer_after\r
 901                (prev_pos.list_node(), before_first.list_node(), before_last.list_node());\r
 902             size_traits::set_size(size_traits::get_size() + n);\r
 903             x.set_size(x.get_size() - n);\r
 904          }\r
 905          else{\r
 906             node_algorithms::transfer_after\r
 907                (prev_pos.list_node(), before_first.list_node(), before_last.list_node());\r
 908          }\r
 909       }\r
 910    }\r
 911 \r
 912    //! <b>Requires</b>: it is an iterator to an element in x.\r
 913    //! \r
 914    //! <b>Effects</b>: Transfers all the elements of list x to this list, before the\r
 915    //! the element pointed by it. No destructors or copy constructors are called.\r
 916    //! \r
 917    //! <b>Returns</b>: The last element inserted of x or the previous element\r
 918    //!   of it if x is empty.\r
 919    //!   This iterator can be used as new "prev" iterator for a new splice call.\r
 920    //!   that will splice new values after the previously spliced values.\r
 921    //! \r
 922    //! <b>Throws</b>: Nothing.\r
 923    //!\r
 924    //! <b>Complexity</b>: Linear to the elements contained in x plus linear to\r
 925    //!   the elements before it.\r
 926    //! \r
 927    //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this\r
 928    //! list. Iterators of this list and all the references are not invalidated.\r
 929    iterator splice(iterator it, islist &x)\r
 930    {  return splice_after(this->previous(it), x);   }\r
 931 \r
 932    //! <b>Requires</b>: it p must be a valid iterator of *this.\r
 933    //!   elem must point to an element contained in list\r
 934    //!   x.\r
 935    //! \r
 936    //! <b>Effects</b>: Transfers the element elem, from list x to this list, \r
 937    //!   before the element pointed by pos. No destructors or copy constructors are called.\r
 938    //! \r
 939    //! <b>Throws</b>: Nothing.\r
 940    //! \r
 941    //! <b>Complexity</b>: Linear to the elements before pos and before elem.\r
 942    //! \r
 943    //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this\r
 944    //! list. Iterators of this list and all the references are not invalidated.\r
 945    void splice(iterator pos, islist &x, iterator elem)\r
 946    {  return splice_after(this->previous(pos), x, this->previous(elem));  }\r
 947 \r
 948    //! <b>Requires</b>: pos must be a dereferenceable iterator in *this\r
 949    //!   and first and last belong to x and first and last a valid range on x. \r
 950    //! \r
 951    //! <b>Effects</b>: Transfers the range [first, last) from list x to this\r
 952    //!   list, before the element pointed by pos.\r
 953    //!   No destructors or copy constructors are called.\r
 954    //! \r
 955    //! <b>Throws</b>: Nothing.\r
 956    //! \r
 957    //! <b>Complexity</b>: Linear to the sum of elements before pos, first, and last.\r
 958    //!   Plus linear to the number of elements transferred if ConstantTimeSize is true.\r
 959    //! \r
 960    //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this\r
 961    //!   list. Iterators of this list and all the references are not invalidated.\r
 962    void splice(iterator pos, islist &x, iterator first, iterator last)\r
 963    {  return splice_after(this->previous(pos), x, this->previous(first), this->previous(last));  }\r
 964 \r
 965    //! <b>Requires</b>: pos must be a dereferenceable iterator in *this\r
 966    //!   and first and last belong to x and first and last a valid range on x. \r
 967    //!   n == std::distance(first, last).\r
 968    //! \r
 969    //! <b>Effects</b>: Transfers the range [first, last) from list x to this\r
 970    //!   list, before the element pointed by pos.\r
 971    //!   No destructors or copy constructors are called.\r
 972    //! \r
 973    //! <b>Throws</b>: Nothing.\r
 974    //! \r
 975    //! <b>Complexity</b>: Linear to the sum of elements before pos, first, and last.\r
 976    //! \r
 977    //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this\r
 978    //!   list. Iterators of this list and all the references are not invalidated.\r
 979    void splice(iterator pos, islist &x, iterator first, iterator last, difference_type n)\r
 980    {  return splice_after(this->previous(pos), x, this->previous(first), this->previous(last), n);  }\r
 981 \r
 982    //! <b>Effects</b>: This function sorts the list *this according to std::less<value_type>. \r
 983    //!   The sort is stable, that is, the relative order of equivalent elements is preserved.\r
 984    //! \r
 985    //! <b>Throws</b>: If value_traits::node_traits::node\r
 986    //!   constructor throws (this does not happen with predefined Boost.Intrusive hooks)\r
 987    //!   or the predicate throws. Basic guarantee.\r
 988    //! \r
 989    //! <b>Complexity</b>: The number of comparisons is approximately N log N, where N\r
 990    //!   is the list's size.\r
 991    //!\r
 992    //! <b>Note</b>: Iterators and references are not invalidated\r
 993    template<class Predicate>\r
 994    void sort(Predicate p)\r
 995    {\r
 996       if (!this->empty() &&\r
 997             node_traits::get_next(node_traits::get_next(get_root_node()))\r
 998                != this->get_root_node()) {\r
 999          islist carry;\r
1000          islist counter[64];\r
1001          int fill = 0;\r
1002          iterator last_inserted;\r
1003          while(!this->empty()){\r
1004             last_inserted = this->begin();\r
1005             carry.splice_after(carry.before_begin(), *this, this->before_begin());\r
1006             int i = 0;\r
1007             while(i < fill && !counter[i].empty()) {\r
1008                last_inserted = carry.merge(counter[i++], p);\r
1009             }\r
1010             BOOST_ASSERT(counter[i].empty());\r
1011 \r
1012             iterator last_element(previous_node(last_inserted, carry.end()));\r
1013             if(ConstantTimeSize){\r
1014                counter[i].splice_after( counter[i].end(), carry\r
1015                                       , carry.before_begin(), last_element\r
1016                                       , carry.size());\r
1017             }\r
1018             else{\r
1019                counter[i].splice_after( counter[i].end(), carry\r
1020                                       , carry.before_begin(), last_element);\r
1021             }\r
1022             //counter[i].splice_after(counter[i].end(), carry, carry.end(), previous_node(last_inserted, carry.end()));\r
1023             //carry.swap(counter[i]);\r
1024             if(i == fill)\r
1025                ++fill;\r
1026          }\r
1027 \r
1028          for (int i = 1; i < fill; ++i)\r
1029             last_inserted = counter[i].merge(counter[i-1], p);\r
1030          //this->swap(counter[fill-1]);\r
1031          BOOST_ASSERT(this->empty());\r
1032 \r
1033          iterator last_element(previous_node(last_inserted, counter[--fill].end()));\r
1034          if(ConstantTimeSize){\r
1035             this->splice_after( end(), counter[fill], counter[fill].before_begin()\r
1036                               , last_element, counter[fill].size());\r
1037          }\r
1038          else{\r
1039             this->splice_after( end(), counter[fill], counter[fill].before_begin()\r
1040                               , last_element);\r
1041          }\r
1042       }\r
1043    }\r
1044 \r
1045    //! <b>Requires</b>: p must be a comparison function that induces a strict weak\r
1046    //!   ordering and both *this and x must be sorted according to that ordering\r
1047    //!   The lists x and *this must be distinct. \r
1048    //! \r
1049    //! <b>Effects</b>: This function removes all of x's elements and inserts them\r
1050    //!   in order into *this. The merge is stable; that is, if an element from *this is \r
1051    //!   equivalent to one from x, then the element from *this will precede the one from x. \r
1052    //! \r
1053    //! <b>Throws</b>: If value_traits::node_traits::node\r
1054    //!   constructor throws (this does not happen with predefined Boost.Intrusive hooks)\r
1055    //!   or std::less<value_type> throws. Basic guarantee.\r
1056    //! \r
1057    //! <b>Complexity</b>: This function is linear time: it performs at most\r
1058    //!   size() + x.size() - 1 comparisons.\r
1059    //! \r
1060    //! <b>Note</b>: Iterators and references are not invalidated.\r
1061    void sort()\r
1062    { this->sort(std::less<value_type>()); }\r
1063 \r
1064    //! <b>Requires</b>: p must be a comparison function that induces a strict weak\r
1065    //!   ordering and both *this and x must be sorted according to that ordering\r
1066    //!   The lists x and *this must be distinct. \r
1067    //! \r
1068    //! <b>Effects</b>: This function removes all of x's elements and inserts them\r
1069    //!   in order into *this. The merge is stable; that is, if an element from *this is \r
1070    //!   equivalent to one from x, then the element from *this will precede the one from x. \r
1071    //! \r
1072    //! <b>Returns</b>: An iterator to the last transferred value, end() is x is empty.\r
1073    //! \r
1074    //! <b>Throws</b>: If the predicate throws. Basic guarantee.\r
1075    //! \r
1076    //! <b>Complexity</b>: This function is linear time: it performs at most\r
1077    //!   size() + x.size() - 1 comparisons.\r
1078    //! \r
1079    //! <b>Note</b>: Iterators and references are not invalidated.\r
1080    template<class Predicate>\r
1081    iterator merge(islist& x, Predicate p) \r
1082    {\r
1083       iterator a(before_begin()), e(end()), ax(x.before_begin());\r
1084       iterator last_inserted(e);\r
1085       iterator a_next;\r
1086       while(++(a_next = a) != e && !x.empty()) {\r
1087          iterator ix(ax);\r
1088          iterator cx;\r
1089          size_type n(0);\r
1090          while(++(cx = ix) != ax && p(*cx, *a_next)){\r
1091             ++ix; ++n;\r
1092          }\r
1093          if(ax != ix){\r
1094             this->splice_after(a, x, ax, ix, n);\r
1095             last_inserted = ix;\r
1096          }\r
1097          a = a_next;\r
1098       }  \r
1099       if (!x.empty()){\r
1100          last_inserted = this->splice_after(a, x);\r
1101       }\r
1102       return last_inserted;\r
1103    }\r
1104 \r
1105    //! <b>Effects</b>: This function removes all of x's elements and inserts them\r
1106    //!   in order into *this according to std::less<value_type>. The merge is stable; \r
1107    //!   that is, if an element from *this is equivalent to one from x, then the element \r
1108    //!   from *this will precede the one from x. \r
1109    //! \r
1110    //! <b>Throws</b>: if std::less<value_type> throws. Basic guarantee.\r
1111    //! \r
1112    //! <b>Complexity</b>: This function is linear time: it performs at most\r
1113    //!   size() + x.size() - 1 comparisons.\r
1114    //! \r
1115    //! <b>Note</b>: Iterators and references are not invalidated\r
1116    void merge(islist& x)\r
1117    { this->merge(x, std::less<value_type>()); }\r
1118 \r
1119    //! <b>Effects</b>: Reverses the order of elements in the list. \r
1120    //! \r
1121    //! <b>Throws</b>: Nothing.\r
1122    //! \r
1123    //! <b>Complexity</b>: This function is linear to the contained elements.\r
1124    //! \r
1125    //! <b>Note</b>: Iterators and references are not invalidated\r
1126    void reverse() \r
1127    {  node_algorithms::reverse(node_ptr(&root));  }\r
1128 \r
1129    //! <b>Effects</b>: Removes all the elements that compare equal to value.\r
1130    //!   No destructors are called.\r
1131    //! \r
1132    //! <b>Throws</b>: If std::equal_to<value_type> throws. Basic guarantee.\r
1133    //! \r
1134    //! <b>Complexity</b>: Linear time. It performs exactly size() comparisons for equality.\r
1135    //! \r
1136    //! <b>Note</b>: The relative order of elements that are not removed is unchanged,\r
1137    //!   and iterators to elements that are not removed remain valid. This function is \r
1138    //!   linear time: it performs exactly size() comparisons for equality.\r
1139    void remove(const value_type &value)\r
1140    {  remove_if(equal_to_value(value));  }\r
1141 \r
1142    //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
1143    //!\r
1144    //! <b>Effects</b>: Removes all the elements that compare equal to value.\r
1145    //!   Destroyer::operator()(pointer) is called for every removed element.\r
1146    //!\r
1147    //! <b>Throws</b>: If std::equal_to<value_type> throws. Basic guarantee.\r
1148    //! \r
1149    //! <b>Complexity</b>: Linear time. It performs exactly size() comparisons for equality.\r
1150    //! \r
1151    //! <b>Note</b>: The relative order of elements that are not removed is unchanged,\r
1152    //!   and iterators to elements that are not removed remain valid.\r
1153    template<class Destroyer>\r
1154    void remove_and_destroy(const value_type &value, Destroyer destroyer)\r
1155    {  remove_and_destroy_if(equal_to_value(value), destroyer);  }\r
1156 \r
1157    //! <b>Effects</b>: Removes all the elements for which a specified\r
1158    //!   predicate is satisfied. No destructors are called.\r
1159    //! \r
1160    //! <b>Throws</b>: If pred throws. Basic guarantee.\r
1161    //! \r
1162    //! <b>Complexity</b>: Linear time. It performs exactly size() calls to the predicate.\r
1163    //! \r
1164    //! <b>Note</b>: The relative order of elements that are not removed is unchanged,\r
1165    //!   and iterators to elements that are not removed remain valid.\r
1166    template<class Pred>\r
1167    void remove_if(Pred pred)\r
1168    {  remove_and_destroy_if(pred, detail::null_destroyer());   }\r
1169 \r
1170    //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
1171    //!\r
1172    //! <b>Effects</b>: Removes all the elements for which a specified\r
1173    //!   predicate is satisfied.\r
1174    //!   Destroyer::operator()(pointer) is called for every removed element.\r
1175    //!\r
1176    //! <b>Throws</b>: If pred throws. Basic guarantee.\r
1177    //! \r
1178    //! <b>Complexity</b>: Linear time. It performs exactly size() comparisons for equality.\r
1179    //!\r
1180    //! <b>Note</b>: The relative order of elements that are not removed is unchanged,\r
1181    //!   and iterators to elements that are not removed remain valid.\r
1182    template<class Pred, class Destroyer>\r
1183    void remove_and_destroy_if(Pred pred, Destroyer destroyer)\r
1184    {\r
1185       iterator bcur(this->before_begin()), cur, e(this->end());\r
1186       \r
1187       while(++(cur = bcur) != e){\r
1188          if (pred(*cur)){\r
1189             pointer p = cur.operator->();\r
1190             this->erase_after(bcur);\r
1191             destroyer(p);\r
1192          }\r
1193          else{\r
1194             ++bcur;\r
1195          }\r
1196       }\r
1197    }\r
1198 \r
1199    //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent \r
1200    //!   elements that are equal from the list. No destructors are called.\r
1201    //! \r
1202    //! <b>Throws</b>: If std::equal_to<value_type> throws. Basic guarantee.\r
1203    //! \r
1204    //! <b>Complexity</b>: Linear time (size()-1) comparisons calls to pred()).\r
1205    //! \r
1206    //! <b>Note</b>: The relative order of elements that are not removed is unchanged,\r
1207    //!   and iterators to elements that are not removed remain valid.\r
1208    void unique()\r
1209    {  unique_and_destroy(std::equal_to<value_type>(), detail::null_destroyer());  }\r
1210 \r
1211    //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent \r
1212    //!   elements that satisfy some binary predicate from the list.\r
1213    //!   No destructors are called.\r
1214    //! \r
1215    //! <b>Throws</b>: If the predicate throws. Basic guarantee.\r
1216    //! \r
1217    //! <b>Complexity</b>: Linear time (size()-1) comparisons equality comparisons.\r
1218    //! \r
1219    //! <b>Note</b>: The relative order of elements that are not removed is unchanged,\r
1220    //!   and iterators to elements that are not removed remain valid.\r
1221    template<class BinaryPredicate>\r
1222    void unique(BinaryPredicate pred)\r
1223    {  unique_and_destroy(pred, detail::null_destroyer());  }\r
1224 \r
1225    //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
1226    //!\r
1227    //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent \r
1228    //!   elements that satisfy some binary predicate from the list.\r
1229    //!   Destroyer::operator()(pointer) is called for every removed element.\r
1230    //! \r
1231    //! <b>Throws</b>: If std::equal_to<value_type> throws. Basic guarantee.\r
1232    //! \r
1233    //! <b>Complexity</b>: Linear time (size()-1) comparisons equality comparisons.\r
1234    //! \r
1235    //! <b>Note</b>: The relative order of elements that are not removed is unchanged,\r
1236    //!   and iterators to elements that are not removed remain valid.\r
1237    template<class Destroyer>\r
1238    void unique_and_destroy(Destroyer destroyer)\r
1239    {  unique(std::equal_to<value_type>(), destroyer);  }\r
1240 \r
1241    //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
1242    //!\r
1243    //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent \r
1244    //!   elements that satisfy some binary predicate from the list.\r
1245    //!   Destroyer::operator()(pointer) is called for every removed element.\r
1246    //! \r
1247    //! <b>Throws</b>: If the predicate throws. Basic guarantee.\r
1248    //! \r
1249    //! <b>Complexity</b>: Linear time (size()-1) comparisons equality comparisons.\r
1250    //! \r
1251    //! <b>Note</b>: The relative order of elements that are not removed is unchanged,\r
1252    //!   and iterators to elements that are not removed remain valid.\r
1253    template<class BinaryPredicate, class Destroyer>\r
1254    void unique_and_destroy(BinaryPredicate pred, Destroyer destroyer)\r
1255    {\r
1256       iterator end_n(end());\r
1257       iterator cur(begin());\r
1258       iterator cur_next;\r
1259 \r
1260       if (cur != end_n) {\r
1261          while(++(cur_next = cur) != end_n) {\r
1262             if (pred(*cur, *cur_next)){\r
1263                pointer p = cur_next.operator->();\r
1264                this->erase_after(cur);\r
1265                destroyer(p);\r
1266             }\r
1267             else{\r
1268                ++cur;\r
1269             }\r
1270          }\r
1271       }\r
1272    }\r
1273 \r
1274    //! <b>Requires</b>: value must be a reference to a value inserted in a list.\r
1275    //! \r
1276    //! <b>Effects</b>: This function returns a const_iterator pointing to the element\r
1277    //! \r
1278    //! <b>Throws</b>: Nothing.\r
1279    //! \r
1280    //! <b>Complexity</b>: Constant time.\r
1281    //! \r
1282    //! <b>Note</b>: Iterators and references are not invalidated.\r
1283    static iterator current(value_type &value) \r
1284    { \r
1285       BOOST_ASSERT (!node_algorithms::unique(ValueTraits::to_node_ptr(value)));\r
1286       return iterator (ValueTraits::to_node_ptr(value)); \r
1287    }\r
1288 \r
1289    //! <b>Requires</b>: value must be a const reference to a value inserted in a list.\r
1290    //! \r
1291    //! <b>Effects</b>: This function returns an iterator pointing to the element.\r
1292    //! \r
1293    //! <b>Throws</b>: Nothing.\r
1294    //! \r
1295    //! <b>Complexity</b>: Constant time.\r
1296    //! \r
1297    //! <b>Note</b>: Iterators and references are not invalidated.\r
1298    static const_iterator current(const value_type &value) \r
1299    { \r
1300       BOOST_ASSERT (!node_algorithms::unique(ValueTraits::to_node_ptr(const_cast<value_type&> (value))));\r
1301       return const_iterator (ValueTraits::to_node_ptr(const_cast<value_type&> (value))); \r
1302    }\r
1303 \r
1304    //! <b>Returns</b>: The iterator to the element before i in the list. \r
1305    //!   Returns the end-iterator, if either i is the begin-iterator or the \r
1306    //!   list is empty. \r
1307    //! \r
1308    //! <b>Throws</b>: Nothing.\r
1309    //! \r
1310    //! <b>Complexity</b>: Linear to the number of elements before i. \r
1311    iterator previous(iterator i)\r
1312    {\r
1313       return iterator\r
1314          (node_algorithms::get_previous_node\r
1315             (before_begin().list_node(), i.list_node()));\r
1316    }\r
1317 \r
1318    //! <b>Returns</b>: The const_iterator to the element before i in the list. \r
1319    //!   Returns the end-const_iterator, if either i is the begin-const_iterator or \r
1320    //!   the list is empty. \r
1321    //! \r
1322    //! <b>Throws</b>: Nothing.\r
1323    //! \r
1324    //! <b>Complexity</b>: Linear to the number of elements before i. \r
1325    const_iterator previous(const_iterator i) const\r
1326    {\r
1327       return const_iterator\r
1328          (node_algorithms::get_previous_node\r
1329             (before_begin().list_node(), i.list_node()));\r
1330    }\r
1331 };\r
1332 \r
1333 template <class V, bool C, class S>\r
1334 inline bool operator==(const islist<V, C, S>& x, const islist<V, C, S>& y)\r
1335 {\r
1336    if(C && x.size() != y.size()){\r
1337       return false;\r
1338    }\r
1339    typedef typename islist<V, C, S>::const_iterator const_iterator;\r
1340    const_iterator end1 = x.end();\r
1341 \r
1342    const_iterator i1 = x.begin();\r
1343    const_iterator i2 = y.begin();\r
1344    if(C){\r
1345       while (i1 != end1 && *i1 == *i2) {\r
1346          ++i1;\r
1347          ++i2;\r
1348       }\r
1349       return i1 == end1;\r
1350    }\r
1351    else{\r
1352       const_iterator end2 = y.end();\r
1353       while (i1 != end1 && i2 != end2 && *i1 == *i2) {\r
1354          ++i1;\r
1355          ++i2;\r
1356       }\r
1357       return i1 == end1 && i2 == end2;\r
1358    }\r
1359 }\r
1360 \r
1361 template <class V, bool C, class S>\r
1362 inline bool operator<(const islist<V, C, S>& x,\r
1363                       const islist<V, C, S>& y)\r
1364 {  return std::lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());  }\r
1365 \r
1366 template <class V, bool C, class S>\r
1367 inline bool operator!=(const islist<V, C, S>& x, const islist<V, C, S>& y) \r
1368 {  return !(x == y); }\r
1369 \r
1370 template <class V, bool C, class S>\r
1371 inline bool operator>(const islist<V, C, S>& x, const islist<V, C, S>& y) \r
1372 {  return y < x;  }\r
1373 \r
1374 template <class V, bool C, class S>\r
1375 inline bool operator<=(const islist<V, C, S>& x, const islist<V, C, S>& y) \r
1376 {  return !(y < x);  }\r
1377 \r
1378 template <class V, bool C, class S>\r
1379 inline bool operator>=(const islist<V, C, S>& x, const islist<V, C, S>& y) \r
1380 {  return !(x < y);  }\r
1381 \r
1382 template <class V, bool C, class S>\r
1383 inline void swap(islist<V, C, S>& x, islist<V, C, S>& y)\r
1384 {  x.swap(y);  }\r
1385 \r
1386 } //namespace intrusive \r
1387 } //namespace boost \r
1388 \r
1389 #include <boost/intrusive/detail/config_end.hpp>\r
1390 \r
1391 #endif //BOOST_INTRUSIVE_ISLIST_HPP\r