diff options
Diffstat (limited to 'common/utility/CombinadicIterator.C')
-rw-r--r-- | common/utility/CombinadicIterator.C | 104 |
1 files changed, 104 insertions, 0 deletions
diff --git a/common/utility/CombinadicIterator.C b/common/utility/CombinadicIterator.C new file mode 100644 index 0000000..15152cb --- /dev/null +++ b/common/utility/CombinadicIterator.C @@ -0,0 +1,104 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA is distributed in the hope that it will be useful, but +// WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#include <cassert> +#include <algorithm> + +#include "CombinadicIterator.H" + +using namespace std; + +CombinadicIterator::CombinadicIterator + (unsigned populationSize, unsigned sampleSize, Array<unsigned>relevant) : + populationSize(populationSize), + relevant(relevant), + notRelevant(populationSize - relevant.getSize()), + minimumRelevance(max((int)sampleSize - (int)notRelevant.getSize(), 1)), + maximumRelevance(min(relevant.getSize(), sampleSize)), + choiceFromRelevant(combinadic.begin(maximumRelevance)), + choiceFromNotRelevant(combinadic.begin(sampleSize - maximumRelevance)), + relevantCombination(sampleSize), + combination(sampleSize) { + assert(sampleSize <= populationSize); + for (unsigned i = 0, j = 0, k = 0; i < notRelevant.getSize(); ++i, ++j) { + while (k < relevant.getSize() && relevant[k] == j) { + ++j; + ++k; + } + notRelevant[i] = j; + } + updateCombinationFromRelevant(); + updateCombination(); +} + +void CombinadicIterator::updateCombinationFromRelevant() { + for (unsigned i = maximumRelevance; i--;) { + relevantCombination[i] = relevant[choiceFromRelevant[i]]; + } +} + +void CombinadicIterator::updateCombination() { + for (unsigned i = combination.getSize(); i-- > maximumRelevance;) { + combination[i] = notRelevant[choiceFromNotRelevant[i - maximumRelevance]]; + } + for (unsigned i = maximumRelevance; i--;) { + combination[i] = relevantCombination[i]; + } + sort(combination + 0, combination + combination.getSize()); +} + +const Array<unsigned>CombinadicIterator::operator *() const { +#ifndef NDEBUG + for (unsigned i = combination.getSize(); --i;) { + assert(combination[i - 1] < combination[i]); + } +#endif + return combination; +} + +CombinadicIterator::operator bool() const { + return combination.getSize(); +} + +CombinadicIterator&CombinadicIterator::operator ++() { + if (!combination.getSize()) { + return *this; + } + bool someFromNotRelevant = choiceFromNotRelevant.getSize(); + if (someFromNotRelevant) { + combinadic.next(choiceFromNotRelevant); + } + if (!someFromNotRelevant || + choiceFromNotRelevant[choiceFromNotRelevant.getSize() - 1] >= + populationSize - relevant.getSize()) { + combinadic.next(choiceFromRelevant); + if (choiceFromRelevant[maximumRelevance - 1] >= relevant.getSize()) { + --maximumRelevance; + if (maximumRelevance < minimumRelevance) { + combination = Array<unsigned>(0); + return *this; + } + choiceFromRelevant = combinadic.begin(maximumRelevance); + } + updateCombinationFromRelevant(); + choiceFromNotRelevant = + combinadic.begin(combination.getSize() - maximumRelevance); + } + updateCombination(); + return *this; +} |