#include <stdlib.h>
#include "pqueue.h"

PQueue::PQueue (int s, valueFunc *v, displayFunc *d) {
   size = s;
   objects = new void*[size];
   tail = 0;
   valfn = v;
   dispfn = d;
}

PQueue::PQueue (valueFunc *v, displayFunc *d) {
   size = 10000;
   objects = new void*[size];
   tail = 0;
   valfn = v;
   dispfn = d;
}

PQueue::PQueue (int s, valueFunc *v) {
   size = s;
   objects = new void*[size];
   tail = 0;
   valfn = v;
   dispfn = NULL;
}

PQueue::PQueue (valueFunc *v) {
   size = 10000;
   objects = new void*[size];
   tail = 0;
   valfn = v;
   dispfn = NULL;
}

PQueue::~PQueue() { delete objects; }

bool PQueue::empty() { return tail == 0; }

void PQueue::insert(void *obj) {
   if (obj == NULL) return;
   int ptr = tail;
   objects[tail++] = obj;
   while ((ptr-1)/2 >= 0 && 
	  valfn->value(objects[ptr]) < valfn->value(objects[(ptr-1)/2])) {
      void *tobj = objects[ptr];
      objects[ptr] = objects[(ptr-1)/2];
      objects[(ptr-1)/2] = tobj;
      ptr = (ptr-1)/2;
   }
}

void *PQueue::remove () {
   if (tail == 0) return NULL;
   void *t = objects[0];
   objects[0] = objects[--tail];
   int ptr = 0;
   while (2*(ptr+1) <= tail) {
      void *p = objects[ptr];
      if (valfn->value(objects[(ptr+1)*2-1]) < valfn->value(objects[ptr])) {
	 if (valfn->value(objects[(ptr+1)*2-1]) < 
	     valfn->value(objects[(ptr+1)*2])) {
	    objects[ptr] = objects[(ptr+1)*2-1];
	    objects[(ptr+1)*2-1] = p;
	    ptr = (ptr+1)*2-1;
	 } else {
	    objects[ptr] = objects[(ptr+1)*2];
	    objects[(ptr+1)*2] = p;
	    ptr = (ptr+1)*2;
	 }
      } else if (2*(ptr+1) < tail) {
	 if (valfn->value(objects[(ptr+1)*2]) < valfn->value(objects[ptr])) {
	    objects[ptr] = objects[(ptr+1)*2];
	    objects[(ptr+1)*2] = p;
	    ptr = (ptr+1)*2;
	 } else break;
      } else break;
   }
   return t;
}

void PQueue::printTree () {
   int blanks = 80/2, d=1, n=1;
   for (int k=0 ; k < tail ; k++) {
      if (d == 0) {
	 n *= 2;
	 d = n;
	 blanks = 40/(n+1);
	 cout << "\n";
	 for (int i=0 ; i < 30/n ; i++) cout << " ";
      } 
      for (int i=0 ; i < blanks ; i++) cout << " ";
      cout << "[";
      if (dispfn == NULL)
	 cout << valfn->value(objects[k]);
      else
	 dispfn->display(objects[k]);
      cout << "] ";
      d--;
   }
   cout << "\n";
}

ostream & operator<<(ostream & out, PQueue *pq) {
   int count = pq->tail;
   bool *isdone = new bool[count];
   for (int i=0 ; i < count ; i++) isdone[i] = false;
   for (int i=0 ; i < count ; i++) {
      int tmp = 10000;
      int j = -1;
      for (int k=0 ; k < pq->tail ; k++) {
	 if (isdone[k]) continue;
	 if (pq->valfn->value(pq->objects[k]) < tmp) {
	    j = k;
	    tmp = pq->valfn->value(pq->objects[k]);
	 }
      }
      isdone[j] = true;
      out << "[";
      if (pq->dispfn == NULL) 
	 out << pq->valfn->value(pq->objects[j]);
      else
	 pq->dispfn->display(pq->objects[j]);
      out << "] ";
   }
   return out;
}