/////////////////////////////////////////////////////////////////////////////
// algor.cpp - demonstrate performance implications of STL algorithms
//
// Jim Fawcett, CSE691 - SW Modeling & Analysis, Fall 2000
/////////////////////////////////////////////////////////////////////////////
// Platform: Dell XPS1000, Windows 2000 Professional, SP1

#pragma warning(disable : 4786)
#include <iostream>
#include <algorithm>
#include <set>
#include <list>
#include "..\timer.h"
using namespace std;

/////////////////////////////////////////////////////////////////////////////
// populate container

template<class cont, class elem>
void fill(cont &c, int N) {

  for(int i = 0; i<N; i++)
    c.insert(c.end(),rand());
}

/////////////////////////////////////////////////////////////////////////////
// search with global find

template<class cont, class elem>
elem globalSearch(cont &c, elem e) {

  static bool first = true;
  if(first) {
    cout << "\n  using global find function";
    first = false;
  }
  return *find(c.begin(), c.end(), e);
}

/////////////////////////////////////////////////////////////////////////////
// search with member find

template<class cont, class elem>
elem memberSearch(cont &c, elem e) {

  static bool first = true;
  if(first) {
    cout << "\n  using member find function";
    first = false;
  }
  return *c.find(c.begin(), c.end(), e);
}

//

/////////////////////////////////////////////////////////////////////////////
// search with member find - specialization for set

template<class elem>
elem memberSearch(set<elem> &c, elem e) {

  static bool first = true;
  if(first) {
    cout << "\n  using member find function";
    first = false;
  }
  return *c.find(e);
}

/////////////////////////////////////////////////////////////////////////////
// function to time function calls

template<class U, class V> 
clock_t timeFunction(U(*pFunc)(V v, U u), V v, U u, int N) {

  timer t;
  t.start();
  int i;
  for(i=0; i<N; i++)
    pFunc(v,u);
  t.stop();

  cout << "\n  type of argument is\n  " << typeid(v).name();

  cout << "\n  time to call function " << N << " times = " 
       << t.elapsed() << " milliseconds" << endl;
  
  return t.elapsed();
}

//

/////////////////////////////////////////////////////////////////////////////
// test stub

void main() {

  cout << "\n  Demonstrate STL Algorithm Performance "
       << "\n =======================================\n";

  const int Nfill = 5000, Nrun = 5000;

  set<double> dSet;
  fill<set<double>,double>(dSet,Nfill);

  double d = rand();

  timeFunction<double,set<double>&>(globalSearch,dSet,d,Nrun);
  timeFunction<double,set<double>&>(memberSearch,dSet,d,Nrun);

  list<double> dList;
  fill<list<double>,double>(dList,Nfill);

  timeFunction<double,list<double>&>(globalSearch,dList,d,Nrun);

  cout << "\n\n";
}