[Avl-cvs] avl/src avl.cpp,1.5,1.6 bst.cpp,1.5,1.6 test.cpp,1.3,1.4 test.h,1.5,1.6

SourceForge Headquarters 225 Broadway Suite 1600 San Diego, CA 92101 +1 (858) 422-6466

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

Modified Files:
	avl.cpp bst.cpp test.cpp test.h 
Log Message:
Test class completed

Index: test.h
===================================================================
RCS file: /cvsroot/avl/avl/src/test.h,v
retrieving revision 1.5
retrieving revision 1.6
diff -C2 -d -r1.5 -r1.6
*** test.h	17 Jul 2004 14:12:59 -0000	1.5
--- test.h	17 Jul 2004 17:05:54 -0000	1.6
***************
*** 5,10 ****
  #include "bst.h"

! //check the time! will be changed soon
! #define mytime int 

  using namespace std;
--- 5,10 ----
  #include "bst.h"

! #include <time.h>
! #include <list>

  using namespace std;
***************
*** 16,21 ****
  	Test();
  	~Test();
! 	Test(int,int,int=150);
! 	mytime getTimer();
  	Avlt* getAvlt();
  	Bst* getBst();
--- 16,20 ----
  	Test();
  	~Test();
! 	Test(int,int=1000,int=1500);
  	Avlt* getAvlt();
  	Bst* getBst();
***************
*** 24,30 ****
  	void Avl_Test(int);
  	void Bst_Test(int);
! 	void Test_Init(int);
  	Avlt* avlt;
  	Bst* bst;

  };
--- 23,34 ----
  	void Avl_Test(int);
  	void Bst_Test(int);
! 	void comparation(int,int);
! 	void Test_Init(int,int);
! 	double getInitTimer();
! 	double getChangeTimer();
  	Avlt* avlt;
  	Bst* bst;
+ 	double init_timer;
+ 	double change_timer;

  };

Index: bst.cpp
===================================================================
RCS file: /cvsroot/avl/avl/src/bst.cpp,v
retrieving revision 1.5
retrieving revision 1.6
diff -C2 -d -r1.5 -r1.6
*** bst.cpp	15 Jul 2004 12:47:21 -0000	1.5
--- bst.cpp	17 Jul 2004 17:05:54 -0000	1.6
***************
*** 167,171 ****
      if ( key == aux1->getValue() )
      {
!       printf("The number -> %d is already in the Binary Search Tree\n",key);
        return;
      }
--- 167,171 ----
      if ( key == aux1->getValue() )
      {
!       //printf("The number -> %d is already in the Binary Search Tree\n",key);
        return;
      }

Index: test.cpp
===================================================================
RCS file: /cvsroot/avl/avl/src/test.cpp,v
retrieving revision 1.3
retrieving revision 1.4
diff -C2 -d -r1.3 -r1.4
*** test.cpp	17 Jul 2004 14:12:59 -0000	1.3
--- test.cpp	17 Jul 2004 17:05:54 -0000	1.4
***************
*** 1,4 ****
  #include "test.h"
- #include <list>

  Test::~Test() {
--- 1,3 ----
***************
*** 6,14 ****
  if (avlt) delete avlt;
  if (bst) delete bst;
  }

  Test::Test() {
! 	Test(0,60,150);
  }

--- 5,14 ----
  if (avlt) delete avlt;
  if (bst) delete bst;
+ 
  }

  Test::Test() {
! 	Test(0,1000,1500);
  }

***************
*** 23,40 ****
  }

! void Test::Test_Init(int base_limit) {

  	int random;
! 		
  	srand ( time(NULL) );
! 	if (avlt) {
! 		
  		for (int i=0;i<base_limit;i++) {
! 			random=rand()%1000;
  			avlt=avlt->insert(random);
  		}
! 
  	}
! 
  }

--- 23,59 ----
  }

! void Test::Test_Init(int base_limit,int kind=0) {

  	int random;
! 	clock_t start, end;
! 
  	srand ( time(NULL) );
! 	
! 	if (avlt && kind==0) {
! 		start = clock();
  		for (int i=0;i<base_limit;i++) {
! 			random=rand()%10000;
  			avlt=avlt->insert(random);
+ 		//	insertion_list.push_back(random);
  		}
! 		end = clock();
! 		init_timer = ((double) (end - start)) / CLOCKS_PER_SEC;
! 		printf("AVL Initialization of %d items tree took %lf seconds\n",base_limit,init_timer);
! 	//	getchar();
  	}
! 	
! 	if (bst && kind==1) {
! 		start = clock();
! 		for (int i=0;i<base_limit;i++) {
! 			random=rand()%10000;
! 			bst->insert(random);
! 		//	insertion_list.push_back(random);
! 		}
! 		end = clock();
! 		init_timer = ((double) (end - start)) / CLOCKS_PER_SEC;
! 		printf("BST Initialization of %d items tree took %lf seconds\n",base_limit,init_timer);
! 	//	getchar();
! 	}
! 	
  }

***************
*** 45,61 ****
  	int decision;
  	int random_erase;
! 	list<int> insertion_list;
  	list<int>::iterator IT;
  	int x;
  	srand ( time(NULL) );
  	if (avlt) {
! 		
  		for (int i=0;i<upper_limit;i++) {
! 			random=rand()%1000;
  			decision=rand()%2;
  			if (decision==0) {
  				avlt=avlt->insert(random);
  				insertion_list.push_back(random);
! 				printf("inserted number %d\n",random);
  			}
  			else if (!insertion_list.empty()){
--- 64,85 ----
  	int decision;
  	int random_erase;
! 	int erase_counter=0,insert_counter=0;
  	list<int>::iterator IT;
+ 	list<int> insertion_list;
  	int x;
+ 	clock_t start, end;
+ 	int waste=0;
  	srand ( time(NULL) );
+ 	
  	if (avlt) {
! 		start=clock();
  		for (int i=0;i<upper_limit;i++) {
! 			random=rand()%10000;
  			decision=rand()%2;
  			if (decision==0) {
  				avlt=avlt->insert(random);
  				insertion_list.push_back(random);
! 				//printf("inserted number %d\n",random);
! 				insert_counter++;
  			}
  			else if (!insertion_list.empty()){
***************
*** 68,80 ****
  					if (x==random_erase) {
  						//printf("x:%d value=%d\n",x,*IT);
! 						printf("erased number %d\n",*IT);
  						avlt=avlt->erase(*IT);
  						if (IT!=insertion_list.end()) insertion_list.erase(IT);
  					}
  				}			
! 			}			

  		}
! 
  	}

--- 92,110 ----
  					if (x==random_erase) {
  						//printf("x:%d value=%d\n",x,*IT);
! 				//		printf("erased number %d\n",*IT);
  						avlt=avlt->erase(*IT);
  						if (IT!=insertion_list.end()) insertion_list.erase(IT);
+ 						erase_counter++;
  					}
  				}			
! 			}
! 			else waste++;

  		}
! 		end=clock();
! 		change_timer = ((double) (end - start)) / CLOCKS_PER_SEC;
! 		printf("AVL TEST RESULTS:\n%d insertions and %d deletions took %lf seconds.\nTotal of %d cycles, wasted:%d\n",insert_counter,erase_counter,change_timer,upper_limit,waste);
! 		printf("press Return to exit\n");
! 		//getchar();
  	}

***************
*** 83,102 ****
  void Test::Bst_Test(int upper_limit) {

  }

! Test::Test(int kind, int upperbound, int base_tree_size=150) {

  	switch (kind){
  		case 0:
  			avlt=new Avlt();
! 			Test_Init(base_tree_size);
  			Avl_Test(upperbound);
  			break;
  		case 1:
  			bst=new Bst();
! 			//Test_Init(); not ready for both
  			Bst_Test(upperbound);
  			break;
  		default:
  			printf("Invalid test selection, application will abort\n");
--- 113,206 ----
  void Test::Bst_Test(int upper_limit) {

+ 	int random;
+ 	int decision;
+ 	int random_erase;
+ 	int erase_counter=0,insert_counter=0;
+ 	list<int>::iterator IT;
+ 	list<int> insertion_list;
+ 	int x;
+ 	clock_t start, end;
+ 	int waste=0;
+ 	
+ 	srand ( time(NULL) );
+ 	
+ 	if (bst) {
+ 		start=clock();
+ 		for (int i=0;i<upper_limit;i++) {
+ 			random=rand()%10000;
+ 			decision=rand()%2;
+ 			if (decision==0) {
+ 				bst->insert(random);
+ 				insertion_list.push_back(random);
+ 				//printf("inserted number %d\n",random);
+ 				insert_counter++;
+ 			}
+ 			else if (!insertion_list.empty()){
+ 			
+ 				random_erase=rand()%insertion_list.size();
+ 
+ 				for ( IT=insertion_list.begin(), x=0; x<=random_erase && IT!=insertion_list.end();
+ 				 IT++, x++) 
+ 				{
+ 					if (x==random_erase) {
+ 						//printf("x:%d value=%d\n",x,*IT);
+ 				//		printf("erased number %d\n",*IT);
+ 						bst->erase(*IT);
+ 						if (IT!=insertion_list.end()) insertion_list.erase(IT);
+ 						erase_counter++;
+ 					}
+ 				}			
+ 			} else waste++;
+ 			
+ 		}
+ 		end=clock();
+ 		change_timer = ((double) (end - start)) / CLOCKS_PER_SEC;
+ 		printf("BST TEST RESULTS:\n%d insertions and %d deletions took %lf seconds.\nTotal of %d cycles, wasted %d\n",insert_counter,erase_counter,change_timer,upper_limit,waste);
+ 		printf("press Return to exit\n");
+ 		//getchar();
+ 	}
+ 
  }

+ void Test::comparation(int base_tree_size, int upperbound ) {

! 	double temp_timer;
! 	
! 	bst=new Bst();
! 	avlt=new Avlt();
! 	
! 	Test_Init(base_tree_size,1); //bst
! 	temp_timer=getInitTimer();
! 	sleep(1);
! 	Test_Init(base_tree_size,0); //avl
! 	printf("\nInit Result:\nBST -> %lf, AVL -> %lf\n",temp_timer,getInitTimer());
! 	if ((temp_timer-getInitTimer())>double(0)) printf("***************************\nAVL faster\n***************************\n");
! 	if ((temp_timer-getInitTimer())<double(0)) printf("***************************\nBST faster\n***************************\n");
! 	if ((temp_timer-getInitTimer())==double(0)) printf("***************************\nNo real differences found\n***************************\n");
! 	Bst_Test(upperbound);
! 	temp_timer=getChangeTimer();
! 	sleep(1);
! 	Avl_Test(upperbound);
! 	if ((temp_timer-getInitTimer())>double(0)) printf("***************************\nAVL faster\n***************************\n");
! 	if ((temp_timer-getInitTimer())<double(0)) printf("***************************\nBST faster\n***************************\n");
! 	if ((temp_timer-getInitTimer())==double(0)) printf("***************************\nNo real differences found\n***************************\n");
! }
! 
! Test::Test(int kind, int upperbound, int base_tree_size) {

  	switch (kind){
  		case 0:
  			avlt=new Avlt();
! 			Test_Init(base_tree_size,0);
  			Avl_Test(upperbound);
  			break;
  		case 1:
  			bst=new Bst();
! 			Test_Init(base_tree_size,1);
  			Bst_Test(upperbound);
  			break;
+ 		case 2:
+ 			comparation(base_tree_size,upperbound);
+ 			break;
  		default:
  			printf("Invalid test selection, application will abort\n");
***************
*** 105,110 ****
  }

! mytime Test::getTimer() {

  }

--- 209,220 ----
  }

! double Test::getInitTimer() {

+ 	return init_timer;
+ }
+ 
+ double Test::getChangeTimer() {
+ 
+ 	return change_timer;
  }

Index: avl.cpp
===================================================================
RCS file: /cvsroot/avl/avl/src/avl.cpp,v
retrieving revision 1.5
retrieving revision 1.6
diff -C2 -d -r1.5 -r1.6
*** avl.cpp	17 Jul 2004 12:34:54 -0000	1.5
--- avl.cpp	17 Jul 2004 17:05:54 -0000	1.6
***************
*** 126,137 ****
  // 0= test avl
  // 1= test bst
! 
!   Test *prova;
!  int upper_bound=100;
! 
! prova = new Test(0,upper_bound);
! 
  //not a good thing...for testing purpose only
! prova->getAvlt()->print1();
  return EXIT_SUCCESS;
  }
--- 126,155 ----
  // 0= test avl
  // 1= test bst
!  Test *prova_avl, *prova_bst;
!  int upper_bound=1000;
!  int base_tree=10000;
!  printf("Welcome to AVL/BST test program\nYou will be asked for values, no controls on your imput, so be careful!\n");
!  printf("What do you want to test? AVL=0 BST=1 Comparation=2\n");
!  int choice;
!  scanf("%d",&choice);
!  printf("Insert the initial number of items\n");
!  scanf("%d",&base_tree);
!  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);
!  }
! //prova->getBst()->print1();
  //not a good thing...for testing purpose only
! //prova->getAvlt()->print1();
  return EXIT_SUCCESS;
  }