Patricia Trees

Your executable MUST be named "pat". You MUST accept 2 command line arguments. The first being the input file name and the second being the output file name. Your program MUST write to the output file regardless of what it is named.(You cannot accept the output file argument then ignore it and hardcode an output file named inputfile.out or inputfile.myout.)

I will be providing more info as the project develops.

Due Date: All Program Components: Monday, April 21th(???) 11:59pm

Your are to implement the operations of a Patricia Tree, as discussed in class and posted in the course notes on the web using appropriate C++ classes. 

You are to structure your main program to accept and interpret file input with the following format:

You are to have an initially empty tree, i.e. root is NULL. Listed below are all of the commands you will be responsible for:

I [integer]     //To "insert" the integer into the Patricia tree.

D [integer]     //To "delete" the integer from the Patricia tree.

S [integer]     //To "search" for the integer key in the Patricia tree.

P     //To print out a "modified" Inorder Traversal of the Patricia Tree.(see below).

I will provide test files that show EXACTLY how the output should look. You are required to match this output EXACTLY

Output: Send your output for this program to a file.  For inserts, it is an error to insert a duplicate value in the Patricia Tree structure, be sure to notify the user of such an attempt.  Tell the user if an operation is successful, as well.  Be sure to give appropriate "error" messages back to the user of your program, via the output file.  For e.g., if asked to delete a value from the Patricia Tree structure that is not found in the structure, you should reply that the value was not found and so could not be deleted.  For the Search operation, if the item being sought is found, print out a message that says you found it and what its value is.  On the other hand, if the item is not found, print out a message to that effect.

Also Note: You are responsible to write a program that deals with *all cases*.  That is, your program should not only *work good on some input files*, it need to work on *all possible* input files.  This means it is not your TAs responsibility to give you an input file that allows your program to work.  It is your responsibility to write code that cannot be broken by any input file and so will work in all cases.  This will be the case for every program you write for this course.

Deletes:  Be sure, for a nodes that have 2 "real" children, to use the Search Predecessor, as discussed in class, and copy over the value of the Search Predecessor in the node to be deleted and then physically delete the Search Predecessor.  

Printing: The standard Inorder Traversal for binary trees needs to be modified, since Patricia Trees have no NULL pointers within them.  Therefore, your stopping state in a traversal will be the same as it is for searching.  That is, when the bit test in the new node being pointed to is the same number or higher than the previous node that pointed to it, then print the value in this "higher or same" bit test node, but there will be no further recursive calls.  This does mean that all of the values in the tree will be printed twice.  That is OK, since you want to be able to make sure that every node is pointed to by an "up" pointer, as well as a "down" pointer.  Where "up" and "down" are referring to the number representing the bit test in a node.   Do not print the dummy header, and print not only the integer value stored in each node, but also the bit test in that node.  (For debugging purposes, you might want to intermediately print out the bit string that represents the integer and also the dummy.)

Input: The input file will consist of integers up to 4 digits long.  You will need to convert these integers into their binary representations.  The highest bit test will be for the highest power of 2 that goes into the integer 9999.  

For the Print and Search algorithms we are assuming we have a node class that has a function called getCheck() that returns the node checkbit. There is also a function called isDummy() that returns true if the current node is the dummy node.
Print Algorithm:

void print(ofstream ofile, Node* subroot, int lastCheck)
{
//this is a modified inorder print we print each node twice, once as an internal
//node and once as a recursion ending "leaf node" remember there are no null pointers
	if(subroot-isDummy()) return;
	if(subroot-getCheck() is greater than or equal to lastCheck)
	{
	 //this is a "leaf node" the same or higher in the tree we want to print this 
	 print to ofile:(subroot-value " as leaf node, checkbit= " subroot-getCheck)   
	}
	else
	{
	 //go left/zero direction pass current checkbit along
	 print(ofile,subroot-zero, subroot-getCheck)
	 //this is an "internal node" we print all of these
	 print to ofile:(subroot-value " as internal node, checkbit= " subroot-getCheck)   
	 //go right/one direction pass current checkbit along
	 print(ofile,subroot-one, subroot-getCheck)
	}
}

bool search(int val,,int* array, Node* subroot, int lastCheck)
{
 //search works like a normal search with the obvious exception of the patricia
 //tree stopping states
 	//zero cant be in tree
 	if(subroot-isDummy()) return false
	else if(subroot-getCheck is greater than or equal to lastCheck)
	{
	  //we are at a "leaf node" compare the 2 keys
	  if(subroot-getValue == val) return true
	  else return false
	}
	else
	{
	  //recurse zero
	  if(array[subroot-getCheck] == 0)
	  	search(val,array,subroot-zero,subroot-getCheck)
	  //recurse one
	  else
	  	search(val,array,subroot-one,subroot-getCheck)
	}
}

int* int2binary(int val)
{
	//declare a dynamic int array the size of bit string(for us 14)
	int* int2bin = new int[MAX_SIZE]
	int dividend = val
	//loop through array MAX_SIZE times and divide by 2
	for(int i=0; i less than MAX_SIZE-1; i++)
	{
		if(dividend mod 2 == 0)
			int2bin[i] = 0
		else
			int2bin[i] = 1
		dividend /= 2
	}
	return int2bin
}