src/gallium/frontends/clover/util/algorithm.hpp

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