#include <LEDA/basic.h>
#include <LEDA/list.h>
#include <LEDA/stl.h>

template <class T>
int func1(list<T> L) { return L.size(); }

template <class T>
int func2(stl_list<T> L) { return L.size(); }


template <class T>
void test_list(int N, list<T>& L, stl_list<T>& SL)
{
  list<T>      L1;
  stl_list<T> SL1;

  T*  A = new T[N];

  int i;
  for (i=0; i<N; i++) A[i] = rand_int(1,10000);

  float t;


  cout << "build list     ";
  cout.flush();

  rand_int.set_seed(1234*N);
  t = used_time();
  for (i = 0; i < N; i++) L.append(A[i]);
  cout << string("  %5.3f sec",used_time(t)) << flush;

  rand_int.set_seed(1234*N);
  t = used_time();
  for (i = 0; i < N; i++) SL.push_back(A[i]);
  cout << string("  %5.3f sec",used_time(t)) << endl;



  cout << "pop and push   ";
  cout.flush();

  t = used_time();
  while (!L.empty()) { L1.push(L.tail()); L.Pop(); }
  cout << string("  %5.3f sec",used_time(t)) << flush;

  t = used_time();
  while (!SL.empty()) { SL1.push_front(SL.back()); SL.pop_back(); }
  cout << string("  %5.3f sec",used_time(t)) << endl;



  cout << "reversing      ";
  cout.flush();

  t = used_time();
  L1.reverse();
  cout << string("  %5.3f sec",used_time(t)) << flush;

  t = used_time();
  SL1.reverse();
  cout << string("  %5.3f sec",used_time(t)) << endl;


  cout << "copy constr    ";
  cout.flush();

  t = used_time();
  func1(L1);
  cout << string("  %5.3f sec",used_time(t)) << flush;

  t = used_time();
  func2(SL1);
  cout << string("  %5.3f sec",used_time(t)) << endl;



  cout << "assignment     ";
  cout.flush();

  t = used_time();
  L = L1;
  cout << string("  %5.3f sec",used_time(t)) << flush;

  t = used_time();
  SL = SL1;
  cout << string("  %5.3f sec",used_time(t)) << endl;



  cout << "clearing       ";
  cout.flush();

  t = used_time();
  L1.clear();
  cout << string("  %5.3f sec",used_time(t)) << flush;

  t = used_time();
  SL1.erase(SL1.begin(),SL1.end());
  cout << string("  %5.3f sec",used_time(t)) << endl;




  cout << "sorting        ";
  cout.flush();

  t = used_time();
  L.sort();
  cout << string("  %5.3f sec",used_time(t)) << flush;

  t = used_time();
  SL.sort();
  cout << string("  %5.3f sec",used_time(t)) << endl;


  cout << "merging        ";
  cout.flush();
  L1 = L;
  SL1 = SL;

  t = used_time();
  L.merge(L1);
  cout << string("  %5.3f sec",used_time(t)) << flush;

  t = used_time();
  SL.merge(SL1);
  cout << string("  %5.3f sec",used_time(t)) << endl;


  cout << "unique         ";
  cout.flush();

  t = used_time();
  L.unique();
  cout << string("  %5.3f sec",used_time(t)) << flush;


  t = used_time();
  SL.unique();
  cout << string("  %5.3f sec",used_time(t)) << endl;



  cout << "iteration      ";
  cout.flush();

  int sum1 = 0;
  t = used_time();
  //T x;
  //forall(x,L) sum1 += Int(x);
  list_item it1;
  forall_items(it1,L) sum1 += Int(L[it1]);
  cout << string("  %5.3f sec",used_time(t)) << flush;

  int sum2 = 0;
  stl_list<T>::iterator it2;
  t = used_time();
  for(it2 = SL.begin(); it2 != SL.end(); it2++) sum2 += Int(*it2);
  cout << string("  %5.3f sec",used_time(t)) << endl;

  if (sum1 != sum2) 
     cout << "Error: lists are different." << endl;




  cout << endl;

  delete[] A;
}


class  my_struct {

  int x,y,z;


public:

my_struct(int a=0) : x(a), y(2*a), z(3*a) {}

friend int Int(const my_struct& s) { return s.x; }

friend int compare(const my_struct& s1, const my_struct& s2)
{ if (s1.x < s2.x) return -1;
  else if (s1.x > s2.x) return +1;
  else if (s1.y < s2.y) return -1;
  else if (s1.y > s2.y) return +1;
  else if (s1.z < s2.z) return -1;
  else if (s1.z > s2.z) return +1;
  else return 0;
 }


friend bool operator==(const my_struct& s1, const my_struct& s2)
{ return s1.x == s2.x && s1.y == s2.y && s1.z == s2.z; }

friend bool operator<(const my_struct& s1, const my_struct& s2)
{ if (s1.x < s2.x) return true;
  else if (s1.x > s2.x) return false;
  else if (s1.y < s2.y) return true;
  else if (s1.y > s2.y) return false;
  else if (s1.z < s2.z) return true;
  else if (s1.z > s2.z) return false;
  else return false;
 }


friend ostream& operator<<(ostream& o, const my_struct& s) 
{ o << s.x << " " << s.y << " " << s.z; return o; }

friend istream& operator>>(istream& i, my_struct&)       { return i; }

LEDA_MEMORY(my_struct)

};


inline int Int(int x)    { return x; }
inline int Int(double x) { return (int)x; }


int main () 
{
  int N = read_int("Number of list entries: "); 
  cout << endl;

  cout << "list<int>        LEDA       STL" << endl;
  list<int>     L1;
  stl_list<int> SL1;
  test_list(N,L1,SL1);


  cout << "list<double>     LEDA       STL" << endl;
  list<double>     L2;
  stl_list<double> SL2;
  test_list(N,L2,SL2);


  cout << "list<class>      LEDA       STL" << endl;
  list<my_struct>     L3;
  stl_list<my_struct> SL3;
  test_list(N,L3,SL3);

  return 0;
}
