/*	Remove the first node, which has the min priority, from the heap

	param: 	heap	pointer to the heap
	pre:	heap is not empty
	post:	the first node is removed from the heap
*/
void removeMinHeap(DynArr *heap)
{
    /* heap->data should be replaced with getmin function*/
    heap->data[0] = getDynArr(heap, (sizeDynArr(heap) - 1));
    heap->size--;
    _adjustHeap(heap, (sizeDynArr(heap) - 1), 0);
}

/*	Remove the first node, which has the min priority, from the heap
 *		
 *			param: 	heap	pointer to the heap
 *				pre:	heap is not empty
 *					post:	the first node is removed from the heap
 *					*/
void removeMinHeap(DynArr *heap)
{
  	/* FIXME */
 heap->data[0] = getDynArr(heap, (sizeDynArr(heap) - 1));
    heap->size--;
    _adjustHeap(heap, (sizeDynArr(heap) - 1), 0);
}

/*	Get the index of the smaller node between two nodes in a heap

	param: 	heap	pointer to the heap
	param:	i	index of one node
	param:	j	index of other node
	pre:	i < size and j < size
	ret:	the index of the smaller node
*/
int _smallerIndexHeap(DynArr *heap, int i, int j)
{
  	assert(i < sizeDynArr(heap));
  	assert(j < sizeDynArr(heap));
  	if (compare(getDynArr(heap, i), getDynArr(heap, j)) == -1)
		return i;
  	else
		return j;
}

void _buildHeap(DynArr *heap)
{
    assert( heap != NULL );
    assert( sizeDynArr( heap ) > 0 );

    /* Start at the last non-leaf node */
    for( int i = ( sizeDynArr( heap ) / 2 ) - 1; i >= 0; --i )
        {
        _adjustHeap( heap, sizeDynArr( heap ), i );
        }
}

/*  Save the list to a file

    param:  heap    pointer to the list
    param:  filePtr	pointer to the file to which the list is saved
    pre:    The list is not empty
    post:   The list is saved to the file in tab-delimited format.
			Each line in the file stores a task, starting with the
			task priority, followed by a tab character (\t), and
			the task description.

			The tasks are not necessarily stored in the file in
			priority order.

*/
void saveList(DynArr *heap, FILE *filePtr)
{
	int i;
	Task* task;
	assert(sizeDynArr(heap) > 0);
	for(i = 0; i < sizeDynArr(heap); i++)
	{
		task = getDynArr(heap, i);
		fprintf(filePtr, "%d\t%s\n", task->priority, task->description);
	}
}

/*	Removes the first occurrence of the specified value from the collection
   if it occurs

   param:	v		pointer to the dynamic array
   param:	val		the value to remove from the array
   pre:	v is not null
   pre:	v is not empty
   post:	val has been removed
   post:	size of the bag is reduced by 1
 */
void removeDynArr(DynArr *v, TYPE val)
{
								/* FIXME: You will write this function */
								int i;
								for (i = 0; i < sizeDynArr(v); i++) {
																/* If the value is found we will remove it and end the for loop */
																if(EQ(val, v->data[i])) {
																								removeAtDynArr(v, i);
																								i = sizeDynArr(v) + 1;
																}
								}
}

/*	Get the index of the smaller node between two nodes in a heap

	param: 	heap	pointer to the heap
	param:	i	index of one node
	param:	j	index of other node
	pre:	i < size and j < size
	ret:	the index of the smaller node
 */
int _smallerIndexHeap(DynArr *heap, int i, int j)
{
    assert(i < sizeDynArr(heap));
    assert(j < sizeDynArr(heap));
    if(compare(heap->data[i], heap->data[j]) == -1) {
        return i;
    }
    else {
        return j;
    }

}

/*  Print the list

    param:  heap    pointer to the list
    pre:    the list is not empty
    post:   The tasks from the list are printed out in priority order.
			The tasks are not removed from the list.
*/
void printList(DynArr *heap)
{
    /* FIXME: Write this */
    struct DynArr *toPrint = createDynArr(sizeDynArr(heap));
    copyDynArr(heap, toPrint);
    int i, max = sizeDynArr(toPrint);
    sortHeap(toPrint);
    // call print_type() on each node
    for(i = 0; i < max; i++)
        print_type(getDynArr(toPrint, i));
        deleteList(toPrint);
}

/*  Print the list

    param:  heap    pointer to the list
    pre:    the list is not empty
    post:   The tasks from the list are printed out in priority order.
			The tasks are not removed from the list.
*/
void printListHelper(DynArr *heap, int pos, int count){
        
        printf("%d\t%s\n", heap->data[pos].priority, heap->data[pos].description);
        count++;
        while(count < sizeDynArr(heap)){
	
        if((pos*2)+1 < sizeDynArr(heap))
                printListHelper(heap, ((pos*2)+1), count);
        if((pos*2)+2 <sizeDynArr(heap))
                printListHelper(heap, ((pos*2)+2), count);
		
        }
}

void sortHeap(DynArr *heap)
{
    assert( heap != NULL );
    assert( sizeDynArr( heap ) > 0 );

    _buildHeap( heap );
    for( int i = ( sizeDynArr( heap ) - 1 ); i > 0; --i )
        {
        /* Swap the outer two elements in the heap, then adjust it */
        swapDynArr( heap, i, 0 );
        _adjustHeap( heap, i, 0 );
        }
}

/*	param: stack the stack being manipulated
	pre: the stack contains at least two elements
	post: the top two elements are popped and
	their quotient is pushed back onto the stack.
*/
void divide(struct DynArr *stack){
    if (sizeDynArr(stack) < 2){
    printf( "\n ERROR \n");
    printf("You need to have at least 2 numbers for division\n");
    printf("Please use:  number1 number2 / format \n");
    printf("number1 / number2 will not work \n");
    }
    assert(sizeDynArr(stack) >= 2);
    double number = topDynArr(stack);
    popDynArr(stack);
    double divide = topDynArr(stack)/number;
    popDynArr(stack);
    pushDynArr(stack, divide);
}

/*	param: stack the stack being manipulated
	pre: the stack contains at least two elements
	post: the top two elements are popped and
	their difference is pushed back onto the stack.
*/
void subtract(struct DynArr *stack){
     if (sizeDynArr(stack) < 2){
        printf( "\n ERROR \n");
        printf("You need to have at least 2 numbers for subtraction \n");
        printf("Please use:  number1 number2 - format \n");
        printf("number1 - number2 will not work \n");
    }
     assert(sizeDynArr(stack) >= 2);
    double number = topDynArr(stack);
    popDynArr(stack);
    double subtract = topDynArr(stack) - number;
    popDynArr(stack);
    pushDynArr(stack, subtract);
}

/*	param: stack the stack being manipulated
	pre: the stack contains at least two elements
	post: the top two elements are popped and
	their sum is pushed back onto the stack.
*/
void add (struct DynArr *stack){
    if (sizeDynArr(stack) < 2){
        printf( "\n ERROR \n");
        printf("You need to have at least 2 numbers for addition \n");
        printf("Please use:  number1 number2 + format \n");
        printf("number1 + number2 will not work \n");
    }
    assert(sizeDynArr(stack) >= 2);
    double first = topDynArr(stack);
    popDynArr(stack);
    double second = topDynArr(stack);
    popDynArr(stack);
    pushDynArr(stack, first + second);
}

/* param: stack the stack being manipulated
pre: the stack contains at least two elements
post: the top two elements are popped and
their quotient is pushed back onto the stack.
*/
void multiply(struct DynArr *stack){
    if (sizeDynArr(stack) < 2){
    printf( "\n ERROR \n");
    printf("You need to have at least 2 numbers for multiplication \n");
    printf("Please use:  number1 number2 x format \n");
    printf("number1 x number2 will not work \n");
    }
    assert(sizeDynArr(stack) >= 2);
    double num2 = topDynArr(stack);
    popDynArr(stack);
    double num1 = topDynArr(stack);
    popDynArr(stack);
    pushDynArr(stack, num1 * num2);
}

void _buildHeap(DynArr *heap)
{
    /* FIXME */
    assert(heap->size != 0);
    int size = sizeDynArr(heap);                //number of elements in heap

    int subTree = size / 2 - 1;                 //1st non-leaf subtree
    int max = sizeDynArr(heap);                 //last element in heap
    while(subTree != 0)
    {
        _adjustHeap(heap, max, subTree);       //percolate down the subtree and adjust order
        subTree--;                             //find next subtree starting
    }
}

/*	Remove the first node, which has the min priority, from the heap

    param:  heap	pointer to the heap
    pre:	heap is not empty
    post:	the first node is removed from the heap
 */
void removeMinHeap(DynArr *heap)
{
    int last;
    assert( sizeDynArr( heap ) > 0 );
    last = sizeDynArr( heap ) - 1;

    /* Copy the last element to the first */
    putDynArr( heap, 0, getDynArr( heap, last ) );

    /* Remove last element */
    removeAtDynArr( heap, last );

    /* Rebuild heap */
    _adjustHeap( heap, last, 0 );
}

/*	Adjust heap to maintain heap property

	param: 	heap	pointer to the heap
	param: 	max		index to adjust up to  (but not included)
	param: 	pos		position index where the adjustment starts
	pre:	max <= size
	post:	heap property is maintained for nodes from index pos to index max-1  (ie. up to, but not including max)
*/
void _adjustHeap(DynArr *heap, int max, int pos)
{
   /* FIXME */
	
	int left, right, small;
	
	assert(max <= sizeDynArr(heap)); 
	
	left = 2 * pos +1;
	right = 2 * pos +2; 

	if(right < max)
	{	
		small = _smallerIndexHeap(heap, left, right);
		
		if(compare(getDynArr(heap, small), getDynArr(heap, pos)) == -1)
		{	
			swapDynArr(heap, pos, small);
		
			_adjustHeap(heap, max, small);
		}
	}
	else if(left <  max)
	{ 	
		if(compare(getDynArr(heap, left), getDynArr(heap, pos)) == -1)
		{	
			swapDynArr(heap, pos, left);
		
			_adjustHeap(heap, max, left);
		}
	}

}

/*	Adjust heap to maintain heap property

	param: 	heap	pointer to the heap
	param: 	max		index to adjust up to  (but not included)
	param: 	pos		position index where the adjustment starts
	pre:	max <= size
	post:	heap property is maintained for nodes from index pos to index max-1  (ie. up to, but not including max)
*/
void _adjustHeap(DynArr *heap, int max, int pos)
{
   /* FIXME */
  assert(max <= sizeDynArr(heap));

  int left = (2 * pos) + 1;
  int right = (2 * pos) + 2;
  int small;
  
  if(right < max)
    {
      small = _smallerIndexHeap(heap, left, right);
      // can't alter type.h, but this would have been cleaner
      // if(heap->data[small].priority < heap->data[pos].priority)
      if (compare(getDynArr(heap,small),getDynArr(heap,pos)) == -1)
	{
	  swapDynArr(heap, small, pos); 
	  _adjustHeap(heap, max, small);
	}
    }
  else if(left < max)
    {
      // here is the type.h problem again
      // if(heap->data[left].priority < heap->data[pos].priority)
      if (compare(getDynArr(heap,left),getDynArr(heap,pos)) == -1)
	{
	  swapDynArr(heap, left, pos);
	  _adjustHeap(heap, max, left);
	}
    }
}

/*	Adjust heap to maintain heap property

	param: 	heap	pointer to the heap
	param: 	max		index to adjust up to  (but not included)
	param: 	pos		position index where the adjustment starts
	pre:	max <= size
	post:	heap property is maintained for nodes from index pos to index max-1  (ie. up to, but not including max)
 */
void _adjustHeap(DynArr *heap, int max, int pos)
{
    assert(max <= sizeDynArr(heap));
    int leftidx = (pos*2)+1;
    int rightidx = (pos*2)+2;
    int smallidx;
    // TYPE temp;
    if(rightidx < max) { //2 Children
        smallidx = _smallerIndexHeap(heap, leftidx, rightidx);
        if(compare(heap->data[smallidx], heap->data[pos]) == -1) {
            /*temp = heap->data[smallidx];
            heap->data[smallidx] = heap->data[pos];
            heap->data[pos] = temp;*/
            swapDynArr(heap, pos, smallidx);
            _adjustHeap(heap, max, smallidx);
        }
    }
    else if(leftidx < max) { // 1 Child
        if(compare(heap->data[pos], heap->data[leftidx]) == -1) {
            //heap->data[pos] = heap->data[leftidx];
            swapDynArr(heap, pos, leftidx);
            _adjustHeap(heap, max, leftidx);
        }

    }
}

void _buildHeap(DynArr *heap)
{
    /* FIXME */
    int index = sizeDynArr(heap);
    for (int i = index / 2 - 1; i>=0; i--)
    _adjustHeap(heap, index, i);
}