• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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>
head(R && 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>
tail(R && 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>
unique(R && 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...>
zip(Rs &&...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
eval(R && r)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
for_each(F && f,Rs &&...rs)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
copy(R && r,I i)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
fold(F && f,A a,R && r)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
count(T && x,R && r)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>
find(F && f,R && 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
all_of(F && f,Rs &&...rs)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
any_of(F && f,Rs &&...rs)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
erase_if(F && f,R && r)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
219