// header files
#include "BST_Utility.h"

/* Data Structures
typedef struct stateDataStruct
   {
    char state[ MIN_STR_LEN ];
    double avgTemp;
    double lowestTemp;
    double highestTemp;

    struct stateDataStruct *leftChildPtr;
    struct stateDataStruct *rightChildPtr;
   } StateDataType;
Data Structures */

// function implementations

/*
Name: clearTree
Process: recursively returns dynamically allocated data to the OS
Function input/parameters: working pointer for recursion (StudentDataType *)
Function output/parameters: none
Function output/returned: empty tree (NULL)
Device input/ ---: none
Device output/ ---: none
Dependencies: free, clearTree (recursively)
*/
StateDataType *clearTree( StateDataType *wkgPtr )
{
    // recurse through the left children
    if(wkgPtr->leftChildPtr != NULL)
    {
        clearTree(wkgPtr->leftChildPtr);
    }
    // recurse through the right children
    if(wkgPtr->rightChildPtr != NULL)
    {
        clearTree(wkgPtr->rightChildPtr);
    }
    // otherwise, free the working pointer if at end of getting to bottom tree
    free(wkgPtr);
    // return NULL since no tree left
    return NULL;
}  

/*
Name: privateCompareStrings
Process: compares two strings as follows:
         - if left string is alphabetically greater than the right string, 
         returns value greater than zero
         - if left string is alphabetically less than the right string, 
         returns value less than zero
         - if strings are alphabetically equal but one is longer, 
           longer one is greater
         - otherwise, returns zero
Function input/parameters: two strings to be compared (const char *)
Function output/parameters: none
Function output/returned: result as specified above (int)
Device input/ ---: none
Device output/ ---: none
Dependencies: privateGetStringLen
*/
int privateCompareStrings( const char *leftStr, const char *rightStr )
{
    int diff, index = 0;
    int leftStrLen = privateGetStringLen(leftStr);
    int rightStrLen = privateGetStringLen(rightStr);

    while(index < leftStrLen && index < rightStrLen)
    {
        diff = leftStr[index] - rightStr[index];
        if(diff != 0)
        {
            return diff;
        }
        index = index + 1;
    }
    return leftStrLen - rightStrLen;
}  

/*
Name: privateCopyString
Process: copies one string into another,
         assumes destination string has appropriate capacity
Function input/parameters: source string (const char *)
Function output/parameters: destination string (const char *)
Function output/returned: none
Device input/ ---: none
Device output/ ---: none
Dependencies: none
*/
void privateCopyString( char *dest, const char *source )
{
    int characterCount = 0;
    // use a while loop, check for !NULL_CHAR
    while(source[characterCount] != NULL_CHAR)
    {
        // copy the character accessed into dest string
        dest[characterCount] = source[characterCount];
        // iterate the number of characters
        characterCount = characterCount + 1;
    }
    // add a NULL_CHAR once done, characterCount is in the right place for \0
    dest[characterCount] = NULL_CHAR;
    // no return, void
}  

/*
Name: copyTree
Process: recursively duplicates the provided tree
         using a pre order traversal strategy
Function input/parameters: working pointer for recursion (StateDataType *)
Function output/parameters: none
Function output/returned: pointer to duplicate tree (StateDataType *)
Device input/ ---: none
Device output/ ---: none
Dependencies: initializeStateNodeFromNode, copyTree (recursively)
*/
StateDataType *copyTree( StateDataType *wkgPtr )
{
    // make a storage pointer
    StateDataType *copyPtr = NULL;
    // check for not equal to null
    if(wkgPtr != NULL)
    {
        // create the pointer given data
        copyPtr = initializeStateNodeFromNode(*wkgPtr);
        // recurse left child
        copyPtr->leftChildPtr = copyTree(wkgPtr->leftChildPtr);
        // recurse right child
        copyPtr->rightChildPtr = copyTree(wkgPtr->rightChildPtr);
    }
    // return copyPtr
    return copyPtr;
} 

/*
Name: displayInOrder
Process: recursively displays tree using in order traversal
Function input/parameters: working pointer for recursion (StateDataType *)
Function output/parameters: none
Function output/returned: none
Device input/ ---: none
Device output/ ---: none
Dependencies: stateDataToString, printf
*/
void displayInOrder( StateDataType *sdtPtr, int *itemNum )
{
    // create empty string
    char displayString[STD_STR_LEN];
    if(sdtPtr != NULL)
    {
        // recurse to left node in tree
        displayInOrder(sdtPtr->leftChildPtr, itemNum);
        // increment the item
        *itemNum = *itemNum + 1;
        // setup the string
        stateDataToString(*sdtPtr, displayString);
        // print out the string
        printf("%2d)   %s", *itemNum, displayString);
        // recurse to right node in tree
        displayInOrder(sdtPtr->rightChildPtr, itemNum);
    }
    // no return, void
}  

/*
Name: displayPostOrder
Process: recursively displays tree using post order traversal
Function input/parameters: working pointer for recursion (StateDataType *)
Function output/parameters: none
Function output/returned: none
Device input/ ---: none
Device output/ ---: none
Dependencies: stateDataToString, printf
*/
void displayPostOrder( StateDataType *sdtPtr, int *itemNum )
{
    // create empty string
    char displayString[STD_STR_LEN];
    if(sdtPtr != NULL)
    {
        // recurse to left node in tree
        displayPostOrder(sdtPtr->leftChildPtr, itemNum);
        // recurse to right node in tree
        displayPostOrder(sdtPtr->rightChildPtr, itemNum);
        // increment the item
        *itemNum = *itemNum + 1;
        // setup the string
        stateDataToString(*sdtPtr, displayString);
        // print out the string
        printf("%2d)   %s", *itemNum, displayString);
    }
    // no return, void
}  

/*
Name: displayPreOrder
Process: recursively displays tree using pre order traversal
Function input/parameters: working pointer for recursion (StateDataType *)
Function output/parameters: none
Function output/returned: none
Device input/ ---: none
Device output/ ---: none
Dependencies: stateDataToString, printf
*/
void displayPreOrder( StateDataType *sdtPtr, int *itemNum )
{
    // create empty string
    char displayString[STD_STR_LEN];
    if(sdtPtr != NULL)
    {
        // increment the item
        *itemNum = *itemNum + 1;
        // setup the string
        stateDataToString(*sdtPtr, displayString);
        // print out the string
        printf("%2d)   %s", *itemNum, displayString);
        // recurse to left node in tree
        displayPostOrder(sdtPtr->leftChildPtr, itemNum);
        // recurse to right node in tree
        displayPostOrder(sdtPtr->rightChildPtr, itemNum);
    }
    // no return, void
}  

/*
Name: privateGetStringLen
Process: finds length of string
Function input/parameters: string (const char *)
Function output/parameters: none
Function output/returned: calculated length of string (int)
Device input/ ---: none
Device output/ ---: none
Dependencies: none
*/
int privateGetStringLen( const char *str )
{
    int strLen = 0;
    // while through string until hit null.
    while(str[strLen] != NULL_CHAR)
    {
        // increment the length string iterator
        strLen = strLen + 1;
    }
    // return strLen
    return strLen;
}  

/*
Name: initializeBST
Process: sets BST root pointer to NULL, root pointer is returned by address
Function input/parameters: address of working pointer (StateDataType **)
Function output/parameters: address of updated working pointer 
                            (StateDataType **)
Function output/returned: none
Device input/ ---: none
Device output/ ---: none
Dependencies: none
*/
void initializeBST( StateDataType **bstPtr )
{
    // initialize the address of the BST to null
    *bstPtr = NULL;
    // no return, void
}  

/*
Name: initializeStateNodeFromData
Process: captures data from individual data items, 
         dynamically creates new node,
         copies data, and returns pointer to new node         
Function input/parameters: data to be copied
                           name (const char *)
                           temperatures (double)
Function output/parameters: none
Function output/returned: pointer to new node as specified (StateDataType *)
Device input/ ---: none
Device output/ ---: none
Dependencies: malloc, sizeof, privateCopyString
*/
StateDataType *initializeStateNodeFromData( const char *state, double avgTemp, 
                                              double lowTemp, double highTemp )
{
    // declare node
    StateDataType *initNode;
    // create the node using malloc
    initNode = malloc(sizeof(StateDataType));
    // copy the state into the node
    privateCopyString(initNode->state, state);
    // copy the avgTemp, lowTemp, and highTemp into node
    initNode->avgTemp = avgTemp;
    initNode->lowestTemp = lowTemp;
    initNode->highestTemp = highTemp; 
    // return the node
    return initNode;
}  

/*
Name: initializeStateNodeFromNode
Process: captures data from source node pointer, dynamically creates new node,
         copies data, and returns pointer to new node         
Function input/parameters: node to be copied (StateDataType)
Function output/parameters: none
Function output/returned: pointer to new node as specified (StateDataType *)
Device input/ ---: none
Device output/ ---: none
Dependencies: initializeStateNodeFromData
Notes: one line of code
*/
StateDataType *initializeStateNodeFromNode( const StateDataType source )
{
    // return the initializeStateNodeFromData function with correct data
    return initializeStateNodeFromData(source.state, source.avgTemp, 
                                         source.lowestTemp, source.highestTemp);
}  

/*
Name: insert
Process: recursively searches for available node in BST,
         creates new node and returns it to the calling function,
         if node is already in tree, data is overwritten
Function input/parameters: working pointer for recursion (StateDataType *),
                           node to be inserted (const StateDataType)
Function output/parameters: none
Function output/returned: pointer to new node as specified (StateDataType *)
Device input/ ---: none
Device output/ ---: none
Dependencies: privateCompareStrings, 
              setStateNodeData, initializeStateNodeFromNode
Notes: No redundant code permitted
*/
StateDataType *insert( StateDataType *wkgPtr, const StateDataType inData )
{
    // define space for node
    StateDataType *insertNode;
    int stringComparator;
    // check to see if the working pointer is not null
    if(wkgPtr != NULL)
    {
        // set string comparator
        stringComparator = privateCompareStrings(inData.state, wkgPtr->state);
        // compare the value less than
        if(stringComparator < 0)
        {
            // workingPtr -> nextPtr = insert(workingPtr->nextPtr, data);
            wkgPtr->leftChildPtr = insert(wkgPtr->leftChildPtr, inData);
        }
        // compare the value greater than
        if(stringComparator > 0)
        {
            // workingPtr -> nextPtr = insert(workingPtr->nextPtr, data);
            wkgPtr->rightChildPtr = insert(wkgPtr->rightChildPtr, inData);
        }
        // compare the value equal to
        if(stringComparator == 0)
        {
            // replaces the data (using setStateNodeData?)
            setStateNodeData(wkgPtr, inData);
        }
    }
    // otherwise, create node
    else
    {
        // create the node using function
        insertNode = initializeStateNodeFromNode(inData);
        // return created node
        return insertNode;
    }
    // return working pointer to prev recursion
    return wkgPtr;
}  

/*
Name: isEmpty
Process: tests root node for NULL, returns result
Function input/parameters: pointer to root node (StateDataType *)
Function output/parameters: none
Function output/returned: result of test as specified (bool)
Device input/ ---: none
Device output/ ---: none
Dependencies: none
*/
bool isEmpty( StateDataType *sdtPtr)
{
    // return check for rootNode being NULL
    return sdtPtr == NULL;
}  

/*
Name: removeFromMin
Process: recursively searches for min node,
         when found, node is unlinked from tree, and returned
Function input/parameters: pointers to parent and child nodes (StateDataType *)
Function output/parameters: none
Function output/returned: pointer to removed node (StateDataType *)
Device input/ ---: none
Device output/ ---: none
Dependencies: removeFromMin (recursively)
*/
StateDataType *removeFromMin( StateDataType *parentPtr,
                                                      StateDataType *childPtr )
{
    // check to see if the left child pointer is null
    if(childPtr->leftChildPtr != NULL)
    {
        // keep going left until end
        childPtr->leftChildPtr = removeFromMin(childPtr, childPtr->leftChildPtr);
    }
    else
    {
        // once found, delink between the parent and child
        parentPtr->leftChildPtr = childPtr->rightChildPtr;
    }
    // return removed ptr
    return childPtr;
}  

/*
Name: removeItem
Process: searches for item, if found, creates new node from search pointer,
         then removes item from tree using helper function,
         otherwise returns NULL
Function input/parameters: address of pointer to root node (StateDataType *),
                           node to be removed with at least state name key
                                                           (const StateDataType)
Function output/parameters: address of updated root node pointer 
                            (StateDataType **)
Function output/returned: pointer to removed item node (StateDataType *)
Device input/ ---: none
Device output/ ---: none
Dependencies: search, initializeStateNodeFromNode, removeItemHelper
*/
bool removeItem( StateDataType **rootPtr, 
                      StateDataType *removedData, const StateDataType outData )
{
    StateDataType *searchPtr;
    // check to see if the BST is there
    if(rootPtr != NULL)
    {
        // search for the data in the tree
        searchPtr = search(*rootPtr, outData);
        // check to see if data was found from search to remove
        if(searchPtr != NULL)
        {
            // if found, set the search value to removedData
            *removedData = *searchPtr;
            // start the recursions down to the remove value
            *rootPtr = removeItemHelper(*rootPtr, outData);
            // return success with item removal
            return true;
        }
    }
    // set removeData to NULL since no value found
    removedData = NULL;
    // return false since no item found or tree empty/not found
    return false;
}

/*
Name: removeItemHelper
Process: recursively searches for item, removes node,
         returns dynamic memory of removed node to OS,
         returns updated link to parent (at each recursive level),
         only one return at end of function
Function input/parameters: pointer to working node (StateDataType *),
                           node to be removed with at least state name key
                                                           (const StateDataType)
Function output/parameters: none
Function output/returned: link to recursive parent
Device input/ ---: none
Device output/ ---: none
Dependencies: privateCompareStrings, setStateDataNode, removeFromMin, 
              free, removeItemHelper (recursively)
Notes: No redundant code permitted
*/
StateDataType *removeItemHelper( StateDataType *wkgPtr, 
                                                  const StateDataType outData )
{
    // create, initialize result of compare strings
    int stringComparator;
    stringComparator = privateCompareStrings(outData.state, wkgPtr->state);
    StateDataType *removalPtr;

    // check for moving to left
    if(stringComparator < 0)
    {
        // - recurse to left, link to left child
        wkgPtr->leftChildPtr = removeItemHelper(wkgPtr->leftChildPtr, outData);
    }
    // otherwise, check for moving to right
    else if(stringComparator > 0)
    {
        // - recurse to right, link to right child
        wkgPtr->rightChildPtr = removeItemHelper(wkgPtr->rightChildPtr, outData);
    }
    // otherwise, check for left child null
    else if(wkgPtr->leftChildPtr == NULL)
    {
        // - set a temp pointer to the wkg pointer
        removalPtr = wkgPtr;
        // - set return pointer to its right child
        wkgPtr = wkgPtr->rightChildPtr;
        // - free temp pointer
        free(removalPtr);
    }
    // otherwise, check for right child null
    else if(wkgPtr->rightChildPtr == NULL)
    {
        // - set a temp pointer to the wkg pointer
        removalPtr = wkgPtr;
        // - set return pointer to its left child
        wkgPtr = wkgPtr->rightChildPtr;
        // - free temp pointer
        free(removalPtr);
    }
    // otherwise, check for right child has no left child
    else if(wkgPtr->rightChildPtr->leftChildPtr == NULL)
    {
        // - copy the data from the right child into the current node
        setStateNodeData(wkgPtr, *wkgPtr->rightChildPtr);
        // - set a temp pointer to the right child
        removalPtr = wkgPtr->rightChildPtr;
        // - link around the right child
        wkgPtr->rightChildPtr = removalPtr->rightChildPtr;
        // - free the right child node
        free(removalPtr);
    }
    // otherwise   // , assume right child has left child
    else
    {
        // - call removeFromMin, capture the returned node,
        removalPtr = removeFromMin(wkgPtr, wkgPtr->rightChildPtr);
        // - set the current node from the captured node
        setStateNodeData(wkgPtr, *removalPtr);
        // - free the captured node (temp ptr)
        free(removalPtr);
    }
    // recommend one return at the bottom of function, will give back wkgPtr
    return wkgPtr;
}

/*
Name: search
Process: recursively searches for item, if found, returns pointer to node,
         otherwise, returns NULL
Function input/parameters: pointer to working node (StateDataType *),
                           node to be found with at least state name key
                                                           (const StateDataType)
Function output/parameters: none
Function output/returned: link to found node, or NULL, as specified
Device input/ ---: none
Device output/ ---: none
Dependencies: compareStrings
Notes: No redundant code permitted
*/
StateDataType *search( StateDataType *wkgPtr, const StateDataType searchData )
{
    // define the string comparison number
    int stringComparator = privateCompareStrings(searchData.state, 
                                                                 wkgPtr->state);
    // check to see if at the end of tree
    if(wkgPtr != NULL)
    {
        // check the left side of the tree
        if(stringComparator < 0)
        {
            return search(wkgPtr->leftChildPtr, searchData);
        }
        // check the right side of the tree
        else if(stringComparator > 0)
        {
            return search(wkgPtr->rightChildPtr, searchData);
        }
        // otherwise, data has been found
        else
        {
            // return the found value
            return wkgPtr;
        }
    }
    // otherwise, return null for not found
    return NULL;
}  

/*
Name: setStateNodeToEmpty
Process: sets state node to empty or default values
Function input/parameters: pointer to node (StateDataType *)
Function output/parameters: pointer to updated node (StateDataType *)
Function output/returned: none
Device input/ ---: none
Device output/ ---: none
Dependencies: none
*/
void setStateNodeToEmpty( StateDataType *node )
{
    // set the state to null character
    node->state[0] = '\0';
    // set the average temp to 0
    node->avgTemp = 0;
    // set the lowest temp to 0
    node->lowestTemp = 0;
    // set the highest temp to 0
    node->highestTemp = 0;
    // (not sure if messing with pointers)
    node->leftChildPtr = NULL;
    node->rightChildPtr = NULL;
    // no return, void
}  

/*
Name: setStateNodeData
Process: copies data from source node to destination pointer
Function input/parameters: node to be copied (StateDataType)
Function output/parameters: destination pointer (StateDataType *)
Function output/returned: none
Device input/ ---: none
Device output/ ---: none
Dependencies: copyString
*/
void setStateNodeData( StateDataType *destPtr, const StateDataType source )
{
    // copy the state from source to dest with privateCopyString
    privateCopyString(destPtr->state, source.state);
    // copy the average temp from source to dest
    destPtr->avgTemp = source.avgTemp;
    // copy the lowest temp from source to dest
    destPtr->lowestTemp = source.lowestTemp;
    // copy the highest temp from source to dest
    destPtr->highestTemp = source.highestTemp;
    // (not sure if messing with pointers)
    // destPtr->leftChildPtr = source.leftChildPtr;
    // destPtr->rightChildPtr = source.rightChildPtr;
    // no return, void
}  

/*
Name: stateDataToString
Process: sets data from node to formatted string
Function input/parameters: node with data to be set (StateDataType)
Function output/parameters: string array with result (char [])
Function output/returned: none
Device input/ ---: none
Device output/ ---: none
Dependencies: sprintf
*/
void stateDataToString( StateDataType stateData, char str[] )
{
    // use sprintf to load the state name into str
    // use sprintf to load the average temp into str
    // use sprintf to load the lowest temp into str
    // use sprintf to load the highest temp into str
    // this is done all at once to avoid many lines
    sprintf(str, "%s/%0.2f/%0.2f/%0.2f\n", stateData.state, stateData.avgTemp, 
                                 stateData.lowestTemp, stateData.highestTemp);
    // no return, void
}