1 | #ifndef MINOR_H |
---|
2 | #define MINOR_H |
---|
3 | |
---|
4 | #ifdef HAVE_MINOR |
---|
5 | |
---|
6 | #include <assert.h> |
---|
7 | #include <iostream> |
---|
8 | #include <string> |
---|
9 | |
---|
10 | using namespace std; |
---|
11 | |
---|
12 | /*! \class MinorKey |
---|
13 | \brief Class MinorKey can be used for representing keys in a cache for |
---|
14 | sub-determinantes; see class Cache. |
---|
15 | |
---|
16 | As such, it is a realization of the template class KeyClass which is used in |
---|
17 | the declaration of class Cache. Following the documentation of class Cache, we |
---|
18 | need to implement at least the methods:<br> |
---|
19 | <c>bool MinorKey::operator< (const MinorKey& key),</c><br> |
---|
20 | <c>bool MinorKey::operator== (const MinorKey& key),</c><br> |
---|
21 | MinorKey uses two private arrays of ints \c _rowKey and \c _columnKey to encode rows and |
---|
22 | columns of a pre-defined matrix. Semantically, the row indices and column indices form the key |
---|
23 | for caching the value of the corresponding minor.<br> |
---|
24 | More concretely, let us assume that the pre-defined matrix has <em>32*R+r, r<32,</em> rows and |
---|
25 | <em>32*C+c, c<32,</em> columns. All row indices can then be captured using R+1 ints, since |
---|
26 | an int is a 32-bit-number (regardless of the platform). The analog holds for the columns. Consequently, each instance of MinorKey |
---|
27 | encodes the sets of rows and columns which shall belong to the minor of interest (and which shall not).<br> |
---|
28 | Example: The \c _rowKey with \c _rowKey[1] = 0...011 and \c _rowKey[0] = 0...01101 encodes the rows with |
---|
29 | indices 33, 32, 3, 2, and 0. |
---|
30 | \author Frank Seelisch, http://www.mathematik.uni-kl.de/~seelisch |
---|
31 | */ |
---|
32 | class MinorKey { |
---|
33 | private: |
---|
34 | /** |
---|
35 | * a pointer to an array[0..k-1] of ints, capturing k*32 bits for determining which |
---|
36 | * rows of a pre-defined matrix shall belong to the minor of interest; |
---|
37 | * for i < j, _rowKey[i] holds lower bits than _rowKey[j] |
---|
38 | */ |
---|
39 | unsigned int* _rowKey; |
---|
40 | |
---|
41 | /** |
---|
42 | * a pointer to an array[0..k-1] of ints, capturing k*32 bits for determining which |
---|
43 | * columns of a pre-defined matrix shall belong to the minor of interest; |
---|
44 | * for i < j, _columnKey[i] holds lower bits than _columnKey[j] |
---|
45 | */ |
---|
46 | unsigned int* _columnKey; |
---|
47 | |
---|
48 | /** |
---|
49 | * the number of ints (i.e. 32-bit-numbers) we need to encode the set of rows; |
---|
50 | * If the higest row index is 70, we need 3 blocks of 32 bits to also encode the 70th bit. |
---|
51 | */ |
---|
52 | int _numberOfRowBlocks; |
---|
53 | |
---|
54 | /** |
---|
55 | * the number of ints (i.e. 32-bit-numbers) we need to encode the set of columns; |
---|
56 | * If the higest column index is 70, we need 3 blocks of 32 bits to also encode the 70th bit. |
---|
57 | */ |
---|
58 | int _numberOfColumnBlocks; |
---|
59 | |
---|
60 | /** |
---|
61 | * Inlined accessor of blockIndex-th element of _rowKey. |
---|
62 | * @param blockIndex the index of the int to be retrieved |
---|
63 | * @return an entry of _rowKey |
---|
64 | */ |
---|
65 | unsigned int getRowKey (const int blockIndex) const; |
---|
66 | |
---|
67 | /** |
---|
68 | * Inlined accessor of blockIndex-th element of _columnKey. |
---|
69 | * @param blockIndex the index of the int to be retrieved |
---|
70 | * @return an entry of _columnKey |
---|
71 | */ |
---|
72 | unsigned int getColumnKey (const int blockIndex) const; |
---|
73 | |
---|
74 | void setRowKey (const int blockIndex, const unsigned int rowKey); |
---|
75 | |
---|
76 | void setColumnKey (const int blockIndex, const unsigned int columnKey); |
---|
77 | |
---|
78 | /** |
---|
79 | * Inlined accessor of _numberOfRowBlocks. |
---|
80 | * @return the number of 32-bit-blocks needed to encode all rows of the minor as a sequence of bits |
---|
81 | */ |
---|
82 | int getNumberOfRowBlocks () const; |
---|
83 | |
---|
84 | /** |
---|
85 | * Inlined accessor of _numberOfColumnBlocks. |
---|
86 | * @return the number of 32-bit-blocks needed to encode all columns of the minor as a sequence of bits |
---|
87 | */ |
---|
88 | int getNumberOfColumnBlocks () const; |
---|
89 | |
---|
90 | void reset(); |
---|
91 | |
---|
92 | // just for debugging |
---|
93 | int getSetBits(const int a) const; |
---|
94 | |
---|
95 | friend class MinorProcessor; |
---|
96 | public: |
---|
97 | /** |
---|
98 | * A constructor for class MinorKey. |
---|
99 | * The ints given in the array rowKey encode all rows which shall belong to the minor. |
---|
100 | * Each array entry encodes 32 rows, e.g. the i-th array entry 0...01101 encodes the rows with |
---|
101 | * absolute matrix row indices 3+i*32, 2+i*32, and 0+i*32. Analog for columns. |
---|
102 | * @param lengthOfRowArray the length of the array rowKey |
---|
103 | * @param rowKey a pointer to an array of ints encoding the set of rows of the minor |
---|
104 | * @param lengthOfColumnArray the length of the array columnKey |
---|
105 | * @param columnKey a pointer to an array of ints encoding the set of columns of the minor |
---|
106 | */ |
---|
107 | MinorKey (const int lengthOfRowArray = 0, const unsigned int* const rowKey = 0, |
---|
108 | const int lengthOfColumnArray = 0, const unsigned int* const columnKey = 0); |
---|
109 | |
---|
110 | /** |
---|
111 | * A setter method for class MinorKey. |
---|
112 | * Just like the constructor of this class, this method will set all private |
---|
113 | * fields according to the given parameters. Note that this method will change the given |
---|
114 | * instance of MinorKey. |
---|
115 | * @param lengthOfRowArray the length of the array rowKey |
---|
116 | * @param rowKey a pointer to an array of ints encoding the set of rows of the minor |
---|
117 | * @param lengthOfColumnArray the length of the array columnKey |
---|
118 | * @param columnKey a pointer to an array of ints encoding the set of columns of the minor |
---|
119 | * @see MinorKey::MinorKey (const int lengthOfRowArray, const int* rowKey, const int lengthOfColumnArray, const int* columnKey) |
---|
120 | */ |
---|
121 | void set(const int lengthOfRowArray, const unsigned int* rowKey, |
---|
122 | const int lengthOfColumnArray, const unsigned int* columnKey); |
---|
123 | |
---|
124 | /** |
---|
125 | * A copy constructor. |
---|
126 | * This method overrides the shallow copy constructor by a self-written deep copy version. |
---|
127 | * @param mk the MinorKey to be deep copied |
---|
128 | */ |
---|
129 | MinorKey (const MinorKey& mk); |
---|
130 | |
---|
131 | /** |
---|
132 | * A destructor for deleting an instance. |
---|
133 | */ |
---|
134 | ~MinorKey (); |
---|
135 | |
---|
136 | // just to make the compiler happy |
---|
137 | MinorKey& operator=(const MinorKey&); |
---|
138 | |
---|
139 | // just to make the compiler happy |
---|
140 | bool operator==(const MinorKey&) const; |
---|
141 | |
---|
142 | // just to make the compiler happy |
---|
143 | bool operator<(const MinorKey&) const; |
---|
144 | |
---|
145 | /** |
---|
146 | * A method for retrieving the (0-based) index of the i-th row in the set of rows encoded in \a this. |
---|
147 | * Lower values for \c i result in lower absolute row indices. |
---|
148 | * \par Example: |
---|
149 | * Applied to the row pattern 10010001101 and i = 3, we get the 0-based index of the 3-rd set bit counted |
---|
150 | * from the right, i.e. 7. |
---|
151 | * \par Assertion |
---|
152 | * The method assumes that there are at least \c i rows encoded in the given MinorKey. |
---|
153 | * @param i the relative index of the row, as encoded in \a this |
---|
154 | * @return (0-based) absolute row index of the i-th row in \a this |
---|
155 | */ |
---|
156 | int getAbsoluteRowIndex (const int i) const; |
---|
157 | |
---|
158 | /** |
---|
159 | * A method for retrieving the (0-based) index of the i-th column in the set of columns encoded in \a this. |
---|
160 | * Lower values for \c i result in lower absolute column indices. |
---|
161 | * \par Example: |
---|
162 | * Applied to the column pattern 10010001101 and i = 3, we get the 0-based index of the 3-rd set bit counted |
---|
163 | * from the right, i.e. 7. |
---|
164 | * \par Assertion |
---|
165 | * The method assumes that there are at least \c i columns encoded in the given MinorKey. |
---|
166 | * @param i the relative index of the column, as encoded in \a this |
---|
167 | * @return (0-based) absolute column index of the i-th row in \a this |
---|
168 | */ |
---|
169 | int getAbsoluteColumnIndex (const int i) const; |
---|
170 | |
---|
171 | /** |
---|
172 | * A method for retrieving the (0-based) relative index of the i-th row in \a this MinorKey. |
---|
173 | * Lower values for \c i result in lower relative row indices. Note that the absolute index |
---|
174 | * \c i is 0-based, too. |
---|
175 | * \par Example: |
---|
176 | * Applied to the row pattern 10010001101 and i = 7, we get the relative 0-based position of the |
---|
177 | * bit representing the absolute index 7, i.e. 3. |
---|
178 | * \par Assertion |
---|
179 | * The method assumes that the bit which corresponds to the absolute index i is actually set. |
---|
180 | * @param i the absolute 0-based index of a row encoded in \a this |
---|
181 | * @return (0-based) relative row index corresponding to \c i |
---|
182 | */ |
---|
183 | int getRelativeRowIndex (const int i) const; |
---|
184 | |
---|
185 | /** |
---|
186 | * A method for retrieving the (0-based) relative index of the i-th column in \a this MinorKey. |
---|
187 | * Lower values for \c i result in lower relative column indices. Note that the absolute index |
---|
188 | * \c i is 0-based, too. |
---|
189 | * \par Example: |
---|
190 | * Applied to the column pattern 10010001101 and i = 7, we get the relative 0-based position of the |
---|
191 | * bit representing the absolute index 7, i.e. 3. |
---|
192 | * \par Assertion |
---|
193 | * The method assumes that the bit which corresponds to the absolute index i is actually set. |
---|
194 | * @param i the absolute 0-based index of a column encoded in \a this |
---|
195 | * @return (0-based) relative column index corresponding to \c i |
---|
196 | */ |
---|
197 | int getRelativeColumnIndex (const int i) const; |
---|
198 | |
---|
199 | /** |
---|
200 | * A method for retrieving the 0-based indices of all rows encoded in \a this MinorKey. |
---|
201 | * The user of this method needs to know the number of rows in \a this, in order to know which |
---|
202 | * indices in \c target[k] will be valid. |
---|
203 | * \par Example: |
---|
204 | * The bit pattern <c>0...01101</c> will give rise to the settings |
---|
205 | * <c>target[0] = 0, target[1] = 2, target[2] = 3</c>, and the user needs to know in advance that |
---|
206 | * there are three rows in \a this MinorKey. |
---|
207 | * \par Assertion |
---|
208 | * The method assumes that target has enough positions for all rows encoded in \a this MinorKey. |
---|
209 | * @param target a pointer to some array of ints that is to be filled with the requested indices |
---|
210 | */ |
---|
211 | void getAbsoluteRowIndices(int* const target) const; |
---|
212 | |
---|
213 | /** |
---|
214 | * A method for retrieving the 0-based indices of all columns encoded in \a this MinorKey. |
---|
215 | * The user of this method needs to know the number of columns in \a this, in order to know which |
---|
216 | * indices in \c target[k] will be valid. |
---|
217 | * \par Example: |
---|
218 | * The bit pattern <c>0...01101</c> will give rise to the settings |
---|
219 | * <c>target[0] = 0, target[1] = 2, target[2] = 3</c>, and the user needs to know in advance that |
---|
220 | * there are three columns in \a this MinorKey. |
---|
221 | * \par Assertion |
---|
222 | * The method assumes that target has enough positions for all columns encoded in \a this MinorKey. |
---|
223 | * @param target a pointer to some array of ints that is to be filled with the requested indices |
---|
224 | */ |
---|
225 | void getAbsoluteColumnIndices(int* const target) const; |
---|
226 | |
---|
227 | /** |
---|
228 | * A method for retrieving a sub-MinorKey resulting from omitting one row and one column |
---|
229 | * of \a this MinorKey. |
---|
230 | * \par Assertion |
---|
231 | * The method assumes that the row with absolute index \c absoluteEraseRowIndex (counted from lower bits |
---|
232 | * to higher bits) and the column with absolute index \c absoluteEraseColumnIndex are actually set in |
---|
233 | * \c mk. |
---|
234 | * @param absoluteEraseRowIndex the 0-based absolute index of a row in \a mk |
---|
235 | * @param absoluteEraseColumnIndex the 0-based absolute index of a column in \a mk |
---|
236 | * @return the MinorKey when omitting the specified row and column |
---|
237 | */ |
---|
238 | MinorKey getSubMinorKey (const int absoluteEraseRowIndex, |
---|
239 | const int absoluteEraseColumnIndex) const; |
---|
240 | |
---|
241 | /** |
---|
242 | * A comparator for two instances of MinorKey. |
---|
243 | * The ordering induced by this implementation determines the ordering of all |
---|
244 | * (key --> value) pairs in a cache that uses MinorKey as KeyClass. |
---|
245 | * @param mk a second MinorKey to be compared with \a this instance |
---|
246 | * @return -1 iff \a this instance is smaller than \a mk; 0 for equality; +1 otherwise |
---|
247 | * @see MinorKey::operator== (const MinorKey&) const |
---|
248 | */ |
---|
249 | int compare (const MinorKey& mk) const; |
---|
250 | |
---|
251 | /** |
---|
252 | * This method redefines the set of rows represented by \a this MinorKey. |
---|
253 | * After the method, the defined set of rows coincides with the lowest |
---|
254 | * \c k rows of \c mk. (Here, lowest means w.r.t. indices.)<br> |
---|
255 | * Note that the method modifies the given instance of MinorKey. |
---|
256 | * \par Assertion |
---|
257 | * It is assumed that \c mk represents at least \c k rows. |
---|
258 | * @param k the number of rows |
---|
259 | * @param mk the MinorKey from which to choose the lowest \c k rows |
---|
260 | * @see MinorKey::selectNextRows (const int k, const MinorKey& mk) |
---|
261 | */ |
---|
262 | void selectFirstRows (const int k, const MinorKey& mk); |
---|
263 | |
---|
264 | /** |
---|
265 | * This method redefines the set of rows represented by \a this MinorKey. |
---|
266 | * Both the old and the new set of \c k rows are subsets of the rows |
---|
267 | * represented by \c mk. After the method, the defined set of rows is |
---|
268 | * the next sensible choice of \c k rows of \c mk. (Here, next means |
---|
269 | * the next w.r.t. the increasing index ordering on multi-indices of |
---|
270 | * natural numbers.)<br> |
---|
271 | * Note that the method modifies the given instance of MinorKey. |
---|
272 | * \par Assertion |
---|
273 | * It is assumed that \c mk represents at least \c k rows. Furthermore, |
---|
274 | * the method assumes that the old set of rows represented by \a this |
---|
275 | * is also a subset of the rows given by \c mk. |
---|
276 | * @param k the number of rows |
---|
277 | * @param mk the MinorKey from which to choose the lowest \c k rows |
---|
278 | * @return true iff there is a next choice of \c k rows |
---|
279 | * @see MinorKey::selectFirstRows (const int k, const MinorKey& mk) |
---|
280 | */ |
---|
281 | bool selectNextRows (const int k, const MinorKey& mk); |
---|
282 | |
---|
283 | /** |
---|
284 | * This method redefines the set of columns represented by \a this MinorKey. |
---|
285 | * After the method, the defined set of columns coincides with the lowest |
---|
286 | * \c k columns of \c mk. (Here, lowest means w.r.t. indices.)<br> |
---|
287 | * Note that the method modifies the given instance of MinorKey. |
---|
288 | * \par Assertion |
---|
289 | * It is assumed that \c mk represents at least \c k columns. |
---|
290 | * @param k the number of columns |
---|
291 | * @param mk the MinorKey from which to choose the lowest \c k columns |
---|
292 | * @see MinorKey::selectNextColumns (const int k, const MinorKey& mk) |
---|
293 | */ |
---|
294 | void selectFirstColumns (const int k, const MinorKey& mk); |
---|
295 | |
---|
296 | /** |
---|
297 | * This method redefines the set of columns represented by \a this MinorKey. |
---|
298 | * Both the old and the new set of \c k columns are subsets of the columns |
---|
299 | * represented by \c mk. After the method, the defined set of columns is |
---|
300 | * the next sensible choice of \c k columns of \c mk. (Here, next means |
---|
301 | * the next w.r.t. the increasing index ordering on multi-indices of |
---|
302 | * natural numbers.)<br> |
---|
303 | * Note that the method modifies the given instance of MinorKey. |
---|
304 | * \par Assertion |
---|
305 | * It is assumed that \c mk represents at least \c k columns. Furthermore, |
---|
306 | * the method assumes that the old set of columns represented by \a this |
---|
307 | * is also a subset of the columns given by \c mk. |
---|
308 | * @param k the number of columns |
---|
309 | * @param mk the MinorKey from which to choose the lowest \c k columns |
---|
310 | * @return true iff there is a next choice of \c k columns |
---|
311 | * @see MinorKey::selectFirstColumns (const int k, const MinorKey& mk) |
---|
312 | */ |
---|
313 | bool selectNextColumns (const int k, const MinorKey& mk); |
---|
314 | |
---|
315 | /** |
---|
316 | * A method for providing a printable version of the represented MinorKey. |
---|
317 | * @return a printable version of the given instance as instance of class string |
---|
318 | */ |
---|
319 | string toString () const; |
---|
320 | |
---|
321 | /** |
---|
322 | * A method for printing a string representation of the given MinorKey to std::cout. |
---|
323 | */ |
---|
324 | void print () const; |
---|
325 | }; |
---|
326 | |
---|
327 | class MinorValue { |
---|
328 | protected: |
---|
329 | /** |
---|
330 | * -1 iff cache is not used, otherwise the number of retrievals so far of the current minor |
---|
331 | */ |
---|
332 | int _retrievals; |
---|
333 | |
---|
334 | /** |
---|
335 | * // -1 iff cache is not used, otherwise the maximum number of potential retrievals of |
---|
336 | * this minor (e.g. when the minor would be kept in cache forever) |
---|
337 | */ |
---|
338 | int _potentialRetrievals; |
---|
339 | |
---|
340 | /** |
---|
341 | * a store for the actual number of multiplications to compute the current minor |
---|
342 | */ |
---|
343 | int _multiplications; |
---|
344 | |
---|
345 | /** |
---|
346 | * a store for the actual number of additions to compute the current minor |
---|
347 | */ |
---|
348 | int _additions; |
---|
349 | |
---|
350 | /** |
---|
351 | * a store for the accumulated number of multiplications to compute the current minor; |
---|
352 | * This also includes all multiplications nested in sub-minors which may be retrieved |
---|
353 | * from a cache. (Thus, these nested operations do not need to be performed again.) |
---|
354 | */ |
---|
355 | int _accumulatedMult; |
---|
356 | |
---|
357 | /** |
---|
358 | * a store for the accumulated number of additions to compute the current minor; |
---|
359 | * This also includes all additions nested in sub-minors which may be retrieved |
---|
360 | * from a cache. (Thus, these nested operations do not need to be performed again.) |
---|
361 | */ |
---|
362 | int _accumulatedSum; |
---|
363 | |
---|
364 | /** |
---|
365 | * A method for obtaining a rank measure for the given MinorValue.<br> |
---|
366 | * Rank measures are used to compare any two instances of MinorValue. The induced ordering |
---|
367 | * on MinorValues has an impact on the caching behaviour in a given cache: Greater |
---|
368 | * MinorValues will be cached longer than lower ones.<br> |
---|
369 | * More explicitely, this means: Make the return value of this method greater, and the given MinorValue |
---|
370 | * will be cached longer when caching strategy 1 is deployed.<br> |
---|
371 | * Rank measure 1 is equal to the number of actually performed multiplications to compute \a mv. |
---|
372 | * @return an integer rank measure of \c this |
---|
373 | * @see MinorValue::operator< (const MinorValue& mv) |
---|
374 | */ |
---|
375 | int rankMeasure1 () const; |
---|
376 | |
---|
377 | /** |
---|
378 | * A method for obtaining a rank measure for the given MinorValue.<br> |
---|
379 | * Rank measures are used to compare any two instances of MinorValue. The induced ordering |
---|
380 | * on MinorValues has an impact on the caching behaviour in a given cache: Greater |
---|
381 | * MinorValues will be cached longer than lower ones.<br> |
---|
382 | * More explicitely, this means: Make the return value of this method greater, and the given MinorValue |
---|
383 | * will be cached longer when caching strategy 1 is deployed.<br> |
---|
384 | * Rank measure 2 is equal to the number of accumulated multiplications to compute the given MinorValue. |
---|
385 | * This also includes all nested multiplications which were performed to compute all |
---|
386 | * sub-minors which could be reused from cache. |
---|
387 | * @return an integer rank measure of \c this |
---|
388 | * @see MinorValue::operator< (const MinorValue& mv) |
---|
389 | */ |
---|
390 | int rankMeasure2 () const; |
---|
391 | |
---|
392 | /** |
---|
393 | * A method for obtaining a rank measure for the given MinorValue.<br> |
---|
394 | * Rank measures are used to compare any two instances of MinorValue. The induced ordering |
---|
395 | * on MinorValues has an impact on the caching behaviour in a given cache: Greater |
---|
396 | * MinorValues will be cached longer than lower ones.<br> |
---|
397 | * More explicitely, this means: Make the return value of this method greater, and the given MinorValue |
---|
398 | * will be cached longer when caching strategy 1 is deployed.<br> |
---|
399 | * Rank measure 3 is equal to the number of actually performed multiplications, weighted |
---|
400 | * with the ratio of not yet performed retrievals over the maximum number of retrievals. |
---|
401 | * @return an integer rank measure of \c this |
---|
402 | * @see MinorValue::operator< (const MinorValue& mv) |
---|
403 | */ |
---|
404 | int rankMeasure3 () const; |
---|
405 | |
---|
406 | /** |
---|
407 | * A method for obtaining a rank measure for the given MinorValue.<br> |
---|
408 | * Rank measures are used to compare any two instances of MinorValue. The induced ordering |
---|
409 | * on MinorValues has an impact on the caching behaviour in a given cache: Greater |
---|
410 | * MinorValues will be cached longer than lower ones.<br> |
---|
411 | * More explicitely, this means: Make the return value of this method greater, and the given MinorValue |
---|
412 | * will be cached longer when caching strategy 1 is deployed.<br> |
---|
413 | * Rank measure 4 is equal to the number of actually performed multiplications, multiplied |
---|
414 | * with the number of not yet performed retrievals. |
---|
415 | * @return an integer rank measure of \c this |
---|
416 | * @see MinorValue::operator< (const MinorValue& mv) |
---|
417 | */ |
---|
418 | int rankMeasure4 () const; |
---|
419 | |
---|
420 | /** |
---|
421 | * A method for obtaining a rank measure for the given MinorValue.<br> |
---|
422 | * Rank measures are used to compare any two instances of MinorValue. The induced ordering |
---|
423 | * on MinorValues has an impact on the caching behaviour in a given cache: Greater |
---|
424 | * MinorValues will be cached longer than lower ones.<br> |
---|
425 | * More explicitely, this means: Make the return value of this method greater, and the given MinorValue |
---|
426 | * will be cached longer when caching strategy 1 is deployed.<br> |
---|
427 | * Rank measure 5 is equal to the number of not yet performed retrievals. This strategy tends |
---|
428 | * to cache MinorValues longer which have a high maximum number of potential retrievals. |
---|
429 | * @return an integer rank measure of \c this |
---|
430 | * @see MinorValue::operator< (const MinorValue& mv) |
---|
431 | */ |
---|
432 | int rankMeasure5 () const; |
---|
433 | |
---|
434 | /** |
---|
435 | * private store for the current value ranking strategy; |
---|
436 | * This member can be set using MinorValue::SetRankingStrategy (const int). |
---|
437 | */ |
---|
438 | static int _RankingStrategy; |
---|
439 | |
---|
440 | /** |
---|
441 | * Inlined accessor for the static private field _RankingStrategy. |
---|
442 | */ |
---|
443 | static int GetRankingStrategy(); |
---|
444 | public: |
---|
445 | // just to make the compiler happy |
---|
446 | bool operator== (const MinorValue& mv) const; |
---|
447 | |
---|
448 | // just to make the compiler happy |
---|
449 | bool operator< (const MinorValue& mv) const; |
---|
450 | |
---|
451 | /** |
---|
452 | * A method for retrieving the weight of a given MinorValue. |
---|
453 | * The implementation of Cache uses this function to determine the total |
---|
454 | * weight of an entire cache. As the user can instantiate Cache by |
---|
455 | * determining its maximum total weight (see Cache::Cache(const int, const int)), |
---|
456 | * the definition of weight of a MinorValue |
---|
457 | * may have an impact on the behaviour of the cache. |
---|
458 | * @return the weight of a given instance of MinorValue |
---|
459 | * @see Cache::getWeight () const |
---|
460 | */ |
---|
461 | virtual int getWeight () const; |
---|
462 | |
---|
463 | /** |
---|
464 | * A method for accessing the number of retrievals of this minor. Multiple retrievals will |
---|
465 | * occur when computing large minors by means of cached sub-minors. (Then, the latter ones |
---|
466 | * may be retrieved multiple times.) |
---|
467 | * @return the number of retrievals of this minor |
---|
468 | * @see MinorValue::getPotentialRetrievals () const |
---|
469 | */ |
---|
470 | int getRetrievals () const; |
---|
471 | |
---|
472 | /** |
---|
473 | * A method for accessing the maximum number of potential retrievals of this minor. |
---|
474 | * Multiple retrievals will |
---|
475 | * occur when computing large minors by means of cached sub-minors. (Then, the latter ones |
---|
476 | * may be retrieved multiple times.) |
---|
477 | * @return the maximum number of potential retrievals of this minor |
---|
478 | * @see MinorValue::getRetrievals () const |
---|
479 | */ |
---|
480 | int getPotentialRetrievals () const; |
---|
481 | |
---|
482 | /** |
---|
483 | * A method for accessing the multiplications performed while computing this minor. |
---|
484 | * Due to multiplication with zero entries of the underlying matrix, some sub-minors |
---|
485 | * may be irrelevant. In this case, the multiplications needed to compute these sub-minors |
---|
486 | * will not be counted (, as they need not be performed). |
---|
487 | * Moreover, multiplications that were needed to compute cached sub-minors will not be counted |
---|
488 | * either, as the value of those sub-minors can be directly retrieved from the cache. |
---|
489 | * @return the number of multiplications performed |
---|
490 | * @see MinorValue::getAccumulatedMultiplications () const |
---|
491 | */ |
---|
492 | int getMultiplications () const; |
---|
493 | |
---|
494 | /** |
---|
495 | * A method for accessing the multiplications performed while computing this minor, including |
---|
496 | * all nested multiplications. |
---|
497 | * Contrary to MinorValue::getMultiplications () const, this method will also count multiplications |
---|
498 | * needed to compute all cached sub-minors (, although they need not be performed again in order to |
---|
499 | * compute the given instance of MinorValue). |
---|
500 | * @return the number of multiplications performed, including nested multiplications |
---|
501 | * @see MinorValue::getMultiplications () const |
---|
502 | */ |
---|
503 | int getAccumulatedMultiplications () const; |
---|
504 | |
---|
505 | /** |
---|
506 | * A method for accessing the additions performed while computing this minor. |
---|
507 | * Additions that were needed to compute cached sub-minors will not be counted, |
---|
508 | * as the value of those sub-minors can be directly retrieved from the cache. |
---|
509 | * @return the number of additions performed |
---|
510 | * @see MinorValue::getAccumulatedAdditions () const |
---|
511 | */ |
---|
512 | int getAdditions () const; |
---|
513 | |
---|
514 | /** |
---|
515 | * A method for accessing the additions performed while computing this minor, including |
---|
516 | * all nested additions. |
---|
517 | * Contrary to MinorValue::getAdditions () const, this method will also count additions |
---|
518 | * needed to compute all cached sub-minors (, although they need not be performed again in order to |
---|
519 | * compute the given instance of MinorValue). |
---|
520 | * @return the number of additions performed, including nested additions |
---|
521 | * @see MinorValue::getAdditions () const |
---|
522 | */ |
---|
523 | int getAccumulatedAdditions () const; |
---|
524 | |
---|
525 | /** |
---|
526 | * A method for incrementing the number of performed retrievals of \a this instance of MinorValue.<br> |
---|
527 | * Note that, when calling MinorValue::incrementRetrievals () for some instance \a mv of MinorValue |
---|
528 | * which has been cached in a Cache under MinorKey \a mk, the user should be careful: |
---|
529 | * After incrementing the number of retrievals for \a mv, the user should always |
---|
530 | * put the value again into cache, i.e. should perform Cache::put (const KeyClass&, const ValueClass&) |
---|
531 | * with \a mk and the modified \a mv as arguments. This is due to the fact that changing the number of |
---|
532 | * performed retrievals of a MinorValue may have an impact on its ranking in Cache. Only by calling |
---|
533 | * Cache::put (const KeyClass&, const ValueClass&) can the user ensure that the pair (\a mk --> \a mv) |
---|
534 | * will be correctly re-positioned within the Cache. |
---|
535 | */ |
---|
536 | void incrementRetrievals (); |
---|
537 | |
---|
538 | /** |
---|
539 | * A method for obtaining a rank measure for theiven MinorValue.<br> |
---|
540 | * Rank measures are used to compare any two instances of MinorValue. The induced ordering |
---|
541 | * on MinorValues has an impact on the caching behaviour of the underlying cache: Greater |
---|
542 | * MinorValues will be cached longer than lower ones.<br> |
---|
543 | * More explicitely, this means: Make the return value of this method greater, and the given MinorValue |
---|
544 | * will be cached longer.<br> |
---|
545 | * Internally, this method will call one of several implementations, depending on the pre-defined |
---|
546 | * caching strategy; see MinorProcessor::SetCacheStrategy (const int). |
---|
547 | * @return an integer rank measure of \c this |
---|
548 | * @see MinorValue::operator< (const MinorValue& mv) |
---|
549 | * @see MinorProcessor::SetCacheStrategy (const int) |
---|
550 | */ |
---|
551 | int getUtility () const; |
---|
552 | |
---|
553 | /** |
---|
554 | * A method for determining the value ranking strategy.<br> |
---|
555 | * This setting has a direct effect on how long the given MinorValue |
---|
556 | * will be cached in any cache that uses MinorValue to represent its |
---|
557 | * cached values. |
---|
558 | * @param rankingStrategy an int, so far one of 1, 2, ..., 5 |
---|
559 | */ |
---|
560 | static void SetRankingStrategy (const int rankingStrategy); |
---|
561 | |
---|
562 | /** |
---|
563 | * A method for providing a printable version of the represented MinorValue. |
---|
564 | * @return a printable version of the given instance as instance of class string |
---|
565 | */ |
---|
566 | virtual string toString () const; |
---|
567 | |
---|
568 | /** |
---|
569 | * A method for printing a string representation of the given MinorValue to std::cout. |
---|
570 | */ |
---|
571 | void print () const; |
---|
572 | }; |
---|
573 | |
---|
574 | /*! \class IntMinorValue |
---|
575 | \brief Class IntMinorValue can be used for representing values in a cache for |
---|
576 | sub-determinantes; see class Cache. |
---|
577 | |
---|
578 | As such, it is a realization of the template class ValueClass which is used in |
---|
579 | the declaration of class Cache. Following the documentation of class Cache, we |
---|
580 | need to implement at least the methods:<br> |
---|
581 | <c>bool IntMinorValue::operator< (const IntMinorValue& key),</c><br> |
---|
582 | <c>bool IntMinorValue::operator== (const IntMinorValue& key),</c><br> |
---|
583 | <c>int IntMinorValue::getWeight ().</c><br><br> |
---|
584 | The main purpose of IntMinorValue is to represent values of sub-determinantes of a pre-defined |
---|
585 | matrix. Class MinorKey is used to determine which rows and columns of this pre-defined matrix |
---|
586 | ought to belong to the respective sub-determinante of interest. So far, IntMinorValue is just |
---|
587 | an example implementation which assumes matrices with int entries, such that the result |
---|
588 | of any minor is again an int.<br> |
---|
589 | Besides capturing the actual value of a minor, IntMinorValue also has built-in facilities to |
---|
590 | count the number of additions and multiplications performed when computing a minor. These two |
---|
591 | counters, especially the latter, are important measures when we want to investigate the complexity |
---|
592 | of computing minors.<br> |
---|
593 | When used in a cache, each minor \e M (e.g. of size 3 x 3) may be used several times, e.g. when |
---|
594 | computing a larger minor (e.g. of size 6 x 6) which contains \e M. MinorValue offers functionality |
---|
595 | to also count the number of retrievals of \e M in such a computational context. |
---|
596 | \author Frank Seelisch, http://www.mathematik.uni-kl.de/~seelisch |
---|
597 | */ |
---|
598 | class IntMinorValue : public MinorValue { |
---|
599 | private: |
---|
600 | /** |
---|
601 | * a store for the actual value of the minor |
---|
602 | */ |
---|
603 | int _result; |
---|
604 | public: |
---|
605 | /** |
---|
606 | * A constructor for class MinorValue. |
---|
607 | * @param result the actual value of the represented minor |
---|
608 | * @param multiplications number of multiplications to compute \a this minor |
---|
609 | * @param additions number of additions to compute \a this minor |
---|
610 | * @param accumulatedMultiplications number of multiplications to compute \a this minor, including nested operations |
---|
611 | * @param accumulatedAdditions number of additions to compute \a this minor, including nested operations |
---|
612 | * @param retrievals number of times this minor has been retrieved from cache |
---|
613 | * @param potentialRetrievals maximum number of times this minor may be retrieved from cache |
---|
614 | */ |
---|
615 | IntMinorValue (const int result, const int multiplications, const int additions, |
---|
616 | const int accumulatedMultiplications, const int accumulatedAdditions, |
---|
617 | const int retrievals, const int potentialRetrievals); |
---|
618 | |
---|
619 | IntMinorValue (const IntMinorValue& mv); |
---|
620 | |
---|
621 | // just to make the compiler happy |
---|
622 | IntMinorValue (); |
---|
623 | |
---|
624 | virtual ~IntMinorValue (); |
---|
625 | |
---|
626 | int getResult() const; |
---|
627 | |
---|
628 | int getWeight () const; |
---|
629 | |
---|
630 | /** |
---|
631 | * A method for providing a printable version of the represented MinorValue. |
---|
632 | * @return a printable version of the given instance as instance of class string |
---|
633 | */ |
---|
634 | string toString () const; |
---|
635 | }; |
---|
636 | |
---|
637 | class PolyMinorValue : public MinorValue { |
---|
638 | private: |
---|
639 | /** |
---|
640 | * a store for the actual value of the minor |
---|
641 | */ |
---|
642 | poly _result; |
---|
643 | public: |
---|
644 | /** |
---|
645 | * A constructor for class MinorValue. |
---|
646 | * @param result the actual value of the represented minor |
---|
647 | * @param multiplications number of multiplications to compute \a this minor |
---|
648 | * @param additions number of additions to compute \a this minor |
---|
649 | * @param accumulatedMultiplications number of multiplications to compute \a this minor, including nested operations |
---|
650 | * @param accumulatedAdditions number of additions to compute \a this minor, including nested operations |
---|
651 | * @param retrievals number of times this minor has been retrieved from cache |
---|
652 | * @param potentialRetrievals maximum number of times this minor may be retrieved from cache |
---|
653 | */ |
---|
654 | PolyMinorValue (const poly result, const int multiplications, const int additions, |
---|
655 | const int accumulatedMultiplications, const int accumulatedAdditions, |
---|
656 | const int retrievals, const int potentialRetrievals); |
---|
657 | |
---|
658 | PolyMinorValue (const PolyMinorValue& mv); |
---|
659 | |
---|
660 | /* deep copy */ |
---|
661 | void operator= (const PolyMinorValue& mv); |
---|
662 | |
---|
663 | // just to make the compiler happy |
---|
664 | PolyMinorValue (); |
---|
665 | |
---|
666 | virtual ~PolyMinorValue (); |
---|
667 | |
---|
668 | poly getResult() const; |
---|
669 | |
---|
670 | int getWeight () const; |
---|
671 | |
---|
672 | /** |
---|
673 | * A method for providing a printable version of the represented MinorValue. |
---|
674 | * @return a printable version of the given instance as instance of class string |
---|
675 | */ |
---|
676 | string toString () const; |
---|
677 | }; |
---|
678 | |
---|
679 | #endif // HAVE_MINOR |
---|
680 | |
---|
681 | #endif |
---|
682 | /* MINOR_H */ |
---|