#include <stdio.h>
#include <stdlib.h>
#define BTREE_TYPE int
#include "btree.h"

void deletebtree(BTREE, int);
BTREENODE deleterbtree(BTREENODE, int);
BTREENODE spliceroot(BTREENODE);
BTREENODE spliceleft(BTREENODE);
BTREENODE spliceright(BTREENODE);
BTREENODE succ(BTREENODE);


int main()
{
   BTREE t = readpreorderbtree();
   int n = 1;

   fflush(stdin);
   inorder(t, "%d\n");

   while(n != -1)
   {
      printf("\nNodo da cancellare: ");
      scanf("%d",&n);

      if(n != -1)
         deletebtree(t, n);

      inorder(t, "%d\n");
   }

   t = destroybtree(t);

   freeemptybtree(t);

   return 0;
}



/* gestisce la cancellazione di un nodo in un albero binario di ricerca */
/* con l'ausilio della funzione deleterbtree(...), a cui passa la radice */
void deletebtree(BTREE handler, int val)
{
   handler->root = deleterbtree(rootbtree(handler),val);
}



/* esegue la cancellazione di un nodo in un albero binario */
/* di ricerca: se cancellazione non avvenuta, restituisce NULL */
BTREENODE deleterbtree(BTREENODE node, int val)
{
   BTREENODE exnode;

   if(!node)                                            /* nodo non trovato */
      return NULL;
   else if(node->info == val)                           /* nodo radice da cancellare */
      node = spliceroot(node);
   else if(node->left && node->left->info == val)       /* NODO SINISTRO DA CANCELLARE: */
   {
      if((node->left->left && !node->left->right) ||    /* ha (almeno) un figlio */
         (!node->left->left && node->left->right)  )
      {
         node->left = spliceleft(node->left);
      }
      else if(isleaf(node->left))                       /* non ha figli (foglia) */
      {
         exnode = node->left;
         node->left = NULL;
         free(exnode);
      }
      else                                              /* ha entrambi i figli */
         node->left = succ(node->left);
   }
   else if(node->right && node->right->info == val)     /* NODO DESTRO DA CANCELLARE */
   {
      if((node->right->left && !node->right->right) ||  /* ha (almeno) un figlio */
         (!node->right->left && node->right->right)  )
      {
         node->right = spliceright(node->right);
      }
      else if(isleaf(node->right))                      /* non ha figli (foglia) */
      {
         exnode = node->right;
         node->right = NULL;
         free(exnode);
      }
      else                                              /* ha entrambi i figli */
         node->right = succ(node->right);
   }
   else if(val < node->info)                            /* sposto la ricerca sul sottoalbero sinistro */
      node->left = deleterbtree(node->left, val);
   else if(val > node->info)                            /* sposto la ricerca sul sottoalbero destro */
      node->right = deleterbtree(node->right, val);


   return node;
}



/* gestisce la cancellazione di una radice */
BTREENODE spliceroot(BTREENODE node)
{
   BTREENODE exnode = node;
   BTREENODE newnode;

   if((exnode->left && !exnode->right) ||               /* ha un figlio: */
      (!exnode->left && exnode->right)  )
   {
      if(exnode->left)                                  /* sinistro */
         newnode = exnode->left;
      else                                              /* destro */
         newnode = exnode->right;
   }
   else if(isleaf(exnode))                              /* non ha figli (foglia) */
      newnode = NULL;
   else                                                 /* ha entrambi i figli */
      newnode = succ(exnode);

   return newnode;
}



/* gestisce la cancellazione di un figlio sinistro */
BTREENODE spliceleft(BTREENODE node)
{
   BTREENODE exnode = node;
   BTREENODE newnode;

   if(node->left)                                       /* ha solo il figlio sinistro */
      newnode = exnode->left;
   else if(node->right)                                 /* ha solo il figlio destro */
      newnode = exnode->right;
   else                                                 /* non ha figli (anomalia) */
      newnode = NULL;

   free(exnode);                                        /* libero memoria occupata dal nodo */

   return newnode;
}



/* gestisce la cancellazione di un figlio destro */
BTREENODE spliceright(BTREENODE node)
{
   BTREENODE exnode = node;
   BTREENODE newnode;

   if(node->left)                                       /* ha solo il figlio sinistro */
      newnode = exnode->left;
   else if(node->right)                                 /* ha solo il figlio destro */
      newnode = exnode->right;
   else                                                 /* non ha figli (anomalia) */
      newnode = NULL;

   free(exnode);                                        /* libero memoria occupata dal nodo */

   return newnode;
}



/* ricerca e pone come sostituto del nodo in entrata il valore minimo del suo sottoalbero destro */
BTREENODE succ(BTREENODE node)
{
   BTREENODE exnode = node;
   BTREENODE dad;
   BTREENODE newnode;

   newnode = exnode->right;                             /* preparo ricerca sul sottoalbero destro del nodo */
   dad = newnode;

   while(newnode->left != NULL)                         /* scorro a sinistra alla ricerca del valore minimo */
   {
      dad = newnode;                                    /* memorizzo come padre il nodo attuale */
      newnode = newnode->left;                          /* mi sposto sul figlio sinistro del nodo attuale */
   }

   dad->left = NULL;                                    /* il padre non ha pił figlio sinistro */
   newnode->left = exnode->left;                        /* figlio sinistro nodo sostitutivo = figlio sinistro nodo da cancellare */

   if(dad != newnode)                                   /* mi sono spostato dalla radice */
   {
      dad->left = newnode->right;                       /* figlio sinistro del padre = figlio (sotto-albero) destro del figlio */
      newnode->right = exnode->right;                   /* figlio destro nodo sostitutivo = figlio destro nodo da cancellare */
   }

   free(exnode);                                        /* libero memoria occupata dal nodo */

   return newnode;
}
