// 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 .
#ifndef COVERAGE_H
#define COVERAGE_H
#include "PascalTriangle.H"
#include "Combinadic.H"
#include "SubstitutionArray.H"
#include "covering/bookkeeping/Options.H"
templateclass 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 offsets;
SubstitutionArray contents;
public:
Coverage(unsigned strength, Options options) :
strength(strength),
options(options),
offsets(triangle.nCr(options.getSize(), strength)) {
unsigned size = 0;
unsigned offsetIndex = 0;
for (Arraycolumns = 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(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,
ArraycolumnsHint,
ArrayfirstsHint,
ArraycountsHint,
ArraysortedCombination) 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
(ArraycolumnsHint,
ArrayfirstsHint,
ArraycountsHint,
ArraysortedCombination) const {
return encode
(combinadic.encode(columnsHint),
columnsHint,
firstsHint,
countsHint,
sortedCombination);
}
unsigned encode(ArraysortedCombination) const {
assert(sortedCombination.getSize() == strength);
Arraycolumns(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.
Arraydecode(unsigned encoding) const {
unsigned offsetIndex = offsets.getSize();
while (offsets[--offsetIndex] > encoding);
unsigned index = encoding - offsets[offsetIndex];
Arraycolumns = combinadic.decode(offsetIndex, strength);
Arrayresult(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(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[](ArraysortedCombination) const {
return Entry(*this, encode(sortedCombination));
}
Entry operator [](ArraysortedCombination) {
return Entry(*this, encode(sortedCombination));
}
// The methods named hintGet work like the [] operator with the aforementioned
// hints.
const Entry hintGet
(unsigned indexHint,
ArraycolumnsHint,
ArrayfirstsHint,
ArraycountsHint,
ArraysortedCombination) const {
return Entry
(*this,
encode
(indexHint, columnsHint, firstsHint, countsHint, sortedCombination));
}
Entry hintGet
(unsigned indexHint,
ArraycolumnsHint,
ArrayfirstsHint,
ArraycountsHint,
ArraysortedCombination) {
return Entry
(*this,
encode
(indexHint, columnsHint, firstsHint, countsHint, sortedCombination));
}
const Entry hintGet
(ArraycolumnsHint,
ArrayfirstsHint,
ArraycountsHint,
ArraysortedCombination) const {
return Entry
(*this,
encode(columnsHint, firstsHint, countsHint, sortedCombination));
}
Entry hintGet
(ArraycolumnsHint,
ArrayfirstsHint,
ArraycountsHint,
ArraysortedCombination) {
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;
}
ArraygetCombination() 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;
}
ArraygetCombination() 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