COPASI API  4.16.103
CIndexedPriorityQueue.h
Go to the documentation of this file.
1 /* Begin CVS Header
2  $Source: /Volumes/Home/Users/shoops/cvs/copasi_dev/copasi/utilities/CIndexedPriorityQueue.h,v $
3  $Revision: 1.18 $
4  $Name: $
5  $Author: shoops $
6  $Date: 2011/03/07 19:34:54 $
7  End CVS Header */
8 
9 // Copyright (C) 2011 - 2010 by Pedro Mendes, Virginia Tech Intellectual
10 // Properties, Inc., University of Heidelberg, and The University
11 // of Manchester.
12 // All rights reserved.
13 
14 // Copyright (C) 2001 - 2007 by Pedro Mendes, Virginia Tech Intellectual
15 // Properties, Inc. and EML Research, gGmbH.
16 // All rights reserved.
17 
18 #ifndef COPASI_CPriorityQueue
19 #define COPASI_CPriorityQueue
20 
21 #include <queue>
22 #include <utility>
23 
25 
26 /**
27  * The PQNode class contains two members, an integer to represent the index,
28  * and a double to represent the key.
29  * The heap structure of the indexed priority queue class is implemented as
30  * a vector of PQNode.
31  */
32 
33 class PQNode
34 {
35  friend class CIndexedPriorityQueue;
36 
37 public:
38  /**
39  * Construct a PQNode with the given index and key
40  * @param idx The index
41  * @param key The key
42  */
43  PQNode(size_t idx, C_FLOAT64 key) : mIndex(idx), mKey(key) {}
44 
45  /**
46  * insert operator
47  */
48  friend std::ostream & operator<<(std::ostream &os, const PQNode & d);
49 
50 private:
51  /**
52  * The index value
53  */
54  size_t mIndex;
55  /**
56  * The key value
57  */
59 };
60 
61 /**
62  * The CIndexedPriorityQueue class provides an indexed priority queue.
63  * Each element consistes of a pair of values, a key and an index.
64  *
65  * The elements in the queue are ordered according to the value of their key.
66  * Since for stochastic simulations the minimum time is required, the queue is
67  * ordered so that the element with the minimum key value is at the top. This is
68  * the opposite of the normal ordering of priority queues.
69  *
70  * The index can be used to access elements from positions other than at
71  * the front of the queue.
72  *
73  * The indexed priority queue as applied to stochastic simulations is described in
74  * "Efficient Exact Stochastic Simulation of Chemical Systems with Many Species
75  * and Many Channels", Gibson and Bruck, J. Phys. Chem. A 104 (2000) 1876-1889
76  */
77 
79 {
80 public:
81  // Lifecycle methods
82  /**
83  * Constructor
84  */
86 
87  /**
88  * Destructor
89  */
91 
92  // Accessors
93  /**
94  * Get the index associated with the highest priority node
95  * @return The index
96  */
97  size_t topIndex() const;
98 
99  /**
100  * Get the key value associated with the highest priority node
101  * @return The key value
102  */
103  C_FLOAT64 topKey() const;
104 
105  /**
106  * Deletes the node in the tree with the given index. The pointer
107  * in the index array is removed.
108  *
109  * added by juergen 26 July, 2002
110  */
111  size_t removeStochReaction(const size_t index);
112 
113  /**
114  * Inserts the node with the given index and key into the tree. The index
115  * has to exist in the index array of course.
116  *
117  * added by juergen 26 July, 2002
118  */
119  size_t insertStochReaction(const size_t index, const C_FLOAT64 key);
120 
121  /**
122  * Initializes the vector mIndexPointer. The vector will be
123  * <numberOfReactions> long and every pointer will be -1, because none of
124  * the nodes can be found in the tree so far. Insert the stochastic
125  * reactions into the tree with insertStochReaction()
126  *
127  * added by juergen 26 July, 2002
128  */
129  void initializeIndexPointer(const size_t numberOfReactions);
130 
131  /**
132  * Return the size of the heap
133  */
134  size_t size() const {return mHeap.size();}
135 
136  // Operations
137  /**
138  * Push an index/key pair onto the queue
139  * @param index The index used to access the node
140  * @param key The key value used to determine the priority
141  */
142  size_t pushPair(const size_t index, const C_FLOAT64 key);
143 
144  /**
145  * Build moves entries until the correct ordering is achieved.
146  */
147  void buildHeap();
148 
149  /**
150  * Update the key value of a node at a given index. This
151  * also moves the node to the correct position if neccessary.
152  * @param index The index used to access the node
153  * @param key The key value used to determine the priority
154  */
155  void updateNode(const size_t index, const C_FLOAT64 key);
156 
157  /**
158  * Overloads the [] operator. Gives the index´th element on the heap
159  * @return Returns the key
160  */
161  C_FLOAT64 operator[](const size_t pos) const
162  {
163  return mHeap[pos].mKey;
164  }
165 
166  void clear();
167 
168  /**
169  * gets the key from a given index
170  * @return Returns the key
171  */
172  C_FLOAT64 getKey(const size_t index) const
173  {
174  // does not consider negative IndexPointer
175  return mHeap[mIndexPointer[index]].mKey;
176  }
177 
178  /**
179  * insert operator
180  */
181  friend std::ostream & operator<<(std::ostream &os,
182  const CIndexedPriorityQueue & d);
183 
184 private:
185  // Private operations
186  /**
187  * Swap a pair of nodes and update the index structure accordingly.
188  */
189  void swapNodes(const size_t index1, const size_t index2);
190 
191  /**
192  * Make a tree rooted at a given position into a heap
193  * @param pos The root position of the tree to heapify
194  */
195  void heapify(const size_t pos);
196 
197  /**
198  * Used by the updateNode function. Update the node at a given position.
199  */
200  void updateAux(const size_t position);
201 
202  /**
203  * Provide the position in the heap of the parent to a node.
204  * The positions are numbered from zero; a parent position less than zero
205  * implies that the current node is already at the top of the tree.
206  * @param pos The current node position
207  * @return The parent node position
208  */
209  size_t parent(const size_t pos) const {return (pos + 1) / 2 - 1;}
210 
211  /**
212  * Provide the position in the heap of the left child of the current node.
213  * @param pos The current node position
214  * @return The left child position
215  */
216  size_t leftChild(const size_t pos) const {return 2*pos + 1;}
217 
218  /**
219  * Provide the position in the heap of the right child of the current node.
220  * @param pos The current node position
221  * @return The right child position
222  */
223  size_t rightChild(const size_t pos) const {return 2*pos + 2;}
224 
225 private:
226  // Members
227  /**
228  * The vector which stores the heap
229  */
230  std::vector<PQNode> mHeap;
231  /**
232  * The vector which stores a pointer to each indexed node on the heap
233  */
234  std::vector<size_t> mIndexPointer;
235 };
236 
237 #endif // COPASI_CPriorityQueue
PQNode(size_t idx, C_FLOAT64 key)
friend std::ostream & operator<<(std::ostream &os, const PQNode &d)
std::vector< size_t > mIndexPointer
C_FLOAT64 operator[](const size_t pos) const
C_FLOAT64 getKey(const size_t index) const
std::vector< PQNode > mHeap
size_t leftChild(const size_t pos) const
size_t insertStochReaction(const size_t index, const C_FLOAT64 key)
void heapify(const size_t pos)
friend std::ostream & operator<<(std::ostream &os, const CIndexedPriorityQueue &d)
void updateAux(const size_t position)
size_t removeStochReaction(const size_t index)
void updateNode(const size_t index, const C_FLOAT64 key)
#define C_FLOAT64
Definition: copasi.h:92
C_FLOAT64 mKey
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
size_t pushPair(const size_t index, const C_FLOAT64 key)
void initializeIndexPointer(const size_t numberOfReactions)