// header file
#include "HeapUtility.h"

// constants

/* Data Structures

typedef struct HeapStruct
   {
    StudentType *array;

    int size, capacity;
   } HeapType;

Data Structures */

// function implementations

/*
Name: addStudentWithData
Process: adds student data to the array with internally generated priority,
         returns true if array not full, false otherwise
Method input/parameters: pointer to HeapType item (HeapType *),
                          name (const char *), student id (int),
                          gender (char), gpa (double), priority (int),
                          display flag (bool)
Method output/parameters: pointer to HeapType item (HeapType *)
Method output/returned: Boolean result of function (bool)
Device input/---: none
Device output/---: none
Dependencies: privateCopyString, privateGenUniqueRandom,
              studentDataToString, privateBubbleUp
*/
bool addStudentWithData(HeapType *heap, const char *inName, int inStudentId,
                        char inGender, double inGpa, bool displayFlag)
{
    // create variables for string display
    char dispString[MAX_STR_LEN];
    // check to see if the size is equal to capacity
    if(heap->size == heap->capacity)
    {
        // if the capacity and the size are equal
        return false;
    }
    // copy the data out of the input variables
    privateCopyString(heap->array[heap->size].name, inName);
    heap->array[heap->size].studentId = inStudentId;
    heap->array[heap->size].gender = inGender;
    heap->array[heap->size].gpa = inGpa;
    heap->array[heap->size].priority = 
                       privateGenUniqueRandom(heap->capacity, GET_RANDOM_VALUE);
    // display if enabled
    if(displayFlag)
    {
        // "cast" our data to a string
        studentDataToString(dispString, heap->array[heap->size]);
        // print out the string
        printf("\nAdding new student: %s\n", dispString);
    }
    // call bubble up to get to the right place
    privateBubbleUp(heap, heap->size, displayFlag);
    // increment the size of the heap
    heap->size = heap->size + 1;
    // return true since operation complete
    return true;
}

/*
Name: addStudentFromStudentElement
Process: adds student element to the array from other element,
         returns true if array not full, false otherwise
Method input/parameters: student data type item to be added (const StudentType)
Method output/parameters: pointer to HeapType (HeapType *)
Method output/returned: Boolean result of function
Device input/---: none
Device output/---: none
Dependencies: one line of code - addStudentWithData
*/
bool addStudentFromElement(HeapType *heap,
                           const StudentType sourceElement, bool displayFlag)
{
    // return the added student with data
    return addStudentWithData(heap, sourceElement.name, sourceElement.studentId,
                          sourceElement.gender, sourceElement.gpa, displayFlag);
}

/*
Name: clearHeapType
Process: deallocates heap and internal array, clears unique random source,
         returns NULL
Method input/parameters: pointer to HeapType (HeapType *)
Method output/parameters: none
Method output/returned: NULL (HeapType *)
Device input/---: none
Device output/---: none
Dependencies: free, privateGenUniqueRandom
*/
HeapType *clearHeapType(HeapType *heap)
{
    // free the heap's array
    free(heap->array);
    // free the random number generator
    privateGenUniqueRandom(heap->capacity, CLEAR_RAND_GENERATOR);
    // free the rest of the heap
    free(heap);
    // return NULL since cleared
    return NULL;
}

/*
Name: createHeapType
Process: initializes heap, and internal array, creates unique random source
Method input/parameters: capacity (int)
Method output/parameters: none
Method output/returned: initialized heap (HeapType *)
Device input/---: none
Device output/---: none
Dependencies: malloc, privateGenUniqueRandom
*/
HeapType *createHeapType(int capacity)
{
    // dynamically allocate the heap
    HeapType *createdHeap = (HeapType *) malloc(sizeof(HeapType));
    // set the heap's capacity to the given capacity
    createdHeap->capacity = capacity;
    // set the heap's size to zero to start
    createdHeap->size = 0;
    // allocate the internal array for the heap
    createdHeap->array = (StudentType *) malloc(sizeof(StudentType) * capacity);
    // initialize the random number generator
    privateGenUniqueRandom(capacity, INITIALIZE_RAND_GENERATOR);
    // return created heap
    return createdHeap;
}

/*
Name: getTreeHeight
Process: recursively finds tree height by using number of nodes
Method input/parameters: node count (int)
Method output/parameters: none
Method output/returned: calculated tree height (int)
Device input/---: none
Device output/---: none
Dependencies: findTreeHeight (recursively)
*/
int findTreeHeight(int nodeCount)
{
    // define height
    int treeHeight = 0;
    // check to see if the count of nodes is more than zero
    if(nodeCount > 1)
    {
        // count the tree height recursively.
        treeHeight = 1 + findTreeHeight((nodeCount - 1)/2);
    }
    // return treeHeight
    return treeHeight;
}

/*
Name: isEmpty
Process: checks for empty list, reports
Method input/parameters: none
Method output/parameters: none
Method output/returned: Boolean result of operation (bool)
Device input/---: none
Device output/---: none
Dependencies: none
*/
bool isEmpty(HeapType *heap)
{
    // return false (temp)
    return heap->size == 0;
}

/*
Name: privateBubbleUp
Process: recursively traverses tree to place new data element
       in the correct location in the tree/array,
       if display flag set, reports bubble up actions
Method input/parameters: pointer to heap (HeapType *),
                         index at current location in tree/array (int),
                         display flag (bool)
Method output/parameters: pointer to updated heap (HeapType *)
Method output/returned: none
Device input/---: none
Device output/---: none
Dependencies: deepCopyStudentData, printf, studentDataToString,
              privateBubbleUp (recursive)
Notes: No more than two statements for any swap operation
*/
void privateBubbleUp(HeapType *heap, int currentIndex, bool displayFlag)
{
    // initialize variables
    int parentIndex = (currentIndex - 1) / 2;
    char bubbleStr[MAX_STR_LEN];
    StudentType swapParent;
    // prepare the swap
    deepCopyStudentData(&swapParent, heap->array[currentIndex]);
    // check for parent and valid index
    if(parentIndex >= 0) //used to be currentIndex > 0
    {
        // compare parent and child priorities
        if(heap->array[parentIndex].priority < 
                                             heap->array[currentIndex].priority)
        {
            // if priorities are BLANK than, swap.
            deepCopyStudentData(&heap->array[currentIndex], 
                                                      heap->array[parentIndex]);
            deepCopyStudentData(&heap->array[parentIndex], swapParent);
            // check for display information
            if(displayFlag)
            {
                // "cast" data to string
                studentDataToString(bubbleStr, heap->array[parentIndex]);
                // print the bubbling
                printf("   - Bubble up swap:\n");
                // print the swapping parts
                printf("     - moving up child: %s", bubbleStr);
                studentDataToString(bubbleStr, heap->array[currentIndex]);
                printf("     - moving down parent: %s\n", bubbleStr);
            }
            // bubbleUp again since swapped
            privateBubbleUp(heap, parentIndex, displayFlag);
        }
    }
    // no return, void.
}

/*
Name: privateTrickleDown
Process: recursively traverses tree to place reordered data element
       in the correct location in the tree/array,
       if display flag set, reports trickle down actions
Method input/parameters: pointer to heap (HeapType *),
                         index at current location in tree/array (int),
                         display flag (bool)
Method output/parameters: pointer to updated heap (HeapType *)
Method output/returned: none
Device input/---: none
Device output/---: none
Dependencies: deepCopyStudentData, printf, studentDataToString,
              privateTrickleDown (recursive)
Notes: No more than two copy operations for any swap operation
*/
void privateTrickleDown(HeapType *heap, int currentIndex, bool displayFlag)
{
    // initialize variables
    bool leftChildSwap = false, rightChildSwap = false;
    int leftChildIndex = currentIndex * 2 + 1;
    int rightChildIndex = currentIndex * 2 + 2;
    int swapStudentIndex;
    StudentType swapStudent;
    char trickleStr[MAX_STR_LEN];
    // check left child and data(priority)
    if(heap->size <= leftChildIndex)
    {
        // check left child exists (given index within size)
        // compare currentIndex priority < leftChildPriority
        if(heap->array[leftChildIndex].priority > 
                                             heap->array[currentIndex].priority)
        {
            // left child > currentIndex, leftChildSwap = true
            leftChildSwap = true;
        }
    }
    // otherwise, check right child and data(priority)
    else
    {
        // check right child exists (given index within size)
        // compare currentIndex priority < rightChildPriority
        if (heap->array[rightChildIndex].priority > 
                                             heap->array[currentIndex].priority)
        {
            // right child > currentIndex, rightChildSwap = true
            rightChildSwap = true;
        }
    }
    // decide to swap with left or right child based on which is max priority
    // if both can be swapped, take the greater priority one.
    if(leftChildSwap && rightChildSwap)
    {
        // set the swapStudent to the greater priority (deepCopy)
        // set the swapStudentIndex to whichever side was picked
        if(heap->array[leftChildIndex].priority > 
                                          heap->array[rightChildIndex].priority)
        {
            rightChildSwap = false;
        }
        else
        {
            leftChildSwap = false;
        }
    }
    // check to see if the leftChildSwap is true
    else if(leftChildSwap)
    {
        // set the swapStudent to the leftChild
        deepCopyStudentData(&swapStudent, heap->array[leftChildIndex]);
        // set the swapStudentIndex to the left
        swapStudentIndex = leftChildIndex;
    }
    // otherwise, check to see if the rightChildSwap is true
    else if(rightChildSwap)
    {
        // set the swapStudent to the rightChild
        deepCopyStudentData(&swapStudent, heap->array[rightChildIndex]);
        // set the swapStudentIndex to the right
        swapStudentIndex = rightChildIndex;
    }
    // swapping operation block and check
    if(leftChildSwap || rightChildSwap)
    {
        // check if displayFlag is true
        if (displayFlag)
        {
            // print out the relevant information
            printf("   - Trickle down swap:\n");
            studentDataToString(trickleStr, heap->array[currentIndex]);
            printf("     - moving down parent:%s", trickleStr);
            // get the swapping side index information
            studentDataToString(trickleStr, heap->array[swapStudentIndex]);
            // check which side is being swapped to display accurate info
            if(leftChildSwap)
            {
                printf("     - moving up left child:%s\n", trickleStr);
            }
            else
            {
                printf("     - moving up right child:%s\n", trickleStr);
            }
        }
        // swapping operation given that there needs to be a swap
        // heap->array[swapStudentIndex] = heap->array[currentIndex]
        deepCopyStudentData(&heap->array[swapStudentIndex], 
                                                     heap->array[currentIndex]);
        // heap->array[currentIndex] = swapStudent
        deepCopyStudentData(&heap->array[currentIndex], swapStudent);
        // trickleDown to next recursion since swapped
        privateTrickleDown(heap, swapStudentIndex, displayFlag);
    }
    // no return, void.
}

/*
Name: removeItem
Process: removes item from heap, adjusts tree, returns
Method input/parameters: pointer to heap type (HeapType *)
Method output/parameters: returned data, or empty returnVal if not found
                                                            (StudentDataType *),
                          pointer to updated heap type (HeapType *)
Method output/returned: none
Device input/---: none
Device output/---: none
Dependencies: deepCopyStudentData, studentDataToString,
              printf, privateTrickleDown
*/
void removeItem(StudentType *returnVal, HeapType *heap, bool displayFlag)
{
    // define a removedItemStr
    char removedItemStr[MAX_STR_LEN];
    // removes item @ index zero
    // (item @ last index of array @ index zero)
    // check to make sure within valid space
    if(heap->size > 0)
    {
        // set the returnVal to the heap's index zero by deep copy
        deepCopyStudentData(returnVal, heap->array[0]);
        // set last to first
        deepCopyStudentData(&heap->array[0], heap->array[heap->size - 1]);
        // decrement size by 1 for array
        heap->size = heap->size - 1;
        // check the displayFlag
        if (displayFlag)
        {
            studentDataToString(removedItemStr, *returnVal);
            // if true, print the removed item
            // print the string for the removed item
            printf("\nRemoving student: %s\n", removedItemStr);
        }
        // call privateTrickleDown to move into correct place
        privateTrickleDown(heap, 0, displayFlag);
        if (displayFlag)
        {
            // show the removed student complete
            printf("%s removed\n", removedItemStr);
        }
    }
    // no return, void.
}