/* albero.cc
 * Scrivere un programma che definisca un albero binario il cui nodo contiene, 
 * come dati, due interi. Il primo intero sarà la chiave, mentre il secondo 
 * indicherà l'ordine di creazione. Usando una variabile globale come 
 * puntatore alla radice dell'albero,
 *      scrivere: 
 *             Una funzione ricorsiva che inserisca un nodo nell'albero 
 *             Una funzione che crei (allochi) un nodo e lo inserisca 
 *                nell'albero, usando al bisogno la funzione ricorsiva di cui sopra. 
 *             Una funzione ricorsiva che 'traversi' l'albero, stampando il contenuto di ogni nodo, nell'ordine 
 *             Una funzione ricorsiva che liberi la memoria occupata dall'albero 
 *             Un programma principale che, utilizzando le funzioni scritte: 
 *                1.Crei un'albero di venti numeri casuali 
 *                2.Li stampi in maniera ordinata, secondo il valore casuale 
 *                3.Liberi la memoria occupata dall'alabero
 * Modificare il programma dell'albero binario assegnato in precedenza (soluzione precedente) in modo da: 
 *          1.creare una classe astratta 'albero' con un attributo statico per il puntoatore alla radice. Dovrà avere: 
 *                    Solo i puntatori 'destro' e sinistro', come attributi non staitic 
 *                    Un costruttore di default che inserisca il nuovo nodo creato nell'albero 
 *                    Un distruttore virtuale che distrugga l'intero albero 
 *                    Un metodo virtuale puro 'confronto' privato con un parametro di tipo void *, 
 *                       che confronta il nodo corrente con quello passato per parametro 
 *                    Un metodo virtuale puro 'stampa' privato che stampa il nodo corrente 
 *                    Un metodo pubblico 'traversa' che stampa, tramite il memtodo stampa l'intero albero 
 *                    Un metodo statico pubblico 'elimina' che esegua la 'delete' dell'intero albero 
 *          2.Una classe alberoIntero che derivi in modo privato da albero, la quale: 
 *                    Possegga due attributi interi chiave e valore 
 *                    Implementi i metodi virtuali pure di albero 
 *                    Renda visibili i metodi 'traversa' e 'elimina' 
 *       Tutti gli attributi devono essere privati 
 */

#include <stdio.h>	// Per le funzioni 'srand' e 'random'
#include <stdlib.h>	// Per la funzione 'time'
#include <time.h>

// Struttura del nodo, come descritto nel testo
class albero {
    albero *sinistro;                   // Puntatore al sottoalbero sinistro
    albero *destro;                     // Puntatore al sottoalbero destro
    static albero *radice;              // Puntatore alla radice (statico)

    void inserisci (albero *n);         // Inserisci ricorsiva, usata internamente
    void traversa ();                   // Traversa ricorsiva, usata internamente

    virtual int compare (void *n) = 0;  // Compare, virtuale pura
    virtual void print () = 0;          // Print, virtula pura
public:
    albero () { sinistro = destro = (albero*) 0; if (radice) radice -> inserisci (this); else radice = this; };
    virtual ~albero ();
    // Funzioni statiche, inerfaccia all'albero nel suo insieme
    static void elimina () { if (radice) delete radice;};
    static void Traversa () { if (radice) radice -> traversa (); };
};

class alberoIntero : private albero {
    int chiave;  // Dati del nodo
    int valore;

    virtual int compare (void *n);  // Implementazione delle virtuali pure di 'albero'
    virtual void print ();
public:
    alberoIntero (int Valore, int Chiave) { chiave = Chiave; valore = Valore; };
    albero::elimina;     // Rendo di nuovo visibile 'elimina'
    albero::Traversa;    // Rendo di nuovo visibile 'Traversa'
};

int alberoIntero::compare (void *n)
{
  return ((alberoIntero *) n) -> chiave - chiave; // Ritorna la differenza fra le chiavi (il confronto)
}

void alberoIntero::print ()
{
  // Stampa i valori del nodo (chiave in un campo di 12, '->' ed il valore in un campo di 2
  printf ("%14d -> %2d\n", chiave, valore);
}

albero *albero::radice;

/* Aggiunge all'albero o sottoalbero puntato da 'a'
 * il nodo puntato da 'n' */
void albero::inserisci (albero *n)
{
  if (compare (n))  // Chiama la 'compare' virtuale, per sapere da che parte mettere il nuovo nodo
  {	// Se il nodo va' aggiunto a sinistra
    if (sinistro != NULL) // Se esiste un sottoalbero di sinistra
      sinistro -> inserisci (n);	// Aggiungo a quel sottalbero
    else	// Se il sottalbero non esiste
      sinistro = n;	// diventa radice del sottoalbero
  }
  else
  {	// Se il nodo va' aggiunto a destra
    if (destro != NULL) // Se esiste un sottoalbero di destra
      destro -> inserisci (n);	// Aggiungo a quel sottalbero
    else	// Se il sottalbero non esiste
      destro = n;	// diventa radice del sottoalbero
  }
} 

/* Metodo che stampa in ordine un sottoalbero, puntato da 'a' */
void albero::traversa ()
{
  if (sinistro)		// Se esiste il sottoalbero sinistro
    sinistro -> traversa ();	// Lo stampa
  print ();             // Chiama la 'print' virtuale per stampare il nodo
  if (destro)		// Se esiste il sottoalbero destro
    destro -> traversa ();	// Lo stampa
}

/* Funzione che libera la memoria occupata da un sottoalbero */
albero::~albero ()
{
  if (sinistro)		// Se esiste un sottoalbero sinistro
    delete sinistro;	// Libera prima la memoria di quel sottoalbero
  if (destro)		// Se esiste un sottoalbero destro
    delete destro;	// Libera prima la memoria di quel sottoalbero
}

/* Funzione principale */
int main ()
{
  srandom (time (NULL));              /* Inizializza il generatore di numeri casuali
                                       * utilizzando il tempo corrente (molto variabile) */
  for (int i = 0; i < 20; i++)	      // Ciclo da 0 a 19
    new alberoIntero (i, random ());  // crea nodo con valore l'indice e chiave casuale
  alberoIntero::Traversa ();          // Stampa l'albero tramite il metodo statico
  alberoIntero::elimina ();           // Libera la memoria dell'albero tramite il metodo statico,
                                      // visto che non ho accesso alla radice
  return 0;
}