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