// heap.cc   ADT for a min-heap   P. Conrad CISC220 06J

#include "heap.h"


Heap_C::Heap_C() // create empty heap
{
  count = 0;
}

void Heap_C::add(int x) // O(log n)
{
  data[count] = x;
  count ++;
  bubbleUp(count-1); 
}

int Heap_C::deleteMin() // O(log n)
{
  int result = data[0];
  data[0] = data[count -1];
  count --;

#ifdef HEAPDEBUG
  cout << "In deleteMin, before heapify(0), *this=" << *this << endl;
#endif

  heapify(0);

#ifdef HEAPDEBUG
  cout << "In deleteMin, after heapify(0), *this=" << *this << endl;
#endif

  return result;
}

void Heap_C::bubbleUp(int index)
{
  // move up towards the root

  // check whether this element is already <= to its parent.
  // if we are at the root, it's parent is "itself", so this 
  // will succeed.   If we are already <= to the parent, this is the
  // base case and we are finished

  int parent = parentOf(index);

  if (data[parent] <= data[index] )
    {
      return; // base case
    }
  // otherwise, swap the two and do a recursive call on the parent

  // swap the root of this subtree with the smaller child

  int temp = data[parent];
  data [parent] = data[index];
  data [index] = temp;

  bubbleUp(parent);
  

}


void Heap_C::heapify(int index)
{
  // we will need to compute these values several times,
  // so storing them in a local variable is both 
  // more efficient (in terms of CPU) and 
  // make the code easier to read

  int leftChild = leftChildOf(index);
  int rightChild = rightChildOf(index);

  // if this node is a leaf, we are finished--a subtree
  // that is rooted at a leaf already has the heap property
  // (mathematicians would say this is a "trivial case")

  if (leftChild >= count) 
    {

#ifdef HEAPDEBUG
      cout << "In heapify, first base case" << endl;
      cout << "rightChild=" << rightChild << " count=" << count << endl;
#endif

      return;  // first base case
    }


  // Second base case:
  //  If we have only one child, it must be a left child.
  //  In that case, we can say that the right child does not exist;
  //  i.e. its index is >= count

  if (rightChild >= count)
    {
      // in this case, we only need to check the left child
      // if the left child is larger, then swap it

      if ( data[index] >= data[leftChild]  )
	{
	  int temp = data[leftChild];
	  data [leftChild] = data[index];
	  data [index] = temp;
	}

      // if this node had only child, then that child cannot
      // have any children (because of the heap shape), so
      // we are finished.

#ifdef HEAPDEBUG
      cout << "In heapify, second base case" << endl;
      cout << "rightChild=" << rightChild << " count=" << count << endl;
#endif

      return;

    }


  // check the node at position "index".
  // see if it is smaller than the two children.
  // If so, we can just return--that the third base case
  
  if ( data[index] <= data[leftChild] && data[index] <= data[rightChild]  )
  {

#ifdef HEAPDEBUG
      cout << "In heapify, third base case" << endl;
#endif

    return;
  }

  // recursive call: pull up the smaller of the two children,
  // then do a recursive call on whichever one we swapped with


  int smallerChild = leftChild; // assume leftChild is smaller

  if ( data[rightChild] <= data[leftChild] )
    smallerChild = rightChild; // change if our assumption was wrong

  // swap the root of this subtree with the smaller child

  int temp = data[smallerChild];
  data [smallerChild] = data[index];
  data [index] = temp;

  // do a recursive call on the tree we swapped with 
  // in case the value we placed there is still larger than ITS children

  heapify(smallerChild);
  return;

}



#include "runTests.h"

void Heap_C::testPrivateMemberFunctions(RunTests_C &test)
{
  test.assertEquals(parentOf(0),0);
  test.assertEquals(parentOf(1),0);
  test.assertEquals(parentOf(2),0);
  test.assertEquals(parentOf(3),1);
  test.assertEquals(parentOf(4),1);
  test.assertEquals(parentOf(5),2);
  test.assertEquals(parentOf(6),2);
  test.assertEquals(parentOf(7),3);
  test.assertEquals(parentOf(8),3);

  test.assertEquals(leftChildOf(0),1);
  test.assertEquals(rightChildOf(0),2);
  test.assertEquals(leftChildOf(1),3);
  test.assertEquals(rightChildOf(1),4);
  test.assertEquals(leftChildOf(2),5);
  test.assertEquals(rightChildOf(2),6);
  test.assertEquals(leftChildOf(3),7);
  test.assertEquals(rightChildOf(3),8);


}

void Heap_C::print(ostream & out) const
{
  out << "[";
  if (count >= 1)
    cout << data[0];
  for (int i=1; i<count; i++)
    {
      out << "|" << data[i];
    }
  cout << "]";
}

ostream & operator << (ostream & left, const Heap_C & right)
{
  right.print(left);
  return left;
}