#include <sys/time.h>
#include <time.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <map>
using namespace std;

inline int clstrcmp(char *a, char* b)
{
  int res = strcmp(a,b);
  if (res<0) return -1;
  if (res>0) return 1;
  return 0;
}

struct WoordKnoop {
   struct WoordKnoop *left;
   struct WoordKnoop *right;
   int flag;
   char *woord;};
typedef struct WoordKnoop *TestNodeAdt;
#define NODE TestNodeAdt
#define LEFT_NODE(watte) (watte->left)
#define RIGHT_NODE(watte) (watte->right)
#define SET_LEFT_NODE(watte,to) (watte->left=to)
#define SET_RIGHT_NODE(watte,to) (watte->right=to)
#define POSITIVE_FLAG(watte) (watte->flag==1)
#define ZERO_FLAG(watte) (watte->flag==0)
#define NEGATIVE_FLAG(watte) (watte->flag==-1)
#define SET_ZERO_FLAG(watte) (watte->flag=0)
#define SET_NEGATIVE_FLAG(watte) (watte->flag=-1)
#define SET_POSITIVE_FLAG(watte) (watte->flag=1)
#define NULLNODE NULL
#define ISNULLNODE(wie) (!wie)
#define SEARCH_DATA char*
#define COMPARE_ADD_DATA(w1,w2) (clstrcmp(w1->woord,w2->woord))
#define COMPARE_SEARCH_DATA(inst,key) (clstrcmp(inst->woord,key))
#define DELETE_NODE(wie) (free(wie))
#define PRINT_NODE(wie) printf("[%c %s]",(wie->flag==1 ? '+' : (wie->flag==-1 ? '-' : '0')),wie->woord)
#include "avltree1m.h"
#include "avltree1m.c"

NODE root=NULLNODE;

static char *ChooseWord()
     {
	int l,t;
	char* s;
	l=random()%10;
	s=(char*)malloc(l+1);
	for(t=0;t<l;t++) s[t]=random()%26+'A';
	s[l]=0;
	return s;
     }

#define count 1000000
static char*WordArray[count];

static struct timeval marked;
void start_timer()
{
 gettimeofday(&marked,NULL);
}

void stop_timer(char * a, char* b)
{
  struct timeval now;
  gettimeofday(&now,NULL);
  long long int B = now.tv_sec;
  B*=1000000L;
  B+=now.tv_usec;

  long long int A = marked.tv_sec;
  A*=1000000L;
  A+=marked.tv_usec;

  // printf("%s\t%s\t%ld\n",a,b,(B-A)/1000);
  printf("%ld\t",(B-A)/1000);
}

void restart_time(char* a, char* b)
{
  stop_timer(a,b);
  start_timer();
}

int maina()
{
  int t;
  NODE knoop;
  start_timer();
  for(t=count;t>0;)
    {
      SEARCH_DATA w=ChooseWord();
      t--;
      WordArray[t]=w;
      if (SearchAvlNode(root,w)) 
	{
	  t++;
	  continue;
	}
      knoop=(struct WoordKnoop*)malloc(sizeof(struct WoordKnoop));
      knoop->woord=w;
      knoop->flag = 0;
      knoop->left = knoop->right = NULL;
      root=AddAvlNode(root,knoop);
    }
  stop_timer("avl","create");
  start_timer();
  for(t=0;t<count;t++)
    {
      root=DeleteAvlNode(root,WordArray[t]);
      knoop=(struct WoordKnoop*)malloc(sizeof(struct WoordKnoop));
      knoop->woord=WordArray[t];
      knoop->flag = 0;
      knoop->left = knoop->right = NULL;
      root=AddAvlNode(root,knoop);
    }
  stop_timer("avl","reinsert");
  start_timer();
  for(t=0;t<count;t++)
    root=DeleteAvlNode(root,WordArray[t]);
  stop_timer("avl","delete");
  for(int t=0;t<count;t++)
    free(WordArray[t]);
}

int mainb()
{
  map<char*,char*> m;
  start_timer();
  for(int t=count;t>0;)
    {
      char * w = ChooseWord();
      t--;
      WordArray[t]=w;
      if (m.find(w)!=m.end())
	{
	  t++;
	  continue;
	}
      m[w]=w;
    }
  stop_timer("map","create");
  start_timer();
  for(int t=0;t<count;t++)
    {
      m.erase(WordArray[t]);
      m[WordArray[t]]=WordArray[t];
    }
  stop_timer("map","reinsert");
  start_timer();
  for(int t=0;t<count;t++)
    m.erase(WordArray[t]);
  stop_timer("map","delete");
  for(int t=0;t<count;t++)
    free(WordArray[t]);
}

int main(int argc,char*[])
{
  printf("%d words (timings expressed in milisecs)\n"
	 "avl\t\tmap\n"
	 "create\treinsert\tdelete\tcreate\treinsert\tdelete\n",count);
  while(true)
    {
      maina();
      mainb();
      printf("\n");
      fflush(stdout);
    }
}