source: git/kernel/linear_algebra/Minor.h @ a3f0fea

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