// generic bubble sort in C++
// pointer version written Jan 00 by Ulrich Stern
// alek: added timing code

#include <stdio.h> //timing
#include <time.h>

#include <iostream.h>

template<class Object, class Comparator>
void mysort(Object* a[], int n, Comparator cmp) {
  for(int i=0; i<n-1; i++)
    for(int j=n-1; j>i; j--)
      if(!cmp(a[j-1], a[j])) {
        Object* tmp = a[j-1];
        a[j-1] = a[j];
        a[j] = tmp;
      }
}

struct Range {
  int lb, ub;
  Range() {}
  Range(int l, int u): lb(l), ub(u) {}
};

ostream& operator << (ostream& out, const Range* r) {
  return out << '[' << r->lb << ',' << r->ub << ']';
}

struct LBComparator {
  bool operator() (const Range* a, const Range* b) const {
    return a->lb < b->lb;
  }
};

struct UBComparator {
  bool operator() (const Range* a, const Range* b) const {
    return a->ub < b->ub;
  }
};

int main() {
  time_t stime, etime;  //timing
  char timebuf[128];

  const int REPEAT = 10;
  const int N = 10000;
  Range* a[N];

  for(int i=0; i<N; i++) {
    a[i] = new Range(i*7%1000, i*13%1000);
  }

  //cout << "sorting...\n";  cout.flush();
  printf( "sorting N=%d REPEAT=%d\n", N, REPEAT);

  _tzset(); //timing
  _strtime( timebuf );
  printf( "started at: %s\n", timebuf );
  time( &stime );

  for(int count = 0; count < REPEAT; ++count) {
    mysort(a, N, LBComparator());
    mysort(a, N, UBComparator());
  }

  time( &etime ); //timing
  _strtime( timebuf );
  printf( "finished at: %s in %g sec\n", timebuf, difftime(etime, stime) );

  //cout << "done.\n";  cout.flush();
  return 0;
}