cgma
PriorityQueue.cpp
Go to the documentation of this file.
00001 #include "cassert"
00002 #include "PriorityQueue.hpp"
00003 #include "CubitMessage.hpp"
00004 
00005 
00006 #ifdef INLINE_TEMPLATES
00007 #define MY_INLINE inline
00008 #else
00009 #define MY_INLINE
00010 #endif
00011 
00012 template <class Object> MY_INLINE
00013 PriorityQueue<Object>::PriorityQueue(typename PriorityQueue<Object>::CompareFunc compare)
00014     : theItems(1)
00015 {
00016   lessThanFunc = compare;
00017 }
00018 template <class Object> MY_INLINE
00019 int PriorityQueue<Object>::size() const
00020 {
00021   return theItems.size() - 1;
00022 }
00023 template <class Object> MY_INLINE
00024 bool PriorityQueue<Object>::empty() const
00025 {
00026   if ( size() == 0 )
00027     return true;
00028   else
00029     return false;
00030 }
00031 template <class Object> MY_INLINE
00032 const Object PriorityQueue<Object>::top() const
00033 {
00034   if ( empty() )
00035   {
00036     PRINT_ERROR("Empty priority queue had top request.\n");
00037     assert(!empty());
00038     return (Object)0;
00039   }
00040   return theItems[1];
00041 }
00042 template <class Object> MY_INLINE
00043 void PriorityQueue<Object>::push(Object x)
00044 {
00045   theItems.push_back(x);
00046   theItems[0] = x;//stash the item here...
00047     //Percolate up.
00048   int hole = size();
00049     //While x is less than the parrent, do (1): then go up the tree (hole /= 2 is the parent...).
00050   for ( ; lessThanFunc(x, theItems[hole/2]); hole /= 2 )
00051   {
00052       //(1) set the replace the parent with the child.
00053     theItems[hole] = theItems[hole/2];
00054   }
00055     //Now where the item is greater than the parent, set this value.
00056   theItems[hole] = x;
00057 }
00058 template <class Object> MY_INLINE
00059 void PriorityQueue<Object>::pop()
00060 {
00061   if ( empty() )
00062   {
00063     PRINT_ERROR("Trying to delete min from empty priority queue.\n");
00064     assert(!empty());
00065     return;
00066   }
00067 
00068   int hole = 1;
00069   int child;
00070 
00071   Object tmp = theItems.back();
00072   theItems.pop_back();
00073   int the_size = size();
00074     //while the current isn't at the end, do (1): then set hole to child.
00075   for ( ; hole*2 <= the_size; hole = child )
00076   {
00077     child = hole*2;
00078     if ( child != the_size &&
00079          lessThanFunc(theItems[child+1], theItems[child]) )
00080       child++;
00081     if ( lessThanFunc(theItems[child], tmp) )
00082       theItems[hole] = theItems[child];
00083     else
00084       break;
00085   }
00086   if ( !empty() )
00087     theItems[hole] = tmp;
00088 }
00089 
00090 template <class Object> MY_INLINE
00091 int PriorityQueue<Object>::where_is_item(Object &a, int start_index, bool queue_is_valid)
00092 {
00093   size_t i;
00094 
00095   if (!queue_is_valid)
00096   {
00097     for (i=0; i < theItems.size(); ++i)
00098     {
00099       if (theItems[i] == a) {return i;}
00100     }
00101     return -1;
00102   }
00103   
00104   if (a == theItems[start_index]) {return start_index;}
00105   if (!lessThanFunc(a, theItems[start_index]) && 2*start_index+1 <= size())
00106   {
00107     int result;
00108     result = where_is_item(a, 2*start_index);
00109     if (result > 0) {return result;}
00110     result = where_is_item(a, 2*start_index+1);
00111     if (result > 0) {return result;}
00112   }
00113   
00114   return -1;
00115 }
00116 
00117 template <class Object> MY_INLINE
00118 bool PriorityQueue<Object>::update_item(Object &a, bool queue_is_valid)
00119 {
00120   int index = where_is_item(a, queue_is_valid);
00121   if (index == -1) {return false;}
00122   else {return update_item(index);}
00123 }
00124 
00125 template <class Object> MY_INLINE
00126 bool PriorityQueue<Object>::update_item(int object_index)
00127 {
00128   if (object_index == 0) {return true;}
00129   
00130   if (lessThanFunc(theItems[object_index], theItems[object_index/2]))
00131   {
00132     Object temp = theItems[object_index];
00133     theItems[object_index] = theItems[object_index/2];
00134     theItems[object_index/2] = temp;
00135     update_item(object_index/2);
00136     return true;
00137   }
00138 
00139   int smaller_child = 2*object_index;
00140   if (2*object_index > size()) {return true;}
00141   if (2*object_index+1 <= size())
00142   {
00143     if (lessThanFunc(theItems[2*object_index+1],theItems[2*object_index])) {++smaller_child;}
00144   }
00145   
00146   if (lessThanFunc(theItems[smaller_child], theItems[object_index]))
00147   {
00148     Object temp = theItems[object_index];
00149     theItems[object_index] = theItems[smaller_child];
00150     theItems[smaller_child] = temp;
00151     update_item(smaller_child);
00152   }
00153 
00154   return true;
00155 }
00156 
00157 template <class Object> MY_INLINE
00158 bool PriorityQueue<Object>::validate(int index)
00159 {
00160   bool fine = true, kid_one = false, kid_two = false;
00161   if  (2*index <= size())
00162   {
00163     kid_one = true;
00164     if ((lessThanFunc(theItems[2*index], theItems[index])))
00165     {
00166       fine = false;
00167     }
00168   }
00169   
00170   if  (2*index+1 <= size())
00171   {
00172     kid_two = true;
00173     if ((lessThanFunc(theItems[2*index+1], theItems[index])))
00174     {
00175       fine = false;
00176     }
00177   }
00178   
00179   if (fine)
00180   {
00181     if (kid_one && !kid_two) {return validate(2*index);}
00182     if (!kid_one && kid_two) {return validate(2*index+1);}
00183     if (kid_one && kid_two) {return (validate(2*index) && validate(2*index+1));}
00184     else {return true;}
00185   }
00186   
00187   return false;
00188   
00189 }
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines