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