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
28namespace boost {
29namespace 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)
34template<class ...Options>
35#else
36template<class O1 = void, class O2 = void, class O3 = void, class O4 = void>
37#endif
38struct 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)
80template<class ...Options>
81#else
82template<class O1, class O2, class O3, class O4>
83#endif
84class 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)
164template<class ...Options>
165#else
166template<class O1 = void, class O2 = void, class O3 = void, class O4 = void>
167#endif
168struct 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)
205template<class ...Options>
206#else
207template<class O1, class O2, class O3, class O4>
208#endif
209class 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

source code of boost/boost/intrusive/avl_set_hook.hpp