Chris@16: // Copyright David Abrahams and Jeremy Siek 2003.
Chris@16: // Distributed under the Boost Software License, Version 1.0. (See
Chris@16: // accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: #ifndef BOOST_ITERATOR_TESTS_HPP
Chris@16: # define BOOST_ITERATOR_TESTS_HPP
Chris@16: 
Chris@16: // This is meant to be the beginnings of a comprehensive, generic
Chris@16: // test suite for STL concepts such as iterators and containers.
Chris@16: //
Chris@16: // Revision History:
Chris@16: // 28 Apr 2002  Fixed input iterator requirements.
Chris@16: //              For a == b a++ == b++ is no longer required.
Chris@16: //              See 24.1.1/3 for details.
Chris@16: //              (Thomas Witt)
Chris@16: // 08 Feb 2001  Fixed bidirectional iterator test so that
Chris@16: //              --i is no longer a precondition.
Chris@16: //              (Jeremy Siek)
Chris@16: // 04 Feb 2001  Added lvalue test, corrected preconditions
Chris@16: //              (David Abrahams)
Chris@16: 
Chris@16: # include <iterator>
Chris@16: # include <assert.h>
Chris@16: # include <boost/type_traits.hpp>
Chris@16: # include <boost/static_assert.hpp>
Chris@16: # include <boost/concept_archetype.hpp> // for detail::dummy_constructor
Chris@16: # include <boost/implicit_cast.hpp>
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16:   // use this for the value type
Chris@101: struct dummyT {
Chris@16:   dummyT() { }
Chris@16:   dummyT(detail::dummy_constructor) { }
Chris@16:   dummyT(int x) : m_x(x) { }
Chris@101:   int foo() const { return m_x; }
Chris@16:   bool operator==(const dummyT& d) const { return m_x == d.m_x; }
Chris@16:   int m_x;
Chris@16: };
Chris@16: 
Chris@16: }
Chris@16: 
Chris@16: namespace boost {
Chris@101: namespace iterators {
Chris@16: 
Chris@16: // Tests whether type Iterator satisfies the requirements for a
Chris@101: // TrivialIterator.
Chris@16: // Preconditions: i != j, *i == val
Chris@16: template <class Iterator, class T>
Chris@16: void trivial_iterator_test(const Iterator i, const Iterator j, T val)
Chris@16: {
Chris@16:   Iterator k;
Chris@16:   assert(i == i);
Chris@16:   assert(j == j);
Chris@16:   assert(i != j);
Chris@16: #ifdef BOOST_NO_STD_ITERATOR_TRAITS
Chris@16:   T v = *i;
Chris@16: #else
Chris@16:   typename std::iterator_traits<Iterator>::value_type v = *i;
Chris@16: #endif
Chris@16:   assert(v == val);
Chris@16: #if 0
Chris@16:   // hmm, this will give a warning for transform_iterator...  perhaps
Chris@16:   // this should be separated out into a stand-alone test since there
Chris@16:   // are several situations where it can't be used, like for
Chris@16:   // integer_range::iterator.
Chris@16:   assert(v == i->foo());
Chris@16: #endif
Chris@16:   k = i;
Chris@16:   assert(k == k);
Chris@16:   assert(k == i);
Chris@16:   assert(k != j);
Chris@16:   assert(*k == val);
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: // Preconditions: i != j
Chris@16: template <class Iterator, class T>
Chris@16: void mutable_trivial_iterator_test(const Iterator i, const Iterator j, T val)
Chris@16: {
Chris@16:   *i = val;
Chris@16:   trivial_iterator_test(i, j, val);
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: // Preconditions: *i == v1, *++i == v2
Chris@16: template <class Iterator, class T>
Chris@101: void input_iterator_test(Iterator i, T v1, T v2)
Chris@16: {
Chris@16:   Iterator i1(i);
Chris@16: 
Chris@16:   assert(i == i1);
Chris@16:   assert(!(i != i1));
Chris@16: 
Chris@16:   // I can see no generic way to create an input iterator
Chris@16:   // that is in the domain of== of i and != i.
Chris@16:   // The following works for istream_iterator but is not
Chris@16:   // guaranteed to work for arbitrary input iterators.
Chris@16:   //
Chris@16:   //   Iterator i2;
Chris@16:   //
Chris@16:   //   assert(i != i2);
Chris@16:   //   assert(!(i == i2));
Chris@16: 
Chris@16:   assert(*i1 == v1);
Chris@16:   assert(*i  == v1);
Chris@16: 
Chris@16:   // we cannot test for equivalence of (void)++i & (void)i++
Chris@16:   // as i is only guaranteed to be single pass.
Chris@16:   assert(*i++ == v1);
Chris@16: 
Chris@16:   i1 = i;
Chris@16: 
Chris@16:   assert(i == i1);
Chris@16:   assert(!(i != i1));
Chris@16: 
Chris@16:   assert(*i1 == v2);
Chris@16:   assert(*i  == v2);
Chris@16: 
Chris@16:   // i is dereferencable, so it must be incrementable.
Chris@16:   ++i;
Chris@16: 
Chris@16:   // how to test for operator-> ?
Chris@16: }
Chris@16: 
Chris@16: // how to test output iterator?
Chris@16: 
Chris@16: 
Chris@16: template <bool is_pointer> struct lvalue_test
Chris@16: {
Chris@16:     template <class Iterator> static void check(Iterator)
Chris@16:     {
Chris@16: # ifndef BOOST_NO_STD_ITERATOR_TRAITS
Chris@16:         typedef typename std::iterator_traits<Iterator>::reference reference;
Chris@16:         typedef typename std::iterator_traits<Iterator>::value_type value_type;
Chris@16: # else
Chris@16:         typedef typename Iterator::reference reference;
Chris@16:         typedef typename Iterator::value_type value_type;
Chris@16: # endif
Chris@16:         BOOST_STATIC_ASSERT(boost::is_reference<reference>::value);
Chris@16:         BOOST_STATIC_ASSERT((boost::is_same<reference,value_type&>::value
Chris@16:                              || boost::is_same<reference,const value_type&>::value
Chris@16:             ));
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: # ifdef BOOST_NO_STD_ITERATOR_TRAITS
Chris@16: template <> struct lvalue_test<true> {
Chris@16:     template <class T> static void check(T) {}
Chris@16: };
Chris@16: #endif
Chris@16: 
Chris@16: template <class Iterator, class T>
Chris@101: void forward_iterator_test(Iterator i, T v1, T v2)
Chris@16: {
Chris@16:   input_iterator_test(i, v1, v2);
Chris@16: 
Chris@16:   Iterator i1 = i, i2 = i;
Chris@16: 
Chris@16:   assert(i == i1++);
Chris@16:   assert(i != ++i2);
Chris@16: 
Chris@16:   trivial_iterator_test(i, i1, v1);
Chris@16:   trivial_iterator_test(i, i2, v1);
Chris@16: 
Chris@16:   ++i;
Chris@16:   assert(i == i1);
Chris@16:   assert(i == i2);
Chris@16:   ++i1;
Chris@16:   ++i2;
Chris@16: 
Chris@16:   trivial_iterator_test(i, i1, v2);
Chris@16:   trivial_iterator_test(i, i2, v2);
Chris@16: 
Chris@16:  // borland doesn't allow non-type template parameters
Chris@16: # if !defined(__BORLANDC__) || (__BORLANDC__ > 0x551)
Chris@16:   lvalue_test<(boost::is_pointer<Iterator>::value)>::check(i);
Chris@16: #endif
Chris@16: }
Chris@16: 
Chris@16: // Preconditions: *i == v1, *++i == v2
Chris@16: template <class Iterator, class T>
Chris@16: void bidirectional_iterator_test(Iterator i, T v1, T v2)
Chris@16: {
Chris@16:   forward_iterator_test(i, v1, v2);
Chris@16:   ++i;
Chris@16: 
Chris@16:   Iterator i1 = i, i2 = i;
Chris@16: 
Chris@16:   assert(i == i1--);
Chris@16:   assert(i != --i2);
Chris@16: 
Chris@16:   trivial_iterator_test(i, i1, v2);
Chris@16:   trivial_iterator_test(i, i2, v2);
Chris@16: 
Chris@16:   --i;
Chris@16:   assert(i == i1);
Chris@16:   assert(i == i2);
Chris@16:   ++i1;
Chris@16:   ++i2;
Chris@16: 
Chris@16:   trivial_iterator_test(i, i1, v1);
Chris@16:   trivial_iterator_test(i, i2, v1);
Chris@16: }
Chris@16: 
Chris@16: // mutable_bidirectional_iterator_test
Chris@16: 
Chris@16: template <class U> struct undefined;
Chris@16: 
Chris@16: // Preconditions: [i,i+N) is a valid range
Chris@16: template <class Iterator, class TrueVals>
Chris@16: void random_access_iterator_test(Iterator i, int N, TrueVals vals)
Chris@16: {
Chris@16:   bidirectional_iterator_test(i, vals[0], vals[1]);
Chris@16:   const Iterator j = i;
Chris@16:   int c;
Chris@16: 
Chris@16:   typedef typename boost::detail::iterator_traits<Iterator>::value_type value_type;
Chris@101: 
Chris@16:   for (c = 0; c < N-1; ++c) {
Chris@16:     assert(i == j + c);
Chris@16:     assert(*i == vals[c]);
Chris@16:     assert(*i == boost::implicit_cast<value_type>(j[c]));
Chris@16:     assert(*i == *(j + c));
Chris@16:     assert(*i == *(c + j));
Chris@16:     ++i;
Chris@16:     assert(i > j);
Chris@16:     assert(i >= j);
Chris@16:     assert(j <= i);
Chris@16:     assert(j < i);
Chris@16:   }
Chris@16: 
Chris@16:   Iterator k = j + N - 1;
Chris@16:   for (c = 0; c < N-1; ++c) {
Chris@16:     assert(i == k - c);
Chris@16:     assert(*i == vals[N - 1 - c]);
Chris@16:     assert(*i == boost::implicit_cast<value_type>(j[N - 1 - c]));
Chris@101:     Iterator q = k - c;
Chris@16:     assert(*i == *q);
Chris@16:     assert(i > j);
Chris@16:     assert(i >= j);
Chris@16:     assert(j <= i);
Chris@16:     assert(j < i);
Chris@16:     --i;
Chris@16:   }
Chris@16: }
Chris@16: 
Chris@16: // Precondition: i != j
Chris@16: template <class Iterator, class ConstIterator>
Chris@16: void const_nonconst_iterator_test(Iterator i, ConstIterator j)
Chris@16: {
Chris@16:   assert(i != j);
Chris@16:   assert(j != i);
Chris@16: 
Chris@16:   ConstIterator k(i);
Chris@16:   assert(k == i);
Chris@16:   assert(i == k);
Chris@16: 
Chris@16:   k = i;
Chris@16:   assert(k == i);
Chris@16:   assert(i == k);
Chris@16: }
Chris@16: 
Chris@101: } // namespace iterators
Chris@101: 
Chris@101: using iterators::undefined;
Chris@101: using iterators::trivial_iterator_test;
Chris@101: using iterators::mutable_trivial_iterator_test;
Chris@101: using iterators::input_iterator_test;
Chris@101: using iterators::lvalue_test;
Chris@101: using iterators::forward_iterator_test;
Chris@101: using iterators::bidirectional_iterator_test;
Chris@101: using iterators::random_access_iterator_test;
Chris@101: using iterators::const_nonconst_iterator_test;
Chris@101: 
Chris@16: } // namespace boost
Chris@16: 
Chris@16: #endif // BOOST_ITERATOR_TESTS_HPP