summaryrefslogtreecommitdiff
path: root/casa/covering/state
diff options
context:
space:
mode:
Diffstat (limited to 'casa/covering/state')
-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
5 files changed, 784 insertions, 0 deletions
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-05-02 01:44:39 +0000