summaryrefslogtreecommitdiff
path: root/casa/covering
diff options
context:
space:
mode:
Diffstat (limited to 'casa/covering')
-rw-r--r--casa/covering/bookkeeping/Coverage.H313
-rw-r--r--casa/covering/bookkeeping/Options.C102
-rw-r--r--casa/covering/bookkeeping/Options.H50
-rw-r--r--casa/covering/cost/CoverageCost.H72
-rw-r--r--casa/covering/filter/CoveringArrayAnnealingFilter.H49
-rw-r--r--casa/covering/goal/CoverageGoal.H43
-rw-r--r--casa/covering/heuristic/CoveringArrayHeuristic.H37
-rw-r--r--casa/covering/report/IterationReport.H53
-rw-r--r--casa/covering/space/CoveringArraySpace.C80
-rw-r--r--casa/covering/space/CoveringArraySpace.H52
-rw-r--r--casa/covering/space/GraftSpace.C187
-rw-r--r--casa/covering/space/GraftSpace.H60
-rw-r--r--casa/covering/space/SingleChangeSpace.C175
-rw-r--r--casa/covering/space/SingleChangeSpace.H61
-rw-r--r--casa/covering/state/CoveringArray.C274
-rw-r--r--casa/covering/state/CoveringArray.H166
-rw-r--r--casa/covering/state/CoveringArrayEntry.C102
-rw-r--r--casa/covering/state/CoveringArrayRow.C113
-rw-r--r--casa/covering/state/CoveringArraySubRow.C129
19 files changed, 2118 insertions, 0 deletions
diff --git a/casa/covering/bookkeeping/Coverage.H b/casa/covering/bookkeeping/Coverage.H
new file mode 100644
index 0000000..c0ce2b3
--- /dev/null
+++ b/casa/covering/bookkeeping/Coverage.H
@@ -0,0 +1,313 @@
+// 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/>.
+
+
+#ifndef COVERAGE_H
+#define COVERAGE_H
+
+#include "PascalTriangle.H"
+#include "Combinadic.H"
+
+#include "SubstitutionArray.H"
+
+#include "covering/bookkeeping/Options.H"
+
+template<class T>class Coverage {
+protected:
+ unsigned strength;
+ Options options;
+ // The offsets are indices into the contents array; entry offsets[i], where i
+ // is the combinadic encoding of a set of columns, is the beginning of the
+ // contents for that column set's t-sets.
+ Array<unsigned> offsets;
+ SubstitutionArray<T> contents;
+
+public:
+ Coverage(unsigned strength, Options options) :
+ strength(strength),
+ options(options),
+ offsets(triangle.nCr(options.getSize(), strength)) {
+ unsigned size = 0;
+ unsigned offsetIndex = 0;
+ for (Array<unsigned>columns = combinadic.begin(strength);
+ columns[strength - 1] < options.getSize();
+ combinadic.next(columns)) {
+ unsigned blockSize = 1;
+ for (unsigned i = strength; i--;) {
+ blockSize *= options.getSymbolCount(columns[i]);
+ }
+ offsets[offsetIndex++] = size;
+ size += blockSize;
+ }
+ contents = Array<T>(size);
+ }
+
+ Coverage(const Coverage&copy) :
+ strength(copy.strength),
+ options(copy.options),
+ offsets(copy.offsets),
+ contents(copy.contents) {}
+
+protected:
+ // The method encode, in its various forms, is responsible for converting a
+ // sorted t-set to an index into the contents array.
+
+ // These hinted versions of encode are for when some information has already
+ // been computed. indexHint is the combinadic encoding of the set of columns;
+ // columnsHint is this set of columns in sorted order; firstsHint is an array
+ // of corresponding first symbols; and countsHint is an array of symbol counts
+ // for each column.
+ unsigned encode
+ (unsigned indexHint,
+ Array<unsigned>columnsHint,
+ Array<unsigned>firstsHint,
+ Array<unsigned>countsHint,
+ Array<unsigned>sortedCombination) const {
+ assert(sortedCombination.getSize() == strength);
+ assert(indexHint < offsets.getSize());
+ unsigned offset = offsets[indexHint];
+ unsigned index = 0;
+ for (unsigned i = strength; i--;) {
+ unsigned column = columnsHint[i];
+ unsigned base = firstsHint[column];
+ unsigned count = countsHint[column];
+ index *= count;
+ index += sortedCombination[i] - base;
+ }
+ return offset + index;
+ }
+
+ unsigned encode
+ (Array<unsigned>columnsHint,
+ Array<unsigned>firstsHint,
+ Array<unsigned>countsHint,
+ Array<unsigned>sortedCombination) const {
+ return encode
+ (combinadic.encode(columnsHint),
+ columnsHint,
+ firstsHint,
+ countsHint,
+ sortedCombination);
+ }
+
+ unsigned encode(Array<unsigned>sortedCombination) const {
+ assert(sortedCombination.getSize() == strength);
+ Array<unsigned>columns(strength);
+ for (unsigned i = strength; i--;) {
+ columns[i] = options.getOption(sortedCombination[i]);
+ }
+ unsigned offsetIndex = combinadic.encode(columns);
+ assert(offsetIndex < offsets.getSize());
+ unsigned offset = offsets[offsetIndex];
+ unsigned index = 0;
+ for (unsigned i = strength; i--;) {
+ unsigned column = columns[i];
+ unsigned base = options.getFirstSymbol(column);
+ unsigned count = options.getSymbolCount(column);
+ index *= count;
+ index += sortedCombination[i] - base;
+ }
+ return offset + index;
+ }
+
+ // The method decode, of course, does the opposite of encode.
+ Array<unsigned>decode(unsigned encoding) const {
+ unsigned offsetIndex = offsets.getSize();
+ while (offsets[--offsetIndex] > encoding);
+ unsigned index = encoding - offsets[offsetIndex];
+ Array<unsigned>columns = combinadic.decode(offsetIndex, strength);
+ Array<unsigned>result(strength);
+ for (unsigned i = 0; i < strength; ++i) {
+ unsigned column = columns[i];
+ unsigned base = options.getFirstSymbol(column);
+ unsigned count = options.getSymbolCount(column);
+ unsigned digit = index % count;
+ index -= digit;
+ index /= count;
+ result[i] = base + digit;
+ }
+ assert(encode(result) == encoding);
+ return result;
+ }
+
+public:
+ unsigned getStrength() const {
+ return strength;
+ }
+ const Options&getOptions() const {
+ return options;
+ }
+
+ class Entry{
+ protected:
+ Coverage& owner;
+ unsigned index;
+ public:
+ Entry(const Coverage&owner,unsigned index) :
+ owner(const_cast<Coverage&>(owner)),
+ index(index) {}
+ operator T() const {
+ return owner.contents[index];
+ }
+ Entry&operator =(const T&value) {
+ owner.contents[index] = value;
+ return *this;
+ }
+ Entry&operator --() {
+ --owner.contents[index];
+ return *this;
+ }
+ Entry&operator ++() {
+ ++owner.contents[index];
+ return *this;
+ }
+ };
+
+ const Entry operator[](Array<unsigned>sortedCombination) const {
+ return Entry(*this, encode(sortedCombination));
+ }
+ Entry operator [](Array<unsigned>sortedCombination) {
+ return Entry(*this, encode(sortedCombination));
+ }
+
+ // The methods named hintGet work like the [] operator with the aforementioned
+ // hints.
+ const Entry hintGet
+ (unsigned indexHint,
+ Array<unsigned>columnsHint,
+ Array<unsigned>firstsHint,
+ Array<unsigned>countsHint,
+ Array<unsigned>sortedCombination) const {
+ return Entry
+ (*this,
+ encode
+ (indexHint, columnsHint, firstsHint, countsHint, sortedCombination));
+ }
+
+ Entry hintGet
+ (unsigned indexHint,
+ Array<unsigned>columnsHint,
+ Array<unsigned>firstsHint,
+ Array<unsigned>countsHint,
+ Array<unsigned>sortedCombination) {
+ return Entry
+ (*this,
+ encode
+ (indexHint, columnsHint, firstsHint, countsHint, sortedCombination));
+ }
+
+ const Entry hintGet
+ (Array<unsigned>columnsHint,
+ Array<unsigned>firstsHint,
+ Array<unsigned>countsHint,
+ Array<unsigned>sortedCombination) const {
+ return Entry
+ (*this,
+ encode(columnsHint, firstsHint, countsHint, sortedCombination));
+ }
+
+ Entry hintGet
+ (Array<unsigned>columnsHint,
+ Array<unsigned>firstsHint,
+ Array<unsigned>countsHint,
+ Array<unsigned>sortedCombination) {
+ return Entry
+ (*this,
+ encode(columnsHint, firstsHint, countsHint, sortedCombination));
+ }
+
+ class iterator {
+ protected:
+ Coverage& owner;
+ unsigned index;
+ public:
+ iterator(Coverage&owner, unsigned index) :
+ owner(owner),
+ index(index) {}
+ const Entry operator *() const {
+ return Entry(owner, index);
+ }
+ Entry operator *() {
+ return Entry(owner, index);
+ }
+ iterator&operator ++() {
+ ++index;
+ return *this;
+ }
+ bool operator ==(const iterator&other) const {
+ return &owner == &other.owner && index == other.index;
+ }
+ bool operator !=(const iterator&other) const {
+ return &owner != &other.owner || index != other.index;
+ }
+ Array<unsigned>getCombination() const {
+ return owner.decode(index);
+ }
+ };
+
+ class const_iterator {
+ protected:
+ const Coverage& owner;
+ unsigned index;
+ public:
+ const_iterator(const Coverage&owner, unsigned index) :
+ owner(owner),
+ index(index) {}
+ const_iterator(const iterator&copy) :
+ owner(copy.owner),
+ index(copy.index) {}
+ const Entry operator *() const {
+ return Entry(owner, index);
+ }
+ const_iterator&operator ++() {
+ ++index;
+ return *this;
+ }
+ bool operator ==(const const_iterator&other) const {
+ return &owner == &other.owner && index == other.index;
+ }
+ bool operator != (const const_iterator&other) const {
+ return &owner != &other.owner || index != other.index;
+ }
+ Array<unsigned>getCombination() const {
+ return owner.decode(index);
+ }
+ };
+
+ iterator begin() {
+ return iterator(*this, 0);
+ }
+ const_iterator begin() const {
+ return const_iterator(*this, 0);
+ }
+ iterator end() {
+ return iterator(*this, contents.getSize());
+ }
+ const_iterator end() const {
+ return const_iterator(*this, contents.getSize());
+ }
+
+ unsigned getSize() const {
+ return contents.getSize();
+ }
+
+ void fill(const T&filler) {
+ contents.fill(filler);
+ }
+};
+
+#endif
diff --git a/casa/covering/bookkeeping/Options.C b/casa/covering/bookkeeping/Options.C
new file mode 100644
index 0000000..cd3c911
--- /dev/null
+++ b/casa/covering/bookkeeping/Options.C
@@ -0,0 +1,102 @@
+// 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 "covering/bookkeeping/Options.H"
+
+Options::Options() :
+ cumulativeValueCounts(0),
+ owningOptions(0) {}
+
+Options::Options(Array<unsigned>values) :
+ cumulativeValueCounts(values.getSize()) {
+ unsigned cumulativeValueCount = 0;
+ for (unsigned i = 0; i < values.getSize(); ++i) {
+ cumulativeValueCount += values[i];
+ cumulativeValueCounts[i] = cumulativeValueCount;
+ }
+ owningOptions = Array<unsigned>(cumulativeValueCount);
+ for (unsigned i = 0, j = 0; i < values.getSize(); ++i) {
+ for (unsigned k = values[i]; k--;) {
+ owningOptions[j++] = i;
+ }
+ }
+}
+
+Options::Options(const Options&copy) :
+ cumulativeValueCounts(copy.cumulativeValueCounts),
+ owningOptions(copy.owningOptions) {}
+
+unsigned Options::getSize() const {
+ return cumulativeValueCounts.getSize();
+}
+
+unsigned Options::getFirstSymbol(unsigned option) const {
+ return option ? cumulativeValueCounts[option - 1] : 0;
+}
+
+Array<unsigned>Options::getFirstSymbols() const {
+ unsigned size = cumulativeValueCounts.getSize();
+ Array<unsigned>result(size);
+ for (unsigned i = size; i-- > 1;) {
+ result[i] = cumulativeValueCounts[i - 1];
+ }
+ if (size) {
+ result[0] = 0;
+ }
+ return result;
+}
+
+unsigned Options::getSymbolCount(unsigned option) const {
+ return option ?
+ (cumulativeValueCounts[option] - cumulativeValueCounts[option - 1]) :
+ cumulativeValueCounts[0];
+}
+
+Array<unsigned>Options::getSymbolCounts() const {
+ unsigned size = cumulativeValueCounts.getSize();
+ Array<unsigned>result(size);
+ for (unsigned i = size; i-- > 1;) {
+ result[i] = cumulativeValueCounts[i] - cumulativeValueCounts[i - 1];
+ }
+ if (size) {
+ result[0] = cumulativeValueCounts[0];
+ }
+ return result;
+}
+
+unsigned Options::getLastSymbol(unsigned option) const {
+ return cumulativeValueCounts[option] - 1;
+}
+
+unsigned Options::getRandomSymbol(unsigned option) const {
+ return rand() % getSymbolCount(option) + getFirstSymbol(option);
+}
+
+unsigned Options::getOtherRandomSymbol(unsigned option, unsigned exclude)
+ const {
+ unsigned count = getSymbolCount(option);
+ if (count == 1) {
+ return getFirstSymbol(option);
+ }
+ unsigned result = rand() % (count - 1) + getFirstSymbol(option);
+ return (result >= exclude) ? (result + 1) : result;
+}
+
+unsigned Options::getOption(unsigned symbol) const {
+ return owningOptions[symbol];
+}
diff --git a/casa/covering/bookkeeping/Options.H b/casa/covering/bookkeeping/Options.H
new file mode 100644
index 0000000..ee047a4
--- /dev/null
+++ b/casa/covering/bookkeeping/Options.H
@@ -0,0 +1,50 @@
+// 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/>.
+
+
+#ifndef OPTIONS_H
+#define OPTIONS_H
+
+#include <cstdlib>
+#include <utility>
+
+#include "Array.H"
+
+class Options {
+protected:
+ // The entry cumulativeValueCounts[i] is the number of values in options 0
+ // through i, inclusive.
+ Array<unsigned> cumulativeValueCounts;
+ // The entry owningOptions[i] is the option that the value i belongs to.
+ Array<unsigned> owningOptions;
+
+public:
+ Options();
+ Options(Array<unsigned>valueCounts);
+ Options(const Options&copy);
+ unsigned getSize() const;
+ unsigned getFirstSymbol(unsigned option) const;
+ Array<unsigned>getFirstSymbols() const;
+ unsigned getSymbolCount(unsigned option) const;
+ Array<unsigned>getSymbolCounts() const;
+ unsigned getLastSymbol(unsigned option) const;
+ unsigned getRandomSymbol(unsigned option) const;
+ unsigned getOtherRandomSymbol(unsigned option, unsigned exclude) const;
+ unsigned getOption(unsigned symbol) const;
+};
+
+#endif
diff --git a/casa/covering/cost/CoverageCost.H b/casa/covering/cost/CoverageCost.H
new file mode 100644
index 0000000..524a240
--- /dev/null
+++ b/casa/covering/cost/CoverageCost.H
@@ -0,0 +1,72 @@
+// 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/>.
+
+
+#ifndef COVERAGE_COST_H
+#define COVERAGE_COST_H
+
+#include <cassert>
+
+class CoverageCost {
+protected:
+ unsigned noncoverage;
+ unsigned multipleCoverage;
+
+public:
+ // So we can initialize an object from a literal zero:
+ CoverageCost(unsigned zero = 0) :
+ noncoverage(0),
+ multipleCoverage(0) {
+ assert(!zero);
+ }
+ CoverageCost(unsigned noncoverage, unsigned multipleCoverage) :
+ noncoverage(noncoverage),
+ multipleCoverage(multipleCoverage) {}
+
+ unsigned getNoncoverage() const {
+ return noncoverage;
+ }
+ unsigned getMultipleCoverage() const {
+ return multipleCoverage;
+ }
+
+ bool operator <(const CoverageCost&other) const {
+ if (noncoverage < other.noncoverage) {
+ return true;
+ }
+ if (noncoverage > other.noncoverage) {
+ return false;
+ }
+ return multipleCoverage < other.multipleCoverage;
+ }
+ bool operator <=(const CoverageCost&other) const {
+ if (noncoverage < other.noncoverage) {
+ return true;
+ }
+ if (noncoverage > other.noncoverage) {
+ return false;
+ }
+ return multipleCoverage <= other.multipleCoverage;
+ }
+ bool operator ==(const CoverageCost&other) const {
+ return
+ noncoverage == other.noncoverage &&
+ multipleCoverage == other.multipleCoverage;
+ }
+};
+
+#endif
diff --git a/casa/covering/filter/CoveringArrayAnnealingFilter.H b/casa/covering/filter/CoveringArrayAnnealingFilter.H
new file mode 100644
index 0000000..f876e8f
--- /dev/null
+++ b/casa/covering/filter/CoveringArrayAnnealingFilter.H
@@ -0,0 +1,49 @@
+// 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/>.
+
+
+#ifndef COVERING_ARRAY_ANNEALING_FILTER_H
+#define COVERING_ARRAY_ANNEALING_FILTER_H
+
+#include "annealing/AnnealingFilter.H"
+
+#include "covering/state/CoveringArray.H"
+#include "covering/cost/CoverageCost.H"
+
+#ifndef MULTIPLE_COVERAGE_WEIGHT
+#define MULTIPLE_COVERAGE_WEIGHT 0.1L
+#endif
+
+class CoveringArrayAnnealingFilter :
+ public AnnealingFilter<CoveringArray, CoverageCost> {
+public:
+ CoveringArrayAnnealingFilter(double temperature, double decay) :
+ AnnealingFilter<CoveringArray, CoverageCost>(temperature, decay) {}
+
+ double convertToDelta(CoverageCost childEstimate, CoverageCost parentEstimate)
+ const {
+ unsigned childNoncoverage = childEstimate.getNoncoverage();
+ unsigned parentNoncoverage = parentEstimate.getNoncoverage();
+ unsigned childMultipleCoverage = childEstimate.getMultipleCoverage();
+ unsigned parentMultipleCoverage = parentEstimate.getMultipleCoverage();
+ return -(double)(childNoncoverage - parentNoncoverage) -
+ MULTIPLE_COVERAGE_WEIGHT *
+ (childMultipleCoverage - parentMultipleCoverage);
+ }
+};
+
+#endif
diff --git a/casa/covering/goal/CoverageGoal.H b/casa/covering/goal/CoverageGoal.H
new file mode 100644
index 0000000..c4e0693
--- /dev/null
+++ b/casa/covering/goal/CoverageGoal.H
@@ -0,0 +1,43 @@
+// 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/>.
+
+
+#ifndef COVERAGE_GOAL_H
+#define COVERAGE_GOAL_H
+
+#include "search/Goal.H"
+
+#include "covering/state/CoveringArray.H"
+
+class CoverageGoal : public Goal<CoveringArray> {
+protected:
+ unsigned targetCoverage;
+public:
+ CoverageGoal(unsigned targetCoverage) :
+ targetCoverage(targetCoverage) {}
+
+ unsigned getTargetCoverage() {
+ return targetCoverage;
+ }
+
+ bool isGoal(const CoveringArray&array) {
+ assert(array.getCoverageCount() <= targetCoverage);
+ return array.getCoverageCount() == targetCoverage;
+ }
+};
+
+#endif
diff --git a/casa/covering/heuristic/CoveringArrayHeuristic.H b/casa/covering/heuristic/CoveringArrayHeuristic.H
new file mode 100644
index 0000000..61214b8
--- /dev/null
+++ b/casa/covering/heuristic/CoveringArrayHeuristic.H
@@ -0,0 +1,37 @@
+// 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/>.
+
+
+#ifndef COVERING_ARRAY_HEURISTIC_H
+#define COVERING_ARRAY_HEURISTIC_H
+
+#include "search/Heuristic.H"
+
+#include "covering/state/CoveringArray.H"
+#include "covering/goal/CoverageGoal.H"
+
+class CoveringArrayHeuristic : public Heuristic<CoveringArray, CoverageCost> {
+ CoverageCost estimate
+ (const CoveringArray&state, const Goal<CoveringArray>&goal) const {
+ unsigned targetCoverage = ((CoverageGoal&)goal).getTargetCoverage();
+ return CoverageCost
+ (targetCoverage - state.getCoverageCount(),
+ state.getMultipleCoverageCount());
+ }
+};
+
+#endif
diff --git a/casa/covering/report/IterationReport.H b/casa/covering/report/IterationReport.H
new file mode 100644
index 0000000..7799b88
--- /dev/null
+++ b/casa/covering/report/IterationReport.H
@@ -0,0 +1,53 @@
+// 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/>.
+
+
+#ifndef ITERATION_REPORT_H
+#define ITERATION_REPORT_H
+
+#include <iostream>
+
+class IterationReport :
+ public Listener<SearchFinish<CoveringArray, CoverageCost> > {
+protected:
+ unsigned total;
+public:
+ IterationReport() :
+ total(0) {}
+ void signal(const SearchFinish<CoveringArray, CoverageCost>&finish) {
+ std::set<const Node<CoveringArray, CoverageCost>*>best =
+ finish.source.getBest();
+ if (best.size()) {
+ const CoveringArray&state = (*best.begin())->getState();
+ assert(state.isTrackingNoncoverage());
+ std::cout << "Search stopped after " << finish.iterations << '/' <<
+ finish.maxIterations << " iteration(s) with " <<
+ state.getNoncoverage().size() << " uncovered t-sets and " <<
+ state.getMultipleCoverageCount() << " multicovered t-sets" << std::endl;
+ } else {
+ std::cout << "Search stopped after " << finish.iterations << '/' <<
+ finish.maxIterations << " iteration(s) with no results" << std::endl;
+ }
+ total += finish.iterations;
+ std::cout << "Used " << total << " total iterations thus far" << std::endl;
+ }
+ unsigned getTotal() const {
+ return total;
+ }
+};
+
+#endif
diff --git a/casa/covering/space/CoveringArraySpace.C b/casa/covering/space/CoveringArraySpace.C
new file mode 100644
index 0000000..6287bd3
--- /dev/null
+++ b/casa/covering/space/CoveringArraySpace.C
@@ -0,0 +1,80 @@
+// 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 "covering/space/CoveringArraySpace.H"
+
+CoveringArraySpace::CoveringArraySpace(unsigned strength, Options options) :
+ strength(strength), options(options) {
+ assert(strength <= options.getSize());
+ for (unsigned i = options.getSize(); i--;) {
+ // The clause atLeast requires that each column be filled.
+ InputClause atLeast;
+ for (unsigned
+ j = options.getFirstSymbol(i),
+ limit = options.getLastSymbol(i);
+ j <= limit;
+ ++j) {
+ atLeast.append(InputTerm(false, j));
+ }
+ solver.addClause(atLeast);
+ // The clauses atMost require that each pairing of symbols from an option
+ // show at least one absence.
+ for (unsigned
+ j = options.getFirstSymbol(i),
+ limit = options.getLastSymbol(i);
+ j <= limit; ++j) {
+ for (unsigned k = j + 1; k <= limit; ++k) {
+ InputClause atMost;
+ atMost.append(InputTerm(true, j));
+ atMost.append(InputTerm(true, k));
+ solver.addClause(atMost);
+ }
+ }
+ }
+}
+
+unsigned CoveringArraySpace::computeTargetCoverage() const {
+ unsigned result = 0;
+ for (Array<unsigned>columns = combinadic.begin(strength);
+ columns[strength - 1] < options.getSize();
+ combinadic.next(columns)) {
+ // Initialization:
+ Array<InputTerm>combination(columns.getSize());
+ for (unsigned i = columns.getSize(); i--;) {
+ combination[i] = InputTerm(false, options.getFirstSymbol(columns[i]));
+ }
+ // Body:
+ loop:
+ {
+ InputKnown known(combination);
+ if (solver(known)) {
+ ++result;
+ }
+ }
+ // Advance:
+ for (unsigned i = columns.getSize(); i--;) {
+ unsigned next = combination[i].getVariable() + 1;
+ if (next <= options.getLastSymbol(columns[i])) {
+ combination[i] = InputTerm(false, next);
+ goto loop;
+ }
+ combination[i] = InputTerm(false, options.getFirstSymbol(columns[i]));
+ }
+ }
+ return result;
+}
diff --git a/casa/covering/space/CoveringArraySpace.H b/casa/covering/space/CoveringArraySpace.H
new file mode 100644
index 0000000..e4702a5
--- /dev/null
+++ b/casa/covering/space/CoveringArraySpace.H
@@ -0,0 +1,52 @@
+// 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/>.
+
+
+#ifndef COVERING_ARRAY_SPACE_H
+#define COVERING_ARRAY_SPACE_H
+
+#include <cassert>
+
+#include "Array.H"
+
+#include "search/StateSpace.H"
+
+#include "covering/state/CoveringArray.H"
+#include "covering/bookkeeping/Options.H"
+#include "covering/cost/CoverageCost.H"
+
+#include "sat/SAT.H"
+
+class CoveringArraySpace : public StateSpace<CoveringArray, CoverageCost>{
+protected:
+ unsigned strength;
+ Options options;
+ mutable SATSolver solver;
+public:
+ CoveringArraySpace(unsigned strength, Options options);
+ virtual ~CoveringArraySpace() {}
+ virtual CoveringArray createStartState(unsigned rows) const = 0;
+ SATSolver&getSolver() {
+ return solver;
+ }
+ const SATSolver&getSolver() const {
+ return solver;
+ }
+ unsigned computeTargetCoverage() const;
+};
+
+#endif
diff --git a/casa/covering/space/GraftSpace.C b/casa/covering/space/GraftSpace.C
new file mode 100644
index 0000000..daa84e0
--- /dev/null
+++ b/casa/covering/space/GraftSpace.C
@@ -0,0 +1,187 @@
+// 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 <algorithm>
+
+#include "utility/igreater.H"
+
+#include "covering/space/GraftSpace.H"
+
+using namespace std;
+
+#ifndef MAXIMUM_SUBROW_CHANGE_FAILED_ATTEMPTS
+#define MAXIMUM_SUBROW_CHANGE_FAILED_ATTEMPTS 32
+#endif
+
+Array<unsigned>GraftSpace::createRandomMatchingRow(InputKnown&known) const {
+ Array<unsigned>result(options.getSize());
+ for (unsigned i = options.getSize(); i--;) {
+ vector<unsigned>candidates;
+ for (unsigned
+ j = options.getSymbolCount(i),
+ base = options.getFirstSymbol(i);
+ j--;) {
+ candidates.push_back(base + j);
+ }
+ unsigned index = rand() % candidates.size();
+ unsigned symbol = candidates[index];
+ known.append(InputTerm(false, symbol));
+ while (!solver(known)) {
+ known.undoAppend();
+ candidates[index] = candidates[candidates.size() - 1];
+ candidates.pop_back();
+ index = rand() % candidates.size();
+ symbol = candidates[index];
+ known.append(InputTerm(false, symbol));
+ }
+ result[i] = symbol;
+ }
+ return result;
+}
+
+CoveringArray GraftSpace::createStartState(unsigned rows) const {
+ CoveringArray result(rows, strength, options, solver);
+ unsigned i = rows;
+ while (i-->resurrectionBuffer.size()) {
+ InputKnown known;
+ result.setBackingArrayRow(i, createRandomMatchingRow(known));
+ }
+ if (resurrectionBuffer.size()) {
+ for (++i;i--;) {
+ Array<unsigned>row = resurrectionBuffer[i];
+ // We must deep copy to preserve the resurrection buffer.
+ for (unsigned j = options.getSize(); j--;) {
+ result.setBackingArrayEntry(i, j, row[j]);
+ }
+ }
+ }
+ result.setTrackingCoverage(true);
+ result.setTrackingNoncoverage(true);
+ return result;
+}
+
+CoverageCost GraftSpace::getTraveled(const CoveringArray&start) const {
+ return 0;
+}
+
+CoverageCost GraftSpace::getTraveled
+ (const Node<CoveringArray, CoverageCost>&parent,const CoveringArray&state)
+ const {
+ return 0;
+}
+
+set<CoveringArray>GraftSpace::getChildren
+ (const CoveringArray&state, float proportion) const {
+ assert(false); // Unimplemented.
+ return getChildren(state, (unsigned)1);
+}
+
+set<CoveringArray>GraftSpace::getChildren
+ (const CoveringArray&state, unsigned count) const {
+ set<CoveringArray>result;
+ unsigned rows = state.getRows();
+ assert(options.getSize() == state.getOptions());
+ assert(state.isTrackingNoncoverage());
+ const set<Array<unsigned>, ArrayComparator<unsigned> >&noncoverage =
+ state.getNoncoverage();
+ if (noncoverage.empty()){
+ return result;
+ }
+ unsigned attempts = 0;
+ for (unsigned i = count; i; ++attempts) {
+ unsigned row = rand() % rows;
+ set<Array<unsigned>, ArrayComparator<unsigned> >::const_iterator
+ combinationIterator = noncoverage.begin();
+ unsigned combinationIndex = rand() % noncoverage.size();
+ while (combinationIndex--) {
+ ++combinationIterator;
+ }
+ Array<unsigned>combination = *combinationIterator;
+ Array<unsigned>columns(strength);
+ InputKnown known;
+ if (attempts < MAXIMUM_SUBROW_CHANGE_FAILED_ATTEMPTS) {
+ for (unsigned j = strength; j--;) {
+ columns[j] = options.getOption(combination[j]);
+ }
+ for (unsigned j = options.getSize(), k = strength; j--;) {
+ if (k && columns[k-1] == j) {
+ unsigned symbol = combination[--k];
+ known.append(InputTerm(false, symbol));
+ } else {
+ assert(!k || columns[k - 1] < j);
+ unsigned symbol = state(row, j);
+ known.append(InputTerm(false, symbol));
+ }
+ }
+ if (solver(known)) {
+ CoveringArray child = state;
+ child(row, columns) = combination;
+ result.insert(child);
+ --i;
+ attempts = 0;
+ }
+ } else {
+ cout << "Considering a full row change" << endl;
+ for (unsigned k = strength; k--;) {
+ known.append(InputTerm(false, combination[k]));
+ }
+ CoveringArray child = state;
+ child(row) = createRandomMatchingRow(known);
+ result.insert(child);
+ --i;
+ attempts = 0;
+ }
+ }
+ return result;
+}
+
+void GraftSpace::signal(const SearchFinish<CoveringArray, CoverageCost>&finish) {
+ const set<const Node<CoveringArray, CoverageCost>*>&best =
+ finish.source.getBest();
+ if (best.empty()) {
+ return;
+ }
+ const CoveringArray&solution = (*best.begin())->getState();
+ unsigned rowCount = solution.getRows();
+ unsigned optionCount = solution.getOptions();
+ resurrectionBuffer.reserve(rowCount);
+ while (resurrectionBuffer.size() < rowCount) {
+ resurrectionBuffer.push_back(Array<unsigned>());
+ }
+ cout << "Sorting rows for distinct coverage" << endl;
+ Array<unsigned>distinctCoverage = solution.countDistinctCoverage();
+ Array<unsigned>permutation(rowCount);
+ for (unsigned i = rowCount; i--;) {
+ permutation[i] = i;
+ }
+ igreater<unsigned>betterDistinctCoverage(distinctCoverage);
+ sort(permutation + 0, permutation + rowCount, betterDistinctCoverage);
+ cout << "Saving rows in resurrection buffer" << endl;
+ for (unsigned i = rowCount; i--;) {
+ unsigned p = permutation[i];
+ Array<unsigned>row = Array<unsigned>(optionCount);
+ for (unsigned j = optionCount; j--;) {
+ row[j] = solution(p, j);
+ }
+ resurrectionBuffer[i] = row;
+ }
+}
+
+void GraftSpace::clearResurrectionBuffer() {
+ resurrectionBuffer.clear();
+}
diff --git a/casa/covering/space/GraftSpace.H b/casa/covering/space/GraftSpace.H
new file mode 100644
index 0000000..abd7b84
--- /dev/null
+++ b/casa/covering/space/GraftSpace.H
@@ -0,0 +1,60 @@
+// 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/>.
+
+
+#ifndef GRAFT_SPACE_H
+#define GRAFT_SPACE_H
+
+#include <vector>
+#include <iostream>
+
+#include "Array.H"
+
+#include "covering/space/CoveringArraySpace.H"
+#include "covering/cost/CoverageCost.H"
+
+#include "events/Listener.H"
+#include "search/SearchFinish.H"
+
+class GraftSpace :
+ public CoveringArraySpace,
+ public Listener<SearchFinish<CoveringArray, CoverageCost> > {
+protected:
+ std::vector<Array<unsigned> > resurrectionBuffer;
+
+public:
+ GraftSpace(unsigned strength, Options options) :
+ CoveringArraySpace(strength, options) {}
+
+protected:
+ Array<unsigned>createRandomMatchingRow(InputKnown&known) const;
+
+public:
+ CoveringArray createStartState(unsigned rows) const;
+ CoverageCost getTraveled(const CoveringArray&start) const;
+ CoverageCost getTraveled
+ (const Node<CoveringArray, CoverageCost>&parent, const CoveringArray&state)
+ const;
+ std::set<CoveringArray>getChildren
+ (const CoveringArray&state, float proportion) const;
+ std::set<CoveringArray>getChildren
+ (const CoveringArray&state,unsigned count) const;
+ void signal(const SearchFinish<CoveringArray, CoverageCost>&finish);
+ void clearResurrectionBuffer();
+};
+
+#endif
diff --git a/casa/covering/space/SingleChangeSpace.C b/casa/covering/space/SingleChangeSpace.C
new file mode 100644
index 0000000..96c4146
--- /dev/null
+++ b/casa/covering/space/SingleChangeSpace.C
@@ -0,0 +1,175 @@
+// 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 <iostream>
+#include <algorithm>
+
+#include "utility/igreater.H"
+
+#include "covering/space/SingleChangeSpace.H"
+
+using namespace std;
+
+#ifndef MAXIMUM_SINGLE_CHANGE_FAILED_ATTEMPTS
+#define MAXIMUM_SINGLE_CHANGE_FAILED_ATTEMPTS 32
+#endif
+
+Array<unsigned>SingleChangeSpace::createRandomMatchingRow
+ (InputKnown&known) const {
+ Array<unsigned>result(options.getSize());
+ for (unsigned i = options.getSize(); i--;) {
+ vector<unsigned>candidates;
+ for (unsigned
+ j = options.getSymbolCount(i),
+ base = options.getFirstSymbol(i);
+ j--;) {
+ candidates.push_back(base + j);
+ }
+ unsigned index = rand() % candidates.size();
+ unsigned symbol = candidates[index];
+ known.append(InputTerm(false, symbol));
+ while (!solver(known)) {
+ known.undoAppend();
+ candidates[index] = candidates[candidates.size() - 1];
+ candidates.pop_back();
+ index = rand() % candidates.size();
+ symbol = candidates[index];
+ known.append(InputTerm(false, symbol));
+ }
+ result[i] = symbol;
+ }
+ return result;
+}
+
+CoveringArray SingleChangeSpace::createStartState(unsigned rows) const {
+ CoveringArray result(rows, strength, options, solver);
+ unsigned i = rows;
+ while (i-->resurrectionBuffer.size()) {
+ InputKnown known;
+ result.setBackingArrayRow(i, createRandomMatchingRow(known));
+ }
+ if (resurrectionBuffer.size()) {
+ for (++i; i--;) {
+ Array<unsigned>row = resurrectionBuffer[i];
+ // We must deep copy to preserve the resurrection buffer.
+ for (unsigned j = options.getSize(); j--;) {
+ result.setBackingArrayEntry(i, j, row[j]);
+ }
+ }
+ }
+ result.setTrackingCoverage(true);
+ result.setTrackingNoncoverage(true);
+ return result;
+}
+
+CoverageCost SingleChangeSpace::getTraveled(const CoveringArray&start) const {
+ return 0;
+}
+
+CoverageCost SingleChangeSpace::getTraveled
+ (const Node<CoveringArray, CoverageCost>&parent, const CoveringArray&state)
+ const {
+ return 0;
+}
+
+set<CoveringArray>SingleChangeSpace::getChildren
+ (const CoveringArray&state, float proportion) const {
+ assert(false); // Unimplemented
+ return getChildren(state, (unsigned)1);
+}
+
+set<CoveringArray>SingleChangeSpace::getChildren
+ (const CoveringArray&state, unsigned count) const {
+ set<CoveringArray>result;
+ unsigned rows = state.getRows();
+ assert(options.getSize() == state.getOptions());
+ assert(state.isTrackingNoncoverage());
+ const set<Array<unsigned>, ArrayComparator<unsigned> >&noncoverage =
+ state.getNoncoverage();
+ if (noncoverage.empty()) {
+ return result;
+ }
+ unsigned attempts = 0;
+ for (unsigned i = count; i; ++attempts) {
+ unsigned row = rand() % rows;
+ unsigned option = rand() % options.getSize();
+ unsigned value = options.getOtherRandomSymbol(option, state(row, option));
+ InputKnown known;
+ known.append(InputTerm(false, value));
+ if (attempts < MAXIMUM_SINGLE_CHANGE_FAILED_ATTEMPTS) {
+ for (unsigned j = 0; j < option; ++j) {
+ known.append(InputTerm(false, state(row, j)));
+ }
+ for (unsigned j = option + 1; j < options.getSize(); ++j) {
+ known.append(InputTerm(false, state(row, j)));
+ }
+ if (solver(known)) {
+ CoveringArray child = state;
+ child(row, option) = value;
+ result.insert(child);
+ --i;
+ attempts = 0;
+ }
+ } else {
+ cout << "Considering a full row change" << endl;
+ CoveringArray child = state;
+ child(row) = createRandomMatchingRow(known);
+ result.insert(child);
+ --i;
+ attempts = 0;
+ }
+ }
+ return result;
+}
+
+void SingleChangeSpace::signal
+ (const SearchFinish<CoveringArray, CoverageCost>&finish) {
+ const set<const Node<CoveringArray, CoverageCost>*>&best =
+ finish.source.getBest();
+ if (best.empty()) {
+ return;
+ }
+ const CoveringArray&solution = (*best.begin())->getState();
+ unsigned rowCount = solution.getRows();
+ unsigned optionCount = solution.getOptions();
+ resurrectionBuffer.reserve(rowCount);
+ while (resurrectionBuffer.size() < rowCount) {
+ resurrectionBuffer.push_back(Array<unsigned>());
+ }
+ cout << "Sorting rows for distinct coverage" << endl;
+ Array<unsigned>distinctCoverage = solution.countDistinctCoverage();
+ Array<unsigned>permutation(rowCount);
+ for (unsigned i = rowCount; i--;) {
+ permutation[i] = i;
+ }
+ igreater<unsigned>betterDistinctCoverage(distinctCoverage);
+ sort(permutation + 0, permutation + rowCount, betterDistinctCoverage);
+ cout << "Saving rows in resurrection buffer" << endl;
+ for (unsigned i = rowCount; i--;) {
+ unsigned p = permutation[i];
+ Array<unsigned>row(optionCount);
+ for (unsigned j = optionCount; j--;) {
+ row[j] = solution(p,j);
+ }
+ resurrectionBuffer[i] = row;
+ }
+}
+
+void SingleChangeSpace::clearResurrectionBuffer() {
+ resurrectionBuffer.clear();
+}
diff --git a/casa/covering/space/SingleChangeSpace.H b/casa/covering/space/SingleChangeSpace.H
new file mode 100644
index 0000000..66efbc3
--- /dev/null
+++ b/casa/covering/space/SingleChangeSpace.H
@@ -0,0 +1,61 @@
+// 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/>.
+
+
+#ifndef SINGLE_CHANGE_SPACE_H
+#define SINGLE_CHANGE_SPACE_H
+
+#include <cstdlib>
+#include <cassert>
+#include <vector>
+
+#include "Array.H"
+
+#include "covering/space/CoveringArraySpace.H"
+#include "covering/cost/CoverageCost.H"
+
+#include "events/Listener.H"
+#include "search/SearchFinish.H"
+
+class SingleChangeSpace :
+ public CoveringArraySpace,
+ public Listener<SearchFinish<CoveringArray, CoverageCost> > {
+protected:
+ std::vector<Array<unsigned> > resurrectionBuffer;
+
+public:
+ SingleChangeSpace(unsigned strength, Options options) :
+ CoveringArraySpace(strength, options) {}
+
+protected:
+ Array<unsigned>createRandomMatchingRow(InputKnown&known) const;
+
+public:
+ CoveringArray createStartState(unsigned rows) const;
+ CoverageCost getTraveled(const CoveringArray&start) const;
+ CoverageCost getTraveled
+ (const Node<CoveringArray, CoverageCost>&parent,
+ const CoveringArray&state) const;
+ std::set<CoveringArray>getChildren
+ (const CoveringArray&state, float proportion) const;
+ std::set<CoveringArray>getChildren
+ (const CoveringArray&state, unsigned count) const;
+ void signal(const SearchFinish<CoveringArray, CoverageCost>&finish);
+ void clearResurrectionBuffer();
+};
+
+#endif
diff --git a/casa/covering/state/CoveringArray.C b/casa/covering/state/CoveringArray.C
new file mode 100644
index 0000000..e5aca80
--- /dev/null
+++ b/casa/covering/state/CoveringArray.C
@@ -0,0 +1,274 @@
+// 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 "covering/state/CoveringArray.H"
+
+using namespace std;
+
+#ifndef MAXIMUM_COVERING_ARRAY_SUBSTITUTION
+#define MAXIMUM_COVERING_ARRAY_SUBSTITUTION 0x40
+#endif
+
+CoveringArray::CoveringArray
+ (unsigned rows, unsigned strength, Options options, SATSolver&solver) :
+ array(rows),
+ substitutions(new map<pair<unsigned, unsigned>, unsigned>()),
+ solver(&solver),
+ trackingCoverage(false),
+ trackingNoncoverage(false),
+ coverageCount(0),
+ multipleCoverageCount(0),
+ coverage(strength, options),
+ noncoverage(new set<Array<unsigned>, ArrayComparator<unsigned> >()) {
+ for (unsigned i = rows; i--;) {
+ array[i] = Array<unsigned>(options.getSize());
+ }
+ coverage.fill(0);
+}
+
+CoveringArray::CoveringArray(const CoveringArray&copy) :
+ array(copy.array),
+ substitutions(copy.substitutions),
+ solver(copy.solver),
+ trackingCoverage(copy.trackingCoverage),
+ trackingNoncoverage(copy.trackingNoncoverage),
+ coverageCount(copy.coverageCount),
+ multipleCoverageCount(copy.multipleCoverageCount),
+ coverage(copy.coverage),
+ noncoverage(copy.noncoverage) {
+ assert(array);
+}
+
+void CoveringArray::setBackingArrayEntry
+ (unsigned row, unsigned option, unsigned value) {
+ assert(!substitutions->size());
+ array[row][option] = value;
+}
+
+void CoveringArray::setBackingArrayRow(unsigned row, Array<unsigned>value) {
+ assert(!substitutions->size());
+ array[row] = value;
+}
+
+unsigned CoveringArray::getCoverageCount() const {
+ return coverageCount;
+}
+
+unsigned CoveringArray::getMultipleCoverageCount() const {
+ return multipleCoverageCount;
+}
+
+Array<unsigned>CoveringArray::countDistinctCoverage() const {
+ assert(trackingCoverage);
+ Array<unsigned>result(array.getSize());
+ result.fill(0);
+ unsigned strength = coverage.getStrength();
+ unsigned limit = coverage.getOptions().getSize();
+ Array<unsigned>firsts = coverage.getOptions().getFirstSymbols();
+ Array<unsigned>counts = coverage.getOptions().getSymbolCounts();
+ unsigned hint = 0;
+ for (Array<unsigned>
+ columns = combinadic.begin(strength),
+ symbols(strength);
+ columns[strength - 1]<limit;
+ combinadic.next(columns), ++hint) {
+ for (unsigned i = array.getSize(); i--;) {
+ for (unsigned j = strength; j--;) {
+ symbols[j] = (*this)(i, columns[j]);
+ }
+ if (coverage.hintGet(hint, columns, firsts, counts, symbols) == 1) {
+ ++result[i];
+ }
+ }
+ }
+ return result;
+}
+
+bool CoveringArray::operator <(const CoveringArray&other) const {
+ return this < &other;
+}
+bool CoveringArray::operator >(const CoveringArray&other) const {
+ return this > &other;
+}
+bool CoveringArray::operator ==(const CoveringArray&other) const {
+ return this == &other;
+}
+bool CoveringArray::operator !=(const CoveringArray&other) const {
+ return this != &other;
+}
+
+void CoveringArray::finalizeSubstitutions() {
+ unsigned outer = getRows();
+ unsigned inner = getOptions();
+ Array<Array<unsigned> >replacement(outer);
+ for (unsigned i = outer; i--;) {
+ replacement[i] = Array<unsigned>(inner);
+ for (unsigned j = inner; j--;) {
+ replacement[i][j] = array[i][j];
+ }
+ }
+ for (map<pair<unsigned, unsigned>, unsigned>::const_iterator
+ iterator = substitutions->begin(),
+ end = substitutions->end();
+ iterator != end;
+ ++iterator) {
+ const pair<unsigned, unsigned>&location = iterator->first;
+ replacement[location.first][location.second] = iterator->second;
+ }
+ substitutions->clear();
+ array = replacement;
+}
+
+void CoveringArray::autoFinalizeSubstitutions() {
+ if (substitutions->size() > MAXIMUM_COVERING_ARRAY_SUBSTITUTION) {
+ finalizeSubstitutions();
+ }
+}
+
+bool CoveringArray::isTrackingCoverage() const {
+ return trackingCoverage;
+}
+
+void CoveringArray::setTrackingCoverage(bool trackingCoverage) {
+ if (this->trackingCoverage) {
+ this->trackingCoverage = trackingCoverage;
+ return;
+ }
+ this->trackingCoverage = trackingCoverage;
+ if (trackingCoverage) {
+ unsigned strength = coverage.getStrength();
+ unsigned limit = coverage.getOptions().getSize();
+ Array<unsigned>firsts = coverage.getOptions().getFirstSymbols();
+ Array<unsigned>counts = coverage.getOptions().getSymbolCounts();
+ coverage.fill(0);
+ coverageCount = 0;
+ multipleCoverageCount = 0;
+ if (substitutions->size()) {
+ unsigned hint = 0;
+ for (Array<unsigned>
+ columns = combinadic.begin(strength),
+ symbols(strength);
+ columns[strength - 1] < limit;
+ combinadic.next(columns), ++hint) {
+ for (unsigned i = array.getSize();i--;) {
+ for (unsigned j = strength;j--;) {
+ symbols[j] = (*this)(i, columns[j]);
+ }
+ unsigned newCoverage =
+ ++coverage.hintGet(hint, columns, firsts, counts, symbols);
+ if (newCoverage == 1) {
+ ++coverageCount;
+ }
+ if (newCoverage>1) {
+ ++multipleCoverageCount;
+ }
+ }
+ }
+ } else {
+ // A special common case where we can bypass the () operator:
+ unsigned hint = 0;
+ for (Array<unsigned>
+ columns = combinadic.begin(strength),
+ symbols(strength);
+ columns[strength - 1] < limit;
+ combinadic.next(columns), ++hint) {
+ for (unsigned i = array.getSize(); i--;) {
+ for (unsigned j = strength; j--;) {
+ symbols[j] = array[i][columns[j]];
+ }
+ unsigned newCoverage =
+ ++coverage.hintGet(hint, columns, firsts, counts, symbols);
+ if (newCoverage == 1) {
+ ++coverageCount;
+ }
+ if (newCoverage>1) {
+ ++multipleCoverageCount;
+ }
+ }
+ }
+ }
+ }
+}
+
+bool CoveringArray::isTrackingNoncoverage() const {
+ return trackingNoncoverage;
+}
+
+void CoveringArray::setTrackingNoncoverage(bool trackingNoncoverage) {
+ if (this->trackingNoncoverage) {
+ this->trackingNoncoverage = trackingNoncoverage;
+ if (!trackingNoncoverage) {
+ noncoverage->clear();
+ }
+ return;
+ }
+ this->trackingNoncoverage = trackingNoncoverage;
+ if (trackingNoncoverage) {
+ assert(trackingCoverage);
+ assert(noncoverage->empty());
+#ifndef NDEBUG
+ unsigned impossible = 0;
+#endif
+ for (Coverage<unsigned>::iterator
+ iterator = coverage.begin(),
+ end = coverage.end();
+ iterator != end;
+ ++iterator) {
+ if (!*iterator) {
+ InputKnown known;
+ Array<unsigned>combination = iterator.getCombination();
+ for (unsigned i = combination.getSize(); i--;) {
+ known.append(InputTerm(false, combination[i]));
+ }
+ if ((*solver)(known)) {
+ noncoverage->insert(combination);
+ }
+#ifndef NDEBUG
+ else {
+ ++impossible;
+ }
+#endif
+ }
+ }
+ assert(coverageCount + noncoverage->size() + impossible ==
+ coverage.getSize());
+ }
+}
+
+const set<Array<unsigned>, ArrayComparator<unsigned> >&
+ CoveringArray::getNoncoverage() const {
+ return *noncoverage;
+}
+
+ostream&operator <<(ostream&out, const CoveringArray&array) {
+ out << '{';
+ for (unsigned i = 0; i < array.getRows(); ++i) {
+ out << '[';
+ for (unsigned j = 0; j < array.getOptions(); ++j) {
+ out << array(i,j) << ',';
+ }
+ out << "X],";
+ }
+ out << "X} -> ";
+ if (array.isTrackingCoverage()) {
+ out << array.getCoverageCount();
+ }else{
+ out << '?';
+ }
+ return out;
+}
diff --git a/casa/covering/state/CoveringArray.H b/casa/covering/state/CoveringArray.H
new file mode 100644
index 0000000..6241230
--- /dev/null
+++ b/casa/covering/state/CoveringArray.H
@@ -0,0 +1,166 @@
+// 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/>.
+
+
+#ifndef COVERING_ARRAY_H
+#define COVERING_ARRAY_H
+
+#include <cassert>
+#include <iostream>
+#include <set>
+#include <map>
+
+#include "Lazy.H"
+#include "Array.H"
+
+#include "covering/bookkeeping/Coverage.H"
+
+#include "sat/SAT.H"
+
+
+class CoveringArray {
+protected:
+ // The first index is the test configuration (row).
+ // The second index is the option (column).
+ Array<Array<unsigned> > array;
+ Lazy<std::map<std::pair<unsigned, unsigned>, unsigned> >
+ substitutions;
+
+ SATSolver* solver;
+
+ bool trackingCoverage;
+ bool trackingNoncoverage;
+
+ unsigned coverageCount;
+ unsigned multipleCoverageCount;
+ Coverage<unsigned> coverage;
+ Lazy<std::set<Array<unsigned>, ArrayComparator<unsigned> > >
+ noncoverage;
+
+public:
+ CoveringArray
+ (unsigned rows, unsigned strength, Options options, SATSolver&solver);
+ CoveringArray(const CoveringArray&copy);
+
+ unsigned getRows() const {
+ return array.getSize();
+ }
+ unsigned getOptions() const {
+ return array.getSize() ? array[0].getSize() : 0;
+ }
+
+ void setBackingArrayEntry(unsigned row, unsigned option, unsigned value);
+ void setBackingArrayRow(unsigned row, Array<unsigned>value);
+
+ class Entry {
+ protected:
+ CoveringArray& owner;
+ unsigned row;
+ unsigned option;
+ public:
+ Entry(CoveringArray&owner, unsigned row, unsigned option) :
+ owner(owner),
+ row(row),
+ option(option) {}
+ protected:
+ void updateTracking(unsigned value);
+ public:
+ operator unsigned() const;
+ Entry&operator =(unsigned value);
+ };
+
+ // Warning: CoveringArray::Row assumes that constraints are always satisfied.
+ class Row {
+ protected:
+ CoveringArray& owner;
+ unsigned row;
+ public:
+ Row(CoveringArray&owner, unsigned row) :
+ owner(owner),
+ row(row) {}
+ protected:
+ void updateTracking(const Array<unsigned>values);
+ public:
+ operator Array<unsigned>() const;
+ Row&operator =(const Array<unsigned>values);
+ };
+
+ // Warning: CoveringArray::SubRow assumes that constraints are always
+ // satisfied.
+ class SubRow {
+ protected:
+ CoveringArray& owner;
+ unsigned row;
+ Array<unsigned> columns;
+ public:
+ SubRow(CoveringArray&owner, unsigned row, Array<unsigned>columns) :
+ owner(owner),
+ row(row),
+ columns(columns) {}
+ protected:
+ void updateTracking(const Array<unsigned>values);
+ public:
+ operator Array<unsigned>() const;
+ SubRow&operator =(const Array<unsigned>values);
+ };
+
+ Entry operator ()(unsigned row, unsigned option) {
+ return Entry(*this, row, option);
+ }
+ const Entry operator ()(unsigned row, unsigned option) const {
+ return Entry(*const_cast<CoveringArray*>(this), row, option);
+ }
+
+ Row operator ()(unsigned row) {
+ return Row(*this, row);
+ }
+ const Row operator ()(unsigned row) const {
+ return Row(*const_cast<CoveringArray*>(this), row);
+ }
+
+ SubRow operator ()(unsigned row, Array<unsigned>columns) {
+ return SubRow(*this, row, columns);
+ }
+ const SubRow operator ()(unsigned row, Array<unsigned>columns) const {
+ return SubRow(*const_cast<CoveringArray*>(this), row, columns);
+ }
+
+ unsigned getCoverageCount() const;
+ unsigned getMultipleCoverageCount() const;
+ Array<unsigned>countDistinctCoverage() const;
+
+ bool operator <(const CoveringArray&other) const;
+ bool operator >(const CoveringArray&other) const;
+ bool operator ==(const CoveringArray&other) const;
+ bool operator !=(const CoveringArray&other) const;
+
+ void finalizeSubstitutions();
+ void autoFinalizeSubstitutions();
+
+ bool isTrackingCoverage() const;
+ void setTrackingCoverage(bool trackingCoverage);
+
+ bool isTrackingNoncoverage() const;
+ void setTrackingNoncoverage(bool trackingNoncoverage);
+
+ const std::set<Array<unsigned>, ArrayComparator<unsigned> >&getNoncoverage()
+ const;
+};
+
+std::ostream&operator <<(std::ostream&out,const CoveringArray&array);
+
+#endif
diff --git a/casa/covering/state/CoveringArrayEntry.C b/casa/covering/state/CoveringArrayEntry.C
new file mode 100644
index 0000000..73e6e24
--- /dev/null
+++ b/casa/covering/state/CoveringArrayEntry.C
@@ -0,0 +1,102 @@
+// 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 "covering/state/CoveringArray.H"
+
+using namespace std;
+
+void CoveringArray::Entry::updateTracking(unsigned value) {
+ if (owner(row,option) == value) {
+ return;
+ }
+ unsigned strength = owner.coverage.getStrength();
+ unsigned limit = owner.coverage.getOptions().getSize();
+ Array<unsigned>firsts = owner.coverage.getOptions().getFirstSymbols();
+ Array<unsigned>counts = owner.coverage.getOptions().getSymbolCounts();
+ unsigned hint = 0;
+ for (Array<unsigned>
+ columns = combinadic.begin(strength),
+ symbols(strength);
+ columns[strength - 1] < limit;
+ combinadic.next(columns), ++hint) {
+ for (unsigned i = strength; i--;) {
+ if (columns[i] == option) {
+ for (unsigned j = strength; j--;) {
+ symbols[j] = owner(row, columns[j]);
+ }
+ InputKnown oldKnown(symbols);
+ if ((*owner.solver)(oldKnown) &&
+ --owner.coverage.hintGet(hint, columns, firsts, counts, symbols) ==
+ 0) {
+ --owner.coverageCount;
+ if (owner.trackingNoncoverage) {
+ Array<unsigned>separateCopyOfSymbols(symbols.getSize());
+ for (unsigned j = symbols.getSize(); j--;) {
+ separateCopyOfSymbols[j] = symbols[j];
+ }
+ bool successfulInsertion =
+ owner.noncoverage->insert(separateCopyOfSymbols).second;
+ assert(successfulInsertion);
+ (void)successfulInsertion; // This is unused without assertions.
+ }
+ } else {
+ --owner.multipleCoverageCount;
+ }
+ symbols[i] = value;
+ InputKnown newKnown(symbols);
+ if ((*owner.solver)(newKnown) &&
+ ++owner.coverage.hintGet(hint, columns, firsts, counts, symbols) ==
+ 1) {
+ ++owner.coverageCount;
+ if (owner.trackingNoncoverage) {
+ Array<unsigned>separateCopyOfSymbols(symbols.getSize());
+ for (unsigned j = symbols.getSize(); j--;) {
+ separateCopyOfSymbols[j] = symbols[j];
+ }
+ bool successfulErasure =
+ (bool)owner.noncoverage->erase(separateCopyOfSymbols);
+ assert(successfulErasure);
+ (void)successfulErasure; // This is unused without assertions.
+ }
+ } else {
+ ++owner.multipleCoverageCount;
+ }
+ break;
+ }
+ }
+ }
+ owner.autoFinalizeSubstitutions();
+}
+
+CoveringArray::Entry::operator unsigned() const {
+ map<pair<unsigned, unsigned>, unsigned>::const_iterator
+ substitution =
+ owner.substitutions->find(pair<unsigned, unsigned>(row,option)),
+ end = owner.substitutions->end();
+ return (substitution == end) ?
+ owner.array[row][option] :
+ substitution->second;
+}
+
+CoveringArray::Entry&CoveringArray::Entry::operator =(unsigned value) {
+ if (owner.trackingCoverage) {
+ updateTracking(value);
+ }
+ (*owner.substitutions)[pair<unsigned, unsigned>(row, option)] = value;
+ return *this;
+}
diff --git a/casa/covering/state/CoveringArrayRow.C b/casa/covering/state/CoveringArrayRow.C
new file mode 100644
index 0000000..10f0a45
--- /dev/null
+++ b/casa/covering/state/CoveringArrayRow.C
@@ -0,0 +1,113 @@
+// 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 "covering/state/CoveringArray.H"
+
+using namespace std;
+
+void CoveringArray::Row::updateTracking(const Array<unsigned>values) {
+ unsigned size = values.getSize();
+ assert(size == owner.getOptions());
+ unsigned strength = owner.coverage.getStrength();
+ unsigned limit = owner.coverage.getOptions().getSize();
+ Array<unsigned>oldRow(size);
+ for (unsigned i = size; i--;) {
+ oldRow[i] = owner(row, i);
+ }
+ Array<unsigned>firsts = owner.coverage.getOptions().getFirstSymbols();
+ Array<unsigned>counts = owner.coverage.getOptions().getSymbolCounts();
+ unsigned hint = 0;
+ for (Array<unsigned>
+ columns = combinadic.begin(strength),
+ oldSymbols(strength),
+ newSymbols(strength);
+ columns[strength - 1] < limit;
+ combinadic.next(columns), ++hint) {
+ bool unchanged = true;
+ for (unsigned j = strength; j--;) {
+ unsigned column = columns[j];
+ oldSymbols[j] = oldRow[column];
+ newSymbols[j] = values[column];
+ if (oldSymbols[j] != newSymbols[j]) {
+ unchanged = false;
+ }
+ }
+ if (unchanged) {
+ continue;
+ }
+ InputKnown oldKnown(oldSymbols);
+ InputKnown newKnown(newSymbols);
+ if (--owner.coverage.hintGet(hint, columns, firsts, counts, oldSymbols) ==
+ 0) {
+ --owner.coverageCount;
+ if (owner.trackingNoncoverage) {
+ Array<unsigned>separateCopyOfSymbols(oldSymbols.getSize());
+ for (unsigned j = oldSymbols.getSize(); j--;) {
+ separateCopyOfSymbols[j] = oldSymbols[j];
+ }
+ bool successfulInsertion =
+ owner.noncoverage->insert(separateCopyOfSymbols).second;
+ assert(successfulInsertion);
+ (void)successfulInsertion; //This is unused without assertions.
+ }
+ } else {
+ --owner.multipleCoverageCount;
+ }
+ if (++owner.coverage.hintGet(hint, columns, firsts, counts, newSymbols) ==
+ 1) {
+ ++owner.coverageCount;
+ if (owner.trackingNoncoverage) {
+ Array<unsigned>separateCopyOfSymbols(newSymbols.getSize());
+ for (unsigned j = newSymbols.getSize(); j--;) {
+ separateCopyOfSymbols[j] = newSymbols[j];
+ }
+ bool successfulErasure =
+ (bool)owner.noncoverage->erase(separateCopyOfSymbols);
+ assert(successfulErasure);
+ (void)successfulErasure; // This is unused without assertions.
+ }
+ } else {
+ ++owner.multipleCoverageCount;
+ }
+ }
+ owner.autoFinalizeSubstitutions();
+}
+
+CoveringArray::Row::operator Array<unsigned>() const {
+ typedef map<pair<unsigned,unsigned>,unsigned>::const_iterator Substitution;
+ Substitution end = owner.substitutions->end();
+ Array<unsigned>result(owner.getOptions());
+ for (pair<unsigned, unsigned>key(row, result.getSize()); key.second--;) {
+ Substitution substitution = owner.substitutions->find(key);
+ result[key.second] =
+ (substitution == end) ?
+ owner.array[row][key.second] :
+ substitution->second;
+ }
+ return result;
+}
+
+CoveringArray::Row&CoveringArray::Row::operator =(const Array<unsigned>values) {
+ if (owner.trackingCoverage) {
+ updateTracking(values);
+ }
+ for (pair<unsigned, unsigned>key(row, owner.getOptions()); key.second--;) {
+ (*owner.substitutions)[key] = values[key.second];
+ }
+ return *this;
+}
diff --git a/casa/covering/state/CoveringArraySubRow.C b/casa/covering/state/CoveringArraySubRow.C
new file mode 100644
index 0000000..b66f546
--- /dev/null
+++ b/casa/covering/state/CoveringArraySubRow.C
@@ -0,0 +1,129 @@
+// 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 "covering/state/CoveringArray.H"
+#include "CombinadicIterator.H"
+
+using namespace std;
+
+void CoveringArray::SubRow::updateTracking(const Array<unsigned>values) {
+ assert(values.getSize() == columns.getSize());
+ const Options&options = owner.coverage.getOptions();
+ unsigned strength = owner.coverage.getStrength();
+ unsigned limit = options.getSize();
+ unsigned changes = 0;
+ Array<unsigned>oldRow(limit);
+ Array<unsigned>newRow(limit);
+ Array<unsigned>changedColumns(columns.getSize());
+ for (unsigned i = limit; i--;) {
+ oldRow[i] = owner(row, i);
+ }
+ for (unsigned i = limit, j = values.getSize(); i--;) {
+ if (j && (columns[j - 1] == i)) {
+ newRow[i] = values[--j];
+ } else {
+ newRow[i] = oldRow[i];
+ }
+ }
+ for (unsigned i = 0; i < limit; ++i) {
+ if (newRow[i] != oldRow[i]) {
+ changedColumns[changes++] = i;
+ }
+ }
+ changedColumns = Array<unsigned>(changedColumns, changes);
+ Array<unsigned>firsts = options.getFirstSymbols();
+ Array<unsigned>counts = options.getSymbolCounts();
+ for (CombinadicIterator combo(limit, strength, changedColumns);
+ combo;
+ ++combo) {
+ const Array<unsigned>updateColumns = *combo;
+ Array<unsigned>oldSymbols(strength);
+ Array<unsigned>newSymbols(strength);
+ for (unsigned j = strength; j--;) {
+ unsigned column = updateColumns[j];
+ oldSymbols[j] = oldRow[column];
+ newSymbols[j] = newRow[column];
+ }
+ Coverage<unsigned>::Entry lost =
+ owner.coverage.hintGet(updateColumns, firsts, counts, oldSymbols);
+ assert(lost); // Assert that what we lost is something we had to lose.
+ if (--lost == 0) {
+ --owner.coverageCount;
+ if (owner.trackingNoncoverage) {
+ Array<unsigned>separateCopyOfSymbols(oldSymbols.getSize());
+ for (unsigned j = oldSymbols.getSize(); j--;) {
+ separateCopyOfSymbols[j] = oldSymbols[j];
+ }
+ bool successfulInsertion =
+ owner.noncoverage->insert(separateCopyOfSymbols).second;
+ assert(successfulInsertion);
+ (void)successfulInsertion; // This is unused without assertions.
+ }
+ } else {
+ --owner.multipleCoverageCount;
+ }
+ Coverage<unsigned>::Entry gained =
+ owner.coverage.hintGet(updateColumns, firsts, counts, newSymbols);
+ if (++gained == 1) {
+ ++owner.coverageCount;
+ if (owner.trackingNoncoverage) {
+ Array<unsigned>separateCopyOfSymbols(newSymbols.getSize());
+ for (unsigned j = newSymbols.getSize(); j--;) {
+ separateCopyOfSymbols[j] = newSymbols[j];
+ }
+ bool successfulErasure =
+ (bool)owner.noncoverage->erase(separateCopyOfSymbols);
+ assert(successfulErasure);
+ (void)successfulErasure; // This is unused without assertions.
+ }
+ } else {
+ ++owner.multipleCoverageCount;
+ }
+ }
+ owner.autoFinalizeSubstitutions();
+}
+
+CoveringArray::SubRow::operator Array<unsigned>() const {
+ typedef map<pair<unsigned, unsigned>, unsigned>::const_iterator Substitution;
+ Substitution end = owner.substitutions->end();
+ unsigned size = columns.getSize();
+ Array<unsigned>result(size);
+ pair<unsigned, unsigned>key(row,0);
+ for (unsigned i = size; i--;) {
+ key.second = columns[i];
+ Substitution substitution = owner.substitutions->find(key);
+ result[i] =
+ (substitution == end) ?
+ owner.array[row][key.second] :
+ substitution->second;
+ }
+ return result;
+}
+CoveringArray::SubRow&CoveringArray::SubRow::operator =
+ (const Array<unsigned>values) {
+ assert(values.getSize() == columns.getSize());
+ if (owner.trackingCoverage) {
+ updateTracking(values);
+ }
+ pair<unsigned, unsigned>key(row, 0);
+ for (unsigned i = columns.getSize(); i--;) {
+ key.second = columns[i];
+ (*owner.substitutions)[key] = values[i];
+ }
+ return *this;
+}
generated by cgit v1.2.1 (git 2.18.0) at 2024-04-28 12:33:50 +0000