boost/pending/iterator_tests.hpp

   1 // Copyright David Abrahams and Jeremy Siek 2003.
   2 // Distributed under the Boost Software License, Version 1.0. (See
   3 // accompanying file LICENSE_1_0.txt or copy at
   4 // http://www.boost.org/LICENSE_1_0.txt)
   5 #ifndef BOOST_ITERATOR_TESTS_HPP
   6 # define BOOST_ITERATOR_TESTS_HPP
   7
   8 // This is meant to be the beginnings of a comprehensive, generic
   9 // test suite for STL concepts such as iterators and containers.
  10 //
  11 // Revision History:
  12 // 28 Apr 2002  Fixed input iterator requirements.
  13 //              For a == b a++ == b++ is no longer required.
  14 //              See 24.1.1/3 for details.
  15 //              (Thomas Witt)
  16 // 08 Feb 2001  Fixed bidirectional iterator test so that
  17 //              --i is no longer a precondition.
  18 //              (Jeremy Siek)
  19 // 04 Feb 2001  Added lvalue test, corrected preconditions
  20 //              (David Abrahams)
  21
  22 # include <iterator>
  23 # include <assert.h>
  24 # include <boost/type_traits.hpp>
  25 # include <boost/static_assert.hpp>
  26 # include <boost/concept_archetype.hpp> // for detail::dummy_constructor
  27 # include <boost/implicit_cast.hpp>
  28 # include <boost/type_traits/broken_compiler_spec.hpp>
  29
  30 namespace boost {
  31
  32   // use this for the value type
  33 struct dummyT {
  34   dummyT() { }
  35   dummyT(detail::dummy_constructor) { }
  36   dummyT(int x) : m_x(x) { }
  37   int foo() const { return m_x; }
  38   bool operator==(const dummyT& d) const { return m_x == d.m_x; }
  39   int m_x;
  40 };
  41
  42 }
  43
  44 BOOST_TT_BROKEN_COMPILER_SPEC(boost::dummyT)
  45
  46 namespace boost {
  47
  48 // Tests whether type Iterator satisfies the requirements for a
  49 // TrivialIterator.
  50 // Preconditions: i != j, *i == val
  51 template <class Iterator, class T>
  52 void trivial_iterator_test(const Iterator i, const Iterator j, T val)
  53 {
  54   Iterator k;
  55   assert(i == i);
  56   assert(j == j);
  57   assert(i != j);
  58 #ifdef BOOST_NO_STD_ITERATOR_TRAITS
  59   T v = *i;
  60 #else
  61   typename std::iterator_traits<Iterator>::value_type v = *i;
  62 #endif
  63   assert(v == val);
  64 #if 0
  65   // hmm, this will give a warning for transform_iterator...  perhaps
  66   // this should be separated out into a stand-alone test since there
  67   // are several situations where it can't be used, like for
  68   // integer_range::iterator.
  69   assert(v == i->foo());
  70 #endif
  71   k = i;
  72   assert(k == k);
  73   assert(k == i);
  74   assert(k != j);
  75   assert(*k == val);
  76 }
  77
  78
  79 // Preconditions: i != j
  80 template <class Iterator, class T>
  81 void mutable_trivial_iterator_test(const Iterator i, const Iterator j, T val)
  82 {
  83   *i = val;
  84   trivial_iterator_test(i, j, val);
  85 }
  86
  87
  88 // Preconditions: *i == v1, *++i == v2
  89 template <class Iterator, class T>
  90 void input_iterator_test(Iterator i, T v1, T v2)
  91 {
  92   Iterator i1(i);
  93
  94   assert(i == i1);
  95   assert(!(i != i1));
  96
  97   // I can see no generic way to create an input iterator
  98   // that is in the domain of== of i and != i.
  99   // The following works for istream_iterator but is not
 100   // guaranteed to work for arbitrary input iterators.
 101   //
 102   //   Iterator i2;
 103   //
 104   //   assert(i != i2);
 105   //   assert(!(i == i2));
 106
 107   assert(*i1 == v1);
 108   assert(*i  == v1);
 109
 110   // we cannot test for equivalence of (void)++i & (void)i++
 111   // as i is only guaranteed to be single pass.
 112   assert(*i++ == v1);
 113
 114   i1 = i;
 115
 116   assert(i == i1);
 117   assert(!(i != i1));
 118
 119   assert(*i1 == v2);
 120   assert(*i  == v2);
 121
 122   // i is dereferencable, so it must be incrementable.
 123   ++i;
 124
 125   // how to test for operator-> ?
 126 }
 127
 128 // how to test output iterator?
 129
 130
 131 template <bool is_pointer> struct lvalue_test
 132 {
 133     template <class Iterator> static void check(Iterator)
 134     {
 135 # ifndef BOOST_NO_STD_ITERATOR_TRAITS
 136         typedef typename std::iterator_traits<Iterator>::reference reference;
 137         typedef typename std::iterator_traits<Iterator>::value_type value_type;
 138 # else
 139         typedef typename Iterator::reference reference;
 140         typedef typename Iterator::value_type value_type;
 141 # endif
 142         BOOST_STATIC_ASSERT(boost::is_reference<reference>::value);
 143         BOOST_STATIC_ASSERT((boost::is_same<reference,value_type&>::value
 144                              || boost::is_same<reference,const value_type&>::value
 145             ));
 146     }
 147 };
 148
 149 # ifdef BOOST_NO_STD_ITERATOR_TRAITS
 150 template <> struct lvalue_test<true> {
 151     template <class T> static void check(T) {}
 152 };
 153 #endif
 154
 155 template <class Iterator, class T>
 156 void forward_iterator_test(Iterator i, T v1, T v2)
 157 {
 158   input_iterator_test(i, v1, v2);
 159
 160   Iterator i1 = i, i2 = i;
 161
 162   assert(i == i1++);
 163   assert(i != ++i2);
 164
 165   trivial_iterator_test(i, i1, v1);
 166   trivial_iterator_test(i, i2, v1);
 167
 168   ++i;
 169   assert(i == i1);
 170   assert(i == i2);
 171   ++i1;
 172   ++i2;
 173
 174   trivial_iterator_test(i, i1, v2);
 175   trivial_iterator_test(i, i2, v2);
 176
 177  // borland doesn't allow non-type template parameters
 178 # if !defined(__BORLANDC__) || (__BORLANDC__ > 0x551)
 179   lvalue_test<(boost::is_pointer<Iterator>::value)>::check(i);
 180 #endif
 181 }
 182
 183 // Preconditions: *i == v1, *++i == v2
 184 template <class Iterator, class T>
 185 void bidirectional_iterator_test(Iterator i, T v1, T v2)
 186 {
 187   forward_iterator_test(i, v1, v2);
 188   ++i;
 189
 190   Iterator i1 = i, i2 = i;
 191
 192   assert(i == i1--);
 193   assert(i != --i2);
 194
 195   trivial_iterator_test(i, i1, v2);
 196   trivial_iterator_test(i, i2, v2);
 197
 198   --i;
 199   assert(i == i1);
 200   assert(i == i2);
 201   ++i1;
 202   ++i2;
 203
 204   trivial_iterator_test(i, i1, v1);
 205   trivial_iterator_test(i, i2, v1);
 206 }
 207
 208 // mutable_bidirectional_iterator_test
 209
 210 template <class U> struct undefined;
 211
 212 // Preconditions: [i,i+N) is a valid range
 213 template <class Iterator, class TrueVals>
 214 void random_access_iterator_test(Iterator i, int N, TrueVals vals)
 215 {
 216   bidirectional_iterator_test(i, vals[0], vals[1]);
 217   const Iterator j = i;
 218   int c;
 219
 220   typedef typename boost::detail::iterator_traits<Iterator>::value_type value_type;
 221
 222   for (c = 0; c < N-1; ++c) {
 223     assert(i == j + c);
 224     assert(*i == vals[c]);
 225     assert(*i == boost::implicit_cast<value_type>(j[c]));
 226     assert(*i == *(j + c));
 227     assert(*i == *(c + j));
 228     ++i;
 229     assert(i > j);
 230     assert(i >= j);
 231     assert(j <= i);
 232     assert(j < i);
 233   }
 234
 235   Iterator k = j + N - 1;
 236   for (c = 0; c < N-1; ++c) {
 237     assert(i == k - c);
 238     assert(*i == vals[N - 1 - c]);
 239     assert(*i == boost::implicit_cast<value_type>(j[N - 1 - c]));
 240     Iterator q = k - c;
 241     assert(*i == *q);
 242     assert(i > j);
 243     assert(i >= j);
 244     assert(j <= i);
 245     assert(j < i);
 246     --i;
 247   }
 248 }
 249
 250 // Precondition: i != j
 251 template <class Iterator, class ConstIterator>
 252 void const_nonconst_iterator_test(Iterator i, ConstIterator j)
 253 {
 254   assert(i != j);
 255   assert(j != i);
 256
 257   ConstIterator k(i);
 258   assert(k == i);
 259   assert(i == k);
 260
 261   k = i;
 262   assert(k == i);
 263   assert(i == k);
 264 }
 265
 266 } // namespace boost
 267
 268 #endif // BOOST_ITERATOR_TESTS_HPP