1 /////////////////////////////////////////////////////////////////////////////
2 //
3 // (C) Copyright Ion Gaztanaga 2013-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 #include <boost/intrusive/list.hpp>
13 #include <boost/intrusive/slist.hpp>
14 #include <boost/intrusive/set.hpp>
15 #include <boost/intrusive/unordered_set.hpp>
16 #include <boost/intrusive/avl_set.hpp>
17 #include <boost/intrusive/sg_set.hpp>
18 #include <boost/intrusive/bs_set.hpp>
19 #include <boost/intrusive/splay_set.hpp>
20 #include <boost/intrusive/treap_set.hpp>
21 #include <boost/intrusive/detail/mpl.hpp>
22 #include <boost/static_assert.hpp>
23 #include "smart_ptr.hpp"
24 #include <functional> //std::greater/std::less
25
26 using namespace boost::intrusive;
27 struct my_tag;
28
29 template<class VoidPtr = void*, link_mode_type mode = normal_link>
30 class MyClass
31 : public make_list_base_hook
32 < void_pointer<VoidPtr>, link_mode<mode> >::type
33 , public make_slist_base_hook
34 < void_pointer<VoidPtr>, link_mode<mode> >::type
35 , public make_set_base_hook
36 < void_pointer<VoidPtr>, link_mode<mode> >::type
37 , public make_unordered_set_base_hook
38 < void_pointer<VoidPtr>, link_mode<mode> >::type
39 , public make_avl_set_base_hook
40 < void_pointer<VoidPtr>, link_mode<mode> >::type
41 , public make_bs_set_base_hook
42 < void_pointer<VoidPtr>, link_mode<mode> >::type
43 {
44 int int_;
45
46 public:
MyClass(int i)47 MyClass(int i)
48 : int_(i)
49 {}
50
operator <(const MyClass & l,const MyClass & r)51 friend bool operator<(const MyClass &l, const MyClass &r)
52 { return l.int_ < r.int_; }
53
operator ==(const MyClass & l,const MyClass & r)54 friend bool operator==(const MyClass &l, const MyClass &r)
55 { return l.int_ == r.int_; }
56
hash_value(const MyClass & v)57 friend std::size_t hash_value(const MyClass &v)
58 { return boost::hash_value(v.int_); }
59
priority_order(const MyClass & l,const MyClass & r)60 friend bool priority_order(const MyClass &l, const MyClass &r)
61 { return l.int_ < r.int_; }
62 };
63
64 template<class T>
65 struct inverse_priority
66 {
operator ()inverse_priority67 bool operator()(const T &l, const T &r)
68 { return l.int_ > r.int_; }
69 };
70
71 template<class T>
72 struct inverse_hash
73 {
operator ()inverse_hash74 bool operator()(const T &l)
75 { return hash_value(l); }
76 };
77
78 template<class T>
79 struct alternative_equal
80 {
operator ()alternative_equal81 bool operator()(const T &l, const T &r)
82 { return l.int_ == r.int_; }
83 };
84
main()85 int main()
86 {
87 ////////////
88 // list
89 ////////////
90 BOOST_STATIC_ASSERT((!detail::is_same< list<MyClass<> >::iterator
91 , list<MyClass<> >::const_iterator
92 >::value));
93 //constant_time_size does not change iterator
94 BOOST_STATIC_ASSERT((detail::is_same< list<MyClass<>, constant_time_size<true> >::iterator
95 , list<MyClass<>, constant_time_size<false> >::iterator
96 >::value));
97 //void_pointer does change iterator
98 BOOST_STATIC_ASSERT((!detail::is_same< list<MyClass<> >::iterator
99 , list<MyClass<smart_ptr<void> > >::iterator
100 >::value));
101 //size_type does not change iterator
102 BOOST_STATIC_ASSERT((detail::is_same< list<MyClass<>, size_type<unsigned int > >::iterator
103 , list<MyClass<>, size_type<unsigned char> >::iterator
104 >::value));
105 ////////////
106 // slist
107 ////////////
108 BOOST_STATIC_ASSERT((!detail::is_same< slist<MyClass<> >::iterator
109 , slist<MyClass<> >::const_iterator
110 >::value));
111 //constant_time_size does not change iterator
112 BOOST_STATIC_ASSERT((detail::is_same< slist<MyClass<>, constant_time_size<true> >::iterator
113 , slist<MyClass<>, constant_time_size<false> >::iterator
114 >::value));
115 //void_pointer does change iterator
116 BOOST_STATIC_ASSERT((!detail::is_same< slist<MyClass<> >::iterator
117 , slist<MyClass<smart_ptr<void> > >::iterator
118 >::value));
119 //size_type does not change iterator
120 BOOST_STATIC_ASSERT((detail::is_same< slist<MyClass<>, size_type<unsigned int > >::iterator
121 , slist<MyClass<>, size_type<unsigned char> >::iterator
122 >::value));
123 //cache_last does not change iterator
124 BOOST_STATIC_ASSERT((detail::is_same< slist<MyClass<>, cache_last<false> >::iterator
125 , slist<MyClass<>, cache_last<true> >::iterator
126 >::value));
127 //linear does not change iterator
128 BOOST_STATIC_ASSERT((detail::is_same< slist<MyClass<>, linear<false> >::iterator
129 , slist<MyClass<>, linear<true> >::iterator
130 >::value));
131 ////////////
132 // set
133 ////////////
134 BOOST_STATIC_ASSERT((!detail::is_same< set<MyClass<> >::iterator
135 , set<MyClass<> >::const_iterator
136 >::value));
137 //constant_time_size does not change iterator
138 BOOST_STATIC_ASSERT((detail::is_same< set<MyClass<>, constant_time_size<true> >::iterator
139 , set<MyClass<>, constant_time_size<false> >::iterator
140 >::value));
141 //void_pointer does change iterator
142 BOOST_STATIC_ASSERT((!detail::is_same< set<MyClass<> >::iterator
143 , set<MyClass<smart_ptr<void> > >::iterator
144 >::value));
145 //size_type does not change iterator
146 BOOST_STATIC_ASSERT((detail::is_same< set<MyClass<>, size_type<unsigned int > >::iterator
147 , set<MyClass<>, size_type<unsigned char> >::iterator
148 >::value));
149 //compare does not change iterator
150 BOOST_STATIC_ASSERT((detail::is_same< set<MyClass<>, compare< std::greater<MyClass<> > > >::iterator
151 , set<MyClass<>, compare< std::less<MyClass<> > > >::iterator
152 >::value));
153 ////////////
154 // avl_set
155 ////////////
156 BOOST_STATIC_ASSERT((!detail::is_same< avl_set<MyClass<> >::iterator
157 , avl_set<MyClass<> >::const_iterator
158 >::value));
159 //constant_time_size does not change iterator
160 BOOST_STATIC_ASSERT((detail::is_same< avl_set<MyClass<>, constant_time_size<true> >::iterator
161 , avl_set<MyClass<>, constant_time_size<false> >::iterator
162 >::value));
163 //void_pointer does change iterator
164 BOOST_STATIC_ASSERT((!detail::is_same< avl_set<MyClass<> >::iterator
165 , avl_set<MyClass<smart_ptr<void> > >::iterator
166 >::value));
167 //size_type does not change iterator
168 BOOST_STATIC_ASSERT((detail::is_same< avl_set<MyClass<>, size_type<unsigned int > >::iterator
169 , avl_set<MyClass<>, size_type<unsigned char> >::iterator
170 >::value));
171 //compare does not change iterator
172 BOOST_STATIC_ASSERT((detail::is_same< avl_set<MyClass<>, compare< std::greater<MyClass<> > > >::iterator
173 , avl_set<MyClass<>, compare< std::less<MyClass<> > > >::iterator
174 >::value));
175 ////////////
176 // sg_set
177 ////////////
178 BOOST_STATIC_ASSERT((!detail::is_same< sg_set<MyClass<> >::iterator
179 , sg_set<MyClass<> >::const_iterator
180 >::value));
181 //void_pointer does change iterator
182 BOOST_STATIC_ASSERT((!detail::is_same< sg_set<MyClass<> >::iterator
183 , sg_set<MyClass<smart_ptr<void> > >::iterator
184 >::value));
185 //size_type does not change iterator
186 BOOST_STATIC_ASSERT((detail::is_same< sg_set<MyClass<>, size_type<unsigned int > >::iterator
187 , sg_set<MyClass<>, size_type<unsigned char> >::iterator
188 >::value));
189 //compare does not change iterator
190 BOOST_STATIC_ASSERT((detail::is_same< sg_set<MyClass<>, compare< std::greater<MyClass<> > > >::iterator
191 , sg_set<MyClass<>, compare< std::less<MyClass<> > > >::iterator
192 >::value));
193 //floating_point does not change iterator
194 BOOST_STATIC_ASSERT((detail::is_same< sg_set<MyClass<>, floating_point<false> >::iterator
195 , sg_set<MyClass<>, floating_point<true> >::iterator
196 >::value));
197 ////////////
198 // bs_set
199 ////////////
200 BOOST_STATIC_ASSERT((!detail::is_same< bs_set<MyClass<> >::iterator
201 , bs_set<MyClass<> >::const_iterator
202 >::value));
203 //constant_time_size does not change iterator
204 BOOST_STATIC_ASSERT((detail::is_same< bs_set<MyClass<>, constant_time_size<true> >::iterator
205 , bs_set<MyClass<>, constant_time_size<false> >::iterator
206 >::value));
207 //void_pointer does change iterator
208 BOOST_STATIC_ASSERT((!detail::is_same< bs_set<MyClass<> >::iterator
209 , bs_set<MyClass<smart_ptr<void> > >::iterator
210 >::value));
211 //size_type does not change iterator
212 BOOST_STATIC_ASSERT((detail::is_same< bs_set<MyClass<>, size_type<unsigned int > >::iterator
213 , bs_set<MyClass<>, size_type<unsigned char> >::iterator
214 >::value));
215 //compare does not change iterator
216 BOOST_STATIC_ASSERT((detail::is_same< bs_set<MyClass<>, compare< std::greater<MyClass<> > > >::iterator
217 , bs_set<MyClass<>, compare< std::less<MyClass<> > > >::iterator
218 >::value));
219 ////////////
220 // splay_set
221 ////////////
222 BOOST_STATIC_ASSERT((!detail::is_same< splay_set<MyClass<> >::iterator
223 , splay_set<MyClass<> >::const_iterator
224 >::value));
225 //constant_time_size does not change iterator
226 BOOST_STATIC_ASSERT((detail::is_same< splay_set<MyClass<>, constant_time_size<true> >::iterator
227 , splay_set<MyClass<>, constant_time_size<false> >::iterator
228 >::value));
229 //void_pointer does change iterator
230 BOOST_STATIC_ASSERT((!detail::is_same< splay_set<MyClass<> >::iterator
231 , splay_set<MyClass<smart_ptr<void> > >::iterator
232 >::value));
233 //size_type does not change iterator
234 BOOST_STATIC_ASSERT((detail::is_same< splay_set<MyClass<>, size_type<unsigned int > >::iterator
235 , splay_set<MyClass<>, size_type<unsigned char> >::iterator
236 >::value));
237 //compare does not change iterator
238 BOOST_STATIC_ASSERT((detail::is_same< splay_set<MyClass<>, compare< std::greater<MyClass<> > > >::iterator
239 , splay_set<MyClass<>, compare< std::less<MyClass<> > > >::iterator
240 >::value));
241 ////////////
242 // treap_set
243 ////////////
244 BOOST_STATIC_ASSERT((!detail::is_same< treap_set<MyClass<> >::iterator
245 , treap_set<MyClass<> >::const_iterator
246 >::value));
247 //constant_time_size does not change iterator
248 BOOST_STATIC_ASSERT((detail::is_same< treap_set<MyClass<>, constant_time_size<true> >::iterator
249 , treap_set<MyClass<>, constant_time_size<false> >::iterator
250 >::value));
251 //void_pointer does change iterator
252 BOOST_STATIC_ASSERT((!detail::is_same< treap_set<MyClass<> >::iterator
253 , treap_set<MyClass<smart_ptr<void> > >::iterator
254 >::value));
255 //size_type does not change iterator
256 BOOST_STATIC_ASSERT((detail::is_same< treap_set<MyClass<>, size_type<unsigned int > >::iterator
257 , treap_set<MyClass<>, size_type<unsigned char> >::iterator
258 >::value));
259 //compare does not change iterator
260 BOOST_STATIC_ASSERT((detail::is_same< treap_set<MyClass<>, compare< std::greater<MyClass<> > > >::iterator
261 , treap_set<MyClass<>, compare< std::less<MyClass<> > > >::iterator
262 >::value));
263 //priority does not change iterator
264 BOOST_STATIC_ASSERT((detail::is_same< treap_set<MyClass<> >::iterator
265 , treap_set<MyClass<>, priority< inverse_priority<MyClass<> > > >::iterator
266 >::value));
267 //////////////
268 // common tree
269 //////////////
270 BOOST_STATIC_ASSERT((detail::is_same< bs_set<MyClass<> >::iterator
271 , sg_set<MyClass<> >::iterator
272 >::value));
273 BOOST_STATIC_ASSERT((detail::is_same< bs_set<MyClass<> >::iterator
274 , treap_set<MyClass<> >::iterator
275 >::value));
276 BOOST_STATIC_ASSERT((detail::is_same< bs_set<MyClass<> >::iterator
277 , splay_set<MyClass<> >::iterator
278 >::value));
279 ////////////
280 // unordered_set
281 ////////////
282 BOOST_STATIC_ASSERT((!detail::is_same< unordered_set<MyClass<> >::iterator
283 , unordered_set<MyClass<> >::const_iterator
284 >::value));
285 //constant_time_size does not change iterator
286 BOOST_STATIC_ASSERT((detail::is_same< unordered_set<MyClass<>, constant_time_size<true> >::iterator
287 , unordered_set<MyClass<>, constant_time_size<false> >::iterator
288 >::value));
289 //void_pointer does change iterator
290 BOOST_STATIC_ASSERT((!detail::is_same< unordered_set<MyClass<> >::iterator
291 , unordered_set<MyClass<smart_ptr<void> > >::iterator
292 >::value));
293 //size_type does not change iterator
294 BOOST_STATIC_ASSERT((detail::is_same< unordered_set<MyClass<>, size_type<unsigned int > >::iterator
295 , unordered_set<MyClass<>, size_type<unsigned char> >::iterator
296 >::value));
297 //hash does not change iterator
298 BOOST_STATIC_ASSERT((detail::is_same< unordered_set<MyClass<> >::iterator
299 , unordered_set<MyClass<>, hash< inverse_hash<MyClass<> > > >::iterator
300 >::value));
301 //equal does not change iterator
302 BOOST_STATIC_ASSERT((detail::is_same< unordered_set<MyClass<> >::iterator
303 , unordered_set<MyClass<>, equal< alternative_equal<MyClass<> > > >::iterator
304 >::value));
305 //power_2_buckets does not change iterator
306 BOOST_STATIC_ASSERT((detail::is_same< unordered_set<MyClass<> >::iterator
307 , unordered_set<MyClass<>, power_2_buckets<true> >::iterator
308 >::value));
309 //cache_begin does not change iterator
310 BOOST_STATIC_ASSERT((detail::is_same< unordered_set<MyClass<> >::iterator
311 , unordered_set<MyClass<>, cache_begin<true> >::iterator
312 >::value));
313 return 0;
314 }
315