6 files changed, 615 insertions, 0 deletions
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