/* Main Program */


#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include "bst.h"
#include "newrand.h"

void main ()
{
 
  int N,M, Range, ave; /* N is the number of values to be inserted into */
          /* BST, range the range of these values, M is the number of   */
          /* deletions done. ave records the average height of the BST  */
  FILE *insert_out, *del_out;  /* file pointers for output files */ 

  char insert_file_name[] = "out1";
  char delete_file_name[] = "out2";
  
  
  int i,j,RandomNum, max=0, steps;
  int sum=0,big=-1,small=-1;

  int count_iterations;

  /* get an initialized BST */
  BST T=STinit();
  

  /* read the number of values to be inserted */
  printf ("N? ");
  scanf ("%d",&N);

  /* read the range these values should have */
  printf ("Range? ");
  scanf ("%d",&Range);

  /* seed the random number generator */
  newrand(-((int) time(NULL)));

  /* open file for output */
  if ((insert_out = fopen(insert_file_name,"w")) == 0)
  {
    fprintf(stderr, "Can't open  %s\n",insert_file_name);
    exit(-1);
  }

  for(i=0; i < N; i++)
  {
    /* rand generates an integer random number 0..Range-1 */
    RandomNum = (int) (newrand (1)*Range);

    /* insert the number into the BST and get the number of steps */
    /* taken for the insertion                                    */
    steps=STinsert(T,RandomNum);
    sum += steps;
 
    /* write this into file */
    fprintf(insert_out," %d ",steps);

    /* max contains the maximum height of the BST, or equivalently */
    /* the maximum number of steps for insertion so far             */
    if (steps>max) max=steps;

  }
 
  ave=sum/N;
  printf("The max depth  is %d and the average %d.\n",max,ave);

  /* close file */
  fclose(insert_out);

 /* now open file for the output for deletes */

  if ((del_out = fopen(delete_file_name,"w")) == 0)
  {
    fprintf(stderr, "Can't open  %s\n",delete_file_name);
    exit(-1);
  }

 /*now start deleting*/
 /* read the number of deletions to be done */
  printf("M for deletions? ");
     scanf("%d",&M);
  /* set max to 0 */
  max = 0;
 
  count_iterations = 0; /* after every 1000iterations print max */

  for (j=0;j<M;j++)
  {
     /* Make one deletion in each iteration */
      count_iterations++;

     /* chose a random number to be deleted */
     /* actually, we'll be deleting the number */
     /* nearest to it in the BST */
	RandomNum = (int) (newrand (1)* Range);

     /* small and big to some default values */
	small=-1;
	big=-1;
     /* get the two nearest numbers in BST to RandomNum */
	STwhatToDel(T,&small,&big,RandomNum);


     /* decide to take the one which is nearer */
	if (small==-1) RandomNum=big;
	else if (big==-1) RandomNum=small;
	else if (big-RandomNum>RandomNum-small) RandomNum=small;
	else RandomNum=big;

     /* delete the element */
	STdelete(T,RandomNum);


     /* Insert a random element in the BST */
	RandomNum = (int) (newrand(1)*Range);
        steps=STinsert(T,RandomNum);

	if (steps>max) max=steps;
 
       
     /* output steps and max */

        fprintf(del_out,"%d ",steps);
        fprintf(del_out,"%d ",max);
     
     /* if 1000 iterations have passed print max */
        if (count_iterations == 1000)
          {
              printf("DELETED %d elements so far ...\n",j+1);
              printf("       the maximum depth so far is %d\n",max);
              count_iterations = 0;
           }
         
        
   }
  /* close file */
  fclose(del_out);
}