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_RANGE_HPP
24#define CLOVER_UTIL_RANGE_HPP
25
26#include <array>
27#include <vector>
28
29#include "util/adaptor.hpp"
30
31namespace clover {
32   ///
33   /// Class that identifies container types where the elements of a
34   /// range can be stored by the type conversion operator.
35   ///
36   /// \a T identifies the range element type.
37   ///
38   template<typename T, typename V>
39   struct range_store_traits;
40
41   template<typename T, typename S>
42   struct range_store_traits<T, std::vector<S>> {
43      typedef void enable;
44
45      template<typename R>
46      static std::vector<S>
47      create(const R &r) {
48         return { r.begin(), r.end() };
49      }
50   };
51
52   template<typename T, typename S, std::size_t N>
53   struct range_store_traits<T, std::array<S, N>> {
54      typedef void enable;
55
56      template<typename R>
57      static std::array<S, N>
58      create(const R &r) {
59         std::array<S, N> v;
60         assert(r.size() == v.size());
61         copy(r, v.begin());
62         return v;
63      }
64   };
65
66   namespace detail {
67      ///
68      /// Common functionality that is shared by other implementations
69      /// of the container concept.
70      ///
71      template<typename R, typename I, typename CI>
72      class basic_range {
73      public:
74         typedef I iterator;
75         typedef CI const_iterator;
76         typedef typename std::iterator_traits<iterator>::value_type value_type;
77         typedef typename std::iterator_traits<iterator>::reference
78            reference;
79         typedef typename std::iterator_traits<const_iterator>::reference
80            const_reference;
81         typedef typename std::iterator_traits<iterator>::difference_type
82            difference_type;
83         typedef std::size_t size_type;
84
85         bool
86         operator==(const basic_range &r) const {
87            return *static_cast<const R *>(this) == r;
88         }
89
90         bool
91         operator!=(const basic_range &r) const {
92            return !(*this == r);
93         }
94
95         iterator
96         begin() {
97            return static_cast<R *>(this)->begin();
98         }
99
100         iterator
101         end() {
102            return static_cast<R *>(this)->end();
103         }
104
105         const_iterator
106         begin() const {
107            return static_cast<const R *>(this)->begin();
108         }
109
110         const_iterator
111         end() const {
112            return static_cast<const R *>(this)->end();
113         }
114
115         std::reverse_iterator<iterator>
116         rbegin() {
117            return { begin() };
118         }
119
120         std::reverse_iterator<iterator>
121         rend() {
122            return { end() };
123         }
124
125         reference
126         front() {
127            return *begin();
128         }
129
130         reference
131         back() {
132            return *(end() - 1);
133         }
134
135         bool
136         empty() const {
137            return begin() == end();
138         }
139
140         reference
141         at(size_type i) {
142            if (i >= static_cast<const R *>(this)->size())
143               throw std::out_of_range("");
144
145            return begin()[i];
146         }
147
148         const_reference
149         at(size_type i) const {
150            if (i >= static_cast<const R *>(this)->size())
151               throw std::out_of_range("");
152
153            return begin()[i];
154         }
155
156         reference
157         operator[](size_type i) {
158            return begin()[i];
159         }
160
161         const_reference
162         operator[](size_type i) const {
163            return begin()[i];
164         }
165
166         template<typename V>
167         using store_traits = range_store_traits<
168               typename std::remove_cv<value_type>::type, V
169            >;
170
171         template<typename V,
172                  typename = typename store_traits<V>::enable>
173         operator V() const {
174            return store_traits<V>::create(*static_cast<const R *>(this));
175         }
176      };
177   }
178
179   ///
180   /// Range that contains all elements delimited by an iterator pair
181   /// (\a i, \a j).  Use range() as convenience constructor.
182   ///
183   template<typename I>
184   class iterator_range : public detail::basic_range<iterator_range<I>, I, I> {
185   public:
186      typedef detail::basic_range<iterator_range<I>, I, I> super;
187
188      iterator_range() : i(), j() {
189      }
190
191      iterator_range(I i, I j) : i(i), j(j) {
192      }
193
194      bool
195      operator==(const iterator_range &r) const {
196         return i == r.i && j == r.j;
197      }
198
199      I
200      begin() const {
201         return i;
202      }
203
204      I
205      end() const {
206         return j;
207      }
208
209      typename super::size_type
210      size() const {
211         return end() - begin();
212      }
213
214   private:
215      I i, j;
216   };
217
218   namespace detail {
219      template<typename T>
220      using preferred_iterator_type = decltype(std::declval<T>().begin());
221   }
222
223   ///
224   /// Range that transforms the contents of a number of source ranges
225   /// \a os element-wise by using the provided functor \a f.  Use
226   /// map() as convenience constructor.
227   ///
228   template<typename F, typename... Os>
229   class adaptor_range :
230      public detail::basic_range<adaptor_range<F, Os...>,
231                                 detail::iterator_adaptor<
232                                    F, detail::preferred_iterator_type<Os>...>,
233                                 detail::iterator_adaptor<
234                                    F, detail::preferred_iterator_type<const Os>...>
235                                 > {
236   public:
237      typedef detail::basic_range<adaptor_range<F, Os...>,
238                                  detail::iterator_adaptor<
239                                     F, detail::preferred_iterator_type<Os>...>,
240                                  detail::iterator_adaptor<
241                                     F, detail::preferred_iterator_type<const Os>...>
242                                  > super;
243
244      template<typename G, typename... Rs>
245      adaptor_range(G &&f, Rs &&... os) :
246         f(std::forward<G>(f)), os(std::forward<Rs>(os)...) {
247      }
248
249      bool
250      operator==(const adaptor_range &r) const {
251         return f == r.f && os == r.os;
252      }
253
254      typename super::iterator
255      begin() {
256         return { f, tuple::map(begins(), os) };
257      }
258
259      typename super::iterator
260      end() {
261         return { f, tuple::map(advances_by(size()),
262                                tuple::map(begins(), os)) };
263      }
264
265      typename super::const_iterator
266      begin() const {
267         return { f, tuple::map(begins(), os) };
268      }
269
270      typename super::const_iterator
271      end() const {
272         return { f, tuple::map(advances_by(size()),
273                                tuple::map(begins(), os)) };
274      }
275
276      typename super::size_type
277      size() const {
278         return tuple::apply(minimum(), tuple::map(sizes(), os));
279      }
280
281   private:
282      F f;
283      std::tuple<Os...> os;
284   };
285
286   ///
287   /// Range that contains all elements delimited by the index pair
288   /// (\a i, \a j) in the source range \a r.  Use slice() as
289   /// convenience constructor.
290   ///
291   template<typename O>
292   class slice_range :
293      public detail::basic_range<slice_range<O>,
294                                 detail::preferred_iterator_type<O>,
295                                 detail::preferred_iterator_type<const O>> {
296   public:
297      typedef detail::basic_range<slice_range<O>,
298                                 detail::preferred_iterator_type<O>,
299                                 detail::preferred_iterator_type<const O>
300                                  > super;
301
302      template<typename R>
303      slice_range(R &&r, typename super::size_type i,
304                  typename super::size_type j) :
305         o(std::forward<R>(r)), i(i), j(j) {
306      }
307
308      bool
309      operator==(const slice_range &r) const {
310         return o == r.o && i == r.i && j == r.j;
311      }
312
313      typename super::iterator
314      begin() {
315         return std::next(o.begin(), i);
316      }
317
318      typename super::iterator
319      end() {
320         return std::next(o.begin(), j);
321      }
322
323      typename super::const_iterator
324      begin() const {
325         return std::next(o.begin(), i);
326      }
327
328      typename super::const_iterator
329      end() const {
330         return std::next(o.begin(), j);
331      }
332
333      typename super::size_type
334      size() const {
335         return j - i;
336      }
337
338   private:
339      O o;
340      typename super::size_type i, j;
341   };
342
343   ///
344   /// Create a range from an iterator pair (\a i, \a j).
345   ///
346   /// \sa iterator_range.
347   ///
348   template<typename T>
349   iterator_range<T>
350   range(T i, T j) {
351      return { i, j };
352   }
353
354   ///
355   /// Create a range of \a n elements starting from iterator \a i.
356   ///
357   /// \sa iterator_range.
358   ///
359   template<typename T>
360   iterator_range<T>
361   range(T i, typename std::iterator_traits<T>::difference_type n) {
362      return { i, i + n };
363   }
364
365   ///
366   /// Create a range by transforming the contents of a number of
367   /// source ranges \a rs element-wise using a provided functor \a f.
368   ///
369   /// \sa adaptor_range.
370   ///
371   template<typename F, typename... Rs>
372   adaptor_range<F, Rs...>
373   map(F &&f, Rs &&... rs) {
374      return { std::forward<F>(f), std::forward<Rs>(rs)... };
375   }
376
377   ///
378   /// Create a range identical to another range \a r.
379   ///
380   template<typename R>
381   adaptor_range<identity, R>
382   range(R &&r) {
383      return { identity(), std::forward<R>(r) };
384   }
385
386   ///
387   /// Create a range by taking the elements delimited by the index
388   /// pair (\a i, \a j) in a source range \a r.
389   ///
390   /// \sa slice_range.
391   ///
392   template<typename R>
393   slice_range<R>
394   slice(R &&r, typename slice_range<R>::size_type i,
395         typename slice_range<R>::size_type j) {
396      return { std::forward<R>(r), i, j };
397   }
398
399   ///
400   /// Range that behaves as a vector of references of type \a T.
401   ///
402   /// Useful because STL containers cannot contain references to
403   /// objects as elements.
404   ///
405   template<typename T>
406   class ref_vector : public adaptor_range<derefs, std::vector<T *>> {
407   public:
408      ref_vector(std::initializer_list<std::reference_wrapper<T>> il) :
409         adaptor_range<derefs, std::vector<T *>>(derefs(), map(addresses(), il)) {
410      }
411
412      template<typename R>
413      ref_vector(R &&r) : adaptor_range<derefs, std::vector<T *>>(
414         derefs(), map(addresses(), std::forward<R>(r))) {
415      }
416   };
417}
418
419#endif
420