[Avl-cvs] avl/src avl.cpp,1.10,1.11 avlt.cpp,1.7,1.8 avlt.h,1.8,1.9 bst.cpp,1.10,1.11 bst.h,1.5,1.6

[Patrizio B. <het...@us...>]

Update of /cvsroot/avl/avl/src
In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv7147/src

Modified Files:
	avl.cpp avlt.cpp avlt.h bst.cpp bst.h 
Log Message:
bug fix and updates


Index: bst.h
===================================================================
RCS file: /cvsroot/avl/avl/src/bst.h,v
retrieving revision 1.5
retrieving revision 1.6
diff -C2 -d -r1.5 -r1.6
*** bst.h	6 Sep 2004 13:16:36 -0000	1.5
--- bst.h	6 Sep 2004 14:12:06 -0000	1.6
***************
*** 39,43 ****
    void print_ric( int, int );
  #ifdef GUI
!   void ric();
  #else
    void c_print(char*);
--- 39,43 ----
    void print_ric( int, int );
  #ifdef GUI
!   void print_gtk_ric();
  #else
    void c_print(char*);
***************
*** 61,85 ****
    //operazioni sugli alberi
    Bst *root();
!   bool isLeaf(); //OK
!   bool isRoot(); //OK
!   int level(); //OK
!   int nodes(); //OK
    int leaves();
    int height();
  
    //operazioni tipiche dei BST
!   Bst *search(int); //OK
!   void insert(int); //OK
!   void erase(int); //Non testato
!   Bst *max(); //OK
!   Bst *min(); //OK
!   Bst *predecessor(); //OK
!   Bst *successor(); //OK
    
    void print();
  #ifndef GUI
!   void print1();
  #else
!   GtkWidget* print1();
  #endif
  };
--- 61,85 ----
    //operazioni sugli alberi
    Bst *root();
!   bool isLeaf(); 
!   bool isRoot(); 
!   int level(); 
!   int nodes(); 
    int leaves();
    int height();
  
    //operazioni tipiche dei BST
!   Bst *search(int); 
!   void insert(int); 
!   void erase(int); 
!   Bst *max(); 
!   Bst *min(); 
!   Bst *predecessor(); 
!   Bst *successor();
    
    void print();
  #ifndef GUI
!   void print_best_look();
  #else
!   GtkWidget* print_best_look();
  #endif
  };

Index: bst.cpp
===================================================================
RCS file: /cvsroot/avl/avl/src/bst.cpp,v
retrieving revision 1.10
retrieving revision 1.11
diff -C2 -d -r1.10 -r1.11
*** bst.cpp	6 Sep 2004 13:16:36 -0000	1.10
--- bst.cpp	6 Sep 2004 14:12:06 -0000	1.11
***************
*** 75,79 ****
  }
  
! /** Restituisce la radice dell'albero a cui appartiene il nodo corrente*/
  Bst *Bst::root()
  {
--- 75,79 ----
  }
  
! /* Restituisce la radice dell'albero a cui appartiene il nodo corrente*/
  Bst *Bst::root()
  {
***************
*** 84,95 ****
  }
  
! /** Indica se il nodo corrente è una foglia */
  bool Bst::isLeaf()
  {
-   //testa (getLeft()==NULL && getRight()==NULL) <==> (!getLeft() && !getRight()) <==> !(getLeft()||getRight())
    return !(getLeft()||getRight());
  }
  
! /** Indica se il nodo è la radice dell'albero*/
  bool Bst::isRoot()
  {
--- 84,94 ----
  }
  
! /* Indica se il nodo corrente è una foglia */
  bool Bst::isLeaf()
  {
    return !(getLeft()||getRight());
  }
  
! /* Indica se il nodo è la radice dell'albero*/
  bool Bst::isRoot()
  {
***************
*** 97,101 ****
  }
  
! /** Calcola il livello del nodo (ovvero la lunghezza del cammino tra il nodo e la radice)*/
  int Bst::level()
  {
--- 96,100 ----
  }
  
! /* Calcola il livello del nodo (ovvero la lunghezza del cammino tra il nodo e la radice)*/
  int Bst::level()
  {
***************
*** 107,111 ****
  }
  
! /** Calcola il numero di nodi dell'albero che ha come radice il nodo*/
  int Bst::nodes()
  {
--- 106,110 ----
  }
  
! /* Calcola il numero di nodi dell'albero che ha come radice il nodo*/
  int Bst::nodes()
  {
***************
*** 121,125 ****
  }
  
! /** Calcola il numero di foglie dell'albero che ha come radice il nodo*/
  int Bst::leaves()
  {
--- 120,124 ----
  }
  
! /* Calcola il numero di foglie dell'albero che ha come radice il nodo*/
  int Bst::leaves()
  {
***************
*** 135,139 ****
  }
  
! /** Calcola l'altezza (lunghezza del ramo più lungo) dell'albero che ha come radice il nodo*/
  int Bst::height()
  {
--- 134,138 ----
  }
  
! /* Calcola l'altezza (lunghezza del ramo più lungo) dell'albero che ha come radice il nodo*/
  int Bst::height()
  {
***************
*** 151,155 ****
  }
  
! /** Ricerca un nodo di valore key in modo iterativo e ne restituisce il puntatore, se la ricerca ha esito negativo restituisce NULL*/
  Bst *Bst::search(int key)
  {
--- 150,154 ----
  }
  
! /* Ricerca un nodo di valore key in modo iterativo e ne restituisce il puntatore, se la ricerca ha esito negativo restituisce NULL*/
  Bst *Bst::search(int key)
  {
***************
*** 170,174 ****
  }
  
! /** Aggiunge un nodo con valore key nell'albero*/
  void Bst::insert(int key)
  {
--- 169,173 ----
  }
  
! /* Aggiunge un nodo con valore key nell'albero*/
  void Bst::insert(int key)
  {
***************
*** 239,243 ****
  }
  
! /** Elimina il nodo di valore key dall'albero*/
  void Bst::erase(int key)
  {
--- 238,242 ----
  }
  
! /* Elimina il nodo di valore key dall'albero*/
  void Bst::erase(int key)
  {
***************
*** 251,255 ****
  }
  
! /** Trova il nodo dell'albero che ha valore massimo e ne restituisce il puntatore*/
  Bst *Bst::max()
  {
--- 250,254 ----
  }
  
! /* Trova il nodo dell'albero che ha valore massimo e ne restituisce il puntatore*/
  Bst *Bst::max()
  {
***************
*** 260,264 ****
  }
  
! /** Trova il nodo dell'albero che ha valore minimo e ne restituisce il puntatore*/
  Bst *Bst::min()
  {
--- 259,263 ----
  }
  
! /* Trova il nodo dell'albero che ha valore minimo e ne restituisce il puntatore*/
  Bst *Bst::min()
  {
***************
*** 269,273 ****
  }
  
! /** Restituisce il puntatore del nodo predecessore (Il nodo che ha valore maggiore tra quelli che hanno valore minore)*/
  Bst *Bst::predecessor()
  {
--- 268,272 ----
  }
  
! /* Restituisce il puntatore del nodo predecessore (Il nodo che ha valore maggiore tra quelli che hanno valore minore)*/
  Bst *Bst::predecessor()
  {
***************
*** 288,292 ****
  }
  
! /** Restituisce il puntatore del nodo successore (Il nodo che ha valore minore tra quelli che hanno valore maggiore)*/
  Bst *Bst::successor()
  {
--- 287,291 ----
  }
  
! /* Restituisce il puntatore del nodo successore (Il nodo che ha valore minore tra quelli che hanno valore maggiore)*/
  Bst *Bst::successor()
  {
***************
*** 307,326 ****
  }
  
- /*void Bst::print_ric(Bst* root, int level)
- {
-     int i;
-     if(root == NULL) 
-       return;
-     
-     print_ric(root->left, level+1);
-     printf("%d[%d],", root->getValue(),level);
-     print_ric(root->right, level+1);
- }
- 
- void Bst::print()
- {
-     print_ric(this, 0);
- }*/
- 
  
  void Bst::print_ric(int lev, int tab)
--- 306,309 ----
***************
*** 383,391 ****
  				printf("[%i;%i;40m",format,color);
  			}
! 			else if(*string=='b'){//BLUE
  				color=BLUE;
  				printf("[%i;%i;40m",format,color);
  			}
! 			else if(*string=='y'){//BLUE
  				color=YELLOW;
  				printf("[%i;%i;40m",format,color);
--- 366,374 ----
  				printf("[%i;%i;40m",format,color);
  			}
! 			else if(*string=='b'){// blue
  				color=BLUE;
  				printf("[%i;%i;40m",format,color);
  			}
! 			else if(*string=='y'){// yellow
  				color=YELLOW;
  				printf("[%i;%i;40m",format,color);
***************
*** 399,403 ****
  }
  // usa c_print per stampare a colori. Funzione ricorsiva
! void Bst::print1()
  {
     char buffer[50];
--- 382,386 ----
  }
  // usa c_print per stampare a colori. Funzione ricorsiva
! void Bst::print_best_look()
  {
     char buffer[50];
***************
*** 426,432 ****
     }
    if( getLeft() )
!     getLeft()->print1();
    if( getRight() )
!     getRight()->print1();
  }
  
--- 409,415 ----
     }
    if( getLeft() )
!     getLeft()->print_best_look();
    if( getRight() )
!     getRight()->print_best_look();
  }
  
***************
*** 439,443 ****
  GtkTreeStore *store;
  
! void Bst::ric()
  {
  
--- 422,426 ----
  GtkTreeStore *store;
  
! void Bst::print_gtk_ric()
  {
  
***************
*** 455,459 ****
  	
  	iter2=iter1; 
! 	getRight()->ric();    
      }
      iter2=aux; //riprende dopo aver appeso i rami destri, e termina con i rami sinistri
--- 438,442 ----
  	
  	iter2=iter1; 
! 	getRight()->print_gtk_ric();    
      }
      iter2=aux; //riprende dopo aver appeso i rami destri, e termina con i rami sinistri
***************
*** 467,471 ****
  	
  	iter2=iter1;
! 	getLeft()->ric();
      
      }
--- 450,454 ----
  	
  	iter2=iter1;
! 	getLeft()->print_gtk_ric();
      
      }
***************
*** 474,478 ****
  
  
! GtkWidget* Bst::print1()
  {
      GtkWidget *scrolled_window;
--- 457,461 ----
  
  
! GtkWidget* Bst::print_best_look()
  {
      GtkWidget *scrolled_window;
***************
*** 505,510 ****
      
      //prendo la root e stampo tutto l'albero, appendo il primo valore e poi ricorsivamente tutti gli altri
!     if (this->root() != NULL) root=this->root();
!     else root=this;
      msg = g_strdup_printf ("%d", root->getValue());
      gtk_tree_store_append (GTK_TREE_STORE (store), &iter2,&iter1);
--- 488,493 ----
      
      //prendo la root e stampo tutto l'albero, appendo il primo valore e poi ricorsivamente tutti gli altri
!     root=this->root();
! 
      msg = g_strdup_printf ("%d", root->getValue());
      gtk_tree_store_append (GTK_TREE_STORE (store), &iter2,&iter1);
***************
*** 512,516 ****
      g_free(msg);
      
!     root->ric();
  
      //finalizzazione: creo una cella e metto in una colonna, che poi metto nell'albero.
--- 495,499 ----
      g_free(msg);
      
!     root->print_gtk_ric();
  
      //finalizzazione: creo una cella e metto in una colonna, che poi metto nell'albero.

Index: avl.cpp
===================================================================
RCS file: /cvsroot/avl/avl/src/avl.cpp,v
retrieving revision 1.10
retrieving revision 1.11
diff -C2 -d -r1.10 -r1.11
*** avl.cpp	6 Sep 2004 13:16:36 -0000	1.10
--- avl.cpp	6 Sep 2004 14:12:06 -0000	1.11
***************
*** 26,129 ****
  int main(int argc, char *argv[])
  {
- #if 0
-  // Bst a(1 ), *b;
-   
-  Avlt *a, *b;
- /*  a.insert(3);
-   a.insert(5);
-   a.insert(4);
-   a.insert(2);
-   a.insert(10);
-   a.insert(-10);
-   a.insert(-1);
-   a.insert(20);
-   a.insert(-20);
-   a.insert(-25);
-   a.insert(-15);
-   a.insert(-6);
-   a.insert(-200);
-   a.insert(-300);
-   a.insert(-400);
-   a.insert(-500);
-   a.insert(-600);
-   a.insert(-700);
-   */
  
- /*  a.insert(6);
-   
-   
-   a.insert(3);
- //  a.insert(-3);
- */
- 
-  Avlt *a = new Avlt(0,1);
-  
-   for (int i=0;i<567;i++)
-   {
-     int aaa=(rand()%1000)-500;
-     a = a->insert( aaa );
-     //if(i>=19)
-     {
- /*      printf("%d->%d\n",i,aaa);
-       if(!a->checkBalance())
-       {
-       a->print();
-       printf("\n-------------------------------------------------------------\n");
-       }*/
-     }
-   }
-   a->print();
- 
-  // a->search(-8)->print1();
- /*  printf("%d\n",a->nodes());
-   a = a->erase(277);
-   a = a->erase(3);
-   a = a->erase(-3);
-   a = a->erase(-8);
-   a = a->erase(-165);
-   a = a->erase(190);
-   a = a->erase(415);
-   a = a->erase(a->root()->getValue());
-  // a = a->erase(-7);
-   printf("\n%d\n",a->nodes());
-   
-   printf("\n%d",a->checkBalance());*/
- //a->print1();
-  // a->search(3)->print1();
-   //a->print();
-   /*
-   a = a->insert(-98);
-   a = a->insert(100);
-   a = a->insert(-1000);
-   a = a->insert(-10);
-   a = a->insert(50);
-   a = a->insert(102);
-   a = a->insert(1000);
-   
-   a->print();
-   
-   a->erase(50);
-   a->print1();*/
-  // a->print();
-   /*vector<Avlt *> v;
-   v = a->getWrongs();
-   
-   for (int i=0; i<v.size(); i++)
-      cout << (v[i])->getValue() << endl;
-   */
-  // printf("%d",a->getFdb());
- //  a->print();
- //  b = (a.getLeft())->getLeft()->getRight();
- //  printf("%d",b->getValue());
- #endif
- 
- 
- 
- 
- 
- /*
  // 0= test avl
  // 1= test bst
!  Test *prova_avl, *prova_bst;
   int upper_bound=1000;
   int base_tree=10000;
--- 26,38 ----
  int main(int argc, char *argv[])
  {
  
  // 0= test avl
  // 1= test bst
! // 2= test comparativo
! 
!  Test *prova=NULL;
!  Avlt* aux_avl=NULL;
!  Bst* aux_bst=NULL;
!  
   int upper_bound=1000;
   int base_tree=10000;
***************
*** 136,200 ****
   printf("Insert the number of changements you want to do on the tree\n");
   scanf("%d",&upper_bound);
   if (choice==0) {
  	printf("Processing AVL, wait\n");
! 	prova_avl = new Test(0,upper_bound,base_tree);
   }
   if (choice==1) {
   	printf("Processing BST, wait\n");
!  	prova_bst = new Test(1,upper_bound,base_tree);
   }
   if (choice==2) {
          printf("Comparation on the way, wait\n");
!         prova_bst = new Test(2,upper_bound,base_tree);
   }
- */
  
   
- //Test *prova;
- //prova = new Test(1,5,1);
- //prova->getBst()->print1();
- //not a good thing...for testing purpose only
- //prova->getAvlt()->print1();
- 
-   /*Bst a(1 );
-   a.insert(3);
-   a.insert(5);
-   a.insert(4);
-   a.insert(2);
-   a.insert(10);
-   a.insert(-10);
-   a.insert(-1);
-   a.insert(20);
-   a.insert(-20);
-   a.insert(-25);
-   a.insert(-15);
-   a.insert(-6);
-   a.insert(-200);
-   a.insert(-300);
-   a.insert(-400);
-   a.insert(-500);
-   a.insert(-600);
-   a.insert(-700);
-   a.erase(1);*/
-   Bst a(1);
-   
-  /* for (int i=0;i<500000;i++)
-   {
-     int aaa=(rand()%1000000)-500000;
-     a.insert( aaa );
-   }
-   for (int i=0;i<1000000;i++)
-   {
-     int aaa=(rand()%1000000)-500000;
-     a.erase( aaa );
-   }*/
-   Test t(0,10,100000);
-   a=*(t.getBst());
  #ifndef GUI
!   a.print1();
  #else
!     GtkWidget *window;
!     GtkWidget *vpaned;
!     GtkWidget *node_list;
  
      gtk_init (&argc, &argv);
--- 45,73 ----
   printf("Insert the number of changements you want to do on the tree\n");
   scanf("%d",&upper_bound);
+  
   if (choice==0) {
  	printf("Processing AVL, wait\n");
! 	prova = new Test(0,upper_bound,base_tree);
! 	aux_avl=prova->getAvlt();
   }
   if (choice==1) {
   	printf("Processing BST, wait\n");
!  	prova = new Test(1,upper_bound,base_tree);
! 	aux_bst=prova->getBst();
   }
   if (choice==2) {
          printf("Comparation on the way, wait\n");
!         prova = new Test(2,upper_bound,base_tree);
   }
  
   
  #ifndef GUI
!     if (choice==0)  aux_avl->print_best_look();
!     if (choice==1)  aux_bst->print_best_look();
  #else
!     if (choice==0 || choice==1) {
!     GtkWidget *window=NULL;
!     GtkWidget *vpaned=NULL;
!     GtkWidget *node_list=NULL;
  
      gtk_init (&argc, &argv);
***************
*** 215,220 ****
      gtk_widget_show (vpaned);
  
!     node_list = a.print1();
! 
      gtk_paned_add1 (GTK_PANED (vpaned), node_list);
      gtk_widget_show (node_list);
--- 88,94 ----
      gtk_widget_show (vpaned);
  
!     if (choice==0)  node_list = aux_avl->print_best_look();
!     if (choice==1)  node_list = aux_bst->print_best_look();
!   
      gtk_paned_add1 (GTK_PANED (vpaned), node_list);
      gtk_widget_show (node_list);
***************
*** 223,226 ****
--- 97,101 ----
  
      gtk_main ();
+     }
  #endif
  	return EXIT_SUCCESS;

Index: avlt.h
===================================================================
RCS file: /cvsroot/avl/avl/src/avlt.h,v
retrieving revision 1.8
retrieving revision 1.9
diff -C2 -d -r1.8 -r1.9
*** avlt.h	6 Sep 2004 13:16:36 -0000	1.8
--- avlt.h	6 Sep 2004 14:12:06 -0000	1.9
***************
*** 42,46 ****
    ~Avlt();
  
- //  void setFdb( int );
    void setFdb();
    void setFdb(Avlt *, Avlt *);
--- 42,45 ----

Index: avlt.cpp
===================================================================
RCS file: /cvsroot/avl/avl/src/avlt.cpp,v
retrieving revision 1.7
retrieving revision 1.8
diff -C2 -d -r1.7 -r1.8
*** avlt.cpp	6 Sep 2004 13:16:36 -0000	1.7
--- avlt.cpp	6 Sep 2004 14:12:06 -0000	1.8
***************
*** 32,42 ****
  }
  
! /** Imposta il Fattore di Bilanciamento a s*/
! /*void Avlt::setFdb( int s )
! {
!   setHeight(s);
! }
! */
! /** Calcola il FdB del nodo corrente*/
  void Avlt::setFdb()
  {
--- 32,36 ----
  }
  
! /* Calcola il FdB del nodo corrente*/
  void Avlt::setFdb()
  {
***************
*** 56,60 ****
  }
  
! /** Calcola il fattore di bilanciamento a di tutti i nodi del cammino da start a end*/
  void Avlt::setFdb( Avlt * start , Avlt * end)
  {
--- 50,54 ----
  }
  
! /* Calcola il fattore di bilanciamento a di tutti i nodi del cammino da start a end*/
  void Avlt::setFdb( Avlt * start , Avlt * end)
  {
***************
*** 91,95 ****
  }
  
! /** Effettua una rotazione verso sinistra e restituisce il nuovo nodo genitore*/
  Avlt *Avlt::leftRotate() //dd
  {
--- 85,89 ----
  }
  
! /* Effettua una rotazione verso sinistra e restituisce il nuovo nodo genitore*/
  Avlt *Avlt::leftRotate() //dd
  {
***************
*** 125,129 ****
  }
  
! /** Effettua una rotazione verso destra e restituisce il nuovo nodo genitore*/
  Avlt *Avlt::rightRotate() //ss
  {
--- 119,123 ----
  }
  
! /* Effettua una rotazione verso destra e restituisce il nuovo nodo genitore*/
  Avlt *Avlt::rightRotate() //ss
  {
***************
*** 159,163 ****
  }
  
! /** Inserisce un nuovo nodo con valore key utilizzando un algoritmo ricorsivo*/
  Avlt *Avlt::insert(int key)
  {
--- 153,157 ----
  }
  
! /* Inserisce un nuovo nodo con valore key utilizzando un algoritmo ricorsivo*/
  Avlt *Avlt::insert(int key)
  {
***************
*** 217,221 ****
  }
  
! /** Inserisce un nuovo nodo con valore key utilizzando un algoritmo iterativo*/
  Avlt *Avlt::insert_iter(int key)
  {
--- 211,215 ----
  }
  
! /* Inserisce un nuovo nodo con valore key utilizzando un algoritmo iterativo*/
  Avlt *Avlt::insert_iter(int key)
  {
***************
*** 321,325 ****
  }
  
! /** Elimina il nodo di valore key dall'albero*/
  Avlt *Avlt::erase(int key)
  {
--- 315,319 ----
  }
  
! /* Elimina il nodo di valore key dall'albero*/
  Avlt *Avlt::erase(int key)
  {
***************
*** 421,425 ****
  }
  
! /** Verifica se l'albero è bilanciato*/
  bool Avlt::checkBalance()
  {
--- 415,419 ----
  }
  
! /* Verifica se l'albero è bilanciato*/
  bool Avlt::checkBalance()
  {
***************
*** 437,441 ****
  }
  
! /** Restituisce un vettore di nodi che hanno FdB diverso da -1,0,+1*/
  vector<Avlt *> Avlt::getWrongs()
  {
--- 431,435 ----
  }
  
! /* Restituisce un vettore di nodi che hanno FdB diverso da -1,0,+1*/
  vector<Avlt *> Avlt::getWrongs()
  {