boost/intrusive/iset_hook.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_ISET_HOOK_HPP\r
  15 #define BOOST_INTRUSIVE_ISET_HOOK_HPP\r
  16 \r
  17 #include "detail/config_begin.hpp"\r
  18 #include "detail/utilities.hpp"\r
  19 #include "detail/pointer_type.hpp"\r
  20 #include "detail/pointer_to_other.hpp"\r
  21 #include "detail/rbtree_node.hpp"\r
  22 #include "rbtree_algorithms.hpp"\r
  23 #include "linking_policy.hpp"\r
  24 #include <boost/get_pointer.hpp>\r
  25 #include <stdexcept>\r
  26 \r
  27 namespace boost {\r
  28 namespace intrusive {\r
  29 \r
  30 //! Derive a class from iset_base_hook in order to store objects in \r
  31 //! in an iset/imultiset. iset_base_hook holds the data necessary to maintain \r
  32 //! the set/multiset and provides an appropriate value_traits class for iset/imultiset.\r
  33 //! \r
  34 //! The first integer template argument defines a tag to identify the node. \r
  35 //! The same tag value can be used in different classes, but if a class is \r
  36 //! derived from more than one iset_base_hook, then each iset_base_hook needs its \r
  37 //! unique tag.\r
  38 //!\r
  39 //! The second boolean template parameter will activate the safe-mode checks\r
  40 //! if it's configured as "true".\r
  41 //!\r
  42 //! The third argument is the pointer type that will be used internally in the hook\r
  43 //! and the iset/imultiset configured from this hook.\r
  44 template<typename Tag, bool SafeMode = true, class VoidPointer = void*>\r
  45 class iset_base_hook\r
  46    :  private detail::rbtree_node_traits<VoidPointer>::node\r
  47 {\r
  48    public:\r
  49    typedef detail::rbtree_node_traits<VoidPointer>    node_traits;\r
  50    enum { linking_policy = SafeMode? safe_mode_link : normal_link};\r
  51 \r
  52    private:\r
  53    typedef rbtree_algorithms<node_traits>     node_algorithms;\r
  54    \r
  55    public:\r
  56    typedef typename node_traits::node                 node;\r
  57    typedef typename boost::pointer_to_other\r
  58       <VoidPointer, node>::type                       node_ptr;\r
  59    typedef typename boost::pointer_to_other\r
  60       <VoidPointer, const node>::type                 const_node_ptr;\r
  61    typedef iset_base_hook\r
  62       <Tag, SafeMode, VoidPointer>                    this_type;\r
  63 \r
  64    typedef typename boost::pointer_to_other\r
  65       <VoidPointer, this_type>::type                  this_type_ptr;\r
  66 \r
  67    typedef typename boost::pointer_to_other\r
  68       <VoidPointer, const this_type>::type            const_this_type_ptr;\r
  69 \r
  70    private:\r
  71 \r
  72    node_ptr this_as_node()\r
  73    {  return node_ptr(static_cast<node *const>(this)); }\r
  74 \r
  75    const_node_ptr this_as_node() const\r
  76    {  return const_node_ptr(static_cast<const node *const>(this)); }\r
  77 \r
  78    public:\r
  79 \r
  80    //! <b>Effects</b>: If SafeMode is true initializes the node\r
  81    //!   to an unlinked state.\r
  82    //! \r
  83    //! <b>Throws</b>: Nothing. \r
  84    iset_base_hook()\r
  85       :  node()\r
  86    {\r
  87       if(SafeMode){\r
  88          node_algorithms::init(this_as_node());\r
  89       }\r
  90    }\r
  91 \r
  92    //! <b>Effects</b>: If SafeMode is true initializes the node\r
  93    //!   to an unlinked state. The argument is ignored.\r
  94    //! \r
  95    //! <b>Throws</b>: Nothing. \r
  96    //! \r
  97    //! <b>Rationale</b>: Providing a copy-constructor\r
  98    //!   makes classes using iset_base_hook STL-compliant without forcing the \r
  99    //!   user to do some additional work. "swap" can be used to emulate\r
 100    //!   move-semantics.\r
 101    iset_base_hook(const iset_base_hook& )\r
 102       :  node()\r
 103    {\r
 104       if(SafeMode){\r
 105          node_algorithms::init(this_as_node());\r
 106       }\r
 107    }\r
 108 \r
 109    //! <b>Effects</b>: If SafeMode is true, an assertion is raised\r
 110    //!   if the node is still linked. After that, the node is initialized\r
 111    //!   to an unlinked state. The argument is ignored.\r
 112    //! \r
 113    //! <b>Throws</b>: Nothing. \r
 114    //! \r
 115    //! <b>Rationale</b>: Providing an assignment operator \r
 116    //!   makes classes using iset_base_hook STL-compliant without forcing the \r
 117    //!   user to do some additional work. "swap" can be used to emulate\r
 118    //!   move-semantics.\r
 119    iset_base_hook& operator=(const iset_base_hook& ) \r
 120    {\r
 121       if(SafeMode){\r
 122          BOOST_ASSERT(!this->linked());\r
 123       }\r
 124       return *this; \r
 125    }\r
 126 \r
 127    //! <b>Effects</b>: If SafeMode is set to false, the destructor does\r
 128    //!   nothing (ie. no code is generated). If SafeMode is true and the\r
 129    //!   object is stored in an iset an assertion is raised.\r
 130    //! \r
 131    //! <b>Throws</b>: Nothing. \r
 132    ~iset_base_hook() \r
 133    {\r
 134       if(SafeMode){\r
 135          BOOST_ASSERT(!this->linked());\r
 136       }\r
 137    }\r
 138 \r
 139    //! <b>Precondition</b>: The hook must be in safe-mode.\r
 140    //!\r
 141    //! <b>Returns</b>: true, if the node belongs to a container, false\r
 142    //!   otherwise. This function can be used to test whether iset::current \r
 143    //!   will return a valid iterator. \r
 144    //!\r
 145    //! <b>Complexity</b>: Constant \r
 146    bool linked() const \r
 147    {\r
 148       //linked() can be only used in safe-mode\r
 149       BOOST_ASSERT(SafeMode);\r
 150       return !node_algorithms::unique(this_as_node()); \r
 151    }\r
 152 \r
 153    //! The value_traits class is used as the first template argument for imultiset. \r
 154    //! The template argument T defines the class type stored in imultiset. Objects \r
 155    //! of type T and of types derived from T can be stored. T don't need to be \r
 156    //! copy-constructible or assignable.\r
 157    template<class T>\r
 158    struct value_traits\r
 159       :  detail::derivation_value_traits<T, this_type, Tag>\r
 160    {};\r
 161 \r
 162    //! <b>Effects</b>: Converts a pointer to a node into\r
 163    //!   a pointer to the hook that holds that node.\r
 164    //! \r
 165    //! <b>Throws</b>: Nothing. \r
 166    static this_type_ptr to_hook_ptr(node_ptr p)\r
 167    {\r
 168       using boost::get_pointer;\r
 169       return this_type_ptr(static_cast<iset_base_hook*> (get_pointer(p))); \r
 170    }\r
 171 \r
 172    //! <b>Effects</b>: Converts a const pointer to a node stored in a container into\r
 173    //!   a const pointer to the hook that holds that node.\r
 174    //! \r
 175    //! <b>Throws</b>: Nothing. \r
 176    static const_this_type_ptr to_hook_ptr(const_node_ptr p)\r
 177    {\r
 178       using boost::get_pointer;\r
 179       return const_this_type_ptr(static_cast<const iset_base_hook*> (get_pointer(p))); \r
 180    }\r
 181 \r
 182    //! <b>Effects</b>: Returns a pointer to the node that this hook holds.\r
 183    //! \r
 184    //! <b>Throws</b>: Nothing. \r
 185    node_ptr to_node_ptr()\r
 186    { return this_as_node(); }\r
 187 \r
 188    //! <b>Effects</b>: Returns a const pointer to the node that this hook holds.\r
 189    //! \r
 190    //! <b>Throws</b>: Nothing. \r
 191    const_node_ptr to_node_ptr() const\r
 192    { return this_as_node(); }\r
 193 };\r
 194 \r
 195 //! Derive a class from iset_auto_base_hook in order to store objects in an \r
 196 //! iset/imultiset. iset_auto_base_hook holds the data necessary to maintain the \r
 197 //! set and provides an appropriate value_traits class for iset/imultiset.\r
 198 //!\r
 199 //! The difference between iset_auto_base_hook and iset_base_hook is that\r
 200 //! iset_auto_base_hook removes itself automatically from the container\r
 201 //! in the assignment operator and the destructor. It also provides a new\r
 202 //! "unlink" method so that the user can unlink its class without using\r
 203 //! the container.\r
 204 //!\r
 205 //! iset_auto_base_hook can only be used with non constant-time iset/imultisets.\r
 206 //! \r
 207 //! The first integer template argument defines a tag to identify the node. \r
 208 //! The same tag value can be used in different classes, but if a class is \r
 209 //! derived from more than one iset_auto_base_hook, then each iset_auto_base_hook needs its \r
 210 //! unique tag.\r
 211 //!\r
 212 //! The second argument is the pointer type that will be used internally in the hook\r
 213 //! and the iset/multiset configured from this hook.\r
 214 template<typename Tag, class VoidPointer = void*>\r
 215 class iset_auto_base_hook\r
 216    :  private detail::rbtree_node_traits<VoidPointer>::node\r
 217 {\r
 218    public:\r
 219    typedef detail::rbtree_node_traits<VoidPointer>    node_traits;\r
 220    enum { linking_policy = auto_unlink  };\r
 221 \r
 222    private:\r
 223    typedef rbtree_algorithms<node_traits>     node_algorithms;\r
 224 \r
 225    public:\r
 226    typedef typename node_traits::node                 node;\r
 227    typedef typename boost::pointer_to_other\r
 228       <VoidPointer, node>::type                       node_ptr;\r
 229    typedef typename boost::pointer_to_other\r
 230       <VoidPointer, const node>::type                 const_node_ptr;\r
 231    typedef iset_auto_base_hook\r
 232       <Tag, VoidPointer>                              this_type;\r
 233 \r
 234    typedef typename boost::pointer_to_other\r
 235       <VoidPointer, this_type>::type                  this_type_ptr;\r
 236 \r
 237    typedef typename boost::pointer_to_other\r
 238       <VoidPointer, const this_type>::type            const_this_type_ptr;\r
 239 \r
 240    private:\r
 241    node_ptr this_as_node()\r
 242    {  return node_ptr(static_cast<node *const>(this)); }\r
 243 \r
 244    const_node_ptr this_as_node() const\r
 245    {  return const_node_ptr(static_cast<const node *const>(this)); }\r
 246 \r
 247    public:\r
 248 \r
 249    //! <b>Effects</b>: Initializes the node\r
 250    //!   to an unlinked state.\r
 251    //! \r
 252    //! <b>Throws</b>: Nothing. \r
 253    iset_auto_base_hook()\r
 254       :  node()\r
 255    {  node_algorithms::init(this_as_node());   }\r
 256 \r
 257    //! <b>Effects</b>: Initializes the node\r
 258    //!   to an unlinked state. The argument is ignored.\r
 259    //! \r
 260    //! <b>Throws</b>: Nothing. \r
 261    //! \r
 262    //! <b>Rationale</b>: Providing a copy-constructor\r
 263    //!   makes classes using iset_auto_base_hook STL-compliant without forcing the \r
 264    //!   user to do some additional work.\r
 265    iset_auto_base_hook(const iset_auto_base_hook& ) \r
 266       :  node()\r
 267    {  node_algorithms::init(this_as_node());   }\r
 268 \r
 269    //! <b>Effects</b>: Removes the node if it's inserted in a container.\r
 270    //!   The argument is ignored.\r
 271    //! \r
 272    //! <b>Throws</b>: Nothing. \r
 273    //! \r
 274    //! <b>Rationale</b>: Providing an assignment operator \r
 275    //!   makes classes using iset_auto_base_hook STL-compliant without forcing the \r
 276    //!   user to do some additional work.\r
 277    iset_auto_base_hook& operator=(const iset_auto_base_hook& ) \r
 278    {  this->unlink(); return *this;  }\r
 279 \r
 280    //! <b>Effects</b>: Removes the node if it's inserted in a container.\r
 281    //! \r
 282    //! <b>Throws</b>: Nothing. \r
 283    ~iset_auto_base_hook() \r
 284    {  this->unlink();  }\r
 285 \r
 286    //! <b>Effects</b>: Swapping two nodes swaps the position of the elements \r
 287    //!   related to those nodes in one or two containers. That is, if the node \r
 288    //!   this is part of the element e1, the node x is part of the element e2 \r
 289    //!   and both elements are included in the containers s1 and s2, then after \r
 290    //!   the swap-operation e1 is in s2 at the position of e2 and e2 is in s1 \r
 291    //!   at the position of e1. If one element is not in a container, then \r
 292    //!   after the swap-operation the other element is not in a container. \r
 293    //!   Iterators to e1 and e2 related to those nodes are invalidated. \r
 294    //!\r
 295    //! <b>Complexity</b>: Constant \r
 296    //!\r
 297    //! <b>Throws</b>: Nothing. \r
 298    void swap_nodes(iset_auto_base_hook& other) \r
 299    { node_algorithms::swap_nodes(this_as_node(), other.this_as_node()); }\r
 300 \r
 301    //! <b>Returns</b>: true, if the node belongs to a container, false\r
 302    //!   otherwise. This function can be used to test whether iset::current \r
 303    //!   will return a valid iterator. \r
 304    //!\r
 305    //! <b>Complexity</b>: Constant \r
 306    bool linked() const \r
 307    {  return !node_algorithms::unique(this_as_node());  }\r
 308 \r
 309    //! <b>Effects</b>: Removes the node if it's inserted in a container.\r
 310    //! \r
 311    //! <b>Throws</b>: Nothing. \r
 312    void unlink()\r
 313    {\r
 314       node_algorithms::unlink_and_rebalance(this_as_node());\r
 315       node_algorithms::init(this_as_node());\r
 316    }\r
 317 \r
 318    //! The value_traits class is used as the first template argument for iset. \r
 319    //! The template argument T defines the class type stored in iset. Objects \r
 320    //! of type T and of types derived from T can be stored. T doesn't need to be \r
 321    //! copy-constructible or assignable.\r
 322    template<class T>\r
 323    struct value_traits\r
 324       : detail::derivation_value_traits<T, this_type, Tag>\r
 325    {};\r
 326 \r
 327    //! <b>Effects</b>: Converts a pointer to a node into\r
 328    //!   a pointer to the hook that holds that node.\r
 329    //! \r
 330    //! <b>Throws</b>: Nothing. \r
 331    static this_type_ptr to_hook_ptr(node_ptr p)\r
 332    {\r
 333       using boost::get_pointer;\r
 334       return this_type_ptr(static_cast<iset_auto_base_hook*> (get_pointer(p))); \r
 335    }\r
 336 \r
 337    //! <b>Effects</b>: Converts a const pointer to a node stored in a container into\r
 338    //!   a const pointer to the hook that holds that node.\r
 339    //! \r
 340    //! <b>Throws</b>: Nothing. \r
 341    static const_this_type_ptr to_hook_ptr(const_node_ptr p)\r
 342    {\r
 343       using boost::get_pointer;\r
 344       return const_this_type_ptr(static_cast<const iset_auto_base_hook*> (get_pointer(p))); \r
 345    }\r
 346 \r
 347    //! <b>Effects</b>: Returns a pointer to the node that this hook holds.\r
 348    //! \r
 349    //! <b>Throws</b>: Nothing. \r
 350    node_ptr to_node_ptr()\r
 351    { return this_as_node(); }\r
 352 \r
 353    //! <b>Effects</b>: Returns a const pointer to the node that this hook holds.\r
 354    //! \r
 355    //! <b>Throws</b>: Nothing. \r
 356    const_node_ptr to_node_ptr() const\r
 357    { return this_as_node(); }\r
 358 };\r
 359 \r
 360 \r
 361 //! Put a public data member iset_member_hook in order to store objects of this class in\r
 362 //! an iset/imultiset. iset_member_hook holds the data necessary for maintaining the\r
 363 //! set/multiset and provides an appropriate value_traits class for iset/imultiset.\r
 364 //! \r
 365 //! The template argument T defines the class type stored in iset/imultiset. Objects of \r
 366 //! type T and of types derived from T can be stored. T doesn't need to be \r
 367 //! copy-constructible or assignable.\r
 368 //! \r
 369 //! The second boolean template parameter will activate the safe-mode checks\r
 370 //! if it's configured as "true".\r
 371 //!\r
 372 //! The third argument is the pointer type that will be used internally in the hook\r
 373 //! and the iset/imultiset configured from this hook.\r
 374 template<class T, bool SafeMode = true, class VoidPointer = void*>\r
 375 class iset_member_hook\r
 376    :  private detail::rbtree_node_traits<VoidPointer>::node\r
 377 {\r
 378    public:\r
 379    typedef detail::rbtree_node_traits<VoidPointer>       node_traits;\r
 380    enum { linking_policy = SafeMode? safe_mode_link : normal_link};\r
 381 \r
 382    private:\r
 383    typedef rbtree_algorithms<node_traits>                node_algorithms;\r
 384 \r
 385    public:\r
 386    typedef typename node_traits::node                 node;\r
 387    typedef typename boost::pointer_to_other\r
 388       <VoidPointer, node>::type                       node_ptr;\r
 389    typedef typename boost::pointer_to_other\r
 390       <VoidPointer, const node>::type                 const_node_ptr;\r
 391    typedef iset_member_hook\r
 392       <T, SafeMode, VoidPointer>                      this_type;\r
 393 \r
 394    typedef typename boost::pointer_to_other\r
 395       <VoidPointer, this_type >::type                 this_type_ptr;\r
 396 \r
 397    typedef typename boost::pointer_to_other\r
 398       <VoidPointer, const this_type >::type           const_this_type_ptr;\r
 399 \r
 400    private:\r
 401    node_ptr this_as_node()\r
 402    {  return node_ptr(static_cast<node *const>(this)); }\r
 403 \r
 404    const_node_ptr this_as_node() const\r
 405    {  return const_node_ptr(static_cast<const node *const>(this)); }\r
 406 \r
 407    public:\r
 408    //! <b>Effects</b>: If SafeMode is true initializes the node\r
 409    //!   to an unlinked state.\r
 410    //! \r
 411    //! <b>Throws</b>: Nothing. \r
 412    iset_member_hook()\r
 413       :  node()\r
 414    {\r
 415       if(SafeMode){\r
 416          node_algorithms::init(this_as_node());\r
 417       }\r
 418    }\r
 419 \r
 420    //! <b>Effects</b>: If SafeMode is true initializes the node\r
 421    //!   to an unlinked state. The argument is ignored.\r
 422    //! \r
 423    //! <b>Throws</b>: Nothing. \r
 424    //! \r
 425    //! <b>Rationale</b>: Providing a copy-constructor\r
 426    //!   makes classes using iset_member_hook STL-compliant without forcing the \r
 427    //!   user to do some additional work.\r
 428    iset_member_hook(const iset_member_hook& )\r
 429       :  node()\r
 430    {\r
 431       if(SafeMode){\r
 432          node_algorithms::init(this_as_node());\r
 433       }\r
 434    }\r
 435 \r
 436    //! <b>Effects</b>: If SafeMode is true, an assertion is raised\r
 437    //!   if the node is still linked. After that, the node is initialized\r
 438    //!   to an unlinked state. The argument is ignored.\r
 439    //! \r
 440    //! <b>Throws</b>: Nothing. \r
 441    //! \r
 442    //! <b>Rationale</b>: Providing an assignment operator \r
 443    //!   makes classes using iset_member_hook STL-compliant without forcing the \r
 444    //!   user to do some additional work.\r
 445    iset_member_hook& operator=(const iset_member_hook& ) \r
 446    {\r
 447       if(SafeMode){\r
 448          BOOST_ASSERT(!this->linked());\r
 449       }\r
 450       return *this;\r
 451    }\r
 452 \r
 453    //! <b>Effects</b>: If SafeMode is set to false, the destructor does\r
 454    //!   nothing (ie. no code is generated). Otherwise, if the object is \r
 455    //!   stored in an imultiset using the appropriate node, the object is removed \r
 456    //!   from that imultiset.\r
 457    //! \r
 458    //! <b>Throws</b>: Nothing. \r
 459    ~iset_member_hook() \r
 460    { \r
 461       if(SafeMode){\r
 462          BOOST_ASSERT(!this->linked());\r
 463       }\r
 464    }\r
 465 \r
 466    //! <b>Returns</b>: true, if the node belongs to a container, false\r
 467    //!   otherwise. This function can be used to test whether iset::current \r
 468    //!   will return a valid iterator. \r
 469    //!\r
 470    //! <b>Complexity</b>: Constant\r
 471    bool linked() const \r
 472    {\r
 473       //We must be in safe-mode to know if we are really linked\r
 474       //Otherwise, this would lead to an unknown state\r
 475       BOOST_ASSERT(SafeMode);\r
 476       return !node_algorithms::unique(this_as_node());\r
 477    }\r
 478 \r
 479    //! The value_traits class is used as the first template argument for imultiset. \r
 480    //! The template argument is a pointer to member pointing to the node in \r
 481    //! the class. Objects of type T and of types derived from T can be stored. \r
 482    //! T don't need to be copy-constructible or assignable.\r
 483    template<this_type T::* P>\r
 484    struct value_traits\r
 485       :  detail::member_value_traits<T, this_type, P>\r
 486    {};\r
 487 \r
 488    //! <b>Effects</b>: Converts a pointer to a node into\r
 489    //!   a pointer to the hook that holds that node.\r
 490    //! \r
 491    //! <b>Throws</b>: Nothing. \r
 492    static this_type_ptr to_hook_ptr(node_ptr p)\r
 493    {\r
 494       using boost::get_pointer;\r
 495       return this_type_ptr(static_cast<this_type*> (get_pointer(p))); \r
 496    }\r
 497 \r
 498    //! <b>Effects</b>: Converts a const pointer to a node stored in a container into\r
 499    //!   a const pointer to the hook that holds that node.\r
 500    //! \r
 501    //! <b>Throws</b>: Nothing. \r
 502    static const_this_type_ptr to_hook_ptr(const_node_ptr p)\r
 503    {\r
 504       using boost::get_pointer;\r
 505       return const_this_type_ptr(static_cast<const this_type*> (get_pointer(p))); \r
 506    }\r
 507 \r
 508    //! <b>Effects</b>: Returns a pointer to the node that this hook holds.\r
 509    //! \r
 510    //! <b>Throws</b>: Nothing. \r
 511    node_ptr to_node_ptr()\r
 512    { return this_as_node(); }\r
 513 \r
 514    //! <b>Effects</b>: Returns a const pointer to the node that this hook holds.\r
 515    //! \r
 516    //! <b>Throws</b>: Nothing. \r
 517    const_node_ptr to_node_ptr() const\r
 518    { return this_as_node(); }\r
 519 };\r
 520 \r
 521 //! Put a public data member iset_auto_member_hook in order to store objects of this \r
 522 //! class in an iset/imultiset. iset_auto_member_hook holds the data necessary for\r
 523 //! maintaining the set/multiset and provides an appropriate value_traits class for\r
 524 //! iset/imultiset.\r
 525 //!\r
 526 //! The difference between iset_auto_member_hook and iset_member_hook is that\r
 527 //! iset_auto_member_hook removes itself automatically from the container\r
 528 //! in the assignment operator and the destructor. It also provides a new\r
 529 //! "unlink" method so that the user can unlink its class without using\r
 530 //! the container.\r
 531 //!\r
 532 //! iset_auto_member_hook can only be used with non constant-time iset/imultisets.\r
 533 //! \r
 534 //! The first template argument T defines the class type stored in iset/imultisets.\r
 535 //! Objects of type T and of types derived from T can be stored. T doesn't need to \r
 536 //! be copy-constructible or assignable.\r
 537 //!\r
 538 //! The second argument is the pointer type that will be used internally in the hook\r
 539 //! and the iset/imultiset configured from this hook.\r
 540 template<class T, class VoidPointer = void *>\r
 541 class iset_auto_member_hook\r
 542    :  private detail::rbtree_node_traits<VoidPointer>::node\r
 543 {\r
 544    public:\r
 545    typedef detail::rbtree_node_traits<VoidPointer>      node_traits;\r
 546    enum { linking_policy = auto_unlink  };\r
 547 \r
 548    private:\r
 549    typedef rbtree_algorithms<node_traits>             node_algorithms;\r
 550 \r
 551    public:\r
 552    typedef typename node_traits::node                 node;\r
 553    typedef typename boost::pointer_to_other\r
 554       <VoidPointer, node>::type                       node_ptr;\r
 555    typedef typename boost::pointer_to_other\r
 556       <VoidPointer, const node>::type                 const_node_ptr;\r
 557    typedef iset_auto_member_hook\r
 558       <T, VoidPointer>                                this_type;\r
 559 \r
 560    typedef typename boost::pointer_to_other\r
 561       <VoidPointer, this_type >::type                 this_type_ptr;\r
 562 \r
 563    typedef typename boost::pointer_to_other\r
 564       <VoidPointer, const this_type >::type           const_this_type_ptr;\r
 565 \r
 566    private:\r
 567    node_ptr this_as_node()\r
 568    {  return node_ptr(static_cast<node *const>(this)); }\r
 569 \r
 570    const_node_ptr this_as_node() const\r
 571    {  return const_node_ptr(static_cast<const node *const>(this)); }\r
 572 \r
 573    public:\r
 574    //! <b>Effects</b>: Initializes the node\r
 575    //!   to an unlinked state.\r
 576    //! \r
 577    //! <b>Throws</b>: Nothing. \r
 578    iset_auto_member_hook()\r
 579       :  node()\r
 580    {  node_algorithms::init(this_as_node());   }\r
 581 \r
 582    //! <b>Effects</b>: Initializes the node\r
 583    //!   to an unlinked state. The argument is ignored.\r
 584    //! \r
 585    //! <b>Throws</b>: Nothing. \r
 586    //! \r
 587    //! <b>Rationale</b>: Providing a copy-constructor\r
 588    //!   makes classes using iset_auto_base_hook STL-compliant without forcing the \r
 589    //!   user to do some additional work.\r
 590    iset_auto_member_hook(const iset_auto_member_hook& ) \r
 591       :  node()\r
 592    {  node_algorithms::init(this_as_node());   }\r
 593 \r
 594    //! <b>Effects</b>: Removes the node if it's inserted in a container.\r
 595    //!   The argument is ignored.\r
 596    //! \r
 597    //! <b>Throws</b>: Nothing. \r
 598    //! \r
 599    //! <b>Rationale</b>: Providing an assignment operator \r
 600    //!   makes classes using iset_auto_base_hook STL-compliant without forcing the \r
 601    //!   user to do some additional work.\r
 602    iset_auto_member_hook& operator=(const iset_auto_member_hook& )\r
 603    {  this->unlink(); return *this;  }\r
 604 \r
 605    //! <b>Effects</b>: Removes the node if it's inserted in a container.\r
 606    //! \r
 607    //! <b>Throws</b>: Nothing. \r
 608    ~iset_auto_member_hook()\r
 609    {  this->unlink();  }\r
 610 \r
 611    //! <b>Effects</b>: Swapping two nodes swaps the position of the elements \r
 612    //!   related to those nodes in one or two containers. That is, if the node \r
 613    //!   this is part of the element e1, the node x is part of the element e2 \r
 614    //!   and both elements are included in the containers s1 and s2, then after \r
 615    //!   the swap-operation e1 is in s2 at the position of e2 and e2 is in s1 \r
 616    //!   at the position of e1. If one element is not in a container, then \r
 617    //!   after the swap-operation the other element is not in a container. \r
 618    //!   Iterators to e1 and e2 related to those nodes are invalidated. \r
 619    //!\r
 620    //! <b>Complexity</b>: Constant \r
 621    //!\r
 622    //! <b>Throws</b>: Nothing.\r
 623    void swap_nodes(iset_auto_member_hook& other) \r
 624    { node_algorithms::swap_nodes(this_as_node(), other.this_as_node()); }\r
 625 \r
 626    //! <b>Returns</b>: true, if the node belongs to a container, false\r
 627    //!   otherwise. This function can be used to test whether iset::current \r
 628    //!   will return a valid iterator. \r
 629    //!\r
 630    //! <b>Complexity</b>: Constant \r
 631    bool linked() const \r
 632    {  return !node_algorithms::unique(this_as_node());  }\r
 633 \r
 634    //! The value_traits class is used as the first template argument for iset. \r
 635    //! The template argument is a pointer to member pointing to the node in \r
 636    //! the class. Objects of type T and of types derived from T can be stored. \r
 637    //! T doesn't need to be copy-constructible or assignable.\r
 638    template<this_type T::* M>\r
 639    struct value_traits\r
 640       : detail::member_value_traits<T, this_type, M>\r
 641    {};\r
 642 \r
 643    //! <b>Effects</b>: Removes the node if it's inserted in a container.\r
 644    //! \r
 645    //! <b>Throws</b>: Nothing. \r
 646    void unlink()\r
 647    {\r
 648       node_algorithms::unlink_and_rebalance(this_as_node());\r
 649       node_algorithms::init(this_as_node());\r
 650    }\r
 651 \r
 652    //! <b>Effects</b>: Converts a pointer to a node into\r
 653    //!   a pointer to the hook that holds that node.\r
 654    //! \r
 655    //! <b>Throws</b>: Nothing. \r
 656    static this_type_ptr to_hook_ptr(node_ptr p)\r
 657    {\r
 658       using boost::get_pointer;\r
 659       return this_type_ptr(static_cast<this_type*> (get_pointer(p))); \r
 660    }\r
 661 \r
 662    //! <b>Effects</b>: Converts a const pointer to a node stored in a container into\r
 663    //!   a const pointer to the hook that holds that node.\r
 664    //! \r
 665    //! <b>Throws</b>: Nothing. \r
 666    static const_this_type_ptr to_hook_ptr(const_node_ptr p)\r
 667    {\r
 668       using boost::get_pointer;\r
 669       return const_this_type_ptr(static_cast<const this_type*> (get_pointer(p))); \r
 670    }\r
 671 \r
 672    //! <b>Effects</b>: Returns a pointer to the node that this hook holds.\r
 673    //! \r
 674    //! <b>Throws</b>: Nothing. \r
 675    node_ptr to_node_ptr()\r
 676    { return this_as_node(); }\r
 677 \r
 678    //! <b>Effects</b>: Returns a const pointer to the node that this hook holds.\r
 679    //! \r
 680    //! <b>Throws</b>: Nothing. \r
 681    const_node_ptr to_node_ptr() const\r
 682    { return this_as_node(); }\r
 683 };\r
 684 \r
 685 } //namespace intrusive \r
 686 } //namespace boost \r
 687 \r
 688 #include "detail/config_end.hpp"\r
 689 \r
 690 #endif //BOOST_INTRUSIVE_ISET_HOOK_HPP\r