clover/util/range.hpp

//
// Copyright 2013 Francisco Jerez
//
// Permission is hereby granted, free of charge, to any person obtaining a
// copy of this software and associated documentation files (the "Software"),
// to deal in the Software without restriction, including without limitation
// the rights to use, copy, modify, merge, publish, distribute, sublicense,
// and/or sell copies of the Software, and to permit persons to whom the
// Software is furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
// THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
// OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
// ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
// OTHER DEALINGS IN THE SOFTWARE.
//

#ifndef CLOVER_UTIL_RANGE_HPP
#define CLOVER_UTIL_RANGE_HPP

#include <array>
#include <vector>

#include "util/adaptor.hpp"

namespace clover {
   ///
   /// Class that identifies container types where the elements of a
   /// range can be stored by the type conversion operator.
   ///
   /// \a T identifies the range element type.
   ///
   template<typename T, typename V>
   struct range_store_traits;

   template<typename T, typename S>
   struct range_store_traits<T, std::vector<S>> {
      typedef void enable;

      template<typename R>
      static std::vector<S>
      create(const R &r) {
         return { r.begin(), r.end() };
      }
   };

   template<typename T, typename S, std::size_t N>
   struct range_store_traits<T, std::array<S, N>> {
      typedef void enable;

      template<typename R>
      static std::array<S, N>
      create(const R &r) {
         std::array<S, N> v;
         assert(r.size() == v.size());
         copy(r, v.begin());
         return v;
      }
   };

   namespace detail {
      ///
      /// Common functionality that is shared by other implementations
      /// of the container concept.
      ///
      template<typename R, typename I, typename CI>
      class basic_range {
      public:
         typedef I iterator;
         typedef CI const_iterator;
         typedef typename std::iterator_traits<iterator>::value_type value_type;
         typedef typename std::iterator_traits<iterator>::reference
            reference;
         typedef typename std::iterator_traits<const_iterator>::reference
            const_reference;
         typedef typename std::iterator_traits<iterator>::difference_type
            difference_type;
         typedef std::size_t size_type;

         bool
         operator==(const basic_range &r) const {
            return *static_cast<const R *>(this) == r;
         }

         bool
         operator!=(const basic_range &r) const {
            return !(*this == r);
         }

         iterator
         begin() {
            return static_cast<R *>(this)->begin();
         }

         iterator
         end() {
            return static_cast<R *>(this)->end();
         }

         const_iterator
         begin() const {
            return static_cast<const R *>(this)->begin();
         }

         const_iterator
         end() const {
            return static_cast<const R *>(this)->end();
         }

         std::reverse_iterator<iterator>
         rbegin() {
            return { begin() };
         }

         std::reverse_iterator<iterator>
         rend() {
            return { end() };
         }

         reference
         front() {
            return *begin();
         }

         reference
         back() {
            return *(end() - 1);
         }

         bool
         empty() const {
            return begin() == end();
         }

         reference
         at(size_type i) {
            if (i >= static_cast<const R *>(this)->size())
               throw std::out_of_range("");

            return begin()[i];
         }

         const_reference
         at(size_type i) const {
            if (i >= static_cast<const R *>(this)->size())
               throw std::out_of_range("");

            return begin()[i];
         }

         reference
         operator[](size_type i) {
            return begin()[i];
         }

         const_reference
         operator[](size_type i) const {
            return begin()[i];
         }

         template<typename V>
         using store_traits = range_store_traits<
               typename std::remove_cv<value_type>::type, V
            >;

         template<typename V,
                  typename = typename store_traits<V>::enable>
         operator V() const {
            return store_traits<V>::create(*static_cast<const R *>(this));
         }
      };
   }

   ///
   /// Range that contains all elements delimited by an iterator pair
   /// (\a i, \a j).  Use range() as convenience constructor.
   ///
   template<typename I>
   class iterator_range : public detail::basic_range<iterator_range<I>, I, I> {
   public:
      typedef detail::basic_range<iterator_range<I>, I, I> super;

      iterator_range() : i(), j() {
      }

      iterator_range(I i, I j) : i(i), j(j) {
      }

      bool
      operator==(const iterator_range &r) const {
         return i == r.i && j == r.j;
      }

      I
      begin() const {
         return i;
      }

      I
      end() const {
         return j;
      }

      typename super::size_type
      size() const {
         return end() - begin();
      }

   private:
      I i, j;
   };

   namespace detail {
      template<typename T>
      using preferred_iterator_type = decltype(std::declval<T>().begin());
   }

   ///
   /// Range that transforms the contents of a number of source ranges
   /// \a os element-wise by using the provided functor \a f.  Use
   /// map() as convenience constructor.
   ///
   template<typename F, typename... Os>
   class adaptor_range :
      public detail::basic_range<adaptor_range<F, Os...>,
                                 detail::iterator_adaptor<
                                    F, detail::preferred_iterator_type<Os>...>,
                                 detail::iterator_adaptor<
                                    F, detail::preferred_iterator_type<const Os>...>
                                 > {
   public:
      typedef detail::basic_range<adaptor_range<F, Os...>,
                                  detail::iterator_adaptor<
                                     F, detail::preferred_iterator_type<Os>...>,
                                  detail::iterator_adaptor<
                                     F, detail::preferred_iterator_type<const Os>...>
                                  > super;

      template<typename G, typename... Rs>
      adaptor_range(G &&f, Rs &&... os) :
         f(std::forward<G>(f)), os(std::forward<Rs>(os)...) {
      }

      bool
      operator==(const adaptor_range &r) const {
         return f == r.f && os == r.os;
      }

      typename super::iterator
      begin() {
         return { f, tuple::map(begins(), os) };
      }

      typename super::iterator
      end() {
         return { f, tuple::map(advances_by(size()),
                                tuple::map(begins(), os)) };
      }

      typename super::const_iterator
      begin() const {
         return { f, tuple::map(begins(), os) };
      }

      typename super::const_iterator
      end() const {
         return { f, tuple::map(advances_by(size()),
                                tuple::map(begins(), os)) };
      }

      typename super::size_type
      size() const {
         return tuple::apply(minimum(), tuple::map(sizes(), os));
      }

   private:
      F f;
      std::tuple<Os...> os;
   };

   ///
   /// Range that contains all elements delimited by the index pair
   /// (\a i, \a j) in the source range \a r.  Use slice() as
   /// convenience constructor.
   ///
   template<typename O>
   class slice_range :
      public detail::basic_range<slice_range<O>,
                                 detail::preferred_iterator_type<O>,
                                 detail::preferred_iterator_type<const O>> {
   public:
      typedef detail::basic_range<slice_range<O>,
                                 detail::preferred_iterator_type<O>,
                                 detail::preferred_iterator_type<const O>
                                  > super;

      template<typename R>
      slice_range(R &&r, typename super::size_type i,
                  typename super::size_type j) :
         o(std::forward<R>(r)), i(i), j(j) {
      }

      bool
      operator==(const slice_range &r) const {
         return o == r.o && i == r.i && j == r.j;
      }

      typename super::iterator
      begin() {
         return std::next(o.begin(), i);
      }

      typename super::iterator
      end() {
         return std::next(o.begin(), j);
      }

      typename super::const_iterator
      begin() const {
         return std::next(o.begin(), i);
      }

      typename super::const_iterator
      end() const {
         return std::next(o.begin(), j);
      }

      typename super::size_type
      size() const {
         return j - i;
      }

   private:
      O o;
      typename super::size_type i, j;
   };

   ///
   /// Create a range from an iterator pair (\a i, \a j).
   ///
   /// \sa iterator_range.
   ///
   template<typename T>
   iterator_range<T>
   range(T i, T j) {
      return { i, j };
   }

   ///
   /// Create a range of \a n elements starting from iterator \a i.
   ///
   /// \sa iterator_range.
   ///
   template<typename T>
   iterator_range<T>
   range(T i, typename std::iterator_traits<T>::difference_type n) {
      return { i, i + n };
   }

   ///
   /// Create a range by transforming the contents of a number of
   /// source ranges \a rs element-wise using a provided functor \a f.
   ///
   /// \sa adaptor_range.
   ///
   template<typename F, typename... Rs>
   adaptor_range<F, Rs...>
   map(F &&f, Rs &&... rs) {
      return { std::forward<F>(f), std::forward<Rs>(rs)... };
   }

   ///
   /// Create a range identical to another range \a r.
   ///
   template<typename R>
   adaptor_range<identity, R>
   range(R &&r) {
      return { identity(), std::forward<R>(r) };
   }

   ///
   /// Create a range by taking the elements delimited by the index
   /// pair (\a i, \a j) in a source range \a r.
   ///
   /// \sa slice_range.
   ///
   template<typename R>
   slice_range<R>
   slice(R &&r, typename slice_range<R>::size_type i,
         typename slice_range<R>::size_type j) {
      return { std::forward<R>(r), i, j };
   }

   ///
   /// Range that behaves as a vector of references of type \a T.
   ///
   /// Useful because STL containers cannot contain references to
   /// objects as elements.
   ///
   template<typename T>
   class ref_vector : public adaptor_range<derefs, std::vector<T *>> {
   public:
      ref_vector(std::initializer_list<std::reference_wrapper<T>> il) :
         adaptor_range<derefs, std::vector<T *>>(derefs(), map(addresses(), il)) {
      }

      template<typename R>
      ref_vector(R &&r) : adaptor_range<derefs, std::vector<T *>>(
         derefs(), map(addresses(), std::forward<R>(r))) {
      }
   };
}

#endif