]>
Commit | Line | Data |
---|---|---|
f67539c2 | 1 | /* Copyright 2016-2020 Joaquin M Lopez Munoz. |
b32b8144 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/poly_collection for library home page. | |
7 | */ | |
8 | ||
9 | #ifndef BOOST_POLY_COLLECTION_ALGORITHM_HPP | |
10 | #define BOOST_POLY_COLLECTION_ALGORITHM_HPP | |
11 | ||
12 | #if defined(_MSC_VER) | |
13 | #pragma once | |
14 | #endif | |
15 | ||
16 | #include <algorithm> | |
17 | #include <boost/poly_collection/detail/auto_iterator.hpp> | |
18 | #include <boost/poly_collection/detail/functional.hpp> | |
19 | #include <boost/poly_collection/detail/iterator_traits.hpp> | |
20 | #include <boost/poly_collection/detail/segment_split.hpp> | |
21 | #include <boost/poly_collection/detail/type_restitution.hpp> | |
b32b8144 | 22 | #include <iterator> |
92f5a8d4 | 23 | #include <random> |
b32b8144 FG |
24 | #include <type_traits> |
25 | #include <utility> | |
26 | ||
27 | /* Improved performance versions of std algorithms over poly_collection. | |
28 | * poly_collection::alg is expected to be faster than the homonym std::alg | |
29 | * because the latter does a traversal over a segmented structured, where | |
30 | * incrementing requires checking for segment change, whereas the former | |
31 | * for-loops over flat segments. | |
32 | * Additionally, poly_collection::alg<Ti...>(...,f) *restitutes* Ti when | |
33 | * passing elements to f, i.e. if the concrete type of the element is Ti | |
34 | * then f is invoked with a [const] Ti&, which can dramatically improve | |
35 | * performance when f has specific overloads for Ti (like, for instance, | |
36 | * generic lambdas) as static optimization can kick in (devirtualization | |
37 | * being a particular example). | |
38 | */ | |
39 | ||
40 | namespace boost{ | |
41 | ||
42 | namespace poly_collection{ | |
43 | ||
44 | namespace detail{ | |
45 | ||
46 | namespace algorithm{ | |
47 | ||
48 | template<typename Iterator> | |
49 | using enable_if_poly_collection_iterator=typename std::enable_if< | |
50 | !std::is_void<typename poly_collection_of<Iterator>::type>::value | |
51 | >::type*; | |
52 | ||
53 | BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_all_of,std::all_of) | |
54 | ||
55 | template< | |
56 | typename... Ts,typename Iterator,typename Predicate, | |
57 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
58 | > | |
59 | bool all_of(const Iterator& first,const Iterator& last,Predicate pred) | |
60 | { | |
61 | auto alg=restitute_range<Ts...>(std_all_of{},pred); | |
62 | for(auto i:detail::segment_split(first,last))if(!alg(i))return false; | |
63 | return true; | |
64 | } | |
65 | ||
66 | BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_any_of,std::any_of) | |
67 | ||
68 | template< | |
69 | typename... Ts,typename Iterator,typename Predicate, | |
70 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
71 | > | |
72 | bool any_of(const Iterator& first,const Iterator& last,Predicate pred) | |
73 | { | |
74 | auto alg=restitute_range<Ts...>(std_any_of{},pred); | |
75 | for(auto i:detail::segment_split(first,last))if(alg(i))return true; | |
76 | return false; | |
77 | } | |
78 | ||
79 | BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_none_of,std::none_of) | |
80 | ||
81 | template< | |
82 | typename... Ts,typename Iterator,typename Predicate, | |
83 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
84 | > | |
85 | bool none_of(const Iterator& first,const Iterator& last,Predicate pred) | |
86 | { | |
87 | auto alg=restitute_range<Ts...>(std_none_of{},pred); | |
88 | for(auto i:detail::segment_split(first,last))if(!alg(i))return false; | |
89 | return true; | |
90 | } | |
91 | ||
92 | struct for_each_alg | |
93 | { | |
b32b8144 FG |
94 | template<typename InputIterator,typename Function> |
95 | void operator()( | |
96 | InputIterator first,InputIterator last,Function& f)const /* note the & */ | |
97 | { | |
98 | for(;first!=last;++first)f(*first); | |
99 | } | |
100 | }; | |
101 | ||
102 | template< | |
103 | typename... Ts,typename Iterator,typename Function, | |
104 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
105 | > | |
106 | Function for_each(const Iterator& first,const Iterator& last,Function f) | |
107 | { | |
108 | for_each_segment(first,last,restitute_range<Ts...>(for_each_alg{},f)); | |
f67539c2 | 109 | return f; |
b32b8144 FG |
110 | } |
111 | ||
92f5a8d4 TL |
112 | struct for_each_n_alg |
113 | { | |
114 | template< | |
115 | typename InputIterator,typename Size,typename Function | |
116 | > | |
117 | InputIterator operator()( | |
118 | InputIterator first,Size n,Function& f)const /* note the & */ | |
119 | { | |
120 | for(;n>0;++first,(void)--n)f(*first); | |
121 | return first; | |
122 | } | |
123 | }; | |
124 | ||
125 | template< | |
126 | typename... Ts,typename Iterator,typename Size,typename Function, | |
127 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
128 | > | |
129 | Iterator for_each_n(const Iterator& first,Size n,Function f) | |
130 | { | |
131 | using traits=iterator_traits<Iterator>; | |
132 | using local_base_iterator=typename traits::local_base_iterator; | |
133 | ||
134 | if(n<=0)return first; | |
135 | ||
136 | auto alg=restitute_iterator<Ts...>( | |
137 | cast_return<local_base_iterator>(for_each_n_alg{})); | |
138 | auto lbit=traits::local_base_iterator_from(first); | |
139 | auto sit=traits::base_segment_info_iterator_from(first); | |
140 | for(;;){ | |
141 | auto m=sit->end()-lbit; | |
142 | if(n<=m){ | |
143 | auto it=alg(sit->type_info(),lbit,n,f); | |
144 | return traits::iterator_from( | |
145 | it,traits::end_base_segment_info_iterator_from(first)); | |
146 | } | |
147 | else{ | |
148 | alg(sit->type_info(),lbit,m,f); | |
149 | n-=m; | |
150 | } | |
151 | ++sit; | |
152 | lbit=sit->begin(); | |
153 | } | |
154 | } | |
155 | ||
b32b8144 FG |
156 | template< |
157 | typename Algorithm,typename... Ts, | |
158 | typename Iterator,typename... Args, | |
159 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
160 | > | |
161 | Iterator generic_find( | |
162 | const Iterator& first,const Iterator& last,Args&&... args) | |
163 | { | |
164 | using traits=iterator_traits<Iterator>; | |
165 | using local_base_iterator=typename traits::local_base_iterator; | |
166 | ||
167 | auto alg=restitute_range<Ts...>( | |
168 | cast_return<local_base_iterator>(Algorithm{}), | |
169 | std::forward<Args>(args)...); | |
170 | for(auto i:detail::segment_split(first,last)){ | |
171 | auto it=alg(i); | |
172 | if(it!=i.end()) | |
173 | return traits::iterator_from( | |
174 | it,traits::end_base_segment_info_iterator_from(last)); | |
175 | } | |
176 | return last; | |
177 | } | |
178 | ||
179 | BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_find,std::find) | |
180 | ||
181 | template< | |
182 | typename... Ts,typename Iterator,typename T, | |
183 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
184 | > | |
185 | Iterator find(const Iterator& first,const Iterator& last,const T& x) | |
186 | { | |
187 | return generic_find<std_find,Ts...>(first,last,x); | |
188 | } | |
189 | ||
190 | BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_find_if,std::find_if) | |
191 | ||
192 | template< | |
193 | typename... Ts,typename Iterator,typename Predicate, | |
194 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
195 | > | |
196 | Iterator find_if(const Iterator& first,const Iterator& last,Predicate pred) | |
197 | { | |
198 | return generic_find<std_find_if,Ts...>(first,last,pred); | |
199 | } | |
200 | ||
201 | BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_find_if_not,std::find_if_not) | |
202 | ||
203 | template< | |
204 | typename... Ts,typename Iterator,typename Predicate, | |
205 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
206 | > | |
207 | Iterator find_if_not(const Iterator& first,const Iterator& last,Predicate pred) | |
208 | { | |
209 | return generic_find<std_find_if_not,Ts...>(first,last,pred); | |
210 | } | |
211 | ||
212 | /* find_end defined after search below */ | |
213 | ||
214 | BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_find_first_of,std::find_first_of) | |
215 | ||
216 | template< | |
217 | typename... Ts,typename Iterator,typename ForwardIterator, | |
218 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
219 | > | |
220 | Iterator find_first_of( | |
221 | const Iterator& first1,const Iterator& last1, | |
222 | ForwardIterator first2,ForwardIterator last2) | |
223 | { | |
224 | return generic_find<std_find_first_of,Ts...>(first1,last1,first2,last2); | |
225 | } | |
226 | ||
227 | template< | |
228 | typename... Ts,typename Iterator, | |
229 | typename ForwardIterator,typename BinaryPredicate, | |
230 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
231 | > | |
232 | Iterator find_first_of( | |
233 | const Iterator& first1,const Iterator& last1, | |
234 | ForwardIterator first2,ForwardIterator last2,BinaryPredicate pred) | |
235 | { | |
236 | return generic_find<std_find_first_of,Ts...>(first1,last1,first2,last2,pred); | |
237 | } | |
238 | ||
239 | template<typename... Ts> | |
240 | struct adjacent_find_alg | |
241 | { | |
b32b8144 FG |
242 | template< |
243 | typename LocalIterator,typename BinaryPredicate,typename LocalBaseIterator | |
244 | > | |
245 | LocalBaseIterator operator()( | |
246 | LocalIterator first,LocalIterator last,BinaryPredicate pred, | |
247 | bool& carry,const std::type_info* prev_info, /* note the &s */ | |
248 | LocalBaseIterator& prev)const | |
249 | { | |
250 | if(first==last)return LocalBaseIterator{last}; | |
251 | if(carry){ | |
252 | auto p=restitute_iterator<Ts...>(deref_to(pred)); | |
253 | if(p(*prev_info,prev,first))return prev; | |
254 | } | |
255 | auto res=std::adjacent_find(first,last,pred); | |
256 | if(res==last){ | |
257 | carry=true; | |
258 | prev_info=&typeid( | |
259 | typename std::iterator_traits<LocalIterator>::value_type); | |
260 | prev=LocalBaseIterator{last-1}; | |
261 | } | |
262 | else carry=false; | |
263 | return LocalBaseIterator{res}; | |
264 | } | |
265 | }; | |
266 | ||
267 | template< | |
268 | typename... Ts,typename Iterator,typename BinaryPredicate, | |
269 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
270 | > | |
271 | Iterator adjacent_find( | |
272 | const Iterator& first,const Iterator& last,BinaryPredicate pred) | |
273 | { | |
274 | using traits=iterator_traits<Iterator>; | |
275 | using local_base_iterator=typename traits::local_base_iterator; | |
276 | ||
277 | bool carry=false; | |
278 | const std::type_info* prev_info{&typeid(void)}; | |
279 | local_base_iterator prev; | |
280 | return generic_find<adjacent_find_alg<Ts...>,Ts...>( | |
281 | first,last,pred,carry,prev_info,prev); | |
282 | } | |
283 | ||
284 | template< | |
285 | typename... Ts,typename Iterator, | |
286 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
287 | > | |
288 | Iterator adjacent_find(const Iterator& first,const Iterator& last) | |
289 | { | |
290 | return algorithm::adjacent_find<Ts...>(first,last,transparent_equal_to{}); | |
291 | } | |
292 | ||
293 | template< | |
294 | typename Algorithm,typename... Ts, | |
295 | typename Iterator,typename... Args, | |
296 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
297 | > | |
298 | std::ptrdiff_t generic_count( | |
299 | const Iterator& first,const Iterator& last,Args&&... args) | |
300 | { | |
301 | auto alg=restitute_range<Ts...>(Algorithm{},std::forward<Args>(args)...); | |
302 | std::ptrdiff_t res=0; | |
303 | for(auto i:detail::segment_split(first,last))res+=alg(i); | |
304 | return res; | |
305 | } | |
306 | ||
307 | BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_count,std::count) | |
308 | ||
309 | template< | |
310 | typename... Ts,typename Iterator,typename T, | |
311 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
312 | > | |
313 | std::ptrdiff_t count(const Iterator& first,const Iterator& last,const T& x) | |
314 | { | |
315 | return generic_count<std_count,Ts...>(first,last,x); | |
316 | } | |
317 | ||
318 | BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_count_if,std::count_if) | |
319 | ||
320 | template< | |
321 | typename... Ts,typename Iterator,typename Predicate, | |
322 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
323 | > | |
324 | std::ptrdiff_t count_if( | |
325 | const Iterator& first,const Iterator& last,Predicate pred) | |
326 | { | |
327 | return generic_count<std_count_if,Ts...>(first,last,pred); | |
328 | } | |
329 | ||
330 | struct mismatch_alg | |
331 | { | |
b32b8144 FG |
332 | template< |
333 | typename InputIterator1, | |
334 | typename InputIterator2,typename BinaryPredicate | |
335 | > | |
336 | InputIterator1 operator()( | |
337 | InputIterator1 first1,InputIterator1 last1, | |
338 | InputIterator2& first2,BinaryPredicate pred)const /* note the & */ | |
339 | { | |
340 | while(first1!=last1&&pred(*first1,*first2)){ | |
341 | ++first1; | |
342 | ++first2; | |
343 | } | |
344 | return first1; | |
345 | } | |
346 | ||
347 | template< | |
348 | typename InputIterator1, | |
349 | typename InputIterator2,typename BinaryPredicate | |
350 | > | |
351 | InputIterator1 operator()( | |
352 | InputIterator1 first1,InputIterator1 last1, | |
353 | InputIterator2& first2,InputIterator2 last2, /* note the & */ | |
354 | BinaryPredicate pred)const | |
355 | { | |
356 | while(first1!=last1&&first2!=last2&&pred(*first1,*first2)){ | |
357 | ++first1; | |
358 | ++first2; | |
359 | } | |
360 | return first1; | |
361 | } | |
362 | }; | |
363 | ||
364 | template< | |
365 | typename... Ts,typename Iterator, | |
366 | typename InputIterator,typename BinaryPredicate, | |
367 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
368 | > | |
369 | std::pair<Iterator,InputIterator> mismatch( | |
370 | const Iterator& first1,const Iterator& last1, | |
371 | InputIterator first2,BinaryPredicate pred) | |
372 | { | |
373 | auto it=generic_find<mismatch_alg,Ts...>(first1,last1,first2,pred); | |
374 | return {it,first2}; | |
375 | } | |
376 | ||
377 | template< | |
378 | typename... Ts,typename Iterator,typename InputIterator, | |
379 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
380 | > | |
381 | std::pair<Iterator,InputIterator> mismatch( | |
382 | const Iterator& first1,const Iterator& last1,InputIterator first2) | |
383 | { | |
384 | return algorithm::mismatch<Ts...>( | |
385 | first1,last1,first2,transparent_equal_to{}); | |
386 | } | |
387 | ||
388 | template< | |
389 | typename... Ts,typename Iterator, | |
390 | typename InputIterator,typename BinaryPredicate, | |
391 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
392 | > | |
393 | std::pair<Iterator,InputIterator> mismatch( | |
394 | const Iterator& first1,const Iterator& last1, | |
395 | InputIterator first2,InputIterator last2,BinaryPredicate pred) | |
396 | { | |
397 | auto it=generic_find<mismatch_alg,Ts...>(first1,last1,first2,last2,pred); | |
398 | return {it,first2}; | |
399 | } | |
400 | ||
401 | template< | |
402 | typename... Ts,typename Iterator,typename InputIterator, | |
403 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
404 | > | |
405 | std::pair<Iterator,InputIterator> mismatch( | |
406 | const Iterator& first1,const Iterator& last1, | |
407 | InputIterator first2,InputIterator last2) | |
408 | { | |
409 | return algorithm::mismatch<Ts...>( | |
410 | first1,last1,first2,last2,transparent_equal_to{}); | |
411 | } | |
412 | ||
413 | struct equal_alg | |
414 | { | |
b32b8144 FG |
415 | template< |
416 | typename InputIterator1, | |
417 | typename InputIterator2,typename BinaryPredicate | |
418 | > | |
419 | bool operator()( | |
420 | InputIterator1 first1,InputIterator1 last1, | |
421 | InputIterator2& first2,BinaryPredicate pred)const /* note the & */ | |
422 | { | |
423 | for(;first1!=last1;++first1,++first2){ | |
424 | if(!pred(*first1,*first2))return false; | |
425 | } | |
426 | return true; | |
427 | } | |
428 | ||
429 | template< | |
430 | typename InputIterator1, | |
431 | typename InputIterator2,typename BinaryPredicate | |
432 | > | |
433 | bool operator()( | |
434 | InputIterator1 first1,InputIterator1 last1, | |
435 | InputIterator2& first2,InputIterator2 last2, /* note the & */ | |
436 | BinaryPredicate pred)const | |
437 | { | |
438 | for(;first1!=last1&&first2!=last2;++first1,++first2){ | |
439 | if(!pred(*first1,*first2))return false; | |
440 | } | |
441 | return first1==last1; /* don't check first2==last2 as op is partial */ | |
442 | } | |
443 | }; | |
444 | ||
445 | template< | |
446 | typename... Ts,typename Iterator, | |
447 | typename InputIterator,typename BinaryPredicate, | |
448 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
449 | > | |
450 | bool equal( | |
451 | const Iterator& first1,const Iterator& last1, | |
452 | InputIterator first2,BinaryPredicate pred) | |
453 | { | |
454 | auto alg=restitute_range<Ts...>(equal_alg{},first2,pred); | |
455 | for(auto i:detail::segment_split(first1,last1))if(!alg(i))return false; | |
456 | return true; | |
457 | } | |
458 | ||
459 | template< | |
460 | typename... Ts,typename Iterator,typename InputIterator, | |
461 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
462 | > | |
463 | bool equal( | |
464 | const Iterator& first1,const Iterator& last1,InputIterator first2) | |
465 | { | |
466 | return algorithm::equal<Ts...>(first1,last1,first2,transparent_equal_to{}); | |
467 | } | |
468 | ||
469 | template< | |
470 | typename... Ts,typename Iterator, | |
471 | typename InputIterator,typename BinaryPredicate, | |
472 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
473 | > | |
474 | bool equal( | |
475 | const Iterator& first1,const Iterator& last1, | |
476 | InputIterator first2,InputIterator last2,BinaryPredicate pred) | |
477 | { | |
478 | auto alg=restitute_range<Ts...>(equal_alg{},first2,last2,pred); | |
479 | for(auto i:detail::segment_split(first1,last1))if(!alg(i))return false; | |
480 | return first2==last2; | |
481 | } | |
482 | ||
483 | template< | |
484 | typename... Ts,typename Iterator,typename InputIterator, | |
485 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
486 | > | |
487 | bool equal( | |
488 | const Iterator& first1,const Iterator& last1, | |
489 | InputIterator first2,InputIterator last2) | |
490 | { | |
491 | return algorithm::equal<Ts...>( | |
492 | first1,last1,first2,last2,transparent_equal_to{}); | |
493 | } | |
494 | ||
92f5a8d4 TL |
495 | template< |
496 | typename Iterator, | |
497 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
498 | > | |
499 | std::ptrdiff_t fast_distance(const Iterator& first,const Iterator& last) | |
500 | { | |
501 | using traits=iterator_traits<Iterator>; | |
502 | ||
503 | if(first==last)return 0; | |
504 | ||
505 | auto sfirst=traits::base_segment_info_iterator_from(first), | |
506 | slast=traits::base_segment_info_iterator_from(last); | |
507 | if(sfirst==slast){ | |
508 | return std::distance( | |
509 | traits::local_base_iterator_from(first), | |
510 | traits::local_base_iterator_from(last)); | |
511 | } | |
512 | else{ | |
513 | std::ptrdiff_t m=std::distance( | |
514 | traits::local_base_iterator_from(first),sfirst->end()); | |
515 | while(++sfirst!=slast)m+=std::distance(sfirst->begin(),sfirst->end()); | |
516 | if(slast!=traits::end_base_segment_info_iterator_from(last)){ | |
517 | m+=std::distance( | |
518 | slast->begin(),traits::local_base_iterator_from(last)); | |
519 | } | |
520 | return m; | |
521 | } | |
522 | } | |
523 | ||
b32b8144 FG |
524 | template< |
525 | typename... Ts,typename Iterator, | |
526 | typename ForwardIterator,typename BinaryPredicate, | |
527 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
528 | > | |
529 | bool is_permutation_suffix( | |
530 | const Iterator& first1,const Iterator& last1, | |
531 | ForwardIterator first2,ForwardIterator last2,BinaryPredicate pred) | |
532 | { | |
533 | using traits=iterator_traits<Iterator>; | |
534 | ||
535 | auto send=traits::end_base_segment_info_iterator_from(last1); | |
536 | for(auto i:detail::segment_split(first1,last1)){ | |
537 | for(auto lbscan=i.begin();lbscan!=i.end();++lbscan){ | |
538 | auto& info=i.type_info(); | |
539 | auto p=head_closure( | |
540 | restitute_iterator<Ts...>(deref_1st_to(pred)),info,lbscan); | |
541 | auto scan=traits::iterator_from(lbscan,send); | |
542 | if(algorithm::find_if<Ts...>(first1,scan,p)!=scan)continue; | |
543 | std::ptrdiff_t matches=std::count_if(first2,last2,p); | |
544 | if(matches==0|| | |
545 | matches!=algorithm::count_if<Ts...>(scan,last1,p))return false; | |
546 | } | |
547 | } | |
548 | return true; | |
549 | } | |
550 | ||
551 | template< | |
552 | typename... Ts,typename Iterator, | |
553 | typename ForwardIterator,typename BinaryPredicate, | |
554 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
555 | > | |
556 | bool is_permutation( | |
557 | Iterator first1,Iterator last1,ForwardIterator first2,BinaryPredicate pred) | |
558 | { | |
559 | std::tie(first1,first2)=algorithm::mismatch<Ts...>(first1,last1,first2,pred); | |
92f5a8d4 | 560 | auto last2=std::next(first2,algorithm::fast_distance(first1,last1)); |
b32b8144 FG |
561 | return is_permutation_suffix<Ts...>(first1,last1,first2,last2,pred); |
562 | } | |
563 | ||
564 | template< | |
565 | typename... Ts,typename Iterator,typename ForwardIterator, | |
566 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
567 | > | |
568 | bool is_permutation( | |
569 | const Iterator& first1,const Iterator& last1,ForwardIterator first2) | |
570 | { | |
571 | return algorithm::is_permutation<Ts...>( | |
572 | first1,last1,first2,transparent_equal_to{}); | |
573 | } | |
574 | ||
575 | template< | |
576 | typename... Ts,typename Iterator, | |
577 | typename ForwardIterator,typename BinaryPredicate, | |
578 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
579 | > | |
580 | bool is_permutation( | |
581 | Iterator first1,Iterator last1, | |
582 | ForwardIterator first2,ForwardIterator last2,BinaryPredicate pred) | |
583 | { | |
584 | std::tie(first1,first2)=algorithm::mismatch<Ts...>( | |
585 | first1,last1,first2,last2,pred); | |
92f5a8d4 TL |
586 | if(algorithm::fast_distance(first1,last1)!=std::distance(first2,last2)) |
587 | return false; | |
b32b8144 FG |
588 | else return is_permutation_suffix<Ts...>(first1,last1,first2,last2,pred); |
589 | } | |
590 | ||
591 | template< | |
592 | typename... Ts,typename Iterator,typename ForwardIterator, | |
593 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
594 | > | |
595 | bool is_permutation( | |
596 | const Iterator& first1,const Iterator& last1, | |
597 | ForwardIterator first2,ForwardIterator last2) | |
598 | { | |
599 | return algorithm::is_permutation<Ts...>( | |
600 | first1,last1,first2,last2,transparent_equal_to{}); | |
601 | } | |
602 | ||
603 | template< | |
604 | typename... Ts,typename Iterator, | |
605 | typename ForwardIterator,typename BinaryPredicate, | |
606 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
607 | > | |
608 | Iterator search( | |
609 | const Iterator& first1,const Iterator& last1, | |
610 | ForwardIterator first2,ForwardIterator last2,BinaryPredicate pred) | |
611 | { | |
612 | using traits=iterator_traits<Iterator>; | |
613 | ||
614 | auto send=traits::end_base_segment_info_iterator_from(last1); | |
615 | for(auto i:detail::segment_split(first1,last1)){ | |
616 | for(auto lbit=i.begin(),lbend=i.end();lbit!=lbend;++lbit){ | |
617 | Iterator it=traits::iterator_from(lbit,send); | |
618 | if(algorithm::mismatch<Ts...>(it,last1,first2,last2,pred).second==last2) | |
619 | return it; | |
620 | } | |
621 | } | |
622 | return last1; | |
623 | } | |
624 | ||
625 | template< | |
626 | typename... Ts,typename Iterator,typename ForwardIterator, | |
627 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
628 | > | |
629 | Iterator search( | |
630 | const Iterator& first1,const Iterator& last1, | |
631 | ForwardIterator first2,ForwardIterator last2) | |
632 | { | |
633 | return algorithm::search<Ts...>( | |
634 | first1,last1,first2,last2,transparent_equal_to{}); | |
635 | } | |
636 | ||
637 | template< | |
638 | typename... Ts,typename Iterator, | |
639 | typename ForwardIterator,typename BinaryPredicate, | |
640 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
641 | > | |
642 | Iterator find_end( | |
643 | Iterator first1,Iterator last1, | |
644 | ForwardIterator first2,ForwardIterator last2,BinaryPredicate pred) | |
645 | { | |
646 | if(first2==last2)return last1; | |
647 | ||
648 | for(Iterator res=last1;;){ | |
649 | Iterator res1=algorithm::search<Ts...>(first1,last1,first2,last2,pred); | |
650 | if(res1==last1)return res; | |
651 | else{ | |
652 | first1=res=res1; | |
653 | ++first1; | |
654 | } | |
655 | } | |
656 | } | |
657 | ||
658 | template< | |
659 | typename... Ts,typename Iterator,typename ForwardIterator, | |
660 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
661 | > | |
662 | Iterator find_end( | |
663 | const Iterator& first1,const Iterator& last1, | |
664 | ForwardIterator first2,ForwardIterator last2) | |
665 | { | |
666 | return algorithm::find_end<Ts...>( | |
667 | first1,last1,first2,last2,transparent_equal_to{}); | |
668 | } | |
669 | ||
670 | struct search_n_alg | |
671 | { | |
b32b8144 FG |
672 | template< |
673 | typename ForwardIterator,typename Size, | |
674 | typename T,typename BinaryPredicate | |
675 | > | |
676 | ForwardIterator operator()( | |
677 | ForwardIterator first,ForwardIterator last, | |
678 | Size count,bool& carry,Size& remain,const T& x, /* note the &s */ | |
679 | BinaryPredicate pred)const | |
680 | { | |
681 | for(;first!=last;++first){ | |
682 | if(!pred(*first,x)){carry=false;remain=count;continue;} | |
683 | auto res=first; | |
684 | for(;;){ | |
685 | if(--remain==0||++first==last)return res; | |
686 | if(!pred(*first,x)){carry=false;remain=count;break;} | |
687 | } | |
688 | } | |
689 | return last; | |
690 | } | |
691 | }; | |
692 | ||
693 | template< | |
694 | typename... Ts,typename Iterator, | |
695 | typename Size,typename T,typename BinaryPredicate, | |
696 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
697 | > | |
698 | Iterator search_n( | |
699 | const Iterator& first,const Iterator& last, | |
700 | Size count,const T& x,BinaryPredicate pred) | |
701 | { | |
702 | using traits=iterator_traits<Iterator>; | |
703 | using local_base_iterator=typename traits::local_base_iterator; | |
704 | ||
705 | if(count<=0)return first; | |
706 | ||
707 | bool carry=false; | |
708 | auto remain=count; | |
709 | auto alg=restitute_range<Ts...>( | |
710 | cast_return<local_base_iterator>(search_n_alg{}), | |
711 | count,carry,remain,x,pred); | |
712 | local_base_iterator prev; | |
713 | for(auto i:detail::segment_split(first,last)){ | |
714 | auto it=alg(i); | |
715 | if(it!=i.end()){ | |
716 | if(remain==0) | |
717 | return traits::iterator_from( | |
718 | carry?prev:it, | |
719 | traits::end_base_segment_info_iterator_from(last)); | |
720 | else if(!carry){prev=it;carry=true;} | |
721 | } | |
722 | } | |
723 | return last; | |
724 | } | |
725 | ||
726 | template< | |
727 | typename... Ts,typename Iterator, | |
728 | typename Size,typename T, | |
729 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
730 | > | |
731 | Iterator search_n( | |
732 | const Iterator& first,const Iterator& last,Size count,const T& x) | |
733 | { | |
734 | return algorithm::search_n<Ts...>( | |
735 | first,last,count,x,transparent_equal_to{}); | |
736 | } | |
737 | ||
738 | template< | |
739 | typename Algorithm,typename... Ts, | |
740 | typename Iterator,typename OutputIterator,typename... Args, | |
741 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
742 | > | |
743 | OutputIterator generic_copy( | |
744 | const Iterator& first,const Iterator& last,OutputIterator res,Args&&... args) | |
745 | { | |
746 | for(auto i:detail::segment_split(first,last)){ | |
747 | auto alg=restitute_range<Ts...>( | |
748 | Algorithm{},res,std::forward<Args>(args)...); | |
749 | res=alg(i); | |
750 | } | |
751 | return res; | |
752 | } | |
753 | ||
754 | BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_copy,std::copy) | |
755 | ||
756 | template< | |
757 | typename... Ts,typename Iterator,typename OutputIterator, | |
758 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
759 | > | |
760 | OutputIterator copy( | |
761 | const Iterator& first,const Iterator& last,OutputIterator res) | |
762 | { | |
763 | return generic_copy<std_copy,Ts...>(first,last,res); | |
764 | } | |
765 | ||
766 | BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_copy_n,std::copy_n) | |
767 | ||
768 | template< | |
769 | typename... Ts,typename Iterator,typename Size,typename OutputIterator, | |
770 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
771 | > | |
772 | OutputIterator copy_n(const Iterator& first,Size count,OutputIterator res) | |
773 | { | |
774 | using traits=iterator_traits<Iterator>; | |
775 | ||
776 | if(count<=0)return res; | |
777 | ||
778 | auto lbit=traits::local_base_iterator_from(first); | |
779 | auto sit=traits::base_segment_info_iterator_from(first); | |
780 | for(;;){ | |
781 | auto n=(std::min)(count,sit->end()-lbit); | |
782 | auto alg=restitute_iterator<Ts...>(std_copy_n{},n,res); | |
783 | res=alg(sit->type_info(),lbit); | |
784 | if((count-=n)==0)break; | |
785 | ++sit; | |
786 | lbit=sit->begin(); | |
787 | } | |
788 | return res; | |
789 | } | |
790 | ||
791 | BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_copy_if,std::copy_if) | |
792 | ||
793 | template< | |
794 | typename... Ts,typename Iterator,typename OutputIterator,typename Predicate, | |
795 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
796 | > | |
797 | OutputIterator copy_if( | |
798 | const Iterator& first,const Iterator& last,OutputIterator res,Predicate pred) | |
799 | { | |
800 | return generic_copy<std_copy_if,Ts...>(first,last,res,pred); | |
801 | } | |
802 | ||
803 | BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_move,std::move) | |
804 | ||
805 | template< | |
806 | typename... Ts,typename Iterator,typename OutputIterator, | |
807 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
808 | > | |
809 | OutputIterator move( | |
810 | const Iterator& first,const Iterator& last,OutputIterator res) | |
811 | { | |
812 | return generic_copy<std_move,Ts...>(first,last,res); | |
813 | } | |
814 | ||
815 | BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_transform,std::transform) | |
816 | ||
817 | template< | |
818 | typename... Ts,typename Iterator, | |
819 | typename OutputIterator,typename UnaryOperation, | |
820 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
821 | > | |
822 | OutputIterator transform( | |
823 | const Iterator& first,const Iterator& last, | |
824 | OutputIterator res,UnaryOperation op) | |
825 | { | |
826 | return generic_copy<std_transform,Ts...>(first,last,res,op); | |
827 | } | |
828 | ||
829 | struct transform2_alg | |
830 | { | |
b32b8144 FG |
831 | template< |
832 | typename InputIterator1,typename InputIterator2, | |
833 | typename OutputIterator,typename BinaryOperation | |
834 | > | |
835 | OutputIterator operator()( | |
836 | InputIterator1 first1,InputIterator1 last1, | |
837 | OutputIterator res, /* third place for compatibility with generic_copy */ | |
838 | InputIterator2& first2, BinaryOperation op)const /* note the & */ | |
839 | { | |
840 | while(first1!=last1)*res++=op(*first1++,*first2++); | |
841 | return res; | |
842 | } | |
843 | }; | |
844 | ||
845 | template< | |
846 | typename... Ts,typename Iterator,typename InputIterator, | |
847 | typename OutputIterator,typename BinaryOperation, | |
848 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
849 | > | |
850 | OutputIterator transform( | |
851 | const Iterator& first1,const Iterator& last1,InputIterator first2, | |
852 | OutputIterator res,BinaryOperation op) | |
853 | { | |
854 | return generic_copy<transform2_alg,Ts...>(first1,last1,res,first2,op); | |
855 | } | |
856 | ||
857 | struct replace_copy_alg | |
858 | { | |
859 | /* std::replace_copy broken in VS2015, internal ticket VSO#279818 | |
860 | * "<algorithm>: replace_copy() and replace_copy_if() shouldn't use the | |
861 | * conditional operator". | |
862 | */ | |
863 | ||
b32b8144 FG |
864 | template<typename InputIterator,typename OutputIterator,typename T> |
865 | OutputIterator operator()( | |
866 | InputIterator first,InputIterator last,OutputIterator res, | |
867 | const T& old_x,const T& new_x) | |
868 | { | |
869 | for(;first!=last;++first,++res){ | |
870 | if(*first==old_x)*res=new_x; | |
871 | else *res=*first; | |
872 | } | |
873 | return res; | |
874 | } | |
875 | }; | |
876 | ||
877 | template< | |
878 | typename... Ts,typename Iterator,typename OutputIterator,typename T, | |
879 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
880 | > | |
881 | OutputIterator replace_copy( | |
882 | const Iterator& first,const Iterator& last,OutputIterator res, | |
883 | const T& old_x,const T& new_x) | |
884 | { | |
885 | return generic_copy<replace_copy_alg,Ts...>(first,last,res,old_x,new_x); | |
886 | } | |
887 | ||
888 | struct replace_copy_if_alg | |
889 | { | |
890 | /* std::replace_copy_if broken in VS2015, internal ticket VSO#279818 | |
891 | * "<algorithm>: replace_copy() and replace_copy_if() shouldn't use the | |
892 | * conditional operator". | |
893 | */ | |
894 | ||
b32b8144 FG |
895 | template< |
896 | typename InputIterator,typename OutputIterator, | |
897 | typename Predicate,typename T | |
898 | > | |
899 | OutputIterator operator()( | |
900 | InputIterator first,InputIterator last,OutputIterator res, | |
901 | Predicate pred,const T& new_x) | |
902 | { | |
903 | for(;first!=last;++first,++res){ | |
904 | if(pred(*first))*res=new_x; | |
905 | else *res=*first; | |
906 | } | |
907 | return res; | |
908 | } | |
909 | }; | |
910 | ||
911 | template< | |
912 | typename... Ts,typename Iterator,typename OutputIterator, | |
913 | typename Predicate,typename T, | |
914 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
915 | > | |
916 | OutputIterator replace_copy_if( | |
917 | const Iterator& first,const Iterator& last,OutputIterator res, | |
918 | Predicate pred,const T& new_x) | |
919 | { | |
920 | return generic_copy<replace_copy_if_alg,Ts...>(first,last,res,pred,new_x); | |
921 | } | |
922 | ||
923 | BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_remove_copy,std::remove_copy) | |
924 | ||
925 | template< | |
926 | typename... Ts,typename Iterator,typename OutputIterator,typename T, | |
927 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
928 | > | |
929 | OutputIterator remove_copy( | |
930 | const Iterator& first,const Iterator& last,OutputIterator res,const T& x) | |
931 | { | |
932 | return generic_copy<std_remove_copy,Ts...>(first,last,res,x); | |
933 | } | |
934 | ||
935 | BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET( | |
936 | std_remove_copy_if,std::remove_copy_if) | |
937 | ||
938 | template< | |
939 | typename... Ts,typename Iterator,typename OutputIterator,typename Predicate, | |
940 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
941 | > | |
942 | OutputIterator remove_copy_if( | |
943 | const Iterator& first,const Iterator& last,OutputIterator res,Predicate pred) | |
944 | { | |
945 | return generic_copy<std_remove_copy_if,Ts...>(first,last,res,pred); | |
946 | } | |
947 | ||
948 | template<typename... Ts> | |
949 | struct unique_copy_alg | |
950 | { | |
b32b8144 FG |
951 | template< |
952 | typename LocalIterator,typename OutputIterator, | |
953 | typename BinaryPredicate,typename LocalBaseIterator | |
954 | > | |
955 | OutputIterator operator()( | |
956 | LocalIterator first,LocalIterator last, | |
957 | OutputIterator res, BinaryPredicate pred, | |
958 | bool& carry,const std::type_info* prev_info, /* note the &s */ | |
959 | LocalBaseIterator& prev)const | |
960 | { | |
961 | if(carry){ | |
962 | auto p=restitute_iterator<Ts...>(deref_to(pred)); | |
963 | for(;first!=last;++first)if(!p(*prev_info,prev,first))break; | |
964 | } | |
965 | if(first==last)return res; | |
966 | res=std::unique_copy(first,last,res,pred); | |
967 | carry=true; | |
968 | prev_info=&typeid( | |
969 | typename std::iterator_traits<LocalIterator>::value_type); | |
970 | prev=LocalBaseIterator{last-1}; | |
971 | return res; | |
972 | } | |
973 | }; | |
974 | ||
975 | template< | |
976 | typename... Ts,typename Iterator, | |
977 | typename OutputIterator,typename BinaryPredicate, | |
978 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
979 | > | |
980 | OutputIterator unique_copy( | |
981 | const Iterator& first,const Iterator& last, | |
982 | OutputIterator res,BinaryPredicate pred) | |
983 | { | |
984 | using traits=iterator_traits<Iterator>; | |
985 | using local_base_iterator=typename traits::local_base_iterator; | |
986 | ||
987 | bool carry=false; | |
988 | const std::type_info* prev_info{&typeid(void)}; | |
989 | local_base_iterator prev; | |
990 | return generic_copy<unique_copy_alg<Ts...>,Ts...>( | |
991 | first,last,res,pred,carry,prev_info,prev); | |
992 | } | |
993 | ||
994 | template< | |
995 | typename... Ts,typename Iterator,typename OutputIterator, | |
996 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
997 | > | |
998 | OutputIterator unique_copy( | |
999 | const Iterator& first,const Iterator& last,OutputIterator res) | |
1000 | { | |
1001 | return algorithm::unique_copy<Ts...>(first,last,res,transparent_equal_to{}); | |
1002 | } | |
1003 | ||
1004 | template< | |
1005 | typename... Ts,typename Iterator,typename OutputIterator, | |
1006 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
1007 | > | |
1008 | OutputIterator rotate_copy( | |
1009 | const Iterator& first,const Iterator& middle,const Iterator& last, | |
1010 | OutputIterator res) | |
1011 | { | |
1012 | res=algorithm::copy<Ts...>(middle,last,res); | |
1013 | return algorithm::copy<Ts...>(first,middle,res); | |
1014 | } | |
1015 | ||
92f5a8d4 TL |
1016 | struct sample_alg |
1017 | { | |
1018 | template< | |
1019 | typename InputIterator,typename OutputIterator, | |
1020 | typename Distance,typename UniformRandomBitGenerator | |
1021 | > | |
1022 | OutputIterator operator()( | |
1023 | InputIterator first,InputIterator last, | |
1024 | OutputIterator res,Distance& n,Distance& m, /* note the &s */ | |
1025 | UniformRandomBitGenerator& g)const | |
1026 | { | |
1027 | for(;first!=last&&n!=0;++first){ | |
1028 | auto r=std::uniform_int_distribution<Distance>(0,--m)(g); | |
1029 | if (r<n){ | |
1030 | *res++=*first; | |
1031 | --n; | |
1032 | } | |
1033 | } | |
1034 | return res; | |
1035 | } | |
1036 | }; | |
1037 | ||
1038 | template< | |
1039 | typename... Ts,typename Iterator,typename OutputIterator, | |
1040 | typename Distance,typename UniformRandomBitGenerator, | |
1041 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
1042 | > | |
1043 | OutputIterator sample( | |
1044 | const Iterator& first,const Iterator& last, | |
1045 | OutputIterator res,Distance n,UniformRandomBitGenerator&& g) | |
1046 | { | |
1047 | Distance m=algorithm::fast_distance(first,last); | |
1048 | n=(std::min)(n,m); | |
1049 | ||
1050 | for(auto i:detail::segment_split(first,last)){ | |
1051 | auto alg=restitute_range<Ts...>(sample_alg{},res,n,m,g); | |
1052 | res=alg(i); | |
1053 | if(n==0)return res; | |
1054 | } | |
1055 | return res; /* never reached */ | |
1056 | } | |
1057 | ||
b32b8144 FG |
1058 | template< |
1059 | typename... Ts,typename Iterator,typename Predicate, | |
1060 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
1061 | > | |
1062 | bool is_partitioned(const Iterator& first,const Iterator& last,Predicate pred) | |
1063 | { | |
1064 | auto it=algorithm::find_if_not<Ts...>(first,last,pred); | |
1065 | if(it==last)return true; | |
1066 | return algorithm::none_of<Ts...>(++it,last,pred); | |
1067 | } | |
1068 | ||
1069 | BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET( | |
1070 | std_partition_copy,std::partition_copy) | |
1071 | ||
1072 | template< | |
1073 | typename... Ts,typename Iterator, | |
1074 | typename OutputIterator1,typename OutputIterator2,typename Predicate, | |
1075 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
1076 | > | |
1077 | std::pair<OutputIterator1,OutputIterator2> partition_copy( | |
1078 | const Iterator& first,const Iterator& last, | |
1079 | OutputIterator1 rest,OutputIterator2 resf,Predicate pred) | |
1080 | { | |
1081 | for(auto i:detail::segment_split(first,last)){ | |
1082 | auto alg=restitute_range<Ts...>(std_partition_copy{},rest,resf,pred); | |
1083 | std::tie(rest,resf)=alg(i); | |
1084 | } | |
1085 | return {rest,resf}; | |
1086 | } | |
1087 | ||
1088 | template<typename Predicate,typename... Ts> | |
1089 | struct partition_point_pred | |
1090 | { | |
1091 | partition_point_pred(const Predicate& pred):pred(pred){} | |
1092 | ||
1093 | template<typename Iterator> | |
1094 | bool operator()(const Iterator& it)const | |
1095 | { | |
1096 | using traits=iterator_traits<Iterator>; | |
1097 | auto p=restitute_iterator<Ts...>(deref_to(pred)); | |
1098 | return p( | |
1099 | traits::base_segment_info_iterator_from(it)->type_info(), | |
1100 | traits::local_base_iterator_from(it)); | |
1101 | } | |
1102 | ||
1103 | Predicate pred; | |
1104 | }; | |
1105 | ||
1106 | template< | |
1107 | typename... Ts,typename Iterator,typename Predicate, | |
1108 | enable_if_poly_collection_iterator<Iterator> =nullptr | |
1109 | > | |
1110 | Iterator partition_point( | |
1111 | const Iterator& first,const Iterator& last,Predicate pred) | |
1112 | { | |
1113 | auto_iterator<Iterator> afirst{first},alast{last}; | |
1114 | partition_point_pred<Predicate,Ts...> p{pred}; | |
1115 | return *std::partition_point(afirst,alast,p); | |
1116 | } | |
1117 | ||
1118 | } /* namespace poly_collection::detail::algorithm */ | |
1119 | ||
1120 | } /* namespace poly_collection::detail */ | |
1121 | ||
1122 | /* non-modifying sequence operations */ | |
1123 | ||
1124 | using detail::algorithm::all_of; | |
1125 | using detail::algorithm::any_of; | |
1126 | using detail::algorithm::none_of; | |
1127 | using detail::algorithm::for_each; | |
92f5a8d4 | 1128 | using detail::algorithm::for_each_n; |
b32b8144 FG |
1129 | using detail::algorithm::find; |
1130 | using detail::algorithm::find_if; | |
1131 | using detail::algorithm::find_if_not; | |
1132 | using detail::algorithm::find_end; | |
1133 | using detail::algorithm::find_first_of; | |
1134 | using detail::algorithm::adjacent_find; | |
1135 | using detail::algorithm::count; | |
1136 | using detail::algorithm::count_if; | |
1137 | using detail::algorithm::mismatch; | |
1138 | using detail::algorithm::equal; | |
1139 | using detail::algorithm::is_permutation; | |
1140 | using detail::algorithm::search; | |
1141 | using detail::algorithm::search_n; | |
1142 | ||
1143 | /* modifying sequence operations */ | |
1144 | ||
1145 | using detail::algorithm::copy; | |
1146 | using detail::algorithm::copy_n; | |
1147 | using detail::algorithm::copy_if; | |
92f5a8d4 | 1148 | /* copy_backward requires BidirectionalIterator */ |
b32b8144 | 1149 | using detail::algorithm::move; |
92f5a8d4 | 1150 | /* move_backward requires BidirectionalIterator */ |
b32b8144 FG |
1151 | /* swap_ranges requires Swappable */ |
1152 | /* iter_swap requires Swappable */ | |
1153 | using detail::algorithm::transform; | |
1154 | /* replace requires Assignable */ | |
1155 | /* replace_if requires Assignable */ | |
1156 | using detail::algorithm::replace_copy; | |
1157 | using detail::algorithm::replace_copy_if; | |
1158 | /* fill requires Assignable */ | |
1159 | /* fill_n requires Assignable */ | |
1160 | /* generate requires Assignable */ | |
1161 | /* generate_n requires Assignable */ | |
1162 | /* remove requires MoveAssignable */ | |
1163 | /* remove_if requires MoveAssignable */ | |
1164 | using detail::algorithm::remove_copy; | |
1165 | using detail::algorithm::remove_copy_if; | |
1166 | /* unique requires MoveAssignable */ | |
1167 | using detail::algorithm::unique_copy; | |
1168 | /* reverse requires BidirectionalIterator */ | |
1169 | /* reverse_copy requires BidirectionalIterator */ | |
1170 | /* rotate requires MoveAssignable */ | |
1171 | using detail::algorithm::rotate_copy; | |
92f5a8d4 | 1172 | using detail::algorithm::sample; |
b32b8144 FG |
1173 | /* shuffle requires RandomAccessIterator */ |
1174 | using detail::algorithm::is_partitioned; | |
1175 | /* partition requires Swappable */ | |
1176 | /* stable_partition requires Swappable */ | |
1177 | using detail::algorithm::partition_copy; | |
1178 | using detail::algorithm::partition_point; | |
1179 | ||
1180 | /* sorting and related operations not provided */ | |
1181 | ||
1182 | } /* namespace poly_collection */ | |
1183 | ||
1184 | } /* namespace boost */ | |
1185 | ||
1186 | #endif |