|
cgma
|
#include <PriorityQueue.hpp>
Public Types | |
| typedef bool(* | CompareFunc )(Object &a, Object &b) |
Public Member Functions | |
| PriorityQueue (CompareFunc compare) | |
| int | size () const |
| bool | empty () const |
| const Object | top () const |
| void | push (Object x) |
| void | pop () |
| int | where_is_item (Object &a, int start_index=1, bool queue_is_valid=false) |
| bool | update_item (Object &a, bool queue_is_valid=false) |
| bool | update_item (int object_index) |
| bool | validate (int index=1) |
Private Attributes | |
| std::vector< Object > | theItems |
| CompareFunc | lessThanFunc |
Definition at line 6 of file PriorityQueue.hpp.
| typedef bool(* PriorityQueue< Object >::CompareFunc)(Object &a, Object &b) |
Definition at line 9 of file PriorityQueue.hpp.
| MY_INLINE PriorityQueue< Object >::PriorityQueue | ( | CompareFunc | compare | ) |
Definition at line 13 of file PriorityQueue.cpp.
: theItems(1) { lessThanFunc = compare; }
| MY_INLINE bool PriorityQueue< Object >::empty | ( | ) | const |
Definition at line 24 of file PriorityQueue.cpp.
{
if ( size() == 0 )
return true;
else
return false;
}
| MY_INLINE void PriorityQueue< Object >::pop | ( | ) |
Definition at line 59 of file PriorityQueue.cpp.
{
if ( empty() )
{
PRINT_ERROR("Trying to delete min from empty priority queue.\n");
assert(!empty());
return;
}
int hole = 1;
int child;
Object tmp = theItems.back();
theItems.pop_back();
int the_size = size();
//while the current isn't at the end, do (1): then set hole to child.
for ( ; hole*2 <= the_size; hole = child )
{
child = hole*2;
if ( child != the_size &&
lessThanFunc(theItems[child+1], theItems[child]) )
child++;
if ( lessThanFunc(theItems[child], tmp) )
theItems[hole] = theItems[child];
else
break;
}
if ( !empty() )
theItems[hole] = tmp;
}
| MY_INLINE void PriorityQueue< Object >::push | ( | Object | x | ) |
Definition at line 43 of file PriorityQueue.cpp.
{
theItems.push_back(x);
theItems[0] = x;//stash the item here...
//Percolate up.
int hole = size();
//While x is less than the parrent, do (1): then go up the tree (hole /= 2 is the parent...).
for ( ; lessThanFunc(x, theItems[hole/2]); hole /= 2 )
{
//(1) set the replace the parent with the child.
theItems[hole] = theItems[hole/2];
}
//Now where the item is greater than the parent, set this value.
theItems[hole] = x;
}
| MY_INLINE int PriorityQueue< Object >::size | ( | ) | const |
Definition at line 19 of file PriorityQueue.cpp.
{
return theItems.size() - 1;
}
| MY_INLINE const Object PriorityQueue< Object >::top | ( | ) | const |
Definition at line 32 of file PriorityQueue.cpp.
{
if ( empty() )
{
PRINT_ERROR("Empty priority queue had top request.\n");
assert(!empty());
return (Object)0;
}
return theItems[1];
}
| MY_INLINE bool PriorityQueue< Object >::update_item | ( | Object & | a, |
| bool | queue_is_valid = false |
||
| ) |
Definition at line 118 of file PriorityQueue.cpp.
{
int index = where_is_item(a, queue_is_valid);
if (index == -1) {return false;}
else {return update_item(index);}
}
| MY_INLINE bool PriorityQueue< Object >::update_item | ( | int | object_index | ) |
Definition at line 126 of file PriorityQueue.cpp.
{
if (object_index == 0) {return true;}
if (lessThanFunc(theItems[object_index], theItems[object_index/2]))
{
Object temp = theItems[object_index];
theItems[object_index] = theItems[object_index/2];
theItems[object_index/2] = temp;
update_item(object_index/2);
return true;
}
int smaller_child = 2*object_index;
if (2*object_index > size()) {return true;}
if (2*object_index+1 <= size())
{
if (lessThanFunc(theItems[2*object_index+1],theItems[2*object_index])) {++smaller_child;}
}
if (lessThanFunc(theItems[smaller_child], theItems[object_index]))
{
Object temp = theItems[object_index];
theItems[object_index] = theItems[smaller_child];
theItems[smaller_child] = temp;
update_item(smaller_child);
}
return true;
}
| MY_INLINE bool PriorityQueue< Object >::validate | ( | int | index = 1 | ) |
Definition at line 158 of file PriorityQueue.cpp.
{
bool fine = true, kid_one = false, kid_two = false;
if (2*index <= size())
{
kid_one = true;
if ((lessThanFunc(theItems[2*index], theItems[index])))
{
fine = false;
}
}
if (2*index+1 <= size())
{
kid_two = true;
if ((lessThanFunc(theItems[2*index+1], theItems[index])))
{
fine = false;
}
}
if (fine)
{
if (kid_one && !kid_two) {return validate(2*index);}
if (!kid_one && kid_two) {return validate(2*index+1);}
if (kid_one && kid_two) {return (validate(2*index) && validate(2*index+1));}
else {return true;}
}
return false;
}
| MY_INLINE int PriorityQueue< Object >::where_is_item | ( | Object & | a, |
| int | start_index = 1, |
||
| bool | queue_is_valid = false |
||
| ) |
Definition at line 91 of file PriorityQueue.cpp.
{
size_t i;
if (!queue_is_valid)
{
for (i=0; i < theItems.size(); ++i)
{
if (theItems[i] == a) {return i;}
}
return -1;
}
if (a == theItems[start_index]) {return start_index;}
if (!lessThanFunc(a, theItems[start_index]) && 2*start_index+1 <= size())
{
int result;
result = where_is_item(a, 2*start_index);
if (result > 0) {return result;}
result = where_is_item(a, 2*start_index+1);
if (result > 0) {return result;}
}
return -1;
}
CompareFunc PriorityQueue< Object >::lessThanFunc [private] |
Definition at line 26 of file PriorityQueue.hpp.
std::vector<Object> PriorityQueue< Object >::theItems [private] |
Definition at line 25 of file PriorityQueue.hpp.
1.7.6.1