source: git/Singular/Minor.h @ 737a68

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