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