boost/lambda/algorithm.hpp

0001 // -- algorithm.hpp -- Boost Lambda Library -----------------------------------
0002 // Copyright (C) 2002 Jaakko Jarvi (jaakko.jarvi@cs.utu.fi)
0003 // Copyright (C) 2002 Gary Powell (gwpowell@hotmail.com)
0004 //
0005 // Distributed under the Boost Software License, Version 1.0. (See
0006 // accompanying file LICENSE_1_0.txt or copy at
0007 // http://www.boost.org/LICENSE_1_0.txt)
0008 //
0009 // For more information, see http://www.boost.org
0010
0011 #ifndef BOOST_LAMBDA_ALGORITHM_HPP
0012 #define BOOST_LAMBDA_ALGORITHM_HPP
0013
0014 #include "boost/lambda/core.hpp"
0015
0016 #include <algorithm>
0017 #include <iterator>  // for iterator_traits
0018 #include <utility> // for std::pair
0019
0020 namespace boost {
0021   namespace lambda {
0022
0023 namespace ll {
0024
0025 // for_each ---------------------------------
0026
0027 struct for_each {
0028
0029   template <class Args>
0030   struct sig {
0031     typedef typename boost::remove_const<
0032         typename boost::tuples::element<3, Args>::type
0033      >::type type;
0034   };
0035
0036   template <class A, class C>
0037   C
0038   operator()(A a, A b, C c) const
0039   { return ::std::for_each(a, b, c); }
0040 };
0041
0042 // find  ---------------------------------
0043
0044 struct find {
0045
0046   template <class Args>
0047   struct sig {
0048     typedef typename boost::remove_const<
0049         typename boost::tuples::element<1, Args>::type
0050      >::type type;
0051   };
0052
0053   template <class A, class C>
0054   A
0055   operator()(A a, A b, const C& c) const
0056   { return ::std::find(a, b, c); }
0057 };
0058
0059
0060 // find_if  ---------------------------------
0061
0062 struct find_if {
0063
0064   template <class Args>
0065   struct sig {
0066     typedef typename boost::remove_const<
0067         typename boost::tuples::element<1, Args>::type
0068      >::type type;
0069   };
0070
0071   template <class A, class C>
0072   A
0073   operator()(A a, A b, C c) const
0074   { return ::std::find_if(a, b, c); }
0075 };
0076
0077 // find_end  ---------------------------------
0078
0079 struct find_end {
0080
0081   template <class Args>
0082   struct sig {
0083     typedef typename boost::remove_const<
0084         typename boost::tuples::element<1, Args>::type
0085      >::type type;
0086   };
0087
0088   template <class A, class C>
0089   A
0090   operator()(A a, A b, C c, C d) const
0091   { return ::std::find_end(a, b, c, d); }
0092
0093   template <class A, class C, class E>
0094   A
0095   operator()(A a, A b, C c, C d, E e) const
0096   { return ::std::find_end(a, b, c, d, e); }
0097
0098 };
0099
0100 // find_first_of  ---------------------------------
0101
0102 struct find_first_of {
0103
0104   template <class Args>
0105   struct sig {
0106     typedef typename boost::remove_const<
0107         typename boost::tuples::element<1, Args>::type
0108      >::type type;
0109   };
0110
0111   template <class A, class C>
0112   A
0113   operator()(A a, A b, C c, C d) const
0114   { return ::std::find_first_of(a, b, c, d); }
0115
0116   template <class A, class C, class E>
0117   A
0118   operator()(A a, A b, C c, C d, E e) const
0119   { return ::std::find_first_of(a, b, c, d, e); }
0120
0121 };
0122
0123 // adjacent_find  ---------------------------------
0124
0125 struct adjacent_find {
0126
0127   template <class Args>
0128   struct sig {
0129     typedef typename boost::remove_const<
0130         typename boost::tuples::element<1, Args>::type
0131      >::type type;
0132   };
0133
0134   template <class A>
0135   A
0136   operator()(A a, A b) const
0137   { return ::std::adjacent_find(a, b); }
0138
0139   template <class A, class C>
0140   A
0141   operator()(A a, A b, C c) const
0142   { return ::std::adjacent_find(a, b, c); }
0143
0144 };
0145
0146 // count  ---------------------------------
0147
0148 struct count {
0149
0150   template <class Args>
0151   struct sig {
0152     typedef typename ::std::iterator_traits<
0153       typename boost::remove_const<
0154            typename boost::tuples::element<1, Args>::type
0155       >::type
0156     >::difference_type type;
0157   };
0158
0159   template <class A, class C >
0160   typename ::std::iterator_traits<A>::difference_type
0161   operator()(A a, A b, const C& c) const
0162   { return ::std::count(a, b, c); }
0163 };
0164
0165 // count_if  ---------------------------------
0166
0167 struct count_if {
0168
0169   template <class Args>
0170   struct sig {
0171     typedef typename ::std::iterator_traits<
0172      typename boost::remove_const<
0173            typename boost::tuples::element<1, Args>::type
0174        >::type
0175     >::difference_type type;
0176   };
0177
0178   template <class A, class C >
0179   typename ::std::iterator_traits<A>::difference_type
0180   operator()(A a, A b, C c) const
0181   { return ::std::count_if(a, b, c); }
0182 };
0183
0184
0185 // mismatch  ---------------------------------
0186
0187 struct mismatch {
0188
0189   template <class Args>
0190   struct sig {
0191     typedef typename boost::remove_const<
0192         typename boost::tuples::element<1, Args>::type
0193      >::type element1_type;
0194
0195     typedef typename boost::remove_const<
0196         typename boost::tuples::element<3, Args>::type
0197      >::type element2_type;
0198
0199     typedef ::std::pair< element1_type, element2_type > type;
0200    };
0201
0202   template <class A, class C >
0203   ::std::pair<A,C>
0204   operator()(A a, A b, C c) const
0205   { return ::std::mismatch(a, b, c); }
0206
0207   template <class A, class C, class D>
0208   ::std::pair<A,C>
0209   operator()(A a, A b, C c, D d) const
0210   { return ::std::mismatch(a, b, c, d); }
0211
0212 };
0213
0214 // equal  ---------------------------------
0215
0216 struct equal {
0217
0218   template <class Args>
0219   struct sig {
0220     typedef bool type;
0221   };
0222
0223   template <class A, class C >
0224   bool
0225   operator()(A a, A b, C c) const
0226   { return ::std::equal(a, b, c); }
0227
0228   template <class A, class C, class D>
0229   bool
0230   operator()(A a, A b, C c, D d) const
0231   { return ::std::equal(a, b, c, d); }
0232
0233 };
0234
0235 // search --------------------------------
0236
0237 struct search {
0238
0239   template <class Args>
0240   struct sig {
0241     typedef typename boost::remove_const<
0242         typename boost::tuples::element<1, Args>::type
0243      >::type type;
0244   };
0245
0246   template <class A, class C>
0247   A
0248   operator()(A a, A b, C c, C d) const
0249   { return std::search(a, b, c, d);}
0250
0251   template <class A, class C, class E>
0252   A
0253   operator()(A a, A b, C c, C d, E e) const
0254   { return std::search(a, b, c, d, e);}
0255
0256 };
0257
0258 // copy  ---------------------------------
0259
0260 struct copy {
0261
0262   template <class Args>
0263   struct sig {
0264     typedef typename boost::remove_const<
0265         typename boost::tuples::element<3, Args>::type
0266      >::type type;
0267   };
0268
0269   template <class A, class C>
0270   C
0271   operator()(A a, A b, C c) const
0272   { return ::std::copy(a, b, c); }
0273
0274 };
0275
0276 // copy_backward  ---------------------------------
0277
0278 struct copy_backward {
0279
0280   template <class Args>
0281   struct sig {
0282     typedef typename boost::remove_const<
0283         typename boost::tuples::element<3, Args>::type
0284      >::type type;
0285   };
0286
0287   template <class A, class C>
0288   C
0289   operator()(A a, A b, C c) const
0290   { return ::std::copy_backward(a, b, c); }
0291
0292 };
0293
0294 // swap  ---------------------------------
0295
0296 struct swap {
0297
0298   template <class Args>
0299   struct sig {
0300     typedef void type;
0301   };
0302
0303   template <class A>
0304   void
0305   operator()(A a, A b) const
0306   { ::std::swap(a, b); }
0307
0308 };
0309
0310 // swap_ranges  ---------------------------------
0311
0312 struct swap_ranges {
0313
0314   template <class Args>
0315   struct sig {
0316     typedef typename boost::remove_const<
0317         typename boost::tuples::element<3, Args>::type
0318      >::type type;
0319   };
0320
0321   template <class A, class C>
0322   C
0323   operator()(A a, A b, C c) const
0324   { return ::std::swap_ranges(a, b, c); }
0325
0326 };
0327
0328 // iter_swap  ---------------------------------
0329
0330 struct iter_swap {
0331
0332   template <class Args>
0333   struct sig {
0334      typedef void type;
0335   };
0336
0337   template <class A>
0338   void
0339   operator()(A a, A b) const
0340   { ::std::iter_swap(a, b); }
0341
0342 };
0343
0344
0345 // transform --------------------------------
0346
0347 struct transform {
0348
0349   template <class Args>
0350   struct sig {
0351     typedef typename boost::remove_const<
0352         typename boost::tuples::element<
0353           boost::tuples::length<Args>::value - 2,
0354           Args
0355       >::type
0356      >::type type;
0357   };
0358
0359   template <class A, class C, class D>
0360   C
0361   operator()(A a, A b, C c, D d) const
0362   { return std::transform(a, b, c, d);}
0363
0364   template <class A, class C, class D, class E>
0365   D
0366   operator()(A a, A b, C c, D d, E e) const
0367   { return std::transform(a, b, c, d, e);}
0368
0369 };
0370
0371 // replace  ---------------------------------
0372
0373 struct replace {
0374
0375   template <class Args>
0376   struct sig {
0377     typedef void type;
0378   };
0379
0380   template <class A, class C>
0381   void
0382   operator()(A a, A b, const C& c, const C& d) const
0383   { ::std::replace(a, b, c, d); }
0384
0385 };
0386
0387 // replace_if  ---------------------------------
0388
0389 struct replace_if {
0390
0391   template <class Args>
0392   struct sig {
0393     typedef void type;
0394   };
0395
0396   template <class A, class C, class D>
0397   void
0398   operator()(A a, A b, C c, const D& d) const
0399   { ::std::replace_if(a, b, c, d); }
0400
0401 };
0402
0403 // replace_copy  ---------------------------------
0404
0405 struct replace_copy {
0406
0407  template <class Args>
0408   struct sig {
0409     typedef typename boost::remove_const<
0410         typename boost::tuples::element<3, Args>::type
0411      >::type type;
0412   };
0413
0414   template <class A, class C, class D>
0415   C
0416   operator()(A a, A b, C c, const D& d, const D& e) const
0417   { return ::std::replace_copy(a, b, c, d, e); }
0418
0419 };
0420
0421 // replace_copy_if  ---------------------------------
0422
0423 struct replace_copy_if {
0424
0425  template <class Args>
0426   struct sig {
0427     typedef typename boost::remove_const<
0428         typename boost::tuples::element<3, Args>::type
0429      >::type type;
0430   };
0431
0432   template <class A, class C, class D, class E>
0433   C
0434   operator()(A a, A b, C c, D d, const E& e) const
0435   { return ::std::replace_copy_if(a, b, c, d, e); }
0436
0437 };
0438
0439 // fill  ---------------------------------
0440
0441 struct fill {
0442
0443   template <class Args>
0444   struct sig {
0445      typedef void type;
0446   };
0447
0448   template <class A, class C>
0449   void
0450   operator()(A a, A b, const C& c) const
0451   { ::std::fill(a, b, c); }
0452
0453 };
0454
0455 // fill_n  ---------------------------------
0456
0457 struct fill_n {
0458
0459   template <class Args>
0460   struct sig {
0461      typedef void type;
0462   };
0463
0464   template <class A, class B, class C>
0465   void
0466   operator()(A a, B b, const C& c) const
0467   { ::std::fill_n(a, b, c); }
0468
0469 };
0470
0471 // generate  ---------------------------------
0472
0473 struct generate {
0474
0475   template <class Args>
0476   struct sig {
0477      typedef void type;
0478   };
0479
0480   template <class A, class C>
0481   void
0482   operator()(A a, A b, C c) const
0483   { ::std::generate(a, b, c); }
0484
0485 };
0486
0487 // generate_n  ---------------------------------
0488
0489 struct generate_n {
0490
0491   template <class Args>
0492   struct sig {
0493      typedef void type;
0494   };
0495
0496   template <class A, class B, class C>
0497   void
0498   operator()(A a, B b, C c) const
0499   { ::std::generate_n(a, b, c); }
0500
0501 };
0502
0503 // remove  ---------------------------------
0504
0505 struct remove {
0506
0507   template <class Args>
0508   struct sig {
0509     typedef typename boost::remove_const<
0510         typename boost::tuples::element<1, Args>::type
0511      >::type type;
0512   };
0513
0514   template <class A, class C >
0515   A
0516   operator()(A a, A b, const C& c) const
0517   { return ::std::remove(a, b, c); }
0518 };
0519
0520 // remove_if  ---------------------------------
0521
0522 struct remove_if {
0523
0524   template <class Args>
0525   struct sig {
0526     typedef typename boost::remove_const<
0527        typename boost::tuples::element<1, Args>::type
0528      >::type type;
0529   };
0530
0531   template <class A, class C >
0532   A
0533   operator()(A a, A b, C c) const
0534   { return ::std::remove_if(a, b, c); }
0535 };
0536
0537 // remove_copy  ---------------------------------
0538
0539 struct remove_copy {
0540
0541   template <class Args>
0542   struct sig {
0543     typedef typename boost::remove_const<
0544        typename boost::tuples::element<3, Args>::type
0545      >::type type;
0546   };
0547
0548   template <class A, class C, class D >
0549   C
0550   operator()(A a, A b, C c, const D& d) const
0551   { return ::std::remove_copy(a, b, c, d); }
0552 };
0553
0554 // remove_copy_if  ---------------------------------
0555
0556 struct remove_copy_if {
0557
0558   template <class Args>
0559   struct sig {
0560     typedef typename boost::remove_const<
0561        typename boost::tuples::element<3, Args>::type
0562      >::type type;
0563   };
0564
0565   template <class A, class C, class D >
0566   C
0567   operator()(A a, A b, C c, D d) const
0568   { return ::std::remove_copy_if(a, b, c, d); }
0569 };
0570
0571 // unique  ---------------------------------
0572
0573 struct unique {
0574
0575   template <class Args>
0576   struct sig {
0577     typedef typename boost::remove_const<
0578         typename boost::tuples::element<1, Args>::type
0579      >::type type;
0580   };
0581
0582   template <class A>
0583   A
0584   operator()(A a, A b) const
0585   { return ::std::unique(a, b); }
0586
0587   template <class A, class C>
0588   A
0589   operator()(A a, A b, C c) const
0590   { return ::std::unique(a, b, c); }
0591
0592 };
0593
0594 // unique_copy  ---------------------------------
0595
0596 struct unique_copy {
0597
0598   template <class Args>
0599   struct sig {
0600     typedef typename boost::remove_const<
0601         typename boost::tuples::element<3, Args>::type
0602      >::type type;
0603   };
0604
0605   template <class A, class C >
0606   C
0607   operator()(A a, A b, C c) const
0608   { return ::std::unique_copy(a, b, c); }
0609
0610   template <class A, class C, class D>
0611   C
0612   operator()(A a, A b, C c, D d) const
0613   { return ::std::unique_copy(a, b, c, d); }
0614
0615 };
0616
0617 // reverse  ---------------------------------
0618
0619 struct reverse {
0620
0621   template <class Args>
0622   struct sig {
0623     typedef void type;
0624   };
0625
0626   template <class A>
0627   void
0628   operator()(A a, A b) const
0629   { ::std::reverse(a, b); }
0630
0631 };
0632
0633 // reverse_copy  ---------------------------------
0634
0635 struct reverse_copy {
0636
0637   template <class Args>
0638   struct sig {
0639     typedef typename boost::remove_const<
0640         typename boost::tuples::element<3, Args>::type
0641      >::type type;
0642   };
0643
0644   template <class A, class C >
0645   C
0646   operator()(A a, A b, C c) const
0647   { return ::std::reverse_copy(a, b, c); }
0648
0649 };
0650
0651 // rotate  ---------------------------------
0652
0653 struct rotate {
0654
0655   template <class Args>
0656   struct sig {
0657     typedef void type;
0658   };
0659
0660   template <class A>
0661   void
0662   operator()(A a, A b, A c) const
0663   { ::std::rotate(a, b, c); }
0664
0665 };
0666
0667 // rotate_copy  ---------------------------------
0668
0669 struct rotate_copy {
0670
0671   template <class Args>
0672   struct sig {
0673     typedef typename boost::remove_const<
0674         typename boost::tuples::element<3, Args>::type
0675      >::type type;
0676   };
0677
0678   template <class A, class D>
0679   D
0680   operator()(A a, A b, A c, D d) const
0681   { return ::std::rotate_copy(a, b, c, d); }
0682
0683 };
0684
0685 // random_shuffle  ---------------------------------
0686
0687 #ifndef BOOST_NO_CXX98_RANDOM_SHUFFLE
0688
0689 struct random_shuffle {
0690
0691   template <class Args>
0692   struct sig {
0693     typedef void type;
0694   };
0695
0696   template <class A>
0697   void
0698   operator()(A a, A b) const
0699   { ::std::random_shuffle(a, b); }
0700
0701   template <class A, class C>
0702   void
0703   operator()(A a, A b, const C& c) const
0704   { ::std::random_shuffle(a, b, c); }
0705
0706 };
0707
0708 #endif
0709
0710 // partition  ---------------------------------
0711
0712 struct partition {
0713
0714   template <class Args>
0715   struct sig {
0716     typedef typename boost::remove_const<
0717         typename boost::tuples::element<1, Args>::type
0718      >::type type;
0719   };
0720
0721   template <class A, class C>
0722   A
0723   operator()(A a, A b, C c) const
0724   { return ::std::partition(a, b, c); }
0725
0726 };
0727
0728 // stable_partition  ---------------------------------
0729
0730 struct stable_partition {
0731
0732   template <class Args>
0733   struct sig {
0734     typedef typename boost::remove_const<
0735         typename boost::tuples::element<1, Args>::type
0736      >::type type;
0737   };
0738
0739   template <class A, class C>
0740   A
0741   operator()(A a, A b, C c) const
0742   { return ::std::stable_partition(a, b, c); }
0743
0744 };
0745
0746 // sort  ---------------------------------
0747
0748 struct sort {
0749
0750   template <class Args>
0751   struct sig {
0752      typedef void type;
0753   };
0754
0755   template <class A>
0756   void
0757   operator()(A a, A b) const
0758   { ::std::sort(a, b); }
0759
0760   template <class A, class C>
0761   void
0762   operator()(A a, A b, C c) const
0763   { ::std::sort(a, b, c); }
0764
0765 };
0766
0767 // stable_sort  ---------------------------------
0768
0769 struct stable_sort {
0770
0771   template <class Args>
0772   struct sig {
0773      typedef void type;
0774   };
0775
0776   template <class A>
0777   void
0778   operator()(A a, A b) const
0779   { ::std::stable_sort(a, b); }
0780
0781   template <class A, class C>
0782   void
0783   operator()(A a, A b, C c) const
0784   { ::std::stable_sort(a, b, c); }
0785
0786 };
0787
0788 // partial_sort  ---------------------------------
0789
0790 struct partial_sort {
0791
0792   template <class Args>
0793   struct sig {
0794      typedef void type;
0795   };
0796
0797   template <class A>
0798   void
0799   operator()(A a, A b, A c) const
0800   { ::std::partial_sort(a, b, c); }
0801
0802   template <class A, class D>
0803   void
0804   operator()(A a, A b, A c, D d) const
0805   { ::std::partial_sort(a, b, c, d); }
0806
0807 };
0808
0809 // partial_sort_copy  ---------------------------------
0810
0811 struct partial_sort_copy {
0812
0813   template <class Args>
0814   struct sig {
0815     typedef typename boost::remove_const<
0816        typename boost::tuples::element<3, Args>::type
0817      >::type type;
0818   };
0819
0820   template <class A, class C>
0821   C
0822   operator()(A a, A b, C c, C d) const
0823   { return ::std::partial_sort_copy(a, b, c, d); }
0824
0825   template <class A, class C, class E >
0826   C
0827   operator()(A a, A b, C c, C d, E e) const
0828   { return ::std::partial_sort_copy(a, b, c, d, e); }
0829 };
0830
0831 // nth_element  ---------------------------------
0832
0833 struct nth_element {
0834
0835   template <class Args>
0836   struct sig {
0837      typedef void type;
0838   };
0839
0840   template <class A>
0841   void
0842   operator()(A a, A b, A c) const
0843   { ::std::nth_element(a, b, c); }
0844
0845   template <class A, class D>
0846   void
0847   operator()(A a, A b, A c, D d) const
0848   { ::std::nth_element(a, b, c, d); }
0849
0850 };
0851
0852 // lower_bound  ---------------------------------
0853
0854 struct lower_bound {
0855
0856   template <class Args>
0857   struct sig {
0858     typedef typename boost::remove_const<
0859         typename boost::tuples::element<1, Args>::type
0860      >::type type;
0861   };
0862
0863   template <class A, class C>
0864   A
0865   operator()(A a, A b, const C& c) const
0866   { return ::std::lower_bound(a, b, c); }
0867
0868   template <class A, class C, class D>
0869   A
0870   operator()(A a, A b, const C& c, D d) const
0871   { return ::std::lower_bound(a, b, c, d); }
0872
0873 };
0874
0875 // upper_bound  ---------------------------------
0876
0877 struct upper_bound {
0878
0879   template <class Args>
0880   struct sig {
0881     typedef typename boost::remove_const<
0882         typename boost::tuples::element<1, Args>::type
0883      >::type type;
0884   };
0885
0886   template <class A, class C>
0887   A
0888   operator()(A a, A b, const C& c) const
0889   { return ::std::upper_bound(a, b, c); }
0890
0891   template <class A, class C, class D>
0892   A
0893   operator()(A a, A b, const C& c, D d) const
0894   { return ::std::upper_bound(a, b, c, d); }
0895
0896 };
0897
0898 // equal_range  ---------------------------------
0899
0900 struct equal_range {
0901
0902  template <class Args>
0903   struct sig {
0904     typedef typename boost::remove_const<
0905         typename boost::tuples::element<1, Args>::type
0906      >::type element_type;
0907
0908     typedef ::std::pair< element_type, element_type > type;
0909    };
0910
0911   template <class A, class C>
0912   ::std::pair<A,A>
0913   operator()(A a, A b, const C& c) const
0914   { return ::std::equal_range(a, b, c); }
0915
0916   template <class A, class C, class D>
0917   ::std::pair<A,A>
0918   operator()(A a, A b, const C& c, D d) const
0919   { return ::std::equal_range(a, b, c, d); }
0920
0921 };
0922
0923 // binary_search  ---------------------------------
0924
0925 struct binary_search {
0926
0927   template <class Args>
0928   struct sig {
0929     typedef bool type;
0930   };
0931
0932   template <class A, class C >
0933   bool
0934   operator()(A a, A b, const C& c) const
0935   { return ::std::binary_search(a, b, c); }
0936
0937   template <class A, class C, class D>
0938   bool
0939   operator()(A a, A b, const C& c, D d) const
0940   { return ::std::binary_search(a, b, c, d); }
0941
0942 };
0943
0944 // merge --------------------------------
0945
0946 struct merge {
0947
0948   template <class Args>
0949   struct sig {
0950     typedef typename boost::remove_const<
0951         typename boost::tuples::element<5, Args>::type
0952      >::type type;
0953   };
0954
0955   template <class A, class C, class E>
0956   E
0957   operator()(A a, A b, C c, C d, E e) const
0958   { return std::merge(a, b, c, d, e);}
0959
0960   template <class A, class C, class E, class F>
0961   E
0962   operator()(A a, A b, C c, C d, E e, F f) const
0963   { return std::merge(a, b, c, d, e, f);}
0964
0965 };
0966
0967 // inplace_merge  ---------------------------------
0968
0969 struct inplace_merge {
0970
0971   template <class Args>
0972   struct sig {
0973     typedef void type;
0974   };
0975
0976   template <class A>
0977   void
0978   operator()(A a, A b, A c) const
0979   { ::std::inplace_merge(a, b, c); }
0980
0981   template <class A, class D>
0982   void
0983   operator()(A a, A b, A c, D d) const
0984   { ::std::inplace_merge(a, b, c, d); }
0985
0986 };
0987
0988 // includes  ---------------------------------
0989
0990 struct includes {
0991
0992   template <class Args>
0993   struct sig {
0994     typedef bool type;
0995   };
0996
0997   template <class A, class C>
0998   bool
0999   operator()(A a, A b, C c, C d) const
1000   { return ::std::includes(a, b, c, d); }
1001
1002   template <class A, class C, class E>
1003   bool
1004   operator()(A a, A b, C c, C d, E e) const
1005   { return ::std::includes(a, b, c, d, e); }
1006
1007 };
1008
1009 // set_union --------------------------------
1010
1011 struct set_union {
1012
1013   template <class Args>
1014   struct sig {
1015     typedef typename boost::remove_const<
1016         typename boost::tuples::element<5, Args>::type
1017      >::type type;
1018   };
1019
1020   template <class A, class C, class E>
1021   E
1022   operator()(A a, A b, C c, C d, E e) const
1023   { return std::set_union(a, b, c, d, e);}
1024
1025   template <class A, class C, class E, class F>
1026   E
1027   operator()(A a, A b, C c, C d, E e, F f) const
1028   { return std::set_union(a, b, c, d, e, f);}
1029
1030 };
1031
1032 // set_intersection --------------------------------
1033
1034 struct set_intersection {
1035
1036   template <class Args>
1037   struct sig {
1038     typedef typename boost::remove_const<
1039         typename boost::tuples::element<5, Args>::type
1040      >::type type;
1041   };
1042
1043   template <class A, class C, class E>
1044   E
1045   operator()(A a, A b, C c, C d, E e) const
1046   { return std::set_intersection(a, b, c, d, e);}
1047
1048   template <class A, class C, class E, class F>
1049   E
1050   operator()(A a,  A b, C c, C d, E e, F f) const
1051   { return std::set_intersection(a, b, c, d, e, f);}
1052
1053 };
1054
1055 // set_difference --------------------------------
1056
1057 struct set_difference {
1058
1059   template <class Args>
1060   struct sig {
1061     typedef typename boost::remove_const<
1062         typename boost::tuples::element<5, Args>::type
1063      >::type type;
1064   };
1065
1066   template <class A, class C, class E>
1067   E
1068   operator()(A a, A b, C c, C d, E e) const
1069   { return std::set_difference(a, b, c, d, e);}
1070
1071   template <class A, class C, class E, class F>
1072   E
1073   operator()(A a, A b, C c, C d, E e, F f) const
1074   { return std::set_difference(a, b, c, d, e, f);}
1075
1076 };
1077
1078
1079 // set_symmetric_difference --------------------------------
1080
1081 struct set_symmetric_difference {
1082
1083   template <class Args>
1084   struct sig {
1085     typedef typename boost::remove_const<
1086         typename boost::tuples::element<5, Args>::type
1087      >::type type;
1088   };
1089
1090   template <class A, class C, class E>
1091   E
1092   operator()(A a, A b, C c, C d, E e) const
1093   { return std::set_symmetric_difference(a, b, c, d, e);}
1094
1095   template <class A, class C, class E, class F>
1096   E
1097   operator()(A a, A b, C c, C d, E e, F f) const
1098   { return std::set_symmetric_difference(a, b, c, d, e, f);}
1099
1100 };
1101
1102 // push_heap  ---------------------------------
1103
1104 struct push_heap {
1105
1106   template <class Args>
1107   struct sig {
1108     typedef void type;
1109   };
1110
1111   template <class A>
1112   void
1113   operator()(A a, A b) const
1114   { ::std::push_heap(a, b); }
1115
1116   template <class A, class C>
1117   void
1118   operator()(A a, A b, C c) const
1119   { ::std::push_heap(a, b, c); }
1120
1121 };
1122
1123 // pop_heap  ---------------------------------
1124
1125 struct pop_heap {
1126
1127   template <class Args>
1128   struct sig {
1129     typedef void type;
1130   };
1131
1132   template <class A>
1133   void
1134   operator()(A a, A b) const
1135   { ::std::pop_heap(a, b); }
1136
1137   template <class A, class C>
1138   void
1139   operator()(A a, A b, C c) const
1140   { ::std::pop_heap(a, b, c); }
1141
1142 };
1143
1144
1145 // make_heap  ---------------------------------
1146
1147 struct make_heap {
1148
1149   template <class Args>
1150   struct sig {
1151     typedef void type;
1152   };
1153
1154   template <class A>
1155   void
1156   operator()(A a, A b) const
1157   { ::std::make_heap(a, b); }
1158
1159   template <class A, class C>
1160   void
1161   operator()(A a, A b, C c) const
1162   { ::std::make_heap(a, b, c); }
1163
1164 };
1165
1166 // sort_heap  ---------------------------------
1167
1168 struct sort_heap {
1169
1170   template <class Args>
1171   struct sig {
1172     typedef void type;
1173   };
1174
1175   template <class A>
1176   void
1177   operator()(A a, A b) const
1178   { ::std::sort_heap(a, b); }
1179
1180   template <class A, class C>
1181   void
1182   operator()(A a, A b, C c) const
1183   { ::std::sort_heap(a, b, c); }
1184
1185 };
1186
1187 // min  ---------------------------------
1188
1189 struct min {
1190
1191   template <class Args>
1192   struct sig {
1193     typedef typename boost::remove_const<
1194         typename boost::tuples::element<1, Args>::type
1195      >::type type;
1196   };
1197
1198   template <class A>
1199   A
1200   operator()(const A& a, const A& b) const
1201   { return (::std::min)(a, b); }
1202
1203   template <class A, class C>
1204   A
1205   operator()(const A& a, const A& b, C c) const
1206   { return (::std::min)(a, b, c); }
1207
1208 };
1209
1210 // max  ---------------------------------
1211
1212 struct max {
1213
1214   template <class Args>
1215   struct sig {
1216     typedef typename boost::remove_const<
1217         typename boost::tuples::element<1, Args>::type
1218      >::type type;
1219   };
1220
1221   template <class A>
1222   A
1223   operator()(const A& a, const A& b) const
1224   { return (::std::max)(a, b); }
1225
1226   template <class A, class C>
1227   A
1228   operator()(const A& a, const A& b, C c) const
1229   { return (::std::max)(a, b, c); }
1230
1231 };
1232
1233 struct min_element {
1234
1235   template <class Args>
1236   struct sig {
1237     typedef typename boost::remove_const<
1238         typename boost::tuples::element<1, Args>::type
1239      >::type type;
1240   };
1241
1242   template <class A>
1243   A
1244   operator()(A a, A b) const
1245   { return ::std::min_element(a, b); }
1246
1247   template <class A, class C>
1248   A
1249   operator()(A a, A b, C c) const
1250   { return ::std::min_element(a, b, c); }
1251
1252 };
1253
1254 // max_element  ---------------------------------
1255
1256 struct max_element {
1257
1258   template <class Args>
1259   struct sig {
1260     typedef typename boost::remove_const<
1261         typename boost::tuples::element<1, Args>::type
1262      >::type type;
1263   };
1264
1265   template <class A>
1266   A
1267   operator()(A a, A b) const
1268   { return ::std::max_element(a, b); }
1269
1270   template <class A, class C>
1271   A
1272   operator()(A a, A b, C c) const
1273   { return ::std::max_element(a, b, c); }
1274
1275 };
1276
1277
1278 // lexicographical_compare  ---------------------------------
1279
1280 struct lexicographical_compare {
1281
1282   template <class Args>
1283   struct sig {
1284     typedef bool type;
1285   };
1286
1287   template <class A, class C>
1288   bool
1289   operator()(A a, A b, C c, C d) const
1290   { return ::std::lexicographical_compare(a, b, c, d); }
1291
1292   template <class A, class C, class E>
1293   bool
1294   operator()(A a, A b, C c, C d, E e) const
1295   { return ::std::lexicographical_compare(a, b, c, d, e); }
1296
1297 };
1298
1299 // next_permutation  ---------------------------------
1300
1301 struct next_permutation {
1302
1303   template <class Args>
1304   struct sig {
1305     typedef bool type;
1306   };
1307
1308   template <class A>
1309   bool
1310   operator()(A a, A b) const
1311   { return ::std::next_permutation(a, b); }
1312
1313   template <class A, class C >
1314   bool
1315   operator()(A a, A b, C c) const
1316   { return ::std::next_permutation(a, b, c); }
1317
1318 };
1319
1320 // prev_permutation  ---------------------------------
1321
1322 struct prev_permutation {
1323
1324   template <class Args>
1325   struct sig {
1326     typedef bool type;
1327   };
1328
1329   template <class A>
1330   bool
1331   operator()(A a, A b) const
1332   { return ::std::prev_permutation(a, b); }
1333
1334   template <class A, class C >
1335   bool
1336   operator()(A a, A b, C c) const
1337   { return ::std::prev_permutation(a, b, c); }
1338
1339 };
1340
1341
1342
1343
1344
1345 } // end of ll namespace
1346
1347 // There is no good way to call an overloaded member function in a
1348 // lambda expression.
1349 // The macro below defines a function object class for calling a
1350 // const_iterator returning member function of a container.
1351
1352 #define CALL_MEMBER(X)                                     \
1353 struct call_##X {                                          \
1354 template <class Args>                                      \
1355   struct sig {                                             \
1356     typedef typename boost::remove_const<                  \
1357         typename boost::tuples::element<1, Args>::type     \
1358      >::type::const_iterator type;                         \
1359   };                                                       \
1360                                                            \
1361   template<class T>                                        \
1362   typename T::const_iterator                               \
1363   operator()(const T& t) const                             \
1364   {                                                        \
1365     return t.X();                                          \
1366   }                                                        \
1367 };
1368
1369 // create call_begin and call_end classes
1370 CALL_MEMBER(begin)
1371 CALL_MEMBER(end)
1372
1373 #undef CALL_MEMBER
1374
1375 } // end of lambda namespace
1376 } // end of boost namespace
1377
1378
1379
1380 #endif