source: git/Singular/Minor.cc @ efa772b

spielwiese
Last change on this file since efa772b was efa772b, checked in by Frank Seelisch <seelisch@…>, 14 years ago
fixed wrong assume condition in Minor.cc git-svn-id: file:///usr/local/Singular/svn/trunk@12672 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 36.4 KB
Line 
1#include "mod2.h"
2#include "structs.h"
3#include "polys.h"
4#include <Minor.h>
5#include "febase.h"
6
7void MinorKey::reset()
8{
9  _numberOfRowBlocks = 0;
10  _numberOfColumnBlocks = 0;
11  delete [] _rowKey;
12  delete [] _columnKey;
13  _rowKey = 0;
14  _columnKey = 0;
15}
16
17MinorKey::MinorKey (const MinorKey& mk)
18{
19  _numberOfRowBlocks = mk.getNumberOfRowBlocks();
20  _numberOfColumnBlocks = mk.getNumberOfColumnBlocks();;
21
22  /* allocate memory for new entries in _rowKey and _columnKey */
23  _rowKey = new unsigned int[_numberOfRowBlocks];
24  _columnKey = new unsigned int[_numberOfColumnBlocks];
25
26  /* copying values from parameter arrays to private arrays */
27  for (int r = 0; r < _numberOfRowBlocks; r++)
28    _rowKey[r] = mk.getRowKey(r);
29  for (int c = 0; c < _numberOfColumnBlocks; c++)
30    _columnKey[c] = mk.getColumnKey(c);
31}
32
33MinorKey& MinorKey::operator=(const MinorKey& mk)
34{
35  if (_numberOfRowBlocks != 0)    delete [] _rowKey;
36  if (_numberOfColumnBlocks != 0) delete [] _columnKey;
37  _numberOfRowBlocks = 0;
38  _numberOfColumnBlocks = 0;
39  _rowKey = 0;
40  _columnKey = 0;
41
42  _numberOfRowBlocks = mk.getNumberOfRowBlocks();
43  _numberOfColumnBlocks = mk.getNumberOfColumnBlocks();;
44
45  /* allocate memory for new entries in _rowKey and _columnKey */
46  _rowKey = new unsigned int[_numberOfRowBlocks];
47  _columnKey = new unsigned int[_numberOfColumnBlocks];
48
49  /* copying values from parameter arrays to private arrays */
50  for (int r = 0; r < _numberOfRowBlocks; r++)
51      _rowKey[r] = mk.getRowKey(r);
52  for (int c = 0; c < _numberOfColumnBlocks; c++)
53      _columnKey[c] = mk.getColumnKey(c);
54     
55  return *this;
56}
57
58void MinorKey::set(const int lengthOfRowArray, const unsigned int* rowKey,
59                   const int lengthOfColumnArray,
60                   const unsigned int* columnKey)
61{
62  /* free memory of _rowKey and _columnKey */
63  if (_numberOfRowBlocks > 0) { delete [] _rowKey; }
64  if (_numberOfColumnBlocks > 0) { delete [] _columnKey; }
65
66  _numberOfRowBlocks = lengthOfRowArray;
67  _numberOfColumnBlocks = lengthOfColumnArray;
68
69  /* allocate memory for new entries in _rowKey and _columnKey; */
70  _rowKey = new unsigned int[_numberOfRowBlocks];
71  _columnKey = new unsigned int[_numberOfColumnBlocks];
72
73  /* copying values from parameter arrays to private arrays */
74  for (int r = 0; r < _numberOfRowBlocks; r++)
75    _rowKey[r] = rowKey[r];
76  for (int c = 0; c < _numberOfColumnBlocks; c++)
77    _columnKey[c] = columnKey[c];
78}
79
80MinorKey::MinorKey(const int lengthOfRowArray,
81                   const unsigned int* const rowKey,
82                   const int lengthOfColumnArray,
83                   const unsigned int* const columnKey)
84{
85  _numberOfRowBlocks = lengthOfRowArray;
86  _numberOfColumnBlocks = lengthOfColumnArray;
87
88  /* allocate memory for new entries in _rowKey and _columnKey */
89  _rowKey = new unsigned int[_numberOfRowBlocks];
90  _columnKey = new unsigned int[_numberOfColumnBlocks];
91
92  /* copying values from parameter arrays to private arrays */
93  for (int r = 0; r < _numberOfRowBlocks; r++)
94    _rowKey[r] = rowKey[r];
95
96  for (int c = 0; c < _numberOfColumnBlocks; c++)
97    _columnKey[c] = columnKey[c];
98}
99
100MinorKey::~MinorKey()
101{
102  /* free memory of _rowKey and _columnKey */
103  delete [] _rowKey;
104  delete [] _columnKey;
105}
106
107void MinorKey::print() const
108{
109  cout << this->toString();
110}
111
112int MinorKey::getAbsoluteRowIndex(const int i) const
113{
114  /* This method is to return the absolute (0-based) index of the i-th
115     row encoded in \a this.
116     Example: bit-pattern of rows: "10010001101", i = 3:
117        This should yield the 0-based absolute index of the 3-rd bit
118        (counted from the right), i.e. 7. */
119
120  int matchedBits = -1; /* counter for matched bits;
121                           this needs to reach i, then we're done */
122  for (int block = 0; block < getNumberOfRowBlocks(); block ++)
123  {
124    /* start with lowest bits, i.e. in block No. 0 */
125    /* the bits in this block of 32 bits: */
126    unsigned int blockBits = getRowKey(block);
127    unsigned int shiftedBit = 1;
128    int exponent = 0;
129    /* The invariant "shiftedBit = 2^exponent" will hold throughout the
130       entire while loop. */
131    while (exponent < 32)
132    {
133      if (shiftedBit & blockBits) matchedBits++;
134      if (matchedBits == i) return exponent + (32 * block);
135      shiftedBit = shiftedBit << 1;
136      exponent++;
137    }
138  }
139  /* We should never reach this line of code. */
140  assert(false);
141}
142
143int MinorKey::getAbsoluteColumnIndex(const int i) const
144{
145  /* This method is to return the absolute (0-based) index of the i-th
146     column encoded in \a this.
147     Example: bit-pattern of columns: "10010001101", i = 3:
148        This should yield the 0-based absolute index of the 3-rd bit
149        (counted from the right), i.e. 7. */
150
151  int matchedBits = -1; /* counter for matched bits; this needs to reach i,
152                           then we're done */
153  for (int block = 0; block < getNumberOfColumnBlocks(); block ++)
154  {
155    /* start with lowest bits, i.e. in block No. 0 */
156    /* the bits in this block of 32 bits: */
157    unsigned int blockBits = getColumnKey(block);
158    unsigned int shiftedBit = 1;
159    int exponent = 0;
160    /* The invariant "shiftedBit = 2^exponent" will hold throughout the
161       entire while loop. */
162    while (exponent < 32)
163    {
164      if (shiftedBit & blockBits) matchedBits++;
165      if (matchedBits == i) return exponent + (32 * block);
166      shiftedBit = shiftedBit << 1;
167      exponent++;
168    }
169  }
170  /* We should never reach this line of code. */
171  assert(false);
172}
173
174void MinorKey::getAbsoluteRowIndices(int* const target) const
175{
176  int i = 0; /* index for filling the target array */
177  for (int block = 0; block < getNumberOfRowBlocks(); block ++)
178  {
179    /* start with lowest bits, i.e. in block No. 0 */
180    /* the bits in this block of 32 bits: */
181    unsigned int blockBits = getRowKey(block);
182    unsigned int shiftedBit = 1;
183    int exponent = 0;
184    /* The invariant "shiftedBit = 2^exponent" will hold throughout the
185       entire while loop. */
186    while (exponent < 32)
187    {
188      if (shiftedBit & blockBits) target[i++] = exponent + (32 * block);
189      shiftedBit = shiftedBit << 1;
190      exponent++;
191    }
192  }
193  return;
194}
195
196void MinorKey::getAbsoluteColumnIndices(int* const target) const
197{
198  int i = 0; /* index for filling the target array */
199  for (int block = 0; block < getNumberOfColumnBlocks(); block ++)
200  {
201    /* start with lowest bits, i.e. in block No. 0 */
202    /* the bits in this block of 32 bits: */
203    unsigned int blockBits = getColumnKey(block);
204    unsigned int shiftedBit = 1;
205    int exponent = 0;
206    /* The invariant "shiftedBit = 2^exponent" will hold throughout the
207       entire while loop. */
208    while (exponent < 32)
209    {
210      if (shiftedBit & blockBits) target[i++] = exponent + (32 * block);
211      shiftedBit = shiftedBit << 1;
212      exponent++;
213    }
214  }
215  return;
216}
217
218int MinorKey::getRelativeRowIndex(const int i) const
219{
220  /* This method is to return the relative (0-based) index of the row
221     with absolute index \c i.
222     Example: bit-pattern of rows: "10010001101", i = 7:
223        This should yield the 0-based relative index of the bit
224        corresponding to row no. 7, i.e. 3. */
225
226  int matchedBits = -1; /* counter for matched bits; this is going to
227                           contain our return value */
228  for (int block = 0; block < getNumberOfRowBlocks(); block ++)
229  {
230    /* start with lowest bits, i.e. in block No. 0 */
231    /* the bits in this block of 32 bits: */
232    unsigned int blockBits = getRowKey(block);
233    unsigned int shiftedBit = 1;
234    int exponent = 0;
235    /* The invariant "shiftedBit = 2^exponent" will hold throughout the
236       entire while loop. */
237    while (exponent < 32)
238    {
239      if (shiftedBit & blockBits) matchedBits++;
240      if (exponent + (32 * block) == i) return matchedBits;
241      shiftedBit = shiftedBit << 1;
242      exponent++;
243    }
244  }
245  /* We should never reach this line of code. */
246  assert(false);
247}
248
249int MinorKey::getRelativeColumnIndex(const int i) const
250{
251  /* This method is to return the relative (0-based) index
252     of the column with absolute index \c i.
253     Example: bit-pattern of columns: "10010001101", i = 7:
254        This should yield the 0-based relative index of the bit
255        corresponding to column no. 7, i.e. 3. */
256
257  int matchedBits = -1; /* counter for matched bits; this is going
258                           to contain our return value */
259  for (int block = 0; block < getNumberOfColumnBlocks(); block ++)
260  {
261    /* start with lowest bits, i.e. in block No. 0 */
262    /* the bits in this block of 32 bits: */
263    unsigned int blockBits = getColumnKey(block);
264    unsigned int shiftedBit = 1;
265    int exponent = 0;
266    /* The invariant "shiftedBit = 2^exponent" will hold
267       throughout the entire while loop. */
268    while (exponent < 32)
269    {
270      if (shiftedBit & blockBits) matchedBits++;
271      if (exponent + (32 * block) == i) return matchedBits;
272      shiftedBit = shiftedBit << 1;
273      exponent++;
274    }
275  }
276  /* We should never reach this line of code. */
277  assert(false);
278}
279
280unsigned int MinorKey::getRowKey(const int blockIndex) const
281{
282  return _rowKey[blockIndex];
283}
284
285unsigned int MinorKey::getColumnKey(const int blockIndex) const
286{
287  return _columnKey[blockIndex];
288}
289
290int MinorKey::getNumberOfRowBlocks() const
291{
292  return _numberOfRowBlocks;
293}
294
295int MinorKey::getNumberOfColumnBlocks() const
296{
297  return _numberOfColumnBlocks;
298}
299
300int MinorKey::getSetBits(const int a) const
301{
302  int b = 0;
303  if (a == 1)
304  { /* rows */
305    for (int i = 0; i < _numberOfRowBlocks; i++)
306    {
307      unsigned int m = _rowKey[i];
308      unsigned int k = 1;
309      for (int j = 0; j < 32; j++)
310      {
311        /* k = 2^j */
312        if (m & k) b++;
313        k = k << 1;
314      }
315    }
316  }
317  else
318  { /* columns */
319    for (int i = 0; i < _numberOfColumnBlocks; i++)
320    {
321      unsigned int m = _columnKey[i];
322      unsigned int k = 1;
323      for (int j = 0; j < 32; j++)
324      {
325        /* k = 2^j */
326        if (m & k) b++;
327        k = k << 1;
328      }
329    }
330  }
331  return b;
332}
333
334MinorKey MinorKey::getSubMinorKey (const int absoluteEraseRowIndex,
335                                   const int absoluteEraseColumnIndex) const
336{
337  int rowBlock = absoluteEraseRowIndex / 32;
338  int exponent = absoluteEraseRowIndex % 32;
339  unsigned int newRowBits = getRowKey(rowBlock) - (1 << exponent);
340  int highestRowBlock = getNumberOfRowBlocks() - 1;
341  /* highestRowBlock will finally contain the highest block index with
342     non-zero bit pattern */
343  if ((newRowBits == 0) && (rowBlock == highestRowBlock))
344  {
345    /* we have thus nullified the highest block;
346       we can now forget about the highest block... */
347    highestRowBlock -= 1;
348    while (getRowKey(highestRowBlock) == 0) /* ...and maybe even some more
349                                               zero-blocks */
350      highestRowBlock -= 1;
351  }
352  /* highestRowBlock now contains the highest row block index with non-zero
353     bit pattern */
354
355  int columnBlock = absoluteEraseColumnIndex / 32;
356  exponent = absoluteEraseColumnIndex % 32;
357  unsigned int newColumnBits = getColumnKey(columnBlock) - (1 << exponent);
358  int highestColumnBlock = getNumberOfColumnBlocks() - 1;
359  /* highestColumnBlock will finally contain the highest block index with
360     non-zero bit pattern */
361  if ((newColumnBits == 0) && (columnBlock == highestColumnBlock))
362  {
363    /* we have thus nullified the highest block;
364       we can now forget about the highest block... */
365    highestColumnBlock -= 1;
366    while (getColumnKey(highestColumnBlock) == 0) /* ...and maybe even some
367                                                     more zero-blocks */
368      highestColumnBlock -= 1;
369  }
370  /* highestColumnBlock now contains the highest column block index with
371     non-zero bit pattern */
372
373  MinorKey result(highestRowBlock + 1, _rowKey, highestColumnBlock + 1,
374                  _columnKey);
375  /* This is just a copy with maybe some leading bit blocks omitted. We still
376     need to re-define the row block at index 'rowBlock' and the column block
377     at index 'columnBlock': */
378  if ((newRowBits != 0) || (rowBlock < getNumberOfRowBlocks() - 1))
379    result.setRowKey(rowBlock, newRowBits);
380  if ((newColumnBits != 0) || (columnBlock < getNumberOfColumnBlocks() - 1))
381    result.setColumnKey(columnBlock, newColumnBits);
382
383  /* let's check that the number of selected rows and columns are equal;
384     (this check is only performed in the debug version) */
385  assume(result.getSetBits(1) == result.getSetBits(2));
386
387  return result;
388}
389
390void MinorKey::setRowKey (const int blockIndex, const unsigned int rowKey)
391{
392    _rowKey[blockIndex] = rowKey;
393}
394
395void MinorKey::setColumnKey (const int blockIndex,
396                             const unsigned int columnKey)
397{
398    _columnKey[blockIndex] = columnKey;
399}
400
401int MinorKey::compare (const MinorKey& that) const
402{
403  /* compare by rowKeys first; in case of equality, use columnKeys */
404  if (this->getNumberOfRowBlocks() < that.getNumberOfRowBlocks())
405    return -1;
406  if (this->getNumberOfRowBlocks() > that.getNumberOfRowBlocks())
407    return 1;
408  /* Here, numbers of rows are equal. */
409  for (int r = this->getNumberOfRowBlocks() - 1; r >= 0; r--)
410  {
411    if (this->getRowKey(r) < that.getRowKey(r)) return -1;
412    if (this->getRowKey(r) > that.getRowKey(r)) return 1;
413  }
414  /* Here, this and that encode ecaxtly the same sets of rows.
415     Now, we take a look at the columns. */
416  if (this->getNumberOfColumnBlocks() < that.getNumberOfColumnBlocks())
417    return -1;
418  if (this->getNumberOfColumnBlocks() > that.getNumberOfColumnBlocks())
419    return 1;
420  /* Here, numbers of columns are equal. */
421  for (int c = this->getNumberOfColumnBlocks() - 1; c >= 0; c--)
422  {
423    if (this->getColumnKey(c) < that.getColumnKey(c)) return -1;
424    if (this->getColumnKey(c) > that.getColumnKey(c)) return 1;
425  }
426  /* Here, this and that encode exactly the same sets of rows and columns. */
427  return 0;
428}
429
430/* just to make the compiler happy;
431   this method should never be called */
432bool MinorKey::operator==(const MinorKey& mk) const
433{
434  assert(false);
435  return this->compare(mk) == 0;
436}
437
438/* just to make the compiler happy;
439   this method should never be called */
440bool MinorKey::operator<(const MinorKey& mk) const
441{
442  assert(false);
443  return this->compare(mk) == -1;
444}
445
446void MinorKey::selectFirstRows (const int k, const MinorKey& mk)
447{
448  int hitBits = 0;      /* the number of bits we have hit; in the end, this
449                           has to be equal to k, the dimension of the minor */
450  int blockIndex = -1;  /* the index of the current int in mk */
451  unsigned int highestInt = 0;  /* the new highest block of this MinorKey */
452  /* We determine which ints of mk we can copy. Their indices will be
453     0, 1, ..., blockIndex - 1. And highestInt is going to capture the highest
454     int (which may be only a portion of the corresponding int in mk.
455     We loop until hitBits = k: */
456  while (hitBits < k)
457  {
458    blockIndex++;
459    highestInt = 0;
460    unsigned int currentInt = mk.getRowKey(blockIndex);
461    unsigned int shiftedBit = 1;
462    int exponent = 0;
463    /* invariant in the loop: shiftedBit = 2^exponent */
464    while (exponent < 32 && hitBits < k)
465    {
466      if (shiftedBit & currentInt)
467      {
468        highestInt += shiftedBit;
469        hitBits++;
470      }
471      shiftedBit = shiftedBit << 1;
472      exponent++;
473    }
474  }
475  /* free old memory */
476  delete [] _rowKey; _rowKey = 0;
477  _numberOfRowBlocks = blockIndex + 1;
478  /* allocate memory for new entries in _rowKey; */
479  _rowKey = new unsigned int[_numberOfRowBlocks];
480  /* copying values from mk to this MinorKey */
481  for (int r = 0; r < blockIndex; r++)
482    _rowKey[r] = mk.getRowKey(r);
483  _rowKey[blockIndex] = highestInt;
484}
485
486void MinorKey::selectFirstColumns (const int k, const MinorKey& mk)
487{
488  int hitBits = 0;      /* the number of bits we have hit; in the end, this
489                           has to be equal to k, the dimension of the minor */
490  int blockIndex = -1;  /* the index of the current int in mk */
491  unsigned int highestInt = 0;  /* the new highest block of this MinorKey */
492  /* We determine which ints of mk we can copy. Their indices will be
493     0, 1, ..., blockIndex - 1. And highestInt is going to capture the highest
494     int (which may be only a portion of the corresponding int in mk.
495     We loop until hitBits = k: */
496  while (hitBits < k)
497  {
498    blockIndex++;
499    highestInt = 0;
500    unsigned int currentInt = mk.getColumnKey(blockIndex);
501    unsigned int shiftedBit = 1;
502    int exponent = 0;
503    /* invariant in the loop: shiftedBit = 2^exponent */
504    while (exponent < 32 && hitBits < k)
505    {
506      if (shiftedBit & currentInt)
507      {
508        highestInt += shiftedBit;
509        hitBits++;
510      }
511      shiftedBit = shiftedBit << 1;
512      exponent++;
513    }
514  }
515  /* free old memory */
516  delete [] _columnKey; _columnKey = 0;
517  _numberOfColumnBlocks = blockIndex + 1;
518  /* allocate memory for new entries in _columnKey; */
519  _columnKey = new unsigned int[_numberOfColumnBlocks];
520  /*  copying values from mk to this MinorKey */
521  for (int c = 0; c < blockIndex; c++)
522    _columnKey[c] = mk.getColumnKey(c);
523  _columnKey[blockIndex] = highestInt;
524}
525
526bool MinorKey::selectNextRows (const int k, const MinorKey& mk)
527{
528  /* We need to compute the set of k rows which must all be contained in mk.
529     AND: This set must be the least possible of this kind which is larger
530          than the currently encoded set of rows. (Here, '<' is w.r.t. to the
531          natural ordering on multi-indices.
532     Example: mk encodes the rows according to the bit pattern 11010111,
533              k = 3, this MinorKey encodes 10010100. Then, the method must
534              shift the set of rows in this MinorKey to 11000001 (, and
535              return true). */
536
537  /* The next two variables will finally name a row which is
538     (1) currently not yet among the rows in this MinorKey, but
539     (2) among the rows in mk, and
540     (3) which is "higher" than the lowest row in this MinorKey, and
541     (4) which is the lowest possible choice such that (1) - (3) hold.
542     If we should not be able to find such a row, then there is no next
543     subset of rows. In this case, the method will return false; otherwise
544     always true. */
545  int newBitBlockIndex = 0;        /* the block index of the bit */
546  unsigned int newBitToBeSet = 0;  /* the bit as 2^e, where 0 <= e <= 31 */
547
548  /* number of ints (representing rows) in this MinorKey: */
549  int blockCount = this->getNumberOfRowBlocks();
550  /* for iterating along the blocks of mk: */
551  int mkBlockIndex = mk.getNumberOfRowBlocks();
552
553  int hitBits = 0;    /* the number of bits we have hit */
554  int bitCounter = 0; /* for storing the number of bits hit before a
555                         specific moment; see below */
556
557  while (hitBits < k)
558  {
559    mkBlockIndex--;
560    unsigned int currentInt = mk.getRowKey(mkBlockIndex);
561    unsigned int shiftedBit = 1 << 31; /* initially, this equals 2^31, i.e.
562                                          the highest bit */
563    while (hitBits < k && shiftedBit > 0)
564    {
565      if ((blockCount - 1 >= mkBlockIndex) &&
566        (shiftedBit & this->getRowKey(mkBlockIndex))) hitBits++;
567      else if (shiftedBit & currentInt)
568      {
569        newBitToBeSet = shiftedBit;
570        newBitBlockIndex = mkBlockIndex;
571        bitCounter = hitBits; /* So, whenever we set newBitToBeSet, we want
572                                 to remember the momentary number of hit
573                                 bits. This will later be needed; see below. */
574      }
575      shiftedBit = shiftedBit >> 1;
576    }
577  }
578
579  if (newBitToBeSet == 0)
580  {
581    return false;
582  }
583  else
584  {
585    /* Note that the following must hold when reaching this line of code:
586       (1) The row with bit newBitToBeSet in this->getRowKey(newBitBlockIndex)
587           is currently not among the rows in this MinorKey, but
588       (2) it is among the rows in mk, and
589       (3) it is higher than the lowest row in this MinorKey, and
590       (4) it is the lowest possible choice such that (1) - (3) hold.
591       In the above example, we would reach this line with
592       newBitToBeSet == 2^6 and bitCounter == 1 (resulting from the bit 2^7).
593       */
594
595    if (blockCount - 1 < newBitBlockIndex)
596    { /* In this case, _rowKey is too small. */
597      /* free old memory */
598      delete [] _rowKey; _rowKey = 0;
599      _numberOfRowBlocks = newBitBlockIndex + 1;
600      /* allocate memory for new entries in _rowKey; */
601      _rowKey = new unsigned int[_numberOfRowBlocks];
602    }
603    else
604    {
605      /* We need to delete all bits in _rowKey[newBitBlockIndex] that are
606         below newBitToBeSet: */
607      unsigned int anInt = this->getRowKey(newBitBlockIndex);
608      unsigned int deleteBit = newBitToBeSet >> 1; // in example: = 2^5
609      while (deleteBit > 0)
610      {
611        if (anInt & deleteBit) anInt -= deleteBit;
612        deleteBit = deleteBit >> 1;
613      };
614      _rowKey[newBitBlockIndex] = anInt;
615      /* ...and we delete all entries in _rowKey[i] for
616         0 <= i < newBitBlockIndex */
617      for (int i = 0; i < newBitBlockIndex; i++)
618        _rowKey[i] = 0;
619    }
620
621    /* We have now deleted all bits from _rowKey[...] below the bit
622       2^newBitToBeSet.
623       In the example we shall have at this point: _rowKey[...] = 10000000.
624       Now let's set the new bit: */
625    _rowKey[newBitBlockIndex] += newBitToBeSet;
626    /* in the example: _rowKey[newBitBlockIndex] = 11000000 */
627    bitCounter++; /* This is now the number of correct bits in _rowKey[...];
628                     i.e. in the example this will be equal to 2. */
629
630    /* Now we only need to fill _rowKey[...] with the lowest possible bits
631       until it consists of exactly k bits. (We know that we need to set
632       exactly (k - bitCounter) additional bits.) */
633    mkBlockIndex = -1;
634    while (bitCounter < k)
635    {
636      mkBlockIndex++;
637      unsigned int currentInt = mk.getRowKey(mkBlockIndex);
638      unsigned int shiftedBit = 1;
639      int exponent = 0;
640      /* invariant: shiftedBit = 2^exponent */
641      while (bitCounter < k && exponent < 32)
642      {
643        if (shiftedBit & currentInt)
644        {
645          _rowKey[mkBlockIndex] += shiftedBit;
646          bitCounter++;
647        };
648        shiftedBit = shiftedBit << 1;
649        exponent++;
650      }
651    };
652    /* in the example, we shall obtain _rowKey[...] = 11000001 */
653
654    return true;
655  }
656}
657
658bool MinorKey::selectNextColumns (const int k, const MinorKey& mk)
659{
660  /* We need to compute the set of k columns which must all be contained in mk.
661     AND: This set must be the least possible of this kind which is larger
662          than the currently encoded set of columns. (Here, '<' is w.r.t. to
663          the natural ordering on multi-indices.
664     Example: mk encodes the columns according to the bit pattern 11010111,
665              k = 3, this MinorKey encodes 10010100. Then, the method must
666              shift the set of columns in this MinorKey to 11000001 (, and
667              return true). */
668
669  /* The next two variables will finally name a columns which is
670     (1) currently not yet among the columns in this MinorKey, but
671     (2) among the columns in mk, and
672     (3) which is "higher" than the lowest columns in this MinorKey, and
673     (4) which is the lowest possible choice such that (1) - (3) hold.
674     If we should not be able to find such a columns, then there is no next
675     subset of columns. In this case, the method will return false; otherwise
676     always true. */
677  int newBitBlockIndex = 0;        /* the block index of the bit */
678  unsigned int newBitToBeSet = 0;  /* the bit as 2^e, where 0 <= e <= 31 */
679
680   /* number of ints (representing columns) in this MinorKey: */
681  int blockCount = this->getNumberOfColumnBlocks();
682  /* for iterating along the blocks of mk: */
683  int mkBlockIndex = mk.getNumberOfColumnBlocks();
684
685  int hitBits = 0;    /* the number of bits we have hit */
686  int bitCounter = 0; /* for storing the number of bits hit before a specific
687                         moment; see below */
688
689  while (hitBits < k) 
690  {
691    mkBlockIndex--;
692    unsigned int currentInt = mk.getColumnKey(mkBlockIndex);
693    unsigned int shiftedBit = 1 << 31; /* initially, this equals 2^31, i.e.
694                                          the highest bit */
695    while (hitBits < k && shiftedBit > 0)
696    {
697      if ((blockCount - 1 >= mkBlockIndex) &&
698        (shiftedBit & this->getColumnKey(mkBlockIndex))) hitBits++;
699      else if (shiftedBit & currentInt) 
700      {
701        newBitToBeSet = shiftedBit;
702        newBitBlockIndex = mkBlockIndex;
703        bitCounter = hitBits; /* So, whenever we set newBitToBeSet, we want to
704                                 remember the momentary number of hit bits.
705                                 This will later be needed; see below. */
706      }
707      shiftedBit = shiftedBit >> 1;
708    }
709  }
710
711  if (newBitToBeSet == 0)
712  {
713    return false;
714  }
715  else
716  {
717    /* Note that the following must hold when reaching this line of code:
718       (1) The columns with bit newBitToBeSet in
719           this->getColumnKey(newBitBlockIndex) is currently not among the
720           columns in this MinorKey, but
721       (2) it is among the columns in mk, and
722       (3) it is higher than the lowest columns in this MinorKey, and
723       (4) it is the lowest possible choice such that (1) - (3) hold.
724       In the above example, we would reach this line with
725       newBitToBeSet == 2^6 and bitCounter == 1 (resulting from the bit 2^7).
726       */
727
728    if (blockCount - 1 < newBitBlockIndex)
729    { /* In this case, _columnKey is too small. */
730        /* free old memory */
731        delete [] _columnKey; _columnKey = 0;
732        _numberOfColumnBlocks = newBitBlockIndex + 1;
733        /* allocate memory for new entries in _columnKey; */
734        _columnKey = new unsigned int[_numberOfColumnBlocks];
735    }
736    else
737    {
738      /* We need to delete all bits in _columnKey[newBitBlockIndex] that are
739         below newBitToBeSet: */
740      unsigned int anInt = this->getColumnKey(newBitBlockIndex);
741      unsigned int deleteBit = newBitToBeSet >> 1; /* in example: = 2^5 */
742      while (deleteBit > 0)
743      {
744        if (anInt & deleteBit) anInt -= deleteBit;
745        deleteBit = deleteBit >> 1;
746      };
747      _columnKey[newBitBlockIndex] = anInt;
748      /* ...and we delete all entries in _columnKey[i] fo
749         0 <= i < newBitBlockIndex */
750      for (int i = 0; i < newBitBlockIndex; i++)
751        _columnKey[i] = 0;
752    }
753
754    /* We have now deleted all bits from _columnKey[...] below the bit
755       2^newBitToBeSet. In the example we shall have at this point:
756       _columnKey[...] = 10000000. Now let's set the new bit: */
757    _columnKey[newBitBlockIndex] += newBitToBeSet;
758    /* in the example: _columnKey[newBitBlockIndex] = 11000000 */
759    bitCounter++; /* This is now the number of correct bits in
760                     _columnKey[...]; i.e. in the example this will be equal
761                     to 2. */
762
763    /* Now we only need to fill _columnKey[...] with the lowest possible bits
764       until it consists of exactly k bits. (We know that we need to set
765       exactly (k - bitCounter) additional bits.) */
766    mkBlockIndex = -1;
767    while (bitCounter < k)
768    {
769      mkBlockIndex++;
770      unsigned int currentInt = mk.getColumnKey(mkBlockIndex);
771      unsigned int shiftedBit = 1;
772      int exponent = 0;
773      /* invariant: shiftedBit = 2^exponent */
774      while (bitCounter < k && exponent < 32)
775      {
776        if (shiftedBit & currentInt)
777        {
778          _columnKey[mkBlockIndex] += shiftedBit;
779          bitCounter++;
780        };
781        shiftedBit = shiftedBit << 1;
782        exponent++;
783      }
784    };
785    /* in the example, we shall obtain _columnKey[...] = 11000001 */
786
787    return true;
788  }
789}
790
791string MinorKey::toString() const
792{
793  char h[32];
794  string t = "";
795  string s = "(";
796  unsigned int z = 0;
797  for (int r = this->getNumberOfRowBlocks() - 1; r >= 0; r--)
798  {
799    z = this->getRowKey(r);
800    while (z != 0)
801    {
802      if ((z % 2) != 0) t = "1" + t; else t = "0" + t;
803      z = z / 2;
804    }
805    if (r < this->getNumberOfRowBlocks() - 1)
806      t = string(32 - t.length(), '0') + t;
807    s += t;
808  }
809  s += ", ";
810  t = "";
811  for (int c = this->getNumberOfColumnBlocks() - 1; c >= 0; c--)
812  {
813    z = this->getColumnKey(c);
814    while (z != 0)
815    {
816      if ((z % 2) != 0) t = "1" + t; else t = "0" + t;
817      z = z / 2;
818    }
819    if (c < this->getNumberOfColumnBlocks() - 1)
820      t = string(32 - t.length(), '0') + t;
821    s += t;
822  }
823  s += ")";
824  return s;
825}
826
827int MinorValue::_RankingStrategy = -1;
828
829int MinorValue::getWeight () const
830{
831  assert(false);  /* must be overridden in derived classes */
832  return 0;
833}
834
835/* just to make the compiler happy;
836   this method should never be called */
837bool MinorValue::operator==(const MinorValue& mv) const
838{
839  assert(false);
840  return (this == &mv);  /* compare addresses of both objects */
841}
842
843string MinorValue::toString () const
844{
845  assert(false);  /* must be overridden in derived classes */
846  return "";
847}
848
849/* just to make the compiler happy;
850   this method should never be called */
851bool MinorValue::operator<(const MinorValue& mv) const
852{
853  assert(false);
854  return (this < &mv);  /* compare addresses of both objects */
855}
856
857int MinorValue::getRetrievals() const
858{
859  return _retrievals;
860}
861
862void MinorValue::incrementRetrievals()
863{
864  _retrievals++;
865}
866
867int MinorValue::getPotentialRetrievals() const
868{
869  return _potentialRetrievals;
870}
871
872int MinorValue::getMultiplications() const
873{
874  return _multiplications;
875}
876
877int MinorValue::getAdditions() const
878{
879  return _additions;
880}
881
882int MinorValue::getAccumulatedMultiplications() const
883{
884  return _accumulatedMult;
885}
886
887int MinorValue::getAccumulatedAdditions() const
888{
889  return _accumulatedSum;
890}
891
892void MinorValue::print() const
893{
894  cout << this->toString();
895}
896
897
898void MinorValue::SetRankingStrategy (const int rankingStrategy)
899{
900  _RankingStrategy = rankingStrategy;
901  if (_RankingStrategy == 6)
902  {
903    /* initialize the random generator with system time */
904    srand ( time(NULL) );
905  }
906}
907
908int MinorValue::GetRankingStrategy()
909{
910  return _RankingStrategy;
911}
912
913/* this is for generically accessing the rank measure regardless of
914   which strategy has been set */
915int MinorValue::getUtility () const
916{
917  switch (this->GetRankingStrategy())
918  {
919    case 1: return this->rankMeasure1();
920    case 2: return this->rankMeasure2();
921    case 3: return this->rankMeasure3();
922    case 4: return this->rankMeasure4();
923    case 5: return this->rankMeasure5();
924    default: return this->rankMeasure1();
925  }
926}
927
928/* here are some sensible caching strategies: */
929int MinorValue::rankMeasure1 () const
930{
931  /* number of actually performed multiplications */
932  return this->getMultiplications();
933}
934
935int MinorValue::rankMeasure2 () const
936{
937  /* accumulated number of performed multiplications, i.e. all including
938     nested multiplications */
939  return this->getAccumulatedMultiplications();
940}
941
942int MinorValue::rankMeasure3 () const
943{
944  /* number of performed multiplications, weighted with the ratio of
945     not yet performed retrievals over the maximal number of retrievals */
946  return this->getMultiplications()
947         * (this->getPotentialRetrievals()
948         - this->getRetrievals())
949         / this->getPotentialRetrievals();
950}
951
952int MinorValue::rankMeasure4 () const
953{
954  /* number of performed multiplications,
955     multiplied with the number of not yet performed retrievals */
956  return this->getMultiplications()
957         * (this->getPotentialRetrievals()
958         - this->getRetrievals());
959}
960
961int MinorValue::rankMeasure5 () const
962{
963  /* number of not yet performed retrievals;
964     tends to cache entries longer when they are going to be retrieved more
965     often in the future */
966  return this->getPotentialRetrievals() - this->getRetrievals();
967}
968
969int IntMinorValue::getWeight () const
970{
971  /* put measure for size of MinorValue here, i.e. number of monomials in
972     polynomial; so far, we use the accumulated number of multiplications
973     (i.e., including all nested ones) to simmulate the size of a polynomial */
974  return _accumulatedMult;
975}
976
977IntMinorValue::IntMinorValue (const int result, const int multiplications,
978                              const int additions,
979                              const int accumulatedMultiplications,
980                              const int accumulatedAdditions,
981                              const int retrievals,
982                              const int potentialRetrievals)
983{
984  _result = result;
985  _multiplications = multiplications;
986  _additions = additions;
987  _accumulatedMult = accumulatedMultiplications;
988  _accumulatedSum = accumulatedAdditions;
989  _potentialRetrievals = potentialRetrievals;
990  _retrievals = retrievals;
991}
992
993IntMinorValue::IntMinorValue ()
994{
995  _result = -1;
996  _multiplications = -1;
997  _additions = -1;
998  _accumulatedMult = -1;
999  _accumulatedSum = -1;
1000  _potentialRetrievals = -1;
1001  _retrievals = -1;
1002}
1003
1004IntMinorValue::~IntMinorValue()
1005{
1006}
1007
1008int IntMinorValue::getResult() const
1009{
1010  return _result;
1011}
1012
1013string IntMinorValue::toString () const
1014{
1015  char h[10];
1016
1017  /* Let's see whether a cache has been used to compute this MinorValue: */
1018  bool cacheHasBeenUsed = true;
1019  if (this->getRetrievals() == -1) cacheHasBeenUsed = false;
1020
1021  sprintf(h, "%d", this->getResult());
1022  string s = h;
1023  s += " [retrievals: ";
1024  if (cacheHasBeenUsed) { sprintf(h, "%d", this->getRetrievals()); s += h; }
1025  else s += "/";
1026  s += " (of ";
1027  if (cacheHasBeenUsed)
1028  {
1029    sprintf(h, "%d", this->getPotentialRetrievals());
1030    s += h;
1031  }
1032  else s += "/";
1033  s += "), *: ";
1034  sprintf(h, "%d", this->getMultiplications()); s += h;
1035  s += " (accumulated: ";
1036  sprintf(h, "%d", this->getAccumulatedMultiplications()); s += h;
1037  s += "), +: ";
1038  sprintf(h, "%d", this->getAdditions()); s += h;
1039  s += " (accumulated: ";
1040  sprintf(h, "%d", this->getAccumulatedAdditions()); s += h;
1041  s += "), rank: ";
1042  if (cacheHasBeenUsed) { sprintf(h, "%d", this->getUtility()); s += h; }
1043  else s += "/";
1044  s += "]";
1045  return s;
1046}
1047
1048IntMinorValue::IntMinorValue (const IntMinorValue& mv)
1049{
1050  _result = mv.getResult();
1051  _retrievals = mv.getRetrievals();
1052  _potentialRetrievals = mv.getPotentialRetrievals();
1053  _multiplications = mv.getMultiplications();
1054  _additions = mv.getAdditions();
1055  _accumulatedMult = mv.getAccumulatedMultiplications();
1056  _accumulatedSum = mv.getAccumulatedAdditions();
1057}
1058
1059PolyMinorValue::PolyMinorValue (const poly result, const int multiplications,
1060                                const int additions,
1061                                const int accumulatedMultiplications,
1062                                const int accumulatedAdditions,
1063                                const int retrievals,
1064                                const int potentialRetrievals)
1065{
1066  _result = pCopy(result);
1067  _multiplications = multiplications;
1068  _additions = additions;
1069  _accumulatedMult = accumulatedMultiplications;
1070  _accumulatedSum = accumulatedAdditions;
1071  _potentialRetrievals = potentialRetrievals;
1072  _retrievals = retrievals;
1073}
1074
1075PolyMinorValue::PolyMinorValue ()
1076{
1077  _result = NULL;
1078  _multiplications = -1;
1079  _additions = -1;
1080  _accumulatedMult = -1;
1081  _accumulatedSum = -1;
1082  _potentialRetrievals = -1;
1083  _retrievals = -1;
1084}
1085
1086PolyMinorValue::~PolyMinorValue()
1087{
1088  p_Delete(&_result, currRing);
1089}
1090
1091poly PolyMinorValue::getResult() const
1092{
1093  return _result;
1094}
1095
1096int PolyMinorValue::getWeight () const
1097{
1098  /* put measure for size of PolyMinorValue here, e.g. the number of monomials
1099     in the cached polynomial */
1100  return pLength(_result); // the number of monomials in the polynomial
1101}
1102
1103string PolyMinorValue::toString () const
1104{
1105  char h[20];
1106
1107  /* Let's see whether a cache has been used to compute this MinorValue: */
1108  bool cacheHasBeenUsed = true;
1109  if (this->getRetrievals() == -1) cacheHasBeenUsed = false;
1110
1111  string s = pString(_result);
1112  s += " [retrievals: ";
1113  if (cacheHasBeenUsed) { sprintf(h, "%d", this->getRetrievals()); s += h; }
1114  else s += "/";
1115  s += " (of ";
1116  if (cacheHasBeenUsed)
1117  {
1118    sprintf(h, "%d", this->getPotentialRetrievals());
1119    s += h;
1120  }
1121  else s += "/";
1122  s += "), *: ";
1123  sprintf(h, "%d", this->getMultiplications()); s += h;
1124  s += " (accumulated: ";
1125  sprintf(h, "%d", this->getAccumulatedMultiplications()); s += h;
1126  s += "), +: ";
1127  sprintf(h, "%d", this->getAdditions()); s += h;
1128  s += " (accumulated: ";
1129  sprintf(h, "%d", this->getAccumulatedAdditions()); s += h;
1130  s += "), rank: ";
1131  if (cacheHasBeenUsed) { sprintf(h, "%d", this->getUtility()); s += h; }
1132  else s += "/";
1133  s += "]";
1134  return s;
1135}
1136
1137PolyMinorValue::PolyMinorValue (const PolyMinorValue& mv)
1138{
1139  _result = pCopy(mv.getResult());
1140  _retrievals = mv.getRetrievals();
1141  _potentialRetrievals = mv.getPotentialRetrievals();
1142  _multiplications = mv.getMultiplications();
1143  _additions = mv.getAdditions();
1144  _accumulatedMult = mv.getAccumulatedMultiplications();
1145  _accumulatedSum = mv.getAccumulatedAdditions();
1146}
1147
1148void PolyMinorValue::operator= (const PolyMinorValue& mv)
1149{
1150  if (_result != mv.getResult()) pDelete(&_result);
1151  _result = pCopy(mv.getResult());
1152  _retrievals = mv.getRetrievals();
1153  _potentialRetrievals = mv.getPotentialRetrievals();
1154  _multiplications = mv.getMultiplications();
1155  _additions = mv.getAdditions();
1156  _accumulatedMult = mv.getAccumulatedMultiplications();
1157  _accumulatedSum = mv.getAccumulatedAdditions();
1158}
Note: See TracBrowser for help on using the repository browser.