/*
 * trial.c
 *
 * test out btree.h
 */

#include "bst.h"
#include "lists.h"
#include <stdio.h>
#include <stdlib.h>

int pre_count(tree_ptr tree, List** preorder, List** pathlength);
void pre_order (node_ptr tree, List** preorder, List** pathlength, int depth, int* count);

void main (){
   tree_ptr tree;
   List* preorder;
   List* pathlength;
   L_POSITION position;
   int no_nodes, i, j, k, l;

   for (l=0; l <=9; l++) {
      preorder = l_newlist();
      pathlength = l_newlist();
      tree = BST_makenull();
      if (tree == T_END){
	 printf("Unable to create tree!\n");
	 exit (0);
      }
      for (i=0; i<=999; i++) {
	 j = RAND_MAX / 32768;
	 j *= 32768;
	 while ((k = rand()) >= j) continue;
	 BST_insert(tree, k % j);
      }
      
      no_nodes = pre_count(tree, &preorder, &pathlength);
      printf("Number of nodes: %i\n", no_nodes);
      position = l_first(pathlength);
      k = j = 0;
      while (position != L_END) {
	 if (l_retrieve(position) > k)
	    k = l_retrieve(position);
	 j = j + l_retrieve(position);
	 position = l_next(position);
      }
      printf("longest path (h): %i\n",k);
      printf("mean path: %i\n", j / no_nodes);

   /* Clean up memory so we can start again */
   
      T_delete_branch(tree->tree);	        /* delete the entire tree */
      tree->tree = T_END;
      while (l_first(preorder) != L_END)	/* delete the preorder list */
	 l_delete(&preorder, l_first(preorder));
      while (l_first(pathlength) != L_END)	/*delete the pathlength list*/
	 l_delete(&pathlength, l_first(pathlength));
   }
      exit (1);
}

int pre_count(tree_ptr tree, List** preorder, List** pathlength) {

   int depth;
   int count;

   depth = count = 0;
   if (tree->tree != T_END)
      pre_order(tree->tree, preorder, pathlength, depth, &count);
   return (count);
}

void pre_order (node_ptr tree, List** preorder, List** pathlength, int depth, int* count) {

   ++depth;
   ++*count;
   
   l_insert(preorder, L_END, T_retrieve(tree));
   l_insert(pathlength, L_END, depth);
   if (T_next(tree, T_LEFT) != T_END)
      pre_order(T_next(tree, T_LEFT), preorder, pathlength, depth, count);
   if (T_next(tree, T_RIGHT) != T_END)
      pre_order(T_next(tree, T_RIGHT), preorder, pathlength, depth, count);
}