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