summaryrefslogtreecommitdiff
path: root/common/utility
diff options
context:
space:
mode:
Diffstat (limited to 'common/utility')
-rw-r--r--common/utility/Array.H128
-rw-r--r--common/utility/Combinadic.C129
-rw-r--r--common/utility/Combinadic.H42
-rw-r--r--common/utility/CombinadicIterator.C104
-rw-r--r--common/utility/CombinadicIterator.H51
-rw-r--r--common/utility/Lazy.H110
-rw-r--r--common/utility/PascalTriangle.C52
-rw-r--r--common/utility/PascalTriangle.H38
-rw-r--r--common/utility/SubstitutionArray.H191
-rw-r--r--common/utility/igreater.H36
-rw-r--r--common/utility/iless.H36
-rw-r--r--common/utility/pgreater.H32
-rw-r--r--common/utility/pless.H32
-rw-r--r--common/utility/relation.H260
14 files changed, 1241 insertions, 0 deletions
diff --git a/common/utility/Array.H b/common/utility/Array.H
new file mode 100644
index 0000000..155bad7
--- /dev/null
+++ b/common/utility/Array.H
@@ -0,0 +1,128 @@
+// 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 ARRAY_H
+#define ARRAY_H
+
+#include <iostream>
+
+template<class T>class Array {
+protected:
+ unsigned size;
+ T* array;
+ unsigned* referenceCount;
+
+ void destroy() {
+ if (referenceCount && !(--*referenceCount)) {
+ delete[] array;
+ delete referenceCount;
+ }
+ array = NULL;
+ }
+
+public:
+ Array() :
+ size(0),
+ array(NULL),
+ referenceCount(NULL) {}
+ Array(unsigned size) :
+ size(size),
+ array(new T[size]),
+ referenceCount(new unsigned(1)) {}
+ Array(const T*raw, unsigned size) :
+ size(size),
+ array(new T[size]),
+ referenceCount(new unsigned(1)) {
+ for (unsigned i = size; i-- > 0;) {
+ array[i] = raw[i];
+ }
+ }
+ Array(const Array&copy) :
+ size(copy.size),
+ array(copy.array),
+ referenceCount(copy.referenceCount) {
+ if (referenceCount) {
+ ++*referenceCount;
+ }
+ }
+
+ Array&operator =(const Array&copy) {
+ destroy();
+ size = copy.size;
+ array = copy.array;
+ referenceCount = copy.referenceCount;
+ ++*referenceCount;
+ return *this;
+ }
+
+ virtual ~Array() {
+ destroy();
+ }
+
+ unsigned getSize() const {
+ return size;
+ }
+
+ operator const T*() const {
+ return array;
+ }
+ operator T*() {
+ return array;
+ }
+
+ void fill(const T&filler) {
+ for (unsigned i = size; i--;) {
+ array[i] = filler;
+ }
+ }
+};
+
+template<class T>std::ostream&operator <<
+ (std::ostream&out, const Array<T>&array) {
+ out << '[';
+ for (unsigned i = 0; i < array.getSize(); ++i) {
+ out << array[i] << ',';
+ }
+ return out << "X]";
+}
+
+template<class T,class COMPARE = std::less<T> >class ArrayComparator {
+public:
+ bool operator()(const Array<T>&left, const Array<T>&right) const {
+ static COMPARE compare;
+ unsigned leftSize = left.getSize();
+ unsigned rightSize = right.getSize();
+ if (leftSize < rightSize) {
+ return true;
+ }
+ if (leftSize > rightSize) {
+ return false;
+ }
+ for (unsigned i = 0; i < leftSize; ++i) {
+ if (compare(left[i], right[i])) {
+ return true;
+ }
+ if (compare(right[i], left[i])) {
+ return false;
+ }
+ }
+ return false;
+ }
+};
+
+#endif
diff --git a/common/utility/Combinadic.C b/common/utility/Combinadic.C
new file mode 100644
index 0000000..812a7d1
--- /dev/null
+++ b/common/utility/Combinadic.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 <cassert>
+
+#include "Combinadic.H"
+
+using namespace std;
+
+static double TWO_PI = 2 * M_PI;
+static double INVERSE_E = 1 / M_E;
+
+// We want result to approximately satisfy
+// cardinality! * encoding = result * (result-1) * ... * (result-(cardinality-1))
+// The right-hand side usually has degree >= 5, so we need to trivialize it a bit.
+// It can be replaced with the overapproximation:
+// cardinality! * encoding = (result - (cardinality-1) / 2) ^ cardinality
+// Factorials are also expensive, so we use Stirling's approximation:
+// sqrt(TWO_PI * cardinality) * ((cardinality / e) ^ cardinality) * encoding =
+// (result - (cardinality-1) / 2) ^ cardinality
+// Now, to solve for result, take the cardinality'th root of both sides:
+// (cardinality / e) *
+// (encoding * sqrt(TWO_PI * cardinality)) ^ (1 / cardinality) =
+// result - (cardinality - 1)/2
+// And then rearrange that and add a half to make the flooring round to nearest:
+// result =
+// (cardinality / e) *
+// (encoding * sqrt(TWO_PI * cardinality)) ^ (1 / cardinality) +
+// cardinality / 2 =
+// ((1 / e) *
+// (encoding * sqrt(TWO_PI * cardinality)) ^ (1 / cardinality) + 0.5) *
+// cardinality
+unsigned Combinadic::guessLastMember(unsigned encoding, unsigned cardinality) {
+ double scaledEncoding = encoding * sqrt(TWO_PI * cardinality);
+ double rootOfEncoding = pow(scaledEncoding, 1.0 / cardinality);
+ return (unsigned)((INVERSE_E * rootOfEncoding + 0.5) * (double)cardinality);
+}
+
+pair<unsigned, unsigned>Combinadic::getLastMemberAndContribution
+ (unsigned encoding, unsigned cardinality) {
+ unsigned member = guessLastMember(encoding, cardinality);
+ unsigned contribution = triangle.nCr(member, cardinality);
+ if (contribution > encoding) {
+ do {
+ contribution = triangle.nCr(--member, cardinality);
+ } while (contribution > encoding);
+ } else {
+ unsigned nextContribution = triangle.nCr(member + 1, cardinality);
+ while (nextContribution <= encoding) {
+ ++member;
+ contribution = nextContribution;
+ nextContribution = triangle.nCr(member + 1, cardinality);
+ }
+ }
+ return pair<unsigned, unsigned>(member, contribution);
+}
+
+unsigned Combinadic::encode(Array<unsigned>sortedSubset) {
+ unsigned result = 0;
+ for (unsigned i = 0; i < sortedSubset.getSize(); ++i) {
+ result += triangle.nCr(sortedSubset[i], i + 1);
+ }
+ return result;
+}
+
+Array<unsigned>Combinadic::decode(unsigned encoding, unsigned cardinality) {
+ Array<unsigned>result(cardinality);
+ for (unsigned i = cardinality; i;) {
+ pair<unsigned, unsigned>memberAndContribution =
+ getLastMemberAndContribution(encoding, i);
+ result[--i] = memberAndContribution.first;
+ encoding -= memberAndContribution.second;
+ }
+ return result;
+}
+
+Array<unsigned>Combinadic::begin(unsigned size) const {
+ Array<unsigned>result(size);
+ for(unsigned i = size; i-- ;) {
+ result[i]=i;
+ }
+ return result;
+}
+
+void Combinadic::previous(Array<unsigned>sortedSubset) const {
+ assert(sortedSubset.getSize());
+ unsigned limit = sortedSubset.getSize();
+ for(unsigned i = 0; i < limit; ++i) {
+ unsigned entry = sortedSubset[i];
+ if (entry > i) {
+ do {
+ sortedSubset[i] = --entry;
+ } while (i-- > 0);
+ return;
+ }
+ }
+}
+
+void Combinadic::next(Array<unsigned>sortedSubset) const {
+ assert(sortedSubset.getSize());
+ unsigned limit = sortedSubset.getSize() - 1, ceiling = sortedSubset[0];
+ for (unsigned i = 0; i < limit; ++i) {
+ unsigned entry = ceiling + 1;
+ ceiling = sortedSubset[i + 1];
+ if (entry < ceiling) {
+ sortedSubset[i] = entry;
+ return;
+ }
+ sortedSubset[i] = i;
+ }
+ ++sortedSubset[limit];
+}
+
+Combinadic combinadic;
diff --git a/common/utility/Combinadic.H b/common/utility/Combinadic.H
new file mode 100644
index 0000000..5edca67
--- /dev/null
+++ b/common/utility/Combinadic.H
@@ -0,0 +1,42 @@
+// 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 COMBINADIC_H
+#define COMBINADIC_H
+
+#include <math.h>
+
+#include "Array.H"
+#include "PascalTriangle.H"
+
+class Combinadic {
+protected:
+ unsigned guessLastMember(unsigned encoding, unsigned cardinality);
+ std::pair<unsigned, unsigned>getLastMemberAndContribution
+ (unsigned encoding, unsigned cardinality);
+public:
+ unsigned encode(Array<unsigned>sortedSubset);
+ Array<unsigned>decode(unsigned encoding, unsigned cardinality);
+ Array<unsigned>begin(unsigned size) const;
+ void previous(Array<unsigned>sortedSubset) const;
+ void next(Array<unsigned>sortedSubset) const;
+};
+
+extern Combinadic combinadic;
+
+#endif
diff --git a/common/utility/CombinadicIterator.C b/common/utility/CombinadicIterator.C
new file mode 100644
index 0000000..15152cb
--- /dev/null
+++ b/common/utility/CombinadicIterator.C
@@ -0,0 +1,104 @@
+// Copyright 2008, 2009 Brady J. Garvin
+
+// This file is part of Covering Arrays by Simulated Annealing (CASA).
+
+// CASA is free software: you can redistribute it and/or modify it
+// under the terms of the GNU General Public License as published by
+// the Free Software Foundation, either version 3 of the License, or
+// (at your option) any later version.
+
+// CASA is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with CASA. If not, see <http://www.gnu.org/licenses/>.
+
+
+#include <cassert>
+#include <algorithm>
+
+#include "CombinadicIterator.H"
+
+using namespace std;
+
+CombinadicIterator::CombinadicIterator
+ (unsigned populationSize, unsigned sampleSize, Array<unsigned>relevant) :
+ populationSize(populationSize),
+ relevant(relevant),
+ notRelevant(populationSize - relevant.getSize()),
+ minimumRelevance(max((int)sampleSize - (int)notRelevant.getSize(), 1)),
+ maximumRelevance(min(relevant.getSize(), sampleSize)),
+ choiceFromRelevant(combinadic.begin(maximumRelevance)),
+ choiceFromNotRelevant(combinadic.begin(sampleSize - maximumRelevance)),
+ relevantCombination(sampleSize),
+ combination(sampleSize) {
+ assert(sampleSize <= populationSize);
+ for (unsigned i = 0, j = 0, k = 0; i < notRelevant.getSize(); ++i, ++j) {
+ while (k < relevant.getSize() && relevant[k] == j) {
+ ++j;
+ ++k;
+ }
+ notRelevant[i] = j;
+ }
+ updateCombinationFromRelevant();
+ updateCombination();
+}
+
+void CombinadicIterator::updateCombinationFromRelevant() {
+ for (unsigned i = maximumRelevance; i--;) {
+ relevantCombination[i] = relevant[choiceFromRelevant[i]];
+ }
+}
+
+void CombinadicIterator::updateCombination() {
+ for (unsigned i = combination.getSize(); i-- > maximumRelevance;) {
+ combination[i] = notRelevant[choiceFromNotRelevant[i - maximumRelevance]];
+ }
+ for (unsigned i = maximumRelevance; i--;) {
+ combination[i] = relevantCombination[i];
+ }
+ sort(combination + 0, combination + combination.getSize());
+}
+
+const Array<unsigned>CombinadicIterator::operator *() const {
+#ifndef NDEBUG
+ for (unsigned i = combination.getSize(); --i;) {
+ assert(combination[i - 1] < combination[i]);
+ }
+#endif
+ return combination;
+}
+
+CombinadicIterator::operator bool() const {
+ return combination.getSize();
+}
+
+CombinadicIterator&CombinadicIterator::operator ++() {
+ if (!combination.getSize()) {
+ return *this;
+ }
+ bool someFromNotRelevant = choiceFromNotRelevant.getSize();
+ if (someFromNotRelevant) {
+ combinadic.next(choiceFromNotRelevant);
+ }
+ if (!someFromNotRelevant ||
+ choiceFromNotRelevant[choiceFromNotRelevant.getSize() - 1] >=
+ populationSize - relevant.getSize()) {
+ combinadic.next(choiceFromRelevant);
+ if (choiceFromRelevant[maximumRelevance - 1] >= relevant.getSize()) {
+ --maximumRelevance;
+ if (maximumRelevance < minimumRelevance) {
+ combination = Array<unsigned>(0);
+ return *this;
+ }
+ choiceFromRelevant = combinadic.begin(maximumRelevance);
+ }
+ updateCombinationFromRelevant();
+ choiceFromNotRelevant =
+ combinadic.begin(combination.getSize() - maximumRelevance);
+ }
+ updateCombination();
+ return *this;
+}
diff --git a/common/utility/CombinadicIterator.H b/common/utility/CombinadicIterator.H
new file mode 100644
index 0000000..faeed39
--- /dev/null
+++ b/common/utility/CombinadicIterator.H
@@ -0,0 +1,51 @@
+// 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 COMBINADIC_ITERATOR_H
+#define COMBINADIC_ITERATOR_H
+
+#include "Combinadic.H"
+
+class CombinadicIterator {
+protected:
+ unsigned populationSize;
+ // The iteration will skip sets whose intersection with relevant is empty.
+ Array<unsigned> relevant;
+ Array<unsigned> notRelevant;
+
+ unsigned minimumRelevance;
+ unsigned maximumRelevance;
+
+ Array<unsigned> choiceFromRelevant;
+ Array<unsigned> choiceFromNotRelevant;
+
+ Array<unsigned> relevantCombination;
+ Array<unsigned> combination;
+public:
+ CombinadicIterator
+ (unsigned populationSize, unsigned sampleSize, Array<unsigned>relevant);
+protected:
+ void updateCombinationFromRelevant();
+ void updateCombination();
+public:
+ const Array<unsigned>operator *() const;
+ operator bool() const;
+ CombinadicIterator&operator ++();
+};
+
+#endif
diff --git a/common/utility/Lazy.H b/common/utility/Lazy.H
new file mode 100644
index 0000000..84bf426
--- /dev/null
+++ b/common/utility/Lazy.H
@@ -0,0 +1,110 @@
+// 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 LAZY_H
+#define LAZY_H
+
+#include <cassert>
+#include <iostream>
+
+template<class T>class Lazy {
+protected:
+ T* implementation;
+ unsigned* referenceCount;
+
+ void destroy() {
+ if (referenceCount) {
+ assert(implementation);
+ if (!(--*referenceCount)) {
+ delete implementation;
+ delete referenceCount;
+ }
+ implementation = NULL;
+ } else {
+ assert(!implementation);
+ }
+ }
+
+public:
+ Lazy() :
+ implementation(NULL),
+ referenceCount(NULL) {}
+ Lazy(T*implementation) :
+ implementation(implementation),
+ referenceCount(implementation ? new unsigned(1) : NULL) {}
+ Lazy(const Lazy&copy) :
+ implementation(copy.implementation),
+ referenceCount(copy.referenceCount) {
+ if (implementation) {
+ assert(referenceCount);
+ ++*referenceCount;
+ } else {
+ assert(!referenceCount);
+ }
+ }
+
+ Lazy&operator =(T*implementation) {
+ destroy();
+ this->implementation = implementation;
+ this->referenceCount = implementation ? new unsigned(1) : NULL;
+ return *this;
+ }
+ Lazy&operator =(const Lazy&copy) {
+ destroy();
+ implementation = copy.implementation;
+ if (implementation) {
+ referenceCount = copy.referenceCount;
+ assert(referenceCount);
+ ++*referenceCount;
+ } else {
+ assert(!copy.referenceCount);
+ referenceCount = NULL;
+ }
+ return *this;
+ }
+
+ virtual ~Lazy(){
+ destroy();
+ }
+
+ const T*operator ->() const {
+ return implementation;
+ }
+ T*operator ->() {
+ if (referenceCount) {
+ assert(implementation);
+ if (*referenceCount > 1) {
+ T*copy = new T(*implementation);
+ destroy();
+ implementation = copy;
+ referenceCount = new unsigned(1);
+ }
+ } else {
+ assert(!implementation);
+ }
+ return implementation;
+ }
+ operator const T*() const {
+ return operator ->();
+ }
+ operator T*() {
+ return operator ->();
+ }
+};
+
+#endif
diff --git a/common/utility/PascalTriangle.C b/common/utility/PascalTriangle.C
new file mode 100644
index 0000000..5a7c378
--- /dev/null
+++ b/common/utility/PascalTriangle.C
@@ -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/>.
+
+
+#include "PascalTriangle.H"
+
+PascalTriangle::PascalTriangle() {
+ Array<unsigned>root(1);
+ root[0] = 1;
+ table.push_back(root);
+}
+
+void PascalTriangle::addRows(unsigned targetDepth) {
+ while (table.size() <= targetDepth) {
+ unsigned depth = table.size();
+ Array<unsigned>line(depth + 1);
+ Array<unsigned>source = table[depth - 1];
+ table.push_back(line);
+ line[0] = 1;
+ for (unsigned column = 1, trail = source[0]; column < depth; ++column) {
+ line[column] = trail;
+ line[column] += trail = source[column];
+ }
+ line[depth] = 1;
+ }
+}
+
+unsigned PascalTriangle::nCr(unsigned n, unsigned r) {
+ if (n >= table.size()) {
+ addRows(n);
+ }
+ if (r > n) {
+ return 0;
+ }
+ return table[n][r];
+}
+
+PascalTriangle triangle;
diff --git a/common/utility/PascalTriangle.H b/common/utility/PascalTriangle.H
new file mode 100644
index 0000000..fd7c5e0
--- /dev/null
+++ b/common/utility/PascalTriangle.H
@@ -0,0 +1,38 @@
+// 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 PASCAL_TRIANGLE_H
+#define PASCAL_TRIANGLE_H
+
+#include <vector>
+
+#include "Array.H"
+
+class PascalTriangle {
+protected:
+ // A table of n choose r, indexed by n then r.
+ std::vector<Array<unsigned> > table;
+public:
+ PascalTriangle();
+ void addRows(unsigned targetDepth);
+ unsigned nCr(unsigned n, unsigned r);
+};
+
+extern PascalTriangle triangle;
+
+#endif
diff --git a/common/utility/SubstitutionArray.H b/common/utility/SubstitutionArray.H
new file mode 100644
index 0000000..48bfbca
--- /dev/null
+++ b/common/utility/SubstitutionArray.H
@@ -0,0 +1,191 @@
+// 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 SUBSTITUTION_ARRAY_H
+#define SUBSTITUTION_ARRAY_H
+
+#include <iostream>
+#include <map>
+
+#include "Array.H"
+#include "Lazy.H"
+
+#ifndef MAXIMUM_SUBSTITUTION_PROPORTION
+#define MAXIMUM_SUBSTITUTION_PROPORTION 0.1F
+#endif
+
+template<class T>class SubstitutionArray : protected Array<T> {
+protected:
+ Lazy<std::map<unsigned, T> > substitutions;
+ unsigned maximumSubstitutions;
+
+public:
+ SubstitutionArray() : Array<T>() {}
+ SubstitutionArray(unsigned size) :
+ Array<T>(size),
+ maximumSubstitutions(MAXIMUM_SUBSTITUTION_PROPORTION * size) {}
+ SubstitutionArray(const T*raw, unsigned size) :
+ Array<T>(raw, size),
+ maximumSubstitutions(MAXIMUM_SUBSTITUTION_PROPORTION * size) {}
+ SubstitutionArray(const Array<T>&copy) :
+ Array<T>(copy),
+ maximumSubstitutions(MAXIMUM_SUBSTITUTION_PROPORTION * Array<T>::size) {}
+ SubstitutionArray(const SubstitutionArray&copy) :
+ Array<T>((const Array<T>&)copy),
+ substitutions(copy.substitutions),
+ maximumSubstitutions(copy.maximumSubstitutions) {}
+
+ SubstitutionArray&operator =(const Array<T>&copy) {
+ Array<T>::operator =(copy);
+ substitutions = NULL;
+ maximumSubstitutions = MAXIMUM_SUBSTITUTION_PROPORTION * Array<T>::size;
+ return *this;
+ }
+ SubstitutionArray&operator =(const SubstitutionArray<T>&copy) {
+ Array<T>::operator =((const Array<T>&)copy);
+ substitutions = copy.substitutions;
+ maximumSubstitutions = MAXIMUM_SUBSTITUTION_PROPORTION * Array<T>::size;
+ return *this;
+ }
+
+ unsigned getSize() const {
+ return Array<T>::getSize();
+ }
+
+ class Entry {
+ protected:
+ SubstitutionArray& owner;
+ unsigned index;
+ public:
+ Entry(const SubstitutionArray&owner, unsigned index) :
+ owner(const_cast<SubstitutionArray&>(owner)),
+ index(index) {}
+
+ operator T() const {
+ if (owner.substitutions) {
+ std::map<unsigned, unsigned>::const_iterator substitution =
+ owner.substitutions->find(index);
+ if (substitution != owner.substitutions->end()) {
+ return substitution->second;
+ }
+ }
+ return owner.array[index];
+ }
+
+ Entry&operator =(const T&value) {
+ if (*owner.referenceCount > 1) {
+ if (!owner.substitutions) {
+ owner.substitutions = new std::map<unsigned, T>();
+ }
+ (*owner.substitutions)[index] = value;
+ owner.autoFinalizeSubstitutions();
+ } else {
+ owner.array[index] = value;
+ }
+ return *this;
+ }
+
+ Entry&operator --() {
+ T old = operator T();
+ return operator =(--old);
+ }
+ Entry&operator ++() {
+ T old = operator T();
+ return operator =(++old);
+ }
+ };
+
+ const Entry operator[](unsigned index) const {
+ return Entry(*this, index);
+ }
+ Entry operator[](unsigned index) {
+ return Entry(*this, index);
+ }
+
+ void fill(const T&filler) {
+ if (*Array<T>::referenceCount > 1) {
+ Array<T>::destroy();
+ Array<T>::array = new T[Array<T>::size];
+ Array<T>::referenceCount = new unsigned(1);
+ substitutions = NULL;
+ }
+ Array<T>::fill(filler);
+ }
+
+ void finalizeSubstitutions() {
+ if (!substitutions) {
+ return;
+ }
+ T*replacement = new T[Array<T>::size];
+ for (unsigned i = Array<T>::size; i--;) {
+ replacement[i] = Array<T>::array[i];
+ }
+ for (typename std::map<unsigned, T>::const_iterator iterator =
+ substitutions->begin(),
+ end = substitutions->end();
+ iterator != end; ++iterator) {
+ replacement[iterator->first] = iterator->second;
+ }
+ Array<T>::destroy();
+ Array<T>::array = replacement;
+ Array<T>::referenceCount = new unsigned(1);
+ substitutions->clear();
+ }
+
+ void autoFinalizeSubstitutions(){
+ if (substitutions && substitutions->size() > maximumSubstitutions) {
+ finalizeSubstitutions();
+ }
+ }
+};
+
+template<class T>std::ostream&operator <<
+ (std::ostream&out, const SubstitutionArray<T>&array) {
+ out << '[';
+ for (unsigned i = 0; i < array.getSize(); ++i) {
+ out << array[i] << ',';
+ }
+ return out << "X]";
+}
+
+template<class T, class COMPARE = std::less<T> >
+ class SubstitutionArrayComparator {
+public:
+ bool operator()(const Array<T>&left,const Array<T>&right) {
+ static COMPARE compare;
+ unsigned leftSize = left.getSize();
+ unsigned rightSize = right.getSize();
+ if (leftSize < rightSize) {
+ return true;
+ }
+ if (leftSize > rightSize) {
+ return false;
+ }
+ for (unsigned i = 0; i < leftSize; ++i) {
+ if (compare(left[i], right[i])) {
+ return true;
+ }
+ if (compare(right[i], left[i])) {
+ return false;
+ }
+ }
+ return false;
+ }
+};
+
+#endif
diff --git a/common/utility/igreater.H b/common/utility/igreater.H
new file mode 100644
index 0000000..a32d62c
--- /dev/null
+++ b/common/utility/igreater.H
@@ -0,0 +1,36 @@
+// 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 IGREATER_H
+#define IGREATER_H
+
+// Compares two indices by the elements in an array at those locations. Returns
+// true if the left indexth element is greater than the right indexth element.
+
+template<class T>class igreater {
+protected:
+ const T* array;
+public:
+ igreater(const T*array) :
+ array(array) {}
+ bool operator ()(unsigned left, unsigned right) const {
+ return array[right] < array[left];
+ }
+};
+
+#endif
diff --git a/common/utility/iless.H b/common/utility/iless.H
new file mode 100644
index 0000000..58aa7dc
--- /dev/null
+++ b/common/utility/iless.H
@@ -0,0 +1,36 @@
+// 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 ILESS_H
+#define ILESS_H
+
+// Compares two indices by the elements in an array at those locations. Returns
+// true if the left indexth element is less than the right indexth element.
+
+template<class T>class iless {
+protected:
+ const T* array;
+public:
+ iless(const T*array) :
+ array(array) {}
+ bool operator ()(unsigned left, unsigned right) const {
+ return array[left] < array[right];
+ }
+};
+
+#endif
diff --git a/common/utility/pgreater.H b/common/utility/pgreater.H
new file mode 100644
index 0000000..6a0a007
--- /dev/null
+++ b/common/utility/pgreater.H
@@ -0,0 +1,32 @@
+// 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 PGREATER_H
+#define PGREATER_H
+
+// Compares two pointers by the objects they point to. Returns true if
+// dereferenced left is greater than dereferenced right.
+
+template<class T>class pgreater {
+public:
+ bool operator ()(const T*left, const T*right) const {
+ return *right < *left;
+ }
+};
+
+#endif
diff --git a/common/utility/pless.H b/common/utility/pless.H
new file mode 100644
index 0000000..f79d76a
--- /dev/null
+++ b/common/utility/pless.H
@@ -0,0 +1,32 @@
+// 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 PLESS_H
+#define PLESS_H
+
+// Compares two pointers by the objects they point to. Returns true if
+// dereferenced left is less than dereferenced right.
+
+template<class T>class pless {
+public:
+ bool operator ()(const T*left, const T*right) const {
+ return *left < *right;
+ }
+};
+
+#endif
diff --git a/common/utility/relation.H b/common/utility/relation.H
new file mode 100644
index 0000000..1c5f0ad
--- /dev/null
+++ b/common/utility/relation.H
@@ -0,0 +1,260 @@
+// 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 RELATION_H
+#define RELATION_H
+
+#include <cassert>
+#include <iostream>
+#include <set>
+#include <map>
+
+// A bidirectional (multi-)map where either the either the key or data type (or
+// both) can be forced to be unique.
+
+// Naming conventions (including abbreviations in identifier names) here
+// resemble those used in the STL, rather than the more Java-like standard in
+// the other code.
+
+template<class key_type, class data_type, bool unique_key, bool unique_data,
+ class key_compare = std::less<key_type>,
+ class data_compare = std::less<data_type> >class relation {
+protected:
+ typedef relation
+ <key_type, data_type, unique_key, unique_data, key_compare, data_compare>
+ relation_type;
+
+ std::multimap<key_type, data_type, key_compare>
+ by_key;
+ std::multimap<data_type, key_type, data_compare>
+ by_data;
+public:
+ typedef unsigned size_type;
+ typedef int difference_type;
+
+ // By-key iterators:
+#define KEY(type) \
+ typedef typename std::multimap<key_type, data_type, key_compare>::type \
+ key_ ## type
+ KEY(iterator);
+ KEY(const_iterator);
+ KEY(reverse_iterator);
+ KEY(const_reverse_iterator);
+#undef KEY
+
+ // By-data iterators:
+#define DATA(type) \
+ typedef typename std::multimap<data_type, key_type, data_compare>::type \
+ data_ ## type
+ DATA(iterator);
+ DATA(const_iterator);
+ DATA(reverse_iterator);
+ DATA(const_reverse_iterator);
+#undef DATA
+
+ // Create, copy, and delete:
+ relation() {}
+ relation(const key_compare&key_comp, const data_compare&data_comp) :
+ by_key(key_comp),
+ by_data(data_comp) {}
+ relation(const relation_type&copy) :
+ by_key(copy.by_key),
+ by_data(copy.by_data) {}
+ relation&operator =(const relation_type&copy) {
+ by_key = copy.by_key;
+ by_data = copy.by_data;
+ }
+ void swap(relation_type&other) {
+ by_key.swap(other.by_key);
+ by_data.swap(other.by_data);
+ }
+ virtual ~relation() {}
+ // Access and mutate:
+ // By key:
+ key_compare key_comp() const {
+ return by_key.key_comp();
+ }
+#define KEY(method, constness) key_ ## method() constness { \
+ return by_key.method(); \
+ }
+ key_iterator KEY(begin,);
+ key_iterator KEY(end,);
+ key_const_iterator KEY(begin, const);
+ key_const_iterator KEY(end, const);
+ key_reverse_iterator KEY(rbegin,);
+ key_reverse_iterator KEY(rend,);
+ key_const_reverse_iterator KEY(rbegin, const);
+ key_const_reverse_iterator KEY(rend, const);
+#undef KEY
+#define KEY(method,constness) key_ ## method(const key_type&key) constness { \
+ return by_key.method(key); \
+ }
+ key_iterator KEY(find,);
+ size_type KEY(count,);
+ key_iterator KEY(lower_bound,);
+ key_const_iterator KEY(lower_bound, const);
+ key_iterator KEY(upper_bound,);
+ key_const_iterator KEY(upper_bound, const);
+ std::pair<key_iterator, key_iterator> KEY(equal_range,);
+ std::pair<key_const_iterator, key_const_iterator> KEY(equal_range, const);
+#undef KEY
+ // (Return whether insertion was successful as second.)
+ std::pair<key_iterator, bool>key_insert
+ (const key_type&key, const data_type&data) {
+ key_iterator key_hint = by_key.find(key);
+ data_iterator data_hint = by_data.find(data);
+ if ((unique_key && key_hint != by_key.end()) ||
+ (unique_data && data_hint != by_data.end())) {
+ return std::pair<key_iterator, bool>(by_key.end(), false);
+ }
+ by_data.insert(data_hint, std::pair<data_type, key_type>(data, key));
+ return std::pair<key_iterator, bool>
+ (by_key.insert
+ (key_hint, std::pair<key_type, data_type>(key, data)), true);
+ }
+ void key_erase(key_iterator pos) {
+ std::pair<data_iterator, data_iterator>data_pos =
+ by_data.equal_range(pos->second);
+ key_type match = pos->first;
+ for (; data_pos.first != data_pos.second; ++data_pos.first) {
+ key_type&candidate = data_pos.first->second;
+ if (!by_key.key_comp()(candidate, match) &&
+ !by_key.key_comp()(match, candidate)) {
+ by_key.erase(pos);
+ by_data.erase(data_pos.first);
+ return;
+ }
+ }
+ assert(false);
+ }
+ size_type key_erase(const key_type&key) {
+ size_type result = 0;
+ std::pair<key_iterator, key_iterator>range = by_key.equal_range(key);
+ while (range.first != range.second) {
+ key_iterator tag = range.first++;
+ erase(tag);
+ ++result;
+ }
+ return result;
+ }
+
+ // By data:
+ data_compare data_comp() const {
+ return by_data.data_comp();
+ }
+#define DATA(method, constness) data_ ## method() constness { \
+ return by_data.method(); \
+ }
+ data_iterator DATA(begin,);
+ data_iterator DATA(end,);
+ data_const_iterator DATA(begin, const);
+ data_const_iterator DATA(end, const);
+ data_reverse_iterator DATA(rbegin,);
+ data_reverse_iterator DATA(rend,);
+ data_const_reverse_iterator DATA(rbegin, const);
+ data_const_reverse_iterator DATA(rend, const);
+#undef DATA
+#define DATA(method, constness) \
+ data_ ## method(const data_type&data) constness { \
+ return by_data.method(data); \
+ }
+ data_iterator DATA(find,);
+ size_type DATA(count,);
+ data_iterator DATA(lower_bound,);
+ data_const_iterator DATA(lower_bound, const);
+ data_iterator DATA(upper_bound,);
+ data_const_iterator DATA(upper_bound, const);
+ std::pair<data_iterator, data_iterator> DATA(equal_range,);
+ std::pair<data_const_iterator, data_const_iterator> DATA(equal_range, const);
+#undef DATA
+ // (Return whether insertion was successful as second.)
+ std::pair<data_iterator, bool>data_insert
+ (const key_type&key, const data_type&data) {
+ key_iterator key_hint = by_key.find(key);
+ data_iterator data_hint = by_data.find(data);
+ if ((unique_key && key_hint != by_key.end()) ||
+ (unique_data && data_hint != by_data.end())) {
+ return std::pair<data_iterator, bool>(by_data.end(), false);
+ }
+ by_key.insert(key_hint, std::pair<key_type, data_type>(key, data));
+ return std::pair<data_iterator, bool>
+ (by_data.insert
+ (data_hint, std::pair<data_type, key_type>(data, key)), true);
+ }
+ void data_erase(data_iterator pos) {
+ std::pair<key_iterator, key_iterator>key_pos = by_key.equal_range(pos->second);
+ data_type match = pos->first;
+ for (; key_pos.first != key_pos.second; ++key_pos.first) {
+ data_type&candidate = key_pos.first->second;
+ if (!by_data.key_comp()(candidate, match) &&
+ !by_data.key_comp()(match, candidate)) {
+ by_data.erase(pos);
+ by_key.erase(key_pos.first);
+ return;
+ }
+ }
+ assert(false);
+ }
+ size_type data_erase(const data_type&data) {
+ size_type result = 0;
+ std::pair<data_iterator, data_iterator>range = by_data.equal_range(data);
+ while (range.first != range.second) {
+ data_iterator tag = range.first++;
+ erase(tag);
+ ++result;
+ }
+ return result;
+ }
+
+ // Others:
+ void clear() {
+ by_key.clear();
+ by_data.clear();
+ }
+ size_type size() const {
+ assert(by_key.size() == by_data.size());
+ return by_key.size();
+ }
+ size_type max_size() const {
+ assert(by_key.max_size() == by_data.max_size());
+ return by_key.max_size();
+ }
+ bool empty() const {
+ assert(by_key.empty() == by_data.empty());
+ return by_key.empty();
+ }
+};
+
+template<class key_type, class data_type, bool unique_key, bool unique_data,
+ class key_compare, class data_compare>std::ostream&operator <<
+ (std::ostream&out,
+ const relation<key_type, data_type, unique_key, unique_data, key_compare,
+ data_compare>&rel) {
+ out << "relation{\n";
+ for (typename relation<key_type, data_type, unique_key, unique_data,
+ key_compare, data_compare>::key_const_iterator iterator =
+ rel.key_begin(),
+ end = rel.key_end();
+ iterator != end;
+ ++iterator) {
+ out << " " << *(iterator->first) << " with " << iterator->second << '\n';
+ }
+ return out << "}\n";
+}
+
+#endif
generated by cgit v1.2.1 (git 2.18.0) at 2024-04-28 03:43:05 +0000