///////////////////////////////////////////////////////////////////////////////
// Simple implementation of three abstract data types (ADTs):
//  Vec  - vector  (a 1D variable length array)
//  Queue - implemented using a Vec
//  Heap - uses Vec to store heap
// In newer C++ compilers, better implementations of these will be available in 
// the STL (Standard Template Library).
///////////////////////////////////////////////////////////////////////////////
#ifdef GNUGPP
 #define BOOL_DEFN
#endif

#include "iostream.h"
#include "ADT.h"

#define max(A,B) ((A)>(B)?(A):(B))
#define min(A,B) ((A)<(B)?(A):(B))

#define MIN_ADT_VEC_SIZE 64
#define MAX_ADT_VEC_INCR 64
#define CHATTY false

// A swap routine is built in on g++ compilers, and part of the STL,
// but not on Tuzo yet.
template<class T> void swap (T& a, T& b)
{
 T tmp = a; 
 a = b;
 b = tmp;
}

///////////////////////////////////////////////////////////////////////////////
// Simple implementation of vectors 
///////////////////////////////////////////////////////////////////////////////

// Vec constructor
template<class T> Vec<T>::Vec(int s=0)
{
 ndata = s;
 if (s>0)
  data = new T[ndata];
}

// Vec destructor
template<class T> Vec<T>::~Vec()
{
  delete[] data;
}

// Return current size of vector
template<class T> int Vec<T>::size()
{
  return ndata;
}                  

// reference operator a[i]
template<class T> T& Vec<T>::operator[](int i)
{
 // Vec indexing is NOT checked for out-of-bounds
 return *(data+i);
}

// Extend a Vec object by n more elements (at end)
template<class T> void Vec<T>::extend(int n, int rotate=0)
{
 if (n > 0) {
  // Should use data.resize(max_size+n) from Standard Template library
  // Work-around (inefficient but simple)
  T* tmp;
  tmp = new T[ndata + n]; // simply allocate a bigger array
  int i;
  if (rotate==0)           // copy old data items
   for(i=0; i<ndata; i++)  
    tmp[i] = data[i];
  else                     // copy data items using cyclic array indexing 
   for(i=0; i<ndata; i++)  
    tmp[i] = data[(i+rotate) % ndata];
  delete[] data;          // delete the old array

  data = tmp;             // reset the pointer
  ndata += n;             // reset the size 
 }
}

/////////////////////////////////////
// The Stack class 
////////////////////////////////////

template<class T> Stack<T>::Stack(int s=0)
 :stack(max(s,MIN_ADT_VEC_SIZE))
{
 max_size = stack.size(); 
 if (CHATTY)
  cout << "Initial stack size " << max_size << "\n";
 top = 0;
}

template<class T> Stack<T>::~Stack(){}    // stack destructor, no-op

template<class T> void Stack<T>::push(T pt) // Push item on stack
{
 // Check for space, increase stack if insufficient space.
 if (top == max_size) {
  if (CHATTY)
   cout << "Resizing stack...";
  // Extend this object minimum of max_size or MAX_ADT_VEC_INCR elements
  stack.extend(min(max_size, MAX_ADT_VEC_INCR));  
  max_size = stack.size();
  if (CHATTY)
   cout << "new stack size: " << max_size << "\n";
 }

 stack[top] = pt;
 top++;
}

// pop item off front of stack (returns NULL if empty)
template<class T> T* Stack<T>::pop() 
{
 if (top == 0) 
  return NULL;

 top--;
 T popped = stack[top];  // Copy previous top element
 return &popped;
}

/////////////////////////////////////
// The Queue class 
////////////////////////////////////

template<class T> Queue<T>::Queue(int s=0)
 :queue(max(s,MIN_ADT_VEC_SIZE))
{
 max_size = queue.size(); 
 if (CHATTY)
  cout << "Initial queue size " << max_size << "\n";
 first = -1; last = 0;
}

template<class T> Queue<T>::~Queue(){}    // queue destructor, no-op

template<class T> void Queue<T>::push(T pt) // Push item on queue
{
 // Check for space, increase queue if insufficient space.
 if (last == first) {
  if (CHATTY)
   cout << "Resizing queue...";
  // Extend this object minimum of max_size or MAX_ADT_VEC_INCR elements,
  // use a cyclic copy starting with first element.
  queue.extend(min(max_size, MAX_ADT_VEC_INCR), first);  
  first = 0;
  last = max_size;
  max_size = queue.size();
  if (CHATTY)
   cout << "new queue size: " << max_size << "\n";
 }

 if (first < 0) {  // queue initially empty
  first = last = 0;
 }
 queue[last] = pt;
 last++;
 last = last % max_size;
}

// pop item off front of queue (returns NULL if empty)
template<class T> T* Queue<T>::pop() 
{

 if (first<0) 
  return NULL;

 T* popped = new T;
 *popped = queue[first];
 first++;
 first = first % max_size;

 if (first == last) {   // popped last item off queue
  first = -1; last = 0; // signifies queue empty 
 }

 return popped;
}

/////////////////////////////////////
// The Heap class 
////////////////////////////////////

// heap constructor
template<class T, class C> Heap<T,C>::Heap(int s=0)
 :heap(max(s,MIN_ADT_VEC_SIZE))
{
 max_size = heap.size(); 
 if (CHATTY)
  cout << "Initial heap size " << max_size << "\n";
 last = 0; 
}

template<class T, class C> Heap<T,C>::~Heap(){}

template<class T, class C> void Heap<T, C>::push(T pt) 
{
 // Check for space, increase heap if insufficient space.
 if (last >= max_size) {
  if (CHATTY)
   cout << "Resizing heap...";
  // Extend this object minimum of max_size or MAX_ADT_VEC_INCR elements
  heap.extend(min(max_size, MAX_ADT_VEC_INCR));  
  max_size = heap.size();
  if (CHATTY)
   cout << "new heap size: " << max_size << "\n";
 }

 // Insert new item at end 
 heap[last] = pt;
 last++;

 // Percolate new item upwards, so long as parent has higher priority.
 int child = last-1;
 int parent;
 while(child>0) {
  parent = (child-1)/2;
  if (C::lt(heap[child], heap[parent])) {
   swap(heap[child], heap[parent]);
  } else
   break;
  child = parent;
 }
 // End of percolation, return from push
}

// Pop from heap:
//  Return minimum priority item, and maintain heap structure
//  If heap is empty, return NULL
template<class T, class C> T* Heap<T,C>::pop()
{

 if (last == 0) {
  return NULL;    // heap is empty
 }

 T* popped = new T;
 *popped = heap[0]; 

 // Replace root by bottom right-most item 
 heap[0] = heap[last-1];
 last--;

 // Percolate the new root element down the tree.
 int parent = 0;
 int left = 1;
 int right = 2;
 while(left <last) {

  if (left < last && C::lt(heap[left], heap[parent]))
   if (right < last && C::lt(heap[right], heap[left])) {
    // right is the minimum priority child
    swap(heap[parent], heap[right]);
    parent = right;
   } else {
    // left is the minimum priority child
    swap(heap[parent], heap[left]);  
    parent = left;
   }
  else 
   if (right < last && C::lt(heap[right], heap[parent])) {
    // right is the minimum priority child since
    // left is known to have higher priority than parent
    swap(heap[parent], heap[right]);
    parent = right;
   } else 
    // Both left and right children have larger priorities than parent...
    break;  // ... so we are finished percolating.  

  // Compute indices of children given new parent
  left = 2*parent+1;
  right = left + 1;  // These children may be beyond the last element.
 }
 // Completed percolation

 return popped;
}
// End of the definition of the Heap class

#ifdef GNUGPP
 // For g++ we need to instantiate particular template classes used 
 // See http://www.cygnus.com/misc/g++FAQ.html
 #include "event.h"
 template class Heap<eventClass*, earlier>;
 template class Queue<clientClass*>;
#endif
