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

/* 
 * Create a single instance of a sparse array tree node with a specific
 * index and value. This Sparse array will be implemented by a binary tree.
 *
 * Arguments:
 * index         the index to be stored in the node
 * value         the value to be stored in the node
 * 
 * returns:
 * SparseNode *  the pointer points to the node just constructed
 *
 * This is a constructor function that allocates
 * memory for a sparse array tree node, and it copies the integer values, and sets the 
 * subtree pointers to NULL. 
 */
SparseNode *SparseNode_create(int index, int value)
{
	if(index < 0 || value == 0) // check that values are reasonable
		return NULL;
	
	SparseNode *temp;
	temp = malloc(sizeof(SparseNode));
	temp->left = NULL; // initialize values
	temp->right = NULL;
	temp->index = index;
	temp->value = value;
	
	return temp;
}

/* Add a particular value into a sparse array tree on a particular index.
 *
 * Arguments:
 * *array        the root node of the sparse array tree
 * index         the index to be stored in the node
 * value         the value to be stored in the node
 * 
 * returns:
 * SparseNode *  the pointer points to the root node of the modified sparse 
 *               array tree
 *
 * The sparse array tree uses the index as a key in a binary search tree.
 * If the index does not exist, create it. 
 * If the index exists, REPLACE the value to the new one. Use the index to
 * determine whether to go left or right in the tree (smaller index
 * values than the current one go left, larger ones go right).
 */

SparseNode * SparseArray_insert ( SparseNode * array, int index, int value )
{
	if(index < 0 || value == 0) // check that values are reasonable
		return array;
	
	if(array == NULL) // create array if it does not exist
		return SparseNode_create(index, value); // return new array
	
	if(index < array->index) // recurse if key is low
		array->left = SparseArray_insert(array->left, index, value);
	else
		if(index > array->index) // recurse if key is high
			array->right = SparseArray_insert(array->right, index, value);
		else // set value if array->index matches key
			array->value = value;
	return array; // return unmodified array head
}

/* Build a sparse array tree from given indices and values with specific length.
 *
 * Arguments:
 * index*         a pointer points to the start position of the index array
 * value*         a pointer points to the start position of the value array
 * length         the size of both array
 * 
 * returns:
 * SparseNode *   the pointer points to the root node of sparse array tree
 *                just constructed
 *
 * It returns a sparse array tree. 
 * You need to insert tree nodes in order
 *
 * (the first sparse array node contains indices[0] and values[0], second node
 * contains indices[1] and values[1]. Basically, each tree node is constructed
 * with each pair in indices and values array. In other words, elements of 
 * indices and values with the same index should go into the same node.)
 */
SparseNode *SparseArray_build(int * indicies, int * values, int length)
{
	SparseNode *temp = NULL;
	int i = 0;
	for(i = 0; i < length; i++) // for loop for inserting array
	{
		temp = SparseArray_insert(temp, indicies[i], values[i]);
	}
	return temp;
}

/* Destroy an entire sparse array tree. 
 *
 * Arguments:
 * *array         the root node of a sparse array tree
 * 
 * returns:
 * void
 *
 * traversing the binary tree in postorder. Use the
 * SparseNode_destroy () function to destroy each node by itself.
 */
void SparseArray_destroy ( SparseNode * array )
{
	if(array != NULL) // recurse down each child
	{
		SparseArray_destroy(array->left);
		SparseArray_destroy(array->right);
		free(array); // remove parent after children are destroyed
	}
}

/* Retrieve the smallest index in the sparse array tree.
 *
 * Arguments:
 * *array         the root node of a sparse array tree
 * 
 * returns:
 * int            the smallest index in the sparse array tree
 *
 * (Hint: consider the property of binary search tree) 
 */
int SparseArray_getMin ( SparseNode * array )
{
	SparseNode *temp = array;
	while(temp->left != NULL) // iterate to lowest index
	{
		temp = temp->left;
	}
	return temp->index; // return lowest index
}

/* Retrieve the largest index in the sparse array tree. 
 *
 * Arguments:
 * *array         the root node of a sparse array tree
 * 
 * returns:
 * int            the largest index in the sparse array tree
 *
 * (Hint: consider the property of binary search tree) 
 */
int SparseArray_getMax ( SparseNode * array )
{
	SparseNode *temp = array;
	while(temp->right != NULL) // iterate to highest index
	{
		temp = temp->right;
	}
	return temp->index; // return highest index
}


/* Retrieve the node associated with a specific index in a sparse
 * array tree.  
 *
 * Arguments:
 * *array         the root node of a sparse array tree
 * index          the index of the node you want to search
 * 
 * returns:
 * SparseNode*    the node with the index that you searched from the tree.
 *                If no node found, NULL should be returned. 
 *                
 * Hint: If the given index is smaller than the current
 * node, search left ; if it is larger, search right.
 */
SparseNode * SparseArray_getNode(SparseNode * array, int index )
{
	SparseNode *temp = array; // do not modify function parameter
	while(temp != NULL) // ensure pointer does not go out of tree
	{
		if(temp->index == index)
		{
	        return temp; // return node if index matches key
		}
	    if(temp->index > index) // move left if greater than key
			temp = temp->left;
		else
	        temp = temp->right; // else move right
	}
	return NULL; // return NULL if index is not found
}

/* Remove a value associated with a particular index from the sparse
 * array. It returns the new
 * sparse array tree ( binary tree root ). 
 *
 * Arguments:
 * *array         the root node of a sparse array tree
 * index          the index of the node you want to remove
 * 
 * returns:
 * SparseNode*    the root node of the sparse array tree that you just modified
 *          
 *    
 * HINT : First, you need to find that node. Then, you will need to isolate
 * several different cases here :
 * - If the array is empty ( NULL ), return NULL
 * - Go left or right if the current node index is different.

 * - If both subtrees are empty, you can just remove the node.

 * - If one subtree is empty, you can just remove the current and
 * replace it with the non - empty child.

 * - If both children exist, you must find the immediate successor of
 * the current node ( leftmost of right branch ), swap its values with
 * the current node ( BOTH index and value ), and then delete the
 * index in the right subtree.
*/
SparseNode * SparseArray_remove ( SparseNode * array, int index )
{
	if (array == NULL)
		return NULL; // return NULL on NULL function pass
	
	if (index < array->index) // recurse through array
	{
		array->left = SparseArray_remove(array->left, index);
		return array;
	}
	if (index > array->index)
	{
		array->right = SparseArray_remove(array->right, index);
		return array;
	}
	
	if (array->left == NULL && array->right == NULL)
	{
		free (array);  // if parent has no children free parent
		return NULL;
	}
	
	if (array->left == NULL) // if parent has one child, free parent
	{
		SparseNode *right1 = array->right;
		free (array);
		return right1;
	}
	if (array->right == NULL)
	{
		SparseNode *left1 = array->left;
		free (array);
		return left1;
	}
	// if parent has two children
	SparseNode *successor = array->right; // create pointer to successor
	while (successor->left != NULL)
	{
		successor = successor->left; // find leftmost child of successor
	}
	int temp_value = array->value; // swap values
	array->index = successor->index;
	array->value = successor->value;
	successor->index = index;
	successor->value = temp_value;
	array->right = SparseArray_remove(array->right, index);
	return array; // return unmodified array

}


/* The function makes a copy of the input sparse array tree
 * and it returns a new copy. 
 *
 * Arguments:
 * *array         the root node of a sparse array tree
 * 
 * returns:
 * SparseNode*    the root node of the new sparse array tree that you just
 *                copied from the input sparse array tree.
 *       
 */
SparseNode * SparseArray_copy(SparseNode * array)
{
	SparseNode *temp = NULL;
	if(array) // recurse through array (deep copy)
	{
		temp = malloc(sizeof(SparseNode));
		temp->index = array->index;
		temp->value = array->value;
		temp->left = SparseArray_copy(array->left);
		temp->right = SparseArray_copy(array->right);
	}
	return temp; // return new array
}

/* Merge array_1 and array_2, and return the result array. 
 * This function WILL NOT CHANGE the contents in array_1 and array_2.
 *
 * Arguments:
 * *array_1         the root node of the first sparse array tree
 * *array_2         the root node of the second sparse array tree
 * 
 * returns:
 * SparseNode*    the root node of the new sparse array tree that you just
 *                merged from the two input sparse array tree
 *     
 * When merging two sparse array tree:
 * 1. The contents in array_1 and array_2 should not be changed. You should make
 *    a copy of array_1, and do merging in this copy.
 * 2. array_2 will be merged to array_1. This means you need to read nodes in 
 *    array_2 and insert them into array_1.
 * 3. You need to use POST-ORDER to traverse the array_2 tree. 
 * 4. Values of two nodes need to be added only when the indices are the same.
 * 5. A node with value of 0 should be removed.
 * 6. if array_2 has nodes with index different than any nodes in array_1, you
 *    should insert those nodes into array_1.
 * 
 * Hint: you may write new functions
 */
// helper function to remove node if its value is zero upon merger
// (copy of SparseArray_insert with modifications if index == array->index)
SparseNode * mergeHelp ( SparseNode * array, int index, int value )
{
	if(index < 0 || value == 0)
		return array;
	
	if(array == NULL)
		return SparseNode_create(index, value);
	
	if(index < array->index)
		array->left = mergeHelp(array->left, index, value);
	else
		if(index > array->index)
			array->right = mergeHelp(array->right, index, value);
		else
		{ // if index == array->index
			array->value = array->value + value; // update value
			if(array->value == 0) // remove node if value == 0
				array = SparseArray_remove(array, index);
		}
	return array;
}

SparseNode * SparseArray_merge(SparseNode * array_1, SparseNode * array_2)
{
	if(array_1 == NULL && array_2 == NULL) // exit if nothing to do
		return NULL;
	if(array_1 == NULL) // nothing to merge, non-NULL array
		return SparseArray_copy(array_2);
	if(array_2 == NULL)
		return SparseArray_copy(array_1);
	
	SparseNode *temp;
	temp = SparseArray_copy(array_1);
	
	SparseNode *temp1 = NULL; // pointer to array_2 node at index i
		
	int i = SparseArray_getMin(array_2); // cycle through array_2
	for(i = SparseArray_getMin(array_2); i <= SparseArray_getMax(array_2); i++)
	{
		temp1 = SparseArray_getNode(array_2, i);
		if(temp1 != NULL)
		{ // merge
			temp = mergeHelp(temp, temp1->index, temp1->value);
		}
	}
	return temp; // return merged array
}