// CS 509 - Advanced Programming
// Fall 2003
//
// Example allocator use.


#include <vector>
#include <cstdio>
#include <unistd.h>
#include <memory>
#include "stopwatch.h"


template < typename T >
class vtr {

  public:

    typedef T value_type;

    vtr() : elements(0), size(0), max(0) { }
   ~vtr() { delete [] elements; }

    void push_back(const T & v) {
      if (size >= max)
	grow();
      assert(size <= max);
      elements[size++] = v;
      }

  private:

    T * elements;
    size_t size, max;

    void grow() {
      max = (max == 0 ? 1 : max*2);
      T * const ne = new T [max];
      for (size_t i = 0; i < size; i++)
	ne[i] = elements[i];
      delete [] elements;
      elements = ne;
      }
  };


template < typename T >
class avtr {

  public:

    typedef T value_type;

    avtr() : elements(0), size(0), max_size(0) { }

   ~avtr() { uncreate(); }

    void push_back(const T & v) {
      if (size >= max_size)
	grow();
      assert(size <= max_size);
      elements[size++] = v;
      }

  private:

    T * elements;
    size_t size, max_size;
    std::allocator<T> alloc;

    void grow() {
      max_size = std::max(max_size*2, size_t(1));
      T * ne = alloc.allocate(max_size);
      std::uninitialized_copy(elements, elements + size, ne);
      uncreate();
      elements = ne;
      }

    void uncreate() {
      if (size) {
	for (T * i = elements + (size - 1); i >= elements; i--)
	  alloc.destroy(i);
	alloc.deallocate(elements, size);
	}
      }
  };


typedef std::pair<double, double> point;

template < typename V >
static void
test(unsigned vsize, unsigned iters) {

  assert(iters > 0);

  unsigned t = 0;

  for (unsigned j = 0; j < iters; j++) {
    V ivec;
    stopwatch sw;
    sw.start();
    for (unsigned i = 0; i < vsize; i++)
      ivec.push_back(typename V::value_type());
    sw.stop();
    if (j > 0)
      t += sw.elapsed();
    }
  printf("%4u\n", 
	 static_cast<unsigned>(static_cast<double>(t)/static_cast<double>((iters - 1)*1000) + 0.5));
  }


template < typename T >
static void
run_times(unsigned vsize, unsigned iters) {
  test<vtr<T> >(vsize, iters);
  test<avtr<T> >(vsize, iters);
  test<std::vector<T> >(vsize, iters);
  }


int main(int argc, char * argv[]) {

  unsigned 
    vsize = 10000,
    iters = 10;

  if (argc >= 2)
    vsize = static_cast<unsigned>(atoi(argv[1]));
  if (argc >= 3)
    iters = static_cast<unsigned>(atoi(argv[2]));

  assert(vsize > 0);
  assert(iters > 0);

  run_times<int>(vsize, iters);
  run_times<point>(vsize, iters);
  }

// $Log: vtr.cc,v $
// Revision 1.1  2003/12/17 01:29:45  rclayton
// Initial revision
//