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