boost/intrusive/splay_set_hook.hpp

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