Chris@101
|
1 /* Copyright 2003-2014 Joaquin M Lopez Munoz.
|
Chris@16
|
2 * Distributed under the Boost Software License, Version 1.0.
|
Chris@16
|
3 * (See accompanying file LICENSE_1_0.txt or copy at
|
Chris@16
|
4 * http://www.boost.org/LICENSE_1_0.txt)
|
Chris@16
|
5 *
|
Chris@16
|
6 * See http://www.boost.org/libs/multi_index for library home page.
|
Chris@16
|
7 */
|
Chris@16
|
8
|
Chris@16
|
9 #ifndef BOOST_MULTI_INDEX_SEQUENCED_INDEX_HPP
|
Chris@16
|
10 #define BOOST_MULTI_INDEX_SEQUENCED_INDEX_HPP
|
Chris@16
|
11
|
Chris@101
|
12 #if defined(_MSC_VER)
|
Chris@16
|
13 #pragma once
|
Chris@16
|
14 #endif
|
Chris@16
|
15
|
Chris@16
|
16 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
|
Chris@16
|
17 #include <boost/call_traits.hpp>
|
Chris@16
|
18 #include <boost/detail/allocator_utilities.hpp>
|
Chris@16
|
19 #include <boost/detail/no_exceptions_support.hpp>
|
Chris@16
|
20 #include <boost/detail/workaround.hpp>
|
Chris@16
|
21 #include <boost/foreach_fwd.hpp>
|
Chris@16
|
22 #include <boost/iterator/reverse_iterator.hpp>
|
Chris@16
|
23 #include <boost/move/core.hpp>
|
Chris@16
|
24 #include <boost/move/utility.hpp>
|
Chris@16
|
25 #include <boost/mpl/bool.hpp>
|
Chris@16
|
26 #include <boost/mpl/not.hpp>
|
Chris@16
|
27 #include <boost/mpl/push_front.hpp>
|
Chris@16
|
28 #include <boost/multi_index/detail/access_specifier.hpp>
|
Chris@16
|
29 #include <boost/multi_index/detail/bidir_node_iterator.hpp>
|
Chris@16
|
30 #include <boost/multi_index/detail/do_not_copy_elements_tag.hpp>
|
Chris@16
|
31 #include <boost/multi_index/detail/index_node_base.hpp>
|
Chris@16
|
32 #include <boost/multi_index/detail/safe_mode.hpp>
|
Chris@16
|
33 #include <boost/multi_index/detail/scope_guard.hpp>
|
Chris@16
|
34 #include <boost/multi_index/detail/seq_index_node.hpp>
|
Chris@16
|
35 #include <boost/multi_index/detail/seq_index_ops.hpp>
|
Chris@16
|
36 #include <boost/multi_index/detail/vartempl_support.hpp>
|
Chris@16
|
37 #include <boost/multi_index/sequenced_index_fwd.hpp>
|
Chris@16
|
38 #include <boost/tuple/tuple.hpp>
|
Chris@16
|
39 #include <boost/type_traits/is_integral.hpp>
|
Chris@16
|
40 #include <cstddef>
|
Chris@16
|
41 #include <functional>
|
Chris@16
|
42 #include <utility>
|
Chris@16
|
43
|
Chris@16
|
44 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
|
Chris@16
|
45 #include<initializer_list>
|
Chris@16
|
46 #endif
|
Chris@16
|
47
|
Chris@16
|
48 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
|
Chris@16
|
49 #include <boost/bind.hpp>
|
Chris@16
|
50 #endif
|
Chris@16
|
51
|
Chris@16
|
52 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
|
Chris@16
|
53 #define BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT_OF(x) \
|
Chris@16
|
54 detail::scope_guard BOOST_JOIN(check_invariant_,__LINE__)= \
|
Chris@16
|
55 detail::make_obj_guard(x,&sequenced_index::check_invariant_); \
|
Chris@16
|
56 BOOST_JOIN(check_invariant_,__LINE__).touch();
|
Chris@16
|
57 #define BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT \
|
Chris@16
|
58 BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT_OF(*this)
|
Chris@16
|
59 #else
|
Chris@16
|
60 #define BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT_OF(x)
|
Chris@16
|
61 #define BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT
|
Chris@16
|
62 #endif
|
Chris@16
|
63
|
Chris@16
|
64 namespace boost{
|
Chris@16
|
65
|
Chris@16
|
66 namespace multi_index{
|
Chris@16
|
67
|
Chris@16
|
68 namespace detail{
|
Chris@16
|
69
|
Chris@16
|
70 /* sequenced_index adds a layer of sequenced indexing to a given Super */
|
Chris@16
|
71
|
Chris@16
|
72 template<typename SuperMeta,typename TagList>
|
Chris@16
|
73 class sequenced_index:
|
Chris@16
|
74 BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS SuperMeta::type
|
Chris@16
|
75
|
Chris@16
|
76 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
|
Chris@16
|
77 ,public safe_mode::safe_container<
|
Chris@16
|
78 sequenced_index<SuperMeta,TagList> >
|
Chris@16
|
79 #endif
|
Chris@16
|
80
|
Chris@16
|
81 {
|
Chris@16
|
82 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
|
Chris@16
|
83 BOOST_WORKAROUND(__MWERKS__,<=0x3003)
|
Chris@16
|
84 /* The "ISO C++ Template Parser" option in CW8.3 has a problem with the
|
Chris@16
|
85 * lifetime of const references bound to temporaries --precisely what
|
Chris@16
|
86 * scopeguards are.
|
Chris@16
|
87 */
|
Chris@16
|
88
|
Chris@16
|
89 #pragma parse_mfunc_templ off
|
Chris@16
|
90 #endif
|
Chris@16
|
91
|
Chris@16
|
92 typedef typename SuperMeta::type super;
|
Chris@16
|
93
|
Chris@16
|
94 protected:
|
Chris@16
|
95 typedef sequenced_index_node<
|
Chris@16
|
96 typename super::node_type> node_type;
|
Chris@16
|
97
|
Chris@16
|
98 private:
|
Chris@16
|
99 typedef typename node_type::impl_type node_impl_type;
|
Chris@16
|
100
|
Chris@16
|
101 public:
|
Chris@16
|
102 /* types */
|
Chris@16
|
103
|
Chris@16
|
104 typedef typename node_type::value_type value_type;
|
Chris@16
|
105 typedef tuples::null_type ctor_args;
|
Chris@16
|
106 typedef typename super::final_allocator_type allocator_type;
|
Chris@16
|
107 typedef typename allocator_type::reference reference;
|
Chris@16
|
108 typedef typename allocator_type::const_reference const_reference;
|
Chris@16
|
109
|
Chris@16
|
110 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
|
Chris@16
|
111 typedef safe_mode::safe_iterator<
|
Chris@16
|
112 bidir_node_iterator<node_type>,
|
Chris@16
|
113 sequenced_index> iterator;
|
Chris@16
|
114 #else
|
Chris@16
|
115 typedef bidir_node_iterator<node_type> iterator;
|
Chris@16
|
116 #endif
|
Chris@16
|
117
|
Chris@16
|
118 typedef iterator const_iterator;
|
Chris@16
|
119
|
Chris@16
|
120 typedef std::size_t size_type;
|
Chris@16
|
121 typedef std::ptrdiff_t difference_type;
|
Chris@16
|
122 typedef typename allocator_type::pointer pointer;
|
Chris@16
|
123 typedef typename allocator_type::const_pointer const_pointer;
|
Chris@16
|
124 typedef typename
|
Chris@16
|
125 boost::reverse_iterator<iterator> reverse_iterator;
|
Chris@16
|
126 typedef typename
|
Chris@16
|
127 boost::reverse_iterator<const_iterator> const_reverse_iterator;
|
Chris@16
|
128 typedef TagList tag_list;
|
Chris@16
|
129
|
Chris@16
|
130 protected:
|
Chris@16
|
131 typedef typename super::final_node_type final_node_type;
|
Chris@16
|
132 typedef tuples::cons<
|
Chris@16
|
133 ctor_args,
|
Chris@16
|
134 typename super::ctor_args_list> ctor_args_list;
|
Chris@16
|
135 typedef typename mpl::push_front<
|
Chris@16
|
136 typename super::index_type_list,
|
Chris@16
|
137 sequenced_index>::type index_type_list;
|
Chris@16
|
138 typedef typename mpl::push_front<
|
Chris@16
|
139 typename super::iterator_type_list,
|
Chris@16
|
140 iterator>::type iterator_type_list;
|
Chris@16
|
141 typedef typename mpl::push_front<
|
Chris@16
|
142 typename super::const_iterator_type_list,
|
Chris@16
|
143 const_iterator>::type const_iterator_type_list;
|
Chris@16
|
144 typedef typename super::copy_map_type copy_map_type;
|
Chris@16
|
145
|
Chris@16
|
146 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
|
Chris@16
|
147 typedef typename super::index_saver_type index_saver_type;
|
Chris@16
|
148 typedef typename super::index_loader_type index_loader_type;
|
Chris@16
|
149 #endif
|
Chris@16
|
150
|
Chris@16
|
151 private:
|
Chris@16
|
152 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
|
Chris@16
|
153 typedef safe_mode::safe_container<
|
Chris@16
|
154 sequenced_index> safe_super;
|
Chris@16
|
155 #endif
|
Chris@16
|
156
|
Chris@16
|
157 typedef typename call_traits<value_type>::param_type value_param_type;
|
Chris@16
|
158
|
Chris@16
|
159 /* Needed to avoid commas in BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL
|
Chris@16
|
160 * expansion.
|
Chris@16
|
161 */
|
Chris@16
|
162
|
Chris@16
|
163 typedef std::pair<iterator,bool> emplace_return_type;
|
Chris@16
|
164
|
Chris@16
|
165 public:
|
Chris@16
|
166
|
Chris@16
|
167 /* construct/copy/destroy
|
Chris@16
|
168 * Default and copy ctors are in the protected section as indices are
|
Chris@16
|
169 * not supposed to be created on their own. No range ctor either.
|
Chris@16
|
170 */
|
Chris@16
|
171
|
Chris@16
|
172 sequenced_index<SuperMeta,TagList>& operator=(
|
Chris@16
|
173 const sequenced_index<SuperMeta,TagList>& x)
|
Chris@16
|
174 {
|
Chris@16
|
175 this->final()=x.final();
|
Chris@16
|
176 return *this;
|
Chris@16
|
177 }
|
Chris@16
|
178
|
Chris@16
|
179 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
|
Chris@16
|
180 sequenced_index<SuperMeta,TagList>& operator=(
|
Chris@16
|
181 std::initializer_list<value_type> list)
|
Chris@16
|
182 {
|
Chris@16
|
183 this->final()=list;
|
Chris@16
|
184 return *this;
|
Chris@16
|
185 }
|
Chris@16
|
186 #endif
|
Chris@16
|
187
|
Chris@16
|
188 template <class InputIterator>
|
Chris@16
|
189 void assign(InputIterator first,InputIterator last)
|
Chris@16
|
190 {
|
Chris@16
|
191 assign_iter(first,last,mpl::not_<is_integral<InputIterator> >());
|
Chris@16
|
192 }
|
Chris@16
|
193
|
Chris@16
|
194 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
|
Chris@16
|
195 void assign(std::initializer_list<value_type> list)
|
Chris@16
|
196 {
|
Chris@16
|
197 assign(list.begin(),list.end());
|
Chris@16
|
198 }
|
Chris@16
|
199 #endif
|
Chris@16
|
200
|
Chris@16
|
201 void assign(size_type n,value_param_type value)
|
Chris@16
|
202 {
|
Chris@16
|
203 BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
|
Chris@16
|
204 clear();
|
Chris@16
|
205 for(size_type i=0;i<n;++i)push_back(value);
|
Chris@16
|
206 }
|
Chris@16
|
207
|
Chris@101
|
208 allocator_type get_allocator()const BOOST_NOEXCEPT
|
Chris@16
|
209 {
|
Chris@16
|
210 return this->final().get_allocator();
|
Chris@16
|
211 }
|
Chris@16
|
212
|
Chris@16
|
213 /* iterators */
|
Chris@16
|
214
|
Chris@101
|
215 iterator begin()BOOST_NOEXCEPT
|
Chris@16
|
216 {return make_iterator(node_type::from_impl(header()->next()));}
|
Chris@101
|
217 const_iterator begin()const BOOST_NOEXCEPT
|
Chris@16
|
218 {return make_iterator(node_type::from_impl(header()->next()));}
|
Chris@101
|
219 iterator
|
Chris@101
|
220 end()BOOST_NOEXCEPT{return make_iterator(header());}
|
Chris@101
|
221 const_iterator
|
Chris@101
|
222 end()const BOOST_NOEXCEPT{return make_iterator(header());}
|
Chris@101
|
223 reverse_iterator
|
Chris@101
|
224 rbegin()BOOST_NOEXCEPT{return boost::make_reverse_iterator(end());}
|
Chris@101
|
225 const_reverse_iterator
|
Chris@101
|
226 rbegin()const BOOST_NOEXCEPT{return boost::make_reverse_iterator(end());}
|
Chris@101
|
227 reverse_iterator
|
Chris@101
|
228 rend()BOOST_NOEXCEPT{return boost::make_reverse_iterator(begin());}
|
Chris@101
|
229 const_reverse_iterator
|
Chris@101
|
230 rend()const BOOST_NOEXCEPT{return boost::make_reverse_iterator(begin());}
|
Chris@101
|
231 const_iterator
|
Chris@101
|
232 cbegin()const BOOST_NOEXCEPT{return begin();}
|
Chris@101
|
233 const_iterator
|
Chris@101
|
234 cend()const BOOST_NOEXCEPT{return end();}
|
Chris@101
|
235 const_reverse_iterator
|
Chris@101
|
236 crbegin()const BOOST_NOEXCEPT{return rbegin();}
|
Chris@101
|
237 const_reverse_iterator
|
Chris@101
|
238 crend()const BOOST_NOEXCEPT{return rend();}
|
Chris@16
|
239
|
Chris@16
|
240 iterator iterator_to(const value_type& x)
|
Chris@16
|
241 {
|
Chris@16
|
242 return make_iterator(node_from_value<node_type>(&x));
|
Chris@16
|
243 }
|
Chris@16
|
244
|
Chris@16
|
245 const_iterator iterator_to(const value_type& x)const
|
Chris@16
|
246 {
|
Chris@16
|
247 return make_iterator(node_from_value<node_type>(&x));
|
Chris@16
|
248 }
|
Chris@16
|
249
|
Chris@16
|
250 /* capacity */
|
Chris@16
|
251
|
Chris@101
|
252 bool empty()const BOOST_NOEXCEPT{return this->final_empty_();}
|
Chris@101
|
253 size_type size()const BOOST_NOEXCEPT{return this->final_size_();}
|
Chris@101
|
254 size_type max_size()const BOOST_NOEXCEPT{return this->final_max_size_();}
|
Chris@16
|
255
|
Chris@16
|
256 void resize(size_type n)
|
Chris@16
|
257 {
|
Chris@16
|
258 BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
|
Chris@16
|
259 if(n>size()){
|
Chris@16
|
260 for(size_type m=n-size();m--;)
|
Chris@16
|
261 this->final_emplace_(BOOST_MULTI_INDEX_NULL_PARAM_PACK);
|
Chris@16
|
262 }
|
Chris@16
|
263 else if(n<size()){for(size_type m=size()-n;m--;)pop_back();}
|
Chris@16
|
264 }
|
Chris@16
|
265
|
Chris@16
|
266 void resize(size_type n,value_param_type x)
|
Chris@16
|
267 {
|
Chris@16
|
268 BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
|
Chris@16
|
269 if(n>size())insert(end(),n-size(),x);
|
Chris@16
|
270 else if(n<size())for(size_type m=size()-n;m--;)pop_back();
|
Chris@16
|
271 }
|
Chris@16
|
272
|
Chris@16
|
273 /* access: no non-const versions provided as sequenced_index
|
Chris@16
|
274 * handles const elements.
|
Chris@16
|
275 */
|
Chris@16
|
276
|
Chris@16
|
277 const_reference front()const{return *begin();}
|
Chris@16
|
278 const_reference back()const{return *--end();}
|
Chris@16
|
279
|
Chris@16
|
280 /* modifiers */
|
Chris@16
|
281
|
Chris@16
|
282 BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL(
|
Chris@16
|
283 emplace_return_type,emplace_front,emplace_front_impl)
|
Chris@16
|
284
|
Chris@16
|
285 std::pair<iterator,bool> push_front(const value_type& x)
|
Chris@16
|
286 {return insert(begin(),x);}
|
Chris@16
|
287 std::pair<iterator,bool> push_front(BOOST_RV_REF(value_type) x)
|
Chris@16
|
288 {return insert(begin(),boost::move(x));}
|
Chris@16
|
289 void pop_front(){erase(begin());}
|
Chris@16
|
290
|
Chris@16
|
291 BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL(
|
Chris@16
|
292 emplace_return_type,emplace_back,emplace_back_impl)
|
Chris@16
|
293
|
Chris@16
|
294 std::pair<iterator,bool> push_back(const value_type& x)
|
Chris@16
|
295 {return insert(end(),x);}
|
Chris@16
|
296 std::pair<iterator,bool> push_back(BOOST_RV_REF(value_type) x)
|
Chris@16
|
297 {return insert(end(),boost::move(x));}
|
Chris@16
|
298 void pop_back(){erase(--end());}
|
Chris@16
|
299
|
Chris@16
|
300 BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL_EXTRA_ARG(
|
Chris@16
|
301 emplace_return_type,emplace,emplace_impl,iterator,position)
|
Chris@16
|
302
|
Chris@16
|
303 std::pair<iterator,bool> insert(iterator position,const value_type& x)
|
Chris@16
|
304 {
|
Chris@16
|
305 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
|
Chris@16
|
306 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
|
Chris@16
|
307 BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
|
Chris@16
|
308 std::pair<final_node_type*,bool> p=this->final_insert_(x);
|
Chris@16
|
309 if(p.second&&position.get_node()!=header()){
|
Chris@16
|
310 relink(position.get_node(),p.first);
|
Chris@16
|
311 }
|
Chris@16
|
312 return std::pair<iterator,bool>(make_iterator(p.first),p.second);
|
Chris@16
|
313 }
|
Chris@16
|
314
|
Chris@16
|
315 std::pair<iterator,bool> insert(iterator position,BOOST_RV_REF(value_type) x)
|
Chris@16
|
316 {
|
Chris@16
|
317 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
|
Chris@16
|
318 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
|
Chris@16
|
319 BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
|
Chris@16
|
320 std::pair<final_node_type*,bool> p=this->final_insert_rv_(x);
|
Chris@16
|
321 if(p.second&&position.get_node()!=header()){
|
Chris@16
|
322 relink(position.get_node(),p.first);
|
Chris@16
|
323 }
|
Chris@16
|
324 return std::pair<iterator,bool>(make_iterator(p.first),p.second);
|
Chris@16
|
325 }
|
Chris@16
|
326
|
Chris@16
|
327 void insert(iterator position,size_type n,value_param_type x)
|
Chris@16
|
328 {
|
Chris@16
|
329 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
|
Chris@16
|
330 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
|
Chris@16
|
331 BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
|
Chris@16
|
332 for(size_type i=0;i<n;++i)insert(position,x);
|
Chris@16
|
333 }
|
Chris@16
|
334
|
Chris@16
|
335 template<typename InputIterator>
|
Chris@16
|
336 void insert(iterator position,InputIterator first,InputIterator last)
|
Chris@16
|
337 {
|
Chris@16
|
338 insert_iter(position,first,last,mpl::not_<is_integral<InputIterator> >());
|
Chris@16
|
339 }
|
Chris@16
|
340
|
Chris@16
|
341 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
|
Chris@16
|
342 void insert(iterator position,std::initializer_list<value_type> list)
|
Chris@16
|
343 {
|
Chris@16
|
344 insert(position,list.begin(),list.end());
|
Chris@16
|
345 }
|
Chris@16
|
346 #endif
|
Chris@16
|
347
|
Chris@16
|
348 iterator erase(iterator position)
|
Chris@16
|
349 {
|
Chris@16
|
350 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
|
Chris@16
|
351 BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
|
Chris@16
|
352 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
|
Chris@16
|
353 BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
|
Chris@16
|
354 this->final_erase_(static_cast<final_node_type*>(position++.get_node()));
|
Chris@16
|
355 return position;
|
Chris@16
|
356 }
|
Chris@16
|
357
|
Chris@16
|
358 iterator erase(iterator first,iterator last)
|
Chris@16
|
359 {
|
Chris@16
|
360 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first);
|
Chris@16
|
361 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last);
|
Chris@16
|
362 BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,*this);
|
Chris@16
|
363 BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,*this);
|
Chris@16
|
364 BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last);
|
Chris@16
|
365 BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
|
Chris@16
|
366 while(first!=last){
|
Chris@16
|
367 first=erase(first);
|
Chris@16
|
368 }
|
Chris@16
|
369 return first;
|
Chris@16
|
370 }
|
Chris@16
|
371
|
Chris@16
|
372 bool replace(iterator position,const value_type& x)
|
Chris@16
|
373 {
|
Chris@16
|
374 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
|
Chris@16
|
375 BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
|
Chris@16
|
376 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
|
Chris@16
|
377 BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
|
Chris@16
|
378 return this->final_replace_(
|
Chris@16
|
379 x,static_cast<final_node_type*>(position.get_node()));
|
Chris@16
|
380 }
|
Chris@16
|
381
|
Chris@16
|
382 bool replace(iterator position,BOOST_RV_REF(value_type) x)
|
Chris@16
|
383 {
|
Chris@16
|
384 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
|
Chris@16
|
385 BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
|
Chris@16
|
386 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
|
Chris@16
|
387 BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
|
Chris@16
|
388 return this->final_replace_rv_(
|
Chris@16
|
389 x,static_cast<final_node_type*>(position.get_node()));
|
Chris@16
|
390 }
|
Chris@16
|
391
|
Chris@16
|
392 template<typename Modifier>
|
Chris@16
|
393 bool modify(iterator position,Modifier mod)
|
Chris@16
|
394 {
|
Chris@16
|
395 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
|
Chris@16
|
396 BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
|
Chris@16
|
397 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
|
Chris@16
|
398 BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
|
Chris@16
|
399
|
Chris@16
|
400 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
|
Chris@16
|
401 /* MSVC++ 6.0 optimizer on safe mode code chokes if this
|
Chris@16
|
402 * this is not added. Left it for all compilers as it does no
|
Chris@16
|
403 * harm.
|
Chris@16
|
404 */
|
Chris@16
|
405
|
Chris@16
|
406 position.detach();
|
Chris@16
|
407 #endif
|
Chris@16
|
408
|
Chris@16
|
409 return this->final_modify_(
|
Chris@16
|
410 mod,static_cast<final_node_type*>(position.get_node()));
|
Chris@16
|
411 }
|
Chris@16
|
412
|
Chris@16
|
413 template<typename Modifier,typename Rollback>
|
Chris@101
|
414 bool modify(iterator position,Modifier mod,Rollback back_)
|
Chris@16
|
415 {
|
Chris@16
|
416 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
|
Chris@16
|
417 BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
|
Chris@16
|
418 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
|
Chris@16
|
419 BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
|
Chris@16
|
420
|
Chris@16
|
421 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
|
Chris@16
|
422 /* MSVC++ 6.0 optimizer on safe mode code chokes if this
|
Chris@16
|
423 * this is not added. Left it for all compilers as it does no
|
Chris@16
|
424 * harm.
|
Chris@16
|
425 */
|
Chris@16
|
426
|
Chris@16
|
427 position.detach();
|
Chris@16
|
428 #endif
|
Chris@16
|
429
|
Chris@16
|
430 return this->final_modify_(
|
Chris@101
|
431 mod,back_,static_cast<final_node_type*>(position.get_node()));
|
Chris@16
|
432 }
|
Chris@16
|
433
|
Chris@16
|
434 void swap(sequenced_index<SuperMeta,TagList>& x)
|
Chris@16
|
435 {
|
Chris@16
|
436 BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
|
Chris@16
|
437 BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT_OF(x);
|
Chris@16
|
438 this->final_swap_(x.final());
|
Chris@16
|
439 }
|
Chris@16
|
440
|
Chris@101
|
441 void clear()BOOST_NOEXCEPT
|
Chris@16
|
442 {
|
Chris@16
|
443 BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
|
Chris@16
|
444 this->final_clear_();
|
Chris@16
|
445 }
|
Chris@16
|
446
|
Chris@16
|
447 /* list operations */
|
Chris@16
|
448
|
Chris@16
|
449 void splice(iterator position,sequenced_index<SuperMeta,TagList>& x)
|
Chris@16
|
450 {
|
Chris@16
|
451 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
|
Chris@16
|
452 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
|
Chris@16
|
453 BOOST_MULTI_INDEX_CHECK_DIFFERENT_CONTAINER(*this,x);
|
Chris@16
|
454 BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
|
Chris@16
|
455 iterator first=x.begin(),last=x.end();
|
Chris@16
|
456 while(first!=last){
|
Chris@16
|
457 if(insert(position,*first).second)first=x.erase(first);
|
Chris@16
|
458 else ++first;
|
Chris@16
|
459 }
|
Chris@16
|
460 }
|
Chris@16
|
461
|
Chris@16
|
462 void splice(iterator position,sequenced_index<SuperMeta,TagList>& x,iterator i)
|
Chris@16
|
463 {
|
Chris@16
|
464 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
|
Chris@16
|
465 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
|
Chris@16
|
466 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(i);
|
Chris@16
|
467 BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(i);
|
Chris@16
|
468 BOOST_MULTI_INDEX_CHECK_IS_OWNER(i,x);
|
Chris@16
|
469 BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
|
Chris@16
|
470 if(&x==this){
|
Chris@16
|
471 if(position!=i)relink(position.get_node(),i.get_node());
|
Chris@16
|
472 }
|
Chris@16
|
473 else{
|
Chris@16
|
474 if(insert(position,*i).second){
|
Chris@16
|
475
|
Chris@16
|
476 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
|
Chris@16
|
477 /* MSVC++ 6.0 optimizer has a hard time with safe mode, and the following
|
Chris@16
|
478 * workaround is needed. Left it for all compilers as it does no
|
Chris@16
|
479 * harm.
|
Chris@16
|
480 */
|
Chris@16
|
481 i.detach();
|
Chris@16
|
482 x.erase(x.make_iterator(i.get_node()));
|
Chris@16
|
483 #else
|
Chris@16
|
484 x.erase(i);
|
Chris@16
|
485 #endif
|
Chris@16
|
486
|
Chris@16
|
487 }
|
Chris@16
|
488 }
|
Chris@16
|
489 }
|
Chris@16
|
490
|
Chris@16
|
491 void splice(
|
Chris@16
|
492 iterator position,sequenced_index<SuperMeta,TagList>& x,
|
Chris@16
|
493 iterator first,iterator last)
|
Chris@16
|
494 {
|
Chris@16
|
495 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
|
Chris@16
|
496 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
|
Chris@16
|
497 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first);
|
Chris@16
|
498 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last);
|
Chris@16
|
499 BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,x);
|
Chris@16
|
500 BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,x);
|
Chris@16
|
501 BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last);
|
Chris@16
|
502 BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
|
Chris@16
|
503 if(&x==this){
|
Chris@16
|
504 BOOST_MULTI_INDEX_CHECK_OUTSIDE_RANGE(position,first,last);
|
Chris@16
|
505 if(position!=last)relink(
|
Chris@16
|
506 position.get_node(),first.get_node(),last.get_node());
|
Chris@16
|
507 }
|
Chris@16
|
508 else{
|
Chris@16
|
509 while(first!=last){
|
Chris@16
|
510 if(insert(position,*first).second)first=x.erase(first);
|
Chris@16
|
511 else ++first;
|
Chris@16
|
512 }
|
Chris@16
|
513 }
|
Chris@16
|
514 }
|
Chris@16
|
515
|
Chris@16
|
516 void remove(value_param_type value)
|
Chris@16
|
517 {
|
Chris@16
|
518 sequenced_index_remove(
|
Chris@16
|
519 *this,std::bind2nd(std::equal_to<value_type>(),value));
|
Chris@16
|
520 }
|
Chris@16
|
521
|
Chris@16
|
522 template<typename Predicate>
|
Chris@16
|
523 void remove_if(Predicate pred)
|
Chris@16
|
524 {
|
Chris@16
|
525 sequenced_index_remove(*this,pred);
|
Chris@16
|
526 }
|
Chris@16
|
527
|
Chris@16
|
528 void unique()
|
Chris@16
|
529 {
|
Chris@16
|
530 sequenced_index_unique(*this,std::equal_to<value_type>());
|
Chris@16
|
531 }
|
Chris@16
|
532
|
Chris@16
|
533 template <class BinaryPredicate>
|
Chris@16
|
534 void unique(BinaryPredicate binary_pred)
|
Chris@16
|
535 {
|
Chris@16
|
536 sequenced_index_unique(*this,binary_pred);
|
Chris@16
|
537 }
|
Chris@16
|
538
|
Chris@16
|
539 void merge(sequenced_index<SuperMeta,TagList>& x)
|
Chris@16
|
540 {
|
Chris@16
|
541 sequenced_index_merge(*this,x,std::less<value_type>());
|
Chris@16
|
542 }
|
Chris@16
|
543
|
Chris@16
|
544 template <typename Compare>
|
Chris@16
|
545 void merge(sequenced_index<SuperMeta,TagList>& x,Compare comp)
|
Chris@16
|
546 {
|
Chris@16
|
547 sequenced_index_merge(*this,x,comp);
|
Chris@16
|
548 }
|
Chris@16
|
549
|
Chris@16
|
550 void sort()
|
Chris@16
|
551 {
|
Chris@16
|
552 BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
|
Chris@16
|
553 sequenced_index_sort(header(),std::less<value_type>());
|
Chris@16
|
554 }
|
Chris@16
|
555
|
Chris@16
|
556 template <typename Compare>
|
Chris@16
|
557 void sort(Compare comp)
|
Chris@16
|
558 {
|
Chris@16
|
559 BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
|
Chris@16
|
560 sequenced_index_sort(header(),comp);
|
Chris@16
|
561 }
|
Chris@16
|
562
|
Chris@101
|
563 void reverse()BOOST_NOEXCEPT
|
Chris@16
|
564 {
|
Chris@16
|
565 BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
|
Chris@16
|
566 node_impl_type::reverse(header()->impl());
|
Chris@16
|
567 }
|
Chris@16
|
568
|
Chris@16
|
569 /* rearrange operations */
|
Chris@16
|
570
|
Chris@16
|
571 void relocate(iterator position,iterator i)
|
Chris@16
|
572 {
|
Chris@16
|
573 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
|
Chris@16
|
574 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
|
Chris@16
|
575 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(i);
|
Chris@16
|
576 BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(i);
|
Chris@16
|
577 BOOST_MULTI_INDEX_CHECK_IS_OWNER(i,*this);
|
Chris@16
|
578 BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
|
Chris@16
|
579 if(position!=i)relink(position.get_node(),i.get_node());
|
Chris@16
|
580 }
|
Chris@16
|
581
|
Chris@16
|
582 void relocate(iterator position,iterator first,iterator last)
|
Chris@16
|
583 {
|
Chris@16
|
584 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
|
Chris@16
|
585 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
|
Chris@16
|
586 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first);
|
Chris@16
|
587 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last);
|
Chris@16
|
588 BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,*this);
|
Chris@16
|
589 BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,*this);
|
Chris@16
|
590 BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last);
|
Chris@16
|
591 BOOST_MULTI_INDEX_CHECK_OUTSIDE_RANGE(position,first,last);
|
Chris@16
|
592 BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
|
Chris@16
|
593 if(position!=last)relink(
|
Chris@16
|
594 position.get_node(),first.get_node(),last.get_node());
|
Chris@16
|
595 }
|
Chris@16
|
596
|
Chris@16
|
597 template<typename InputIterator>
|
Chris@16
|
598 void rearrange(InputIterator first)
|
Chris@16
|
599 {
|
Chris@16
|
600 BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
|
Chris@16
|
601 node_type* pos=header();
|
Chris@16
|
602 for(size_type s=size();s--;){
|
Chris@16
|
603 const value_type& v=*first++;
|
Chris@16
|
604 relink(pos,node_from_value<node_type>(&v));
|
Chris@16
|
605 }
|
Chris@16
|
606 }
|
Chris@16
|
607
|
Chris@16
|
608 BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS:
|
Chris@16
|
609 sequenced_index(const ctor_args_list& args_list,const allocator_type& al):
|
Chris@16
|
610 super(args_list.get_tail(),al)
|
Chris@16
|
611 {
|
Chris@16
|
612 empty_initialize();
|
Chris@16
|
613 }
|
Chris@16
|
614
|
Chris@16
|
615 sequenced_index(const sequenced_index<SuperMeta,TagList>& x):
|
Chris@16
|
616 super(x)
|
Chris@16
|
617
|
Chris@16
|
618 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
|
Chris@16
|
619 ,safe_super()
|
Chris@16
|
620 #endif
|
Chris@16
|
621
|
Chris@16
|
622 {
|
Chris@16
|
623 /* the actual copying takes place in subsequent call to copy_() */
|
Chris@16
|
624 }
|
Chris@16
|
625
|
Chris@16
|
626 sequenced_index(
|
Chris@16
|
627 const sequenced_index<SuperMeta,TagList>& x,do_not_copy_elements_tag):
|
Chris@16
|
628 super(x,do_not_copy_elements_tag())
|
Chris@16
|
629
|
Chris@16
|
630 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
|
Chris@16
|
631 ,safe_super()
|
Chris@16
|
632 #endif
|
Chris@16
|
633
|
Chris@16
|
634 {
|
Chris@16
|
635 empty_initialize();
|
Chris@16
|
636 }
|
Chris@16
|
637
|
Chris@16
|
638 ~sequenced_index()
|
Chris@16
|
639 {
|
Chris@16
|
640 /* the container is guaranteed to be empty by now */
|
Chris@16
|
641 }
|
Chris@16
|
642
|
Chris@16
|
643 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
|
Chris@16
|
644 iterator make_iterator(node_type* node){return iterator(node,this);}
|
Chris@16
|
645 const_iterator make_iterator(node_type* node)const
|
Chris@16
|
646 {return const_iterator(node,const_cast<sequenced_index*>(this));}
|
Chris@16
|
647 #else
|
Chris@16
|
648 iterator make_iterator(node_type* node){return iterator(node);}
|
Chris@16
|
649 const_iterator make_iterator(node_type* node)const
|
Chris@16
|
650 {return const_iterator(node);}
|
Chris@16
|
651 #endif
|
Chris@16
|
652
|
Chris@16
|
653 void copy_(
|
Chris@16
|
654 const sequenced_index<SuperMeta,TagList>& x,const copy_map_type& map)
|
Chris@16
|
655 {
|
Chris@16
|
656 node_type* org=x.header();
|
Chris@16
|
657 node_type* cpy=header();
|
Chris@16
|
658 do{
|
Chris@16
|
659 node_type* next_org=node_type::from_impl(org->next());
|
Chris@16
|
660 node_type* next_cpy=map.find(static_cast<final_node_type*>(next_org));
|
Chris@16
|
661 cpy->next()=next_cpy->impl();
|
Chris@16
|
662 next_cpy->prior()=cpy->impl();
|
Chris@16
|
663 org=next_org;
|
Chris@16
|
664 cpy=next_cpy;
|
Chris@16
|
665 }while(org!=x.header());
|
Chris@16
|
666
|
Chris@16
|
667 super::copy_(x,map);
|
Chris@16
|
668 }
|
Chris@16
|
669
|
Chris@16
|
670 template<typename Variant>
|
Chris@101
|
671 final_node_type* insert_(
|
Chris@101
|
672 value_param_type v,final_node_type*& x,Variant variant)
|
Chris@16
|
673 {
|
Chris@101
|
674 final_node_type* res=super::insert_(v,x,variant);
|
Chris@101
|
675 if(res==x)link(static_cast<node_type*>(x));
|
Chris@16
|
676 return res;
|
Chris@16
|
677 }
|
Chris@16
|
678
|
Chris@16
|
679 template<typename Variant>
|
Chris@101
|
680 final_node_type* insert_(
|
Chris@101
|
681 value_param_type v,node_type* position,final_node_type*& x,Variant variant)
|
Chris@16
|
682 {
|
Chris@101
|
683 final_node_type* res=super::insert_(v,position,x,variant);
|
Chris@101
|
684 if(res==x)link(static_cast<node_type*>(x));
|
Chris@16
|
685 return res;
|
Chris@16
|
686 }
|
Chris@16
|
687
|
Chris@16
|
688 void erase_(node_type* x)
|
Chris@16
|
689 {
|
Chris@16
|
690 unlink(x);
|
Chris@16
|
691 super::erase_(x);
|
Chris@16
|
692
|
Chris@16
|
693 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
|
Chris@16
|
694 detach_iterators(x);
|
Chris@16
|
695 #endif
|
Chris@16
|
696 }
|
Chris@16
|
697
|
Chris@16
|
698 void delete_all_nodes_()
|
Chris@16
|
699 {
|
Chris@16
|
700 for(node_type* x=node_type::from_impl(header()->next());x!=header();){
|
Chris@16
|
701 node_type* y=node_type::from_impl(x->next());
|
Chris@16
|
702 this->final_delete_node_(static_cast<final_node_type*>(x));
|
Chris@16
|
703 x=y;
|
Chris@16
|
704 }
|
Chris@16
|
705 }
|
Chris@16
|
706
|
Chris@16
|
707 void clear_()
|
Chris@16
|
708 {
|
Chris@16
|
709 super::clear_();
|
Chris@16
|
710 empty_initialize();
|
Chris@16
|
711
|
Chris@16
|
712 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
|
Chris@16
|
713 safe_super::detach_dereferenceable_iterators();
|
Chris@16
|
714 #endif
|
Chris@16
|
715 }
|
Chris@16
|
716
|
Chris@16
|
717 void swap_(sequenced_index<SuperMeta,TagList>& x)
|
Chris@16
|
718 {
|
Chris@16
|
719 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
|
Chris@16
|
720 safe_super::swap(x);
|
Chris@16
|
721 #endif
|
Chris@16
|
722
|
Chris@16
|
723 super::swap_(x);
|
Chris@16
|
724 }
|
Chris@16
|
725
|
Chris@16
|
726 void swap_elements_(sequenced_index<SuperMeta,TagList>& x)
|
Chris@16
|
727 {
|
Chris@16
|
728 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
|
Chris@16
|
729 safe_super::swap(x);
|
Chris@16
|
730 #endif
|
Chris@16
|
731
|
Chris@16
|
732 super::swap_elements_(x);
|
Chris@16
|
733 }
|
Chris@16
|
734
|
Chris@16
|
735 template<typename Variant>
|
Chris@16
|
736 bool replace_(value_param_type v,node_type* x,Variant variant)
|
Chris@16
|
737 {
|
Chris@16
|
738 return super::replace_(v,x,variant);
|
Chris@16
|
739 }
|
Chris@16
|
740
|
Chris@16
|
741 bool modify_(node_type* x)
|
Chris@16
|
742 {
|
Chris@16
|
743 BOOST_TRY{
|
Chris@16
|
744 if(!super::modify_(x)){
|
Chris@16
|
745 unlink(x);
|
Chris@16
|
746
|
Chris@16
|
747 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
|
Chris@16
|
748 detach_iterators(x);
|
Chris@16
|
749 #endif
|
Chris@16
|
750
|
Chris@16
|
751 return false;
|
Chris@16
|
752 }
|
Chris@16
|
753 else return true;
|
Chris@16
|
754 }
|
Chris@16
|
755 BOOST_CATCH(...){
|
Chris@16
|
756 unlink(x);
|
Chris@16
|
757
|
Chris@16
|
758 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
|
Chris@16
|
759 detach_iterators(x);
|
Chris@16
|
760 #endif
|
Chris@16
|
761
|
Chris@16
|
762 BOOST_RETHROW;
|
Chris@16
|
763 }
|
Chris@16
|
764 BOOST_CATCH_END
|
Chris@16
|
765 }
|
Chris@16
|
766
|
Chris@16
|
767 bool modify_rollback_(node_type* x)
|
Chris@16
|
768 {
|
Chris@16
|
769 return super::modify_rollback_(x);
|
Chris@16
|
770 }
|
Chris@16
|
771
|
Chris@16
|
772 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
|
Chris@16
|
773 /* serialization */
|
Chris@16
|
774
|
Chris@16
|
775 template<typename Archive>
|
Chris@16
|
776 void save_(
|
Chris@16
|
777 Archive& ar,const unsigned int version,const index_saver_type& sm)const
|
Chris@16
|
778 {
|
Chris@16
|
779 sm.save(begin(),end(),ar,version);
|
Chris@16
|
780 super::save_(ar,version,sm);
|
Chris@16
|
781 }
|
Chris@16
|
782
|
Chris@16
|
783 template<typename Archive>
|
Chris@16
|
784 void load_(
|
Chris@16
|
785 Archive& ar,const unsigned int version,const index_loader_type& lm)
|
Chris@16
|
786 {
|
Chris@16
|
787 lm.load(
|
Chris@101
|
788 ::boost::bind(
|
Chris@101
|
789 &sequenced_index::rearranger,this,::boost::arg<1>(),::boost::arg<2>()),
|
Chris@16
|
790 ar,version);
|
Chris@16
|
791 super::load_(ar,version,lm);
|
Chris@16
|
792 }
|
Chris@16
|
793 #endif
|
Chris@16
|
794
|
Chris@16
|
795 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
|
Chris@16
|
796 /* invariant stuff */
|
Chris@16
|
797
|
Chris@16
|
798 bool invariant_()const
|
Chris@16
|
799 {
|
Chris@16
|
800 if(size()==0||begin()==end()){
|
Chris@16
|
801 if(size()!=0||begin()!=end()||
|
Chris@16
|
802 header()->next()!=header()->impl()||
|
Chris@16
|
803 header()->prior()!=header()->impl())return false;
|
Chris@16
|
804 }
|
Chris@16
|
805 else{
|
Chris@16
|
806 size_type s=0;
|
Chris@16
|
807 for(const_iterator it=begin(),it_end=end();it!=it_end;++it,++s){
|
Chris@16
|
808 if(it.get_node()->next()->prior()!=it.get_node()->impl())return false;
|
Chris@16
|
809 if(it.get_node()->prior()->next()!=it.get_node()->impl())return false;
|
Chris@16
|
810 }
|
Chris@16
|
811 if(s!=size())return false;
|
Chris@16
|
812 }
|
Chris@16
|
813
|
Chris@16
|
814 return super::invariant_();
|
Chris@16
|
815 }
|
Chris@16
|
816
|
Chris@16
|
817 /* This forwarding function eases things for the boost::mem_fn construct
|
Chris@16
|
818 * in BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT. Actually,
|
Chris@16
|
819 * final_check_invariant is already an inherited member function of index.
|
Chris@16
|
820 */
|
Chris@16
|
821 void check_invariant_()const{this->final_check_invariant_();}
|
Chris@16
|
822 #endif
|
Chris@16
|
823
|
Chris@16
|
824 private:
|
Chris@16
|
825 node_type* header()const{return this->final_header();}
|
Chris@16
|
826
|
Chris@16
|
827 void empty_initialize()
|
Chris@16
|
828 {
|
Chris@16
|
829 header()->prior()=header()->next()=header()->impl();
|
Chris@16
|
830 }
|
Chris@16
|
831
|
Chris@16
|
832 void link(node_type* x)
|
Chris@16
|
833 {
|
Chris@16
|
834 node_impl_type::link(x->impl(),header()->impl());
|
Chris@16
|
835 };
|
Chris@16
|
836
|
Chris@16
|
837 static void unlink(node_type* x)
|
Chris@16
|
838 {
|
Chris@16
|
839 node_impl_type::unlink(x->impl());
|
Chris@16
|
840 }
|
Chris@16
|
841
|
Chris@16
|
842 static void relink(node_type* position,node_type* x)
|
Chris@16
|
843 {
|
Chris@16
|
844 node_impl_type::relink(position->impl(),x->impl());
|
Chris@16
|
845 }
|
Chris@16
|
846
|
Chris@16
|
847 static void relink(node_type* position,node_type* first,node_type* last)
|
Chris@16
|
848 {
|
Chris@16
|
849 node_impl_type::relink(
|
Chris@16
|
850 position->impl(),first->impl(),last->impl());
|
Chris@16
|
851 }
|
Chris@16
|
852
|
Chris@16
|
853 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
|
Chris@16
|
854 void rearranger(node_type* position,node_type *x)
|
Chris@16
|
855 {
|
Chris@16
|
856 if(!position)position=header();
|
Chris@16
|
857 node_type::increment(position);
|
Chris@16
|
858 if(position!=x)relink(position,x);
|
Chris@16
|
859 }
|
Chris@16
|
860 #endif
|
Chris@16
|
861
|
Chris@16
|
862 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
|
Chris@16
|
863 void detach_iterators(node_type* x)
|
Chris@16
|
864 {
|
Chris@16
|
865 iterator it=make_iterator(x);
|
Chris@16
|
866 safe_mode::detach_equivalent_iterators(it);
|
Chris@16
|
867 }
|
Chris@16
|
868 #endif
|
Chris@16
|
869
|
Chris@16
|
870 template <class InputIterator>
|
Chris@16
|
871 void assign_iter(InputIterator first,InputIterator last,mpl::true_)
|
Chris@16
|
872 {
|
Chris@16
|
873 BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
|
Chris@16
|
874 clear();
|
Chris@16
|
875 for(;first!=last;++first)this->final_insert_ref_(*first);
|
Chris@16
|
876 }
|
Chris@16
|
877
|
Chris@16
|
878 void assign_iter(size_type n,value_param_type value,mpl::false_)
|
Chris@16
|
879 {
|
Chris@16
|
880 BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
|
Chris@16
|
881 clear();
|
Chris@16
|
882 for(size_type i=0;i<n;++i)push_back(value);
|
Chris@16
|
883 }
|
Chris@16
|
884
|
Chris@16
|
885 template<typename InputIterator>
|
Chris@16
|
886 void insert_iter(
|
Chris@16
|
887 iterator position,InputIterator first,InputIterator last,mpl::true_)
|
Chris@16
|
888 {
|
Chris@16
|
889 BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
|
Chris@16
|
890 for(;first!=last;++first){
|
Chris@16
|
891 std::pair<final_node_type*,bool> p=
|
Chris@16
|
892 this->final_insert_ref_(*first);
|
Chris@16
|
893 if(p.second&&position.get_node()!=header()){
|
Chris@16
|
894 relink(position.get_node(),p.first);
|
Chris@16
|
895 }
|
Chris@16
|
896 }
|
Chris@16
|
897 }
|
Chris@16
|
898
|
Chris@16
|
899 void insert_iter(
|
Chris@16
|
900 iterator position,size_type n,value_param_type x,mpl::false_)
|
Chris@16
|
901 {
|
Chris@16
|
902 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
|
Chris@16
|
903 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
|
Chris@16
|
904 BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
|
Chris@16
|
905 for(size_type i=0;i<n;++i)insert(position,x);
|
Chris@16
|
906 }
|
Chris@16
|
907
|
Chris@16
|
908 template<BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK>
|
Chris@16
|
909 std::pair<iterator,bool> emplace_front_impl(
|
Chris@16
|
910 BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK)
|
Chris@16
|
911 {
|
Chris@16
|
912 return emplace_impl(begin(),BOOST_MULTI_INDEX_FORWARD_PARAM_PACK);
|
Chris@16
|
913 }
|
Chris@16
|
914
|
Chris@16
|
915 template<BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK>
|
Chris@16
|
916 std::pair<iterator,bool> emplace_back_impl(
|
Chris@16
|
917 BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK)
|
Chris@16
|
918 {
|
Chris@16
|
919 return emplace_impl(end(),BOOST_MULTI_INDEX_FORWARD_PARAM_PACK);
|
Chris@16
|
920 }
|
Chris@16
|
921
|
Chris@16
|
922 template<BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK>
|
Chris@16
|
923 std::pair<iterator,bool> emplace_impl(
|
Chris@16
|
924 iterator position,BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK)
|
Chris@16
|
925 {
|
Chris@16
|
926 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
|
Chris@16
|
927 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
|
Chris@16
|
928 BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
|
Chris@16
|
929 std::pair<final_node_type*,bool> p=
|
Chris@16
|
930 this->final_emplace_(BOOST_MULTI_INDEX_FORWARD_PARAM_PACK);
|
Chris@16
|
931 if(p.second&&position.get_node()!=header()){
|
Chris@16
|
932 relink(position.get_node(),p.first);
|
Chris@16
|
933 }
|
Chris@16
|
934 return std::pair<iterator,bool>(make_iterator(p.first),p.second);
|
Chris@16
|
935 }
|
Chris@16
|
936
|
Chris@16
|
937 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
|
Chris@16
|
938 BOOST_WORKAROUND(__MWERKS__,<=0x3003)
|
Chris@16
|
939 #pragma parse_mfunc_templ reset
|
Chris@16
|
940 #endif
|
Chris@16
|
941 };
|
Chris@16
|
942
|
Chris@16
|
943 /* comparison */
|
Chris@16
|
944
|
Chris@16
|
945 template<
|
Chris@16
|
946 typename SuperMeta1,typename TagList1,
|
Chris@16
|
947 typename SuperMeta2,typename TagList2
|
Chris@16
|
948 >
|
Chris@16
|
949 bool operator==(
|
Chris@16
|
950 const sequenced_index<SuperMeta1,TagList1>& x,
|
Chris@16
|
951 const sequenced_index<SuperMeta2,TagList2>& y)
|
Chris@16
|
952 {
|
Chris@16
|
953 return x.size()==y.size()&&std::equal(x.begin(),x.end(),y.begin());
|
Chris@16
|
954 }
|
Chris@16
|
955
|
Chris@16
|
956 template<
|
Chris@16
|
957 typename SuperMeta1,typename TagList1,
|
Chris@16
|
958 typename SuperMeta2,typename TagList2
|
Chris@16
|
959 >
|
Chris@16
|
960 bool operator<(
|
Chris@16
|
961 const sequenced_index<SuperMeta1,TagList1>& x,
|
Chris@16
|
962 const sequenced_index<SuperMeta2,TagList2>& y)
|
Chris@16
|
963 {
|
Chris@16
|
964 return std::lexicographical_compare(x.begin(),x.end(),y.begin(),y.end());
|
Chris@16
|
965 }
|
Chris@16
|
966
|
Chris@16
|
967 template<
|
Chris@16
|
968 typename SuperMeta1,typename TagList1,
|
Chris@16
|
969 typename SuperMeta2,typename TagList2
|
Chris@16
|
970 >
|
Chris@16
|
971 bool operator!=(
|
Chris@16
|
972 const sequenced_index<SuperMeta1,TagList1>& x,
|
Chris@16
|
973 const sequenced_index<SuperMeta2,TagList2>& y)
|
Chris@16
|
974 {
|
Chris@16
|
975 return !(x==y);
|
Chris@16
|
976 }
|
Chris@16
|
977
|
Chris@16
|
978 template<
|
Chris@16
|
979 typename SuperMeta1,typename TagList1,
|
Chris@16
|
980 typename SuperMeta2,typename TagList2
|
Chris@16
|
981 >
|
Chris@16
|
982 bool operator>(
|
Chris@16
|
983 const sequenced_index<SuperMeta1,TagList1>& x,
|
Chris@16
|
984 const sequenced_index<SuperMeta2,TagList2>& y)
|
Chris@16
|
985 {
|
Chris@16
|
986 return y<x;
|
Chris@16
|
987 }
|
Chris@16
|
988
|
Chris@16
|
989 template<
|
Chris@16
|
990 typename SuperMeta1,typename TagList1,
|
Chris@16
|
991 typename SuperMeta2,typename TagList2
|
Chris@16
|
992 >
|
Chris@16
|
993 bool operator>=(
|
Chris@16
|
994 const sequenced_index<SuperMeta1,TagList1>& x,
|
Chris@16
|
995 const sequenced_index<SuperMeta2,TagList2>& y)
|
Chris@16
|
996 {
|
Chris@16
|
997 return !(x<y);
|
Chris@16
|
998 }
|
Chris@16
|
999
|
Chris@16
|
1000 template<
|
Chris@16
|
1001 typename SuperMeta1,typename TagList1,
|
Chris@16
|
1002 typename SuperMeta2,typename TagList2
|
Chris@16
|
1003 >
|
Chris@16
|
1004 bool operator<=(
|
Chris@16
|
1005 const sequenced_index<SuperMeta1,TagList1>& x,
|
Chris@16
|
1006 const sequenced_index<SuperMeta2,TagList2>& y)
|
Chris@16
|
1007 {
|
Chris@16
|
1008 return !(x>y);
|
Chris@16
|
1009 }
|
Chris@16
|
1010
|
Chris@16
|
1011 /* specialized algorithms */
|
Chris@16
|
1012
|
Chris@16
|
1013 template<typename SuperMeta,typename TagList>
|
Chris@16
|
1014 void swap(
|
Chris@16
|
1015 sequenced_index<SuperMeta,TagList>& x,
|
Chris@16
|
1016 sequenced_index<SuperMeta,TagList>& y)
|
Chris@16
|
1017 {
|
Chris@16
|
1018 x.swap(y);
|
Chris@16
|
1019 }
|
Chris@16
|
1020
|
Chris@16
|
1021 } /* namespace multi_index::detail */
|
Chris@16
|
1022
|
Chris@16
|
1023 /* sequenced index specifier */
|
Chris@16
|
1024
|
Chris@16
|
1025 template <typename TagList>
|
Chris@16
|
1026 struct sequenced
|
Chris@16
|
1027 {
|
Chris@16
|
1028 BOOST_STATIC_ASSERT(detail::is_tag<TagList>::value);
|
Chris@16
|
1029
|
Chris@16
|
1030 template<typename Super>
|
Chris@16
|
1031 struct node_class
|
Chris@16
|
1032 {
|
Chris@16
|
1033 typedef detail::sequenced_index_node<Super> type;
|
Chris@16
|
1034 };
|
Chris@16
|
1035
|
Chris@16
|
1036 template<typename SuperMeta>
|
Chris@16
|
1037 struct index_class
|
Chris@16
|
1038 {
|
Chris@16
|
1039 typedef detail::sequenced_index<SuperMeta,typename TagList::type> type;
|
Chris@16
|
1040 };
|
Chris@16
|
1041 };
|
Chris@16
|
1042
|
Chris@16
|
1043 } /* namespace multi_index */
|
Chris@16
|
1044
|
Chris@16
|
1045 } /* namespace boost */
|
Chris@16
|
1046
|
Chris@16
|
1047 /* Boost.Foreach compatibility */
|
Chris@16
|
1048
|
Chris@16
|
1049 template<typename SuperMeta,typename TagList>
|
Chris@16
|
1050 inline boost::mpl::true_* boost_foreach_is_noncopyable(
|
Chris@16
|
1051 boost::multi_index::detail::sequenced_index<SuperMeta,TagList>*&,
|
Chris@16
|
1052 boost::foreach::tag)
|
Chris@16
|
1053 {
|
Chris@16
|
1054 return 0;
|
Chris@16
|
1055 }
|
Chris@16
|
1056
|
Chris@16
|
1057 #undef BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT
|
Chris@16
|
1058 #undef BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT_OF
|
Chris@16
|
1059
|
Chris@16
|
1060 #endif
|