// CS 509 - Advanced Programming II
// Spring '04
//
// Experimenting with vector vs. map performance.

#include <map>
#include <iostream>
#include <vector>
#include "cl-options.h"
#include "episode-timer.h"

typedef std::map<int, int> iimap;
typedef std::vector<int> ivec;

static void 
interleaved(const ivec & vals, episode_timer & mtime, episode_timer & vtime) {

  assert(not (vals.size() & 1));

  mtime.start();
    iimap m;

    for (unsigned i = 0; i < vals.size(); i += 2) {
      m.insert(std::make_pair(vals[i], vals[i]));
      m.find(vals[i + 1]);
      }
  mtime.stop();

  vtime.start();
    ivec v;
    v.reserve(vals.size());

    for (unsigned i = 0; i < vals.size(); i += 2) {
      v.insert(std::lower_bound(v.begin(), v.end(), vals[i]), vals[i]);
      std::binary_search(v.begin(), v.end(), vals[i + 1]);
      }
  vtime.stop();
  }


static void 
staged(const ivec & vals, episode_timer & mtime, episode_timer & vtime) {

  assert(not (vals.size() & 1));

  mtime.start();
    iimap m;

    for (unsigned i = 0; i < vals.size(); i += 2)
      m.insert(std::make_pair(vals[i], vals[i]));

    for (unsigned i = 1; i < vals.size(); i += 2)
      m.find(vals[i]);
  mtime.stop();

  vtime.start();
    ivec v;
    v.reserve(vals.size());

    for (unsigned i = 0; i < vals.size(); i += 2)
      v.push_back(vals[i]);

    std::sort(v.begin(), v.end());

    for (unsigned i = 1; i < vals.size(); i += 2)
      std::binary_search(v.begin(), v.end(), vals[i]);
  vtime.stop();
  }


static void time(
  void (* test)(const ivec &, episode_timer &, episode_timer &), 
  unsigned iters, unsigned size) {

  episode_timer mtime, vtime;
  ivec vals;
  vals.reserve(size*2);
  for (unsigned i = 0; i < size; i++) {
    vals.push_back(random());
    vals.push_back(random());
    }

  for (unsigned j = 0; j < iters; j++) {
    random_shuffle(vals.begin(), vals.end());
    test(vals, mtime, vtime);
    }

  std::cout << "size " << size << " iters " << iters
	    << " map time " << mtime.average() << " (" << mtime.stddev() 
	    << ") vector time " << vtime.average() 
	    << " (" << vtime.stddev() << ")\n";
  }

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

  cl_options opts;
  opts['i'] = "10";
  opts['s'] = "1000";
  get_cl_options(argc, argv, opts);

  time(interleaved, atoi(opts['i']), atoi(opts['s']));
  }

/*
xlabel total insert + find operations
ylabel time (msec)
curvelabel map
curvelabel vector
curvecolor 1 0 0
curvecolor 0 0 1
legendposition 0.1 0.70
data size %x iters 10 map time %y1 vector time %y2

g++ -o t -O -ansi -pedantic -I $HOME/lib/c vvm.cc $HOME/lib/c/cl-options.cc
*/


// $Log: vvm.cc,v $
// Revision 1.1  2004/03/09 23:39:38  rclayton
// Initial revision
//