cgma
PriorityQueue< Object > Class Template Reference

#include <PriorityQueue.hpp>

List of all members.

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

Detailed Description

template<class Object>
class PriorityQueue< Object >

Definition at line 6 of file PriorityQueue.hpp.


Member Typedef Documentation

template<class Object>
typedef bool(* PriorityQueue< Object >::CompareFunc)(Object &a, Object &b)

Definition at line 9 of file PriorityQueue.hpp.


Constructor & Destructor Documentation

template<class Object>
MY_INLINE PriorityQueue< Object >::PriorityQueue ( CompareFunc  compare)

Definition at line 13 of file PriorityQueue.cpp.

    : theItems(1)
{
  lessThanFunc = compare;
}

Member Function Documentation

template<class Object >
MY_INLINE bool PriorityQueue< Object >::empty ( ) const

Definition at line 24 of file PriorityQueue.cpp.

{
  if ( size() == 0 )
    return true;
  else
    return false;
}
template<class Object >
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;
}
template<class Object >
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;
}
template<class Object >
MY_INLINE int PriorityQueue< Object >::size ( ) const

Definition at line 19 of file PriorityQueue.cpp.

{
  return theItems.size() - 1;
}
template<class Object >
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];
}
template<class Object >
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);}
}
template<class Object >
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;
}
template<class Object >
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;
  
}
template<class Object >
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;
}

Member Data Documentation

template<class Object>
CompareFunc PriorityQueue< Object >::lessThanFunc [private]

Definition at line 26 of file PriorityQueue.hpp.

template<class Object>
std::vector<Object> PriorityQueue< Object >::theItems [private]

Definition at line 25 of file PriorityQueue.hpp.


The documentation for this class was generated from the following files:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines