#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define WORD 50  // lunghezza  massima di una parola



/*** DEFINIZIONI GLOBALI ***/

/* Struttura  per rappresentare una occorrenza <word,num>  */

struct occorrenza{
  char *word;
  int num; 
};

typedef struct occorrenza occorrenza;


/* Struttura  per rappresentare un nodo dell'albero   */

struct node { 
  occorrenza *key; //  indirizzo occorrenza rappresentata dal nodo 
    struct node * up; 
    struct node * left; 
    struct node * right; 
}; 

typedef struct node node; 


int mainTest1();
int mainOcc();

int main(){
  return mainTest1();
  // return mainOcc();
}



/*** CONFRONTO FRA PAROLE ***/



/* Restituisce 1 se le parole w1 e w2 sono uguali, 0 altrimenti */

int strUguale(char *w1, char *w2){
  // Si puo' usare la funzione   strcmp() di string.h 
}


/* Restituisce 1 se w1 < w2 rispetto  all'ordinamento lessicografico, 0 altrimenti */

int strMinore(char *w1, char *w2){
   // Si puo' usare la funzione   strcmp() di string.h 
}


/*** TEST  per le funzioni di confronto fra parole     ***/


int mainTest1(){
  char w1[WORD+1],  w2[WORD+1]; 

  printf("Prima parola ---> ");
  scanf("%s", w1);
  printf("Seconda parola ---> ");
  scanf("%s", w2);
  if(strUguale(w1,w2))
     printf("%s = %s\n", w1,w2);
  if(strMinore(w1,w2))
    printf("%s < %s\n", w1,w2);
  if(strMinore(w2,w1))
    printf("%s < %s\n", w2,w1);
  return 0;
}


/*** FUNZIONI PER LE OCCORRENZE  ***/


/* Crea un array contenente la parola w  e restituisce l'indirizzo nuovo array   */

char* newWord(char *w){
  char *new;
  new = calloc(strlen(w)+1, sizeof(char));
  strcpy(new, w);
  return new;
}


/* Crea  l'occorrenza  <w, 1> e restituisce un puntatore alla nuova occorrenza */

//newOccorrenza(w){
//}


/* Incrementa di 1 il valore di num dell'occorrenza  in p */

void incrementaOcc(node *p){
}

/* Decrementa di 1 il valore di num dell'occorrenza  in p */

void decrementaOcc(node *p){
}




/***  FUNZIONE PER  ALBERI  BINARI DI RICERCA CONTENENTI OCCORRENZE  ****/

/* Crea un albero  vuoto  */

node *newTree() {
    return NULL;
}


/*   Crea un  nodo contenente l'occorrenza <w,1>   */


//node *newNode(char* w){
//}


/* Inserisce un nuovo nodo contenente l'occorrenza <w,1> nell'albero r  
   e  restituisce  la radice dell'albero ottenuto   */

// node *treeInsert(char *w, node *r){
// }


/***  RICERCA    ***/

/*   Cerca un nodo contenente l'occorrenza di w  nell'albero  r.
     Se il nodo esiste restituisce il suo indirizzo, altrimenti restituisce NULL  */

// node *findWord(char *w, node *r){
// }



/*** ELIMINAZIONE DI UN NODO ****/



/* Libera la memoria occupata dal nodo p. Si assume p!=NULL */

void freeNode(node *p){
}


/* Cancella il nodo x dall'albero r  e restituisce la radice dell'albero ottenuto */ 


// NON RICHIEDE MODIFICHE

node *treeDelete(node *x, node *r){
  node *s;  // nodo che deve sostituire x 
  
  
  /***  Trova  il nodo s  che deve sostituire x  ***/
  
  if(x->left==NULL && x->right == NULL)
    /** CASO 1: x non ha figli **/
    s = NULL;
  else if (x->left == NULL || x->right == NULL)
    /** CASO 2:  x  ha un solo figlio   **/
    s = (x->left != NULL) ? x->left : x->right;
  else{ /**  CASO 3: x  ha  due figli   **/
/* s e' il figlio piu' a destra  nel sottoalbero sin. di x */
    s = x->left;
    while(s->right != NULL)
      s = s->right;
 /*  il figlio sin. di s prende il posto di s */
    if(s->up == x) // s e' figlio sin. di x 
      x->left = s->left;
    else  // s e' figlio destro di s->up 
      s->up->right = s->left;
    if (s->left != NULL)
      s->left->up = s->up;
    // i nuovi  figli di s sono i figli di x 
    s->left = x->left;
    if (s->left != NULL)
      s->left->up = s;
    s->right = x->right;
    if (s->right != NULL)
      s->right->up = s;
  }
  
  /***  Il nodo  x e' sostituito da s.
	Se x e' la radice, s diventa la radice del nuovo albero ***/
  
  if(x == r){ // x e' la radice 
    r = s; // nuova radice 
    if(r!= NULL) // il nuovo albero non e' vuoto 
      r->up = NULL;
  }
  else if (x->up->left == x){ // x e' figlio sin. 
    x->up->left = s;
    if(s != NULL) // s non e' vuoto 
      s->up = x->up;
  }
  else{  
    x->up->right = s;
    if(s != NULL) // s non e' vuoto 
      s->up = x->up;
  } 
 
 /***  Eliminazione del nodo x ***/

  freeNode(x); 
  return r;
}



/***  STAMPA  ***/



/* Stampa l'occorrenza  nel nodo p */

void printNode(node  *p){
}


/* Stampa  l'albero delle  occorrenze in ordine alfabetico  */

void printInorder(node *r) { 
  if(r != NULL){
    printInorder(r->left); 
    printNode(r);
    printInorder(r->right); 
  }
}



/* Stampa  l'albero delle  occorrenze in ordine alfabetico inverso  */


void printInorderInv(node *r) { 
}


/*** FUNZIONI PRINCIPALI ***/





/* Funzione che implementa l'operazione addWord(word). 
   proot e'  l'indirizzo della radice dell'albero delle occorrenze
   (passaggio  'per indirizzo') 
*/
    

// addWord(word, proot){
//}



/* Funzione che implementa l'operazione  addFromFile(fileName). 
   proot e'  l'indirizzo della radice dell'albero delle occorrenze
   (passaggio  'per indirizzo') 
*/
    
void addFromFile(char* fileName, node **proot){
  char word[WORD+1];
  FILE *fp;
  
  /* occorre aprire in lettura il file fileName */
  fp = fopen(fileName,"r");
  if(fp == NULL)  // il file fileName non esiste
     printf("%s: file inesistente\n", fileName);
   else{
     while(fscanf(fp,"%s", word) == 1) // word contiene la parola letta dal file
       // aggiungere la parola  word chiamando addWord()
   // Il ciclo while termina quando viene letto EOF  
   // Il file fp va chiuso
       fclose(fp); 
   }
}


/* Funzione che implementa l'operazione  printOcc(word).
   r e' la radice dell'albero delle occorrenze */

void printOcc(char *word, node* r){
}



/*  Funzione che implementa l'operazione printTab().
    r  e' la radice dell'albero delle occorrenze  */

void printTab(node *r){
  if(r == NULL)
    printf("Tabella vuota\n");
  else{
    printf("\nOCCORRENZE:\n");
    printInorder(r);
  }
}

/*  Funzione che implementa l'operazione printTabInv().
    r  e' la radice dell'albero delle occorrenze  */


void printTabInv(node *r){
}

/* Funzione che implementa l'operazione delWord(word). 
   proot e'  l'indirizzo della radice dell'albero delle occorrenze
   (passaggio  'per indirizzo') 
*/
    

// delWord(word, proot){
//}


/*** MAIN PROGRAMMA OCCORRENZE ***/


int mainOcc(){
  int c; 
 
  // DEFINIZIONI E INIZIALIZZAZIONI
  
  while((c=getchar()) != 'f'){
    /* esce dal ciclo quando viene letto il carattere f */ 
    switch(c){
    case '+':  // + word -->  addWord(word)
      break;
    case 'r':  // r fileName -->  addFromFile(fileName)
      break;
    case '?':  // ? word -->    printOcc(word)
      break;
    case '-':   // - word -->    delWord(word)
      break;
    case 'p':  // p -->    printTab() 
      break;  
    case 'i':  // i  -->    printTabInv() 
      break;  
    }  // end switch 
  } // end while 
  return 0;
}