boost/boost/counting_iterator.hpp

   1 // (C) Copyright David Abrahams and Jeremy Siek 2000-2001. Permission to copy,
   2 // use, modify, sell and distribute this software is granted provided this
   3 // copyright notice appears in all copies. This software is provided "as is"
   4 // without express or implied warranty, and with no claim as to its suitability
   5 // for any purpose.
   6 //
   7 // See http://www.boost.org for most recent version including documentation.
   8 //
   9 // Supplies:
  10 //
  11 //   template <class Incrementable> class counting_iterator_traits;
  12 //   template <class Incrementable> class counting_iterator_policies;
  13 //
  14 //     Iterator traits and policies for adapted iterators whose dereferenced
  15 //     value progresses through consecutive values of Incrementable when the
  16 //     iterator is derferenced.
  17 //
  18 //   template <class Incrementable> struct counting_iterator_generator;
  19 //
  20 //     A "type generator" whose nested type "type" is a counting iterator as
  21 //     described above.
  22 //
  23 //   template <class Incrementable>
  24 //     typename counting_iterator_generator<Incrementable>::type
  25 //     make_counting_iterator(Incrementable);
  26 //
  27 //     A function which produces an adapted counting iterator over values of
  28 //     Incrementable.
  29 //
  30 // Revision History
  31 // 14 Feb 2001  Removed unnecessary typedefs from counting_iterator_traits
  32 //              (Jeremy Siek)
  33 // 11 Feb 2001  Use BOOST_STATIC_CONSTANT (Dave Abrahams)
  34 // 11 Feb 2001  Clean up after John Maddocks's (finally effective!) Borland
  35 //              fixes (David Abrahams).
  36 // 10 Feb 2001  Use new iterator_adaptor<> interface (David Abrahams)
  37 // 10 Feb 2001  Rolled in supposed Borland fixes from John Maddock, but not
  38 //              seeing any improvement yet (David Abrahams)
  39 // 09 Feb 2001  Factored out is_numeric computation. Borland still
  40 //              unhappy :( (David Abrahams)
  41 // 08 Feb 2001  Beginning of a failed attempt to appease Borland
  42 //              (David Abrahams)
  43 // 07 Feb 2001  rename counting_iterator() -> make_counting_iterator()
  44 //              (David Abrahams)
  45 // 04 Feb 2001  Added counting_iterator_generator; updated comments
  46 //              (David Abrahams)
  47 // 24 Jan 2001  initial revision, based on Jeremy Siek's
  48 //              boost/pending/integer_range.hpp (David Abrahams)
  49
  50 #ifndef BOOST_COUNTING_ITERATOR_HPP_DWA20000119
  51 # define BOOST_COUNTING_ITERATOR_HPP_DWA20000119
  52
  53 # include <boost/config.hpp>
  54 # include <boost/detail/iterator.hpp>
  55 # include <boost/iterator_adaptors.hpp>
  56 # include <boost/type_traits.hpp>
  57 # include <boost/detail/numeric_traits.hpp>
  58 # include <boost/static_assert.hpp>
  59 # include <boost/limits.hpp>
  60
  61 namespace boost {
  62
  63 namespace detail {
  64
  65   // Template class counting_iterator_traits_select -- choose an
  66   // iterator_category and difference_type for a counting_iterator at
  67   // compile-time based on whether or not it wraps an integer or an iterator,
  68   // using "poor man's partial specialization".
  69   template <bool is_integer> struct counting_iterator_traits_select;
  70
  71   // Incrementable is an iterator type
  72   template <>
  73   struct counting_iterator_traits_select<false>
  74   {
  75       template <class Incrementable>
  76       struct traits
  77       {
  78        private:
  79           typedef boost::detail::iterator_traits<Incrementable> x;
  80        public:
  81           typedef typename x::iterator_category iterator_category;
  82           typedef typename x::difference_type difference_type;
  83       };
  84   };
  85
  86   // Incrementable is a numeric type
  87   template <>
  88   struct counting_iterator_traits_select<true>
  89   {
  90       template <class Incrementable>
  91       struct traits
  92       {
  93           typedef typename
  94             boost::detail::numeric_traits<Incrementable>::difference_type
  95           difference_type;
  96           typedef std::random_access_iterator_tag iterator_category;
  97       };
  98   };
  99
 100   // Template class distance_policy_select -- choose a policy for computing the
 101   // distance between counting_iterators at compile-time based on whether or not
 102   // the iterator wraps an integer or an iterator, using "poor man's partial
 103   // specialization".
 104
 105   template <bool is_integer> struct distance_policy_select;
 106
 107   // A policy for wrapped iterators
 108   template <>
 109   struct distance_policy_select<false>
 110   {
 111       template <class Distance, class Incrementable>
 112       struct policy {
 113           static Distance distance(Incrementable x, Incrementable y)
 114               { return boost::detail::distance(x, y); }
 115       };
 116   };
 117
 118   // A policy for wrapped numbers
 119   template <>
 120   struct distance_policy_select<true>
 121   {
 122       template <class Distance, class Incrementable>
 123       struct policy {
 124           static Distance distance(Incrementable x, Incrementable y)
 125               { return numeric_distance(x, y); }
 126       };
 127   };
 128
 129   // Try to detect numeric types at compile time in ways compatible with the
 130   // limitations of the compiler and library.
 131   template <class T>
 132   struct is_numeric {
 133     // For a while, this wasn't true, but we rely on it below. This is a regression assert.
 134     BOOST_STATIC_ASSERT(::boost::is_integral<char>::value);
 135 # ifndef BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS
 136 #  if defined(BOOST_HAS_LONG_LONG)
 137     BOOST_STATIC_CONSTANT(bool,
 138                           value = (
 139                               std::numeric_limits<T>::is_specialized
 140                               | boost::is_same<T,long long>::value
 141                               | boost::is_same<T,unsigned long long>::value));
 142 #  else
 143      BOOST_STATIC_CONSTANT(bool, value = std::numeric_limits<T>::is_specialized);
 144 #  endif
 145 # else
 146 #  if !defined(__BORLANDC__)
 147     BOOST_STATIC_CONSTANT(bool, value = (
 148         boost::is_convertible<int,T>::value && boost::is_convertible<T,int>::value));
 149 #  else
 150     BOOST_STATIC_CONSTANT(bool, value = ::boost::is_arithmetic<T>::value);
 151 #  endif
 152 # endif
 153   };
 154
 155   // Compute the distance over arbitrary numeric and/or iterator types
 156   template <class Distance, class Incrementable>
 157   Distance any_distance(Incrementable start, Incrementable finish, Distance* = 0)
 158   {
 159
 160       return distance_policy_select<(
 161           is_numeric<Incrementable>::value)>::template
 162           policy<Distance, Incrementable>::distance(start, finish);
 163   }
 164
 165 } // namespace detail
 166
 167 template <class Incrementable>
 168 struct counting_iterator_traits {
 169  private:
 170     typedef ::boost::detail::counting_iterator_traits_select<(
 171         ::boost::detail::is_numeric<Incrementable>::value
 172         )> binder;
 173     typedef typename binder::template traits<Incrementable> traits;
 174  public:
 175     typedef typename traits::difference_type difference_type;
 176     typedef typename traits::iterator_category iterator_category;
 177 };
 178
 179 template <class Incrementable>
 180 struct counting_iterator_policies : public default_iterator_policies
 181 {
 182     template <class IteratorAdaptor>
 183     typename IteratorAdaptor::reference dereference(const IteratorAdaptor& i) const
 184         { return i.base(); }
 185
 186     template <class Iterator1, class Iterator2>
 187     typename Iterator1::difference_type distance(
 188         const Iterator1& x, const Iterator2& y) const
 189     {
 190         typedef typename Iterator1::difference_type difference_type;
 191         return boost::detail::any_distance<difference_type>(
 192             x.base(), y.base());
 193     }
 194 };
 195
 196 // A type generator for counting iterators
 197 template <class Incrementable>
 198 struct counting_iterator_generator
 199 {
 200     typedef typename boost::remove_const<
 201         Incrementable
 202     >::type value_type;
 203
 204     typedef counting_iterator_traits<value_type> traits;
 205
 206     typedef iterator_adaptor<
 207         value_type
 208         , counting_iterator_policies<value_type>
 209         , value_type
 210         , value_type const&
 211         , value_type const*
 212         , typename traits::iterator_category
 213         , typename traits::difference_type
 214     > type;
 215 };
 216
 217 // Manufacture a counting iterator for an arbitrary incrementable type
 218 template <class Incrementable>
 219 inline typename counting_iterator_generator<Incrementable>::type
 220 make_counting_iterator(Incrementable x)
 221 {
 222   typedef typename counting_iterator_generator<Incrementable>::type result_t;
 223   return result_t(x);
 224 }
 225
 226
 227 } // namespace boost
 228
 229 #endif // BOOST_COUNTING_ITERATOR_HPP_DWA20000119