#include <LEDA/basic.h>
#include <LEDA/list.h>
#include <LEDA/string.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 sort_demo(K a, int n, char* s)
{ cout << "\n\ntest with type " << s <<"\n\n";
  int f = 0; int powf = 1;
  while (powf < n) {f++; powf *=2;}
  f = 200;
{ cout << "\n\nf = " << f;
  list<K > L;

{
  for(int i = 0; i < n; i++)
    { list_item it = L.last();
      int j = f-1;
      while (it && j > 0)
        { it = L.pred(it); j--; }
      if (it) L.insert(convert(a,i),it,after);
      else L.push(convert(a,i));
    }
}
 
  f_sortseq<K,int> S;
  K i; 
  float T = used_time();
  forall(i,L)
     if (S.empty()) S.insert(i, 0); 
    else S.insert_at(S.max_item(),i,0,after);
  cout << "\ncopying L to S " << used_time(T);
  S.clear();
  T = used_time();
  forall(i,L)
     S.insert(i, 0); 
  cout << "\nrepeated insertion " << used_time(T);
  S.clear();
  T = used_time();
  forall(i, L)
  { if (S.empty()) S.insert(i, 0); 
    else 
    { f_seq_item it = S.finger_locate(S.max_item(), i); 
      if (it) S.insert_at(it,i,0,before); 
      else S.insert_at(S.max_item(),i,0,after);
    }
  }
  cout << "\nfinger sort1: " << used_time(T);
  S.clear();
  T = used_time();
  S.insert(L.head(),0);
  list_item it = L.succ(L.first());
  while (it)
  { f_seq_item s_it = S.finger_locate(i); 
      if (s_it) S.insert_at(s_it,i,0,before); 
      else S.insert_at(S.max_item(),i,0,after);
    it = L.succ(it);
  }
  cout << "\nfinger sort2: " << used_time(T);
  S.clear();

  list<K > L1(L);
  L1.sort();
  cout << "\nlist sort: " << used_time(T);
}
newline;newline;
}


main(){ 
int n = read_int("n = ");

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

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


}

