/*****************************************************************************
 *  
 *  File: PQ.C
 *  Author: Shawn Stoffer
 *  Description:  This file contains all of the defintions of the objects
 *                used for this implementation of a Priority queue.
 *  Systems:  This was written for SunOS, Solaris, linux, and AIX, but should
 *            not encounter any difficulties on other systems, as it does not
 *            use any system specific functions/calls.
 *  File Layout:  PQElement methods (although right now there are none....)
 *                are at the top, and then PQ methods are at the bottom.
 ****************************************************************************/

#include "PQ.h"

PQElement::PQElement(int priority) : prio(priority), index(0) { }
void PQElement::SetPrio(int newp) { prio = newp; }
int PQElement::Priority() { return prio; }
void PQElement::SetIndex(int nidx) { index = nidx; }
int PQElement::Index() { return index; }
PQElement::~PQElement() { }

PQ::PQ() : queue(0), size(0), used(0) { } 

PQ::PQ(size_t nsize) : size(nsize), used(0) {
  queue = new PQElement*[size];
  // Although it might be wise to initialize the array to NULL
  // pointers... It is not neccesary, because used determines how many
  // elements there are in the array.
}

PQ::~PQ() {
  for (int i = 0; i < size; i++) {
    // This came about due to a strange bug that when I used 'delete queue[i]'
    // it would delete the array....
    delete (queue[i]);
  }
  delete [] queue;
}

//**********   PQ methods  *************

// Variables are as follows:
//    p - this is the place on the heap that the target element is at.
//        this is assumed to be a valid id.  If sent any value that is not a 
//        valid address for the heap...this funciton will blow up.
//    curr - this is the pointer to the element to be moved.
//    queue - the internal queue of this PQ object.
//   Function:  This function will copy the pointer at location p, make a
//     sentinel at 0 and will then compare priorities, starting with location
//     p, to find where the elements should go.  If its parent has a greater 
//     value of the priority (meaning lower priority), it will move the parent
//     down to where it was, and then move into its parents location.
void PQ::upheap(int p) {
  PQElement * curr;
  curr = queue[p];  
  queue[0] = new PQElement(-1); // Follow example in the book of highest prio.
  while (queue[p/2]->Priority() > curr->Priority()) {
    // All that has to be done is switch the pointers.
    queue[p] = queue[p/2]; 
    queue[p]->SetIndex(p);
    p = p/2;
  }
  queue[p] = curr;  // we have a place for the element, so stick it in there.
  curr->SetIndex(p); // make sure to change the internal index of the element.
}

// This functions variables are as follows:
//     curr - assumed to be a pointer to a real PQElement.  If it is not, this
//            function will place a bad pointer into the queue and this could 
//            cause problems later in the implementation.
//     size - the maximum size of the current queue (according to memory 
//            allocated.
//     used - the amount of locations in the heap currently taken up.
//     queue - the internal queue of the PQ object.
//     n - the temporary queue.
void PQ::insert(PQElement * curr) {
  queue[++used] = curr;
  upheap(used);
}

// The function variables are as follows:
//     p is assumed to be a valid location on the heap.
//     i is a  counting variable.
//     curr is a temporary variable for the PQElement to be moved.
//     used is the amount of the internal queue that is currently being used.
void PQ::downheap(int p) {
  int i;
  PQElement * curr;

  curr = queue[p];
  while (p <= used/2) {
    i = p+p;
    if (i < used && queue[i]->Priority() > queue[i+1]->Priority()) i++;
    if (curr->Priority() <= queue[i]->Priority()) break;
    queue[p] = queue[i]; 
    queue[p]->SetIndex(p);
    p = i;
  }
  queue[p] = curr;
  curr->SetIndex(p);
}

/*  This will always remove something from above the bottom of the tree, 
 *  so an effiecient way to tdo this is free the element to be deleted, then 
 *  exchange the last element with the deleted element, and call down heap on 
 *  it to put it back in its place.  Normally this would cause a memory leak, 
 *  but we know that the caller already has a pointer to it.
 */

void PQ::extract(size_t idx) {
  // what if this is the last element?  Then we would be doing nothing...
  if (queue[idx] == queue[used]) used--;
  else {  
    queue[idx] = queue[used--];
    if (queue[idx]->Priority() < queue[idx/2]->Priority()) 
      upheap(idx);
    else 
    downheap(idx);
  }
}

//  The function's variables are as follows:
//     curr is a temporary variable to hold onto the top queue element.
//     queue is the internal queue of the PQ Object.
PQElement * PQ::remove() {
  if (!used) return NULL;
  PQElement * curr = queue[1];
  queue[1] = queue[used--];  // make the last PQElement the first
  downheap(1);               // and then move it down to it's real position in 
                             // the heap.
  curr->SetIndex(0);
  return curr;
}

// This function will check the top element from the queue's time and return
// that.
int PQ::check() {
  if (used < 1) return 0;
  return queue[1]->Priority();
}

// This function's variables:
//   curr is a pointer to a PQElement.  If it is not valid it will kill the program.
//   This function will return a pointer to the element replaced.
PQElement* PQ::replace(PQElement *curr) {
  queue[0] = curr;
  downheap(0);
  queue[0]->SetIndex(0);
  return queue[0];
}

void PQ::resize(size_t nsize) {
  PQElement ** n = new PQElement*[nsize];
  if (queue) {
    memcpy(n, queue, sizeof(PQElement**)*used+2);
    delete [] queue;
  }
  queue = n;
  size = nsize;
}