node_ptr find_char(node_ptr &p, char x) 
	{
	
    	if (p != NULL) 
		{ 
		if (p->key == x)
			{
			cout << p->key << endl;  // here, it prints the key that is the same a sx
			cout << p->val << endl;
			return p;
			}
		else
        		{
			find_char(p->left, x);  // take left subtree            		
			find_char(p->right, x); // take right subtree
			}

// allow easy indexing (with no searching) to any node  
NODEP *allNodes = new NODEP[UCHAR_MAX + 1];  
for (int i = 0; i < (UCHAR_MAX + 1); ++i)
  allNodes[i] = NULL;

for (NodeDequeItr itr = _deque.begin(); itr != _deque.end(); ++itr) {
  if ((*itr)->isLeaf())
    allNodes[(*itr)->cc.ch] = *itr;
}

/************************************* 
 * Filename: CSC310-Assignment5.cpp
 * Description: Prompts the user for an input file, which is
 * assumed to contain one character (including ' '), followed
 * by a blank space, followed by a frequency number, on each
 * line. A Huffman tree is then built from these values. Finally
 * the user is prompted for an output file, which the program
 * writes each char followed by a blank, followed by it's
 * appropriate Huffman code, in asscending alphabetical order.
 *************************************************************/
#include<iostream>
#include<fstream>
#include<cstring>
using namespace std;

struct node
        {
        char key; int val;
        node *left, *right, *next, *prev;
        };

typedef node* node_ptr;

void add_tree(node_ptr &head, node_ptr &list);
/**************************************************
 *	Description: Creates a parent node from two smallest adjacent nodes on
 * the list.
 *************************************************/

void add_list(node_ptr &head, node_ptr &list, int value, int character);
/**************************************************
 *	Description: Adds nodes to a list with a character and number
 * attached to each node.
 *************************************************/

void sort_list(node_ptr &head, node_ptr &list);
/**************************************************
 *	Description: Sorts the nodes on the list directly via insertion
 * sort. Ensures children links are maintained.
 *************************************************/

void find_code(node_ptr &root, node_ptr &list, char matrix[][32]);
/**************************************************
 *	Description: Finds the Huffman code for each char that was read
 * in and attached to the tree. Reads each char and it's adjacent
 * code into matrix[][32]
 *************************************************/

void sort_array(char a[], int size);
/**************************************************
 *	Description: Simply uses an insertion sort to sort a  given
 * array. In this case, the char array for refrencing when
 * printing to file in alphabetical order.
 *************************************************/
 
void print_matrix(char matrix[][32], int count, char a[]);
/**************************************************
 *	Description: Prints each char, followed by a space, followed
 * by it's appropriate Huffman code, to a user designated output
 * file in ascending alphabetical order.
 *************************************************/

int main(void)
	{
   node_ptr root=NULL, list=NULL;  // initialize root and list pointer
	int v = 0,size = 0;             // v = frequency #, size = number of characters in file
	char ifilename[15];
	char matrix[128][32];			  // holds the chars with corresponding code for sorthing
	char a[128];					  // index of chars stored for refrencing

	ifstream read;

	/************ Prompt for input file & open stream **************************/
	cout <<"Enter a file name to read from: ";
	cin>> ifilename;
	read.open(ifilename);

	if (read.fail())
		{
		cout << "File not found, exiting..." << endl;
		exit(1);
		}
	/** End file input stream opening **/

	/************* read from file ********************************************/
	while(read.get(a[size]))                  // read char into array
		{
		sort_array(a, size);	          // keep array sorted.
		read.get();                       // get the next char, which should be ' '
		read >> v;                        // read the frequency number
		add_list(root, list, v, a[size]); // add the node to the list
		size++;   		                   // increment size
		read.ignore(1,'\n');
		}
	read.close();                       // read from stream finished, close stream
	/*************** End read from file ***************************************/

	/*************** Build Huffman tree from list *****************************/
	while(list->next != NULL)
		{
		sort_list(root, list);       // ensure 1st 2 nodes are the smallest on list...
		add_tree(root,list);         // ..if two are equal, node with a char is 1st
		if(root->next == NULL)break; // breakes when the root is the only node left
		}
	/*************** Huffman tree building is complete *************************/

   /**************  Here, find each char in the tree and encode ***************/
	find_code(root, list, matrix);
   /***************** End encoding ********************************************/

	/**************** Print to file ********************************************/
	print_matrix(matrix, size, a);
   /**************** End of print to file *************************************/

   return 0;
   }

void add_tree(node_ptr &head, node_ptr &list)
	{
	list = head;                 // set node to root

	node_ptr tmp = new node;     // create node to be used as parent node
	tmp->key = 0;                /* to avoid confusion, parent nodes will have an
   									     escape sequence char (shouldnt be in a file) */
	tmp->val = list->val + list->next->val;  // set node's value to the sum of children
	tmp->left = list;            // connect smallest node to the left
	tmp->right = list->next;     /* connect the next node, which should be more or equal
                                   to the right. */
	tmp->right->prev = tmp;      // point prev links of children nodes to parent
	tmp->left->prev = tmp;

	if(list->next->next != NULL)
		{
      /****** Disconnect children from list ***/
		list = list->next->next;
		list->prev->prev->prev = tmp;
		list->prev->prev->next = NULL;
		list->prev->prev = tmp;
		list->prev->next = NULL;
		list->prev = NULL;
		head = list;

      /**** cycle through list and connect parent to the end ***/
		while(list->next != NULL)list = list->next;
		list->next = tmp; tmp->prev = list; tmp->next = NULL;
		}
	else
		{                            // case if parent is last node on list
		list->next->prev = NULL;
		list->next = NULL;
		head = tmp;
		}
	list = head;
	}

void add_list(node_ptr &head, node_ptr &list, int value, int character)
	{
	if (!list)         			// if list is empty
		{                       // set val and key, and set as head
		list = new node;
		list->key = character;
		list->val = value;
		head = list;
		list->next = NULL;
		list->prev = NULL;
		}
	else
		{
		while (list->next != NULL) list = list->next;  //cycle to end of list
		node_ptr tmp = new node;                  // create new node
		tmp->key = character;                     // set key and val
		tmp->val = value;
		list->next = tmp;                         // conenct previous node to new node
		tmp->next = NULL;                         // next node == NULL
		tmp->prev = list;                         // set prev link to previous node
		}
}

void sort_list(node_ptr &head, node_ptr &list)
	{
	node_ptr temp;                             //pointer for sorting
	node_ptr tmp = head;                       // set temp to head
   /*********************************************************
    * Begining with the 2nd node, cycle through the list until
    * a node is encounered that is greater than the previous node.
    * Then continue cycling back through the list changing links
    * until the node is in it's correct place.
    ***********************************************************/
	for (tmp = tmp->next; tmp; tmp = tmp->next)
		{
		list = tmp;
		while(list->prev->val > list->val)
			{
			temp = list->prev;
			temp->next = list->next;
			if(temp->prev != NULL)       //if temp is not at the beginning of the list
				{
				temp->prev->next = list;  // set the previous link to list
				list->prev = temp->prev;  // set list's prev link to the node before temp
				}
			else
				{
            list->prev = NULL;        // set list->prev to NULL
				head = list;              // point beginning of list to node
            }
				if(list->next != NULL) list->next->prev = temp; //sets next node prev to temp

            temp->prev = list;        // temp's previous link is pointing to list
				list->next = temp;        // list's next link is pointing to temp

				if(!list->prev)break;     // break if at beginning of list
			}
		}
	}

void find_code(node_ptr &root, node_ptr &list, char matrix[][32])
	{
	char code[30];        //code for character to be encoded (30 bit implementation)
	int count = 0;		    //counts # of lines needed in output file

	for (int i = 0; list; i++)
		{
		if(list->left != NULL)
			{
			code[i] = '0';       // insert 0 in code when left branch is taken
			list = list->left;   // take left branch
			}
		else if(list->right != NULL) // should only evaluate to true if right is taken
			{
			code[i] = '1';       // insert 1 if right branch is taken
			list = list->right;  // take right branch
			}
		else                    // leaf is reached
			{
			if(list->key != 0)   // only consider nodes containg chars other than 0
				{
				matrix[count][0] = list->key;    // sets 1st element to char
				matrix[count][1] = ' ';          // sets 2nd element to blank space
				for (int j = 2; j < i + 2; j++)
					{
					matrix[count][j] = code[j-2]; // adds huffman code to adjacent char
					matrix[count][j+1] = '\0';    // ensures '/0' is in the correct position
					}
				count++;
				}
			if(code[i-1] == '0')     // delete leftmost node if it was read
				{
				list->prev->left = NULL;
				delete list;

				}
			else if (list->prev == NULL)  // breaks if last node is root
				break;
			else                          // delete right node if it was read
				{
				list->prev->right = NULL;
				delete list;
				}
			i = -1;  							//sets i to 0 on next run
			list = root;                  // set list pointer to top of tree
			}
		}

	}

void sort_array(char a[], int size)
	{
   /** Simple insertion sort to sort array of characters for file output ***/
	int temp = 0, j = 0;
	for (int i = 0; i < size; i++)
		{
		temp = a[i]; j = i;
		while( a[j-1] > temp)
			{
			a[j] = a[j - 1];
			j--;
			}
		a[j] = temp;
		}
	}

void print_matrix(char matrix[][32], int count, char a[])
	{
	ofstream write;
	char ofilename[15];		// output file name

   /**** Prompt user for output file ***/
   cout << "Enter an output file to write to: ";
	cin >> ofilename;
   /***** End Output file prompt ******/

   /*** Open Output File ****/
	write.open(ofilename);
	if(write.fail())
		{
		cout << "Error encountered!" << endl;
		exit(1);
		}
   /*** End File Opening ****/

	for (int i = 0; i < count; i++)
		{
		for (int j = count-1; j > -1; j--)
			{
			if (a[i] == matrix[j][0])      // cycle through matrix until equal to
				{                           // a[i]. Array a[i] is sorted.
				for (int k = 0; matrix[j][k] != '\0'; k++)
					write << matrix[j][k]; // output <char> <blankspace> <huffman code>
				}
			}
		write << endl;                  // write new line
		}
	write.close();                     // close output

	}