detail/text/algorithm.hpp

0001 // Copyright (C) 2020 T. Zachary Laine
0002 //
0003 // Distributed under the Boost Software License, Version 1.0. (See
0004 // accompanying file LICENSE_1_0.txt or copy at
0005 // http://www.boost.org/LICENSE_1_0.txt)
0006 #ifndef BOOST_PARSER_DETAIL_TEXT_ALGORITHM_HPP
0007 #define BOOST_PARSER_DETAIL_TEXT_ALGORITHM_HPP
0008
0009 #include <boost/parser/detail/text/config.hpp>
0010 #include <boost/parser/detail/text/detail/algorithm.hpp>
0011 #include <boost/parser/detail/text/detail/sentinel_tag.hpp>
0012
0013 #include <boost/parser/detail/stl_interfaces/view_interface.hpp>
0014
0015 #include <cstddef>
0016 #include <iterator>
0017 #include <utility>
0018
0019
0020 namespace boost::parser::detail { namespace text {
0021
0022     namespace detail {
0023         template<typename Iter>
0024         std::ptrdiff_t distance(Iter first, Iter last, non_sentinel_tag)
0025         {
0026             return std::distance(first, last);
0027         }
0028
0029         template<typename Iter, typename Sentinel>
0030         std::ptrdiff_t distance(Iter first, Sentinel last, sentinel_tag)
0031         {
0032             std::ptrdiff_t retval = 0;
0033             while (first != last) {
0034                 ++retval;
0035                 ++first;
0036             }
0037             return retval;
0038         }
0039     }
0040
0041     /** Range-friendly version of `std::distance()`, taking an iterator and a
0042         sentinel. */
0043     template<typename Iter, typename Sentinel>
0044     std::ptrdiff_t distance(Iter first, Sentinel last)
0045     {
0046         return detail::distance(
0047             first,
0048             last,
0049             typename std::conditional<
0050                 std::is_same<Iter, Sentinel>::value,
0051                 detail::non_sentinel_tag,
0052                 detail::sentinel_tag>::type());
0053     }
0054
0055     /** Range-friendly version of `std::find()`, taking an iterator and a
0056         sentinel. */
0057     template<typename BidiIter, typename Sentinel, typename T>
0058     BidiIter find(BidiIter first, Sentinel last, T const & x)
0059     {
0060         while (first != last) {
0061             if (*first == x)
0062                 return first;
0063             ++first;
0064         }
0065         return first;
0066     }
0067
0068     /** A range-friendly compliment to `std::find()`; returns an iterator to
0069         the first element not equal to `x`. */
0070     template<typename BidiIter, typename Sentinel, typename T>
0071     BidiIter find_not(BidiIter first, Sentinel last, T const & x)
0072     {
0073         while (first != last) {
0074             if (*first != x)
0075                 return first;
0076             ++first;
0077         }
0078         return first;
0079     }
0080
0081     /** Range-friendly version of `std::find_if()`, taking an iterator and a
0082         sentinel. */
0083     template<typename BidiIter, typename Sentinel, typename Pred>
0084     BidiIter find_if(BidiIter first, Sentinel last, Pred p)
0085     {
0086         while (first != last) {
0087             if (p(*first))
0088                 return first;
0089             ++first;
0090         }
0091         return first;
0092     }
0093
0094     /** Range-friendly version of `std::find_if_not()`, taking an iterator and
0095         a sentinel. */
0096     template<typename BidiIter, typename Sentinel, typename Pred>
0097     BidiIter find_if_not(BidiIter first, Sentinel last, Pred p)
0098     {
0099         while (first != last) {
0100             if (!p(*first))
0101                 return first;
0102             ++first;
0103         }
0104         return first;
0105     }
0106
0107     /** Analogue of `std::find()` that finds the last value in `[first, last)`
0108         equal to `x`. */
0109     template<typename BidiIter, typename T>
0110     BidiIter find_backward(BidiIter first, BidiIter last, T const & x)
0111     {
0112         auto it = last;
0113         while (it != first) {
0114             if (*--it == x)
0115                 return it;
0116         }
0117         return last;
0118     }
0119
0120     /** Analogue of `std::find()` that finds the last value in `[first, last)`
0121         not equal to `x`. */
0122     template<typename BidiIter, typename T>
0123     BidiIter find_not_backward(BidiIter first, BidiIter last, T const & x)
0124     {
0125         auto it = last;
0126         while (it != first) {
0127             if (*--it != x)
0128                 return it;
0129         }
0130         return last;
0131     }
0132
0133     /** Analogue of `std::find()` that finds the last value `v` in `[first,
0134         last)` for which `p(v)` is true. */
0135     template<typename BidiIter, typename Pred>
0136     BidiIter find_if_backward(BidiIter first, BidiIter last, Pred p)
0137     {
0138         auto it = last;
0139         while (it != first) {
0140             if (p(*--it))
0141                 return it;
0142         }
0143         return last;
0144     }
0145
0146     /** Analogue of `std::find()` that finds the last value `v` in `[first,
0147         last)` for which `p(v)` is false. */
0148     template<typename BidiIter, typename Pred>
0149     BidiIter find_if_not_backward(BidiIter first, BidiIter last, Pred p)
0150     {
0151         auto it = last;
0152         while (it != first) {
0153             if (!p(*--it))
0154                 return it;
0155         }
0156         return last;
0157     }
0158
0159     /** A utility range type returned by `foreach_subrange*()`. */
0160     template<typename Iter, typename Sentinel = Iter>
0161     using foreach_subrange_range =
0162         BOOST_PARSER_DETAIL_TEXT_SUBRANGE<Iter, Sentinel>;
0163
0164     /** Calls `f(sub)` for each subrange `sub` in `[first, last)`.  A subrange
0165         is a contiguous subsequence of elements that each compares equal to
0166         the first element of the subsequence.  Subranges passed to `f` are
0167         non-overlapping. */
0168     template<typename FwdIter, typename Sentinel, typename Func>
0169     Func foreach_subrange(FwdIter first, Sentinel last, Func f)
0170     {
0171         while (first != last) {
0172             auto const & x = *first;
0173             auto const next = boost::parser::detail::text::find_not(first, last, x);
0174             if (first != next) {
0175                 f(boost::parser::detail::text::foreach_subrange_range<FwdIter, Sentinel>(
0176                     first, next));
0177             }
0178             first = next;
0179         }
0180         return f;
0181     }
0182
0183     /** Calls `f(sub)` for each subrange `sub` in `[first, last)`.  A subrange
0184         is a contiguous subsequence of elements that for each element `e`,
0185         `proj(e)` each compares equal to `proj()` of the first element of the
0186         subsequence.  Subranges passed to `f` are non-overlapping. */
0187     template<typename FwdIter, typename Sentinel, typename Func, typename Proj>
0188     Func foreach_subrange(FwdIter first, Sentinel last, Func f, Proj proj)
0189     {
0190         using value_type = typename std::iterator_traits<FwdIter>::value_type;
0191         while (first != last) {
0192             auto const & x = proj(*first);
0193             auto const next = boost::parser::detail::text::find_if_not(
0194                 first, last, [&x, proj](const value_type & element) {
0195                     return proj(element) == x;
0196                 });
0197             if (first != next) {
0198                 f(boost::parser::detail::text::foreach_subrange_range<FwdIter, Sentinel>(
0199                     first, next));
0200             }
0201             first = next;
0202         }
0203         return f;
0204     }
0205
0206     /** Calls `f(sub)` for each subrange `sub` in `[first, last)`.  A subrange
0207         is a contiguous subsequence of elements, each of which is equal to
0208         `x`.  Subranges passed to `f` are non-overlapping. */
0209     template<typename FwdIter, typename Sentinel, typename T, typename Func>
0210     Func foreach_subrange_of(FwdIter first, Sentinel last, T const & x, Func f)
0211     {
0212         while (first != last) {
0213             first = boost::parser::detail::text::find(first, last, x);
0214             auto const next = boost::parser::detail::text::find_not(first, last, x);
0215             if (first != next) {
0216                 f(boost::parser::detail::text::foreach_subrange_range<FwdIter, Sentinel>(
0217                     first, next));
0218             }
0219             first = next;
0220         }
0221         return f;
0222     }
0223
0224     /** Calls `f(sub)` for each subrange `sub` in `[first, last)`.  A subrange
0225         is a contiguous subsequence of elements `ei` for which `p(ei)` is
0226         true.  Subranges passed to `f` are non-overlapping. */
0227     template<typename FwdIter, typename Sentinel, typename Pred, typename Func>
0228     Func foreach_subrange_if(FwdIter first, Sentinel last, Pred p, Func f)
0229     {
0230         while (first != last) {
0231             first = boost::parser::detail::text::find_if(first, last, p);
0232             auto const next = boost::parser::detail::text::find_if_not(first, last, p);
0233             if (first != next) {
0234                 f(boost::parser::detail::text::foreach_subrange_range<FwdIter, Sentinel>(
0235                     first, next));
0236             }
0237             first = next;
0238         }
0239         return f;
0240     }
0241
0242     /** Sentinel-friendly version of `std::all_of()`. */
0243     template<typename Iter, typename Sentinel, typename Pred>
0244     bool all_of(Iter first, Sentinel last, Pred p)
0245     {
0246         for (; first != last; ++first) {
0247             if (!p(*first))
0248                 return false;
0249         }
0250         return true;
0251     }
0252
0253     /** Sentinel-friendly version of `std::equal()`. */
0254     template<
0255         typename Iter1,
0256         typename Sentinel1,
0257         typename Iter2,
0258         typename Sentinel2>
0259     bool equal(Iter1 first1, Sentinel1 last1, Iter2 first2, Sentinel2 last2)
0260     {
0261         for (; first1 != last1 && first2 != last2; ++first1, ++first2) {
0262             if (*first1 != *first2)
0263                 return false;
0264         }
0265         return first1 == last1 && first2 == last2;
0266     }
0267
0268     /** Sentinel-friendly version of `std::mismatch()`. */
0269     template<
0270         typename Iter1,
0271         typename Sentinel1,
0272         typename Iter2,
0273         typename Sentinel2>
0274     std::pair<Iter1, Iter2>
0275     mismatch(Iter1 first1, Sentinel1 last1, Iter2 first2, Sentinel2 last2)
0276     {
0277         for (; first1 != last1 && first2 != last2; ++first1, ++first2) {
0278             if (*first1 != *first2)
0279                 break;
0280         }
0281         return {first1, first2};
0282     }
0283
0284     /** Sentinel-friendly version of
0285         `std::lexicographical_compare_three_way()`, except that it returns an
0286         `int` instead of a `std::strong_ordering`. */
0287     template<
0288         typename Iter1,
0289         typename Sentinel1,
0290         typename Iter2,
0291         typename Sentinel2>
0292     int lexicographical_compare_three_way(
0293         Iter1 first1, Sentinel1 last1, Iter2 first2, Sentinel2 last2)
0294     {
0295         auto const iters = boost::parser::detail::text::mismatch(first1, last1, first2, last2);
0296         if (iters.first == last1) {
0297             if (iters.second == last2)
0298                 return 0;
0299             else
0300                 return -1;
0301         } else if (iters.second == last2) {
0302             return 1;
0303         } else if (*iters.first < *iters.second) {
0304             return -1;
0305         } else {
0306             return 1;
0307         }
0308     }
0309
0310     /** The view type returned by `boost::parser::detail::text::search()`. */
0311     template<typename Iter>
0312     using search_result = BOOST_PARSER_DETAIL_TEXT_SUBRANGE<Iter>;
0313
0314     /** Sentinel-friendly version of `std::search()`. */
0315     template<
0316         typename Iter1,
0317         typename Sentinel1,
0318         typename Iter2,
0319         typename Sentinel2>
0320     search_result<Iter1>
0321     search(Iter1 first1, Sentinel1 last1, Iter2 first2, Sentinel2 last2)
0322     {
0323         if (first1 == last1 || first2 == last2)
0324             return {first1, first1};
0325
0326         if (detail::next(first2) == last2) {
0327             auto const it = parser::detail::text::find(first1, last1, *first2);
0328             if (it == last1)
0329                 return {it, it};
0330             return {it, detail::next(it)};
0331         }
0332
0333         auto it = first1;
0334         for (;;) {
0335             first1 = parser::detail::text::find(first1, last1, *first2);
0336
0337             if (first1 == last1)
0338                 return {first1, first1};
0339
0340             auto it2 = detail::next(first2);
0341             it = first1;
0342             if (++it == last1)
0343                 return {it, it};
0344
0345             while (*it == *it2) {
0346                 if (++it2 == last2)
0347                     return {first1, ++it};
0348                 if (++it == last1)
0349                     return {it, it};
0350             }
0351
0352             ++first1;
0353         }
0354
0355         return {first1, first1};
0356     }
0357
0358     /** Sentinel-friendly version of `std::find_first_of()`. */
0359     template<
0360         typename Iter1,
0361         typename Sentinel1,
0362         typename Iter2,
0363         typename Sentinel2,
0364         typename Pred>
0365     Iter1 find_first_of(
0366         Iter1 first1, Sentinel1 last1, Iter2 first2, Sentinel2 last2, Pred pred)
0367     {
0368         for (; first1 != last1; ++first1) {
0369             for (auto it = first2; it != last2; ++it) {
0370                 if (pred(*first1, *it))
0371                     return first1;
0372             }
0373         }
0374         return first1;
0375     }
0376
0377 }}
0378
0379 #if BOOST_PARSER_DETAIL_TEXT_USE_CONCEPTS
0380
0381 namespace std::ranges {
0382     template<typename Iter, typename Sentinel>
0383     inline constexpr bool enable_borrowed_range<
0384         boost::parser::detail::text::foreach_subrange_range<Iter, Sentinel>> = true;
0385 }
0386
0387 #endif
0388
0389 #endif