src/gallium/state_trackers/clover/util/range.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_RANGE_HPP
  24 #define CLOVER_UTIL_RANGE_HPP
  25
  26 #include <array>
  27 #include <vector>
  28
  29 #include "util/adaptor.hpp"
  30
  31 namespace 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>
  42    struct range_store_traits<T, std::vector<T>> {
  43       typedef void enable;
  44
  45       template<typename R>
  46       static std::vector<T>
  47       create(const R &r) {
  48          return { r.begin(), r.end() };
  49       }
  50    };
  51
  52    template<typename T, std::size_t N>
  53    struct range_store_traits<T, std::array<T, N>> {
  54       typedef void enable;
  55
  56       template<typename R>
  57       static std::array<T, N>
  58       create(const R &r) {
  59          std::array<T, 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