CIndexedPriorityQueue Class Reference

#include <CIndexedPriorityQueue.h>

Collaboration diagram for CIndexedPriorityQueue:

Public Member Functions
void	buildHeap ()
	CIndexedPriorityQueue ()
void	clear ()
C_FLOAT64	getKey (const size_t index) const
void	initializeIndexPointer (const size_t numberOfReactions)
size_t	insertStochReaction (const size_t index, const C_FLOAT64 key)
C_FLOAT64	operator[] (const size_t pos) const
size_t	pushPair (const size_t index, const C_FLOAT64 key)
size_t	removeStochReaction (const size_t index)
size_t	size () const
size_t	topIndex () const
C_FLOAT64	topKey () const
void	updateNode (const size_t index, const C_FLOAT64 key)
	~CIndexedPriorityQueue ()

Private Member Functions
void	heapify (const size_t pos)
size_t	leftChild (const size_t pos) const
size_t	parent (const size_t pos) const
size_t	rightChild (const size_t pos) const
void	swapNodes (const size_t index1, const size_t index2)
void	updateAux (const size_t position)

Private Attributes
std::vector< PQNode >	mHeap
std::vector< size_t >	mIndexPointer

Friends
std::ostream &	operator<< (std::ostream &os, const CIndexedPriorityQueue &d)

Detailed Description

The CIndexedPriorityQueue class provides an indexed priority queue. Each element consistes of a pair of values, a key and an index.

The elements in the queue are ordered according to the value of their key. Since for stochastic simulations the minimum time is required, the queue is ordered so that the element with the minimum key value is at the top. This is the opposite of the normal ordering of priority queues.

The index can be used to access elements from positions other than at the front of the queue.

The indexed priority queue as applied to stochastic simulations is described in "Efficient Exact Stochastic Simulation of Chemical Systems with Many Species and Many Channels", Gibson and Bruck, J. Phys. Chem. A 104 (2000) 1876-1889

Definition at line 78 of file CIndexedPriorityQueue.h.

Constructor & Destructor Documentation

CIndexedPriorityQueue::CIndexedPriorityQueue

(

)

Constructor

Definition at line 27 of file CIndexedPriorityQueue.cpp.

{}

CIndexedPriorityQueue::~CIndexedPriorityQueue

(

)

Destructor

Definition at line 30 of file CIndexedPriorityQueue.cpp.

{}

Member Function Documentation

void CIndexedPriorityQueue::buildHeap

(

)

Build moves entries until the correct ordering is achieved.

Definition at line 127 of file CIndexedPriorityQueue.cpp.

References C_INVALID_INDEX, heapify(), and mHeap.

Referenced by CStochNextReactionMethod::setupPriorityQueue().

{
  for (size_t i = mHeap.size() / 2 - 1; i != C_INVALID_INDEX; i--)
    {
      heapify(i);
    }
}

void CIndexedPriorityQueue::clear

(

)

Definition at line 135 of file CIndexedPriorityQueue.cpp.

References mHeap, and mIndexPointer.

Referenced by CStochNextReactionMethod::setupPriorityQueue(), CHybridMethodODE45::setupPriorityQueue(), CHybridMethod::setupPriorityQueue(), and CHybridMethodLSODA::setupPriorityQueue().

{mHeap.clear(); mIndexPointer.clear();}

C_FLOAT64 CIndexedPriorityQueue::getKey ( const size_t  index ) const

inline

gets the key from a given index

Returns

Returns the key

Definition at line 172 of file CIndexedPriorityQueue.h.

References mHeap, and mIndexPointer.

Referenced by CStochNextReactionMethod::updatePriorityQueue(), CHybridMethod::updateTauMu(), CHybridMethodLSODA::updateTauMu(), and CHybridMethodODE45::updateTauMu().

  {
    // does not consider negative IndexPointer
    return mHeap[mIndexPointer[index]].mKey;
  }

void CIndexedPriorityQueue::heapify ( const size_t  pos )

private

Make a tree rooted at a given position into a heap

Parameters

pos	The root position of the tree to heapify

Definition at line 164 of file CIndexedPriorityQueue.cpp.

References leftChild(), mHeap, rightChild(), and swapNodes().

Referenced by buildHeap(), and removeStochReaction().

{
  size_t left = leftChild(current);
  size_t right = rightChild(current);
  size_t highest_priority = current;

  //    cout << "Heapifying " << current << "(Currently " << mHeap[current].mKey << ")" << endl;
  if ((static_cast<unsigned int>(left) < mHeap.size()) && (mHeap[left].mKey < mHeap[current].mKey))
    {
      highest_priority = left;
    }

  if ((static_cast<unsigned int>(right) < mHeap.size()) && (mHeap[right].mKey < mHeap[highest_priority].mKey))
    {
      highest_priority = right;
    }

  if (highest_priority != current)
    {
      swapNodes(current, highest_priority);
      heapify(highest_priority);
    }
}

void CIndexedPriorityQueue::initializeIndexPointer

(

const size_t

numberOfReactions

)

Initializes the vector mIndexPointer. The vector will be <numberOfReactions> long and every pointer will be -1, because none of the nodes can be found in the tree so far. Insert the stochastic reactions into the tree with insertStochReaction()

added by juergen 26 July, 2002

Definition at line 92 of file CIndexedPriorityQueue.cpp.

References C_INVALID_INDEX, and mIndexPointer.

Referenced by CHybridMethodODE45::setupPriorityQueue(), CHybridMethod::setupPriorityQueue(), and CHybridMethodLSODA::setupPriorityQueue().

{
  size_t i;

  for (i = 0; i < numberOfReactions; i++)
    {
      mIndexPointer.push_back(C_INVALID_INDEX);
    }
}

size_t CIndexedPriorityQueue::insertStochReaction	(	const size_t	index,
		const C_FLOAT64	key
	)

Inserts the node with the given index and key into the tree. The index has to exist in the index array of course.

added by juergen 26 July, 2002

Definition at line 68 of file CIndexedPriorityQueue.cpp.

References mHeap, mIndexPointer, parent(), and swapNodes().

Referenced by CHybridMethod::partitionSystem(), CHybridMethodLSODA::partitionSystem(), CHybridMethodODE45::setupPriorityQueue(), CHybridMethod::setupPriorityQueue(), and CHybridMethodLSODA::setupPriorityQueue().

{
  size_t pos;

  // check if index is valid
  if (index >= mIndexPointer.size()) return - 1;

  // first the node is inserted at the end of the heap
  mIndexPointer[index] = mHeap.size();
  PQNode heap_node(index, key);
  mHeap.push_back(heap_node);
  // bubble the node up the tree to the right position !
  pos = mIndexPointer[index];

  while ((pos > 0) && (mHeap[parent(pos)].mKey > key))
    {
      swapNodes(pos, parent(pos));
      pos = parent(pos);
    }

  return 0;
}

size_t CIndexedPriorityQueue::leftChild ( const size_t  pos ) const

inlineprivate

Provide the position in the heap of the left child of the current node.

Parameters

pos	The current node position

Returns

The left child position

Definition at line 216 of file CIndexedPriorityQueue.h.

Referenced by heapify(), and updateAux().

{return 2*pos + 1;}

C_FLOAT64 CIndexedPriorityQueue::operator[] ( const size_t  pos ) const

inline

Overloads the [] operator. Gives the index´th element on the heap

Returns

Returns the key

Definition at line 161 of file CIndexedPriorityQueue.h.

References mHeap.

  {
    return mHeap[pos].mKey;
  }

size_t CIndexedPriorityQueue::parent ( const size_t  pos ) const

inlineprivate

Provide the position in the heap of the parent to a node. The positions are numbered from zero; a parent position less than zero implies that the current node is already at the top of the tree.

Parameters

pos	The current node position

Returns

The parent node position

Definition at line 209 of file CIndexedPriorityQueue.h.

Referenced by insertStochReaction(), and updateAux().

{return (pos + 1) / 2 - 1;}

size_t CIndexedPriorityQueue::pushPair	(	const size_t	index,
		const C_FLOAT64	key
	)

Push an index/key pair onto the queue

Parameters

index	The index used to access the node
key	The key value used to determine the priority

Definition at line 102 of file CIndexedPriorityQueue.cpp.

References CCopasiMessage::ERROR, mHeap, and mIndexPointer.

Referenced by CStochNextReactionMethod::setupPriorityQueue().

{
  // Add an element to the priority queue. This merely pushes an item onto
  // the back of the vector corresponding to the heap, and pushes the index
  // onto the back of the vector corresponding to the index structure.
  // Implicit is the assumption that this is done in contiguous ascending order
  // for the index; i.e. in index order 0,1,2,3...
  // N.B. The structures are not yet ordered as an indexed priority queue; this must
  // be done using the buildHeap() method

  // First check that the index corresponds to the heap size before insertion
  if (static_cast<unsigned int>(index) != mHeap.size())
    {
      CCopasiMessage(CCopasiMessage::ERROR, "Error inserting pair into priority queue");
      return - 1;
    }

  PQNode heap_node(index, key);
  mHeap.push_back(heap_node);
  // at first, position == index
  size_t position = index; // for clarity
  mIndexPointer.push_back(position);
  return 0;
}

size_t CIndexedPriorityQueue::removeStochReaction

(

const size_t

index

)

Deletes the node in the tree with the given index. The pointer in the index array is removed.

added by juergen 26 July, 2002

Definition at line 44 of file CIndexedPriorityQueue.cpp.

References C_INVALID_INDEX, heapify(), mHeap, mIndexPointer, and swapNodes().

Referenced by CHybridMethod::partitionSystem(), and CHybridMethodLSODA::partitionSystem().

{
  size_t t;

  // check if index is valid
  if (index >= mIndexPointer.size()) return C_INVALID_INDEX;

  if ((mIndexPointer[index] != C_INVALID_INDEX) && (mIndexPointer[index] != (mHeap.size() - 1))) // if the node with the given index exists in the tree
    {// remove the node with the given index from the tree
      swapNodes(t = mIndexPointer[index], mHeap.size() - 1);
      mHeap.pop_back();
      mIndexPointer[index] = -1;
      heapify(t);
    }
  else if (mIndexPointer[index] == (mHeap.size() - 1)) // last node in the heap
    {
      mHeap.pop_back();
      mIndexPointer[index] = -1;
    }

  return 0;
}

size_t CIndexedPriorityQueue::rightChild ( const size_t  pos ) const

inlineprivate

Provide the position in the heap of the right child of the current node.

Parameters

pos	The current node position

Returns

The right child position

Definition at line 223 of file CIndexedPriorityQueue.h.

Referenced by heapify(), and updateAux().

{return 2*pos + 2;}

size_t CIndexedPriorityQueue::size ( ) const

inline

Return the size of the heap

Definition at line 134 of file CIndexedPriorityQueue.h.

References mHeap.

Referenced by CHybridNextReactionLSODAMethod::doSingleStep(), and CHybridNextReactionRKMethod::doSingleStep().

{return mHeap.size();}

void CIndexedPriorityQueue::swapNodes ( const size_t  index1, const size_t  index2  )

private

Swap a pair of nodes and update the index structure accordingly.

Definition at line 146 of file CIndexedPriorityQueue.cpp.

References C_FLOAT64, mHeap, and mIndexPointer.

Referenced by heapify(), insertStochReaction(), removeStochReaction(), and updateAux().

{
  //    cout << "Swapping node " << pos1 << "(" << mHeap[pos1].mKey << ") with node ";
  //    cout << pos2 << "(" << mHeap[pos2].mKey << ")\n";
  C_FLOAT64 tempkey = mHeap[pos1].mKey;
  size_t index1 = mHeap[pos1].mIndex;
  size_t index2 = mHeap[pos2].mIndex;
  // Put the contents of the node at pos2 into the node at pos1
  mHeap[pos1].mIndex = index2;
  mHeap[pos1].mKey = mHeap[pos2].mKey;
  // Put the contents formerly in the node at pos1 into the node at pos2
  mHeap[pos2].mIndex = index1;
  mHeap[pos2].mKey = tempkey;
  // Swap the pointers in the index vector
  mIndexPointer[index1] = pos2;
  mIndexPointer[index2] = pos1;
}

size_t CIndexedPriorityQueue::topIndex

(

)

const

Get the index associated with the highest priority node

Returns

The index

Definition at line 38 of file CIndexedPriorityQueue.cpp.

References mHeap.

Referenced by CStochNextReactionMethod::doSingleStep(), CHybridMethod::getStochTimeAndIndex(), CHybridMethodLSODA::getStochTimeAndIndex(), and CHybridMethodODE45::getStochTimeAndIndex().

{
  return mHeap[0].mIndex;
}

C_FLOAT64 CIndexedPriorityQueue::topKey

(

)

const

Get the key value associated with the highest priority node

Returns

The key value

Definition at line 33 of file CIndexedPriorityQueue.cpp.

References mHeap.

Referenced by CStochNextReactionMethod::doSingleStep(), CHybridMethod::getStochTimeAndIndex(), CHybridMethodLSODA::getStochTimeAndIndex(), and CHybridMethodODE45::getStochTimeAndIndex().

{
  return mHeap[0].mKey;
}

void CIndexedPriorityQueue::updateAux ( const size_t  position )

private

Used by the updateNode function. Update the node at a given position.

Definition at line 188 of file CIndexedPriorityQueue.cpp.

References C_FLOAT64, C_INVALID_INDEX, leftChild(), mHeap, min, parent(), rightChild(), and swapNodes().

Referenced by updateNode().

{
  size_t parent_pos = parent(pos);
  C_FLOAT64 keyval = mHeap[pos].mKey;

  if (parent_pos != C_INVALID_INDEX &&
      keyval < mHeap[parent_pos].mKey)
    {
      swapNodes(pos, parent_pos);
      updateAux(parent_pos);
    }
  else
    {
      size_t left = leftChild(pos);
      size_t right = rightChild(pos);
      C_FLOAT64 min = 0.0;
      size_t min_pos = 0;

      if (left < mHeap.size())
        {
          min = mHeap[left].mKey;
          min_pos = left;
        }

      C_FLOAT64 val; // = mHeap[right].mKey; //!!!

      if ((right < mHeap.size()) && ((val = mHeap[right].mKey) < min))
        {
          min = val;
          min_pos = right;
        }

      if ((min_pos > 0) && (keyval > min))
        {
          //            swapNodes(mHeap[pos].mIndex, min_pos);
          swapNodes(pos, min_pos);
          updateAux(min_pos);
        }
    }
}

void CIndexedPriorityQueue::updateNode	(	const size_t	index,
		const C_FLOAT64	key
	)

Update the key value of a node at a given index. This also moves the node to the correct position if neccessary.

Parameters

index	The index used to access the node
key	The key value used to determine the priority

Definition at line 138 of file CIndexedPriorityQueue.cpp.

References mHeap, mIndexPointer, and updateAux().

Referenced by CStochNextReactionMethod::updatePriorityQueue(), CHybridMethod::updatePriorityQueue(), CHybridMethodLSODA::updatePriorityQueue(), CHybridMethodODE45::updatePriorityQueue(), CHybridMethod::updateTauMu(), CHybridMethodLSODA::updateTauMu(), and CHybridMethodODE45::updateTauMu().

{
  size_t pos = mIndexPointer[index];
  //    cout << "Setting heap at " << pos << " to be " << new_key << endl;
  mHeap[pos].mKey = new_key;
  updateAux(pos);
}

Friends And Related Function Documentation

std::ostream& operator<< ( std::ostream &  os, const CIndexedPriorityQueue &  d  )

friend

insert operator

Definition at line 286 of file CIndexedPriorityQueue.cpp.

{
  size_t i;

  os << "PQ: " << std::endl;

  std::vector <PQNode>::const_iterator it;
  os << "  mHeap: " << std::endl;

  for (it = d.mHeap.begin(); it != d.mHeap.end(); it++)
    os << *it << std::endl;

  os << "  mIndexPointer: " << std::endl;

  for (i = 0; i < d.mIndexPointer.size(); i++)
    os << d.mIndexPointer[i] << " ";

  os << std::endl;

  os << std::endl;

  return os;
}

Member Data Documentation

std::vector<PQNode> CIndexedPriorityQueue::mHeap

private

The vector which stores the heap

Definition at line 230 of file CIndexedPriorityQueue.h.

Referenced by buildHeap(), clear(), getKey(), heapify(), insertStochReaction(), operator<<(), operator[](), pushPair(), removeStochReaction(), size(), swapNodes(), topIndex(), topKey(), updateAux(), and updateNode().

std::vector<size_t> CIndexedPriorityQueue::mIndexPointer

private

The vector which stores a pointer to each indexed node on the heap

Definition at line 234 of file CIndexedPriorityQueue.h.

Referenced by clear(), getKey(), initializeIndexPointer(), insertStochReaction(), operator<<(), pushPair(), removeStochReaction(), swapNodes(), and updateNode().

---

The documentation for this class was generated from the following files:

• CIndexedPriorityQueue.h
• CIndexedPriorityQueue.cpp