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
32namespace 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
219