#include <stdlib.h>
#include <stdio.h>
//#include "tree.h"

/*Typen för en nod struct node.*/
typedef struct node{
  struct node *left;
  struct node *right;
  void *content;
} *Nodeptr, Node;

/*Typen för ett binärt ordnat träd. I själva verket är det en pekare till
trädhuvudet.*/
typedef struct binsearchtree{
  int (*cmp)(void*, void*);
  Nodeptr root;
} *Binsearchtree;

/*Funktionen initierar ett binärt ordnat träd. Den tar en jämförelsefunktion
som argument. Den retunerar det nya trädet om minne finns tillängligt, NULL 
annars.*/
Binsearchtree inittree(int (*cmp)(void*, void*)){
  Binsearchtree head = NULL;
  if((head = malloc(sizeof(struct binsearchtree)))){
    head->root = NULL;
    head->cmp = cmp;
  }
  return head;
}

/*Privat hjälpfunktion till inrerttree.*/
static void *insertrec(Nodeptr *nptr, void *element, int (*cmp)(void*, 
void*)){
  if (!*nptr){
    if((*nptr = malloc(sizeof(Node)))){
      (*nptr)->left = NULL;
      (*nptr)->right = NULL;
      return (*nptr)->content = element;
    }
    return NULL;
  }
  if((*cmp)(element, (*nptr)->content) < 0)
    return insertrec(&(*nptr)->left, element, cmp);
  if((*cmp)(element, (*nptr)->content) > 0)
    return insertrec(&(*nptr)->right, element, cmp);
  return (*nptr)->content;
}

/*Funktionen lägger till ett element i trädet. Den tar ett godtyckligt träd 
av typen
Binsearchtree som argument, sammt en pekare till ett element av typen void. 
Returnerar
en pekare till det nya elementet (eller till det gamla om elementet redan 
fanns),
eller om minnet har tagit slut NULL.*/
void *inserttree(Binsearchtree tree, void *element){
  return insertrec(&tree->root, element, tree->cmp);
}

/*Privat hjälpfunktion till find.*/
static void *findrec(Nodeptr nptr, void *element, int (*cmp)(void*, void*)){
  if (!nptr) return NULL;
  if ((*cmp)(element, nptr->content) < 0)
    return findrec(nptr->left, element, cmp);
  if ((*cmp)(element, nptr->content) > 0)
    return findrec(nptr->right, element, cmp);
  return nptr->content;
}

/*Funktionen letar efter ett elementet och returnerar det. Den tar ett 
binärt ordnat
träd och det sökta elementet som argument.*/
void *find(Binsearchtree tree, void *element){
  return findrec(tree->root, element, tree->cmp);
}

/*Privat hjälpfunktion till delete.*/
static Nodeptr getleftmost(Nodeptr *nptr){
  Nodeptr tmp;
  if ((*nptr)->left)
    return getleftmost(&(*nptr)->left);
  else {
    tmp=*nptr;
    *nptr=(*nptr)->right;
    return tmp;
  }
}

/*Privat hjälpfunktion till delete.*/
static void deleterec(Nodeptr *nptr, void *element, int (*cmp)(void*, 
void*), void (*del)(void*)){
  if (!*nptr) return;
  else if (((*cmp)(element, (*nptr)->content)) < 0){
    printf("1\n");
    deleterec(&(*nptr)->left, element, cmp, del);
  }
  else if (((*cmp)(element, (*nptr)->content)) > 0){
    printf("2\n");
    deleterec(&(*nptr)->right, element, cmp, del);
  }
  else{
    printf("3\n");
    Nodeptr tmp = *nptr;
    if (!(*nptr)->left)
      *nptr = (*nptr)->right;
    else if (!(*nptr)->right)
      *nptr = (*nptr)->left;
    else{
      *nptr=getleftmost(&(*nptr)->right);
      (*nptr)->left = tmp->left;
      (*nptr)->right = tmp->right;
    }
    printf("4\n");
    printf("%d\n",(*((int*)tmp->content)));
    (*del)(tmp->content);
    printf("5\n");
    free(tmp);
    printf("6\n");
  }
}

/*Funktionen tar bort ett element ur listan. Den tar ett BOT, det sökta 
elementet
samt en bortagnings funktion som argument. Borttagningsfunktionen anger hur
elementet skall tas bort.*/
void delete(Binsearchtree tree, void *element, void (*del)(void*)){
  deleterec(&tree->root, element, tree->cmp, del);
}

/*Privat hjälpfunktion till doforall.*/
static void doforallrec(Nodeptr nptr, void (*todo)(void*)){
  if (nptr){
    doforallrec(nptr->left, todo);
    (*todo)(nptr->content);
    doforallrec(nptr->right, todo);
  }
}

/*Inordertraverseringsfunktion, den utför funktionen todo på varje element i 
trädet
bst i sorteringsordning*/
void doforall(Binsearchtree bst, void (*todo)(void*)){
  doforallrec(bst->root, todo);
}

/*Privat hjälpfunktion till preorder.*/
static void preorderrec(Nodeptr nptr, void (*todo)(void*)){
  if (nptr){
    (*todo)(nptr->content);
    preorderrec(nptr->left, todo);
    preorderrec(nptr->right, todo);
  }
}

/*Som doforall fast med preordertraversering*/
void preorder(Binsearchtree bst, void (*todo)(void*)){
  preorderrec(bst->root, todo);
}

/*Privat hjälpfunktion till postorder.*/
static void postorderrec(Nodeptr nptr, void (*todo)(void*)){
  if (nptr){
    postorderrec(nptr->left, todo);
    postorderrec(nptr->right, todo);
    (*todo)(nptr->content);
  }
}

/*Som doforall fast med postordertraversering*/
void postorder(Binsearchtree bst, void (*todo)(void*)){
  postorderrec(bst->root, todo);
}

int func(int *x, int *y){
  int z;
  if (*x < *y)
    z = -1;
  else if (*x > *y)
    z = 1;
  else
    z = 0;
  return z;
}

void delfunc(int *todel){
  free(todel);
}

void todofunc(int *elem){
  printf("%d ",*elem);
}

void printtree(Nodeptr nptr, int depth){
  int *tmp;
  if (nptr){
    printtree(nptr->left, depth+1);
    tmp = nptr->content;
    printf("%*d\n",depth * 5, *tmp);
    printtree(nptr->right, depth+1);
  }
}

int main(void){
  int arr[30] ={15,17,20,3,11,26,29,1,5,23,18,2,21,22,28,4,6,24,13,12,7,10,8,27,9,14,16,19,25,30};
  int *treearr[30];
  int arrarr[16] = {18,2,21,22,28,4,6,24,13,12,7,10,8,27,9,14};
  int i;
  for (i = 0; i < 30; i++){
    treearr[i] = malloc(sizeof(int));
    *treearr[i] = arr[i];
  }
  Binsearchtree bst = inittree((int (*)(void*, void*))func);
  for (i = 0; i < 30; i++)
    inserttree(bst, treearr[i]);
  for (i = 0; i < 16; i++)
    delete(bst, &arrarr[i], (void (*)(void*))delfunc);
  //delete(bst, &arr[0], (void (*)(void*))delfunc);
  printf("sorteringsordning\n");
  doforall(bst, (void (*)(void*))todofunc);
  printf("\n");
  printf("preorder\n");
  preorder(bst, (void (*)(void*))todofunc);
  printf("\n");
  printf("postorder\n");
  postorder(bst, (void (*)(void*))todofunc);
  printf("\n");
  printtree(bst->root, 1);
  return 0;
}