diff options
Diffstat (limited to 'src/gallium/frontends/clover/util/algorithm.hpp')
| -rw-r--r-- | src/gallium/frontends/clover/util/algorithm.hpp | 218 |
1 files changed, 218 insertions, 0 deletions
diff --git a/src/gallium/frontends/clover/util/algorithm.hpp b/src/gallium/frontends/clover/util/algorithm.hpp new file mode 100644 index 00000000000..1658458ee18 --- /dev/null +++ b/src/gallium/frontends/clover/util/algorithm.hpp @@ -0,0 +1,218 @@ +// +// 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 |