| // |
| // Copyright 2013 Francisco Jerez |
| // |
| // Permission is hereby granted, free of charge, to any person obtaining a |
| // copy of this software and associated documentation files (the "Software"), |
| // to deal in the Software without restriction, including without limitation |
| // the rights to use, copy, modify, merge, publish, distribute, sublicense, |
| // and/or sell copies of the Software, and to permit persons to whom the |
| // Software is furnished to do so, subject to the following conditions: |
| // |
| // The above copyright notice and this permission notice shall be included in |
| // all copies or substantial portions of the Software. |
| // |
| // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
| // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
| // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL |
| // THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR |
| // OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, |
| // ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR |
| // OTHER DEALINGS IN THE SOFTWARE. |
| // |
| |
| #ifndef CLOVER_UTIL_ALGORITHM_HPP |
| #define CLOVER_UTIL_ALGORITHM_HPP |
| |
| #include <algorithm> |
| #include <stdexcept> |
| |
| #include "util/range.hpp" |
| #include "util/functional.hpp" |
| |
| namespace clover { |
| namespace detail { |
| template<typename R> |
| using preferred_reference_type = decltype(*std::declval<R>().begin()); |
| } |
| |
| /// |
| /// Return the first element in a range. |
| /// |
| template<typename R> |
| detail::preferred_reference_type<R> |
| head(R &&r) { |
| assert(!r.empty()); |
| return r.front(); |
| } |
| |
| /// |
| /// Return all elements in a range but the first. |
| /// |
| template<typename R> |
| slice_range<R> |
| tail(R &&r) { |
| assert(!r.empty()); |
| return { std::forward<R>(r), 1, r.size() }; |
| } |
| |
| /// |
| /// Return the only element in a range. |
| /// |
| template<typename R> |
| detail::preferred_reference_type<R> |
| unique(R &&r) { |
| if (r.size() != 1) |
| throw std::out_of_range(""); |
| |
| return r.front(); |
| } |
| |
| /// |
| /// Combine a variable number of ranges element-wise in a single |
| /// range of tuples. |
| /// |
| template<typename... Rs> |
| adaptor_range<zips, Rs...> |
| zip(Rs &&... rs) { |
| return map(zips(), std::forward<Rs>(rs)...); |
| } |
| |
| /// |
| /// Evaluate the elements of a range. |
| /// |
| /// Useful because most of the range algorithms evaluate their |
| /// result lazily. |
| /// |
| template<typename R> |
| void |
| eval(R &&r) { |
| for (auto i = r.begin(), e = r.end(); i != e; ++i) |
| *i; |
| } |
| |
| /// |
| /// Apply functor \a f element-wise on a variable number of ranges |
| /// \a rs. |
| /// |
| /// The functor \a f should take as many arguments as ranges are |
| /// provided. |
| /// |
| template<typename F, typename... Rs> |
| void |
| for_each(F &&f, Rs &&... rs) { |
| eval(map(std::forward<F>(f), std::forward<Rs>(rs)...)); |
| } |
| |
| /// |
| /// Copy all elements from range \a r into an output container |
| /// starting from iterator \a i. |
| /// |
| template<typename R, typename I> |
| void |
| copy(R &&r, I i) { |
| for (detail::preferred_reference_type<R> x : r) |
| *(i++) = x; |
| } |
| |
| /// |
| /// Reduce the elements of range \a r by applying functor \a f |
| /// element by element. |
| /// |
| /// \a f should take an accumulator value (which is initialized to |
| /// \a a) and an element value as arguments, and return an updated |
| /// accumulator value. |
| /// |
| /// \returns The final value of the accumulator. |
| /// |
| template<typename F, typename A, typename R> |
| A |
| fold(F &&f, A a, R &&r) { |
| for (detail::preferred_reference_type<R> x : r) |
| a = f(a, x); |
| |
| return a; |
| } |
| |
| /// |
| /// Return how many elements of range \a r are equal to \a x. |
| /// |
| template<typename T, typename R> |
| typename std::remove_reference<R>::type::size_type |
| count(T &&x, R &&r) { |
| typename std::remove_reference<R>::type::size_type n = 0; |
| |
| for (detail::preferred_reference_type<R> y : r) { |
| if (x == y) |
| n++; |
| } |
| |
| return n; |
| } |
| |
| /// |
| /// Return the first element in range \a r for which predicate \a f |
| /// evaluates to true. |
| /// |
| template<typename F, typename R> |
| detail::preferred_reference_type<R> |
| find(F &&f, R &&r) { |
| for (detail::preferred_reference_type<R> x : r) { |
| if (f(x)) |
| return x; |
| } |
| |
| throw std::out_of_range(""); |
| } |
| |
| /// |
| /// Return true if the element-wise application of predicate \a f |
| /// on \a rs evaluates to true for all elements. |
| /// |
| template<typename F, typename... Rs> |
| bool |
| all_of(F &&f, Rs &&... rs) { |
| for (auto b : map(f, rs...)) { |
| if (!b) |
| return false; |
| } |
| |
| return true; |
| } |
| |
| /// |
| /// Return true if the element-wise application of predicate \a f |
| /// on \a rs evaluates to true for any element. |
| /// |
| template<typename F, typename... Rs> |
| bool |
| any_of(F &&f, Rs &&... rs) { |
| for (auto b : map(f, rs...)) { |
| if (b) |
| return true; |
| } |
| |
| return false; |
| } |
| |
| /// |
| /// Erase elements for which predicate \a f evaluates to true from |
| /// container \a r. |
| /// |
| template<typename F, typename R> |
| void |
| erase_if(F &&f, R &&r) { |
| auto i = r.begin(), e = r.end(); |
| |
| for (auto j = r.begin(); j != e; ++j) { |
| if (!f(*j)) { |
| if (j != i) |
| *i = std::move(*j); |
| ++i; |
| } |
| } |
| |
| r.erase(i, e); |
| } |
| } |
| |
| #endif |