COPASI API  4.16.103
Public Member Functions | Private Member Functions | Private Attributes | Friends | List of all members
CIndexedPriorityQueue Class Reference

#include <CIndexedPriorityQueue.h>

Collaboration diagram for CIndexedPriorityQueue:
Collaboration graph
[legend]

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< PQNodemHeap
 
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.

28 {}
CIndexedPriorityQueue::~CIndexedPriorityQueue ( )

Destructor

Definition at line 30 of file CIndexedPriorityQueue.cpp.

31 {}

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().

128 {
129  for (size_t i = mHeap.size() / 2 - 1; i != C_INVALID_INDEX; i--)
130  {
131  heapify(i);
132  }
133 }
#define C_INVALID_INDEX
Definition: copasi.h:222
std::vector< PQNode > mHeap
void heapify(const size_t pos)
void CIndexedPriorityQueue::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().

173  {
174  // does not consider negative IndexPointer
175  return mHeap[mIndexPointer[index]].mKey;
176  }
std::vector< size_t > mIndexPointer
std::vector< PQNode > mHeap
void CIndexedPriorityQueue::heapify ( const size_t  pos)
private

Make a tree rooted at a given position into a heap

Parameters
posThe 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().

165 {
166  size_t left = leftChild(current);
167  size_t right = rightChild(current);
168  size_t highest_priority = current;
169 
170  // cout << "Heapifying " << current << "(Currently " << mHeap[current].mKey << ")" << endl;
171  if ((static_cast<unsigned int>(left) < mHeap.size()) && (mHeap[left].mKey < mHeap[current].mKey))
172  {
173  highest_priority = left;
174  }
175 
176  if ((static_cast<unsigned int>(right) < mHeap.size()) && (mHeap[right].mKey < mHeap[highest_priority].mKey))
177  {
178  highest_priority = right;
179  }
180 
181  if (highest_priority != current)
182  {
183  swapNodes(current, highest_priority);
184  heapify(highest_priority);
185  }
186 }
std::vector< PQNode > mHeap
size_t leftChild(const size_t pos) const
void heapify(const size_t pos)
void swapNodes(const size_t index1, const size_t index2)
size_t rightChild(const size_t pos) const
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().

93 {
94  size_t i;
95 
96  for (i = 0; i < numberOfReactions; i++)
97  {
98  mIndexPointer.push_back(C_INVALID_INDEX);
99  }
100 }
std::vector< size_t > mIndexPointer
#define C_INVALID_INDEX
Definition: copasi.h:222
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().

69 {
70  size_t pos;
71 
72  // check if index is valid
73  if (index >= mIndexPointer.size()) return - 1;
74 
75  // first the node is inserted at the end of the heap
76  mIndexPointer[index] = mHeap.size();
77  PQNode heap_node(index, key);
78  mHeap.push_back(heap_node);
79  // bubble the node up the tree to the right position !
80  pos = mIndexPointer[index];
81 
82  while ((pos > 0) && (mHeap[parent(pos)].mKey > key))
83  {
84  swapNodes(pos, parent(pos));
85  pos = parent(pos);
86  }
87 
88  return 0;
89 }
std::vector< size_t > mIndexPointer
std::vector< PQNode > mHeap
void swapNodes(const size_t index1, const size_t index2)
size_t parent(const size_t pos) const
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
posThe current node position
Returns
The left child position

Definition at line 216 of file CIndexedPriorityQueue.h.

Referenced by heapify(), and updateAux().

216 {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.

162  {
163  return mHeap[pos].mKey;
164  }
std::vector< PQNode > mHeap
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
posThe current node position
Returns
The parent node position

Definition at line 209 of file CIndexedPriorityQueue.h.

Referenced by insertStochReaction(), and updateAux().

209 {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
indexThe index used to access the node
keyThe 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().

103 {
104  // Add an element to the priority queue. This merely pushes an item onto
105  // the back of the vector corresponding to the heap, and pushes the index
106  // onto the back of the vector corresponding to the index structure.
107  // Implicit is the assumption that this is done in contiguous ascending order
108  // for the index; i.e. in index order 0,1,2,3...
109  // N.B. The structures are not yet ordered as an indexed priority queue; this must
110  // be done using the buildHeap() method
111 
112  // First check that the index corresponds to the heap size before insertion
113  if (static_cast<unsigned int>(index) != mHeap.size())
114  {
115  CCopasiMessage(CCopasiMessage::ERROR, "Error inserting pair into priority queue");
116  return - 1;
117  }
118 
119  PQNode heap_node(index, key);
120  mHeap.push_back(heap_node);
121  // at first, position == index
122  size_t position = index; // for clarity
123  mIndexPointer.push_back(position);
124  return 0;
125 }
std::vector< size_t > mIndexPointer
std::vector< PQNode > mHeap
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().

45 {
46  size_t t;
47 
48  // check if index is valid
49  if (index >= mIndexPointer.size()) return C_INVALID_INDEX;
50 
51  if ((mIndexPointer[index] != C_INVALID_INDEX) && (mIndexPointer[index] != (mHeap.size() - 1))) // if the node with the given index exists in the tree
52  {// remove the node with the given index from the tree
53  swapNodes(t = mIndexPointer[index], mHeap.size() - 1);
54  mHeap.pop_back();
55  mIndexPointer[index] = -1;
56  heapify(t);
57  }
58  else if (mIndexPointer[index] == (mHeap.size() - 1)) // last node in the heap
59  {
60  mHeap.pop_back();
61  mIndexPointer[index] = -1;
62  }
63 
64  return 0;
65 }
std::vector< size_t > mIndexPointer
#define C_INVALID_INDEX
Definition: copasi.h:222
std::vector< PQNode > mHeap
void heapify(const size_t pos)
void swapNodes(const size_t index1, const size_t index2)
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
posThe current node position
Returns
The right child position

Definition at line 223 of file CIndexedPriorityQueue.h.

Referenced by heapify(), and updateAux().

223 {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().

134 {return mHeap.size();}
std::vector< PQNode > mHeap
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().

147 {
148  // cout << "Swapping node " << pos1 << "(" << mHeap[pos1].mKey << ") with node ";
149  // cout << pos2 << "(" << mHeap[pos2].mKey << ")\n";
150  C_FLOAT64 tempkey = mHeap[pos1].mKey;
151  size_t index1 = mHeap[pos1].mIndex;
152  size_t index2 = mHeap[pos2].mIndex;
153  // Put the contents of the node at pos2 into the node at pos1
154  mHeap[pos1].mIndex = index2;
155  mHeap[pos1].mKey = mHeap[pos2].mKey;
156  // Put the contents formerly in the node at pos1 into the node at pos2
157  mHeap[pos2].mIndex = index1;
158  mHeap[pos2].mKey = tempkey;
159  // Swap the pointers in the index vector
160  mIndexPointer[index1] = pos2;
161  mIndexPointer[index2] = pos1;
162 }
std::vector< size_t > mIndexPointer
std::vector< PQNode > mHeap
#define C_FLOAT64
Definition: copasi.h:92
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().

39 {
40  return mHeap[0].mIndex;
41 }
std::vector< PQNode > mHeap
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().

34 {
35  return mHeap[0].mKey;
36 }
std::vector< PQNode > mHeap
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().

189 {
190  size_t parent_pos = parent(pos);
191  C_FLOAT64 keyval = mHeap[pos].mKey;
192 
193  if (parent_pos != C_INVALID_INDEX &&
194  keyval < mHeap[parent_pos].mKey)
195  {
196  swapNodes(pos, parent_pos);
197  updateAux(parent_pos);
198  }
199  else
200  {
201  size_t left = leftChild(pos);
202  size_t right = rightChild(pos);
203  C_FLOAT64 min = 0.0;
204  size_t min_pos = 0;
205 
206  if (left < mHeap.size())
207  {
208  min = mHeap[left].mKey;
209  min_pos = left;
210  }
211 
212  C_FLOAT64 val; // = mHeap[right].mKey; //!!!
213 
214  if ((right < mHeap.size()) && ((val = mHeap[right].mKey) < min))
215  {
216  min = val;
217  min_pos = right;
218  }
219 
220  if ((min_pos > 0) && (keyval > min))
221  {
222  // swapNodes(mHeap[pos].mIndex, min_pos);
223  swapNodes(pos, min_pos);
224  updateAux(min_pos);
225  }
226  }
227 }
#define C_INVALID_INDEX
Definition: copasi.h:222
std::vector< PQNode > mHeap
size_t leftChild(const size_t pos) const
void updateAux(const size_t position)
#define C_FLOAT64
Definition: copasi.h:92
void swapNodes(const size_t index1, const size_t index2)
size_t rightChild(const size_t pos) const
size_t parent(const size_t pos) const
#define min(a, b)
Definition: f2c.h:175
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
indexThe index used to access the node
keyThe 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().

139 {
140  size_t pos = mIndexPointer[index];
141  // cout << "Setting heap at " << pos << " to be " << new_key << endl;
142  mHeap[pos].mKey = new_key;
143  updateAux(pos);
144 }
std::vector< size_t > mIndexPointer
std::vector< PQNode > mHeap
void updateAux(const size_t position)

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.

287 {
288  size_t i;
289 
290  os << "PQ: " << std::endl;
291 
292  std::vector <PQNode>::const_iterator it;
293  os << " mHeap: " << std::endl;
294 
295  for (it = d.mHeap.begin(); it != d.mHeap.end(); it++)
296  os << *it << std::endl;
297 
298  os << " mIndexPointer: " << std::endl;
299 
300  for (i = 0; i < d.mIndexPointer.size(); i++)
301  os << d.mIndexPointer[i] << " ";
302 
303  os << std::endl;
304 
305  os << std::endl;
306 
307  return os;
308 }
std::vector< size_t > mIndexPointer
std::vector< PQNode > mHeap

Member Data Documentation

std::vector<PQNode> CIndexedPriorityQueue::mHeap
private
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: