// file: $isip/class/dstr/PriorityQueue/PriorityQueue.h// version: $Id: PriorityQueue.h,v 1.5 2002/08/13 14:19:43 alphonso Exp $//// make sure definitions are made only once//#ifndef ISIP_PRIORITY_QUEUE#define ISIP_PRIORITY_QUEUE// isip include files//#ifndef ISIP_DSTR_BASE#include <DstrBase.h>#endif#ifndef ISIP_LONG#include <Long.h>#endif#ifndef ISIP_STRING#include <String.h>#endif#ifndef ISIP_CHAR#include <Char.h>#endif#ifndef ISIP_CONSOLE#include <Console.h>#endif// forward class definitions//template<class TObject> class PriorityQueueDiagnose;// PriorityQueue: this class implements a standard priority queue// using a vector to implement the underlying heap data structure.//template<class TObject>class PriorityQueue : public DstrBase {    //---------------------------------------------------------------------------  //  // public constants  //  //---------------------------------------------------------------------------public:    // define the class name  //  static const String CLASS_NAME;  //----------------------------------------  //  // i/o related constants  //  //----------------------------------------      static const String DEF_PARAM;    //----------------------------------------  //  // default values and arguments  //  //----------------------------------------    // default values  //  static const long DEF_END_POS = -1;    // default arguments to methods  //    //----------------------------------------  //  // error codes  //  //----------------------------------------      //---------------------------------------------------------------------------  //  // protected data  //  //---------------------------------------------------------------------------protected:  // comparison function for the items in the priority queue  //  typedef Integral::COMPARE (*COMPARE_FUNC)(TObject* item1, TObject* item2);    // the internal structure of the priority queue  //  TObject** v_d;  // the allocation mode  //  ALLOCATION alloc_d;  // number of elements of this vector  //  Long length_d;  // the maximum number of elements  //  Long capacity_d;    // debugging parameters  //  static Integral::DEBUG debug_level_d;  // define the memory manager  //    static MemoryManager mgr_d;    //---------------------------------------------------------------------------  //  // required public methods  //  //---------------------------------------------------------------------------public:    // static methods:  //  the diagnose method is moved outside the class header file and  //  defined in the PriorityQueueDiagnose.h in order to avoid issues  //  with preprocessing of the diagnose code.  //  static const String& name();    // method: setDebug  //  static boolean setDebug(Integral::DEBUG debug_level) {    debug_level_d = debug_level;    return true;  }  // other debug methods  //  boolean debug(const unichar* message) const;       // destructor/constructor(s)  //  ~PriorityQueue();  PriorityQueue(ALLOCATION alloc = DEF_ALLOCATION);  PriorityQueue(const PriorityQueue<TObject>& copy_queue);  // assign method  //  boolean assign(const PriorityQueue<TObject>& copy_stack);    // method: operator=  //  PriorityQueue<TObject>& operator=(const PriorityQueue<TObject>& arg) {    assign(arg);    return *this;  }  // method: eq  //  boolean eq(const PriorityQueue<TObject>& arg) const;    // method: read  //  boolean read(Sof& sof, long tag) {    return read(sof, tag, name());  }  // method: write  //  boolean write(Sof& sof, long tag) const {    return write(sof, tag, name());  }  // method: sofSize  //  long sofSize() const {    return 0;  }  // method: read  //    boolean read(Sof& sof, long tag, const String& name) {    return Error::handle(name(), L"read", Error::ARG, __FILE__, __LINE__);  }  // method: write  //    boolean write(Sof& sof, long tag, const String& name) const {    return Error::handle(name(), L"write", Error::ARG, __FILE__, __LINE__);  }  // method: readData  //    boolean readData(Sof& sof, const String& pname = DEF_PARAM,		   long size = SofParser::FULL_OBJECT,                   boolean param = true,		   boolean nested = true) {    return Error::handle(name(), L"readData", Error::ARG, __FILE__, __LINE__);  }  // method: writeData  //    boolean writeData(Sof& sof, const String& pname = DEF_PARAM) const {    return Error::handle(name(), L"writeData", Error::ARG, __FILE__, __LINE__);  }  // method: new  //  static void* operator new(size_t size) {    return mgr_d.get();  }  // method: new[]  //  static void* operator new[](size_t size) {    return mgr_d.getBlock(size);  }  // method: delete  //  static void operator delete(void* ptr) {    mgr_d.release(ptr);  }  // method: delete[]  //  static void operator delete[](void* ptr) {    mgr_d.releaseBlock(ptr);  }  // method: setGrowSize  //  static boolean setGrowSize(long grow_size) {    return mgr_d.setGrow(grow_size);  }      // method: clear  //  boolean clear(Integral::CMODE cmode = Integral::DEF_CMODE);    //---------------------------------------------------------------------------  //  // class-specific public methods:  //  priority queue push, pop and top methods  //  //---------------------------------------------------------------------------  // method inserts an intem into the priority queue  //  boolean push(TObject* item, COMPARE_FUNC comp_func = compare);  // method removes the largest item from the priority queue  //  TObject* pop(TObject* item = (TObject*)NULL);    // method: top  //  const TObject* top() const;  TObject* top();    //---------------------------------------------------------------------------  //  // class-specific public methods:  //  size-related methods  //  //--------------------------------------------------------------------------  // method: isEmpty  //  boolean isEmpty() const {    return ((long)length_d == 0);  }  // method: length  //  long length() const {    return (long)length_d;  }  // method: getCapacity  //  long getCapacity() const {    return (long)capacity_d;  }    // resize methods  //  boolean setLength(long length, boolean preserve_values = true);  boolean setCapacity(long capacity, boolean preserve_values = true);  //---------------------------------------------------------------------------  //  // private methods  //  //---------------------------------------------------------------------------private:  //---------------------------------------------------------------------------  //  // class-specific public methods:  //  priority queue property methods  //  //---------------------------------------------------------------------------    // method: parent  //  long parent(long val) {    return (val - 1) / 2;  }  // method: left  //  long left(long val) {    return  (2 * val) + 1;  }  // method: right  //  long right(long val) {    return (2 * val) + 2;  }    //---------------------------------------------------------------------------  //  // class-specific public methods:  //  heap manipulation methods  //  //--------------------------------------------------------------------------   // this method evaluates the kernel for the input vectors  //  static Integral::COMPARE compare(TObject* item1, TObject* item2);    // method to reorder the heap and maintain the heap property  //  boolean heapify(long index, COMPARE_FUNC comp_func = compare);  // method to construct a heap out of an existing array  //  boolean buildHeap();  // method to sort an existing heap  //  boolean heapSort();  // method to access the heap based on the mode  //  TObject* accessByMode(TObject* item);};//-----------------------------------------------------------------------------//// we define non-integral constants at the end of class definition for// templates (for non-templates these are defined in the default constructor)//      //-----------------------------------------------------------------------------// constants: required constants such as the class name//template <class TObject>const String PriorityQueue<TObject>::CLASS_NAME(L"PriorityQueue");template <class TObject>const String PriorityQueue<TObject>::DEF_PARAM(L"values");// static instantiations: debug level//template <class TObject>Integral::DEBUG PriorityQueue<TObject>::debug_level_d = Integral::NONE;// static instantiations: the memory manager//template <class TObject>MemoryManager PriorityQueue<TObject>::mgr_d(sizeof(PriorityQueue<TObject>), CLASS_NAME);// below are all the methods for the Queue template class//      // ---------------------------------------------------------------------//// required static methods////----------------------------------------------------------------------// method: name//// arguments: none//// return: a static String& containing the class name//// this method returns the class name//template<class TObject>const String& PriorityQueue<TObject>::name() {    // create the static name string for this class and return it  //  static String cname(CLASS_NAME);  cname.clear();  cname.concat(CLASS_NAME);  cname.concat(L"<");  cname.concat(TObject::name());  cname.concat(L">");    // return the name  //  return cname;}// ---------------------------------------------------------------------//// required debug methods////----------------------------------------------------------------------// method: debug//// arguments://  unichar* message: (input) information message//// return: a boolean value indicating status//// this method dumps the contents of an object to the console// template<class TObject>boolean PriorityQueue<TObject>::debug(const unichar* message_a) const {  // declare temporary strings to hold class data  //  String output;  String value;  String param;  String numeric;    // dump the length  //  value.assign((long)length_d);  output.debugStr(name(), message_a, L"length_d", value);  Console::put(output);  // dump the capacity  //  value.assign((long)capacity_d);  output.debugStr(name(), message_a, L"capacity_d", value);  Console::put(output);  // dump the values  //  for (long i = 0; i < (long)length_d; i++) {    param.assign(L"v_d[");    value.assign(i);    param.concat(value);    param.concat(L"]");    output.debugStr(name(), message_a, param);    Console::put(output);    // increase indention    //    Console::increaseIndention();        // call the debug method of the element    //    if (v_d[i] != (TObject*)NULL) {      v_d[i]->debug(L"");    }    Console::decreaseIndention();  }    // exit gracefully  //   return true;}//------------------------------------------------------------------------//// required destructor/constructor(s)////-----------------------------------------------------------------------// method: destructor//// arguments: none//// return: none//template<class TObject>PriorityQueue<TObject>::~PriorityQueue() {  // free memory  //  clear(Integral::RELEASE);}// method: default constructor//// arguments://  ALLOCATION alloc: (input) the flag to specify whether or not the item//                     memory is allocated by the node itself//// return: none//template<class TObject>PriorityQueue<TObject>::PriorityQueue(ALLOCATION alloc_a) {  // initialize data  //   length_d = (long)0;  capacity_d = (long)0;  v_d = (TObject**)NULL;    // set the allocation flag  //  alloc_d = alloc_a;}// method: copy constructor//// arguments://  const PriorityQueue<TObject>& copy_queue: (input) the queue to copy//// return: none//template<class TObject>PriorityQueue<TObject>::PriorityQueue(const PriorityQueue<TObject>& copy_queue_a) {  // initialize data  //   length_d = (long)0;  capacity_d = (long)0;  v_d = (TObject**)NULL;    // call the assign method to copy the queue  //  assign(copy_queue_a);}//------------------------------------------------------------------------//// required assign methods////-------------------------------------------------------------------------// method: assign//// arguments://  const PriorityQueue<TObject>& copy_queue: (input) the queue to copy//// return: a boolean value indicating status//// this method copies the contents of the input to this queue//template<class TObject>boolean PriorityQueue<TObject>::assign(const PriorityQueue<TObject>& copy_queue_a) {  // resize the vector  //   if (!setLength(copy_queue_a.length(), false)) {    return Error::handle(name(), L"assign", Error::NOMEM, __FILE__, __LINE__);  }    // copy the data  //   for (long index = 0; index < (long)length_d; index++) {    v_d[index] = accessByMode(copy_queue_a.v_d[index]);  }  // exit gracefully  //  return true;}//------------------------------------------------------------------------//// required equality methods////------------------------------------------------------------------------// method: eq//// arguments://  const PriorityQueue<TObject>& compare_queue: (input) the queue to compare//// return: a boolean value indicating status//// this method compares two queues for equivalence. two queues are equivalent// if all corresponding items are equivalent//template<class TObject>boolean PriorityQueue<TObject>::eq(const PriorityQueue<TObject>& compare_queue_a) const {    // declare the output variable  //  boolean are_equal = true;  // two PriorityQueues can not be equivalent if they are of differing lengths  //  if ((long)length_d != (long)compare_queue_a.length_d) {        // set the break flag    //    are_equal = false;  }  // loop over each element and see if each is equivalent  //  for (long i = 0; are_equal && (i < (long)length_d); i++) {        // see if the current items are equal    //    if (alloc_d == SYSTEM) {