]>
Commit | Line | Data |
---|---|---|
f67539c2 | 1 | /* Copyright 2003-2020 Joaquin M Lopez Munoz. |
7c673cae FG |
2 | * Distributed under the Boost Software License, Version 1.0. |
3 | * (See accompanying file LICENSE_1_0.txt or copy at | |
4 | * http://www.boost.org/LICENSE_1_0.txt) | |
5 | * | |
6 | * See http://www.boost.org/libs/multi_index for library home page. | |
7 | * | |
8 | * The internal implementation of red-black trees is based on that of SGI STL | |
9 | * stl_tree.h file: | |
10 | * | |
11 | * Copyright (c) 1996,1997 | |
12 | * Silicon Graphics Computer Systems, Inc. | |
13 | * | |
14 | * Permission to use, copy, modify, distribute and sell this software | |
15 | * and its documentation for any purpose is hereby granted without fee, | |
16 | * provided that the above copyright notice appear in all copies and | |
17 | * that both that copyright notice and this permission notice appear | |
18 | * in supporting documentation. Silicon Graphics makes no | |
19 | * representations about the suitability of this software for any | |
20 | * purpose. It is provided "as is" without express or implied warranty. | |
21 | * | |
22 | * | |
23 | * Copyright (c) 1994 | |
24 | * Hewlett-Packard Company | |
25 | * | |
26 | * Permission to use, copy, modify, distribute and sell this software | |
27 | * and its documentation for any purpose is hereby granted without fee, | |
28 | * provided that the above copyright notice appear in all copies and | |
29 | * that both that copyright notice and this permission notice appear | |
30 | * in supporting documentation. Hewlett-Packard Company makes no | |
31 | * representations about the suitability of this software for any | |
32 | * purpose. It is provided "as is" without express or implied warranty. | |
33 | * | |
34 | */ | |
35 | ||
36 | #ifndef BOOST_MULTI_INDEX_DETAIL_ORD_INDEX_IMPL_HPP | |
37 | #define BOOST_MULTI_INDEX_DETAIL_ORD_INDEX_IMPL_HPP | |
38 | ||
39 | #if defined(_MSC_VER) | |
40 | #pragma once | |
41 | #endif | |
42 | ||
43 | #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */ | |
44 | #include <algorithm> | |
45 | #include <boost/call_traits.hpp> | |
11fdf7f2 | 46 | #include <boost/core/addressof.hpp> |
7c673cae FG |
47 | #include <boost/detail/no_exceptions_support.hpp> |
48 | #include <boost/detail/workaround.hpp> | |
49 | #include <boost/foreach_fwd.hpp> | |
50 | #include <boost/iterator/reverse_iterator.hpp> | |
51 | #include <boost/move/core.hpp> | |
52 | #include <boost/mpl/bool.hpp> | |
53 | #include <boost/mpl/if.hpp> | |
54 | #include <boost/mpl/push_front.hpp> | |
55 | #include <boost/multi_index/detail/access_specifier.hpp> | |
f67539c2 | 56 | #include <boost/multi_index/detail/adl_swap.hpp> |
92f5a8d4 | 57 | #include <boost/multi_index/detail/allocator_traits.hpp> |
7c673cae FG |
58 | #include <boost/multi_index/detail/bidir_node_iterator.hpp> |
59 | #include <boost/multi_index/detail/do_not_copy_elements_tag.hpp> | |
60 | #include <boost/multi_index/detail/index_node_base.hpp> | |
61 | #include <boost/multi_index/detail/modify_key_adaptor.hpp> | |
62 | #include <boost/multi_index/detail/ord_index_node.hpp> | |
63 | #include <boost/multi_index/detail/ord_index_ops.hpp> | |
64 | #include <boost/multi_index/detail/safe_mode.hpp> | |
65 | #include <boost/multi_index/detail/scope_guard.hpp> | |
66 | #include <boost/multi_index/detail/unbounded.hpp> | |
67 | #include <boost/multi_index/detail/value_compare.hpp> | |
68 | #include <boost/multi_index/detail/vartempl_support.hpp> | |
69 | #include <boost/multi_index/detail/ord_index_impl_fwd.hpp> | |
70 | #include <boost/ref.hpp> | |
71 | #include <boost/tuple/tuple.hpp> | |
72 | #include <boost/type_traits/is_same.hpp> | |
73 | #include <utility> | |
74 | ||
75 | #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) | |
76 | #include <initializer_list> | |
77 | #endif | |
78 | ||
79 | #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) | |
80 | #include <boost/archive/archive_exception.hpp> | |
f67539c2 | 81 | #include <boost/bind/bind.hpp> |
7c673cae FG |
82 | #include <boost/multi_index/detail/duplicates_iterator.hpp> |
83 | #include <boost/throw_exception.hpp> | |
84 | #endif | |
85 | ||
86 | #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING) | |
87 | #define BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT_OF(x) \ | |
88 | detail::scope_guard BOOST_JOIN(check_invariant_,__LINE__)= \ | |
89 | detail::make_obj_guard(x,&ordered_index_impl::check_invariant_); \ | |
90 | BOOST_JOIN(check_invariant_,__LINE__).touch(); | |
91 | #define BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT \ | |
92 | BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT_OF(*this) | |
93 | #else | |
94 | #define BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT_OF(x) | |
95 | #define BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT | |
96 | #endif | |
97 | ||
98 | namespace boost{ | |
99 | ||
100 | namespace multi_index{ | |
101 | ||
102 | namespace detail{ | |
103 | ||
104 | /* ordered_index adds a layer of ordered indexing to a given Super and accepts | |
105 | * an augmenting policy for optional addition of order statistics. | |
106 | */ | |
107 | ||
108 | /* Most of the implementation of unique and non-unique indices is | |
109 | * shared. We tell from one another on instantiation time by using | |
110 | * these tags. | |
111 | */ | |
112 | ||
113 | struct ordered_unique_tag{}; | |
114 | struct ordered_non_unique_tag{}; | |
115 | ||
116 | template< | |
117 | typename KeyFromValue,typename Compare, | |
118 | typename SuperMeta,typename TagList,typename Category,typename AugmentPolicy | |
119 | > | |
120 | class ordered_index; | |
121 | ||
122 | template< | |
123 | typename KeyFromValue,typename Compare, | |
124 | typename SuperMeta,typename TagList,typename Category,typename AugmentPolicy | |
125 | > | |
126 | class ordered_index_impl: | |
127 | BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS SuperMeta::type | |
128 | ||
129 | #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) | |
130 | ,public safe_mode::safe_container< | |
131 | ordered_index_impl< | |
132 | KeyFromValue,Compare,SuperMeta,TagList,Category,AugmentPolicy> > | |
133 | #endif | |
134 | ||
135 | { | |
136 | #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\ | |
137 | BOOST_WORKAROUND(__MWERKS__,<=0x3003) | |
138 | /* The "ISO C++ Template Parser" option in CW8.3 has a problem with the | |
139 | * lifetime of const references bound to temporaries --precisely what | |
140 | * scopeguards are. | |
141 | */ | |
142 | ||
143 | #pragma parse_mfunc_templ off | |
144 | #endif | |
145 | ||
146 | typedef typename SuperMeta::type super; | |
147 | ||
148 | protected: | |
149 | typedef ordered_index_node< | |
150 | AugmentPolicy,typename super::node_type> node_type; | |
151 | ||
152 | protected: /* for the benefit of AugmentPolicy::augmented_interface */ | |
153 | typedef typename node_type::impl_type node_impl_type; | |
154 | typedef typename node_impl_type::pointer node_impl_pointer; | |
155 | ||
156 | public: | |
157 | /* types */ | |
158 | ||
159 | typedef typename KeyFromValue::result_type key_type; | |
160 | typedef typename node_type::value_type value_type; | |
161 | typedef KeyFromValue key_from_value; | |
162 | typedef Compare key_compare; | |
163 | typedef value_comparison< | |
164 | value_type,KeyFromValue,Compare> value_compare; | |
165 | typedef tuple<key_from_value,key_compare> ctor_args; | |
166 | typedef typename super::final_allocator_type allocator_type; | |
11fdf7f2 TL |
167 | typedef value_type& reference; |
168 | typedef const value_type& const_reference; | |
7c673cae FG |
169 | |
170 | #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) | |
171 | typedef safe_mode::safe_iterator< | |
172 | bidir_node_iterator<node_type>, | |
173 | ordered_index_impl> iterator; | |
174 | #else | |
175 | typedef bidir_node_iterator<node_type> iterator; | |
176 | #endif | |
177 | ||
178 | typedef iterator const_iterator; | |
179 | ||
92f5a8d4 TL |
180 | private: |
181 | typedef allocator_traits<allocator_type> alloc_traits; | |
182 | ||
183 | public: | |
184 | typedef typename alloc_traits::size_type size_type; | |
185 | typedef typename alloc_traits::difference_type difference_type; | |
186 | typedef typename alloc_traits::pointer pointer; | |
187 | typedef typename alloc_traits::const_pointer const_pointer; | |
7c673cae FG |
188 | typedef typename |
189 | boost::reverse_iterator<iterator> reverse_iterator; | |
190 | typedef typename | |
191 | boost::reverse_iterator<const_iterator> const_reverse_iterator; | |
192 | typedef TagList tag_list; | |
193 | ||
194 | protected: | |
195 | typedef typename super::final_node_type final_node_type; | |
196 | typedef tuples::cons< | |
197 | ctor_args, | |
198 | typename super::ctor_args_list> ctor_args_list; | |
199 | typedef typename mpl::push_front< | |
200 | typename super::index_type_list, | |
201 | ordered_index< | |
202 | KeyFromValue,Compare, | |
203 | SuperMeta,TagList,Category,AugmentPolicy | |
204 | > >::type index_type_list; | |
205 | typedef typename mpl::push_front< | |
206 | typename super::iterator_type_list, | |
207 | iterator>::type iterator_type_list; | |
208 | typedef typename mpl::push_front< | |
209 | typename super::const_iterator_type_list, | |
210 | const_iterator>::type const_iterator_type_list; | |
211 | typedef typename super::copy_map_type copy_map_type; | |
212 | ||
213 | #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) | |
214 | typedef typename super::index_saver_type index_saver_type; | |
215 | typedef typename super::index_loader_type index_loader_type; | |
216 | #endif | |
217 | ||
218 | protected: | |
219 | #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) | |
220 | typedef safe_mode::safe_container< | |
221 | ordered_index_impl> safe_super; | |
222 | #endif | |
223 | ||
224 | typedef typename call_traits< | |
225 | value_type>::param_type value_param_type; | |
226 | typedef typename call_traits< | |
227 | key_type>::param_type key_param_type; | |
228 | ||
229 | /* Needed to avoid commas in BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL | |
230 | * expansion. | |
231 | */ | |
232 | ||
233 | typedef std::pair<iterator,bool> emplace_return_type; | |
234 | ||
235 | public: | |
236 | ||
237 | /* construct/copy/destroy | |
238 | * Default and copy ctors are in the protected section as indices are | |
239 | * not supposed to be created on their own. No range ctor either. | |
240 | * Assignment operators defined at ordered_index rather than here. | |
241 | */ | |
242 | ||
243 | allocator_type get_allocator()const BOOST_NOEXCEPT | |
244 | { | |
245 | return this->final().get_allocator(); | |
246 | } | |
247 | ||
248 | /* iterators */ | |
249 | ||
250 | iterator | |
251 | begin()BOOST_NOEXCEPT{return make_iterator(leftmost());} | |
252 | const_iterator | |
253 | begin()const BOOST_NOEXCEPT{return make_iterator(leftmost());} | |
254 | iterator | |
255 | end()BOOST_NOEXCEPT{return make_iterator(header());} | |
256 | const_iterator | |
257 | end()const BOOST_NOEXCEPT{return make_iterator(header());} | |
258 | reverse_iterator | |
259 | rbegin()BOOST_NOEXCEPT{return boost::make_reverse_iterator(end());} | |
260 | const_reverse_iterator | |
261 | rbegin()const BOOST_NOEXCEPT{return boost::make_reverse_iterator(end());} | |
262 | reverse_iterator | |
263 | rend()BOOST_NOEXCEPT{return boost::make_reverse_iterator(begin());} | |
264 | const_reverse_iterator | |
265 | rend()const BOOST_NOEXCEPT{return boost::make_reverse_iterator(begin());} | |
266 | const_iterator | |
267 | cbegin()const BOOST_NOEXCEPT{return begin();} | |
268 | const_iterator | |
269 | cend()const BOOST_NOEXCEPT{return end();} | |
270 | const_reverse_iterator | |
271 | crbegin()const BOOST_NOEXCEPT{return rbegin();} | |
272 | const_reverse_iterator | |
273 | crend()const BOOST_NOEXCEPT{return rend();} | |
274 | ||
275 | iterator iterator_to(const value_type& x) | |
276 | { | |
11fdf7f2 | 277 | return make_iterator(node_from_value<node_type>(boost::addressof(x))); |
7c673cae FG |
278 | } |
279 | ||
280 | const_iterator iterator_to(const value_type& x)const | |
281 | { | |
11fdf7f2 | 282 | return make_iterator(node_from_value<node_type>(boost::addressof(x))); |
7c673cae FG |
283 | } |
284 | ||
285 | /* capacity */ | |
286 | ||
287 | bool empty()const BOOST_NOEXCEPT{return this->final_empty_();} | |
288 | size_type size()const BOOST_NOEXCEPT{return this->final_size_();} | |
289 | size_type max_size()const BOOST_NOEXCEPT{return this->final_max_size_();} | |
290 | ||
291 | /* modifiers */ | |
292 | ||
293 | BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL( | |
294 | emplace_return_type,emplace,emplace_impl) | |
295 | ||
296 | BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL_EXTRA_ARG( | |
297 | iterator,emplace_hint,emplace_hint_impl,iterator,position) | |
298 | ||
299 | std::pair<iterator,bool> insert(const value_type& x) | |
300 | { | |
301 | BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT; | |
302 | std::pair<final_node_type*,bool> p=this->final_insert_(x); | |
303 | return std::pair<iterator,bool>(make_iterator(p.first),p.second); | |
304 | } | |
305 | ||
306 | std::pair<iterator,bool> insert(BOOST_RV_REF(value_type) x) | |
307 | { | |
308 | BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT; | |
309 | std::pair<final_node_type*,bool> p=this->final_insert_rv_(x); | |
310 | return std::pair<iterator,bool>(make_iterator(p.first),p.second); | |
311 | } | |
312 | ||
313 | iterator insert(iterator position,const value_type& x) | |
314 | { | |
315 | BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); | |
316 | BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); | |
317 | BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT; | |
318 | std::pair<final_node_type*,bool> p=this->final_insert_( | |
319 | x,static_cast<final_node_type*>(position.get_node())); | |
320 | return make_iterator(p.first); | |
321 | } | |
322 | ||
323 | iterator insert(iterator position,BOOST_RV_REF(value_type) x) | |
324 | { | |
325 | BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); | |
326 | BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); | |
327 | BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT; | |
328 | std::pair<final_node_type*,bool> p=this->final_insert_rv_( | |
329 | x,static_cast<final_node_type*>(position.get_node())); | |
330 | return make_iterator(p.first); | |
331 | } | |
332 | ||
333 | template<typename InputIterator> | |
334 | void insert(InputIterator first,InputIterator last) | |
335 | { | |
336 | BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT; | |
337 | node_type* hint=header(); /* end() */ | |
338 | for(;first!=last;++first){ | |
339 | hint=this->final_insert_ref_( | |
340 | *first,static_cast<final_node_type*>(hint)).first; | |
341 | node_type::increment(hint); | |
342 | } | |
343 | } | |
344 | ||
345 | #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) | |
346 | void insert(std::initializer_list<value_type> list) | |
347 | { | |
348 | insert(list.begin(),list.end()); | |
349 | } | |
350 | #endif | |
351 | ||
352 | iterator erase(iterator position) | |
353 | { | |
354 | BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); | |
355 | BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position); | |
356 | BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); | |
357 | BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT; | |
358 | this->final_erase_(static_cast<final_node_type*>(position++.get_node())); | |
359 | return position; | |
360 | } | |
361 | ||
362 | size_type erase(key_param_type x) | |
363 | { | |
364 | BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT; | |
365 | std::pair<iterator,iterator> p=equal_range(x); | |
366 | size_type s=0; | |
367 | while(p.first!=p.second){ | |
368 | p.first=erase(p.first); | |
369 | ++s; | |
370 | } | |
371 | return s; | |
372 | } | |
373 | ||
374 | iterator erase(iterator first,iterator last) | |
375 | { | |
376 | BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first); | |
377 | BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last); | |
378 | BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,*this); | |
379 | BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,*this); | |
380 | BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last); | |
381 | BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT; | |
382 | while(first!=last){ | |
383 | first=erase(first); | |
384 | } | |
385 | return first; | |
386 | } | |
387 | ||
388 | bool replace(iterator position,const value_type& x) | |
389 | { | |
390 | BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); | |
391 | BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position); | |
392 | BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); | |
393 | BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT; | |
394 | return this->final_replace_( | |
395 | x,static_cast<final_node_type*>(position.get_node())); | |
396 | } | |
397 | ||
398 | bool replace(iterator position,BOOST_RV_REF(value_type) x) | |
399 | { | |
400 | BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); | |
401 | BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position); | |
402 | BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); | |
403 | BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT; | |
404 | return this->final_replace_rv_( | |
405 | x,static_cast<final_node_type*>(position.get_node())); | |
406 | } | |
407 | ||
408 | template<typename Modifier> | |
409 | bool modify(iterator position,Modifier mod) | |
410 | { | |
411 | BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); | |
412 | BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position); | |
413 | BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); | |
414 | BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT; | |
415 | ||
416 | #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) | |
417 | /* MSVC++ 6.0 optimizer on safe mode code chokes if this | |
418 | * this is not added. Left it for all compilers as it does no | |
419 | * harm. | |
420 | */ | |
421 | ||
422 | position.detach(); | |
423 | #endif | |
424 | ||
425 | return this->final_modify_( | |
426 | mod,static_cast<final_node_type*>(position.get_node())); | |
427 | } | |
428 | ||
429 | template<typename Modifier,typename Rollback> | |
430 | bool modify(iterator position,Modifier mod,Rollback back_) | |
431 | { | |
432 | BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); | |
433 | BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position); | |
434 | BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); | |
435 | BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT; | |
436 | ||
437 | #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) | |
438 | /* MSVC++ 6.0 optimizer on safe mode code chokes if this | |
439 | * this is not added. Left it for all compilers as it does no | |
440 | * harm. | |
441 | */ | |
442 | ||
443 | position.detach(); | |
444 | #endif | |
445 | ||
446 | return this->final_modify_( | |
447 | mod,back_,static_cast<final_node_type*>(position.get_node())); | |
448 | } | |
449 | ||
450 | template<typename Modifier> | |
451 | bool modify_key(iterator position,Modifier mod) | |
452 | { | |
453 | BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); | |
454 | BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position); | |
455 | BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); | |
456 | BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT; | |
457 | return modify( | |
458 | position,modify_key_adaptor<Modifier,value_type,KeyFromValue>(mod,key)); | |
459 | } | |
460 | ||
461 | template<typename Modifier,typename Rollback> | |
462 | bool modify_key(iterator position,Modifier mod,Rollback back_) | |
463 | { | |
464 | BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); | |
465 | BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position); | |
466 | BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); | |
467 | BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT; | |
468 | return modify( | |
469 | position, | |
470 | modify_key_adaptor<Modifier,value_type,KeyFromValue>(mod,key), | |
471 | modify_key_adaptor<Rollback,value_type,KeyFromValue>(back_,key)); | |
472 | } | |
473 | ||
474 | void swap( | |
475 | ordered_index< | |
476 | KeyFromValue,Compare,SuperMeta,TagList,Category,AugmentPolicy>& x) | |
477 | { | |
478 | BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT; | |
479 | BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT_OF(x); | |
480 | this->final_swap_(x.final()); | |
481 | } | |
482 | ||
483 | void clear()BOOST_NOEXCEPT | |
484 | { | |
485 | BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT; | |
486 | this->final_clear_(); | |
487 | } | |
488 | ||
489 | /* observers */ | |
490 | ||
491 | key_from_value key_extractor()const{return key;} | |
492 | key_compare key_comp()const{return comp_;} | |
493 | value_compare value_comp()const{return value_compare(key,comp_);} | |
494 | ||
495 | /* set operations */ | |
496 | ||
497 | /* Internally, these ops rely on const_iterator being the same | |
498 | * type as iterator. | |
499 | */ | |
500 | ||
501 | template<typename CompatibleKey> | |
502 | iterator find(const CompatibleKey& x)const | |
503 | { | |
504 | return make_iterator(ordered_index_find(root(),header(),key,x,comp_)); | |
505 | } | |
506 | ||
507 | template<typename CompatibleKey,typename CompatibleCompare> | |
508 | iterator find( | |
509 | const CompatibleKey& x,const CompatibleCompare& comp)const | |
510 | { | |
511 | return make_iterator(ordered_index_find(root(),header(),key,x,comp)); | |
512 | } | |
513 | ||
514 | template<typename CompatibleKey> | |
515 | size_type count(const CompatibleKey& x)const | |
516 | { | |
517 | return count(x,comp_); | |
518 | } | |
519 | ||
520 | template<typename CompatibleKey,typename CompatibleCompare> | |
521 | size_type count(const CompatibleKey& x,const CompatibleCompare& comp)const | |
522 | { | |
523 | std::pair<iterator,iterator> p=equal_range(x,comp); | |
92f5a8d4 | 524 | size_type n=static_cast<size_type>(std::distance(p.first,p.second)); |
7c673cae FG |
525 | return n; |
526 | } | |
527 | ||
528 | template<typename CompatibleKey> | |
529 | iterator lower_bound(const CompatibleKey& x)const | |
530 | { | |
531 | return make_iterator( | |
532 | ordered_index_lower_bound(root(),header(),key,x,comp_)); | |
533 | } | |
534 | ||
535 | template<typename CompatibleKey,typename CompatibleCompare> | |
536 | iterator lower_bound( | |
537 | const CompatibleKey& x,const CompatibleCompare& comp)const | |
538 | { | |
539 | return make_iterator( | |
540 | ordered_index_lower_bound(root(),header(),key,x,comp)); | |
541 | } | |
542 | ||
543 | template<typename CompatibleKey> | |
544 | iterator upper_bound(const CompatibleKey& x)const | |
545 | { | |
546 | return make_iterator( | |
547 | ordered_index_upper_bound(root(),header(),key,x,comp_)); | |
548 | } | |
549 | ||
550 | template<typename CompatibleKey,typename CompatibleCompare> | |
551 | iterator upper_bound( | |
552 | const CompatibleKey& x,const CompatibleCompare& comp)const | |
553 | { | |
554 | return make_iterator( | |
555 | ordered_index_upper_bound(root(),header(),key,x,comp)); | |
556 | } | |
557 | ||
558 | template<typename CompatibleKey> | |
559 | std::pair<iterator,iterator> equal_range( | |
560 | const CompatibleKey& x)const | |
561 | { | |
562 | std::pair<node_type*,node_type*> p= | |
563 | ordered_index_equal_range(root(),header(),key,x,comp_); | |
564 | return std::pair<iterator,iterator>( | |
565 | make_iterator(p.first),make_iterator(p.second)); | |
566 | } | |
567 | ||
568 | template<typename CompatibleKey,typename CompatibleCompare> | |
569 | std::pair<iterator,iterator> equal_range( | |
570 | const CompatibleKey& x,const CompatibleCompare& comp)const | |
571 | { | |
572 | std::pair<node_type*,node_type*> p= | |
573 | ordered_index_equal_range(root(),header(),key,x,comp); | |
574 | return std::pair<iterator,iterator>( | |
575 | make_iterator(p.first),make_iterator(p.second)); | |
576 | } | |
577 | ||
578 | /* range */ | |
579 | ||
580 | template<typename LowerBounder,typename UpperBounder> | |
581 | std::pair<iterator,iterator> | |
582 | range(LowerBounder lower,UpperBounder upper)const | |
583 | { | |
584 | typedef typename mpl::if_< | |
585 | is_same<LowerBounder,unbounded_type>, | |
586 | BOOST_DEDUCED_TYPENAME mpl::if_< | |
587 | is_same<UpperBounder,unbounded_type>, | |
588 | both_unbounded_tag, | |
589 | lower_unbounded_tag | |
590 | >::type, | |
591 | BOOST_DEDUCED_TYPENAME mpl::if_< | |
592 | is_same<UpperBounder,unbounded_type>, | |
593 | upper_unbounded_tag, | |
594 | none_unbounded_tag | |
595 | >::type | |
596 | >::type dispatch; | |
597 | ||
598 | return range(lower,upper,dispatch()); | |
599 | } | |
600 | ||
601 | BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: | |
602 | ordered_index_impl(const ctor_args_list& args_list,const allocator_type& al): | |
603 | super(args_list.get_tail(),al), | |
604 | key(tuples::get<0>(args_list.get_head())), | |
605 | comp_(tuples::get<1>(args_list.get_head())) | |
606 | { | |
607 | empty_initialize(); | |
608 | } | |
609 | ||
610 | ordered_index_impl( | |
611 | const ordered_index_impl< | |
612 | KeyFromValue,Compare,SuperMeta,TagList,Category,AugmentPolicy>& x): | |
613 | super(x), | |
614 | ||
615 | #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) | |
616 | safe_super(), | |
617 | #endif | |
618 | ||
619 | key(x.key), | |
620 | comp_(x.comp_) | |
621 | { | |
622 | /* Copy ctor just takes the key and compare objects from x. The rest is | |
623 | * done in a subsequent call to copy_(). | |
624 | */ | |
625 | } | |
626 | ||
627 | ordered_index_impl( | |
628 | const ordered_index_impl< | |
629 | KeyFromValue,Compare,SuperMeta,TagList,Category,AugmentPolicy>& x, | |
630 | do_not_copy_elements_tag): | |
631 | super(x,do_not_copy_elements_tag()), | |
632 | ||
633 | #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) | |
634 | safe_super(), | |
635 | #endif | |
636 | ||
637 | key(x.key), | |
638 | comp_(x.comp_) | |
639 | { | |
640 | empty_initialize(); | |
641 | } | |
642 | ||
643 | ~ordered_index_impl() | |
644 | { | |
645 | /* the container is guaranteed to be empty by now */ | |
646 | } | |
647 | ||
648 | #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) | |
649 | iterator make_iterator(node_type* node){return iterator(node,this);} | |
650 | const_iterator make_iterator(node_type* node)const | |
651 | {return const_iterator(node,const_cast<ordered_index_impl*>(this));} | |
652 | #else | |
653 | iterator make_iterator(node_type* node){return iterator(node);} | |
654 | const_iterator make_iterator(node_type* node)const | |
655 | {return const_iterator(node);} | |
656 | #endif | |
657 | ||
658 | void copy_( | |
659 | const ordered_index_impl< | |
660 | KeyFromValue,Compare,SuperMeta,TagList,Category,AugmentPolicy>& x, | |
661 | const copy_map_type& map) | |
662 | { | |
663 | if(!x.root()){ | |
664 | empty_initialize(); | |
665 | } | |
666 | else{ | |
667 | header()->color()=x.header()->color(); | |
668 | AugmentPolicy::copy(x.header()->impl(),header()->impl()); | |
669 | ||
670 | node_type* root_cpy=map.find(static_cast<final_node_type*>(x.root())); | |
671 | header()->parent()=root_cpy->impl(); | |
672 | ||
673 | node_type* leftmost_cpy=map.find( | |
674 | static_cast<final_node_type*>(x.leftmost())); | |
675 | header()->left()=leftmost_cpy->impl(); | |
676 | ||
677 | node_type* rightmost_cpy=map.find( | |
678 | static_cast<final_node_type*>(x.rightmost())); | |
679 | header()->right()=rightmost_cpy->impl(); | |
680 | ||
681 | typedef typename copy_map_type::const_iterator copy_map_iterator; | |
682 | for(copy_map_iterator it=map.begin(),it_end=map.end();it!=it_end;++it){ | |
683 | node_type* org=it->first; | |
684 | node_type* cpy=it->second; | |
685 | ||
686 | cpy->color()=org->color(); | |
687 | AugmentPolicy::copy(org->impl(),cpy->impl()); | |
688 | ||
689 | node_impl_pointer parent_org=org->parent(); | |
690 | if(parent_org==node_impl_pointer(0))cpy->parent()=node_impl_pointer(0); | |
691 | else{ | |
692 | node_type* parent_cpy=map.find( | |
693 | static_cast<final_node_type*>(node_type::from_impl(parent_org))); | |
694 | cpy->parent()=parent_cpy->impl(); | |
695 | if(parent_org->left()==org->impl()){ | |
696 | parent_cpy->left()=cpy->impl(); | |
697 | } | |
698 | else if(parent_org->right()==org->impl()){ | |
699 | /* header() does not satisfy this nor the previous check */ | |
700 | parent_cpy->right()=cpy->impl(); | |
701 | } | |
702 | } | |
703 | ||
704 | if(org->left()==node_impl_pointer(0)) | |
705 | cpy->left()=node_impl_pointer(0); | |
706 | if(org->right()==node_impl_pointer(0)) | |
707 | cpy->right()=node_impl_pointer(0); | |
708 | } | |
709 | } | |
710 | ||
711 | super::copy_(x,map); | |
712 | } | |
713 | ||
714 | template<typename Variant> | |
715 | final_node_type* insert_( | |
716 | value_param_type v,final_node_type*& x,Variant variant) | |
717 | { | |
718 | link_info inf; | |
719 | if(!link_point(key(v),inf,Category())){ | |
720 | return static_cast<final_node_type*>(node_type::from_impl(inf.pos)); | |
721 | } | |
722 | ||
723 | final_node_type* res=super::insert_(v,x,variant); | |
724 | if(res==x){ | |
725 | node_impl_type::link( | |
726 | static_cast<node_type*>(x)->impl(),inf.side,inf.pos,header()->impl()); | |
727 | } | |
728 | return res; | |
729 | } | |
730 | ||
731 | template<typename Variant> | |
732 | final_node_type* insert_( | |
733 | value_param_type v,node_type* position,final_node_type*& x,Variant variant) | |
734 | { | |
735 | link_info inf; | |
736 | if(!hinted_link_point(key(v),position,inf,Category())){ | |
737 | return static_cast<final_node_type*>(node_type::from_impl(inf.pos)); | |
738 | } | |
739 | ||
740 | final_node_type* res=super::insert_(v,position,x,variant); | |
741 | if(res==x){ | |
742 | node_impl_type::link( | |
743 | static_cast<node_type*>(x)->impl(),inf.side,inf.pos,header()->impl()); | |
744 | } | |
745 | return res; | |
746 | } | |
747 | ||
748 | void erase_(node_type* x) | |
749 | { | |
750 | node_impl_type::rebalance_for_erase( | |
751 | x->impl(),header()->parent(),header()->left(),header()->right()); | |
752 | super::erase_(x); | |
753 | ||
754 | #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) | |
755 | detach_iterators(x); | |
756 | #endif | |
757 | } | |
758 | ||
759 | void delete_all_nodes_() | |
760 | { | |
761 | delete_all_nodes(root()); | |
762 | } | |
763 | ||
764 | void clear_() | |
765 | { | |
766 | super::clear_(); | |
767 | empty_initialize(); | |
768 | ||
769 | #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) | |
770 | safe_super::detach_dereferenceable_iterators(); | |
771 | #endif | |
772 | } | |
773 | ||
f67539c2 | 774 | template<typename BoolConstant> |
7c673cae FG |
775 | void swap_( |
776 | ordered_index_impl< | |
f67539c2 TL |
777 | KeyFromValue,Compare,SuperMeta,TagList,Category,AugmentPolicy>& x, |
778 | BoolConstant swap_allocators) | |
7c673cae | 779 | { |
f67539c2 TL |
780 | adl_swap(key,x.key); |
781 | adl_swap(comp_,x.comp_); | |
7c673cae FG |
782 | |
783 | #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) | |
784 | safe_super::swap(x); | |
785 | #endif | |
786 | ||
f67539c2 | 787 | super::swap_(x,swap_allocators); |
7c673cae FG |
788 | } |
789 | ||
790 | void swap_elements_( | |
791 | ordered_index_impl< | |
792 | KeyFromValue,Compare,SuperMeta,TagList,Category,AugmentPolicy>& x) | |
793 | { | |
794 | #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) | |
795 | safe_super::swap(x); | |
796 | #endif | |
797 | ||
798 | super::swap_elements_(x); | |
799 | } | |
800 | ||
801 | template<typename Variant> | |
802 | bool replace_(value_param_type v,node_type* x,Variant variant) | |
803 | { | |
804 | if(in_place(v,x,Category())){ | |
805 | return super::replace_(v,x,variant); | |
806 | } | |
807 | ||
808 | node_type* next=x; | |
809 | node_type::increment(next); | |
810 | ||
811 | node_impl_type::rebalance_for_erase( | |
812 | x->impl(),header()->parent(),header()->left(),header()->right()); | |
813 | ||
814 | BOOST_TRY{ | |
815 | link_info inf; | |
816 | if(link_point(key(v),inf,Category())&&super::replace_(v,x,variant)){ | |
817 | node_impl_type::link(x->impl(),inf.side,inf.pos,header()->impl()); | |
818 | return true; | |
819 | } | |
820 | node_impl_type::restore(x->impl(),next->impl(),header()->impl()); | |
821 | return false; | |
822 | } | |
823 | BOOST_CATCH(...){ | |
824 | node_impl_type::restore(x->impl(),next->impl(),header()->impl()); | |
825 | BOOST_RETHROW; | |
826 | } | |
827 | BOOST_CATCH_END | |
828 | } | |
829 | ||
830 | bool modify_(node_type* x) | |
831 | { | |
832 | bool b; | |
833 | BOOST_TRY{ | |
834 | b=in_place(x->value(),x,Category()); | |
835 | } | |
836 | BOOST_CATCH(...){ | |
837 | erase_(x); | |
838 | BOOST_RETHROW; | |
839 | } | |
840 | BOOST_CATCH_END | |
841 | if(!b){ | |
842 | node_impl_type::rebalance_for_erase( | |
843 | x->impl(),header()->parent(),header()->left(),header()->right()); | |
844 | BOOST_TRY{ | |
845 | link_info inf; | |
846 | if(!link_point(key(x->value()),inf,Category())){ | |
847 | super::erase_(x); | |
848 | ||
849 | #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) | |
850 | detach_iterators(x); | |
851 | #endif | |
852 | return false; | |
853 | } | |
854 | node_impl_type::link(x->impl(),inf.side,inf.pos,header()->impl()); | |
855 | } | |
856 | BOOST_CATCH(...){ | |
857 | super::erase_(x); | |
858 | ||
859 | #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) | |
860 | detach_iterators(x); | |
861 | #endif | |
862 | ||
863 | BOOST_RETHROW; | |
864 | } | |
865 | BOOST_CATCH_END | |
866 | } | |
867 | ||
868 | BOOST_TRY{ | |
869 | if(!super::modify_(x)){ | |
870 | node_impl_type::rebalance_for_erase( | |
871 | x->impl(),header()->parent(),header()->left(),header()->right()); | |
872 | ||
873 | #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) | |
874 | detach_iterators(x); | |
875 | #endif | |
876 | ||
877 | return false; | |
878 | } | |
879 | else return true; | |
880 | } | |
881 | BOOST_CATCH(...){ | |
882 | node_impl_type::rebalance_for_erase( | |
883 | x->impl(),header()->parent(),header()->left(),header()->right()); | |
884 | ||
885 | #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) | |
886 | detach_iterators(x); | |
887 | #endif | |
888 | ||
889 | BOOST_RETHROW; | |
890 | } | |
891 | BOOST_CATCH_END | |
892 | } | |
893 | ||
894 | bool modify_rollback_(node_type* x) | |
895 | { | |
896 | if(in_place(x->value(),x,Category())){ | |
897 | return super::modify_rollback_(x); | |
898 | } | |
899 | ||
900 | node_type* next=x; | |
901 | node_type::increment(next); | |
902 | ||
903 | node_impl_type::rebalance_for_erase( | |
904 | x->impl(),header()->parent(),header()->left(),header()->right()); | |
905 | ||
906 | BOOST_TRY{ | |
907 | link_info inf; | |
908 | if(link_point(key(x->value()),inf,Category())&& | |
909 | super::modify_rollback_(x)){ | |
910 | node_impl_type::link(x->impl(),inf.side,inf.pos,header()->impl()); | |
911 | return true; | |
912 | } | |
913 | node_impl_type::restore(x->impl(),next->impl(),header()->impl()); | |
914 | return false; | |
915 | } | |
916 | BOOST_CATCH(...){ | |
917 | node_impl_type::restore(x->impl(),next->impl(),header()->impl()); | |
918 | BOOST_RETHROW; | |
919 | } | |
920 | BOOST_CATCH_END | |
921 | } | |
922 | ||
b32b8144 FG |
923 | bool check_rollback_(node_type* x)const |
924 | { | |
925 | return in_place(x->value(),x,Category())&&super::check_rollback_(x); | |
926 | } | |
927 | ||
7c673cae FG |
928 | #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) |
929 | /* serialization */ | |
930 | ||
931 | template<typename Archive> | |
932 | void save_( | |
933 | Archive& ar,const unsigned int version,const index_saver_type& sm)const | |
934 | { | |
935 | save_(ar,version,sm,Category()); | |
936 | } | |
937 | ||
938 | template<typename Archive> | |
939 | void load_(Archive& ar,const unsigned int version,const index_loader_type& lm) | |
940 | { | |
941 | load_(ar,version,lm,Category()); | |
942 | } | |
943 | #endif | |
944 | ||
945 | #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING) | |
946 | /* invariant stuff */ | |
947 | ||
948 | bool invariant_()const | |
949 | { | |
950 | if(size()==0||begin()==end()){ | |
951 | if(size()!=0||begin()!=end()|| | |
952 | header()->left()!=header()->impl()|| | |
953 | header()->right()!=header()->impl())return false; | |
954 | } | |
955 | else{ | |
956 | if((size_type)std::distance(begin(),end())!=size())return false; | |
957 | ||
958 | std::size_t len=node_impl_type::black_count( | |
959 | leftmost()->impl(),root()->impl()); | |
960 | for(const_iterator it=begin(),it_end=end();it!=it_end;++it){ | |
961 | node_type* x=it.get_node(); | |
962 | node_type* left_x=node_type::from_impl(x->left()); | |
963 | node_type* right_x=node_type::from_impl(x->right()); | |
964 | ||
965 | if(x->color()==red){ | |
966 | if((left_x&&left_x->color()==red)|| | |
967 | (right_x&&right_x->color()==red))return false; | |
968 | } | |
969 | if(left_x&&comp_(key(x->value()),key(left_x->value())))return false; | |
970 | if(right_x&&comp_(key(right_x->value()),key(x->value())))return false; | |
971 | if(!left_x&&!right_x&& | |
972 | node_impl_type::black_count(x->impl(),root()->impl())!=len) | |
973 | return false; | |
974 | if(!AugmentPolicy::invariant(x->impl()))return false; | |
975 | } | |
976 | ||
977 | if(leftmost()->impl()!=node_impl_type::minimum(root()->impl())) | |
978 | return false; | |
979 | if(rightmost()->impl()!=node_impl_type::maximum(root()->impl())) | |
980 | return false; | |
981 | } | |
982 | ||
983 | return super::invariant_(); | |
984 | } | |
985 | ||
986 | ||
987 | /* This forwarding function eases things for the boost::mem_fn construct | |
988 | * in BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT. Actually, | |
989 | * final_check_invariant is already an inherited member function of | |
990 | * ordered_index_impl. | |
991 | */ | |
992 | void check_invariant_()const{this->final_check_invariant_();} | |
993 | #endif | |
994 | ||
995 | protected: /* for the benefit of AugmentPolicy::augmented_interface */ | |
996 | node_type* header()const{return this->final_header();} | |
997 | node_type* root()const{return node_type::from_impl(header()->parent());} | |
998 | node_type* leftmost()const{return node_type::from_impl(header()->left());} | |
999 | node_type* rightmost()const{return node_type::from_impl(header()->right());} | |
1000 | ||
1001 | private: | |
1002 | void empty_initialize() | |
1003 | { | |
1004 | header()->color()=red; | |
1005 | /* used to distinguish header() from root, in iterator.operator++ */ | |
1006 | ||
1007 | header()->parent()=node_impl_pointer(0); | |
1008 | header()->left()=header()->impl(); | |
1009 | header()->right()=header()->impl(); | |
1010 | } | |
1011 | ||
1012 | struct link_info | |
1013 | { | |
1014 | /* coverity[uninit_ctor]: suppress warning */ | |
1015 | link_info():side(to_left){} | |
1016 | ||
1017 | ordered_index_side side; | |
1018 | node_impl_pointer pos; | |
1019 | }; | |
1020 | ||
1021 | bool link_point(key_param_type k,link_info& inf,ordered_unique_tag) | |
1022 | { | |
1023 | node_type* y=header(); | |
1024 | node_type* x=root(); | |
1025 | bool c=true; | |
1026 | while(x){ | |
1027 | y=x; | |
1028 | c=comp_(k,key(x->value())); | |
1029 | x=node_type::from_impl(c?x->left():x->right()); | |
1030 | } | |
1031 | node_type* yy=y; | |
1032 | if(c){ | |
1033 | if(yy==leftmost()){ | |
1034 | inf.side=to_left; | |
1035 | inf.pos=y->impl(); | |
1036 | return true; | |
1037 | } | |
1038 | else node_type::decrement(yy); | |
1039 | } | |
1040 | ||
1041 | if(comp_(key(yy->value()),k)){ | |
1042 | inf.side=c?to_left:to_right; | |
1043 | inf.pos=y->impl(); | |
1044 | return true; | |
1045 | } | |
1046 | else{ | |
1047 | inf.pos=yy->impl(); | |
1048 | return false; | |
1049 | } | |
1050 | } | |
1051 | ||
1052 | bool link_point(key_param_type k,link_info& inf,ordered_non_unique_tag) | |
1053 | { | |
1054 | node_type* y=header(); | |
1055 | node_type* x=root(); | |
1056 | bool c=true; | |
1057 | while (x){ | |
1058 | y=x; | |
1059 | c=comp_(k,key(x->value())); | |
1060 | x=node_type::from_impl(c?x->left():x->right()); | |
1061 | } | |
1062 | inf.side=c?to_left:to_right; | |
1063 | inf.pos=y->impl(); | |
1064 | return true; | |
1065 | } | |
1066 | ||
1067 | bool lower_link_point(key_param_type k,link_info& inf,ordered_non_unique_tag) | |
1068 | { | |
1069 | node_type* y=header(); | |
1070 | node_type* x=root(); | |
1071 | bool c=false; | |
1072 | while (x){ | |
1073 | y=x; | |
1074 | c=comp_(key(x->value()),k); | |
1075 | x=node_type::from_impl(c?x->right():x->left()); | |
1076 | } | |
1077 | inf.side=c?to_right:to_left; | |
1078 | inf.pos=y->impl(); | |
1079 | return true; | |
1080 | } | |
1081 | ||
1082 | bool hinted_link_point( | |
1083 | key_param_type k,node_type* position,link_info& inf,ordered_unique_tag) | |
1084 | { | |
1085 | if(position->impl()==header()->left()){ | |
1086 | if(size()>0&&comp_(k,key(position->value()))){ | |
1087 | inf.side=to_left; | |
1088 | inf.pos=position->impl(); | |
1089 | return true; | |
1090 | } | |
1091 | else return link_point(k,inf,ordered_unique_tag()); | |
1092 | } | |
1093 | else if(position==header()){ | |
1094 | if(comp_(key(rightmost()->value()),k)){ | |
1095 | inf.side=to_right; | |
1096 | inf.pos=rightmost()->impl(); | |
1097 | return true; | |
1098 | } | |
1099 | else return link_point(k,inf,ordered_unique_tag()); | |
1100 | } | |
1101 | else{ | |
1102 | node_type* before=position; | |
1103 | node_type::decrement(before); | |
1104 | if(comp_(key(before->value()),k)&&comp_(k,key(position->value()))){ | |
1105 | if(before->right()==node_impl_pointer(0)){ | |
1106 | inf.side=to_right; | |
1107 | inf.pos=before->impl(); | |
1108 | return true; | |
1109 | } | |
1110 | else{ | |
1111 | inf.side=to_left; | |
1112 | inf.pos=position->impl(); | |
1113 | return true; | |
1114 | } | |
1115 | } | |
1116 | else return link_point(k,inf,ordered_unique_tag()); | |
1117 | } | |
1118 | } | |
1119 | ||
1120 | bool hinted_link_point( | |
1121 | key_param_type k,node_type* position,link_info& inf,ordered_non_unique_tag) | |
1122 | { | |
1123 | if(position->impl()==header()->left()){ | |
1124 | if(size()>0&&!comp_(key(position->value()),k)){ | |
1125 | inf.side=to_left; | |
1126 | inf.pos=position->impl(); | |
1127 | return true; | |
1128 | } | |
1129 | else return lower_link_point(k,inf,ordered_non_unique_tag()); | |
1130 | } | |
1131 | else if(position==header()){ | |
1132 | if(!comp_(k,key(rightmost()->value()))){ | |
1133 | inf.side=to_right; | |
1134 | inf.pos=rightmost()->impl(); | |
1135 | return true; | |
1136 | } | |
1137 | else return link_point(k,inf,ordered_non_unique_tag()); | |
1138 | } | |
1139 | else{ | |
1140 | node_type* before=position; | |
1141 | node_type::decrement(before); | |
1142 | if(!comp_(k,key(before->value()))){ | |
1143 | if(!comp_(key(position->value()),k)){ | |
1144 | if(before->right()==node_impl_pointer(0)){ | |
1145 | inf.side=to_right; | |
1146 | inf.pos=before->impl(); | |
1147 | return true; | |
1148 | } | |
1149 | else{ | |
1150 | inf.side=to_left; | |
1151 | inf.pos=position->impl(); | |
1152 | return true; | |
1153 | } | |
1154 | } | |
1155 | else return lower_link_point(k,inf,ordered_non_unique_tag()); | |
1156 | } | |
1157 | else return link_point(k,inf,ordered_non_unique_tag()); | |
1158 | } | |
1159 | } | |
1160 | ||
1161 | void delete_all_nodes(node_type* x) | |
1162 | { | |
1163 | if(!x)return; | |
1164 | ||
1165 | delete_all_nodes(node_type::from_impl(x->left())); | |
1166 | delete_all_nodes(node_type::from_impl(x->right())); | |
1167 | this->final_delete_node_(static_cast<final_node_type*>(x)); | |
1168 | } | |
1169 | ||
b32b8144 | 1170 | bool in_place(value_param_type v,node_type* x,ordered_unique_tag)const |
7c673cae FG |
1171 | { |
1172 | node_type* y; | |
1173 | if(x!=leftmost()){ | |
1174 | y=x; | |
1175 | node_type::decrement(y); | |
1176 | if(!comp_(key(y->value()),key(v)))return false; | |
1177 | } | |
1178 | ||
1179 | y=x; | |
1180 | node_type::increment(y); | |
1181 | return y==header()||comp_(key(v),key(y->value())); | |
1182 | } | |
1183 | ||
b32b8144 | 1184 | bool in_place(value_param_type v,node_type* x,ordered_non_unique_tag)const |
7c673cae FG |
1185 | { |
1186 | node_type* y; | |
1187 | if(x!=leftmost()){ | |
1188 | y=x; | |
1189 | node_type::decrement(y); | |
1190 | if(comp_(key(v),key(y->value())))return false; | |
1191 | } | |
1192 | ||
1193 | y=x; | |
1194 | node_type::increment(y); | |
1195 | return y==header()||!comp_(key(y->value()),key(v)); | |
1196 | } | |
1197 | ||
1198 | #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) | |
1199 | void detach_iterators(node_type* x) | |
1200 | { | |
1201 | iterator it=make_iterator(x); | |
1202 | safe_mode::detach_equivalent_iterators(it); | |
1203 | } | |
1204 | #endif | |
1205 | ||
1206 | template<BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK> | |
1207 | std::pair<iterator,bool> emplace_impl(BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK) | |
1208 | { | |
1209 | BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT; | |
1210 | std::pair<final_node_type*,bool>p= | |
1211 | this->final_emplace_(BOOST_MULTI_INDEX_FORWARD_PARAM_PACK); | |
1212 | return std::pair<iterator,bool>(make_iterator(p.first),p.second); | |
1213 | } | |
1214 | ||
1215 | template<BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK> | |
1216 | iterator emplace_hint_impl( | |
1217 | iterator position,BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK) | |
1218 | { | |
1219 | BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); | |
1220 | BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); | |
1221 | BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT; | |
1222 | std::pair<final_node_type*,bool>p= | |
1223 | this->final_emplace_hint_( | |
1224 | static_cast<final_node_type*>(position.get_node()), | |
1225 | BOOST_MULTI_INDEX_FORWARD_PARAM_PACK); | |
1226 | return make_iterator(p.first); | |
1227 | } | |
1228 | ||
1229 | template<typename LowerBounder,typename UpperBounder> | |
1230 | std::pair<iterator,iterator> | |
1231 | range(LowerBounder lower,UpperBounder upper,none_unbounded_tag)const | |
1232 | { | |
1233 | node_type* y=header(); | |
1234 | node_type* z=root(); | |
1235 | ||
1236 | while(z){ | |
1237 | if(!lower(key(z->value()))){ | |
1238 | z=node_type::from_impl(z->right()); | |
1239 | } | |
1240 | else if(!upper(key(z->value()))){ | |
1241 | y=z; | |
1242 | z=node_type::from_impl(z->left()); | |
1243 | } | |
1244 | else{ | |
1245 | return std::pair<iterator,iterator>( | |
1246 | make_iterator( | |
1247 | lower_range(node_type::from_impl(z->left()),z,lower)), | |
1248 | make_iterator( | |
1249 | upper_range(node_type::from_impl(z->right()),y,upper))); | |
1250 | } | |
1251 | } | |
1252 | ||
1253 | return std::pair<iterator,iterator>(make_iterator(y),make_iterator(y)); | |
1254 | } | |
1255 | ||
1256 | template<typename LowerBounder,typename UpperBounder> | |
1257 | std::pair<iterator,iterator> | |
1258 | range(LowerBounder,UpperBounder upper,lower_unbounded_tag)const | |
1259 | { | |
1260 | return std::pair<iterator,iterator>( | |
1261 | begin(), | |
1262 | make_iterator(upper_range(root(),header(),upper))); | |
1263 | } | |
1264 | ||
1265 | template<typename LowerBounder,typename UpperBounder> | |
1266 | std::pair<iterator,iterator> | |
1267 | range(LowerBounder lower,UpperBounder,upper_unbounded_tag)const | |
1268 | { | |
1269 | return std::pair<iterator,iterator>( | |
1270 | make_iterator(lower_range(root(),header(),lower)), | |
1271 | end()); | |
1272 | } | |
1273 | ||
1274 | template<typename LowerBounder,typename UpperBounder> | |
1275 | std::pair<iterator,iterator> | |
1276 | range(LowerBounder,UpperBounder,both_unbounded_tag)const | |
1277 | { | |
1278 | return std::pair<iterator,iterator>(begin(),end()); | |
1279 | } | |
1280 | ||
1281 | template<typename LowerBounder> | |
1282 | node_type * lower_range(node_type* top,node_type* y,LowerBounder lower)const | |
1283 | { | |
1284 | while(top){ | |
1285 | if(lower(key(top->value()))){ | |
1286 | y=top; | |
1287 | top=node_type::from_impl(top->left()); | |
1288 | } | |
1289 | else top=node_type::from_impl(top->right()); | |
1290 | } | |
1291 | ||
1292 | return y; | |
1293 | } | |
1294 | ||
1295 | template<typename UpperBounder> | |
1296 | node_type * upper_range(node_type* top,node_type* y,UpperBounder upper)const | |
1297 | { | |
1298 | while(top){ | |
1299 | if(!upper(key(top->value()))){ | |
1300 | y=top; | |
1301 | top=node_type::from_impl(top->left()); | |
1302 | } | |
1303 | else top=node_type::from_impl(top->right()); | |
1304 | } | |
1305 | ||
1306 | return y; | |
1307 | } | |
1308 | ||
1309 | #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) | |
1310 | template<typename Archive> | |
1311 | void save_( | |
1312 | Archive& ar,const unsigned int version,const index_saver_type& sm, | |
1313 | ordered_unique_tag)const | |
1314 | { | |
1315 | super::save_(ar,version,sm); | |
1316 | } | |
1317 | ||
1318 | template<typename Archive> | |
1319 | void load_( | |
1320 | Archive& ar,const unsigned int version,const index_loader_type& lm, | |
1321 | ordered_unique_tag) | |
1322 | { | |
1323 | super::load_(ar,version,lm); | |
1324 | } | |
1325 | ||
1326 | template<typename Archive> | |
1327 | void save_( | |
1328 | Archive& ar,const unsigned int version,const index_saver_type& sm, | |
1329 | ordered_non_unique_tag)const | |
1330 | { | |
1331 | typedef duplicates_iterator<node_type,value_compare> dup_iterator; | |
1332 | ||
1333 | sm.save( | |
1334 | dup_iterator(begin().get_node(),end().get_node(),value_comp()), | |
1335 | dup_iterator(end().get_node(),value_comp()), | |
1336 | ar,version); | |
1337 | super::save_(ar,version,sm); | |
1338 | } | |
1339 | ||
1340 | template<typename Archive> | |
1341 | void load_( | |
1342 | Archive& ar,const unsigned int version,const index_loader_type& lm, | |
1343 | ordered_non_unique_tag) | |
1344 | { | |
1345 | lm.load( | |
1346 | ::boost::bind( | |
1347 | &ordered_index_impl::rearranger,this, | |
1348 | ::boost::arg<1>(),::boost::arg<2>()), | |
1349 | ar,version); | |
1350 | super::load_(ar,version,lm); | |
1351 | } | |
1352 | ||
1353 | void rearranger(node_type* position,node_type *x) | |
1354 | { | |
1355 | if(!position||comp_(key(position->value()),key(x->value()))){ | |
1356 | position=lower_bound(key(x->value())).get_node(); | |
1357 | } | |
1358 | else if(comp_(key(x->value()),key(position->value()))){ | |
1359 | /* inconsistent rearrangement */ | |
1360 | throw_exception( | |
1361 | archive::archive_exception( | |
1362 | archive::archive_exception::other_exception)); | |
1363 | } | |
1364 | else node_type::increment(position); | |
1365 | ||
1366 | if(position!=x){ | |
1367 | node_impl_type::rebalance_for_erase( | |
1368 | x->impl(),header()->parent(),header()->left(),header()->right()); | |
1369 | node_impl_type::restore( | |
1370 | x->impl(),position->impl(),header()->impl()); | |
1371 | } | |
1372 | } | |
1373 | #endif /* serialization */ | |
1374 | ||
1375 | protected: /* for the benefit of AugmentPolicy::augmented_interface */ | |
1376 | key_from_value key; | |
1377 | key_compare comp_; | |
1378 | ||
1379 | #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\ | |
1380 | BOOST_WORKAROUND(__MWERKS__,<=0x3003) | |
1381 | #pragma parse_mfunc_templ reset | |
1382 | #endif | |
1383 | }; | |
1384 | ||
1385 | template< | |
1386 | typename KeyFromValue,typename Compare, | |
1387 | typename SuperMeta,typename TagList,typename Category,typename AugmentPolicy | |
1388 | > | |
1389 | class ordered_index: | |
1390 | public AugmentPolicy::template augmented_interface< | |
1391 | ordered_index_impl< | |
1392 | KeyFromValue,Compare,SuperMeta,TagList,Category,AugmentPolicy | |
1393 | > | |
1394 | >::type | |
1395 | { | |
1396 | typedef typename AugmentPolicy::template | |
1397 | augmented_interface< | |
1398 | ordered_index_impl< | |
1399 | KeyFromValue,Compare, | |
1400 | SuperMeta,TagList,Category,AugmentPolicy | |
1401 | > | |
1402 | >::type super; | |
1403 | public: | |
1404 | typedef typename super::ctor_args_list ctor_args_list; | |
1405 | typedef typename super::allocator_type allocator_type; | |
1406 | typedef typename super::iterator iterator; | |
1407 | ||
1408 | /* construct/copy/destroy | |
1409 | * Default and copy ctors are in the protected section as indices are | |
1410 | * not supposed to be created on their own. No range ctor either. | |
1411 | */ | |
1412 | ||
1413 | ordered_index& operator=(const ordered_index& x) | |
1414 | { | |
1415 | this->final()=x.final(); | |
1416 | return *this; | |
1417 | } | |
1418 | ||
1419 | #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) | |
1420 | ordered_index& operator=( | |
1421 | std::initializer_list<BOOST_DEDUCED_TYPENAME super::value_type> list) | |
1422 | { | |
1423 | this->final()=list; | |
1424 | return *this; | |
1425 | } | |
1426 | #endif | |
1427 | ||
1428 | protected: | |
1429 | ordered_index( | |
1430 | const ctor_args_list& args_list,const allocator_type& al): | |
1431 | super(args_list,al){} | |
1432 | ||
92f5a8d4 | 1433 | ordered_index(const ordered_index& x):super(x){} |
7c673cae FG |
1434 | |
1435 | ordered_index(const ordered_index& x,do_not_copy_elements_tag): | |
92f5a8d4 | 1436 | super(x,do_not_copy_elements_tag()){} |
7c673cae FG |
1437 | }; |
1438 | ||
1439 | /* comparison */ | |
1440 | ||
1441 | template< | |
1442 | typename KeyFromValue1,typename Compare1, | |
1443 | typename SuperMeta1,typename TagList1,typename Category1, | |
1444 | typename AugmentPolicy1, | |
1445 | typename KeyFromValue2,typename Compare2, | |
1446 | typename SuperMeta2,typename TagList2,typename Category2, | |
1447 | typename AugmentPolicy2 | |
1448 | > | |
1449 | bool operator==( | |
1450 | const ordered_index< | |
1451 | KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1,AugmentPolicy1>& x, | |
1452 | const ordered_index< | |
1453 | KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2,AugmentPolicy2>& y) | |
1454 | { | |
1455 | return x.size()==y.size()&&std::equal(x.begin(),x.end(),y.begin()); | |
1456 | } | |
1457 | ||
1458 | template< | |
1459 | typename KeyFromValue1,typename Compare1, | |
1460 | typename SuperMeta1,typename TagList1,typename Category1, | |
1461 | typename AugmentPolicy1, | |
1462 | typename KeyFromValue2,typename Compare2, | |
1463 | typename SuperMeta2,typename TagList2,typename Category2, | |
1464 | typename AugmentPolicy2 | |
1465 | > | |
1466 | bool operator<( | |
1467 | const ordered_index< | |
1468 | KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1,AugmentPolicy1>& x, | |
1469 | const ordered_index< | |
1470 | KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2,AugmentPolicy2>& y) | |
1471 | { | |
1472 | return std::lexicographical_compare(x.begin(),x.end(),y.begin(),y.end()); | |
1473 | } | |
1474 | ||
1475 | template< | |
1476 | typename KeyFromValue1,typename Compare1, | |
1477 | typename SuperMeta1,typename TagList1,typename Category1, | |
1478 | typename AugmentPolicy1, | |
1479 | typename KeyFromValue2,typename Compare2, | |
1480 | typename SuperMeta2,typename TagList2,typename Category2, | |
1481 | typename AugmentPolicy2 | |
1482 | > | |
1483 | bool operator!=( | |
1484 | const ordered_index< | |
1485 | KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1,AugmentPolicy1>& x, | |
1486 | const ordered_index< | |
1487 | KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2,AugmentPolicy2>& y) | |
1488 | { | |
1489 | return !(x==y); | |
1490 | } | |
1491 | ||
1492 | template< | |
1493 | typename KeyFromValue1,typename Compare1, | |
1494 | typename SuperMeta1,typename TagList1,typename Category1, | |
1495 | typename AugmentPolicy1, | |
1496 | typename KeyFromValue2,typename Compare2, | |
1497 | typename SuperMeta2,typename TagList2,typename Category2, | |
1498 | typename AugmentPolicy2 | |
1499 | > | |
1500 | bool operator>( | |
1501 | const ordered_index< | |
1502 | KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1,AugmentPolicy1>& x, | |
1503 | const ordered_index< | |
1504 | KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2,AugmentPolicy2>& y) | |
1505 | { | |
1506 | return y<x; | |
1507 | } | |
1508 | ||
1509 | template< | |
1510 | typename KeyFromValue1,typename Compare1, | |
1511 | typename SuperMeta1,typename TagList1,typename Category1, | |
1512 | typename AugmentPolicy1, | |
1513 | typename KeyFromValue2,typename Compare2, | |
1514 | typename SuperMeta2,typename TagList2,typename Category2, | |
1515 | typename AugmentPolicy2 | |
1516 | > | |
1517 | bool operator>=( | |
1518 | const ordered_index< | |
1519 | KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1,AugmentPolicy1>& x, | |
1520 | const ordered_index< | |
1521 | KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2,AugmentPolicy2>& y) | |
1522 | { | |
1523 | return !(x<y); | |
1524 | } | |
1525 | ||
1526 | template< | |
1527 | typename KeyFromValue1,typename Compare1, | |
1528 | typename SuperMeta1,typename TagList1,typename Category1, | |
1529 | typename AugmentPolicy1, | |
1530 | typename KeyFromValue2,typename Compare2, | |
1531 | typename SuperMeta2,typename TagList2,typename Category2, | |
1532 | typename AugmentPolicy2 | |
1533 | > | |
1534 | bool operator<=( | |
1535 | const ordered_index< | |
1536 | KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1,AugmentPolicy1>& x, | |
1537 | const ordered_index< | |
1538 | KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2,AugmentPolicy2>& y) | |
1539 | { | |
1540 | return !(x>y); | |
1541 | } | |
1542 | ||
1543 | /* specialized algorithms */ | |
1544 | ||
1545 | template< | |
1546 | typename KeyFromValue,typename Compare, | |
1547 | typename SuperMeta,typename TagList,typename Category,typename AugmentPolicy | |
1548 | > | |
1549 | void swap( | |
1550 | ordered_index< | |
1551 | KeyFromValue,Compare,SuperMeta,TagList,Category,AugmentPolicy>& x, | |
1552 | ordered_index< | |
1553 | KeyFromValue,Compare,SuperMeta,TagList,Category,AugmentPolicy>& y) | |
1554 | { | |
1555 | x.swap(y); | |
1556 | } | |
1557 | ||
1558 | } /* namespace multi_index::detail */ | |
1559 | ||
1560 | } /* namespace multi_index */ | |
1561 | ||
1562 | } /* namespace boost */ | |
1563 | ||
1564 | /* Boost.Foreach compatibility */ | |
1565 | ||
1566 | template< | |
1567 | typename KeyFromValue,typename Compare, | |
1568 | typename SuperMeta,typename TagList,typename Category,typename AugmentPolicy | |
1569 | > | |
1570 | inline boost::mpl::true_* boost_foreach_is_noncopyable( | |
1571 | boost::multi_index::detail::ordered_index< | |
1572 | KeyFromValue,Compare,SuperMeta,TagList,Category,AugmentPolicy>*&, | |
1573 | boost_foreach_argument_dependent_lookup_hack) | |
1574 | { | |
1575 | return 0; | |
1576 | } | |
1577 | ||
1578 | #undef BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT | |
1579 | #undef BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT_OF | |
1580 | ||
1581 | #endif |