/* Filename:  heap.cpp

   Programmer:  Br. David Carlson

   Date:  October 4, 1997

   Revised:  June 19, 1999

   Revised:  July 17, 2000 to use modern headers.

   Reference:  Data Structures with C++, by Ford and Topp, pp 690 - 703.

   This file implements the functions for the HeapClass declared in heap.h.
*/

#include "heap.h"


/* Given:   IntArray  Array of integers.
            Count     The number of integers in IntArray.
   Task:    To construct a heap object containing a pointer to IntArray.
            This includes moving the data around in IntArray so as to get
            a heap.
   Return:  IntArray  Modified array.
            The object itself is also modified and will contain a
            pointer to the array that holds the heap data.
*/
HeapClass::HeapClass(IntArrayType IntArray, int Count)
   {
   int CurrentPosition;

   if (Count <= 0)
      {
      cerr << "Cannot construct a heap with size 0 or less." << endl;
      exit(1);
      }

   MaxHeapSize = Count;
   HeapSize = Count;
   HeapArrayPtr = IntArray;   // a pointer assignment statement

   // Set CurrentPosition to the last index of a parent node:
   CurrentPosition = (HeapSize - 2) / 2;

   while (CurrentPosition >= 0)
      {
      // Get heap condition for subtree rooted at index CurrentPosition:
      FilterDown(CurrentPosition);
      CurrentPosition--;
      }
   }


/* Given:  Nothing other than the implicit HeapClass object.
   Task:   To remove the smallest item from the heap and readjust it
           so that it remains a heap.  If there is nothing to remove
           from the heap, terminate the program.
   Return: In the function name, return this smallest item.
*/
int HeapClass::Delete(void)
   {
   int Temp;

   if (HeapSize == 0)
      {
      cerr << "Cannot remove from an empty heap" << endl;
      exit(1);
      }

   Temp = HeapArrayPtr[0];   // Item at index 0 is the smallest
   // copy last one to root:
   HeapArrayPtr[0] = HeapArrayPtr[HeapSize - 1];
   HeapSize--;
   FilterDown(0);   // readjust to be a heap
   return Temp;
   }


/* Given:  StartIndex   Index at which to start restoring the heap.
           Of course, we also have the implied HeapClass object.
           It is assumed that we already have a heap except possibly
           for the item at index StartIndex.
   Task:   To readjust the items in the subtree rooted at StartIndex
           so that we have a heap.
   Return: Nothing directly, but the implied HeapClass object is
           modified.
*/
void HeapClass::FilterDown(int StartIndex)
   {
   int CurrentPosition, ChildPosition, RightChildPosition, Target;

   CurrentPosition = StartIndex;
   Target = HeapArrayPtr[StartIndex];
   ChildPosition = LeftChild(CurrentPosition);

   while (ChildPosition < HeapSize)
      {
      RightChildPosition = ChildPosition + 1;
      //  Set ChildPosition to index of smaller of right, left children:
      if ((RightChildPosition < HeapSize) &&
        (HeapArrayPtr[RightChildPosition] <= HeapArrayPtr[ChildPosition]))
        ChildPosition = RightChildPosition;

      if (Target <= HeapArrayPtr[ChildPosition])
         break;  // Get out of loop, heap OK with Target at CurrentPosition

      // Move value of the smaller child to the parent node:
      HeapArrayPtr[CurrentPosition] = HeapArrayPtr[ChildPosition];
      // Move down the tree:
      CurrentPosition = ChildPosition;
      ChildPosition = LeftChild(CurrentPosition);
      }

   // Put Target into the correct location:
   HeapArrayPtr[CurrentPosition] = Target;
   }


/* Given:  StartIndex  The index at which to start restoring the heap.
           Of course, we also have the implied HeapClass object.
           It is assumed that we have a heap from index 0 to index
           StartIndex - 1, so that the only item possibly out of order
           is the one at StartIndex.
   Task:   Move up the tree from StartIndex, adjusting so as to
           have a heap from index 0 to index StartIndex.
   Return: Nothing directly, but the implied HeapClass object is
           modified.
*/
void HeapClass::FilterUp(int StartIndex)
   {
   int CurrentPosition, ParentPosition, Target;

   CurrentPosition = StartIndex;
   ParentPosition = Parent(CurrentPosition);
   Target = HeapArrayPtr[StartIndex];

   while (CurrentPosition != 0)
      {
      if (HeapArrayPtr[ParentPosition] <= Target)
         break; // Get out of loop, heap OK with Target at CurrentPosition

      // Move parent value to child:
      HeapArrayPtr[CurrentPosition] = HeapArrayPtr[ParentPosition];
      // Move up in the tree:
      CurrentPosition = ParentPosition;
      ParentPosition = Parent(CurrentPosition);
      }

   // Place Target at the position located for it:
   HeapArrayPtr[CurrentPosition] = Target;
   }


/* Given:  Item   Number to insert into the heap.
           Of course, we also have the implied HeapClass object.
   Task:   To insert Item into the heap so as to maintain it as a heap.
   Return: Nothing directly, but the implied HeapClass object is modified.
*/
void HeapClass::Insert(int Item)
   {
   if (HeapSize == MaxHeapSize)
      {
      cerr << "Cannot insert into a full heap" << endl;
      exit(1);
      }

   // At first, place item at the end of the heap:
   HeapArrayPtr[HeapSize] = Item;
   FilterUp(HeapSize);   // restore heap property
   HeapSize++;
   }