From 76729f9670ba63a9146079b081bdb5b5ae0bbd3d Mon Sep 17 00:00:00 2001 From: Kenny Ballou Date: Fri, 28 Feb 2020 15:36:09 -0700 Subject: CASA fork: initial commit Snapshot from http://cse.unl.edu/~citportal/. --- common/posix/getopt.h | 177 ++++++++++++++++++++++++ common/utility/Array.H | 128 ++++++++++++++++++ common/utility/Combinadic.C | 129 ++++++++++++++++++ common/utility/Combinadic.H | 42 ++++++ common/utility/CombinadicIterator.C | 104 +++++++++++++++ common/utility/CombinadicIterator.H | 51 +++++++ common/utility/Lazy.H | 110 +++++++++++++++ common/utility/PascalTriangle.C | 52 ++++++++ common/utility/PascalTriangle.H | 38 ++++++ common/utility/SubstitutionArray.H | 191 ++++++++++++++++++++++++++ common/utility/igreater.H | 36 +++++ common/utility/iless.H | 36 +++++ common/utility/pgreater.H | 32 +++++ common/utility/pless.H | 32 +++++ common/utility/relation.H | 260 ++++++++++++++++++++++++++++++++++++ 15 files changed, 1418 insertions(+) create mode 100644 common/posix/getopt.h create mode 100644 common/utility/Array.H create mode 100644 common/utility/Combinadic.C create mode 100644 common/utility/Combinadic.H create mode 100644 common/utility/CombinadicIterator.C create mode 100644 common/utility/CombinadicIterator.H create mode 100644 common/utility/Lazy.H create mode 100644 common/utility/PascalTriangle.C create mode 100644 common/utility/PascalTriangle.H create mode 100644 common/utility/SubstitutionArray.H create mode 100644 common/utility/igreater.H create mode 100644 common/utility/iless.H create mode 100644 common/utility/pgreater.H create mode 100644 common/utility/pless.H create mode 100644 common/utility/relation.H (limited to 'common') diff --git a/common/posix/getopt.h b/common/posix/getopt.h new file mode 100644 index 0000000..feea50c --- /dev/null +++ b/common/posix/getopt.h @@ -0,0 +1,177 @@ +/* Declarations for getopt. + Copyright (C) 1989-1994,1996-1999,2001,2003,2004 + Free Software Foundation, Inc. + This file is part of the GNU C Library. + + The GNU C Library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + The GNU C Library 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 + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with the GNU C Library; if not, write to the Free + Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA + 02111-1307 USA. */ + +#ifndef _GETOPT_H + +#ifndef __need_getopt +# define _GETOPT_H 1 +#endif + +/* If __GNU_LIBRARY__ is not already defined, either we are being used + standalone, or this is the first header included in the source file. + If we are being used with glibc, we need to include , but + that does not exist if we are standalone. So: if __GNU_LIBRARY__ is + not defined, include , which will pull in for us + if it's from glibc. (Why ctype.h? It's guaranteed to exist and it + doesn't flood the namespace with stuff the way some other headers do.) */ +#if !defined __GNU_LIBRARY__ +# include +#endif + +#ifndef __THROW +# ifndef __GNUC_PREREQ +# define __GNUC_PREREQ(maj, min) (0) +# endif +# if defined __cplusplus && __GNUC_PREREQ (2,8) +# define __THROW throw () +# else +# define __THROW +# endif +#endif + +#ifdef __cplusplus +extern "C" { +#endif + +/* For communication from `getopt' to the caller. + When `getopt' finds an option that takes an argument, + the argument value is returned here. + Also, when `ordering' is RETURN_IN_ORDER, + each non-option ARGV-element is returned here. */ + +extern char *optarg; + +/* Index in ARGV of the next element to be scanned. + This is used for communication to and from the caller + and for communication between successive calls to `getopt'. + + On entry to `getopt', zero means this is the first call; initialize. + + When `getopt' returns -1, this is the index of the first of the + non-option elements that the caller should itself scan. + + Otherwise, `optind' communicates from one call to the next + how much of ARGV has been scanned so far. */ + +extern int optind; + +/* Callers store zero here to inhibit the error message `getopt' prints + for unrecognized options. */ + +extern int opterr; + +/* Set to an option character which was unrecognized. */ + +extern int optopt; + +#ifndef __need_getopt +/* Describe the long-named options requested by the application. + The LONG_OPTIONS argument to getopt_long or getopt_long_only is a vector + of `struct option' terminated by an element containing a name which is + zero. + + The field `has_arg' is: + no_argument (or 0) if the option does not take an argument, + required_argument (or 1) if the option requires an argument, + optional_argument (or 2) if the option takes an optional argument. + + If the field `flag' is not NULL, it points to a variable that is set + to the value given in the field `val' when the option is found, but + left unchanged if the option is not found. + + To have a long-named option do something other than set an `int' to + a compiled-in constant, such as set a value from `optarg', set the + option's `flag' field to zero and its `val' field to a nonzero + value (the equivalent single-letter option character, if there is + one). For long options that have a zero `flag' field, `getopt' + returns the contents of the `val' field. */ + +struct option +{ + const char *name; + /* has_arg can't be an enum because some compilers complain about + type mismatches in all the code that assumes it is an int. */ + int has_arg; + int *flag; + int val; +}; + +/* Names for the values of the `has_arg' field of `struct option'. */ + +# define no_argument 0 +# define required_argument 1 +# define optional_argument 2 +#endif /* need getopt */ + + +/* Get definitions and prototypes for functions to process the + arguments in ARGV (ARGC of them, minus the program name) for + options given in OPTS. + + Return the option character from OPTS just read. Return -1 when + there are no more options. For unrecognized options, or options + missing arguments, `optopt' is set to the option letter, and '?' is + returned. + + The OPTS string is a list of characters which are recognized option + letters, optionally followed by colons, specifying that that letter + takes an argument, to be placed in `optarg'. + + If a letter in OPTS is followed by two colons, its argument is + optional. This behavior is specific to the GNU `getopt'. + + The argument `--' causes premature termination of argument + scanning, explicitly telling `getopt' that there are no more + options. + + If OPTS begins with `--', then non-option arguments are treated as + arguments to the option '\0'. This behavior is specific to the GNU + `getopt'. */ + +#ifdef __GNU_LIBRARY__ +/* Many other libraries have conflicting prototypes for getopt, with + differences in the consts, in stdlib.h. To avoid compilation + errors, only prototype getopt for the GNU C library. */ +extern int getopt (int ___argc, char *const *___argv, const char *__shortopts) + __THROW; +/*#else // not __GNU_LIBRARY__ // +extern int getopt ();*/ +#endif /* __GNU_LIBRARY__ */ + +#ifndef __need_getopt +extern int getopt_long (int ___argc, char *const *___argv, + const char *__shortopts, + const struct option *__longopts, int *__longind) + __THROW; +extern int getopt_long_only (int ___argc, char *const *___argv, + const char *__shortopts, + const struct option *__longopts, int *__longind) + __THROW; + +#endif + +#ifdef __cplusplus +} +#endif + +/* Make sure we later can get all the definitions and declarations. */ +#undef __need_getopt + +#endif /* getopt.h */ 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 . + + +#ifndef ARRAY_H +#define ARRAY_H + +#include + +templateclass 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©) : + size(copy.size), + array(copy.array), + referenceCount(copy.referenceCount) { + if (referenceCount) { + ++*referenceCount; + } + } + + Array&operator =(const Array©) { + 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; + } + } +}; + +templatestd::ostream&operator << + (std::ostream&out, const Array&array) { + out << '['; + for (unsigned i = 0; i < array.getSize(); ++i) { + out << array[i] << ','; + } + return out << "X]"; +} + +template >class ArrayComparator { +public: + bool operator()(const Array&left, const Array&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 . + + +#include + +#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); +} + +pairCombinadic::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(member, contribution); +} + +unsigned Combinadic::encode(ArraysortedSubset) { + unsigned result = 0; + for (unsigned i = 0; i < sortedSubset.getSize(); ++i) { + result += triangle.nCr(sortedSubset[i], i + 1); + } + return result; +} + +ArrayCombinadic::decode(unsigned encoding, unsigned cardinality) { + Arrayresult(cardinality); + for (unsigned i = cardinality; i;) { + pairmemberAndContribution = + getLastMemberAndContribution(encoding, i); + result[--i] = memberAndContribution.first; + encoding -= memberAndContribution.second; + } + return result; +} + +ArrayCombinadic::begin(unsigned size) const { + Arrayresult(size); + for(unsigned i = size; i-- ;) { + result[i]=i; + } + return result; +} + +void Combinadic::previous(ArraysortedSubset) 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(ArraysortedSubset) 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 . + + +#ifndef COMBINADIC_H +#define COMBINADIC_H + +#include + +#include "Array.H" +#include "PascalTriangle.H" + +class Combinadic { +protected: + unsigned guessLastMember(unsigned encoding, unsigned cardinality); + std::pairgetLastMemberAndContribution + (unsigned encoding, unsigned cardinality); +public: + unsigned encode(ArraysortedSubset); + Arraydecode(unsigned encoding, unsigned cardinality); + Arraybegin(unsigned size) const; + void previous(ArraysortedSubset) const; + void next(ArraysortedSubset) 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 . + + +#include +#include + +#include "CombinadicIterator.H" + +using namespace std; + +CombinadicIterator::CombinadicIterator + (unsigned populationSize, unsigned sampleSize, Arrayrelevant) : + 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 ArrayCombinadicIterator::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(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 . + + +#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 relevant; + Array notRelevant; + + unsigned minimumRelevance; + unsigned maximumRelevance; + + Array choiceFromRelevant; + Array choiceFromNotRelevant; + + Array relevantCombination; + Array combination; +public: + CombinadicIterator + (unsigned populationSize, unsigned sampleSize, Arrayrelevant); +protected: + void updateCombinationFromRelevant(); + void updateCombination(); +public: + const Arrayoperator *() 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 . + + +#ifndef LAZY_H +#define LAZY_H + +#include +#include + +templateclass 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©) : + 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©) { + 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 . + + +#include "PascalTriangle.H" + +PascalTriangle::PascalTriangle() { + Arrayroot(1); + root[0] = 1; + table.push_back(root); +} + +void PascalTriangle::addRows(unsigned targetDepth) { + while (table.size() <= targetDepth) { + unsigned depth = table.size(); + Arrayline(depth + 1); + Arraysource = 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 . + + +#ifndef PASCAL_TRIANGLE_H +#define PASCAL_TRIANGLE_H + +#include + +#include "Array.H" + +class PascalTriangle { +protected: + // A table of n choose r, indexed by n then r. + std::vector > 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 . + + +#ifndef SUBSTITUTION_ARRAY_H +#define SUBSTITUTION_ARRAY_H + +#include +#include + +#include "Array.H" +#include "Lazy.H" + +#ifndef MAXIMUM_SUBSTITUTION_PROPORTION +#define MAXIMUM_SUBSTITUTION_PROPORTION 0.1F +#endif + +templateclass SubstitutionArray : protected Array { +protected: + Lazy > substitutions; + unsigned maximumSubstitutions; + +public: + SubstitutionArray() : Array() {} + SubstitutionArray(unsigned size) : + Array(size), + maximumSubstitutions(MAXIMUM_SUBSTITUTION_PROPORTION * size) {} + SubstitutionArray(const T*raw, unsigned size) : + Array(raw, size), + maximumSubstitutions(MAXIMUM_SUBSTITUTION_PROPORTION * size) {} + SubstitutionArray(const Array©) : + Array(copy), + maximumSubstitutions(MAXIMUM_SUBSTITUTION_PROPORTION * Array::size) {} + SubstitutionArray(const SubstitutionArray©) : + Array((const Array&)copy), + substitutions(copy.substitutions), + maximumSubstitutions(copy.maximumSubstitutions) {} + + SubstitutionArray&operator =(const Array©) { + Array::operator =(copy); + substitutions = NULL; + maximumSubstitutions = MAXIMUM_SUBSTITUTION_PROPORTION * Array::size; + return *this; + } + SubstitutionArray&operator =(const SubstitutionArray©) { + Array::operator =((const Array&)copy); + substitutions = copy.substitutions; + maximumSubstitutions = MAXIMUM_SUBSTITUTION_PROPORTION * Array::size; + return *this; + } + + unsigned getSize() const { + return Array::getSize(); + } + + class Entry { + protected: + SubstitutionArray& owner; + unsigned index; + public: + Entry(const SubstitutionArray&owner, unsigned index) : + owner(const_cast(owner)), + index(index) {} + + operator T() const { + if (owner.substitutions) { + std::map::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(); + } + (*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::referenceCount > 1) { + Array::destroy(); + Array::array = new T[Array::size]; + Array::referenceCount = new unsigned(1); + substitutions = NULL; + } + Array::fill(filler); + } + + void finalizeSubstitutions() { + if (!substitutions) { + return; + } + T*replacement = new T[Array::size]; + for (unsigned i = Array::size; i--;) { + replacement[i] = Array::array[i]; + } + for (typename std::map::const_iterator iterator = + substitutions->begin(), + end = substitutions->end(); + iterator != end; ++iterator) { + replacement[iterator->first] = iterator->second; + } + Array::destroy(); + Array::array = replacement; + Array::referenceCount = new unsigned(1); + substitutions->clear(); + } + + void autoFinalizeSubstitutions(){ + if (substitutions && substitutions->size() > maximumSubstitutions) { + finalizeSubstitutions(); + } + } +}; + +templatestd::ostream&operator << + (std::ostream&out, const SubstitutionArray&array) { + out << '['; + for (unsigned i = 0; i < array.getSize(); ++i) { + out << array[i] << ','; + } + return out << "X]"; +} + +template > + class SubstitutionArrayComparator { +public: + bool operator()(const Array&left,const Array&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 . + + +#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. + +templateclass 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 . + + +#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. + +templateclass 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 . + + +#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. + +templateclass 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 . + + +#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. + +templateclass 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 . + + +#ifndef RELATION_H +#define RELATION_H + +#include +#include +#include +#include + +// 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 data_compare = std::less >class relation { +protected: + typedef relation + + relation_type; + + std::multimap + by_key; + std::multimap + by_data; +public: + typedef unsigned size_type; + typedef int difference_type; + + // By-key iterators: +#define KEY(type) \ + typedef typename std::multimap::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::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©) : + by_key(copy.by_key), + by_data(copy.by_data) {} + relation&operator =(const relation_type©) { + 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(equal_range,); + std::pair KEY(equal_range, const); +#undef KEY + // (Return whether insertion was successful as second.) + std::pairkey_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(by_key.end(), false); + } + by_data.insert(data_hint, std::pair(data, key)); + return std::pair + (by_key.insert + (key_hint, std::pair(key, data)), true); + } + void key_erase(key_iterator pos) { + std::pairdata_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::pairrange = 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(equal_range,); + std::pair DATA(equal_range, const); +#undef DATA + // (Return whether insertion was successful as second.) + std::pairdata_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(by_data.end(), false); + } + by_key.insert(key_hint, std::pair(key, data)); + return std::pair + (by_data.insert + (data_hint, std::pair(data, key)), true); + } + void data_erase(data_iterator pos) { + std::pairkey_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::pairrange = 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(); + } +}; + +templatestd::ostream&operator << + (std::ostream&out, + const relation&rel) { + out << "relation{\n"; + for (typename relation::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 -- cgit v1.2.1