1 | // -- algorithm.hpp -- Boost Lambda Library ----------------------------------- |
2 | // Copyright (C) 2002 Jaakko Jarvi (jaakko.jarvi@cs.utu.fi) |
3 | // Copyright (C) 2002 Gary Powell (gwpowell@hotmail.com) |
4 | // |
5 | // Distributed under the Boost Software License, Version 1.0. (See |
6 | // accompanying file LICENSE_1_0.txt or copy at |
7 | // http://www.boost.org/LICENSE_1_0.txt) |
8 | // |
9 | // For more information, see http://www.boost.org |
10 | |
11 | #ifndef BOOST_LAMBDA_ALGORITHM_HPP |
12 | #define BOOST_LAMBDA_ALGORITHM_HPP |
13 | |
14 | #include "boost/lambda/core.hpp" |
15 | |
16 | #include <algorithm> |
17 | #include <iterator> // for iterator_traits |
18 | #include <utility> // for std::pair |
19 | |
20 | namespace boost { |
21 | namespace lambda { |
22 | |
23 | namespace ll { |
24 | |
25 | // for_each --------------------------------- |
26 | |
27 | struct for_each { |
28 | |
29 | template <class Args> |
30 | struct sig { |
31 | typedef typename boost::remove_const< |
32 | typename boost::tuples::element<3, Args>::type |
33 | >::type type; |
34 | }; |
35 | |
36 | template <class A, class C> |
37 | C |
38 | operator()(A a, A b, C c) const |
39 | { return ::std::for_each(a, b, c); } |
40 | }; |
41 | |
42 | // find --------------------------------- |
43 | |
44 | struct find { |
45 | |
46 | template <class Args> |
47 | struct sig { |
48 | typedef typename boost::remove_const< |
49 | typename boost::tuples::element<1, Args>::type |
50 | >::type type; |
51 | }; |
52 | |
53 | template <class A, class C> |
54 | A |
55 | operator()(A a, A b, const C& c) const |
56 | { return ::std::find(a, b, c); } |
57 | }; |
58 | |
59 | |
60 | // find_if --------------------------------- |
61 | |
62 | struct find_if { |
63 | |
64 | template <class Args> |
65 | struct sig { |
66 | typedef typename boost::remove_const< |
67 | typename boost::tuples::element<1, Args>::type |
68 | >::type type; |
69 | }; |
70 | |
71 | template <class A, class C> |
72 | A |
73 | operator()(A a, A b, C c) const |
74 | { return ::std::find_if(a, b, c); } |
75 | }; |
76 | |
77 | // find_end --------------------------------- |
78 | |
79 | struct find_end { |
80 | |
81 | template <class Args> |
82 | struct sig { |
83 | typedef typename boost::remove_const< |
84 | typename boost::tuples::element<1, Args>::type |
85 | >::type type; |
86 | }; |
87 | |
88 | template <class A, class C> |
89 | A |
90 | operator()(A a, A b, C c, C d) const |
91 | { return ::std::find_end(a, b, c, d); } |
92 | |
93 | template <class A, class C, class E> |
94 | A |
95 | operator()(A a, A b, C c, C d, E e) const |
96 | { return ::std::find_end(a, b, c, d, e); } |
97 | |
98 | }; |
99 | |
100 | // find_first_of --------------------------------- |
101 | |
102 | struct find_first_of { |
103 | |
104 | template <class Args> |
105 | struct sig { |
106 | typedef typename boost::remove_const< |
107 | typename boost::tuples::element<1, Args>::type |
108 | >::type type; |
109 | }; |
110 | |
111 | template <class A, class C> |
112 | A |
113 | operator()(A a, A b, C c, C d) const |
114 | { return ::std::find_first_of(a, b, c, d); } |
115 | |
116 | template <class A, class C, class E> |
117 | A |
118 | operator()(A a, A b, C c, C d, E e) const |
119 | { return ::std::find_first_of(a, b, c, d, e); } |
120 | |
121 | }; |
122 | |
123 | // adjacent_find --------------------------------- |
124 | |
125 | struct adjacent_find { |
126 | |
127 | template <class Args> |
128 | struct sig { |
129 | typedef typename boost::remove_const< |
130 | typename boost::tuples::element<1, Args>::type |
131 | >::type type; |
132 | }; |
133 | |
134 | template <class A> |
135 | A |
136 | operator()(A a, A b) const |
137 | { return ::std::adjacent_find(a, b); } |
138 | |
139 | template <class A, class C> |
140 | A |
141 | operator()(A a, A b, C c) const |
142 | { return ::std::adjacent_find(a, b, c); } |
143 | |
144 | }; |
145 | |
146 | // count --------------------------------- |
147 | |
148 | struct count { |
149 | |
150 | template <class Args> |
151 | struct sig { |
152 | typedef typename ::std::iterator_traits< |
153 | typename boost::remove_const< |
154 | typename boost::tuples::element<1, Args>::type |
155 | >::type |
156 | >::difference_type type; |
157 | }; |
158 | |
159 | template <class A, class C > |
160 | typename ::std::iterator_traits<A>::difference_type |
161 | operator()(A a, A b, const C& c) const |
162 | { return ::std::count(a, b, c); } |
163 | }; |
164 | |
165 | // count_if --------------------------------- |
166 | |
167 | struct count_if { |
168 | |
169 | template <class Args> |
170 | struct sig { |
171 | typedef typename ::std::iterator_traits< |
172 | typename boost::remove_const< |
173 | typename boost::tuples::element<1, Args>::type |
174 | >::type |
175 | >::difference_type type; |
176 | }; |
177 | |
178 | template <class A, class C > |
179 | typename ::std::iterator_traits<A>::difference_type |
180 | operator()(A a, A b, C c) const |
181 | { return ::std::count_if(a, b, c); } |
182 | }; |
183 | |
184 | |
185 | // mismatch --------------------------------- |
186 | |
187 | struct mismatch { |
188 | |
189 | template <class Args> |
190 | struct sig { |
191 | typedef typename boost::remove_const< |
192 | typename boost::tuples::element<1, Args>::type |
193 | >::type element1_type; |
194 | |
195 | typedef typename boost::remove_const< |
196 | typename boost::tuples::element<3, Args>::type |
197 | >::type element2_type; |
198 | |
199 | typedef ::std::pair< element1_type, element2_type > type; |
200 | }; |
201 | |
202 | template <class A, class C > |
203 | ::std::pair<A,C> |
204 | operator()(A a, A b, C c) const |
205 | { return ::std::mismatch(a, b, c); } |
206 | |
207 | template <class A, class C, class D> |
208 | ::std::pair<A,C> |
209 | operator()(A a, A b, C c, D d) const |
210 | { return ::std::mismatch(a, b, c, d); } |
211 | |
212 | }; |
213 | |
214 | // equal --------------------------------- |
215 | |
216 | struct equal { |
217 | |
218 | template <class Args> |
219 | struct sig { |
220 | typedef bool type; |
221 | }; |
222 | |
223 | template <class A, class C > |
224 | bool |
225 | operator()(A a, A b, C c) const |
226 | { return ::std::equal(a, b, c); } |
227 | |
228 | template <class A, class C, class D> |
229 | bool |
230 | operator()(A a, A b, C c, D d) const |
231 | { return ::std::equal(a, b, c, d); } |
232 | |
233 | }; |
234 | |
235 | // search -------------------------------- |
236 | |
237 | struct search { |
238 | |
239 | template <class Args> |
240 | struct sig { |
241 | typedef typename boost::remove_const< |
242 | typename boost::tuples::element<1, Args>::type |
243 | >::type type; |
244 | }; |
245 | |
246 | template <class A, class C> |
247 | A |
248 | operator()(A a, A b, C c, C d) const |
249 | { return std::search(a, b, c, d);} |
250 | |
251 | template <class A, class C, class E> |
252 | A |
253 | operator()(A a, A b, C c, C d, E e) const |
254 | { return std::search(a, b, c, d, e);} |
255 | |
256 | }; |
257 | |
258 | // copy --------------------------------- |
259 | |
260 | struct copy { |
261 | |
262 | template <class Args> |
263 | struct sig { |
264 | typedef typename boost::remove_const< |
265 | typename boost::tuples::element<3, Args>::type |
266 | >::type type; |
267 | }; |
268 | |
269 | template <class A, class C> |
270 | C |
271 | operator()(A a, A b, C c) const |
272 | { return ::std::copy(a, b, c); } |
273 | |
274 | }; |
275 | |
276 | // copy_backward --------------------------------- |
277 | |
278 | struct copy_backward { |
279 | |
280 | template <class Args> |
281 | struct sig { |
282 | typedef typename boost::remove_const< |
283 | typename boost::tuples::element<3, Args>::type |
284 | >::type type; |
285 | }; |
286 | |
287 | template <class A, class C> |
288 | C |
289 | operator()(A a, A b, C c) const |
290 | { return ::std::copy_backward(a, b, c); } |
291 | |
292 | }; |
293 | |
294 | // swap --------------------------------- |
295 | |
296 | struct swap { |
297 | |
298 | template <class Args> |
299 | struct sig { |
300 | typedef void type; |
301 | }; |
302 | |
303 | template <class A> |
304 | void |
305 | operator()(A a, A b) const |
306 | { ::std::swap(a, b); } |
307 | |
308 | }; |
309 | |
310 | // swap_ranges --------------------------------- |
311 | |
312 | struct swap_ranges { |
313 | |
314 | template <class Args> |
315 | struct sig { |
316 | typedef typename boost::remove_const< |
317 | typename boost::tuples::element<3, Args>::type |
318 | >::type type; |
319 | }; |
320 | |
321 | template <class A, class C> |
322 | C |
323 | operator()(A a, A b, C c) const |
324 | { return ::std::swap_ranges(a, b, c); } |
325 | |
326 | }; |
327 | |
328 | // iter_swap --------------------------------- |
329 | |
330 | struct iter_swap { |
331 | |
332 | template <class Args> |
333 | struct sig { |
334 | typedef void type; |
335 | }; |
336 | |
337 | template <class A> |
338 | void |
339 | operator()(A a, A b) const |
340 | { ::std::iter_swap(a, b); } |
341 | |
342 | }; |
343 | |
344 | |
345 | // transform -------------------------------- |
346 | |
347 | struct transform { |
348 | |
349 | template <class Args> |
350 | struct sig { |
351 | typedef typename boost::remove_const< |
352 | typename boost::tuples::element< |
353 | boost::tuples::length<Args>::value - 2, |
354 | Args |
355 | >::type |
356 | >::type type; |
357 | }; |
358 | |
359 | template <class A, class C, class D> |
360 | C |
361 | operator()(A a, A b, C c, D d) const |
362 | { return std::transform(a, b, c, d);} |
363 | |
364 | template <class A, class C, class D, class E> |
365 | D |
366 | operator()(A a, A b, C c, D d, E e) const |
367 | { return std::transform(a, b, c, d, e);} |
368 | |
369 | }; |
370 | |
371 | // replace --------------------------------- |
372 | |
373 | struct replace { |
374 | |
375 | template <class Args> |
376 | struct sig { |
377 | typedef void type; |
378 | }; |
379 | |
380 | template <class A, class C> |
381 | void |
382 | operator()(A a, A b, const C& c, const C& d) const |
383 | { ::std::replace(a, b, c, d); } |
384 | |
385 | }; |
386 | |
387 | // replace_if --------------------------------- |
388 | |
389 | struct replace_if { |
390 | |
391 | template <class Args> |
392 | struct sig { |
393 | typedef void type; |
394 | }; |
395 | |
396 | template <class A, class C, class D> |
397 | void |
398 | operator()(A a, A b, C c, const D& d) const |
399 | { ::std::replace_if(a, b, c, d); } |
400 | |
401 | }; |
402 | |
403 | // replace_copy --------------------------------- |
404 | |
405 | struct replace_copy { |
406 | |
407 | template <class Args> |
408 | struct sig { |
409 | typedef typename boost::remove_const< |
410 | typename boost::tuples::element<3, Args>::type |
411 | >::type type; |
412 | }; |
413 | |
414 | template <class A, class C, class D> |
415 | C |
416 | operator()(A a, A b, C c, const D& d, const D& e) const |
417 | { return ::std::replace_copy(a, b, c, d, e); } |
418 | |
419 | }; |
420 | |
421 | // replace_copy_if --------------------------------- |
422 | |
423 | struct replace_copy_if { |
424 | |
425 | template <class Args> |
426 | struct sig { |
427 | typedef typename boost::remove_const< |
428 | typename boost::tuples::element<3, Args>::type |
429 | >::type type; |
430 | }; |
431 | |
432 | template <class A, class C, class D, class E> |
433 | C |
434 | operator()(A a, A b, C c, D d, const E& e) const |
435 | { return ::std::replace_copy_if(a, b, c, d, e); } |
436 | |
437 | }; |
438 | |
439 | // fill --------------------------------- |
440 | |
441 | struct fill { |
442 | |
443 | template <class Args> |
444 | struct sig { |
445 | typedef void type; |
446 | }; |
447 | |
448 | template <class A, class C> |
449 | void |
450 | operator()(A a, A b, const C& c) const |
451 | { ::std::fill(a, b, c); } |
452 | |
453 | }; |
454 | |
455 | // fill_n --------------------------------- |
456 | |
457 | struct fill_n { |
458 | |
459 | template <class Args> |
460 | struct sig { |
461 | typedef void type; |
462 | }; |
463 | |
464 | template <class A, class B, class C> |
465 | void |
466 | operator()(A a, B b, const C& c) const |
467 | { ::std::fill_n(a, b, c); } |
468 | |
469 | }; |
470 | |
471 | // generate --------------------------------- |
472 | |
473 | struct generate { |
474 | |
475 | template <class Args> |
476 | struct sig { |
477 | typedef void type; |
478 | }; |
479 | |
480 | template <class A, class C> |
481 | void |
482 | operator()(A a, A b, C c) const |
483 | { ::std::generate(a, b, c); } |
484 | |
485 | }; |
486 | |
487 | // generate_n --------------------------------- |
488 | |
489 | struct generate_n { |
490 | |
491 | template <class Args> |
492 | struct sig { |
493 | typedef void type; |
494 | }; |
495 | |
496 | template <class A, class B, class C> |
497 | void |
498 | operator()(A a, B b, C c) const |
499 | { ::std::generate_n(a, b, c); } |
500 | |
501 | }; |
502 | |
503 | // remove --------------------------------- |
504 | |
505 | struct remove { |
506 | |
507 | template <class Args> |
508 | struct sig { |
509 | typedef typename boost::remove_const< |
510 | typename boost::tuples::element<1, Args>::type |
511 | >::type type; |
512 | }; |
513 | |
514 | template <class A, class C > |
515 | A |
516 | operator()(A a, A b, const C& c) const |
517 | { return ::std::remove(a, b, c); } |
518 | }; |
519 | |
520 | // remove_if --------------------------------- |
521 | |
522 | struct remove_if { |
523 | |
524 | template <class Args> |
525 | struct sig { |
526 | typedef typename boost::remove_const< |
527 | typename boost::tuples::element<1, Args>::type |
528 | >::type type; |
529 | }; |
530 | |
531 | template <class A, class C > |
532 | A |
533 | operator()(A a, A b, C c) const |
534 | { return ::std::remove_if(a, b, c); } |
535 | }; |
536 | |
537 | // remove_copy --------------------------------- |
538 | |
539 | struct remove_copy { |
540 | |
541 | template <class Args> |
542 | struct sig { |
543 | typedef typename boost::remove_const< |
544 | typename boost::tuples::element<3, Args>::type |
545 | >::type type; |
546 | }; |
547 | |
548 | template <class A, class C, class D > |
549 | C |
550 | operator()(A a, A b, C c, const D& d) const |
551 | { return ::std::remove_copy(a, b, c, d); } |
552 | }; |
553 | |
554 | // remove_copy_if --------------------------------- |
555 | |
556 | struct remove_copy_if { |
557 | |
558 | template <class Args> |
559 | struct sig { |
560 | typedef typename boost::remove_const< |
561 | typename boost::tuples::element<3, Args>::type |
562 | >::type type; |
563 | }; |
564 | |
565 | template <class A, class C, class D > |
566 | C |
567 | operator()(A a, A b, C c, D d) const |
568 | { return ::std::remove_copy_if(a, b, c, d); } |
569 | }; |
570 | |
571 | // unique --------------------------------- |
572 | |
573 | struct unique { |
574 | |
575 | template <class Args> |
576 | struct sig { |
577 | typedef typename boost::remove_const< |
578 | typename boost::tuples::element<1, Args>::type |
579 | >::type type; |
580 | }; |
581 | |
582 | template <class A> |
583 | A |
584 | operator()(A a, A b) const |
585 | { return ::std::unique(a, b); } |
586 | |
587 | template <class A, class C> |
588 | A |
589 | operator()(A a, A b, C c) const |
590 | { return ::std::unique(a, b, c); } |
591 | |
592 | }; |
593 | |
594 | // unique_copy --------------------------------- |
595 | |
596 | struct unique_copy { |
597 | |
598 | template <class Args> |
599 | struct sig { |
600 | typedef typename boost::remove_const< |
601 | typename boost::tuples::element<3, Args>::type |
602 | >::type type; |
603 | }; |
604 | |
605 | template <class A, class C > |
606 | C |
607 | operator()(A a, A b, C c) const |
608 | { return ::std::unique_copy(a, b, c); } |
609 | |
610 | template <class A, class C, class D> |
611 | C |
612 | operator()(A a, A b, C c, D d) const |
613 | { return ::std::unique_copy(a, b, c, d); } |
614 | |
615 | }; |
616 | |
617 | // reverse --------------------------------- |
618 | |
619 | struct reverse { |
620 | |
621 | template <class Args> |
622 | struct sig { |
623 | typedef void type; |
624 | }; |
625 | |
626 | template <class A> |
627 | void |
628 | operator()(A a, A b) const |
629 | { ::std::reverse(a, b); } |
630 | |
631 | }; |
632 | |
633 | // reverse_copy --------------------------------- |
634 | |
635 | struct reverse_copy { |
636 | |
637 | template <class Args> |
638 | struct sig { |
639 | typedef typename boost::remove_const< |
640 | typename boost::tuples::element<3, Args>::type |
641 | >::type type; |
642 | }; |
643 | |
644 | template <class A, class C > |
645 | C |
646 | operator()(A a, A b, C c) const |
647 | { return ::std::reverse_copy(a, b, c); } |
648 | |
649 | }; |
650 | |
651 | // rotate --------------------------------- |
652 | |
653 | struct rotate { |
654 | |
655 | template <class Args> |
656 | struct sig { |
657 | typedef void type; |
658 | }; |
659 | |
660 | template <class A> |
661 | void |
662 | operator()(A a, A b, A c) const |
663 | { ::std::rotate(a, b, c); } |
664 | |
665 | }; |
666 | |
667 | // rotate_copy --------------------------------- |
668 | |
669 | struct rotate_copy { |
670 | |
671 | template <class Args> |
672 | struct sig { |
673 | typedef typename boost::remove_const< |
674 | typename boost::tuples::element<3, Args>::type |
675 | >::type type; |
676 | }; |
677 | |
678 | template <class A, class D> |
679 | D |
680 | operator()(A a, A b, A c, D d) const |
681 | { return ::std::rotate_copy(a, b, c, d); } |
682 | |
683 | }; |
684 | |
685 | // random_shuffle --------------------------------- |
686 | |
687 | struct random_shuffle { |
688 | |
689 | template <class Args> |
690 | struct sig { |
691 | typedef void type; |
692 | }; |
693 | |
694 | template <class A> |
695 | void |
696 | operator()(A a, A b) const |
697 | { ::std::random_shuffle(a, b); } |
698 | |
699 | template <class A, class C> |
700 | void |
701 | operator()(A a, A b, const C& c) const |
702 | { ::std::random_shuffle(a, b, c); } |
703 | |
704 | }; |
705 | |
706 | |
707 | // partition --------------------------------- |
708 | |
709 | struct partition { |
710 | |
711 | template <class Args> |
712 | struct sig { |
713 | typedef typename boost::remove_const< |
714 | typename boost::tuples::element<1, Args>::type |
715 | >::type type; |
716 | }; |
717 | |
718 | template <class A, class C> |
719 | A |
720 | operator()(A a, A b, C c) const |
721 | { return ::std::partition(a, b, c); } |
722 | |
723 | }; |
724 | |
725 | // stable_partition --------------------------------- |
726 | |
727 | struct stable_partition { |
728 | |
729 | template <class Args> |
730 | struct sig { |
731 | typedef typename boost::remove_const< |
732 | typename boost::tuples::element<1, Args>::type |
733 | >::type type; |
734 | }; |
735 | |
736 | template <class A, class C> |
737 | A |
738 | operator()(A a, A b, C c) const |
739 | { return ::std::stable_partition(a, b, c); } |
740 | |
741 | }; |
742 | |
743 | // sort --------------------------------- |
744 | |
745 | struct sort { |
746 | |
747 | template <class Args> |
748 | struct sig { |
749 | typedef void type; |
750 | }; |
751 | |
752 | template <class A> |
753 | void |
754 | operator()(A a, A b) const |
755 | { ::std::sort(a, b); } |
756 | |
757 | template <class A, class C> |
758 | void |
759 | operator()(A a, A b, C c) const |
760 | { ::std::sort(a, b, c); } |
761 | |
762 | }; |
763 | |
764 | // stable_sort --------------------------------- |
765 | |
766 | struct stable_sort { |
767 | |
768 | template <class Args> |
769 | struct sig { |
770 | typedef void type; |
771 | }; |
772 | |
773 | template <class A> |
774 | void |
775 | operator()(A a, A b) const |
776 | { ::std::stable_sort(a, b); } |
777 | |
778 | template <class A, class C> |
779 | void |
780 | operator()(A a, A b, C c) const |
781 | { ::std::stable_sort(a, b, c); } |
782 | |
783 | }; |
784 | |
785 | // partial_sort --------------------------------- |
786 | |
787 | struct partial_sort { |
788 | |
789 | template <class Args> |
790 | struct sig { |
791 | typedef void type; |
792 | }; |
793 | |
794 | template <class A> |
795 | void |
796 | operator()(A a, A b, A c) const |
797 | { ::std::partial_sort(a, b, c); } |
798 | |
799 | template <class A, class D> |
800 | void |
801 | operator()(A a, A b, A c, D d) const |
802 | { ::std::partial_sort(a, b, c, d); } |
803 | |
804 | }; |
805 | |
806 | // partial_sort_copy --------------------------------- |
807 | |
808 | struct partial_sort_copy { |
809 | |
810 | template <class Args> |
811 | struct sig { |
812 | typedef typename boost::remove_const< |
813 | typename boost::tuples::element<3, Args>::type |
814 | >::type type; |
815 | }; |
816 | |
817 | template <class A, class C> |
818 | C |
819 | operator()(A a, A b, C c, C d) const |
820 | { return ::std::partial_sort_copy(a, b, c, d); } |
821 | |
822 | template <class A, class C, class E > |
823 | C |
824 | operator()(A a, A b, C c, C d, E e) const |
825 | { return ::std::partial_sort_copy(a, b, c, d, e); } |
826 | }; |
827 | |
828 | // nth_element --------------------------------- |
829 | |
830 | struct nth_element { |
831 | |
832 | template <class Args> |
833 | struct sig { |
834 | typedef void type; |
835 | }; |
836 | |
837 | template <class A> |
838 | void |
839 | operator()(A a, A b, A c) const |
840 | { ::std::nth_element(a, b, c); } |
841 | |
842 | template <class A, class D> |
843 | void |
844 | operator()(A a, A b, A c, D d) const |
845 | { ::std::nth_element(a, b, c, d); } |
846 | |
847 | }; |
848 | |
849 | // lower_bound --------------------------------- |
850 | |
851 | struct lower_bound { |
852 | |
853 | template <class Args> |
854 | struct sig { |
855 | typedef typename boost::remove_const< |
856 | typename boost::tuples::element<1, Args>::type |
857 | >::type type; |
858 | }; |
859 | |
860 | template <class A, class C> |
861 | A |
862 | operator()(A a, A b, const C& c) const |
863 | { return ::std::lower_bound(a, b, c); } |
864 | |
865 | template <class A, class C, class D> |
866 | A |
867 | operator()(A a, A b, const C& c, D d) const |
868 | { return ::std::lower_bound(a, b, c, d); } |
869 | |
870 | }; |
871 | |
872 | // upper_bound --------------------------------- |
873 | |
874 | struct upper_bound { |
875 | |
876 | template <class Args> |
877 | struct sig { |
878 | typedef typename boost::remove_const< |
879 | typename boost::tuples::element<1, Args>::type |
880 | >::type type; |
881 | }; |
882 | |
883 | template <class A, class C> |
884 | A |
885 | operator()(A a, A b, const C& c) const |
886 | { return ::std::upper_bound(a, b, c); } |
887 | |
888 | template <class A, class C, class D> |
889 | A |
890 | operator()(A a, A b, const C& c, D d) const |
891 | { return ::std::upper_bound(a, b, c, d); } |
892 | |
893 | }; |
894 | |
895 | // equal_range --------------------------------- |
896 | |
897 | struct equal_range { |
898 | |
899 | template <class Args> |
900 | struct sig { |
901 | typedef typename boost::remove_const< |
902 | typename boost::tuples::element<1, Args>::type |
903 | >::type element_type; |
904 | |
905 | typedef ::std::pair< element_type, element_type > type; |
906 | }; |
907 | |
908 | template <class A, class C> |
909 | ::std::pair<A,A> |
910 | operator()(A a, A b, const C& c) const |
911 | { return ::std::equal_range(a, b, c); } |
912 | |
913 | template <class A, class C, class D> |
914 | ::std::pair<A,A> |
915 | operator()(A a, A b, const C& c, D d) const |
916 | { return ::std::equal_range(a, b, c, d); } |
917 | |
918 | }; |
919 | |
920 | // binary_search --------------------------------- |
921 | |
922 | struct binary_search { |
923 | |
924 | template <class Args> |
925 | struct sig { |
926 | typedef bool type; |
927 | }; |
928 | |
929 | template <class A, class C > |
930 | bool |
931 | operator()(A a, A b, const C& c) const |
932 | { return ::std::binary_search(a, b, c); } |
933 | |
934 | template <class A, class C, class D> |
935 | bool |
936 | operator()(A a, A b, const C& c, D d) const |
937 | { return ::std::binary_search(a, b, c, d); } |
938 | |
939 | }; |
940 | |
941 | // merge -------------------------------- |
942 | |
943 | struct merge { |
944 | |
945 | template <class Args> |
946 | struct sig { |
947 | typedef typename boost::remove_const< |
948 | typename boost::tuples::element<5, Args>::type |
949 | >::type type; |
950 | }; |
951 | |
952 | template <class A, class C, class E> |
953 | E |
954 | operator()(A a, A b, C c, C d, E e) const |
955 | { return std::merge(a, b, c, d, e);} |
956 | |
957 | template <class A, class C, class E, class F> |
958 | E |
959 | operator()(A a, A b, C c, C d, E e, F f) const |
960 | { return std::merge(a, b, c, d, e, f);} |
961 | |
962 | }; |
963 | |
964 | // inplace_merge --------------------------------- |
965 | |
966 | struct inplace_merge { |
967 | |
968 | template <class Args> |
969 | struct sig { |
970 | typedef void type; |
971 | }; |
972 | |
973 | template <class A> |
974 | void |
975 | operator()(A a, A b, A c) const |
976 | { ::std::inplace_merge(a, b, c); } |
977 | |
978 | template <class A, class D> |
979 | void |
980 | operator()(A a, A b, A c, D d) const |
981 | { ::std::inplace_merge(a, b, c, d); } |
982 | |
983 | }; |
984 | |
985 | // includes --------------------------------- |
986 | |
987 | struct includes { |
988 | |
989 | template <class Args> |
990 | struct sig { |
991 | typedef bool type; |
992 | }; |
993 | |
994 | template <class A, class C> |
995 | bool |
996 | operator()(A a, A b, C c, C d) const |
997 | { return ::std::includes(a, b, c, d); } |
998 | |
999 | template <class A, class C, class E> |
1000 | bool |
1001 | operator()(A a, A b, C c, C d, E e) const |
1002 | { return ::std::includes(a, b, c, d, e); } |
1003 | |
1004 | }; |
1005 | |
1006 | // set_union -------------------------------- |
1007 | |
1008 | struct set_union { |
1009 | |
1010 | template <class Args> |
1011 | struct sig { |
1012 | typedef typename boost::remove_const< |
1013 | typename boost::tuples::element<5, Args>::type |
1014 | >::type type; |
1015 | }; |
1016 | |
1017 | template <class A, class C, class E> |
1018 | E |
1019 | operator()(A a, A b, C c, C d, E e) const |
1020 | { return std::set_union(a, b, c, d, e);} |
1021 | |
1022 | template <class A, class C, class E, class F> |
1023 | E |
1024 | operator()(A a, A b, C c, C d, E e, F f) const |
1025 | { return std::set_union(a, b, c, d, e, f);} |
1026 | |
1027 | }; |
1028 | |
1029 | // set_intersection -------------------------------- |
1030 | |
1031 | struct set_intersection { |
1032 | |
1033 | template <class Args> |
1034 | struct sig { |
1035 | typedef typename boost::remove_const< |
1036 | typename boost::tuples::element<5, Args>::type |
1037 | >::type type; |
1038 | }; |
1039 | |
1040 | template <class A, class C, class E> |
1041 | E |
1042 | operator()(A a, A b, C c, C d, E e) const |
1043 | { return std::set_intersection(a, b, c, d, e);} |
1044 | |
1045 | template <class A, class C, class E, class F> |
1046 | E |
1047 | operator()(A a, A b, C c, C d, E e, F f) const |
1048 | { return std::set_intersection(a, b, c, d, e, f);} |
1049 | |
1050 | }; |
1051 | |
1052 | // set_difference -------------------------------- |
1053 | |
1054 | struct set_difference { |
1055 | |
1056 | template <class Args> |
1057 | struct sig { |
1058 | typedef typename boost::remove_const< |
1059 | typename boost::tuples::element<5, Args>::type |
1060 | >::type type; |
1061 | }; |
1062 | |
1063 | template <class A, class C, class E> |
1064 | E |
1065 | operator()(A a, A b, C c, C d, E e) const |
1066 | { return std::set_difference(a, b, c, d, e);} |
1067 | |
1068 | template <class A, class C, class E, class F> |
1069 | E |
1070 | operator()(A a, A b, C c, C d, E e, F f) const |
1071 | { return std::set_difference(a, b, c, d, e, f);} |
1072 | |
1073 | }; |
1074 | |
1075 | |
1076 | // set_symmetric_difference -------------------------------- |
1077 | |
1078 | struct set_symmetric_difference { |
1079 | |
1080 | template <class Args> |
1081 | struct sig { |
1082 | typedef typename boost::remove_const< |
1083 | typename boost::tuples::element<5, Args>::type |
1084 | >::type type; |
1085 | }; |
1086 | |
1087 | template <class A, class C, class E> |
1088 | E |
1089 | operator()(A a, A b, C c, C d, E e) const |
1090 | { return std::set_symmetric_difference(a, b, c, d, e);} |
1091 | |
1092 | template <class A, class C, class E, class F> |
1093 | E |
1094 | operator()(A a, A b, C c, C d, E e, F f) const |
1095 | { return std::set_symmetric_difference(a, b, c, d, e, f);} |
1096 | |
1097 | }; |
1098 | |
1099 | // push_heap --------------------------------- |
1100 | |
1101 | struct push_heap { |
1102 | |
1103 | template <class Args> |
1104 | struct sig { |
1105 | typedef void type; |
1106 | }; |
1107 | |
1108 | template <class A> |
1109 | void |
1110 | operator()(A a, A b) const |
1111 | { ::std::push_heap(a, b); } |
1112 | |
1113 | template <class A, class C> |
1114 | void |
1115 | operator()(A a, A b, C c) const |
1116 | { ::std::push_heap(a, b, c); } |
1117 | |
1118 | }; |
1119 | |
1120 | // pop_heap --------------------------------- |
1121 | |
1122 | struct pop_heap { |
1123 | |
1124 | template <class Args> |
1125 | struct sig { |
1126 | typedef void type; |
1127 | }; |
1128 | |
1129 | template <class A> |
1130 | void |
1131 | operator()(A a, A b) const |
1132 | { ::std::pop_heap(a, b); } |
1133 | |
1134 | template <class A, class C> |
1135 | void |
1136 | operator()(A a, A b, C c) const |
1137 | { ::std::pop_heap(a, b, c); } |
1138 | |
1139 | }; |
1140 | |
1141 | |
1142 | // make_heap --------------------------------- |
1143 | |
1144 | struct make_heap { |
1145 | |
1146 | template <class Args> |
1147 | struct sig { |
1148 | typedef void type; |
1149 | }; |
1150 | |
1151 | template <class A> |
1152 | void |
1153 | operator()(A a, A b) const |
1154 | { ::std::make_heap(a, b); } |
1155 | |
1156 | template <class A, class C> |
1157 | void |
1158 | operator()(A a, A b, C c) const |
1159 | { ::std::make_heap(a, b, c); } |
1160 | |
1161 | }; |
1162 | |
1163 | // sort_heap --------------------------------- |
1164 | |
1165 | struct sort_heap { |
1166 | |
1167 | template <class Args> |
1168 | struct sig { |
1169 | typedef void type; |
1170 | }; |
1171 | |
1172 | template <class A> |
1173 | void |
1174 | operator()(A a, A b) const |
1175 | { ::std::sort_heap(a, b); } |
1176 | |
1177 | template <class A, class C> |
1178 | void |
1179 | operator()(A a, A b, C c) const |
1180 | { ::std::sort_heap(a, b, c); } |
1181 | |
1182 | }; |
1183 | |
1184 | // min --------------------------------- |
1185 | |
1186 | struct min { |
1187 | |
1188 | template <class Args> |
1189 | struct sig { |
1190 | typedef typename boost::remove_const< |
1191 | typename boost::tuples::element<1, Args>::type |
1192 | >::type type; |
1193 | }; |
1194 | |
1195 | template <class A> |
1196 | A |
1197 | operator()(const A& a, const A& b) const |
1198 | { return (::std::min)(a, b); } |
1199 | |
1200 | template <class A, class C> |
1201 | A |
1202 | operator()(const A& a, const A& b, C c) const |
1203 | { return (::std::min)(a, b, c); } |
1204 | |
1205 | }; |
1206 | |
1207 | // max --------------------------------- |
1208 | |
1209 | struct max { |
1210 | |
1211 | template <class Args> |
1212 | struct sig { |
1213 | typedef typename boost::remove_const< |
1214 | typename boost::tuples::element<1, Args>::type |
1215 | >::type type; |
1216 | }; |
1217 | |
1218 | template <class A> |
1219 | A |
1220 | operator()(const A& a, const A& b) const |
1221 | { return (::std::max)(a, b); } |
1222 | |
1223 | template <class A, class C> |
1224 | A |
1225 | operator()(const A& a, const A& b, C c) const |
1226 | { return (::std::max)(a, b, c); } |
1227 | |
1228 | }; |
1229 | |
1230 | struct min_element { |
1231 | |
1232 | template <class Args> |
1233 | struct sig { |
1234 | typedef typename boost::remove_const< |
1235 | typename boost::tuples::element<1, Args>::type |
1236 | >::type type; |
1237 | }; |
1238 | |
1239 | template <class A> |
1240 | A |
1241 | operator()(A a, A b) const |
1242 | { return ::std::min_element(a, b); } |
1243 | |
1244 | template <class A, class C> |
1245 | A |
1246 | operator()(A a, A b, C c) const |
1247 | { return ::std::min_element(a, b, c); } |
1248 | |
1249 | }; |
1250 | |
1251 | // max_element --------------------------------- |
1252 | |
1253 | struct max_element { |
1254 | |
1255 | template <class Args> |
1256 | struct sig { |
1257 | typedef typename boost::remove_const< |
1258 | typename boost::tuples::element<1, Args>::type |
1259 | >::type type; |
1260 | }; |
1261 | |
1262 | template <class A> |
1263 | A |
1264 | operator()(A a, A b) const |
1265 | { return ::std::max_element(a, b); } |
1266 | |
1267 | template <class A, class C> |
1268 | A |
1269 | operator()(A a, A b, C c) const |
1270 | { return ::std::max_element(a, b, c); } |
1271 | |
1272 | }; |
1273 | |
1274 | |
1275 | // lexicographical_compare --------------------------------- |
1276 | |
1277 | struct lexicographical_compare { |
1278 | |
1279 | template <class Args> |
1280 | struct sig { |
1281 | typedef bool type; |
1282 | }; |
1283 | |
1284 | template <class A, class C> |
1285 | bool |
1286 | operator()(A a, A b, C c, C d) const |
1287 | { return ::std::lexicographical_compare(a, b, c, d); } |
1288 | |
1289 | template <class A, class C, class E> |
1290 | bool |
1291 | operator()(A a, A b, C c, C d, E e) const |
1292 | { return ::std::lexicographical_compare(a, b, c, d, e); } |
1293 | |
1294 | }; |
1295 | |
1296 | // next_permutation --------------------------------- |
1297 | |
1298 | struct next_permutation { |
1299 | |
1300 | template <class Args> |
1301 | struct sig { |
1302 | typedef bool type; |
1303 | }; |
1304 | |
1305 | template <class A> |
1306 | bool |
1307 | operator()(A a, A b) const |
1308 | { return ::std::next_permutation(a, b); } |
1309 | |
1310 | template <class A, class C > |
1311 | bool |
1312 | operator()(A a, A b, C c) const |
1313 | { return ::std::next_permutation(a, b, c); } |
1314 | |
1315 | }; |
1316 | |
1317 | // prev_permutation --------------------------------- |
1318 | |
1319 | struct prev_permutation { |
1320 | |
1321 | template <class Args> |
1322 | struct sig { |
1323 | typedef bool type; |
1324 | }; |
1325 | |
1326 | template <class A> |
1327 | bool |
1328 | operator()(A a, A b) const |
1329 | { return ::std::prev_permutation(a, b); } |
1330 | |
1331 | template <class A, class C > |
1332 | bool |
1333 | operator()(A a, A b, C c) const |
1334 | { return ::std::prev_permutation(a, b, c); } |
1335 | |
1336 | }; |
1337 | |
1338 | |
1339 | |
1340 | |
1341 | |
1342 | } // end of ll namespace |
1343 | |
1344 | // There is no good way to call an overloaded member function in a |
1345 | // lambda expression. |
1346 | // The macro below defines a function object class for calling a |
1347 | // const_iterator returning member function of a container. |
1348 | |
1349 | #define CALL_MEMBER(X) \ |
1350 | struct call_##X { \ |
1351 | template <class Args> \ |
1352 | struct sig { \ |
1353 | typedef typename boost::remove_const< \ |
1354 | typename boost::tuples::element<1, Args>::type \ |
1355 | >::type::const_iterator type; \ |
1356 | }; \ |
1357 | \ |
1358 | template<class T> \ |
1359 | typename T::const_iterator \ |
1360 | operator()(const T& t) const \ |
1361 | { \ |
1362 | return t.X(); \ |
1363 | } \ |
1364 | }; |
1365 | |
1366 | // create call_begin and call_end classes |
1367 | CALL_MEMBER(begin) |
1368 | CALL_MEMBER(end) |
1369 | |
1370 | #undef CALL_MEMBER |
1371 | |
1372 | } // end of lambda namespace |
1373 | } // end of boost namespace |
1374 | |
1375 | |
1376 | |
1377 | #endif |
1378 | |