#include <LEDA/basic.h>
#include <LEDA/string.h>
#include <LEDA/random.h>
#include <LEDA/_sortseq.h>
#include <LEDA/impl/skiplist.h>
#include <LEDA/f_sortseq.h>
#include <LEDA/quadruple.h>

#include <assert.h>

int convert(int a, int y){ return y;}

double convert(double a, int y){ return ((double) y); }

quadruple<int,int,int,int> convert(quadruple<int,int,int,int> a,int y)
       { return quadruple<int,int,int,int>(0,0,0,y);}


template <class K>
void speed_test(K a, int n, char* s)
{ cout << "\n\ntest with type " << s <<"\n\n";
  K* A = new K[n];
  for (int i = 0; i < n; i++)
      { int x = rand_int(0,1000000);
        A[i] = convert(a,x);
      }
  float T = used_time();
  { f_sortseq<K,int> S;
    for (int i = 0; i < n; i++)
      S.insert(A[i],0);
    S.clear();
    cout << "\n\nused time for f_sortseq = " << used_time(T);
  }
  { _sortseq<K,int,skiplist> S;
    for (int i = 0; i < n; i++)
      S.insert(A[i],0);
    S.clear();
    cout << "\n\nused time for sortseq = " << used_time(T);
  }
  cout << "\n\nand now the sorted insertions";
  { f_sortseq<K,int> S;
    S.insert(convert(a,0),0);
    for (int i = 1; i < n; i++)
      S.insert_at(S.max(),convert(a,i),0);
    S.clear();
    cout << "\n\nused time for f_sortseq = " << used_time(T);
  }
  { _sortseq<K,int,skiplist> S;
    S.insert(convert(a,0),0);
    for (int i = 1; i < n; i++)
      S.insert_at(S.max(),convert(a,i),0);
    S.clear();
    cout << "\n\nused time for sortseq = " << used_time(T);
  }
  
  newline;
  delete[] A;
}

main(){

int n = read_int("n = ");

int a1 = 0; 
double a2 = 0; 
quadruple<int,int,int,int> a3;


speed_test(a1,n,"int");
speed_test(a2,n,"double");
speed_test(a3,n,"quadruple");


}


