#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <sys/time.h>

#include "ul_utmalloc.h"
#include "ul_gavl.h"

/*===========================================================*/
/* checking code */

#define GAVL_CHECK_NOBAL 0x0020

#define GAVL_ERR_PARENT  0x0001
#define GAVL_ERR_HDIFF   0x0002
#define GAVL_ERR_HEIGHT  0x0010
#define GAVL_ERR_BALANCE 0x0020

typedef struct gavl_check_st{
  int mode;
  int err;
  int count;
  int depth;
  gavl_node_t *node;
  gavl_root_t *root;
  int (*node_fnc)(gavl_node_t *node, struct gavl_check_st *check);
  void *context;
  int *status;
} gavl_check_st_t;

int 
gavl_hdiff_check_recurse(gavl_node_t *node, gavl_node_t *parent,
                         gavl_check_st_t* check)
{
  int lh, rh;

  if(!node) return 0;
  check->depth++;
  if(node->parent!=parent) check->err|=GAVL_ERR_PARENT;
  lh=gavl_hdiff_check_recurse(node->left, node, check);
  if(check->node_fnc)
    check->err|=check->node_fnc(node, check);
  rh=gavl_hdiff_check_recurse(node->right, node, check);
  check->count++;
  if((rh>lh+1) || (rh+1<lh)){
    if(!(check->mode&GAVL_CHECK_NOBAL)){
      check->err|=GAVL_ERR_BALANCE;
    }
  }
  if(node->hdiff!=lh-rh){
    check->err|=GAVL_ERR_HDIFF;
  }
 
  if(check->err && !check->node) check->node=node;
  check->depth--;
  return lh>rh?lh+1:rh+1;
}

void 
gavl_hdiff_check_reperr(gavl_node_t *node, gavl_check_st_t* check)
{
  volatile int i;
  for(i=0;i<1000;i++);
}

int 
gavl_hdiff_check(gavl_node_t *node, int mode)
{
  int i;
  int h=0;
  gavl_check_st_t check;
  check.mode=mode;
  check.err=0;
  check.count=0;
  check.node=NULL;
  check.depth=0;
  check.node_fnc=NULL;
  check.root=NULL;
  
  if(node)
    h=gavl_hdiff_check_recurse(node, node->parent,&check);

  if(!(check.mode&GAVL_CHECK_NOBAL)){
    for(i=0;(1<<i)<=check.count;i++);
    if(h>i+1) check.err|=GAVL_ERR_HEIGHT;
  }

  if(check.err){
    gavl_hdiff_check_reperr(node,&check);
  }
  return check.err;
}

/*===========================================================*/
/* custom tree definition */

#include "ul_gavlcust.h"
#include "ul_gavlrepcust.h"
#include "ul_gavlflesint.h"

#undef GAVL_TEST_FLES

typedef struct cust2_item {
  int my_val;
  gavl_node_t my_node;
  int more_data;
} cust2_item_t;

typedef struct cust2_root {
 #ifndef GAVL_TEST_FLES
  gavl_cust_root_field_t my_root;
 #else /*GAVL_TEST_FLES*/
  gavl_fles_int_root_field_t my_root;
 #endif /*GAVL_TEST_FLES*/
  int my_info;
  int my_first_val;
  int my_last_val;
} cust2_root_t;

typedef int cust2_key_t;

/* Custom tree declarations */
/* GAVL_CUST_NODE_INT_DEC - standard custom tree with internal node */
/* GAVL_FLES_INT_DEC      - tree with enhanced first last access speed  */

#ifndef GAVL_TEST_FLES
GAVL_CUST_NODE_INT_DEC(cust2, cust2_root_t, cust2_item_t, cust2_key_t,
	my_root, my_node, my_val, cust2_cmp_fnc)
#else /*GAVL_TEST_FLES*/
GAVL_FLES_INT_DEC(cust2, cust2_root_t, cust2_item_t, cust2_key_t,
	my_root, my_node, my_val, cust2_cmp_fnc)
#endif /*GAVL_TEST_FLES*/

inline int
cust2_cmp_fnc(const cust2_key_t *a, const cust2_key_t *b)
{
  if (*a>*b) return 1;
  if (*a<*b) return -1;
  return 0;
}

/* Custom tree implementation */
/* GAVL_CUST_NODE_INT_IMP - version with strict ordering */
/* GAVL_CUST_NODE_INT_REP_IMP - version without strict ordering */
/* GAVL_FLES_INT_IMP      - tree with enhanced first last access speed  */

#ifndef GAVL_TEST_FLES
GAVL_CUST_NODE_INT_IMP(cust2, cust2_root_t, cust2_item_t, cust2_key_t,
	my_root, my_node, my_val, cust2_cmp_fnc)
#else /*GAVL_TEST_FLES*/
GAVL_FLES_INT_IMP(cust2, cust2_root_t, cust2_item_t, cust2_key_t,
	my_root, my_node, my_val, cust2_cmp_fnc, 0, 
	root->my_first_val=cust2_first(root)->my_val,
	root->my_last_val=cust2_first(root)->my_val, 
	)
#endif /*GAVL_TEST_FLES*/

cust2_root_t cust2_root;


void test_cust_tree(void)
{
  int i;
  cust2_key_t k;
  cust2_item_t *item, *item2;
  for(i=1;i<=100;i++){
    item=malloc(sizeof(cust2_item_t));
    item->my_val=i;
    if(cust2_insert(&cust2_root,item)<0)
      printf("cust2_insert error\n");
  }
  printf("Custom tree cust2 for_each:\n");
  gavl_cust_for_each(cust2, &cust2_root, item)
    printf("%d ",item->my_val);
  printf("\n");

  k=90;
  printf("Custom tree cust2 for_each_from %ld:\n", (long)k);
  gavl_cust_for_each_from(cust2, &cust2_root, &k, item){
    printf("After %d : ",item->my_val);
    gavl_cust_for_each_after(cust2, &cust2_root, &item->my_val, item2)
      printf(" %d",item2->my_val);
    printf("\n");
  }

  printf("Custom tree cust2 delete 1-90:\n");
  for(i=1;i<=100-10;i++){
    item=cust2_find(&cust2_root,&i);
    if(cust2_delete(&cust2_root,item)<0)
      printf("cust2_delete error\n");
    free(item);
  }

  printf("Custom tree cust2 for_each_rev:\n");
  gavl_cust_for_each_rev(cust2,&cust2_root,item)
    printf("%d ",item->my_val);
  printf("\n");

  printf("Custom tree cust2 for_each_cut:\n");
  gavl_cust_for_each_cut(cust2,&cust2_root,item){
    printf("%d ",item->my_val);
    free(item);
  }
  printf("\n");
}

void test_cust_tree_it(void)
{
  int i;
  cust2_key_t k;
  cust2_item_t *item;
  cust2_it_t it1, it2;
  
  for(i=1;i<=100;i++){
    item=malloc(sizeof(cust2_item_t));
    item->my_val=i;
    if(cust2_insert(&cust2_root,item)<0)
      printf("cust2_insert error\n");
  }
  printf("Custom tree cust2 for each with iterator:\n");
  for(cust2_first_it(&cust2_root, &it1);
      (item=cust2_it2item(&it1));cust2_next_it(&it1))
    printf("%d ",item->my_val);
  printf("\n");

  k=90;
  printf("Custom tree cust2 for_each_from %ld:\n", (long)k);
  for(cust2_find_first_it(&cust2_root, &k, &it1);
      (item=cust2_it2item(&it1));cust2_next_it(&it1)){
    printf("After %d : ",item->my_val);
    for(cust2_find_after_it(&cust2_root, &item->my_val, &it2);
        (item=cust2_it2item(&it2));cust2_next_it(&it2))
      printf(" %d",item->my_val);
    printf("\n");
  }

  printf("Custom tree cust2 delete 1-90:\n");
  for(i=1;i<=100-10;i++){
    item=cust2_find(&cust2_root,&i);
    if(cust2_delete(&cust2_root,item)<0)
      printf("cust2_delete error\n");
    free(item);
  }

  printf("Custom tree cust2 for_each_rev:\n");
  for(cust2_last_it(&cust2_root, &it1);
      (item=cust2_it2item(&it1));cust2_prev_it(&it1))
    printf("%d ",item->my_val);
  printf("\n");

  printf("Custom tree cust2 for_each_cut:\n");
  gavl_cust_for_each_cut(cust2,&cust2_root,item){
    printf("%d ",item->my_val);
    free(item);
  }
  printf("\n");
}

void test_cust_tree_macro_it(void)
{
  int i;
  cust2_key_t k;
  cust2_item_t *item;
  cust2_it_t it1, it2;
  
  for(i=1;i<=100;i++){
    item=malloc(sizeof(cust2_item_t));
    item->my_val=i;
    if(cust2_insert(&cust2_root,item)<0)
      printf("cust2_insert error\n");
  }
  printf("Custom tree cust2 for each with iterator:\n");
  ul_for_each_it(cust2, &cust2_root, it1){
    item=cust2_it2item(&it1);
    printf("%d ",item->my_val);
  }
  printf("\n");

  k=90;
  printf("Custom tree cust2 for_each_from %ld:\n", (long)k);
  ul_for_each_from_it(cust2, &cust2_root, &k, it1){
    item=cust2_it2item(&it1);
    printf("After %d : ",item->my_val);
    ul_for_each_after_it(cust2, &cust2_root, &item->my_val, it2){
      item=cust2_it2item(&it2);
      printf(" %d",item->my_val);
    }
    printf("\n");
  }

  printf("Custom tree cust2 delete 1-90:\n");
  for(i=1;i<=100-10;i++){
    item=cust2_find(&cust2_root,&i);
    if(cust2_delete(&cust2_root,item)<0)
      printf("cust2_delete error\n");
    free(item);
  }

  printf("Custom tree cust2 for_each_rev:\n");
  ul_for_each_rev_it(cust2, &cust2_root, it1){
    item=cust2_it2item(&it1);
    printf("%d ",item->my_val);
  }
  printf("\n");

  printf("Custom tree cust2 for_each_cut:\n");
  gavl_cust_for_each_cut(cust2,&cust2_root,item){
    printf("%d ",item->my_val);
    free(item);
  }
  printf("\n");
}

/*===========================================================*/
/* 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--;
  }
  printf("%s :\t%4ld.%06ld\n",s,sec,usec);
}

void cust_timing_test(void)
{
  int i;
  int items_cnt=100000;
  cust2_item_t *items;
  struct timeval time_start, time_stop;

  printf("\nRunning custom tree timing test for %d items\n",items_cnt);
  
  items=malloc(items_cnt*sizeof(cust2_item_t));
  if(!items){
    printf("malloc failed\n");
    return;
  }
  
  for(i=0;i<items_cnt;i++){
    items[i].my_val=i;
    items[i].more_data=0;
  }
  
  gettimeofday(&time_start,NULL);
  for(i=0;i<items_cnt;i++){
    if(cust2_insert(&cust2_root,items+i)<0)
      printf("cust2_insert error\n");
  }
  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(!cust2_find(&cust2_root,&i))
      printf("cust2_find error\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(1){
      if(cust2_delete(&cust2_root,items+i)<0)
	printf("cust2_delete error\n");
    }else{
      if(!cust2_cut_first(&cust2_root))
	printf("cust2_cut_first NULL\n");
    }
  }
  gettimeofday(&time_stop,NULL);
  timing_test_print(&time_start,&time_stop,"cust delete");

  free(items);
}

void timing_test(void)
{
  int i;
  int items_cnt=100000;
  cust2_item_t *items;
  cust2_item_t *item;
  struct timeval time_start, time_stop;
  gavl_root_t tt_root;
  
  tt_root.root_node = NULL;
  tt_root.node_offs = UL_OFFSETOF(cust2_item_t, my_node);
  /*tt_root.node_offs = -1;*/
  tt_root.key_offs = UL_OFFSETOF(cust2_item_t, my_val);
  tt_root.cmp_fnc = gavl_cmp_int;

  printf("\nRunning generic tree timing test for %d items\n",items_cnt);
  
  items=malloc(items_cnt*sizeof(cust2_item_t));
  if(!items){
    printf("malloc failed\n");
    return;
  }
  
  for(i=0;i<items_cnt;i++){
    items[i].my_val=i;
    items[i].more_data=0;
  }
  
  gettimeofday(&time_start,NULL);
  for(i=0;i<items_cnt;i++){
    if(gavl_insert(&tt_root,items+i,0)<0)
      printf("gavl_insert error\n");
  }
  gettimeofday(&time_stop,NULL);
  timing_test_print(&time_start,&time_stop,"GAVL insert");
  
  gettimeofday(&time_start,NULL);
  for(i=0;i<items_cnt;i++){
    if(!(item=gavl_find(&tt_root,&i)))
      printf("gavl_find error\n");
    else
      if(item->my_val!=i)
        printf("gavl_find mismatch\n");
  }
  gettimeofday(&time_stop,NULL);
  timing_test_print(&time_start,&time_stop,"GAVL find");

  gettimeofday(&time_start,NULL);
  for(i=0;i<items_cnt;i++){
    if(gavl_delete(&tt_root,items+i)<0)
      printf("gavl_delete error\n");
  }
  gettimeofday(&time_stop,NULL);
  timing_test_print(&time_start,&time_stop,"GAVL delete");

  free(items);
}

/*===========================================================*/
/* test code */

typedef struct test_item1 {
  int val;
} test_item1_t;

gavl_root_t test_gavl1={
  .root_node = NULL,
  .node_offs = -1,
  .key_offs = UL_OFFSETOF(test_item1_t, val),
  .cmp_fnc = gavl_cmp_int
};

int gavl_print_tree1(gavl_root_t *root, gavl_node_t *node,
		int lev, gavl_node_t *parent, int mode)
{
  static int cnt;
  static int err;
  int i, val;
  int lh, rh;
  int ret;
  if(!parent){
    cnt=0;
    err=0;
  }
  if(node!=NULL)
  {
    lh=gavl_print_tree1(root, node->left,lev+1, node, mode);
    cnt++;
    val=*(int*)gavl_node2key(root,node);
    if(!(mode&0x80)){
      for(i=0;i++<lev;) printf(" ");
      printf(">%d  %d\n",val,node->hdiff);
    }
    if(node->parent!=parent) printf("Parent error\n");
    rh=gavl_print_tree1(root, node->right,lev+1, node, mode);
    if((rh>lh+1) || (rh+1<lh)){
      if(!(mode&0x20)){
        printf("Balance error for value %d, lh %d, rd %d, hdiff %d\n",val,lh,rh,node->hdiff);
        err=2;
      }
    }
    if(node->hdiff!=lh-rh){
      printf("HDIFF error for value %d, lh %d, rd %d, hdiff %d\n",val,lh,rh,node->hdiff);
      err=1;
    }
    ret=lh>rh?lh+1:rh+1;
  } else ret=0;
  if(!parent){
    for(i=0;(1<<i)<=cnt;i++);
    if(!(mode&0x40)){
      printf("Count %d log %d max %d\n",cnt,i,ret);
    }
    if(ret>i+1) printf("Tree height >log2(n)+1\n");
    if(err){
      printf("Error %d\n",err);
      ret=-1;
    }
  }
  return ret;  
}

int gavl_check(gavl_root_t *root)
{
  int ret;
  if(!root)
    root=&test_gavl1;
  ret=gavl_print_tree1(root, root->root_node, 0, NULL, 0xc0);
  return ret;
}


void gavl_foreach_test1(gavl_root_t *root)
{
  int val, prev=-INT_MAX;
  gavl_node_t *n;
  for(n=gavl_first_node(root);n;n=gavl_next_node(n)){
    val=*(int*)gavl_node2key(&test_gavl1,n);
    printf(" %d",val);
    if(prev>val) printf("\nError in ordering\n");
    prev=val;
  } 
  printf("\n");
  
}

#ifdef WITH_C99
void gavl_foreach_test2(gavl_root_t *root)
{
  int val, prev=-INT_MAX;
  test_item1_t *item1;
  test_item1_t *item2;
  printf("gavl_generic_for_each:\n");
  gavl_generic_for_each(test_item1_t, root, item1){
    val=item1->val;
    printf("after %d:",val);
    if(prev>val) printf("\nError in ordering\n");
    prev=val;
    gavl_generic_for_each_after(test_item1_t, root, &val, item2)
    {
      printf(" %d",item2->val);
    }
    printf("\n");  
  }
}
#endif /*WITH_C99*/

int main(int argc, char *argv[])
{
  int val;
  int n, i;
  int ret;
  char c;
  test_item1_t *item;
  gavl_node_t *node, *node1, *node2;
  
  if(0){
    cust_timing_test();
    return 0;
  }

  c=0;
  do{
    if(!c || (c=='\n'))
      printf("\nTree edit: a <val>|d <val>|x..exit > ");
    c=0;
    scanf("%c",&c);
    switch(c){
      case 'a':
        if (scanf("%d",&val)==1){
	  item=malloc(sizeof(test_item1_t));
	  item->val=val;
	  ret=gavl_insert(&test_gavl1,item,0);
	  printf("gavl_insert of val %d returned %d\n\n",val,ret);
	  gavl_print_tree1(&test_gavl1, test_gavl1.root_node, 0, NULL, 0);
        }
	break;
      case 'd':
        if (scanf("%d",&val)==1){
	  ret=gavl_search_node(&test_gavl1, &val, GAVL_FANY, &node);
	  if(!ret){
	    printf("No node with key %d\n",val);
	    break;
	  }
	  item=gavl_node2item(&test_gavl1,node);
	  ret=gavl_delete_node(&test_gavl1,node);
	  free(item);
	  printf("gavl_delete_node of val %d returned %d\n\n",val,ret);
	  gavl_print_tree1(&test_gavl1, test_gavl1.root_node, 0, NULL, 0);
        }
	break;
      case 'f':
	gavl_foreach_test1(&test_gavl1);
	break;
     #ifdef WITH_C99
      case 'F':
	gavl_foreach_test2(&test_gavl1);
	break;
     #endif /*WITH_C99*/
      case 's':
        ret=scanf("%d %d %d",&val, &n, &i);
	if(ret<3) i=1;
        if (ret>=2){
	  while(n--){
	    item=malloc(sizeof(test_item1_t));
	    item->val=val;
	    ret=gavl_insert(&test_gavl1,item,0);
	    if(ret<0)
    	      printf("gavl_insert of val %d returned %d\n\n",val,ret);
	    gavl_print_tree1(&test_gavl1, test_gavl1.root_node, 0, NULL, 0xc0);
	    val+=i;
	  }
	  printf("\n");
	  gavl_print_tree1(&test_gavl1, test_gavl1.root_node, 0, NULL, 0);
	  gavl_print_tree1(&test_gavl1, test_gavl1.root_node, 0, NULL, 0xc0);
        }
	break;
      case 'l':
	i=0;
	node2=NULL;
        node=gavl_last_node(&test_gavl1);
	while(node){
	  node1=gavl_prev_node(node);
          gavl_delete_node(&test_gavl1,node);
	  gavl_print_tree1(&test_gavl1, test_gavl1.root_node, 0, NULL, 0xc0);
	  node->hdiff=i; i--;
	  node->right=node2; if(node2) node2->parent=node;
	  node2=node;
	  node=node1;
	}
	test_gavl1.root_node=node2;
        gavl_print_tree1(&test_gavl1, test_gavl1.root_node, 0, NULL, 0x20);
        break;
      case 'L':
	i=0;
	node2=NULL;
        node=gavl_first_node(&test_gavl1);
	while(node){
	  node1=gavl_next_node(node);
          gavl_delete_node(&test_gavl1,node);
          gavl_print_tree1(&test_gavl1, test_gavl1.root_node, 0, NULL, 0xc0);
	  node->hdiff=i; i++;
	  node->left=node2; if(node2) node2->parent=node;
	  node2=node;
	  node=node1;
	}
	test_gavl1.root_node=node2;
        gavl_print_tree1(&test_gavl1, test_gavl1.root_node, 0, NULL, 0x20);
        break;
      case 'r':
	gavl_balance_enhance(&test_gavl1.root_node);
        gavl_print_tree1(&test_gavl1, test_gavl1.root_node, 0, NULL, 0x20);
        break;
      case 'k':
        for(node1=gavl_first_node(&test_gavl1);node1;node1=node2){
	  /*This is test code and it doesnot free node or item */
	  node2=gavl_delete_and_next_node(&test_gavl1, node1);
	  printf("Value of node %d\n",*(int*)gavl_node2key(&test_gavl1, node1));
          gavl_print_tree1(&test_gavl1, test_gavl1.root_node, 0, NULL, 0x20);
	} 
	break;
      case 'b':
	gavl_balance(&test_gavl1);
        gavl_print_tree1(&test_gavl1, test_gavl1.root_node, 0, NULL, 0x00);
        break;
      case 'c':
        if (scanf("%d",&val)==1){
	  ret=gavl_search_node(&test_gavl1, &val, GAVL_FANY, &node);
	  if(!ret){
	    printf("No node with key %d\n",val);
	    break;
	  }
	  node1=node;
	  for(i=0;node1;i++){
	    if(node1->hdiff>0) node1=node1->left;
	    else node1=node1->right;
	  }
          gavl_adjust_hdiff(node,-i);
	  if(!node->parent) test_gavl1.root_node=NULL;
	  else if(node==node->parent->left) node->parent->left=NULL;
	  else node->parent->right=NULL;
	  
        }
        gavl_print_tree1(&test_gavl1, test_gavl1.root_node, 0, NULL, 0x20);
	break;
      case 'C':
        printf("\nCheck of custom tree for_each\n");
        test_cust_tree();
        printf("\nCheck of custom tree iterators\n");
        test_cust_tree_macro_it();
        printf("\nCheck of custom tree for_each iterators\n");
        test_cust_tree_it();
        break;
      case 't':
        timing_test();
        break;
      case 'T':
        cust_timing_test();
        break;
    }
  } while(c!='x');
  return 0;
}