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 | |