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