1 // 2 // Copyright 2013 Francisco Jerez 3 // 4 // Permission is hereby granted, free of charge, to any person obtaining a 5 // copy of this software and associated documentation files (the "Software"), 6 // to deal in the Software without restriction, including without limitation 7 // the rights to use, copy, modify, merge, publish, distribute, sublicense, 8 // and/or sell copies of the Software, and to permit persons to whom the 9 // Software is furnished to do so, subject to the following conditions: 10 // 11 // The above copyright notice and this permission notice shall be included in 12 // all copies or substantial portions of the Software. 13 // 14 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 15 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 16 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 17 // THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR 18 // OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, 19 // ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR 20 // OTHER DEALINGS IN THE SOFTWARE. 21 // 22 23 #ifndef CLOVER_UTIL_ALGORITHM_HPP 24 #define CLOVER_UTIL_ALGORITHM_HPP 25 26 #include <algorithm> 27 #include <stdexcept> 28 29 #include "util/range.hpp" 30 #include "util/functional.hpp" 31 32 namespace clover { 33 namespace detail { 34 template<typename R> 35 using preferred_reference_type = decltype(*std::declval<R>().begin()); 36 } 37 38 /// 39 /// Return the first element in a range. 40 /// 41 template<typename R> 42 detail::preferred_reference_type<R> head(R && r)43 head(R &&r) { 44 assert(!r.empty()); 45 return r.front(); 46 } 47 48 /// 49 /// Return all elements in a range but the first. 50 /// 51 template<typename R> 52 slice_range<R> tail(R && r)53 tail(R &&r) { 54 assert(!r.empty()); 55 return { std::forward<R>(r), 1, r.size() }; 56 } 57 58 /// 59 /// Return the only element in a range. 60 /// 61 template<typename R> 62 detail::preferred_reference_type<R> unique(R && r)63 unique(R &&r) { 64 if (r.size() != 1) 65 throw std::out_of_range(""); 66 67 return r.front(); 68 } 69 70 /// 71 /// Combine a variable number of ranges element-wise in a single 72 /// range of tuples. 73 /// 74 template<typename... Rs> 75 adaptor_range<zips, Rs...> zip(Rs &&...rs)76 zip(Rs &&... rs) { 77 return map(zips(), std::forward<Rs>(rs)...); 78 } 79 80 /// 81 /// Evaluate the elements of a range. 82 /// 83 /// Useful because most of the range algorithms evaluate their 84 /// result lazily. 85 /// 86 template<typename R> 87 void eval(R && r)88 eval(R &&r) { 89 for (auto i = r.begin(), e = r.end(); i != e; ++i) 90 *i; 91 } 92 93 /// 94 /// Apply functor \a f element-wise on a variable number of ranges 95 /// \a rs. 96 /// 97 /// The functor \a f should take as many arguments as ranges are 98 /// provided. 99 /// 100 template<typename F, typename... Rs> 101 void for_each(F && f,Rs &&...rs)102 for_each(F &&f, Rs &&... rs) { 103 eval(map(std::forward<F>(f), std::forward<Rs>(rs)...)); 104 } 105 106 /// 107 /// Copy all elements from range \a r into an output container 108 /// starting from iterator \a i. 109 /// 110 template<typename R, typename I> 111 void copy(R && r,I i)112 copy(R &&r, I i) { 113 for (detail::preferred_reference_type<R> x : r) 114 *(i++) = x; 115 } 116 117 /// 118 /// Reduce the elements of range \a r by applying functor \a f 119 /// element by element. 120 /// 121 /// \a f should take an accumulator value (which is initialized to 122 /// \a a) and an element value as arguments, and return an updated 123 /// accumulator value. 124 /// 125 /// \returns The final value of the accumulator. 126 /// 127 template<typename F, typename A, typename R> 128 A fold(F && f,A a,R && r)129 fold(F &&f, A a, R &&r) { 130 for (detail::preferred_reference_type<R> x : r) 131 a = f(a, x); 132 133 return a; 134 } 135 136 /// 137 /// Return how many elements of range \a r are equal to \a x. 138 /// 139 template<typename T, typename R> 140 typename std::remove_reference<R>::type::size_type count(T && x,R && r)141 count(T &&x, R &&r) { 142 typename std::remove_reference<R>::type::size_type n = 0; 143 144 for (detail::preferred_reference_type<R> y : r) { 145 if (x == y) 146 n++; 147 } 148 149 return n; 150 } 151 152 /// 153 /// Return the first element in range \a r for which predicate \a f 154 /// evaluates to true. 155 /// 156 template<typename F, typename R> 157 detail::preferred_reference_type<R> find(F && f,R && r)158 find(F &&f, R &&r) { 159 for (detail::preferred_reference_type<R> x : r) { 160 if (f(x)) 161 return x; 162 } 163 164 throw std::out_of_range(""); 165 } 166 167 /// 168 /// Return true if the element-wise application of predicate \a f 169 /// on \a rs evaluates to true for all elements. 170 /// 171 template<typename F, typename... Rs> 172 bool all_of(F && f,Rs &&...rs)173 all_of(F &&f, Rs &&... rs) { 174 for (auto b : map(f, rs...)) { 175 if (!b) 176 return false; 177 } 178 179 return true; 180 } 181 182 /// 183 /// Return true if the element-wise application of predicate \a f 184 /// on \a rs evaluates to true for any element. 185 /// 186 template<typename F, typename... Rs> 187 bool any_of(F && f,Rs &&...rs)188 any_of(F &&f, Rs &&... rs) { 189 for (auto b : map(f, rs...)) { 190 if (b) 191 return true; 192 } 193 194 return false; 195 } 196 197 /// 198 /// Erase elements for which predicate \a f evaluates to true from 199 /// container \a r. 200 /// 201 template<typename F, typename R> 202 void erase_if(F && f,R && r)203 erase_if(F &&f, R &&r) { 204 auto i = r.begin(), e = r.end(); 205 206 for (auto j = r.begin(); j != e; ++j) { 207 if (!f(*j)) { 208 if (j != i) 209 *i = std::move(*j); 210 ++i; 211 } 212 } 213 214 r.erase(i, e); 215 } 216 } 217 218 #endif 219