Testsuite additions

[Chris Jefferson <caj at cs dot york dot ac dot uk>]

I submitted an earlier version of this, but have since cleaned it up 
some more.

testsuite_iterators.h is able to wrap a basic pointer as any of the 
categories of iterator. It also checks to see if any operations are 
performed on the iterator which should not be. By defining 
DISABLE_ITERATOR_DEBUG the debugging features can be removed and in this 
case the pointers should be as efficent as simple raw pointers, giving a 
way of testing an algorithm's performance on each type of input operator.

Note: Some comically, I don't promise that I've managed to test all of 
this testsuite :) So should you try and use it and find that you get an 
error, suspect the testsuite as well as the algorithm. Hopefully these 
should be sorted out over time. I already have a bunch of other tests 
written, but I want to check these get accepted before neatening them up 
and submitted.

To show the use of testsuite_iterators.h, I attach alg_test.cc which 
tests search_n and also search_n_performance.cc , which tests the 
performance of search_n under both random_access and forward iterators 
(yes they are identical at the moment, but they might not be soon).


// Copyright (C) 2004 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 2, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License along
// with this library; see the file COPYING.  If not, write to the Free
// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
// USA.

// 25 algorithms, search_n

#include <algorithm>
#include <functional>
#include <testsuite_hooks.h>
#include <testsuite_iterators.h>

#define TEST_DEPTH 14
int array1[11] = {0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0};
int array2[TEST_DEPTH];

bool 
pred(int i, int j)
{
  return i == j;
}

bool
lexstep(int* start, int length) 
{
  int i = 0;
  int carry = 1;
  while(i < length && carry) 
    {
      if(start[i] == 1)
	start[i] = 0;
      else 
	{
	  start[i] = 1;
	  carry = 0;
	}
      i++;
    }
  return !carry;
}

using __gnu_test::test_container;
using __gnu_test::random_access_iterator_wrapper;
using __gnu_test::bidirectional_iterator_wrapper;
using __gnu_test::forward_iterator_wrapper;

int main() {
  test_container<int,forward_iterator_wrapper> con(array1,array1 + 10);
  VERIFY(search_n(con.end(), con.end(), 0, 1) == con.end());
  VERIFY(search_n(con.end(), con.end(), 1, 1) == con.end());
  VERIFY(search_n(con.begin(), con.end(), 1, 1).ptr == array1 + 1);
  VERIFY(search_n(con.begin(), con.end(), 2, 1).ptr == array1 + 4);
  VERIFY(search_n(con.begin(), con.end(), 3, 1).ptr == array1 + 7);
  VERIFY(search_n(con.begin(), con.end(), 3, 0) == con.end());

  // Now do a brute-force comparison of the different types
  for(int i = 0; i < TEST_DEPTH; i++) 
    {
      for(int j = 0; j < i; j++)
	array2[i] = 0;
      do {
	for(int j = 0; j < i; j++)
	  {
	    test_container<int, forward_iterator_wrapper>
	      forwardcon(array2, array2 + i);
	    test_container<int, bidirectional_iterator_wrapper>
	      randomcon(array2, array2 + i);
	    test_container<int, bidirectional_iterator_wrapper>
	      bidircon(array2, array2 + i);

	    int* t1 = search_n(forwardcon.begin(),
			       forwardcon.end(), j, 1).ptr;
	    int* t2 = search_n(forwardcon.begin(),
			       forwardcon.end(), j, 1, pred).ptr;
	    int* t3 = search_n(bidircon.begin(),
			       bidircon.end(), j, 1).ptr;
	    int* t4 = search_n(bidircon.begin(),
			       bidircon.end(), j, 1, pred).ptr;
	    int* t5 = search_n(randomcon.begin(),
			       randomcon.end(), j, 1).ptr;
	    int* t6 = search_n(randomcon.begin(),
			       randomcon.end(), j, 1, pred).ptr;
	    VERIFY((t1 == t2) && (t2 == t3) && (t3 == t4) &&
		   (t4 == t5) && (t5 == t6));
	  }
      } 
      while(lexstep(array2, i));
    }
  return 0;
}

// -*- C++ -*-
// Iterator Wrappers for the C++ library testsuite. 
//
// Copyright (C) 2004 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 2, or (at your option)
// any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License along
// with this library; see the file COPYING.  If not, write to the Free
// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
// USA.
//
// As a special exception, you may use this file as part of a free software
// library without restriction.  Specifically, if other files instantiate
// templates or use macros or inline functions from this file, or you compile
// this file and link it with other files to produce an executable, this
// file does not by itself cause the resulting executable to be covered by
// the GNU General Public License.  This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the GNU General Public License.

// This file provides the following:
//
// input_iterator_wrapper, output_iterator_wrapper
// forward_iterator_wrapper, bidirectional_iterator_wrapper and
// random_access_wrapper, which attempt to exactly perform the requirements
// of these types of iterators. These are constructed from the class
// test_container, which is given two pointers to T and an iterator type.

#include <testsuite_hooks.h>
#include <iterator>

#ifndef _TESTSUITE_ITERATORS
#define _TESTSUITE_ITERATORS

#ifdef DISABLE_ITERATOR_DEBUG
#define ITERATOR_VERIFY(x)
#else
#define ITERATOR_VERIFY(x) VERIFY(x)
#endif

namespace __gnu_test
{
  /**
   * @brief Simple container for holding two pointers.
   *
   * Note that input_iterator_wrapper changes first to denote
   * how the valid range of == , ++, etc. change as the iterators are used.
   */
  template<typename T>
    struct BoundsContainer
    {
      T* first;
      T* last;
      BoundsContainer(T* _first, T* _last)
	: first(_first), last(_last)
      { }
    };

  // Simple container for holding state of a set of output iterators.
  template<typename T>
    struct OutputContainer : public BoundsContainer<T>
    {
      T* incrementedto;
      bool* writtento;
      OutputContainer(T* _first, T* _last)
	: BoundsContainer<T>(_first, _last), incrementedto(_first)
      {
	writtento = new bool[this->last - this->first];
	for(int i = 0; i < this->last - this->first; i++)
	  writtento = false;
      }

      ~OutputContainer()
      { delete[] writtento; }
    };

  // Produced by output_iterator to allow limited writing to pointer
  template<class T>
    class WritableObject
    {
      T* ptr;

    public:
      OutputContainer<T>* SharedInfo;
      WritableObject(T* ptr_in,OutputContainer<T>* SharedInfo_in):
	ptr(ptr_in), SharedInfo(SharedInfo_in)
      { }

      void
      operator=(T& new_val)
      {
	ITERATOR_VERIFY(SharedInfo->writtento[ptr - SharedInfo->first] == 0);
	SharedInfo->writtento[ptr - SharedInfo->first] = 1;
	ptr = new_val;
      }
    };

  /**
   * @brief output_iterator wrapper for pointer
   * 
   * This class takes a pointer and wraps it to provide exactly
   * the requirements of a output_iterator. It should not be
   * instansiated directly, but generated from a test_container
   */
  template<class T>
  struct output_iterator_wrapper: public std::iterator
  <std::output_iterator_tag, T, ptrdiff_t, T*, T&>
  {
    typedef OutputContainer<T> ContainerType;
    T* ptr;
    ContainerType* SharedInfo;

    output_iterator_wrapper(T* _ptr, ContainerType* SharedInfo_in)
      :ptr(_ptr), SharedInfo(SharedInfo_in)
    {
      ITERATOR_VERIFY(ptr >= SharedInfo->first && ptr <= SharedInfo->last);
    }
    
    output_iterator_wrapper(const output_iterator_wrapper& in)
      :ptr(in.ptr), SharedInfo(in.SharedInfo)
    { }

    WritableObject<T>
    operator*() const
    {
      ITERATOR_VERIFY(ptr < SharedInfo->last);
      ITERATOR_VERIFY(SharedInfo->writtento[ptr - SharedInfo->first] == false);
      return WritableObject<T>(ptr, SharedInfo);
    }
    
    output_iterator_wrapper&
    operator=(const output_iterator_wrapper& in) 
    {
      ptr = in.ptr;
      SharedInfo = in.SharedInfo;
    }

    output_iterator_wrapper&
    operator++()
    {
      ITERATOR_VERIFY(SharedInfo && ptr < SharedInfo->last);
      ITERATOR_VERIFY(ptr>=SharedInfo->first);
      ptr++;
      SharedInfo->first=ptr;
      return *this;
    }

    output_iterator_wrapper
    operator++(int)
    {
      output_iterator_wrapper<T> tmp = *this;
      ++*this;
      return tmp;
    }

  };

  /**
   * @brief input_iterator wrapper for pointer
   * 
   * This class takes a pointer and wraps it to provide exactly
   * the requirements of a input_iterator. It should not be
   * instansiated directly, but generated from a test_container
   */
  template<class T>
  class input_iterator_wrapper:public std::iterator
  <std::input_iterator_tag, T, ptrdiff_t, T*, T&>
  {
  protected:
    input_iterator_wrapper()
    { }

  public:
    typedef BoundsContainer<T> ContainerType;
    T* ptr;
    ContainerType* SharedInfo;

    input_iterator_wrapper(T* _ptr, ContainerType* SharedInfo_in)
      : ptr(_ptr), SharedInfo(SharedInfo_in)
    { ITERATOR_VERIFY(ptr >= SharedInfo->first && ptr <= SharedInfo->last); }
    
    input_iterator_wrapper(const input_iterator_wrapper& in)
      : ptr(in.ptr), SharedInfo(in.SharedInfo)
    { }

    bool
    operator==(const input_iterator_wrapper& in) const
    {
      ITERATOR_VERIFY(SharedInfo != NULL && SharedInfo == in.SharedInfo);
      ITERATOR_VERIFY(ptr>=SharedInfo->first && in.ptr>=SharedInfo->first);
      return ptr == in.ptr;
    }

    bool
    operator!=(const input_iterator_wrapper& in) const
    {
      return !(*this == in);
    }

    T&
    operator*() const
    {
      ITERATOR_VERIFY(SharedInfo && ptr < SharedInfo->last);
      ITERATOR_VERIFY(ptr >= SharedInfo->first);
      return *ptr;
    }

    T*
    operator->() const
    {
      return &**this;
    }

    input_iterator_wrapper&
    operator=(const input_iterator_wrapper& in)
    {
      ptr = in.ptr;
      SharedInfo = in.SharedInfo;
      return *this;
    }

    input_iterator_wrapper&
    operator++()
    {
      ITERATOR_VERIFY(SharedInfo && ptr < SharedInfo->last);
      ITERATOR_VERIFY(ptr>=SharedInfo->first);
      ptr++;
      SharedInfo->first=ptr;
      return *this;
    }

    void
    operator++(int)
    {
      ++*this;
    }
  };


  /**
   * @brief forward_iterator wrapper for pointer
   * 
   * This class takes a pointer and wraps it to provide exactly
   * the requirements of a forward_iterator. It should not be
   * instansiated directly, but generated from a test_container
   */
  template<class T>
  struct forward_iterator_wrapper:public input_iterator_wrapper<T>
  {
    typedef BoundsContainer<T> ContainerType;
    typedef std::forward_iterator_tag iterator_category;
    forward_iterator_wrapper(T* _ptr, ContainerType* SharedInfo_in)
      :input_iterator_wrapper<T>(_ptr, SharedInfo_in)
    { }
    
    forward_iterator_wrapper(const forward_iterator_wrapper& in)
      :input_iterator_wrapper<T>(in)
    { }

    forward_iterator_wrapper()
    {
      this->ptr = NULL;
      this->SharedInfo = NULL;
    }

    T&
    operator*() const
    {
      ITERATOR_VERIFY(this->SharedInfo && this->ptr < this->SharedInfo->last);
      return *(this->ptr);
    }

    T*
    operator->() const
    { return &**this; }

    forward_iterator_wrapper&
    operator++()
    {
      ITERATOR_VERIFY(this->SharedInfo && this->ptr < this->SharedInfo->last);
      this->ptr++;
      return *this;
    }

    forward_iterator_wrapper
    operator++(int)
    {
      forward_iterator_wrapper<T> tmp = *this;
      ++*this;
      return tmp;
    }
   };

  /**
   * @brief bidirectional_iterator wrapper for pointer
   * 
   * This class takes a pointer and wraps it to provide exactly
   * the requirements of a forward_iterator. It should not be
   * instansiated directly, but generated from a test_container
   */
  template<class T>
  struct bidirectional_iterator_wrapper:public forward_iterator_wrapper<T>
  {
    typedef BoundsContainer<T> ContainerType;
    typedef std::bidirectional_iterator_tag iterator_category;
    bidirectional_iterator_wrapper(T* _ptr, ContainerType* SharedInfo_in)
      :forward_iterator_wrapper<T>(_ptr, SharedInfo_in)
    { }

    bidirectional_iterator_wrapper(const bidirectional_iterator_wrapper& in)
      :forward_iterator_wrapper<T>(in)
    { }

    bidirectional_iterator_wrapper(): forward_iterator_wrapper<T>()
    { }

    bidirectional_iterator_wrapper&
    operator=(const bidirectional_iterator_wrapper& in)
    {
      this->ptr = in.ptr;
      this->SharedInfo = in.SharedInfo;
      return *this;
    }
   
    bidirectional_iterator_wrapper&
    operator++()
    {
      ITERATOR_VERIFY(this->SharedInfo && this->ptr < this->SharedInfo->last);
      this->ptr++;
      return *this;
    }

    bidirectional_iterator_wrapper
    operator++(int)
    {
      bidirectional_iterator_wrapper<T> tmp = *this;
      ++*this;
      return tmp;
    }

    bidirectional_iterator_wrapper& 
    operator--()
    {
      ITERATOR_VERIFY(this->SharedInfo && this->ptr > this->SharedInfo->first);
      this->ptr--;
      return *this;
    }

    bidirectional_iterator_wrapper
    operator--(int)
    { 
      bidirectional_iterator_wrapper<T> tmp = *this;
      --*this;
      return tmp;
    }
   };

  /**
   * @brief random_access_iterator wrapper for pointer
   * 
   * This class takes a pointer and wraps it to provide exactly
   * the requirements of a forward_iterator. It should not be
   * instansiated directly, but generated from a test_container
   */
  template<class T>
  struct random_access_iterator_wrapper:public bidirectional_iterator_wrapper<T>
  {
    typedef BoundsContainer<T> ContainerType;
    typedef std::random_access_iterator_tag iterator_category;
    random_access_iterator_wrapper(T* _ptr, ContainerType* SharedInfo_in)
      : bidirectional_iterator_wrapper<T>(_ptr, SharedInfo_in)
    { }

    random_access_iterator_wrapper(const random_access_iterator_wrapper<T>& in)
      : bidirectional_iterator_wrapper<T>(in)
    { }

    random_access_iterator_wrapper():bidirectional_iterator_wrapper<T>()
    { }

    random_access_iterator_wrapper&
    operator=(const random_access_iterator_wrapper& in)
    {
      this->ptr = in.ptr;
      this->SharedInfo = in.SharedInfo;
    }

    random_access_iterator_wrapper&
    operator++()
    {
      ITERATOR_VERIFY(this->SharedInfo && this->ptr < this->SharedInfo->last);
      this->ptr++;
      return *this;
    }

    random_access_iterator_wrapper
    operator++(int)
    {
      random_access_iterator_wrapper<T> tmp = *this;
      ++*this;
      return tmp;
    }

    random_access_iterator_wrapper&
    operator--()
    {
      ITERATOR_VERIFY(this->SharedInfo && this->ptr > this->SharedInfo->first);
      this->ptr--;
      return *this;
    }

    random_access_iterator_wrapper
    operator--(int)
    {
      random_access_iterator_wrapper<T> tmp = *this;
      ++*this;
      return tmp;
    }

    random_access_iterator_wrapper&
    operator+=(ptrdiff_t n)
    {
      if(n > 0)
	{
	  ITERATOR_VERIFY(n <= this->SharedInfo->last - this->ptr);
	  this->ptr += n;
	}
      else
	{
	  ITERATOR_VERIFY(n <= this->ptr - this->SharedInfo->first);
	  this->ptr += n;
	}
      return *this;
    }

    random_access_iterator_wrapper
    operator+(ptrdiff_t n)
    {
      random_access_iterator_wrapper<T> tmp = *this;
      return tmp += n;
    }

    random_access_iterator_wrapper&
    operator-=(ptrdiff_t n)
    { return *this += -n; }

    random_access_iterator_wrapper
    operator-(ptrdiff_t n)
    {
      random_access_iterator_wrapper<T> tmp = *this;
      return tmp -= n;
    }

    ptrdiff_t
    operator-(const random_access_iterator_wrapper<T>& in)
    {
      ITERATOR_VERIFY(this->SharedInfo == in.SharedInfo);
      return this->ptr - in.ptr;
    }

    T&
    operator[](ptrdiff_t n)
    { return *(this + n); }

    bool
    operator<(const random_access_iterator_wrapper<T>& in) const
    {
      ITERATOR_VERIFY(this->SharedInfo == in.SharedInfo);
      return this->ptr < in.ptr;
    }

    bool
    operator>(const random_access_iterator_wrapper<T>& in) const
    {
      return in < *this;
    }

    bool
    operator>=(const random_access_iterator_wrapper<T>& in) const
    {
      return !(*this < in);
    }

    bool 
    operator<=(const random_access_iterator_wrapper<T>& in) const
    {
      return !(*this > in);
    }
   };


  /** 
   * @brief A container-type class for holding iterator wrappers
   * test_container takes two parameters, a class T and an iterator
   * wrapper templated by T (for example forward_iterator_wrapper<T>.
   * It takes two pointers representing a range and presents them as 
   * a container of iterators.
   */
  template <class T, template<class T> class ItType>
  struct test_container
  {
    typename ItType<T>::ContainerType bounds;
    test_container(T* _first, T* _last):bounds(_first, _last)
    { }

    ItType<T>
    it(int pos)
    {
      ITERATOR_VERIFY(pos >= 0 && pos <= (bounds.last - bounds.first));
      return ItType<T>(bounds.first + pos, &bounds);
    }

    ItType<T>
    it(T* pos)
    {
      ITERATOR_VERIFY(pos >= bounds.first && pos <= bounds.last);
      return ItType<T>(pos, &bounds);
    }

    ItType<T>
    begin()
    { return it(bounds.first); }

    ItType<T>
    end()
    { return it(bounds.last); }
   };
}
#endif

// Copyright (C) 2004 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 2, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License along
// with this library; see the file COPYING.  If not, write to the Free
// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
// USA.

// As a special exception, you may use this file as part of a free software
// library without restriction.  Specifically, if other files instantiate
// templates or use macros or inline functions from this file, or you compile
// this file and link it with other files to produce an executable, this
// file does not by itself cause the resulting executable to be covered by
// the GNU General Public License.  This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the GNU General Public License.

#define DISABLE_ITERATOR_DEBUG 1

#include<cstdlib>
#include<vector>
#include<algorithm>

#include<sstream>
#include<testsuite_performance.h>
#include<testsuite_iterators.h>

using namespace std;
using namespace __gnu_test;

const int length = 10000000;
const int match_length = 3;
int array[length];

int
main(void)
{
  time_counter time;
  resource_counter resource;
  int match = rand() % (match_length - 1);
  for(int i = 0; i < length; i++)
    {
      array[i] = (match != 0) ? 1 : 0;
      if(--match < 0) match = rand() % (match_length - 1);
    }
  test_container<int, forward_iterator_wrapper> fcon(array, array + length);
  start_counters(time, resource);
  for(int i = 0; i < 100; i++)
    search_n(fcon.begin(), fcon.end(), 10, 1);
  stop_counters(time, resource);
  report_performance(__FILE__, "forward iterator", time, resource);
  clear_counters(time, resource);

  test_container<int, random_access_iterator_wrapper> rcon(array, array + length);
  start_counters(time, resource);
  for(int i = 0; i < 100; i++)
    search_n(rcon.begin(), rcon.end(), 10, 1);
  stop_counters(time, resource);
  report_performance(__FILE__, "random acess iterator", time, resource);
  clear_counters(time, resource);
}

2004-13-11  Chris Jefferson <chris@bubblescope.net>

	* testsuite/testsuite_iterators.h : New
        * testsuite/25_algorithms/search_n/alg_test.cc : New
        * testsuite/performance/25_algorithms/search_n.cc : New