v3/algorithm/unique_copy.hpp

0001 /// \file
0002 // Range v3 library
0003 //
0004 //  Copyright Eric Niebler 2013-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_ALGORITHM_UNIQUE_COPY_HPP
0014 #define RANGES_V3_ALGORITHM_UNIQUE_COPY_HPP
0015
0016 #include <meta/meta.hpp>
0017
0018 #include <range/v3/range_fwd.hpp>
0019
0020 #include <range/v3/algorithm/result_types.hpp>
0021 #include <range/v3/functional/comparisons.hpp>
0022 #include <range/v3/functional/identity.hpp>
0023 #include <range/v3/functional/invoke.hpp>
0024 #include <range/v3/iterator/concepts.hpp>
0025 #include <range/v3/iterator/traits.hpp>
0026 #include <range/v3/range/access.hpp>
0027 #include <range/v3/range/concepts.hpp>
0028 #include <range/v3/range/dangling.hpp>
0029 #include <range/v3/range/traits.hpp>
0030 #include <range/v3/utility/static_const.hpp>
0031
0032 #include <range/v3/detail/prologue.hpp>
0033
0034 namespace ranges
0035 {
0036     /// \addtogroup group-algorithms
0037     /// @{
0038
0039     template<typename I, typename O>
0040     using unique_copy_result = detail::in_out_result<I, O>;
0041
0042     /// \cond
0043     namespace detail
0044     {
0045         template<typename I, typename S, typename O, typename C, typename P>
0046         constexpr unique_copy_result<I, O> unique_copy_impl(I first,
0047                                                             S last,
0048                                                             O out,
0049                                                             C pred,
0050                                                             P proj,
0051                                                             std::input_iterator_tag,
0052                                                             std::false_type)
0053         {
0054             if(first != last)
0055             {
0056                 // Must save a copy into a local because we will need this value
0057                 // even after we advance the input iterator.
0058                 iter_value_t<I> value =
0059                     *first; // This is guaranteed by indirectly_copyable
0060                 *out = value;
0061                 ++out;
0062                 while(++first != last)
0063                 {
0064                     auto && x = *first;
0065                     if(!invoke(pred, invoke(proj, value), invoke(proj, x)))
0066                     {
0067                         value = (decltype(x) &&)x;
0068                         *out = value;
0069                         ++out;
0070                     }
0071                 }
0072             }
0073             return {first, out};
0074         }
0075
0076         template<typename I, typename S, typename O, typename C, typename P>
0077         constexpr unique_copy_result<I, O> unique_copy_impl(I first,
0078                                                             S last,
0079                                                             O out,
0080                                                             C pred,
0081                                                             P proj,
0082                                                             std::forward_iterator_tag,
0083                                                             std::false_type)
0084         {
0085             if(first != last)
0086             {
0087                 I tmp = first;
0088                 *out = *tmp;
0089                 ++out;
0090                 while(++first != last)
0091                 {
0092                     auto && x = *first;
0093                     if(!invoke(pred, invoke(proj, *tmp), invoke(proj, x)))
0094                     {
0095                         *out = (decltype(x) &&)x;
0096                         ++out;
0097                         tmp = first;
0098                     }
0099                 }
0100             }
0101             return {first, out};
0102         }
0103
0104         template<typename I, typename S, typename O, typename C, typename P>
0105         constexpr unique_copy_result<I, O> unique_copy_impl(I first,
0106                                                             S last,
0107                                                             O out,
0108                                                             C pred,
0109                                                             P proj,
0110                                                             std::input_iterator_tag, std::true_type)
0111         {
0112             if(first != last)
0113             {
0114                 *out = *first;
0115                 while(++first != last)
0116                 {
0117                     auto && x = *first;
0118                     if(!invoke(pred, invoke(proj, *out), invoke(proj, x)))
0119                         *++out = (decltype(x) &&)x;
0120                 }
0121                 ++out;
0122             }
0123             return {first, out};
0124         }
0125     } // namespace detail
0126     /// \endcond
0127
0128     RANGES_FUNC_BEGIN(unique_copy)
0129
0130         /// \brief template function unique_copy
0131         ///
0132         /// range-based version of the `unique_copy` std algorithm
0133         ///
0134         /// \pre `Rng` is a model of the `input_range` concept
0135         /// \pre `O` is a model of the `weakly_incrementable` concept
0136         /// \pre `C` is a model of the `relation` concept
0137         template(typename I,
0138                  typename S,
0139                  typename O,
0140                  typename C = equal_to,
0141                  typename P = identity)(
0142             requires input_iterator<I> AND sentinel_for<S, I> AND
0143                 indirect_relation<C, projected<I, P>> AND weakly_incrementable<O> AND
0144                 indirectly_copyable<I, O> AND
0145                 (forward_iterator<I> || forward_iterator<O> ||
0146                  indirectly_copyable_storable<I, O>)) //
0147         constexpr unique_copy_result<I, O> RANGES_FUNC(unique_copy)(
0148             I first, S last, O out, C pred = C{}, P proj = P{}) //
0149         {
0150             return detail::unique_copy_impl(std::move(first),
0151                                             std::move(last),
0152                                             std::move(out),
0153                                             std::move(pred),
0154                                             std::move(proj),
0155                                             iterator_tag_of<I>(),
0156                                             meta::bool_<forward_iterator<O>>{});
0157         }
0158
0159         /// \overload
0160         template(typename Rng, typename O, typename C = equal_to, typename P = identity)(
0161             requires input_range<Rng> AND
0162                 indirect_relation<C, projected<iterator_t<Rng>, P>> AND
0163                 weakly_incrementable<O> AND indirectly_copyable<iterator_t<Rng>, O> AND
0164                 (forward_iterator<iterator_t<Rng>> || forward_iterator<O> ||
0165                  indirectly_copyable_storable<iterator_t<Rng>, O>)) //
0166         constexpr unique_copy_result<borrowed_iterator_t<Rng>, O> //
0167         RANGES_FUNC(unique_copy)(Rng && rng, O out, C pred = C{}, P proj = P{}) //
0168         {
0169             return detail::unique_copy_impl(begin(rng),
0170                                             end(rng),
0171                                             std::move(out),
0172                                             std::move(pred),
0173                                             std::move(proj),
0174                                             iterator_tag_of<iterator_t<Rng>>(),
0175                                             meta::bool_<forward_iterator<O>>{});
0176         }
0177
0178     RANGES_FUNC_END(unique_copy)
0179
0180     namespace cpp20
0181     {
0182         using ranges::unique_copy;
0183         using ranges::unique_copy_result;
0184     } // namespace cpp20
0185     /// @}
0186 } // namespace ranges
0187
0188 #include <range/v3/detail/epilogue.hpp>
0189
0190 #endif