stl/algorithm/querying.hpp

0001 // Copyright 2005 Daniel Wallin.
0002 // Copyright 2005 Joel de Guzman.
0003 // Copyright 2005 Dan Marsden.
0004 // Copyright 2008 Hartmut Kaiser.
0005 // Copyright 2015 John Fletcher.
0006 //
0007 // Use, modification and distribution is subject to the Boost Software
0008 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0009 // http://www.boost.org/LICENSE_1_0.txt)
0010 //
0011 // Modeled after range_ex, Copyright 2004 Eric Niebler
0012
0013 #ifndef BOOST_PHOENIX_ALGORITHM_QUERYING_HPP
0014 #define BOOST_PHOENIX_ALGORITHM_QUERYING_HPP
0015
0016 #include <algorithm>
0017
0018 #include <boost/phoenix/core/limits.hpp>
0019 #include <boost/phoenix/stl/algorithm/detail/has_find.hpp>
0020 #include <boost/phoenix/stl/algorithm/detail/has_lower_bound.hpp>
0021 #include <boost/phoenix/stl/algorithm/detail/has_upper_bound.hpp>
0022 #include <boost/phoenix/stl/algorithm/detail/has_equal_range.hpp>
0023
0024 #include <boost/phoenix/stl/algorithm/detail/begin.hpp>
0025 #include <boost/phoenix/stl/algorithm/detail/end.hpp>
0026 #include <boost/phoenix/stl/algorithm/detail/decay_array.hpp>
0027
0028 #include <boost/phoenix/function/adapt_callable.hpp>
0029
0030 //#include <boost/range/result_iterator.hpp> is deprecated
0031 #include <boost/range/iterator.hpp>
0032 #include <boost/range/difference_type.hpp>
0033
0034 namespace boost { namespace phoenix {
0035     namespace impl
0036     {
0037         struct find
0038         {
0039             template <typename Sig>
0040             struct result;
0041
0042             template <typename This, class R, class T>
0043             struct result<This(R&, T&)>
0044                 : range_iterator<R>
0045             {};
0046
0047             template<class R, class T>
0048             typename range_iterator<R>::type
0049             execute(R& r, T const& x, mpl::true_) const
0050             {
0051                 return r.find(x);
0052             }
0053
0054             template<class R, class T>
0055             typename range_iterator<R>::type
0056             execute(R& r, T const& x, mpl::false_) const
0057             {
0058                 return std::find(detail::begin_(r), detail::end_(r), x);
0059             }
0060
0061             template<class R, class T>
0062             typename range_iterator<R>::type
0063             operator()(R& r, T const& x) const
0064             {
0065                 return execute(r, x, has_find<R>());
0066             }
0067         };
0068
0069         struct find_if
0070         {
0071             template <typename Sig>
0072             struct result;
0073
0074             template <typename This, class R, class P>
0075             struct result<This(R&, P)>
0076                 : range_iterator<R>
0077             {};
0078
0079             template<class R, class P>
0080             typename range_iterator<R>::type
0081             operator()(R& r, P p) const
0082             {
0083                 return std::find_if(detail::begin_(r), detail::end_(r), p);
0084             }
0085         };
0086
0087         struct find_end
0088         {
0089             template <typename Sig>
0090             struct result;
0091
0092             template<typename This, class R, class R2>
0093             struct result<This(R&, R2&)>
0094                 : range_iterator<R>
0095             {};
0096
0097             template<typename This, class R, class R2, class P>
0098             struct result<This(R&, R2&, P)>
0099                 : range_iterator<R>
0100             {};
0101
0102             template<class R, class R2>
0103             typename range_iterator<R>::type
0104             operator()(R& r, R2& r2) const
0105             {
0106                 return std::find_end(
0107                     detail::begin_(r)
0108                     , detail::end_(r)
0109                     , detail::begin_(r2)
0110                     , detail::end_(r2)
0111                     );
0112             }
0113
0114             template<class R, class R2, class P>
0115             typename range_iterator<R>::type
0116             operator()(R& r, R2& r2, P p) const
0117             {
0118                 return std::find_end(
0119                     detail::begin_(r)
0120                     , detail::end_(r)
0121                     , detail::begin_(r2)
0122                     , detail::end_(r2)
0123                     , p
0124                     );
0125             }
0126         };
0127
0128         struct find_first_of
0129         {
0130             template <typename Sig>
0131             struct result;
0132
0133             template<typename This, class R, class R2>
0134             struct result<This(R&, R2&)>
0135                 : range_iterator<R>
0136             {};
0137
0138             template<typename This, class R, class R2, class P>
0139             struct result<This(R&, R2&, P)>
0140                 : range_iterator<R>
0141             {};
0142
0143             template<class R, class R2>
0144             typename range_iterator<R>::type
0145             operator()(R& r, R2& r2) const
0146             {
0147                 return std::find_first_of(
0148                     detail::begin_(r)
0149                     , detail::end_(r)
0150                     , detail::begin_(r2)
0151                     , detail::end_(r2)
0152                     );
0153             }
0154
0155             template<class R, class R2, class P>
0156             typename range_iterator<R>::type
0157             operator()(R& r, R2& r2, P p) const
0158             {
0159                 return std::find_first_of(
0160                     detail::begin_(r)
0161                     , detail::end_(r)
0162                     , detail::begin_(r2)
0163                     , detail::end_(r2)
0164                     , p
0165                     );
0166             }
0167         };
0168
0169         struct adjacent_find
0170         {
0171             template <typename Sig>
0172             struct result;
0173
0174             template <typename This, class R>
0175             struct result<This(R&)>
0176                 : range_iterator<R>
0177             {};
0178
0179             template <typename This, class R, class P>
0180             struct result<This(R&, P)>
0181                 : range_iterator<R>
0182             {};
0183
0184             template<class R>
0185             typename range_iterator<R>::type
0186             operator()(R& r) const
0187             {
0188                 return std::adjacent_find(detail::begin_(r), detail::end_(r));
0189             }
0190
0191             template<class R, class P>
0192             typename range_iterator<R>::type
0193             operator()(R& r, P p) const
0194             {
0195                 return std::adjacent_find(detail::begin_(r), detail::end_(r), p);
0196             }
0197         };
0198
0199         struct count
0200         {
0201             template <typename Sig>
0202             struct result;
0203
0204             template <typename This, class R, class T>
0205             struct result<This(R&, T&)>
0206                 : range_difference<R>
0207             {};
0208
0209             template<class R, class T>
0210             typename range_difference<R>::type
0211             operator()(R& r, T const& x) const
0212             {
0213                 return std::count(detail::begin_(r), detail::end_(r), x);
0214             }
0215         };
0216
0217         struct count_if
0218         {
0219             template <typename Sig>
0220             struct result;
0221
0222             template <typename This, class R, class P>
0223             struct result<This(R&, P)>
0224                 : range_difference<R>
0225             {};
0226
0227             template<class R, class P>
0228             typename range_difference<R>::type
0229             operator()(R& r, P p) const
0230             {
0231                 return std::count_if(detail::begin_(r), detail::end_(r), p);
0232             }
0233         };
0234
0235         struct distance
0236         {
0237             template <typename Sig>
0238             struct result;
0239
0240             template <typename This, class R>
0241             struct result<This(R&)>
0242                 : range_difference<R>
0243             {};
0244
0245             template<class R>
0246             typename range_difference<R>::type
0247             operator()(R& r) const
0248             {
0249                 return std::distance(detail::begin_(r), detail::end_(r));
0250             }
0251         };
0252
0253         struct equal
0254         {
0255             typedef bool result_type;
0256
0257             template<class R, class I>
0258             bool operator()(R& r, I i) const
0259             {
0260                 return std::equal(detail::begin_(r), detail::end_(r), i);
0261             }
0262
0263             template<class R, class I, class P>
0264             bool operator()(R& r, I i, P p) const
0265             {
0266                 return std::equal(detail::begin_(r), detail::end_(r), i, p);
0267             }
0268         };
0269
0270         struct search
0271         {
0272             template <typename Sig>
0273             struct result;
0274
0275             template <typename This, class R, typename R2>
0276             struct result<This(R&, R2&)>
0277                 : range_iterator<R>
0278             {};
0279
0280             template <typename This, class R, typename R2, class P>
0281             struct result<This(R&, R2&, P)>
0282                 : range_iterator<R>
0283             {};
0284
0285             template<class R, class R2>
0286             typename range_iterator<R>::type
0287             operator()(R& r, R2& r2) const
0288             {
0289                 return std::search(
0290                     detail::begin_(r)
0291                     , detail::end_(r)
0292                     , detail::begin_(r2)
0293                     , detail::end_(r2)
0294                     );
0295             }
0296
0297             template<class R, class R2, class P>
0298             typename range_iterator<R>::type
0299             operator()(R& r, R2& r2, P p) const
0300             {
0301                 return std::search(
0302                     detail::begin_(r)
0303                     , detail::end_(r)
0304                     , detail::begin_(r2)
0305                     , detail::end_(r2)
0306                     , p
0307                     );
0308             }
0309         };
0310
0311         struct lower_bound
0312         {
0313             template <typename Sig>
0314             struct result;
0315
0316             template <typename This, class R, class T>
0317             struct result<This(R&, T&)>
0318                 : range_iterator<R>
0319             {};
0320
0321             template <typename This, class R, class T, class C>
0322             struct result<This(R&, T&, C)>
0323                 : range_iterator<R>
0324             {};
0325
0326             template<class R, class T>
0327             typename range_iterator<R>::type
0328             execute(R& r, T const& val, mpl::true_) const
0329             {
0330                 return r.lower_bound(val);
0331             }
0332
0333             template<class R, class T>
0334             typename range_iterator<R>::type
0335             execute(R& r, T const& val, mpl::false_) const
0336             {
0337                 return std::lower_bound(detail::begin_(r), detail::end_(r), val);
0338             }
0339
0340             template<class R, class T>
0341             typename range_iterator<R>::type
0342             operator()(R& r, T const& val) const
0343             {
0344                 return execute(r, val, has_lower_bound<R>());
0345             }
0346
0347             template<class R, class T, class C>
0348             typename range_iterator<R>::type
0349             operator()(R& r, T const& val, C c) const
0350             {
0351                 return std::lower_bound(detail::begin_(r), detail::end_(r), val, c);
0352             }
0353         };
0354
0355         struct upper_bound
0356         {
0357             template <typename Sig>
0358             struct result;
0359
0360             template <typename This, class R, class T>
0361             struct result<This(R&, T&)>
0362                 : range_iterator<R>
0363             {};
0364
0365             template <typename This, class R, class T, class C>
0366             struct result<This(R&, T&, C)>
0367                 : range_iterator<R>
0368             {};
0369
0370             template<class R, class T>
0371             typename range_iterator<R>::type
0372             execute(R& r, T const& val, mpl::true_) const
0373             {
0374                 return r.upper_bound(val);
0375             }
0376
0377             template<class R, class T>
0378             typename range_iterator<R>::type
0379             execute(R& r, T const& val, mpl::false_) const
0380             {
0381                 return std::upper_bound(detail::begin_(r), detail::end_(r), val);
0382             }
0383
0384             template<class R, class T>
0385             typename range_iterator<R>::type
0386             operator()(R& r, T const& val) const
0387             {
0388                 return execute(r, val, has_upper_bound<R>());
0389             }
0390
0391             template<class R, class T, class C>
0392             typename range_iterator<R>::type
0393             operator()(R& r, T const& val, C c) const
0394             {
0395                 return std::upper_bound(detail::begin_(r), detail::end_(r), val, c);
0396             }
0397         };
0398
0399         namespace result_of
0400         {
0401             template <typename R, typename T, typename C = void>
0402             struct equal_range
0403             {
0404                 typedef std::pair<
0405                     typename range_iterator<R>::type
0406                     , typename range_iterator<R>::type
0407                 > type;
0408             };
0409         }
0410
0411         struct equal_range
0412         {
0413             template <typename Sig>
0414             struct result;
0415
0416             template <typename This, class R, class T>
0417             struct result<This(R&, T&)>
0418                 : result_of::equal_range<R,T>
0419             {};
0420
0421             template <typename This, class R, class T, class C>
0422             struct result<This(R&, T&, C)>
0423                 : result_of::equal_range<R,T, C>
0424             {};
0425
0426             template<class R, class T>
0427             typename result_of::equal_range<R, T>::type
0428             execute(R& r, T const& val, mpl::true_) const
0429             {
0430                 return r.equal_range(val);
0431             }
0432
0433             template<class R, class T>
0434             typename result_of::equal_range<R, T>::type
0435             execute(R& r, T const& val, mpl::false_) const
0436             {
0437                 return std::equal_range(detail::begin_(r), detail::end_(r), val);
0438             }
0439
0440             template<class R, class T>
0441             typename result_of::equal_range<R, T>::type
0442             operator()(R& r, T const& val) const
0443             {
0444                 return execute(r, val, has_equal_range<R>());
0445             }
0446
0447             template<class R, class T, class C>
0448             typename result_of::equal_range<R, T, C>::type
0449             operator()(R& r, T const& val, C c) const
0450             {
0451                 return std::equal_range(detail::begin_(r), detail::end_(r), val, c);
0452             }
0453         };
0454
0455         namespace result_of
0456         {
0457             template <typename R, typename I, typename P = void>
0458             struct mismatch
0459             {
0460                 typedef std::pair<
0461                     typename range_iterator<R>::type
0462                     , typename detail::decay_array<I>::type
0463                 > type;
0464             };
0465         }
0466
0467         struct mismatch
0468         {
0469             template <typename Sig>
0470             struct result;
0471
0472             template<typename This, class R, class I>
0473             struct result<This(R&, I)>
0474                 : result_of::mismatch<R, I>
0475             {};
0476
0477             template<typename This, class R, class I, class P>
0478             struct result<This(R&, I, P)>
0479                 : result_of::mismatch<R, I, P>
0480             {};
0481
0482             template<class R, class I>
0483             typename result_of::mismatch<R, I>::type
0484             operator()(R& r, I i) const
0485             {
0486                 return std::mismatch(detail::begin_(r), detail::end_(r), i);
0487             }
0488
0489             template<class R, class I, class P>
0490             typename result_of::mismatch<R, I, P>::type
0491             operator()(R& r, I i, P p) const
0492             {
0493                 return std::mismatch(detail::begin_(r), detail::end_(r), i, p);
0494             }
0495         };
0496
0497         struct binary_search
0498         {
0499             typedef bool result_type;
0500
0501             template<class R, class T>
0502             bool operator()(R& r, T const& val) const
0503             {
0504                 return std::binary_search(detail::begin_(r), detail::end_(r), val);
0505             }
0506
0507             template<class R, class T, class C>
0508             bool operator()(R& r, T const& val, C c) const
0509             {
0510                 return std::binary_search(detail::begin_(r), detail::end_(r), val, c);
0511             }
0512         };
0513
0514         struct includes
0515         {
0516             typedef bool result_type;
0517
0518             template<class R1, class R2>
0519             bool operator()(R1& r1, R2& r2) const
0520             {
0521                 return std::includes(
0522                     detail::begin_(r1), detail::end_(r1)
0523                     , detail::begin_(r2), detail::end_(r2)
0524                     );
0525             }
0526
0527             template<class R1, class R2, class C>
0528             bool operator()(R1& r1, R2& r2, C c) const
0529             {
0530                 return std::includes(
0531                     detail::begin_(r1), detail::end_(r1)
0532                     , detail::begin_(r2), detail::end_(r2)
0533                     , c
0534                     );
0535             }
0536         };
0537
0538         struct min_element
0539         {
0540             template <typename Sig>
0541             struct result;
0542
0543             template <typename This, class R>
0544             struct result<This(R&)>
0545                 : range_iterator<R>
0546             {};
0547
0548             template <typename This, class R, class P>
0549             struct result<This(R&, P)>
0550                 : range_iterator<R>
0551             {};
0552
0553             template<class R>
0554             typename range_iterator<R>::type
0555             operator()(R& r) const
0556             {
0557                 return std::min_element(detail::begin_(r), detail::end_(r));
0558             }
0559
0560             template<class R, class P>
0561             typename range_iterator<R>::type
0562             operator()(R& r, P p) const
0563             {
0564                 return std::min_element(detail::begin_(r), detail::end_(r), p);
0565             }
0566         };
0567
0568         struct max_element
0569         {
0570             template <typename Sig>
0571             struct result;
0572
0573             template <typename This, class R>
0574             struct result<This(R&)>
0575                 : range_iterator<R>
0576             {};
0577
0578             template <typename This, class R, class P>
0579             struct result<This(R&, P)>
0580                 : range_iterator<R>
0581             {};
0582
0583             template<class R>
0584             typename range_iterator<R>::type
0585             operator()(R& r) const
0586             {
0587                 return std::max_element(detail::begin_(r), detail::end_(r));
0588             }
0589
0590             template<class R, class P>
0591             typename range_iterator<R>::type
0592             operator()(R& r, P p) const
0593             {
0594                 return std::max_element(detail::begin_(r), detail::end_(r), p);
0595             }
0596         };
0597
0598         struct lexicographical_compare
0599         {
0600             typedef bool result_type;
0601
0602             template<class R1, class R2>
0603             bool operator()(R1& r1, R2& r2) const
0604             {
0605                 return std::lexicographical_compare(
0606                     detail::begin_(r1), detail::end_(r1)
0607                     , detail::begin_(r2), detail::end_(r2)
0608                     );
0609             }
0610
0611             template<class R1, class R2, class P>
0612             bool operator()(R1& r1, R2& r2, P p) const
0613             {
0614                 return std::lexicographical_compare(
0615                     detail::begin_(r1), detail::end_(r1)
0616                     , detail::begin_(r2), detail::end_(r2)
0617                     , p
0618                     );
0619             }
0620         };
0621
0622     }
0623
0624     BOOST_PHOENIX_ADAPT_CALLABLE(find, impl::find, 2)
0625     BOOST_PHOENIX_ADAPT_CALLABLE(find_if, impl::find_if, 2)
0626     BOOST_PHOENIX_ADAPT_CALLABLE(find_end, impl::find_end, 2)
0627     BOOST_PHOENIX_ADAPT_CALLABLE(find_end, impl::find_end, 3)
0628     BOOST_PHOENIX_ADAPT_CALLABLE(find_first_of, impl::find_first_of, 2)
0629     BOOST_PHOENIX_ADAPT_CALLABLE(find_first_of, impl::find_first_of, 3)
0630     BOOST_PHOENIX_ADAPT_CALLABLE(adjacent_find, impl::adjacent_find, 1)
0631     BOOST_PHOENIX_ADAPT_CALLABLE(adjacent_find, impl::adjacent_find, 2)
0632     BOOST_PHOENIX_ADAPT_CALLABLE(count, impl::count, 2)
0633     BOOST_PHOENIX_ADAPT_CALLABLE(count_if, impl::count_if, 2)
0634     BOOST_PHOENIX_ADAPT_CALLABLE(distance, impl::distance, 1)
0635     BOOST_PHOENIX_ADAPT_CALLABLE(equal, impl::equal, 2)
0636     BOOST_PHOENIX_ADAPT_CALLABLE(equal, impl::equal, 3)
0637     BOOST_PHOENIX_ADAPT_CALLABLE(search, impl::search, 2)
0638     BOOST_PHOENIX_ADAPT_CALLABLE(search, impl::search, 3)
0639     BOOST_PHOENIX_ADAPT_CALLABLE(lower_bound, impl::lower_bound, 2)
0640     BOOST_PHOENIX_ADAPT_CALLABLE(lower_bound, impl::lower_bound, 3)
0641     BOOST_PHOENIX_ADAPT_CALLABLE(upper_bound, impl::upper_bound, 2)
0642     BOOST_PHOENIX_ADAPT_CALLABLE(upper_bound, impl::upper_bound, 3)
0643     BOOST_PHOENIX_ADAPT_CALLABLE(equal_range, impl::equal_range, 2)
0644     BOOST_PHOENIX_ADAPT_CALLABLE(equal_range, impl::equal_range, 3)
0645     BOOST_PHOENIX_ADAPT_CALLABLE(mismatch, impl::mismatch, 2)
0646     BOOST_PHOENIX_ADAPT_CALLABLE(mismatch, impl::mismatch, 3)
0647     BOOST_PHOENIX_ADAPT_CALLABLE(binary_search, impl::binary_search, 2)
0648     BOOST_PHOENIX_ADAPT_CALLABLE(binary_search, impl::binary_search, 3)
0649     BOOST_PHOENIX_ADAPT_CALLABLE(includes, impl::includes, 2)
0650     BOOST_PHOENIX_ADAPT_CALLABLE(includes, impl::includes, 3)
0651     BOOST_PHOENIX_ADAPT_CALLABLE(min_element, impl::min_element, 1)
0652     BOOST_PHOENIX_ADAPT_CALLABLE(min_element, impl::min_element, 2)
0653     BOOST_PHOENIX_ADAPT_CALLABLE(max_element, impl::max_element, 1)
0654     BOOST_PHOENIX_ADAPT_CALLABLE(max_element, impl::max_element, 2)
0655     BOOST_PHOENIX_ADAPT_CALLABLE(lexicographical_compare, impl::lexicographical_compare, 2)
0656     BOOST_PHOENIX_ADAPT_CALLABLE(lexicographical_compare, impl::lexicographical_compare, 3)
0657
0658 }}
0659
0660 #endif