Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2025-12-15 10:26:41 

0001 /// \file
0002 // Range v3 library
0003 //
0004 //  Copyright Eric Niebler 2014-present
0005 //
0006 //  Use, modification and distribution is subject to the
0007 //  Boost Software License, Version 1.0. (See accompanying
0008 //  file LICENSE_1_0.txt or copy at
0009 //  http://www.boost.org/LICENSE_1_0.txt)
0010 //
0011 // Project home: https://github.com/ericniebler/range-v3
0012 //
0013 #ifndef RANGES_V3_ITERATOR_OPERATIONS_HPP
0014 #define RANGES_V3_ITERATOR_OPERATIONS_HPP
0015 
0016 #include <type_traits>
0017 #include <utility>
0018 
0019 #include <range/v3/range_fwd.hpp>
0020 
0021 #include <range/v3/iterator/concepts.hpp>
0022 #include <range/v3/iterator/traits.hpp>
0023 #include <range/v3/range/concepts.hpp>
0024 
0025 #include <range/v3/detail/prologue.hpp>
0026 
0027 namespace ranges
0028 {
0029     /// \addtogroup group-iterator
0030     /// @{
0031 
0032     /// \cond
0033     template<typename I>
0034         // requires input_or_output_iterator<I>
0035     struct counted_iterator;
0036     /// \endcond
0037 
0038     struct advance_fn
0039     {
0040 #if RANGES_CXX_IF_CONSTEXPR >= RANGES_CXX_IF_CONSTEXPR_17
0041         template(typename I)(
0042             requires input_or_output_iterator<I>)
0043         constexpr void operator()(I & i, iter_difference_t<I> n) const
0044         // [[expects: n >= 0 || bidirectional_iterator<I>]]
0045         {
0046             if constexpr(random_access_iterator<I>)
0047             {
0048                 i += n;
0049             }
0050             else
0051             {
0052                 if constexpr(bidirectional_iterator<I>)
0053                     for(; 0 > n; ++n)
0054                         --i;
0055                 RANGES_EXPECT(0 <= n);
0056                 for(; 0 < n; --n)
0057                     ++i;
0058             }
0059         }
0060 
0061         template(typename I, typename S)(
0062             requires sentinel_for<S, I>)
0063         constexpr void operator()(I & i, S bound) const
0064         // [[expects axiom: reachable(i, bound)]]
0065         {
0066             if constexpr(assignable_from<I &, S>)
0067             {
0068                 i = std::move(bound);
0069             }
0070             else if constexpr(sized_sentinel_for<S, I>)
0071             {
0072                 iter_difference_t<I> d = bound - i;
0073                 RANGES_EXPECT(0 <= d);
0074                 (*this)(i, d);
0075             }
0076             else
0077                 while(i != bound)
0078                     ++i;
0079         }
0080 
0081         template(typename I, typename S)(
0082             requires sentinel_for<S, I>)
0083         constexpr iter_difference_t<I> //
0084         operator()(I & i, iter_difference_t<I> n, S bound) const
0085         // [[expects axiom: 0 == n ||
0086         //     (0 < n && reachable(i, bound)) ||
0087         //     (0 > n && same_as<I, S> && bidirectional_iterator<I> && reachable(bound,
0088         //     i))]]
0089         {
0090             if constexpr(sized_sentinel_for<S, I>)
0091             {
0092                 if(0 == n)
0093                     return 0;
0094                 const auto d = bound - i;
0095                 if constexpr(bidirectional_iterator<I> && same_as<I, S>)
0096                 {
0097                     RANGES_EXPECT(0 <= n ? 0 <= d : 0 >= d);
0098                     if(0 <= n ? d <= n : d >= n)
0099                     {
0100                         i = std::move(bound);
0101                         return n - d;
0102                     }
0103                 }
0104                 else
0105                 {
0106                     RANGES_EXPECT(0 <= n && 0 <= d);
0107                     if(d <= n)
0108                     {
0109                         (*this)(i, std::move(bound));
0110                         return n - d;
0111                     }
0112                 }
0113                 (*this)(i, n);
0114                 return 0;
0115             }
0116             else
0117             {
0118                 if constexpr(bidirectional_iterator<I> && same_as<I, S>)
0119                 {
0120                     if(0 > n)
0121                     {
0122                         do
0123                         {
0124                             --i;
0125                             ++n;
0126                         } while(0 != n && i != bound);
0127                         return n;
0128                     }
0129                 }
0130                 RANGES_EXPECT(0 <= n);
0131                 while(0 != n && i != bound)
0132                 {
0133                     ++i;
0134                     --n;
0135                 }
0136                 return n;
0137             }
0138         }
0139 #else
0140     private:
0141         template<typename I>
0142         static constexpr void n_(I & i, iter_difference_t<I> n, std::input_iterator_tag);
0143         template<typename I>
0144         static constexpr void n_(I & i, iter_difference_t<I> n,
0145                                  std::bidirectional_iterator_tag);
0146         template<typename I>
0147         static constexpr void n_(I & i, iter_difference_t<I> n,
0148                                  std::random_access_iterator_tag);
0149         template<typename I, typename S>
0150         static constexpr void to_impl_(I & i, S s, sentinel_tag);
0151         template<typename I, typename S>
0152         static constexpr void to_impl_(I & i, S s, sized_sentinel_tag);
0153         template<typename I, typename S>
0154         static constexpr void to_(I & i, S s, std::true_type); // assignable
0155         template<typename I, typename S>
0156         static constexpr void to_(I & i, S s, std::false_type); // !assignable
0157         template<typename I, typename S>
0158         static constexpr iter_difference_t<I> bounded_(I & it, iter_difference_t<I> n,
0159                                                        S bound, sentinel_tag,
0160                                                        std::input_iterator_tag);
0161         template<typename I>
0162         static constexpr iter_difference_t<I> bounded_(I & it, iter_difference_t<I> n,
0163                                                        I bound, sentinel_tag,
0164                                                        std::bidirectional_iterator_tag);
0165         template<typename I, typename S, typename Concept>
0166         static constexpr iter_difference_t<I> bounded_(I & it, iter_difference_t<I> n,
0167                                                        S bound, sized_sentinel_tag,
0168                                                        Concept);
0169 
0170     public:
0171         // Advance a certain number of steps:
0172         template(typename I)(
0173             requires input_or_output_iterator<I>)
0174         constexpr void operator()(I & i, iter_difference_t<I> n) const
0175         {
0176             advance_fn::n_(i, n, iterator_tag_of<I>{});
0177         }
0178         // Advance to a certain position:
0179         template(typename I, typename S)(
0180             requires sentinel_for<S, I>)
0181         constexpr void operator()(I & i, S s) const
0182         {
0183             advance_fn::to_(
0184                 i, static_cast<S &&>(s), meta::bool_<assignable_from<I &, S>>());
0185         }
0186         // Advance a certain number of times, with a bound:
0187         template(typename I, typename S)(
0188             requires sentinel_for<S, I>)
0189         constexpr iter_difference_t<I> //
0190         operator()(I & it, iter_difference_t<I> n, S bound) const
0191         {
0192             return advance_fn::bounded_(it,
0193                                         n,
0194                                         static_cast<S &&>(bound),
0195                                         sentinel_tag_of<S, I>(),
0196                                         iterator_tag_of<I>());
0197         }
0198 #endif
0199 
0200         template(typename I)(
0201             requires input_or_output_iterator<I>)
0202         constexpr void operator()(counted_iterator<I> & i, iter_difference_t<I> n) const;
0203     };
0204 
0205     /// \sa `advance_fn`
0206     RANGES_INLINE_VARIABLE(advance_fn, advance)
0207 
0208 #if RANGES_CXX_IF_CONSTEXPR < RANGES_CXX_IF_CONSTEXPR_17
0209     template<typename I>
0210     constexpr void advance_fn::n_(I & i, iter_difference_t<I> n, std::input_iterator_tag)
0211     {
0212         RANGES_EXPECT(n >= 0);
0213         for(; n > 0; --n)
0214             ++i;
0215     }
0216     template<typename I>
0217     constexpr void advance_fn::n_(I & i, iter_difference_t<I> n,
0218                                   std::bidirectional_iterator_tag)
0219     {
0220         if(n > 0)
0221             for(; n > 0; --n)
0222                 ++i;
0223         else
0224             for(; n < 0; ++n)
0225                 --i;
0226     }
0227     template<typename I>
0228     constexpr void advance_fn::n_(I & i, iter_difference_t<I> n,
0229                                   std::random_access_iterator_tag)
0230     {
0231         i += n;
0232     }
0233     template<typename I, typename S>
0234     constexpr void advance_fn::to_impl_(I & i, S s, sentinel_tag)
0235     {
0236         while(i != s)
0237             ++i;
0238     }
0239     template<typename I, typename S>
0240     constexpr void advance_fn::to_impl_(I & i, S s, sized_sentinel_tag)
0241     {
0242         iter_difference_t<I> d = s - i;
0243         RANGES_EXPECT(0 <= d);
0244         advance(i, d);
0245     }
0246     // Advance to a certain position:
0247     template<typename I, typename S>
0248     constexpr void advance_fn::to_(I & i, S s, std::true_type)
0249     {
0250         i = static_cast<S &&>(s);
0251     }
0252     template<typename I, typename S>
0253     constexpr void advance_fn::to_(I & i, S s, std::false_type)
0254     {
0255         advance_fn::to_impl_(i, static_cast<S &&>(s), sentinel_tag_of<S, I>());
0256     }
0257     template<typename I, typename S>
0258     constexpr iter_difference_t<I> advance_fn::bounded_(I & it, iter_difference_t<I> n,
0259                                                         S bound, sentinel_tag,
0260                                                         std::input_iterator_tag)
0261     {
0262         RANGES_EXPECT(0 <= n);
0263         for(; 0 != n && it != bound; --n)
0264             ++it;
0265         return n;
0266     }
0267     template<typename I>
0268     constexpr iter_difference_t<I> advance_fn::bounded_(I & it, iter_difference_t<I> n,
0269                                                         I bound, sentinel_tag,
0270                                                         std::bidirectional_iterator_tag)
0271     {
0272         if(0 <= n)
0273             for(; 0 != n && it != bound; --n)
0274                 ++it;
0275         else
0276             for(; 0 != n && it != bound; ++n)
0277                 --it;
0278         return n;
0279     }
0280     template<typename I, typename S, typename Concept>
0281     constexpr iter_difference_t<I> advance_fn::bounded_(I & it, iter_difference_t<I> n,
0282                                                         S bound, sized_sentinel_tag,
0283                                                         Concept)
0284     {
0285         RANGES_EXPECT(((bool)same_as<I, S> || 0 <= n));
0286         if(n == 0)
0287             return 0;
0288         iter_difference_t<I> d = bound - it;
0289         RANGES_EXPECT(0 <= n ? 0 <= d : 0 >= d);
0290         if(0 <= n ? n >= d : n <= d)
0291         {
0292             advance(it, static_cast<S &&>(bound));
0293             return n - d;
0294         }
0295         advance(it, n);
0296         return 0;
0297     }
0298 #endif
0299 
0300     struct next_fn
0301     {
0302         template(typename I)(
0303             requires input_or_output_iterator<I>)
0304         constexpr I operator()(I it) const
0305         {
0306             return ++it;
0307         }
0308         template(typename I)(
0309             requires input_or_output_iterator<I>)
0310         constexpr I operator()(I it, iter_difference_t<I> n) const
0311         {
0312             advance(it, n);
0313             return it;
0314         }
0315         template(typename I, typename S)(
0316             requires sentinel_for<S, I>)
0317         constexpr I operator()(I it, S s) const
0318         {
0319             advance(it, static_cast<S &&>(s));
0320             return it;
0321         }
0322         template(typename I, typename S)(
0323             requires sentinel_for<S, I>)
0324         constexpr I operator()(I it, iter_difference_t<I> n, S bound) const
0325         {
0326             advance(it, n, static_cast<S &&>(bound));
0327             return it;
0328         }
0329     };
0330 
0331     /// \sa `next_fn`
0332     RANGES_INLINE_VARIABLE(next_fn, next)
0333 
0334     struct prev_fn
0335     {
0336         template(typename I)(
0337             requires bidirectional_iterator<I>)
0338         constexpr I operator()(I it) const
0339         {
0340             return --it;
0341         }
0342         template(typename I)(
0343             requires bidirectional_iterator<I>)
0344         constexpr I operator()(I it, iter_difference_t<I> n) const
0345         {
0346             advance(it, -n);
0347             return it;
0348         }
0349         template(typename I)(
0350             requires bidirectional_iterator<I>)
0351         constexpr I operator()(I it, iter_difference_t<I> n, I bound) const
0352         {
0353             advance(it, -n, static_cast<I &&>(bound));
0354             return it;
0355         }
0356     };
0357 
0358     /// \sa `prev_fn`
0359     RANGES_INLINE_VARIABLE(prev_fn, prev)
0360 
0361     struct iter_enumerate_fn
0362     {
0363     private:
0364         template(typename I, typename S)(
0365             requires (!sized_sentinel_for<I, I>)) //
0366         static constexpr std::pair<iter_difference_t<I>, I> //
0367         impl_i(I first, S last, sentinel_tag)
0368         {
0369             iter_difference_t<I> d = 0;
0370             for(; first != last; ++first)
0371                 ++d;
0372             return {d, first};
0373         }
0374         template(typename I, typename S)(
0375             requires sized_sentinel_for<I, I>)
0376         static constexpr std::pair<iter_difference_t<I>, I> //
0377         impl_i(I first, S end_, sentinel_tag)
0378         {
0379             I last = ranges::next(first, end_);
0380             auto n = static_cast<iter_difference_t<I>>(last - first);
0381             RANGES_EXPECT(((bool)same_as<I, S> || 0 <= n));
0382             return {n, last};
0383         }
0384         template<typename I, typename S>
0385         static constexpr std::pair<iter_difference_t<I>, I> //
0386         impl_i(I first, S last, sized_sentinel_tag)
0387         {
0388             auto n = static_cast<iter_difference_t<I>>(last - first);
0389             RANGES_EXPECT(((bool)same_as<I, S> || 0 <= n));
0390             return {n, ranges::next(first, last)};
0391         }
0392 
0393     public:
0394         template(typename I, typename S)(
0395             requires sentinel_for<S, I>)
0396         constexpr std::pair<iter_difference_t<I>, I> operator()(I first, S last) const
0397         {
0398             return iter_enumerate_fn::impl_i(static_cast<I &&>(first),
0399                                              static_cast<S &&>(last),
0400                                              sentinel_tag_of<S, I>());
0401         }
0402     };
0403 
0404     /// \sa `iter_enumerate_fn`
0405     RANGES_INLINE_VARIABLE(iter_enumerate_fn, iter_enumerate)
0406 
0407     struct iter_distance_fn
0408     {
0409     private:
0410         template<typename I, typename S>
0411         static constexpr iter_difference_t<I> impl_i(I first, S last, sentinel_tag)
0412         {
0413             return iter_enumerate(static_cast<I &&>(first), static_cast<S &&>(last))
0414                 .first;
0415         }
0416         template<typename I, typename S>
0417         static constexpr iter_difference_t<I> impl_i(I first, S last, sized_sentinel_tag)
0418         {
0419             auto n = static_cast<iter_difference_t<I>>(last - first);
0420             RANGES_EXPECT(((bool)same_as<I, S> || 0 <= n));
0421             return n;
0422         }
0423 
0424     public:
0425         template(typename I, typename S)(
0426             requires input_or_output_iterator<I> AND sentinel_for<S, I>)
0427         constexpr iter_difference_t<I> operator()(I first, S last) const
0428         {
0429             return iter_distance_fn::impl_i(static_cast<I &&>(first),
0430                                             static_cast<S &&>(last),
0431                                             sentinel_tag_of<S, I>());
0432         }
0433     };
0434 
0435     /// \sa `iter_distance_fn`
0436     RANGES_INLINE_VARIABLE(iter_distance_fn, iter_distance)
0437 
0438     struct iter_distance_compare_fn
0439     {
0440     private:
0441         template<typename I, typename S>
0442         static constexpr int impl_i(I first, S last, iter_difference_t<I> n, sentinel_tag)
0443         {
0444             if(n < 0)
0445                 return 1;
0446             for(; n > 0; --n, ++first)
0447             {
0448                 if(first == last)
0449                     return -1;
0450             }
0451             return first == last ? 0 : 1;
0452         }
0453         template<typename I, typename S>
0454         static constexpr int impl_i(I first, S last, iter_difference_t<I> n,
0455                                     sized_sentinel_tag)
0456         {
0457             iter_difference_t<I> dist = last - first;
0458             if(n < dist)
0459                 return 1;
0460             if(dist < n)
0461                 return -1;
0462             return 0;
0463         }
0464 
0465     public:
0466         template(typename I, typename S)(
0467             requires input_iterator<I> AND sentinel_for<S, I>)
0468         constexpr int operator()(I first, S last, iter_difference_t<I> n) const
0469         {
0470             return iter_distance_compare_fn::impl_i(static_cast<I &&>(first),
0471                                                     static_cast<S &&>(last),
0472                                                     n,
0473                                                     sentinel_tag_of<S, I>());
0474         }
0475     };
0476 
0477     /// \sa `iter_distance_compare_fn`
0478     RANGES_INLINE_VARIABLE(iter_distance_compare_fn, iter_distance_compare)
0479 
0480     // Like distance(b,e), but guaranteed to be O(1)
0481     struct iter_size_fn
0482     {
0483         template(typename I, typename S)(
0484             requires sized_sentinel_for<S, I>)
0485         constexpr meta::_t<std::make_unsigned<iter_difference_t<I>>> //
0486         operator()(I const & first, S last) const
0487         {
0488             using size_type = meta::_t<std::make_unsigned<iter_difference_t<I>>>;
0489             iter_difference_t<I> n = last - first;
0490             RANGES_EXPECT(0 <= n);
0491             return static_cast<size_type>(n);
0492         }
0493     };
0494 
0495     /// \sa `iter_size_fn`
0496     RANGES_INLINE_VARIABLE(iter_size_fn, iter_size)
0497 
0498     /// \cond
0499     namespace adl_uncounted_recounted_detail
0500     {
0501         template<typename I>
0502         constexpr I uncounted(I i)
0503         {
0504             return i;
0505         }
0506 
0507         template<typename I>
0508         constexpr I recounted(I const &, I i, iter_difference_t<I>)
0509         {
0510             return i;
0511         }
0512 
0513         struct uncounted_fn
0514         {
0515             template<typename I>
0516             constexpr auto operator()(I i) const -> decltype(uncounted((I &&) i))
0517             {
0518                 return uncounted((I &&) i);
0519             }
0520         };
0521 
0522         struct recounted_fn
0523         {
0524             template<typename I, typename J>
0525             constexpr auto operator()(I i, J j, iter_difference_t<J> n) const
0526                 -> decltype(recounted((I &&) i, (J &&) j, n))
0527             {
0528                 return recounted((I &&) i, (J &&) j, n);
0529             }
0530         };
0531     } // namespace adl_uncounted_recounted_detail
0532     /// \endcond
0533 
0534     RANGES_INLINE_VARIABLE(adl_uncounted_recounted_detail::uncounted_fn, uncounted)
0535     RANGES_INLINE_VARIABLE(adl_uncounted_recounted_detail::recounted_fn, recounted)
0536 
0537     struct enumerate_fn : iter_enumerate_fn
0538     {
0539     private:
0540         template<typename Rng>
0541         static constexpr std::pair<range_difference_t<Rng>, iterator_t<Rng>> impl_r(
0542             Rng & rng, range_tag, range_tag)
0543         {
0544             return iter_enumerate(begin(rng), end(rng));
0545         }
0546         template<typename Rng>
0547         static constexpr std::pair<range_difference_t<Rng>, iterator_t<Rng>> impl_r(
0548             Rng & rng, common_range_tag, sized_range_tag)
0549         {
0550             return {static_cast<range_difference_t<Rng>>(size(rng)), end(rng)};
0551         }
0552 
0553     public:
0554         using iter_enumerate_fn::operator();
0555 
0556         template(typename Rng)(
0557             requires range<Rng>)
0558         constexpr std::pair<range_difference_t<Rng>, iterator_t<Rng>> operator()(Rng && rng) const
0559         {
0560             // Better not be trying to compute the distance of an infinite range:
0561             RANGES_EXPECT(!is_infinite<Rng>::value);
0562             return enumerate_fn::impl_r(
0563                 rng, common_range_tag_of<Rng>(), sized_range_tag_of<Rng>());
0564         }
0565     };
0566 
0567     /// \sa `enumerate_fn`
0568     RANGES_INLINE_VARIABLE(enumerate_fn, enumerate)
0569 
0570     struct distance_fn : iter_distance_fn
0571     {
0572     private:
0573         template<typename Rng>
0574         static range_difference_t<Rng> impl_r(Rng & rng, range_tag)
0575         {
0576             return enumerate(rng).first;
0577         }
0578         template<typename Rng>
0579         static constexpr range_difference_t<Rng> impl_r(Rng & rng, sized_range_tag)
0580         {
0581             return static_cast<range_difference_t<Rng>>(size(rng));
0582         }
0583 
0584     public:
0585         using iter_distance_fn::operator();
0586 
0587         template(typename Rng)(
0588             requires range<Rng>)
0589         constexpr range_difference_t<Rng> operator()(Rng && rng) const
0590         {
0591             // Better not be trying to compute the distance of an infinite range:
0592             RANGES_EXPECT(!is_infinite<Rng>::value);
0593             return distance_fn::impl_r(rng, sized_range_tag_of<Rng>());
0594         }
0595     };
0596 
0597     /// \sa `distance_fn`
0598     RANGES_INLINE_VARIABLE(distance_fn, distance)
0599 
0600     // The interface of distance_compare is taken from Util.listLengthCmp in the GHC API.
0601     struct distance_compare_fn : iter_distance_compare_fn
0602     {
0603     private:
0604         template<typename Rng>
0605         static constexpr int impl_r(Rng & rng, range_difference_t<Rng> n, range_tag)
0606         {
0607             // Infinite ranges are always compared to be larger than a finite number.
0608             return is_infinite<Rng>::value
0609                        ? 1
0610                        : iter_distance_compare(begin(rng), end(rng), n);
0611         }
0612         template<typename Rng>
0613         static constexpr int impl_r(Rng & rng, range_difference_t<Rng> n, sized_range_tag)
0614         {
0615             auto dist = distance(rng); // O(1) since rng is a sized_range
0616             if(dist > n)
0617                 return 1;
0618             else if(dist < n)
0619                 return -1;
0620             else
0621                 return 0;
0622         }
0623 
0624     public:
0625         using iter_distance_compare_fn::operator();
0626 
0627         template(typename Rng)(
0628             requires range<Rng>)
0629         constexpr int operator()(Rng && rng, range_difference_t<Rng> n) const
0630         {
0631             return distance_compare_fn::impl_r(rng, n, sized_range_tag_of<Rng>());
0632         }
0633     };
0634 
0635     /// \sa `distance_compare_fn`
0636     RANGES_INLINE_VARIABLE(distance_compare_fn, distance_compare)
0637 
0638     namespace cpp20
0639     {
0640         using ranges::advance;
0641         using ranges::distance;
0642         using ranges::next;
0643         using ranges::prev;
0644     } // namespace cpp20
0645     /// @}
0646 } // namespace ranges
0647 
0648 #include <range/v3/detail/epilogue.hpp>
0649 
0650 #endif // RANGES_V3_ITERATOR_OPERATIONS_HPP
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!