First public contribution.
1 // -- algorithm.hpp -- Boost Lambda Library -----------------------------------
2 // Copyright (C) 2002 Jaakko Järvi (jaakko.jarvi@cs.utu.fi)
3 // Copyright (C) 2002 Gary Powell (gwpowell@hotmail.com)
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)
9 // For more information, see http://www.boost.org
11 #ifndef BOOST_LAMBDA_ALGORITHM_HPP
12 #define BOOST_LAMBDA_ALGORITHM_HPP
14 #include "boost/lambda/core.hpp"
17 #include <iterator> // for iterator_traits
18 #include <utility> // for std::pair
25 // for_each ---------------------------------
31 typedef typename boost::remove_const<
32 typename boost::tuples::element<3, Args>::type
36 template <class A, class C>
38 operator()(A a, A b, C c) const
39 { return ::std::for_each(a, b, c); }
42 // find ---------------------------------
48 typedef typename boost::remove_const<
49 typename boost::tuples::element<1, Args>::type
53 template <class A, class C>
55 operator()(A a, A b, const C& c) const
56 { return ::std::find(a, b, c); }
60 // find_if ---------------------------------
66 typedef typename boost::remove_const<
67 typename boost::tuples::element<1, Args>::type
71 template <class A, class C>
73 operator()(A a, A b, C c) const
74 { return ::std::find_if(a, b, c); }
77 // find_end ---------------------------------
83 typedef typename boost::remove_const<
84 typename boost::tuples::element<1, Args>::type
88 template <class A, class C>
90 operator()(A a, A b, C c, C d) const
91 { return ::std::find_end(a, b, c, d); }
93 template <class A, class C, class E>
95 operator()(A a, A b, C c, C d, E e) const
96 { return ::std::find_end(a, b, c, d, e); }
100 // find_first_of ---------------------------------
102 struct find_first_of {
104 template <class Args>
106 typedef typename boost::remove_const<
107 typename boost::tuples::element<1, Args>::type
111 template <class A, class C>
113 operator()(A a, A b, C c, C d) const
114 { return ::std::find_first_of(a, b, c, d); }
116 template <class A, class C, class E>
118 operator()(A a, A b, C c, C d, E e) const
119 { return ::std::find_first_of(a, b, c, d, e); }
123 // adjacent_find ---------------------------------
125 struct adjacent_find {
127 template <class Args>
129 typedef typename boost::remove_const<
130 typename boost::tuples::element<1, Args>::type
136 operator()(A a, A b) const
137 { return ::std::adjacent_find(a, b); }
139 template <class A, class C>
141 operator()(A a, A b, C c) const
142 { return ::std::adjacent_find(a, b, c); }
146 // count ---------------------------------
150 template <class Args>
152 typedef typename ::std::iterator_traits<
153 typename boost::remove_const<
154 typename boost::tuples::element<1, Args>::type
156 >::difference_type type;
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); }
165 // count_if ---------------------------------
169 template <class Args>
171 typedef typename ::std::iterator_traits<
172 typename boost::remove_const<
173 typename boost::tuples::element<1, Args>::type
175 >::difference_type type;
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); }
185 // mismatch ---------------------------------
189 template <class Args>
191 typedef typename boost::remove_const<
192 typename boost::tuples::element<1, Args>::type
193 >::type element1_type;
195 typedef typename boost::remove_const<
196 typename boost::tuples::element<3, Args>::type
197 >::type element2_type;
199 typedef ::std::pair< element1_type, element2_type > type;
202 template <class A, class C >
204 operator()(A a, A b, C c) const
205 { return ::std::mismatch(a, b, c); }
207 template <class A, class C, class D>
209 operator()(A a, A b, C c, D d) const
210 { return ::std::mismatch(a, b, c, d); }
214 // equal ---------------------------------
218 template <class Args>
223 template <class A, class C >
225 operator()(A a, A b, C c) const
226 { return ::std::equal(a, b, c); }
228 template <class A, class C, class D>
230 operator()(A a, A b, C c, D d) const
231 { return ::std::equal(a, b, c, d); }
235 // search --------------------------------
239 template <class Args>
241 typedef typename boost::remove_const<
242 typename boost::tuples::element<1, Args>::type
246 template <class A, class C>
248 operator()(A a, A b, C c, C d) const
249 { return std::search(a, b, c, d);}
251 template <class A, class C, class E>
253 operator()(A a, A b, C c, C d, E e) const
254 { return std::search(a, b, c, d, e);}
258 // copy ---------------------------------
262 template <class Args>
264 typedef typename boost::remove_const<
265 typename boost::tuples::element<3, Args>::type
269 template <class A, class C>
271 operator()(A a, A b, C c) const
272 { return ::std::copy(a, b, c); }
276 // copy_backward ---------------------------------
278 struct copy_backward {
280 template <class Args>
282 typedef typename boost::remove_const<
283 typename boost::tuples::element<3, Args>::type
287 template <class A, class C>
289 operator()(A a, A b, C c) const
290 { return ::std::copy_backward(a, b, c); }
294 // swap ---------------------------------
298 template <class Args>
305 operator()(A a, A b) const
306 { ::std::swap(a, b); }
310 // swap_ranges ---------------------------------
314 template <class Args>
316 typedef typename boost::remove_const<
317 typename boost::tuples::element<3, Args>::type
321 template <class A, class C>
323 operator()(A a, A b, C c) const
324 { return ::std::swap_ranges(a, b, c); }
328 // iter_swap ---------------------------------
332 template <class Args>
339 operator()(A a, A b) const
340 { ::std::iter_swap(a, b); }
345 // transform --------------------------------
349 template <class Args>
351 typedef typename boost::remove_const<
352 typename boost::tuples::element<
353 boost::tuples::length<Args>::value - 2,
359 template <class A, class C, class D>
361 operator()(A a, A b, C c, D d) const
362 { return std::transform(a, b, c, d);}
364 template <class A, class C, class D, class E>
366 operator()(A a, A b, C c, D d, E e) const
367 { return std::transform(a, b, c, d, e);}
371 // replace ---------------------------------
375 template <class Args>
380 template <class A, class C>
382 operator()(A a, A b, const C& c, const C& d) const
383 { ::std::replace(a, b, c, d); }
387 // replace_if ---------------------------------
391 template <class Args>
396 template <class A, class C, class D>
398 operator()(A a, A b, C c, const D& d) const
399 { ::std::replace_if(a, b, c, d); }
403 // replace_copy ---------------------------------
405 struct replace_copy {
407 template <class Args>
409 typedef typename boost::remove_const<
410 typename boost::tuples::element<3, Args>::type
414 template <class A, class C, class D>
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); }
421 // replace_copy_if ---------------------------------
423 struct replace_copy_if {
425 template <class Args>
427 typedef typename boost::remove_const<
428 typename boost::tuples::element<3, Args>::type
432 template <class A, class C, class D, class E>
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); }
439 // fill ---------------------------------
443 template <class Args>
448 template <class A, class C>
450 operator()(A a, A b, const C& c) const
451 { ::std::fill(a, b, c); }
455 // fill_n ---------------------------------
459 template <class Args>
464 template <class A, class B, class C>
466 operator()(A a, B b, const C& c) const
467 { ::std::fill_n(a, b, c); }
471 // generate ---------------------------------
475 template <class Args>
480 template <class A, class C>
482 operator()(A a, A b, C c) const
483 { ::std::generate(a, b, c); }
487 // generate_n ---------------------------------
491 template <class Args>
496 template <class A, class B, class C>
498 operator()(A a, B b, C c) const
499 { ::std::generate_n(a, b, c); }
503 // remove ---------------------------------
507 template <class Args>
509 typedef typename boost::remove_const<
510 typename boost::tuples::element<1, Args>::type
514 template <class A, class C >
516 operator()(A a, A b, const C& c) const
517 { return ::std::remove(a, b, c); }
520 // remove_if ---------------------------------
524 template <class Args>
526 typedef typename boost::remove_const<
527 typename boost::tuples::element<1, Args>::type
531 template <class A, class C >
533 operator()(A a, A b, C c) const
534 { return ::std::remove_if(a, b, c); }
537 // remove_copy ---------------------------------
541 template <class Args>
543 typedef typename boost::remove_const<
544 typename boost::tuples::element<3, Args>::type
548 template <class A, class C, class D >
550 operator()(A a, A b, C c, const D& d) const
551 { return ::std::remove_copy(a, b, c, d); }
554 // remove_copy_if ---------------------------------
556 struct remove_copy_if {
558 template <class Args>
560 typedef typename boost::remove_const<
561 typename boost::tuples::element<3, Args>::type
565 template <class A, class C, class D >
567 operator()(A a, A b, C c, D d) const
568 { return ::std::remove_copy_if(a, b, c, d); }
571 // unique ---------------------------------
575 template <class Args>
577 typedef typename boost::remove_const<
578 typename boost::tuples::element<1, Args>::type
584 operator()(A a, A b) const
585 { return ::std::unique(a, b); }
587 template <class A, class C>
589 operator()(A a, A b, C c) const
590 { return ::std::unique(a, b, c); }
594 // unique_copy ---------------------------------
598 template <class Args>
600 typedef typename boost::remove_const<
601 typename boost::tuples::element<3, Args>::type
605 template <class A, class C >
607 operator()(A a, A b, C c) const
608 { return ::std::unique_copy(a, b, c); }
610 template <class A, class C, class D>
612 operator()(A a, A b, C c, D d) const
613 { return ::std::unique_copy(a, b, c, d); }
617 // reverse ---------------------------------
621 template <class Args>
628 operator()(A a, A b) const
629 { ::std::reverse(a, b); }
633 // reverse_copy ---------------------------------
635 struct reverse_copy {
637 template <class Args>
639 typedef typename boost::remove_const<
640 typename boost::tuples::element<3, Args>::type
644 template <class A, class C >
646 operator()(A a, A b, C c) const
647 { return ::std::reverse_copy(a, b, c); }
651 // rotate ---------------------------------
655 template <class Args>
662 operator()(A a, A b, A c) const
663 { ::std::rotate(a, b, c); }
667 // rotate_copy ---------------------------------
671 template <class Args>
673 typedef typename boost::remove_const<
674 typename boost::tuples::element<3, Args>::type
678 template <class A, class D>
680 operator()(A a, A b, A c, D d) const
681 { return ::std::rotate_copy(a, b, c, d); }
685 // random_shuffle ---------------------------------
687 struct random_shuffle {
689 template <class Args>
696 operator()(A a, A b) const
697 { ::std::random_shuffle(a, b); }
699 template <class A, class C>
701 operator()(A a, A b, const C& c) const
702 { ::std::random_shuffle(a, b, c); }
707 // partition ---------------------------------
711 template <class Args>
713 typedef typename boost::remove_const<
714 typename boost::tuples::element<1, Args>::type
718 template <class A, class C>
720 operator()(A a, A b, C c) const
721 { return ::std::partition(a, b, c); }
725 // stable_partition ---------------------------------
727 struct stable_partition {
729 template <class Args>
731 typedef typename boost::remove_const<
732 typename boost::tuples::element<1, Args>::type
736 template <class A, class C>
738 operator()(A a, A b, C c) const
739 { return ::std::stable_partition(a, b, c); }
743 // sort ---------------------------------
747 template <class Args>
754 operator()(A a, A b) const
755 { ::std::sort(a, b); }
757 template <class A, class C>
759 operator()(A a, A b, C c) const
760 { ::std::sort(a, b, c); }
764 // stable_sort ---------------------------------
768 template <class Args>
775 operator()(A a, A b) const
776 { ::std::stable_sort(a, b); }
778 template <class A, class C>
780 operator()(A a, A b, C c) const
781 { ::std::stable_sort(a, b, c); }
785 // partial_sort ---------------------------------
787 struct partial_sort {
789 template <class Args>
796 operator()(A a, A b, A c) const
797 { ::std::partial_sort(a, b, c); }
799 template <class A, class D>
801 operator()(A a, A b, A c, D d) const
802 { ::std::partial_sort(a, b, c, d); }
806 // partial_sort_copy ---------------------------------
808 struct partial_sort_copy {
810 template <class Args>
812 typedef typename boost::remove_const<
813 typename boost::tuples::element<3, Args>::type
817 template <class A, class C>
819 operator()(A a, A b, C c, C d) const
820 { return ::std::partial_sort_copy(a, b, c, d); }
822 template <class A, class C, class E >
824 operator()(A a, A b, C c, C d, E e) const
825 { return ::std::partial_sort_copy(a, b, c, d, e); }
828 // nth_element ---------------------------------
832 template <class Args>
839 operator()(A a, A b, A c) const
840 { ::std::nth_element(a, b, c); }
842 template <class A, class D>
844 operator()(A a, A b, A c, D d) const
845 { ::std::nth_element(a, b, c, d); }
849 // lower_bound ---------------------------------
853 template <class Args>
855 typedef typename boost::remove_const<
856 typename boost::tuples::element<1, Args>::type
860 template <class A, class C>
862 operator()(A a, A b, const C& c) const
863 { return ::std::lower_bound(a, b, c); }
865 template <class A, class C, class D>
867 operator()(A a, A b, const C& c, D d) const
868 { return ::std::lower_bound(a, b, c, d); }
872 // upper_bound ---------------------------------
876 template <class Args>
878 typedef typename boost::remove_const<
879 typename boost::tuples::element<1, Args>::type
883 template <class A, class C>
885 operator()(A a, A b, const C& c) const
886 { return ::std::upper_bound(a, b, c); }
888 template <class A, class C, class D>
890 operator()(A a, A b, const C& c, D d) const
891 { return ::std::upper_bound(a, b, c, d); }
895 // equal_range ---------------------------------
899 template <class Args>
901 typedef typename boost::remove_const<
902 typename boost::tuples::element<1, Args>::type
903 >::type element_type;
905 typedef ::std::pair< element_type, element_type > type;
908 template <class A, class C>
910 operator()(A a, A b, const C& c) const
911 { return ::std::equal_range(a, b, c); }
913 template <class A, class C, class D>
915 operator()(A a, A b, const C& c, D d) const
916 { return ::std::equal_range(a, b, c, d); }
920 // binary_search ---------------------------------
922 struct binary_search {
924 template <class Args>
929 template <class A, class C >
931 operator()(A a, A b, const C& c) const
932 { return ::std::binary_search(a, b, c); }
934 template <class A, class C, class D>
936 operator()(A a, A b, const C& c, D d) const
937 { return ::std::binary_search(a, b, c, d); }
941 // merge --------------------------------
945 template <class Args>
947 typedef typename boost::remove_const<
948 typename boost::tuples::element<5, Args>::type
952 template <class A, class C, class E>
954 operator()(A a, A b, C c, C d, E e) const
955 { return std::merge(a, b, c, d, e);}
957 template <class A, class C, class E, class F>
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);}
964 // inplace_merge ---------------------------------
966 struct inplace_merge {
968 template <class Args>
975 operator()(A a, A b, A c) const
976 { ::std::inplace_merge(a, b, c); }
978 template <class A, class D>
980 operator()(A a, A b, A c, D d) const
981 { ::std::inplace_merge(a, b, c, d); }
985 // includes ---------------------------------
989 template <class Args>
994 template <class A, class C>
996 operator()(A a, A b, C c, C d) const
997 { return ::std::includes(a, b, c, d); }
999 template <class A, class C, class E>
1001 operator()(A a, A b, C c, C d, E e) const
1002 { return ::std::includes(a, b, c, d, e); }
1006 // set_union --------------------------------
1010 template <class Args>
1012 typedef typename boost::remove_const<
1013 typename boost::tuples::element<5, Args>::type
1017 template <class A, class C, class E>
1019 operator()(A a, A b, C c, C d, E e) const
1020 { return std::set_union(a, b, c, d, e);}
1022 template <class A, class C, class E, class F>
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);}
1029 // set_intersection --------------------------------
1031 struct set_intersection {
1033 template <class Args>
1035 typedef typename boost::remove_const<
1036 typename boost::tuples::element<5, Args>::type
1040 template <class A, class C, class E>
1042 operator()(A a, A b, C c, C d, E e) const
1043 { return std::set_intersection(a, b, c, d, e);}
1045 template <class A, class C, class E, class F>
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);}
1052 // set_difference --------------------------------
1054 struct set_difference {
1056 template <class Args>
1058 typedef typename boost::remove_const<
1059 typename boost::tuples::element<5, Args>::type
1063 template <class A, class C, class E>
1065 operator()(A a, A b, C c, C d, E e) const
1066 { return std::set_difference(a, b, c, d, e);}
1068 template <class A, class C, class E, class F>
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);}
1076 // set_symmetric_difference --------------------------------
1078 struct set_symmetric_difference {
1080 template <class Args>
1082 typedef typename boost::remove_const<
1083 typename boost::tuples::element<5, Args>::type
1087 template <class A, class C, class 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);}
1092 template <class A, class C, class E, class F>
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);}
1099 // push_heap ---------------------------------
1103 template <class Args>
1110 operator()(A a, A b) const
1111 { ::std::push_heap(a, b); }
1113 template <class A, class C>
1115 operator()(A a, A b, C c) const
1116 { ::std::push_heap(a, b, c); }
1120 // pop_heap ---------------------------------
1124 template <class Args>
1131 operator()(A a, A b) const
1132 { ::std::pop_heap(a, b); }
1134 template <class A, class C>
1136 operator()(A a, A b, C c) const
1137 { ::std::pop_heap(a, b, c); }
1142 // make_heap ---------------------------------
1146 template <class Args>
1153 operator()(A a, A b) const
1154 { ::std::make_heap(a, b); }
1156 template <class A, class C>
1158 operator()(A a, A b, C c) const
1159 { ::std::make_heap(a, b, c); }
1163 // sort_heap ---------------------------------
1167 template <class Args>
1174 operator()(A a, A b) const
1175 { ::std::sort_heap(a, b); }
1177 template <class A, class C>
1179 operator()(A a, A b, C c) const
1180 { ::std::sort_heap(a, b, c); }
1184 // min ---------------------------------
1188 template <class Args>
1190 typedef typename boost::remove_const<
1191 typename boost::tuples::element<1, Args>::type
1197 operator()(const A& a, const A& b) const
1198 { return (::std::min)(a, b); }
1200 template <class A, class C>
1202 operator()(const A& a, const A& b, C c) const
1203 { return (::std::min)(a, b, c); }
1207 // max ---------------------------------
1211 template <class Args>
1213 typedef typename boost::remove_const<
1214 typename boost::tuples::element<1, Args>::type
1220 operator()(const A& a, const A& b) const
1221 { return (::std::max)(a, b); }
1223 template <class A, class C>
1225 operator()(const A& a, const A& b, C c) const
1226 { return (::std::max)(a, b, c); }
1230 struct min_element {
1232 template <class Args>
1234 typedef typename boost::remove_const<
1235 typename boost::tuples::element<1, Args>::type
1241 operator()(A a, A b) const
1242 { return ::std::min_element(a, b); }
1244 template <class A, class C>
1246 operator()(A a, A b, C c) const
1247 { return ::std::min_element(a, b, c); }
1251 // max_element ---------------------------------
1253 struct max_element {
1255 template <class Args>
1257 typedef typename boost::remove_const<
1258 typename boost::tuples::element<1, Args>::type
1264 operator()(A a, A b) const
1265 { return ::std::max_element(a, b); }
1267 template <class A, class C>
1269 operator()(A a, A b, C c) const
1270 { return ::std::max_element(a, b, c); }
1275 // lexicographical_compare ---------------------------------
1277 struct lexicographical_compare {
1279 template <class Args>
1284 template <class A, class C>
1286 operator()(A a, A b, C c, C d) const
1287 { return ::std::lexicographical_compare(a, b, c, d); }
1289 template <class A, class C, class E>
1291 operator()(A a, A b, C c, C d, E e) const
1292 { return ::std::lexicographical_compare(a, b, c, d, e); }
1296 // next_permutation ---------------------------------
1298 struct next_permutation {
1300 template <class Args>
1307 operator()(A a, A b) const
1308 { return ::std::next_permutation(a, b); }
1310 template <class A, class C >
1312 operator()(A a, A b, C c) const
1313 { return ::std::next_permutation(a, b, c); }
1317 // prev_permutation ---------------------------------
1319 struct prev_permutation {
1321 template <class Args>
1328 operator()(A a, A b) const
1329 { return ::std::prev_permutation(a, b); }
1331 template <class A, class C >
1333 operator()(A a, A b, C c) const
1334 { return ::std::prev_permutation(a, b, c); }
1342 } // end of ll namespace
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.
1349 #define CALL_MEMBER(X) \
1351 template <class Args> \
1353 typedef typename boost::remove_const< \
1354 typename boost::tuples::element<1, Args>::type \
1355 >::type::const_iterator type; \
1359 typename T::const_iterator \
1360 operator()(const T& t) const \
1366 // create call_begin and call_end classes
1372 } // end of lambda namespace
1373 } // end of boost namespace