boost/intrusive/avl_set_hook.hpp

   1 /////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Ion Gaztanaga 2007-2008
   4 //
   5 // Distributed under the Boost Software License, Version 1.0.
   6 //    (See accompanying file LICENSE_1_0.txt or copy at
   7 //          http://www.boost.org/LICENSE_1_0.txt)
   8 //
   9 // See http://www.boost.org/libs/intrusive for documentation.
  10 //
  11 /////////////////////////////////////////////////////////////////////////////
  12
  13 #ifndef BOOST_INTRUSIVE_AVL_SET_HOOK_HPP
  14 #define BOOST_INTRUSIVE_AVL_SET_HOOK_HPP
  15
  16 #include <boost/intrusive/detail/config_begin.hpp>
  17 #include <boost/intrusive/intrusive_fwd.hpp>
  18 #include <boost/intrusive/detail/utilities.hpp>
  19 #include <boost/intrusive/detail/avltree_node.hpp>
  20 #include <boost/intrusive/avltree_algorithms.hpp>
  21 #include <boost/intrusive/options.hpp>
  22 #include <boost/intrusive/detail/generic_hook.hpp>
  23
  24 namespace boost {
  25 namespace intrusive {
  26
  27 /// @cond
  28 template<class VoidPointer, bool OptimizeSize = false>
  29 struct get_avl_set_node_algo
  30 {
  31    typedef avltree_algorithms<avltree_node_traits<VoidPointer, OptimizeSize> > type;
  32 };
  33 /// @endcond
  34
  35 //! Helper metafunction to define a \c avl_set_base_hook that yields to the same
  36 //! type when the same options (either explicitly or implicitly) are used.
  37 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
  38 template<class ...Options>
  39 #else
  40 template<class O1 = none, class O2 = none, class O3 = none, class O4 = none>
  41 #endif
  42 struct make_avl_set_base_hook
  43 {
  44    /// @cond
  45    typedef typename pack_options
  46       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
  47       <hook_defaults, O1, O2, O3, O4>
  48       #else
  49       <hook_defaults, Options...>
  50       #endif
  51       ::type packed_options;
  52
  53    typedef detail::generic_hook
  54    < get_avl_set_node_algo<typename packed_options::void_pointer
  55                       ,packed_options::optimize_size>
  56    , typename packed_options::tag
  57    , packed_options::link_mode
  58    , detail::AvlSetBaseHook
  59    > implementation_defined;
  60    /// @endcond
  61    typedef implementation_defined type;
  62 };
  63
  64 //! Derive a class from avl_set_base_hook in order to store objects in
  65 //! in an avl_set/avl_multiset. avl_set_base_hook holds the data necessary to maintain
  66 //! the avl_set/avl_multiset and provides an appropriate value_traits class for avl_set/avl_multiset.
  67 //!
  68 //! The hook admits the following options: \c tag<>, \c void_pointer<>,
  69 //! \c link_mode<> and \c optimize_size<>.
  70 //!
  71 //! \c tag<> defines a tag to identify the node.
  72 //! The same tag value can be used in different classes, but if a class is
  73 //! derived from more than one \c list_base_hook, then each \c list_base_hook needs its
  74 //! unique tag.
  75 //!
  76 //! \c void_pointer<> is the pointer type that will be used internally in the hook
  77 //! and the the container configured to use this hook.
  78 //!
  79 //! \c link_mode<> will specify the linking mode of the hook (\c normal_link,
  80 //! \c auto_unlink or \c safe_link).
  81 //!
  82 //! \c optimize_size<> will tell the hook to optimize the hook for size instead
  83 //! of speed.
  84 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
  85 template<class ...Options>
  86 #else
  87 template<class O1, class O2, class O3, class O4>
  88 #endif
  89 class avl_set_base_hook
  90    :  public make_avl_set_base_hook
  91       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
  92       <O1, O2, O3, O4>
  93       #else
  94       <Options...>
  95       #endif
  96       ::type
  97 {
  98    #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
  99    //! <b>Effects</b>: If link_mode is \c auto_unlink or \c safe_link
 100    //!   initializes the node to an unlinked state.
 101    //!
 102    //! <b>Throws</b>: Nothing.
 103    avl_set_base_hook();
 104
 105    //! <b>Effects</b>: If link_mode is \c auto_unlink or \c safe_link
 106    //!   initializes the node to an unlinked state. The argument is ignored.
 107    //!
 108    //! <b>Throws</b>: Nothing.
 109    //!
 110    //! <b>Rationale</b>: Providing a copy-constructor
 111    //!   makes classes using the hook STL-compliant without forcing the
 112    //!   user to do some additional work. \c swap can be used to emulate
 113    //!   move-semantics.
 114    avl_set_base_hook(const avl_set_base_hook& );
 115
 116    //! <b>Effects</b>: Empty function. The argument is ignored.
 117    //!
 118    //! <b>Throws</b>: Nothing.
 119    //!
 120    //! <b>Rationale</b>: Providing an assignment operator
 121    //!   makes classes using the hook STL-compliant without forcing the
 122    //!   user to do some additional work. \c swap can be used to emulate
 123    //!   move-semantics.
 124    avl_set_base_hook& operator=(const avl_set_base_hook& );
 125
 126    //! <b>Effects</b>: If link_mode is \c normal_link, the destructor does
 127    //!   nothing (ie. no code is generated). If link_mode is \c safe_link and the
 128    //!   object is stored in a set an assertion is raised. If link_mode is
 129    //!   \c auto_unlink and \c is_linked() is true, the node is unlinked.
 130    //!
 131    //! <b>Throws</b>: Nothing.
 132    ~avl_set_base_hook();
 133
 134    //! <b>Effects</b>: Swapping two nodes swaps the position of the elements
 135    //!   related to those nodes in one or two containers. That is, if the node
 136    //!   this is part of the element e1, the node x is part of the element e2
 137    //!   and both elements are included in the containers s1 and s2, then after
 138    //!   the swap-operation e1 is in s2 at the position of e2 and e2 is in s1
 139    //!   at the position of e1. If one element is not in a container, then
 140    //!   after the swap-operation the other element is not in a container.
 141    //!   Iterators to e1 and e2 related to those nodes are invalidated.
 142    //!
 143    //! <b>Complexity</b>: Constant
 144    //!
 145    //! <b>Throws</b>: Nothing.
 146    void swap_nodes(avl_set_base_hook &other);
 147
 148    //! <b>Precondition</b>: link_mode must be \c safe_link or \c auto_unlink.
 149    //!
 150    //! <b>Returns</b>: true, if the node belongs to a container, false
 151    //!   otherwise. This function can be used to test whether \c set::iterator_to
 152    //!   will return a valid iterator.
 153    //!
 154    //! <b>Complexity</b>: Constant
 155    bool is_linked() const;
 156
 157    //! <b>Effects</b>: Removes the node if it's inserted in a container.
 158    //!   This function is only allowed if link_mode is \c auto_unlink.
 159    //!
 160    //! <b>Throws</b>: Nothing.
 161    void unlink();
 162    #endif
 163 };
 164
 165 //! Helper metafunction to define a \c avl_set_member_hook that yields to the same
 166 //! type when the same options (either explicitly or implicitly) are used.
 167 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 168 template<class ...Options>
 169 #else
 170 template<class O1 = none, class O2 = none, class O3 = none, class O4 = none>
 171 #endif
 172 struct make_avl_set_member_hook
 173 {
 174    /// @cond
 175    typedef typename pack_options
 176       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 177       <hook_defaults, O1, O2, O3, O4>
 178       #else
 179       <hook_defaults, Options...>
 180       #endif
 181       ::type packed_options;
 182
 183    typedef detail::generic_hook
 184    < get_avl_set_node_algo<typename packed_options::void_pointer
 185                       ,packed_options::optimize_size>
 186    , member_tag
 187    , packed_options::link_mode
 188    , detail::NoBaseHook
 189    > implementation_defined;
 190    /// @endcond
 191    typedef implementation_defined type;
 192 };
 193
 194 //! Put a public data member avl_set_member_hook in order to store objects of this class in
 195 //! an avl_set/avl_multiset. avl_set_member_hook holds the data necessary for maintaining the
 196 //! avl_set/avl_multiset and provides an appropriate value_traits class for avl_set/avl_multiset.
 197 //!
 198 //! The hook admits the following options: \c void_pointer<>,
 199 //! \c link_mode<> and \c optimize_size<>.
 200 //!
 201 //! \c void_pointer<> is the pointer type that will be used internally in the hook
 202 //! and the the container configured to use this hook.
 203 //!
 204 //! \c link_mode<> will specify the linking mode of the hook (\c normal_link,
 205 //! \c auto_unlink or \c safe_link).
 206 //!
 207 //! \c optimize_size<> will tell the hook to optimize the hook for size instead
 208 //! of speed.
 209 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 210 template<class ...Options>
 211 #else
 212 template<class O1, class O2, class O3, class O4>
 213 #endif
 214 class avl_set_member_hook
 215    :  public make_avl_set_member_hook
 216       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 217       <O1, O2, O3, O4>
 218       #else
 219       <Options...>
 220       #endif
 221       ::type
 222 {
 223    #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
 224    //! <b>Effects</b>: If link_mode is \c auto_unlink or \c safe_link
 225    //!   initializes the node to an unlinked state.
 226    //!
 227    //! <b>Throws</b>: Nothing.
 228    avl_set_member_hook();
 229
 230    //! <b>Effects</b>: If link_mode is \c auto_unlink or \c safe_link
 231    //!   initializes the node to an unlinked state. The argument is ignored.
 232    //!
 233    //! <b>Throws</b>: Nothing.
 234    //!
 235    //! <b>Rationale</b>: Providing a copy-constructor
 236    //!   makes classes using the hook STL-compliant without forcing the
 237    //!   user to do some additional work. \c swap can be used to emulate
 238    //!   move-semantics.
 239    avl_set_member_hook(const avl_set_member_hook& );
 240
 241    //! <b>Effects</b>: Empty function. The argument is ignored.
 242    //!
 243    //! <b>Throws</b>: Nothing.
 244    //!
 245    //! <b>Rationale</b>: Providing an assignment operator
 246    //!   makes classes using the hook STL-compliant without forcing the
 247    //!   user to do some additional work. \c swap can be used to emulate
 248    //!   move-semantics.
 249    avl_set_member_hook& operator=(const avl_set_member_hook& );
 250
 251    //! <b>Effects</b>: If link_mode is \c normal_link, the destructor does
 252    //!   nothing (ie. no code is generated). If link_mode is \c safe_link and the
 253    //!   object is stored in a set an assertion is raised. If link_mode is
 254    //!   \c auto_unlink and \c is_linked() is true, the node is unlinked.
 255    //!
 256    //! <b>Throws</b>: Nothing.
 257    ~avl_set_member_hook();
 258
 259    //! <b>Effects</b>: Swapping two nodes swaps the position of the elements
 260    //!   related to those nodes in one or two containers. That is, if the node
 261    //!   this is part of the element e1, the node x is part of the element e2
 262    //!   and both elements are included in the containers s1 and s2, then after
 263    //!   the swap-operation e1 is in s2 at the position of e2 and e2 is in s1
 264    //!   at the position of e1. If one element is not in a container, then
 265    //!   after the swap-operation the other element is not in a container.
 266    //!   Iterators to e1 and e2 related to those nodes are invalidated.
 267    //!
 268    //! <b>Complexity</b>: Constant
 269    //!
 270    //! <b>Throws</b>: Nothing.
 271    void swap_nodes(avl_set_member_hook &other);
 272
 273    //! <b>Precondition</b>: link_mode must be \c safe_link or \c auto_unlink.
 274    //!
 275    //! <b>Returns</b>: true, if the node belongs to a container, false
 276    //!   otherwise. This function can be used to test whether \c set::iterator_to
 277    //!   will return a valid iterator.
 278    //!
 279    //! <b>Complexity</b>: Constant
 280    bool is_linked() const;
 281
 282    //! <b>Effects</b>: Removes the node if it's inserted in a container.
 283    //!   This function is only allowed if link_mode is \c auto_unlink.
 284    //!
 285    //! <b>Throws</b>: Nothing.
 286    void unlink();
 287    #endif
 288 };
 289
 290 } //namespace intrusive
 291 } //namespace boost
 292
 293 #include <boost/intrusive/detail/config_end.hpp>
 294
 295 #endif //BOOST_INTRUSIVE_AVL_SET_HOOK_HPP