| 667 | } |
| 668 | |
| 669 | bool MinorKey::selectNextColumns (const int k, const MinorKey& mk) |
| 670 | { |
| 671 | /* We need to compute the set of k columns which must all be contained in mk. |
| 672 | AND: This set must be the least possible of this kind which is larger |
| 673 | than the currently encoded set of columns. (Here, '<' is w.r.t. to |
| 674 | the natural ordering on multi-indices. |
| 675 | Example: mk encodes the columns according to the bit pattern 11010111, |
| 676 | k = 3, this MinorKey encodes 10010100. Then, the method must |
| 677 | shift the set of columns in this MinorKey to 11000001 (, and |
| 678 | return true). */ |
| 679 | |
| 680 | /* The next two variables will finally name a column which is |
| 681 | (1) currently not yet among the columns in this MinorKey, but |
| 682 | (2) among the columns in mk, and |
| 683 | (3) which is "higher" than the lowest column in this MinorKey, and |
| 684 | (4) which is the lowest possible choice such that (1) - (3) hold. |
| 685 | If we should not be able to find such a column, then there is no next |
| 686 | subset of columns. In this case, the method will return false; otherwise |
| 687 | always true. */ |
| 688 | int newBitBlockIndex = 0; /* the block index of the bit */ |
| 689 | unsigned int newBitToBeSet = 0; /* the bit as 2^e, where 0 <= e <= 31 */ |
| 690 | |
| 691 | /* number of ints (representing columns) in this MinorKey: */ |
| 692 | int blockCount = this->getNumberOfColumnBlocks(); |
| 693 | /* for iterating along the blocks of mk: */ |
| 694 | int mkBlockIndex = mk.getNumberOfColumnBlocks(); |
| 695 | |
| 696 | int hitBits = 0; /* the number of bits we have hit */ |
| 697 | int bitCounter = 0; /* for storing the number of bits hit before a specific |
| 698 | moment; see below */ |
| 699 | while (hitBits < k) |
| 700 | { |
| 701 | mkBlockIndex--; |
| 702 | unsigned int currentInt = mk.getColumnKey(mkBlockIndex); |
| 703 | unsigned int shiftedBit = 1 << 31; /* initially, this equals 2^31, i.e. |
| 704 | the highest bit */ |
| 705 | while (hitBits < k && shiftedBit > 0) |
| 706 | { |
| 707 | if ((blockCount - 1 >= mkBlockIndex) && |
| 708 | (shiftedBit & this->getColumnKey(mkBlockIndex))) hitBits++; |
| 709 | else if (shiftedBit & currentInt) |
| 710 | { |
| 711 | newBitToBeSet = shiftedBit; |
| 712 | newBitBlockIndex = mkBlockIndex; |
| 713 | bitCounter = hitBits; /* So, whenever we set newBitToBeSet, we want to |
| 714 | remember the momentary number of hit bits. |
| 715 | This will later be needed; see below. */ |
| 716 | } |
| 717 | shiftedBit = shiftedBit >> 1; |
| 718 | } |
| 719 | } |
| 720 | if (newBitToBeSet == 0) |
| 721 | { |
| 722 | return false; |
| 723 | } |
| 724 | else |
| 725 | { |
| 726 | /* Note that the following must hold when reaching this line of code: |
no test coverage detected