//
// 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