/*
 * Copyright by Jyrki Katajainen
 * January-March 1998
 * May 2000
 */

#include <cassert>
#include <iostream>
#include <iterator>
#include "find.cpp"

template <typename F>
void generate (
  F first,
  F beyond
) {

  typedef typename std::iterator_traits<F>::value_type E;
  
  F p = first;
  while (p != beyond) {
    *p = E(2 * (p - first) + 1); 
    ++p;
  }
}

int main() {

  const unsigned int bign = 12;

  typedef int E;
  typedef E* (*routine)(E*, E*, const E&);
  routine search = cphstl::find;

  for (unsigned int n = 0; n <= bign; n++) {
    std::cout << "   n = " << n << std::endl;
    E a[12];
    generate(a, a + n);
    for (unsigned int i = 0; i < n; i++) {
      if (n > 0) assert(search(a, a + n, a[i]) == a + i);
      else assert(search(a, a + n, a[i]) == a);
      assert(search(a, a + n, a[i] - 1) == a + n);
      assert(search(a, a + n, a[i] + 1) == a + n);
    }
    E b[12] = {0,0,0,0,0,0,0,0,0,0,0,0};
    assert(search(b, b + n, -1) == b + n);
    if (n > 0)  assert(b <= search(b, b + n, 0) && search(b, b + n, 0) < b + n);
    else assert(search(b, b + n, 0) == b);
    if (n > 0) assert(search(b, b + n, 0) < b + n);
    else assert(search(b, b + n, 0) == b);
    assert(search(b, b + n, 1) == b + n);
  }

  return 0;
}