#include <glib/gtree.h>
#include <string.h>
#include <time.h>
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

/*===========================================================*/
/* timing tests */

void timing_test_print(struct timeval *start, struct timeval *stop, char *s)
{
  long sec, usec;
  sec=stop->tv_sec-start->tv_sec;
  usec=stop->tv_usec-start->tv_usec;
  if(usec>=1000000) {
    usec-=1000000;
    sec++;
  }
  if(usec<0) {
    usec+=1000000;
    sec--;
  }
 #ifdef CMP_COUNTING
  printf("%s :\t%4ld.%06ld cmps %ld\n",s,sec,usec, cmp_count);
  cmp_count=0;
 #else
  printf("%s :\t%4ld.%06ld\n",s,sec,usec);
 #endif
}

/*===========================================================*/

static gint
my_compare (gconstpointer a,
            gconstpointer b)
{
  const int *ia = a;
  const int *ib = b;

  return *ia - *ib;
}


void gtree_timing_test(int *items_val, int items_cnt)
{
  int i;
  GTree *tree;
  int *item;

  struct timeval time_start, time_stop;

  printf("\nRunning gtree tree timing test for %d items (g_tree)\n",items_cnt);
  
  tree = g_tree_new (my_compare);

  gettimeofday(&time_start,NULL);
  for(i=0;i<items_cnt;i++){
    g_tree_insert (tree, &items_val[i], &items_val[i]);
  }
  gettimeofday(&time_stop,NULL);
  timing_test_print(&time_start,&time_stop,"cust insert");
  
  gettimeofday(&time_start,NULL);
  for(i=0;i<items_cnt;i++){
    if(!(item=g_tree_lookup(tree,&i)))
      printf("gtree_find error\n");
    else 
      if(*item!=i)
        printf("gtree_find mismatch\n");
  }
  gettimeofday(&time_stop,NULL);
  timing_test_print(&time_start,&time_stop,"cust find");

  gettimeofday(&time_start,NULL);
  for(i=0;i<items_cnt;i++){
    if(!(item=g_tree_lookup(tree,&i)))
      printf("gtree_find error\n");
    else 
      if(*item!=i)
        printf("gtree_find mismatch\n");
  }
  gettimeofday(&time_stop,NULL);
  timing_test_print(&time_start,&time_stop,"cust find");

  gettimeofday(&time_start,NULL);
  for(i=0;i<items_cnt;i++){
    g_tree_remove (tree,&i);
  }
  gettimeofday(&time_stop,NULL);
  timing_test_print(&time_start,&time_stop,"cust delete");

}

/*===========================================================*/

int main(int argc, char *argv[])
{
  int items_cnt=1000000;
  int *items_val;
  int perturb_count;
  int i;

  if(argc>1)
    items_cnt=atoi(argv[1]);

  perturb_count=2*items_cnt;
  if(argc>2)
    perturb_count=atoi(argv[2]);

  items_val=malloc(items_cnt*sizeof(int));
  
  for(i=0;i<items_cnt;i++)
    items_val[i]=i;

  gtree_timing_test(items_val, items_cnt);

  srand (1);

  for(i=0;i<perturb_count;i++){
    int a, b, t;
    do
      a=((long long)items_cnt*rand())/RAND_MAX;
    while((a>=items_cnt)||(a<0));
    do
      b=((long long)items_cnt*rand())/RAND_MAX;
    while((b>=items_cnt)||(b<0));
    t=items_val[b];
    items_val[b]=items_val[a];
    items_val[a]=t;
  }


  gtree_timing_test(items_val, items_cnt);
  
  free(items_val);
  
  return 0;
}