diff options
Diffstat (limited to 'casa/covering/bookkeeping')
-rw-r--r-- | casa/covering/bookkeeping/Coverage.H | 313 | ||||
-rw-r--r-- | casa/covering/bookkeeping/Options.C | 102 | ||||
-rw-r--r-- | casa/covering/bookkeeping/Options.H | 50 |
3 files changed, 465 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©) : + 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©) : + 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©) : + 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©); + 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 |