#include <stdio.h>
#include <stdlib.h>     // exit
#include <string.h>     // strcpy, strlen
#include "MinHeap.h"    // with include "State.h"

// Priority queue implementation as a MinHeap
MinHeap::MinHeap(int size):  N(0), Size(size)
{  Heap = (State**) calloc (Size+1,sizeof *Heap); }

MinHeap::~MinHeap(void)
{
   while ( N > 0 )      // First, empty the remaining queued entries
      delete Heap[N--];
   free(Heap);          // Generated by calloc / realloc
}

int MinHeap::isEmpty ( void )
{  return N == 0;  }    // Not exactly rocket science!

int MinHeap::size ( void ) { return Size; }

void MinHeap::add ( State* item )
{  N++;
   if ( N > Size ) // Dynamic memory allocation on overflow
   {  Size += Size;
      Heap = (State**) realloc (Heap, (Size+1) * sizeof *Heap);
   }
   Heap[N] = item;
   upHeap(N);
}

State*  MinHeap::remove ( void )
{  State* Rtn = Heap[1];

   if (N < 1) return NULL;        // I.e., attempt to dequeue on empty

   Heap[1] = Heap[N--];           // The last shall be first
   downHeap(1);                   // --- but not for long

   return Rtn;                    // Return item that had been on top
}

void MinHeap::upHeap(int C)  // Correct the heap from C upwards
{  int P = C/2;
   State* Hold = Heap[C];    

   while ( P > 0 && Hold->compare(Heap[P]) < 0 )
   {
      Heap[C] = Heap[P];
      C = P;
      P = C/2;
   }
   Heap[C] = Hold;
}

void MinHeap::downHeap(int P)// Correct the heap from P downwards
{
   State* Hold = Heap[P];
   int C = 2*P;

   while (C <= N)
   {
      if ( C < N && Heap[C]->compare(Heap[C+1]) > 0 )
         C++;
      if ( ! (Heap[C]->compare(Hold) < 0) )
         break;
      Heap[P] = Heap[C];
      P = C;
      C = 2*P;
   }
   Heap[P] = Hold;
}