1 /// \file 2 // Range v3 library 3 // 4 // Copyright Eric Niebler 2013-present 5 // 6 // Use, modification and distribution is subject to the 7 // Boost Software License, Version 1.0. (See accompanying 8 // file LICENSE_1_0.txt or copy at 9 // http://www.boost.org/LICENSE_1_0.txt) 10 // 11 // Project home: https://github.com/ericniebler/range-v3 12 // 13 #ifndef RANGES_V3_ALGORITHM_UNIQUE_COPY_HPP 14 #define RANGES_V3_ALGORITHM_UNIQUE_COPY_HPP 15 16 #include <meta/meta.hpp> 17 18 #include <range/v3/range_fwd.hpp> 19 20 #include <range/v3/algorithm/result_types.hpp> 21 #include <range/v3/functional/comparisons.hpp> 22 #include <range/v3/functional/identity.hpp> 23 #include <range/v3/functional/invoke.hpp> 24 #include <range/v3/iterator/concepts.hpp> 25 #include <range/v3/iterator/traits.hpp> 26 #include <range/v3/range/access.hpp> 27 #include <range/v3/range/concepts.hpp> 28 #include <range/v3/range/dangling.hpp> 29 #include <range/v3/range/traits.hpp> 30 #include <range/v3/utility/static_const.hpp> 31 32 #include <range/v3/detail/prologue.hpp> 33 34 namespace ranges 35 { 36 /// \addtogroup group-algorithms 37 /// @{ 38 39 template<typename I, typename O> 40 using unique_copy_result = detail::in_out_result<I, O>; 41 42 /// \cond 43 namespace detail 44 { 45 template<typename I, typename S, typename O, typename C, typename P> unique_copy_impl(I first,S last,O out,C pred,P proj,std::input_iterator_tag,std::false_type)46 unique_copy_result<I, O> unique_copy_impl(I first, S last, O out, C pred, P proj, 47 std::input_iterator_tag, 48 std::false_type) 49 { 50 if(first != last) 51 { 52 // Must save a copy into a local because we will need this value 53 // even after we advance the input iterator. 54 iter_value_t<I> value = 55 *first; // This is guaranteed by indirectly_copyable 56 *out = value; 57 ++out; 58 while(++first != last) 59 { 60 auto && x = *first; 61 if(!invoke(pred, invoke(proj, value), invoke(proj, x))) 62 { 63 value = (decltype(x) &&)x; 64 *out = value; 65 ++out; 66 } 67 } 68 } 69 return {first, out}; 70 } 71 72 template<typename I, typename S, typename O, typename C, typename P> unique_copy_impl(I first,S last,O out,C pred,P proj,std::forward_iterator_tag,std::false_type)73 unique_copy_result<I, O> unique_copy_impl(I first, S last, O out, C pred, P proj, 74 std::forward_iterator_tag, 75 std::false_type) 76 { 77 if(first != last) 78 { 79 I tmp = first; 80 *out = *tmp; 81 ++out; 82 while(++first != last) 83 { 84 auto && x = *first; 85 if(!invoke(pred, invoke(proj, *tmp), invoke(proj, x))) 86 { 87 *out = (decltype(x) &&)x; 88 ++out; 89 tmp = first; 90 } 91 } 92 } 93 return {first, out}; 94 } 95 96 template<typename I, typename S, typename O, typename C, typename P> unique_copy_impl(I first,S last,O out,C pred,P proj,std::input_iterator_tag,std::true_type)97 unique_copy_result<I, O> unique_copy_impl(I first, S last, O out, C pred, P proj, 98 std::input_iterator_tag, std::true_type) 99 { 100 if(first != last) 101 { 102 *out = *first; 103 while(++first != last) 104 { 105 auto && x = *first; 106 if(!invoke(pred, invoke(proj, *out), invoke(proj, x))) 107 *++out = (decltype(x) &&)x; 108 } 109 ++out; 110 } 111 return {first, out}; 112 } 113 } // namespace detail 114 /// \endcond 115 RANGES_FUNC_BEGIN(unique_copy)116 RANGES_FUNC_BEGIN(unique_copy) 117 118 /// \brief template function unique_copy 119 /// 120 /// range-based version of the `unique_copy` std algorithm 121 /// 122 /// \pre `Rng` is a model of the `input_range` concept 123 /// \pre `O` is a model of the `weakly_incrementable` concept 124 /// \pre `C` is a model of the `relation` concept 125 template(typename I, 126 typename S, 127 typename O, 128 typename C = equal_to, 129 typename P = identity)( 130 /// \pre 131 requires input_iterator<I> AND sentinel_for<S, I> AND 132 indirect_relation<C, projected<I, P>> AND weakly_incrementable<O> AND 133 indirectly_copyable<I, O> AND 134 (forward_iterator<I> || forward_iterator<O> || 135 indirectly_copyable_storable<I, O>)) // 136 unique_copy_result<I, O> RANGES_FUNC(unique_copy)( 137 I first, S last, O out, C pred = C{}, P proj = P{}) // 138 { 139 return detail::unique_copy_impl(std::move(first), 140 std::move(last), 141 std::move(out), 142 std::move(pred), 143 std::move(proj), 144 iterator_tag_of<I>(), 145 meta::bool_<forward_iterator<O>>{}); 146 } 147 148 /// \overload 149 template(typename Rng, typename O, typename C = equal_to, typename P = identity)( 150 /// \pre 151 requires input_range<Rng> AND 152 indirect_relation<C, projected<iterator_t<Rng>, P>> AND 153 weakly_incrementable<O> AND indirectly_copyable<iterator_t<Rng>, O> AND 154 (forward_iterator<iterator_t<Rng>> || forward_iterator<O> || 155 indirectly_copyable_storable<iterator_t<Rng>, O>)) // 156 unique_copy_result<borrowed_iterator_t<Rng>, O> // RANGES_FUNC(unique_copy)157 RANGES_FUNC(unique_copy)(Rng && rng, O out, C pred = C{}, P proj = P{}) // 158 { 159 return detail::unique_copy_impl(begin(rng), 160 end(rng), 161 std::move(out), 162 std::move(pred), 163 std::move(proj), 164 iterator_tag_of<iterator_t<Rng>>(), 165 meta::bool_<forward_iterator<O>>{}); 166 } 167 168 RANGES_FUNC_END(unique_copy) 169 170 namespace cpp20 171 { 172 using ranges::unique_copy; 173 using ranges::unique_copy_result; 174 } // namespace cpp20 175 /// @} 176 } // namespace ranges 177 178 #include <range/v3/detail/epilogue.hpp> 179 180 #endif 181