// Code timeing vector growth in various ways.
// CS 509 - Spring 2004

#include <cstdio>
#include <vector>
#include <cmath>
#include <cassert>
#include "stopwatch.h"


static double 
stddev(unsigned * times, unsigned n) {

  unsigned xsq_sum = 0, xsum = 0;

  assert(n > 1);

  while (n-- > 0) {
    const unsigned x = times[n];
    xsq_sum += x*x;
    xsum += x;
    }

  return sqrt((static_cast<double>(xsq_sum) -
	       static_cast<double>(xsum*xsum)/static_cast<double>(n))/
	      static_cast<double>(n - 1));
  }

#define timeit(_code) \
 do {const unsigned iters = 10; unsigned i; \
      unsigned * times = new unsigned[iters] ; \
      for (i = 0; i < iters; i++) { \
        stopwatch sw; sw.start(); \
        _code \
        sw.stop(); times[i] = sw.elapsed(); } \
      unsigned total = 0; for (i = 0; i < iters; i++) total += times[i]; \
      printf("%u iterations, %4u msec/iter (%g).\n", iters, \
	     static_cast<unsigned>(static_cast<double>(total)/ \
             static_cast<double>(1000*iters)), stddev(times, iters)); \
    } while (false)

struct shred {
  std::vector<int> edge1, edge2;
  shred() { }
  };

int main() {

  const unsigned vsize = 200000;

  timeit(
    std::vector<int> ivec;
    for (unsigned j = 0; j < vsize; j++)
      ivec.push_back(j);
    );

  timeit(
    std::vector<int> ivec;
    for (unsigned j = 0; j < vsize; j++)
      ivec.push_back(j);
    );

  timeit(
    std::vector<int> ivec(vsize);
    for (unsigned j = 0; j < vsize; j++)
      ivec[j] = j;
    );

  timeit(
    std::vector<int> ivec;
    ivec.reserve(vsize);
    for (unsigned j = 0; j < vsize; j++)
      ivec.push_back(j);
    );

  shred s;

  timeit(
    std::vector<shred> svec;
    for (unsigned j = 0; j < vsize; j++)
      svec.push_back(s);
    );

  timeit(
    std::vector<shred> svec(vsize);
    for (unsigned j = 0; j < vsize; j++)
      svec[j] = s;
    );

  timeit(
    std::vector<shred> svec;
    svec.reserve(vsize);
    for (unsigned j = 0; j < vsize; j++)
      svec.push_back(s);
    );
  }

// $Log: vgrowth.cc,v $
// Revision 1.1  2004/02/05 22:23:17  rclayton
// Initial revision
//