boost/intrusive/splay_set_hook.hpp

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