#include <LEDA/map.h>


int map_test(map<int,int>& D, int N, int* A, char* name)
{ 
  cout << string("%-12s",name);
  cout.flush();

  float T;
  float T0 = T = used_time();

  int sum = 0;

  int i;
  for(i=0; i<N; i++)  D[A[i]] = A[i];
  cout << string("%10.2f",used_time(T));
  cout.flush();

  for(i=0; i<N; i++)  sum += D[A[i]];
  cout << string("%10.2f",used_time(T));
  cout.flush();

  cout << string("%10.2f",used_time(T0));
  newline;

  return sum;
}

main()
{
  int     N      = read_int("# keys = ");
  int*    Int    = new int[N];
  int*    Int1   = new int[N];



  int i;
  for(i=0; i<N; i++) Int[i] = rand_int(0,100000);
  for(i=0; i<N; i++) Int1[i] = i;

  int k;


  newline;
  cout << "                insert    lookup    total\n";
  newline;

  cout << "Random Integers" << endl;
  newline;

  { map<int,int> M(0);
    map_test(M,N,Int,"map");
    newline;
   }

  for(k=1; k<=1024; k*=2)
  { cout << "k = " << k << endl;
    map<int,int> M(0,k);
    map_test(M,N,Int,"map");
   }
  newline;


  cout << "Sorted Integers" << endl;
  newline;

  { map<int,int> M(0);
    map_test(M,N,Int1,"map");
    newline;
   }

  for(k=1; k<=1024; k*=2)
  { cout << "k = " << k << endl;
    map<int,int> M(0,k);
    map_test(M,N,Int1,"map");
   }
  newline;

  return 0;
}

