#include <stdio.h>
#include <stdlib.h>

#define	randomCapital()	((char)(('A') + rand() % ('Z' - 'A' + 1)))

typedef enum  {FALSE, TRUE} bool;

/* KEY DATA AND ELEMENT */

typedef char keyType;  /* user defined */
typedef int dataType;  /* user defined but not used in this program */
typedef dataType* dataPtr;

typedef struct eltType* eltPtr;
typedef struct eltType {
   keyType   key;
   dataPtr  data;
} eltType;

eltPtr newElt(keyType k, dataPtr pd);
/*
//	construct a new element from k and pd 
//	and return a pointer to this element
*/
eltPtr newElt(keyType k, dataPtr pd) { }

void printKey(eltPtr pe);
void printKey(eltPtr pe) {printf("%c", pe->key);}
void printNull();
void printNull() {printf("%c", '*');}

/* TREENODE AND TREE */

typedef struct treeNode* treePtr;
typedef struct treeNode {
	eltPtr   elt;
	treePtr  lhs;
	treePtr  rhs;
	int     freq; // convenient to control multiple insert
} treeNode;

typedef treePtr tree;

treePtr newNode(eltPtr pe);
/*
//	construct a new node that contains pointer pe to element
//	initialize the other members of the node  
//	and return a pointer to this node
*/
treePtr newNode(eltPtr pe) { }

/* FUNCTION PROTOTYPES, DOCUMENTATION AND DEFINITION */

tree createTree();
/*
//	pre    true
//	action create a new empty tree and return this tree
//	res    a new empty tree exists
*/
tree createTree() {}

bool isEmptyTree(tree t);
/*
//	pre    t exists
//	action determine whether tree t is empty or not
//	res    true is tree t is empty otherwise false
*/
bool isEmptyTree(tree t) {}

int theSizeOf(tree t);
/*
//	pre    t exists
//	action determine the number of nodes in tree t
//	res    the number of nodes
*/
int theSizeOf(tree t) {}

tree destroyTree(tree t);
/*
//	pre    t exists
//	action free all elements and all nodes
//	res    a new empty tree exists
*/
tree destroyTree(tree t) {}

tree insert(eltPtr pe, tree t);
/*
//	pre    t exists and e is well-defined
//	action insert e into t and preseve BST properties
//	res    the new tree is BST and has been returned
*/
tree insert(eltPtr pe, tree t) {}

tree delete(keyType k, tree t);
/*
//	pre    t exists and k is well-defined
//	action remove node with key k from tree t and preserve BST properties
//	       if no node with key k exists then no action
//	res    the new tree is BST and has been returned
*/
tree delete(keyType k, tree t) {}

dataPtr getData(keyType k, tree t);
/*
//	pre    t exists and k is well-defined
//	action find node with key k from tree t and return its dataPtr
//	       if no node with key k exists then NULL is returned
//	res    acccording to action
*/
dataPtr getData(keyType k, tree t) {}

void setData(keyType k, dataPtr pd, tree t);
/*
//	pre    t exists and k is well-defined
//	action find node with key k from tree t and update its data
//	       if no node with key k exists then no action
//	res    according to action
*/
void setData(keyType k, dataPtr pd, tree t) {}

void printTree(tree t);
/*
//	pre    t exists
//	action print keys (and empty subtrees) in in-order
//	res    according to action
*/
void printTree(tree t) {
  if (t) {
    printTree(t->lhs); printKey(t->elt); printTree(t->rhs);
  }
  else
    printNull();
}

void printKeysAndFreqs(tree t, void f(treePtr));
/*
//	pre    t exists
//	action as the name suggests (see output)
//	res    according to action
//	usage  call this higher order function with printKeyAndFreq for f 
*/
void printKeysAndFreqs(tree t, void f(treePtr)) {}
void printKeyAndFreq(treePtr t) ;
void printKeyAndFreq(treePtr t) {
	printf("%2c[%2d]\t", t->elt->key, t->freq);
	if ((t->elt->key - 'A') % 5 == 0) printf("\n");
}

int sumOfFreqs(tree t, int f(treePtr));
/*
//	pre    t exists
//	action determine the sum of all frequencies
//	res    the sum of all frequencies
//	usage  call this higher order function with getFreq for f 
*/
int sumOfFreqs(tree t, int f(treePtr)) {}
int getFreq(treePtr t) ;
int getFreq(treePtr t) {
	return(t->freq);
}

int main(void) {
	int i;
	char c;
	tree t = createTree();

	srand(time(NULL));
	for (i = 0; i < 26*32; i++)
		t = insert(newElt(randomCapital(), NULL), t);

	printf("the size of the tree = %d\n", theSizeOf(t));
	printTree(t); printf("\n");

	printKeysAndFreqs(t, printKeyAndFreq);		
	printf("sum of freqs = %d\n\n", sumOfFreqs(t, getFreq));
 
	printf("delete letters D .. P\n"); 
	for (c = 'D'; c <= 'P'; c++)
		t = delete(c, t);
	printTree(t); printf("\n");

	printf("delete 13 random letters: ");
	for (i = 0; i < 13; i++) {
		c = randomCapital(); 
		printf("%c", c);
		t = delete(c, t);
	}
	printf("\n"); printTree(t); printf("\n");

	printf("release the tree\n"); 
	t = destroyTree(t);
	printTree(t); printf("\n");
	printf("size of tree? %d\n", theSizeOf(t));

	//	etc., etc.

	return(0);
	
}
/*
SAMPLE OUTPUT

	insert random capitals 26*32 = 832 times
	the size of the tree = 26
	the keys are
	*A*B*C*D*E*F*G*H*I*J*K*L*M*N*O*P*Q*R*S*T*U*V*W*X*Y*Z*
	the keys and frequencies are
	 A[32]
	 B[21]   C[30]   D[31]   E[30]   F[32]
	 G[30]   H[36]   I[25]   J[35]   K[34]
	 L[35]   M[30]   N[31]   O[39]   P[37]
	 Q[37]   R[36]   S[34]   T[26]   U[31]
	 V[23]   W[36]   X[31]   Y[28]   Z[42]
	sum of freqs = 832
	
	delete letters D .. P
	*A*B*C*Q*R*S*T*U*V*W*X*Y*Z*
	delete 13 random letters: BOXMNCDYXALQT
	*R*S*U*V*W*Z*
	release the tree
	*
	size of tree? 0

*/