2 // Copyright 2013 Francisco Jerez
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:
11 // The above copyright notice and this permission notice shall be included in
12 // all copies or substantial portions of the Software.
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.
23 #ifndef CLOVER_UTIL_RANGE_HPP
24 #define CLOVER_UTIL_RANGE_HPP
29 #include "util/adaptor.hpp"
33 /// Class that identifies container types where the elements of a
34 /// range can be stored by the type conversion operator.
36 /// \a T identifies the range element type.
38 template<typename T, typename V>
39 struct range_store_traits;
41 template<typename T, typename S>
42 struct range_store_traits<T, std::vector<S>> {
48 return { r.begin(), r.end() };
52 template<typename T, typename S, std::size_t N>
53 struct range_store_traits<T, std::array<S, N>> {
57 static std::array<S, N>
60 assert(r.size() == v.size());
68 /// Common functionality that is shared by other implementations
69 /// of the container concept.
71 template<typename R, typename I, typename CI>
75 typedef CI const_iterator;
76 typedef typename std::iterator_traits<iterator>::value_type value_type;
77 typedef typename std::iterator_traits<iterator>::reference
79 typedef typename std::iterator_traits<const_iterator>::reference
81 typedef typename std::iterator_traits<iterator>::difference_type
83 typedef std::size_t size_type;
86 operator==(const basic_range &r) const {
87 return *static_cast<const R *>(this) == r;
91 operator!=(const basic_range &r) const {
97 return static_cast<R *>(this)->begin();
102 return static_cast<R *>(this)->end();
107 return static_cast<const R *>(this)->begin();
112 return static_cast<const R *>(this)->end();
115 std::reverse_iterator<iterator>
120 std::reverse_iterator<iterator>
137 return begin() == end();
142 if (i >= static_cast<const R *>(this)->size())
143 throw std::out_of_range("");
149 at(size_type i) const {
150 if (i >= static_cast<const R *>(this)->size())
151 throw std::out_of_range("");
157 operator[](size_type i) {
162 operator[](size_type i) const {
167 using store_traits = range_store_traits<
168 typename std::remove_cv<value_type>::type, V
172 typename = typename store_traits<V>::enable>
174 return store_traits<V>::create(*static_cast<const R *>(this));
180 /// Range that contains all elements delimited by an iterator pair
181 /// (\a i, \a j). Use range() as convenience constructor.
184 class iterator_range : public detail::basic_range<iterator_range<I>, I, I> {
186 typedef detail::basic_range<iterator_range<I>, I, I> super;
188 iterator_range() : i(), j() {
191 iterator_range(I i, I j) : i(i), j(j) {
195 operator==(const iterator_range &r) const {
196 return i == r.i && j == r.j;
209 typename super::size_type
211 return end() - begin();
220 using preferred_iterator_type = decltype(std::declval<T>().begin());
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.
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>...>
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>...>
244 template<typename G, typename... Rs>
245 adaptor_range(G &&f, Rs &&... os) :
246 f(std::forward<G>(f)), os(std::forward<Rs>(os)...) {
250 operator==(const adaptor_range &r) const {
251 return f == r.f && os == r.os;
254 typename super::iterator
256 return { f, tuple::map(begins(), os) };
259 typename super::iterator
261 return { f, tuple::map(advances_by(size()),
262 tuple::map(begins(), os)) };
265 typename super::const_iterator
267 return { f, tuple::map(begins(), os) };
270 typename super::const_iterator
272 return { f, tuple::map(advances_by(size()),
273 tuple::map(begins(), os)) };
276 typename super::size_type
278 return tuple::apply(minimum(), tuple::map(sizes(), os));
283 std::tuple<Os...> os;
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.
293 public detail::basic_range<slice_range<O>,
294 detail::preferred_iterator_type<O>,
295 detail::preferred_iterator_type<const O>> {
297 typedef detail::basic_range<slice_range<O>,
298 detail::preferred_iterator_type<O>,
299 detail::preferred_iterator_type<const O>
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) {
309 operator==(const slice_range &r) const {
310 return o == r.o && i == r.i && j == r.j;
313 typename super::iterator
315 return std::next(o.begin(), i);
318 typename super::iterator
320 return std::next(o.begin(), j);
323 typename super::const_iterator
325 return std::next(o.begin(), i);
328 typename super::const_iterator
330 return std::next(o.begin(), j);
333 typename super::size_type
340 typename super::size_type i, j;
344 /// Create a range from an iterator pair (\a i, \a j).
346 /// \sa iterator_range.
355 /// Create a range of \a n elements starting from iterator \a i.
357 /// \sa iterator_range.
361 range(T i, typename std::iterator_traits<T>::difference_type n) {
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.
369 /// \sa adaptor_range.
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)... };
378 /// Create a range identical to another range \a r.
381 adaptor_range<identity, R>
383 return { identity(), std::forward<R>(r) };
387 /// Create a range by taking the elements delimited by the index
388 /// pair (\a i, \a j) in a source range \a 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 };
400 /// Range that behaves as a vector of references of type \a T.
402 /// Useful because STL containers cannot contain references to
403 /// objects as elements.
406 class ref_vector : public adaptor_range<derefs, std::vector<T *>> {
408 ref_vector(std::initializer_list<std::reference_wrapper<T>> il) :
409 adaptor_range<derefs, std::vector<T *>>(derefs(), map(addresses(), il)) {
413 ref_vector(R &&r) : adaptor_range<derefs, std::vector<T *>>(
414 derefs(), map(addresses(), std::forward<R>(r))) {