1 ///////////////////////////////////////////////////////////////////////////// 2 // 3 // (C) Copyright Ion Gaztanaga 2007-2013 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 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 #if defined(BOOST_HAS_PRAGMA_ONCE) 25 # pragma once 26 #endif 27 28 namespace boost { 29 namespace intrusive { 30 31 //! Helper metafunction to define a \c avl_set_base_hook that yields to the same 32 //! type when the same options (either explicitly or implicitly) are used. 33 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 34 template<class ...Options> 35 #else 36 template<class O1 = void, class O2 = void, class O3 = void, class O4 = void> 37 #endif 38 struct make_avl_set_base_hook 39 { 40 /// @cond 41 typedef typename pack_options 42 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 43 <hook_defaults, O1, O2, O3, O4> 44 #else 45 <hook_defaults, Options...> 46 #endif 47 ::type packed_options; 48 49 typedef generic_hook 50 < AvlTreeAlgorithms 51 , avltree_node_traits<typename packed_options::void_pointer, packed_options::optimize_size> 52 , typename packed_options::tag 53 , packed_options::link_mode 54 , AvlTreeBaseHookId 55 > implementation_defined; 56 /// @endcond 57 typedef implementation_defined type; 58 }; 59 60 //! Derive a class from avl_set_base_hook in order to store objects in 61 //! in an avl_set/avl_multiset. avl_set_base_hook holds the data necessary to maintain 62 //! the avl_set/avl_multiset and provides an appropriate value_traits class for avl_set/avl_multiset. 63 //! 64 //! The hook admits the following options: \c tag<>, \c void_pointer<>, 65 //! \c link_mode<> and \c optimize_size<>. 66 //! 67 //! \c tag<> defines a tag to identify the node. 68 //! The same tag value can be used in different classes, but if a class is 69 //! derived from more than one \c list_base_hook, then each \c list_base_hook needs its 70 //! unique tag. 71 //! 72 //! \c void_pointer<> is the pointer type that will be used internally in the hook 73 //! and the container configured to use this hook. 74 //! 75 //! \c link_mode<> will specify the linking mode of the hook (\c normal_link, 76 //! \c auto_unlink or \c safe_link). 77 //! 78 //! \c optimize_size<> will tell the hook to optimize the hook for size instead 79 //! of speed. 80 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 81 template<class ...Options> 82 #else 83 template<class O1, class O2, class O3, class O4> 84 #endif 85 class avl_set_base_hook 86 : public make_avl_set_base_hook 87 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 88 <O1, O2, O3, O4> 89 #else 90 <Options...> 91 #endif 92 ::type 93 { 94 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) 95 public: 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 avl_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 avl_set_base_hook(const avl_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 avl_set_base_hook& operator=(const avl_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 ~avl_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(avl_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 avl_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 = void, class O2 = void, class O3 = void, class O4 = void> 168 #endif 169 struct make_avl_set_member_hook 170 { 171 /// @cond 172 typedef typename pack_options 173 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 174 <hook_defaults, O1, O2, O3, O4> 175 #else 176 <hook_defaults, Options...> 177 #endif 178 ::type packed_options; 179 180 typedef generic_hook 181 < AvlTreeAlgorithms 182 , avltree_node_traits<typename packed_options::void_pointer, packed_options::optimize_size> 183 , member_tag 184 , packed_options::link_mode 185 , NoBaseHookId 186 > implementation_defined; 187 /// @endcond 188 typedef implementation_defined type; 189 }; 190 191 //! Put a public data member avl_set_member_hook in order to store objects of this class in 192 //! an avl_set/avl_multiset. avl_set_member_hook holds the data necessary for maintaining the 193 //! avl_set/avl_multiset and provides an appropriate value_traits class for avl_set/avl_multiset. 194 //! 195 //! The hook admits the following options: \c void_pointer<>, 196 //! \c link_mode<> and \c optimize_size<>. 197 //! 198 //! \c void_pointer<> is the pointer type that will be used internally in the hook 199 //! and the container configured to use this hook. 200 //! 201 //! \c link_mode<> will specify the linking mode of the hook (\c normal_link, 202 //! \c auto_unlink or \c safe_link). 203 //! 204 //! \c optimize_size<> will tell the hook to optimize the hook for size instead 205 //! of speed. 206 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 207 template<class ...Options> 208 #else 209 template<class O1, class O2, class O3, class O4> 210 #endif 211 class avl_set_member_hook 212 : public make_avl_set_member_hook 213 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 214 <O1, O2, O3, O4> 215 #else 216 <Options...> 217 #endif 218 ::type 219 { 220 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) 221 public: 222 //! <b>Effects</b>: If link_mode is \c auto_unlink or \c safe_link 223 //! initializes the node to an unlinked state. 224 //! 225 //! <b>Throws</b>: Nothing. 226 avl_set_member_hook(); 227 228 //! <b>Effects</b>: If link_mode is \c auto_unlink or \c safe_link 229 //! initializes the node to an unlinked state. The argument is ignored. 230 //! 231 //! <b>Throws</b>: Nothing. 232 //! 233 //! <b>Rationale</b>: Providing a copy-constructor 234 //! makes classes using the hook STL-compliant without forcing the 235 //! user to do some additional work. \c swap can be used to emulate 236 //! move-semantics. 237 avl_set_member_hook(const avl_set_member_hook& ); 238 239 //! <b>Effects</b>: Empty function. The argument is ignored. 240 //! 241 //! <b>Throws</b>: Nothing. 242 //! 243 //! <b>Rationale</b>: Providing an assignment operator 244 //! makes classes using the hook STL-compliant without forcing the 245 //! user to do some additional work. \c swap can be used to emulate 246 //! move-semantics. 247 avl_set_member_hook& operator=(const avl_set_member_hook& ); 248 249 //! <b>Effects</b>: If link_mode is \c normal_link, the destructor does 250 //! nothing (ie. no code is generated). If link_mode is \c safe_link and the 251 //! object is stored in a set an assertion is raised. If link_mode is 252 //! \c auto_unlink and \c is_linked() is true, the node is unlinked. 253 //! 254 //! <b>Throws</b>: Nothing. 255 ~avl_set_member_hook(); 256 257 //! <b>Effects</b>: Swapping two nodes swaps the position of the elements 258 //! related to those nodes in one or two containers. That is, if the node 259 //! this is part of the element e1, the node x is part of the element e2 260 //! and both elements are included in the containers s1 and s2, then after 261 //! the swap-operation e1 is in s2 at the position of e2 and e2 is in s1 262 //! at the position of e1. If one element is not in a container, then 263 //! after the swap-operation the other element is not in a container. 264 //! Iterators to e1 and e2 related to those nodes are invalidated. 265 //! 266 //! <b>Complexity</b>: Constant 267 //! 268 //! <b>Throws</b>: Nothing. 269 void swap_nodes(avl_set_member_hook &other); 270 271 //! <b>Precondition</b>: link_mode must be \c safe_link or \c auto_unlink. 272 //! 273 //! <b>Returns</b>: true, if the node belongs to a container, false 274 //! otherwise. This function can be used to test whether \c set::iterator_to 275 //! will return a valid iterator. 276 //! 277 //! <b>Complexity</b>: Constant 278 bool is_linked() const; 279 280 //! <b>Effects</b>: Removes the node if it's inserted in a container. 281 //! This function is only allowed if link_mode is \c auto_unlink. 282 //! 283 //! <b>Throws</b>: Nothing. 284 void unlink(); 285 #endif 286 }; 287 288 } //namespace intrusive 289 } //namespace boost 290 291 #include <boost/intrusive/detail/config_end.hpp> 292 293 #endif //BOOST_INTRUSIVE_AVL_SET_HOOK_HPP 294