set.hh
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Guido Tack <tack@gecode.org>
* Christian Schulte <schulte@gecode.org>
*
* Copyright:
* Guido Tack, 2005
* Christian Schulte, 2005
*
* This file is part of Gecode, the generic constraint
* development environment:
* http://www.gecode.org
*
* Permission is hereby granted, free of charge, to any person obtaining
* a copy of this software and associated documentation files (the
* "Software"), to deal in the Software without restriction, including
* without limitation the rights to use, copy, modify, merge, publish,
* distribute, sublicense, and/or sell copies of the Software, and to
* permit persons to whom the Software is furnished to do so, subject to
* the following conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*
*/
#ifndef __GECODE_TEST_SET_HH__
#define __GECODE_TEST_SET_HH__
#include <gecode/set.hh>
#include "test/test.hh"
#include "test/int.hh"
namespace Test {
namespace Set {
class CountableSetValues {
private:
Gecode::IntSetValues dv;
int cur;
int i;
public:
CountableSetValues(void) {}
CountableSetValues(const Gecode::IntSet& d0, int cur0)
: dv(d0), cur(cur0), i(1) {
if (! (i & cur))
operator++();
}
void init(const Gecode::IntSet& d0, int cur0) {
dv = d0;
cur = cur0;
i = 1;
if (! (i & cur))
operator++();
}
bool operator()(void) const {
return i<=cur;
}
void operator++(void) {
do {
++dv;
i = i<<1;
} while (! (i & cur) && i<cur);
}
int val(void) const { return dv.val(); }
};
class CountableSetRanges
: public Gecode::Iter::Values::ToRanges<CountableSetValues> {
private:
CountableSetValues v;
public:
CountableSetRanges(void) {}
CountableSetRanges(const Gecode::IntSet& d, int cur) : v(d, cur) {
Gecode::Iter::Values::ToRanges<CountableSetValues>::init(v);
}
void init(const Gecode::IntSet& d, int cur) {
v.init(d, cur);
Gecode::Iter::Values::ToRanges<CountableSetValues>::init(v);
}
};
class CountableSet {
private:
Gecode::IntSet d;
unsigned int cur;
unsigned int lubmax;
public:
CountableSet(const Gecode::IntSet& s);
CountableSet(void) {}
void init(const Gecode::IntSet& s);
bool operator()(void) const { return cur<lubmax; }
void operator++(void);
int val(void) const;
};
class SetAssignment {
private:
int n;
CountableSet* dsv;
Test::Int::CpltAssignment ir;
bool done;
public:
Gecode::IntSet lub;
int withInt;
SetAssignment(int n, const Gecode::IntSet& d, int i = 0);
bool operator()(void) const { return !done; }
void operator++(void);
int operator[](int i) const {
assert((i>=0) && (i<n));
return dsv[i].val();
}
int intval(void) const { return ir[0]; }
const Test::Int::Assignment& ints(void) const { return ir; }
int size(void) const { return n; }
~SetAssignment(void) { delete [] dsv; }
};
class SetTest;
class SetTestSpace : public Gecode::Space {
public:
Gecode::IntSet d;
Gecode::SetVarArray x;
Gecode::IntVarArray y;
int withInt;
Gecode::Reify r;
bool reified;
SetTest* test;
SetTestSpace(int n, Gecode::IntSet& d0, int i, SetTest* t,
bool log=true);
SetTestSpace(int n, Gecode::IntSet& d0, int i, SetTest* t,
Gecode::ReifyMode rm, bool log=true);
SetTestSpace(SetTestSpace& s);
virtual Gecode::Space* copy(void);
void post(void);
bool failed(void);
bool subsumed(bool b);
void rel(int i, Gecode::SetRelType srt, const Gecode::IntSet& is);
void cardinality(int i, int cmin, int cmax);
void rel(int i, Gecode::IntRelType irt, int n);
void rel(bool sol);
void assign(const SetAssignment& a);
bool assigned(void) const;
void removeFromLub(int v, int i, const SetAssignment& a);
void removeFromLub(int v, int i, const SetAssignment& a,
SetTestSpace& c);
void addToGlb(int v, int i, const SetAssignment& a);
void addToGlb(int v, int i, const SetAssignment& a,
SetTestSpace& c);
bool fixprob(void);
bool prune(const SetAssignment& a);
unsigned int propagators(void);
void disable(void);
void enable(void);
bool disabled(const SetAssignment& a, SetTestSpace& c);
bool same(SetTestSpace& c);
};
class SetTest : public Base {
private:
int arity;
Gecode::IntSet lub;
bool reified;
int withInt;
void removeFromLub(int v, Gecode::SetVar& x, int i,
const Gecode::IntSet& a);
void addToGlb(int v, Gecode::SetVar& x, int i, const Gecode::IntSet& a);
SetAssignment* make_assignment(void);
protected:
bool disabled;
bool testsubsumed;
public:
SetTest(const std::string& s,
int a, const Gecode::IntSet& d, bool r=false, int w=0)
: Base("Set::"+s), arity(a), lub(d), reified(r), withInt(w),
disabled(true), testsubsumed(true) {}
virtual bool solution(const SetAssignment&) const = 0;
virtual void post(Gecode::Space& home, Gecode::SetVarArray& x,
Gecode::IntVarArray& y) = 0;
virtual void post(Gecode::Space&, Gecode::SetVarArray&,
Gecode::IntVarArray&, Gecode::Reify) {}
virtual bool run(void);
static std::string str(Gecode::SetRelType srt);
static std::string str(Gecode::SetOpType srt);
static std::string str(int i);
static std::string str(const Gecode::IntArgs& i);
};
class SetRelTypes {
private:
static const Gecode::SetRelType srts[6];
int i;
public:
SetRelTypes(void);
bool operator()(void) const;
void operator++(void);
Gecode::SetRelType srt(void) const;
};
class SetOpTypes {
private:
static const Gecode::SetOpType sots[4];
int i;
public:
SetOpTypes(void);
bool operator()(void) const;
void operator++(void);
Gecode::SetOpType sot(void) const;
};
}}
std::ostream&
operator<<(std::ostream&, const Test::Set::SetAssignment& a);
#include "test/set.hpp"
#endif
// STATISTICS: test-set
Gecode::IntArgs
Passing integer arguments.
Definition int.hh:628
Gecode::IntSetValues
Value iterator for integer sets.
Definition int.hh:333
Gecode::IntSet
Integer sets.
Definition int.hh:174
Gecode::IntVarArray
Integer variable array.
Definition int.hh:763
Gecode::Iter::Values::ToRanges
Range iterator from value iterator.
Definition values-ranges.hpp:46
Gecode::Iter::Values::ToRanges::init
void init(I &i)
Initialize with value iterator i.
Definition values-ranges.hpp:94
Gecode::Reify
Reification specification.
Definition int.hh:876
Gecode::SetVarArray
Set variable array
Definition set.hh:570
Gecode::SetVar
Set variables
Definition set.hh:127
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Gecode::Space::c
struct Gecode::Space::@055132133326276162005044145100211202071356247106::@155123175027073262103111264343315000271204104107 c
Data available only during copying.
Test::Base::Base
Base(const std::string &s)
Create and register test with name s.
Definition test.cpp:59
Test::Int::Assignment
Base class for assignments
Definition int.hh:59
Test::Int::CpltAssignment
Generate all assignments.
Definition int.hh:79
Test::Set::CountableSetRanges::init
void init(const Gecode::IntSet &d, int cur)
Initialize with set d0 and bit-pattern cur0.
Definition set.hh:111
Test::Set::CountableSetRanges::CountableSetRanges
CountableSetRanges(const Gecode::IntSet &d, int cur)
Initialize with set d0 and bit-pattern cur0.
Definition set.hh:107
Test::Set::CountableSetRanges::CountableSetRanges
CountableSetRanges(void)
Default constructor.
Definition set.hh:105
Test::Set::CountableSetValues
Value iterator producing subsets of an IntSet.
Definition set.hh:60
Test::Set::CountableSetValues::val
int val(void) const
Return current value.
Definition set.hh:94
Test::Set::CountableSetValues::init
void init(const Gecode::IntSet &d0, int cur0)
Initialize with set d0 and bit-pattern cur0.
Definition set.hh:75
Test::Set::CountableSetValues::operator()
bool operator()(void) const
Test if finished.
Definition set.hh:83
Test::Set::CountableSetValues::CountableSetValues
CountableSetValues(void)
Default constructor.
Definition set.hh:67
Test::Set::CountableSetValues::operator++
void operator++(void)
Move to next value.
Definition set.hh:87
Test::Set::CountableSetValues::CountableSetValues
CountableSetValues(const Gecode::IntSet &d0, int cur0)
Initialize with set d0 and bit-pattern cur0.
Definition set.hh:69
Test::Set::CountableSet
Iterate all subsets of a given set.
Definition set.hh:118
Test::Set::CountableSet::val
int val(void) const
Return current subset.
Definition set.cpp:64
Test::Set::CountableSet::CountableSet
CountableSet(void)
Default constructor.
Definition set.hh:130
Test::Set::CountableSet::CountableSet
CountableSet(const Gecode::IntSet &s)
Initialize with set s.
Definition set.cpp:44
Test::Set::CountableSet::operator()
bool operator()(void) const
Check if still subsets left.
Definition set.hh:134
Test::Set::CountableSet::init
void init(const Gecode::IntSet &s)
Initialize with set s.
Definition set.cpp:55
Test::Set::CountableSet::operator++
void operator++(void)
Move to next subset.
Definition set.cpp:51
Test::Set::SetAssignment
Generate all set assignments.
Definition set.hh:142
Test::Set::SetAssignment::intval
int intval(void) const
Return value for first integer variable.
Definition set.hh:169
Test::Set::SetAssignment::ints
const Test::Int::Assignment & ints(void) const
Return assignment for integer variables.
Definition set.hh:171
Test::Set::SetAssignment::operator++
void operator++(void)
Move to next assignment.
Definition set.cpp:76
Test::Set::SetAssignment::SetAssignment
SetAssignment(int n, const Gecode::IntSet &d, int i=0)
Initialize with n set variables, initial bound d and i int variables.
Definition set.cpp:68
Test::Set::SetAssignment::size
int size(void) const
Return arity.
Definition set.hh:173
Test::Set::SetAssignment::operator[]
int operator[](int i) const
Return value for variable i.
Definition set.hh:164
Test::Set::SetAssignment::withInt
int withInt
How many integer variables to iterate.
Definition set.hh:156
Test::Set::SetAssignment::operator()
bool operator()(void) const
Test whether all assignments have been iterated.
Definition set.hh:160
Test::Set::SetAssignment::~SetAssignment
~SetAssignment(void)
Destructor.
Definition set.hh:175
Test::Set::SetAssignment::lub
Gecode::IntSet lub
The common superset for all domains.
Definition set.hh:154
Test::Set::SetOpTypes::SetOpTypes
SetOpTypes(void)
Initialize iterator.
Definition set.hpp:100
Test::Set::SetOpTypes::sot
Gecode::SetOpType sot(void) const
Return current operation type.
Definition set.hpp:111
Test::Set::SetOpTypes::operator++
void operator++(void)
Increment to next operation type.
Definition set.hpp:107
Test::Set::SetOpTypes::operator()
bool operator()(void) const
Test whether iterator is done.
Definition set.hpp:103
Test::Set::SetRelTypes::SetRelTypes
SetRelTypes(void)
Initialize iterator.
Definition set.hpp:84
Test::Set::SetRelTypes::operator++
void operator++(void)
Increment to next relation type.
Definition set.hpp:91
Test::Set::SetRelTypes::srt
Gecode::SetRelType srt(void) const
Return current relation type.
Definition set.hpp:95
Test::Set::SetRelTypes::operator()
bool operator()(void) const
Test whether iterator is done.
Definition set.hpp:87
Test::Set::SetTestSpace::disabled
bool disabled(const SetAssignment &a, SetTestSpace &c)
Prune values also in a space c with disabled propagators, but not those in assignment a.
Definition set.cpp:541
Test::Set::SetTestSpace::subsumed
bool subsumed(bool b)
Check for subsumption if b is true.
Definition set.cpp:197
Test::Set::SetTestSpace::post
void post(void)
Post propagator.
Definition set.cpp:170
Test::Set::SetTestSpace::test
SetTest * test
The test currently run.
Definition set.hh:197
Test::Set::SetTestSpace::x
Gecode::SetVarArray x
Set variables to be tested.
Definition set.hh:187
Test::Set::SetTestSpace::assigned
bool assigned(void) const
Test whether all variables are assigned.
Definition set.cpp:274
Test::Set::SetTestSpace::d
Gecode::IntSet d
Initial domain.
Definition set.hh:185
Test::Set::SetTestSpace::removeFromLub
void removeFromLub(int v, int i, const SetAssignment &a)
Remove value v from the upper bound of x[i].
Definition set.cpp:285
Test::Set::SetTestSpace::fixprob
bool fixprob(void)
Perform fixpoint computation.
Definition set.cpp:341
Test::Set::SetTestSpace::copy
virtual Gecode::Space * copy(void)
Copy space during cloning.
Definition set.cpp:165
Test::Set::SetTestSpace::r
Gecode::Reify r
Reification information.
Definition set.hh:193
Test::Set::SetTestSpace::SetTestSpace
SetTestSpace(int n, Gecode::IntSet &d0, int i, SetTest *t, bool log=true)
Create test space without reification.
Definition set.cpp:120
Test::Set::SetTestSpace::y
Gecode::IntVarArray y
Int variables to be tested.
Definition set.hh:189
Test::Set::SetTestSpace::failed
bool failed(void)
Compute a fixpoint and check for failure.
Definition set.cpp:183
Test::Set::SetTestSpace::disable
void disable(void)
Disable propagators in space and compute fixpoint (make all idle).
Definition set.cpp:695
Test::Set::SetTestSpace::rel
void rel(int i, Gecode::SetRelType srt, const Gecode::IntSet &is)
Perform set tell operation on x[i].
Definition set.cpp:202
Test::Set::SetTestSpace::reified
bool reified
Whether the test is for a reified propagator.
Definition set.hh:195
Test::Set::SetTestSpace::prune
bool prune(const SetAssignment &a)
Perform random pruning.
Definition set.cpp:405
Test::Set::SetTestSpace::addToGlb
void addToGlb(int v, int i, const SetAssignment &a)
Remove value v from the lower bound of x[i].
Definition set.cpp:313
Test::Set::SetTestSpace::same
bool same(SetTestSpace &c)
Check whether propagation is the same as in c.
Definition set.cpp:374
Test::Set::SetTestSpace::cardinality
void cardinality(int i, int cmin, int cmax)
Perform cardinality tell operation on x[i].
Definition set.cpp:223
Test::Set::SetTestSpace::assign
void assign(const SetAssignment &a)
Assign all variables to values in a.
Definition set.cpp:258
Test::Set::SetTestSpace::enable
void enable(void)
Enable propagators in space.
Definition set.cpp:690
Test::Set::SetTestSpace::propagators
unsigned int propagators(void)
Return the number of propagators.
Definition set.cpp:685
Test::Set::SetTestSpace::withInt
int withInt
How many integer variables are used by the test.
Definition set.hh:191
Test::Set::SetTest
Base class for tests with set constraints
Definition set.hh:273
Test::Set::SetTest::post
virtual void post(Gecode::Space &home, Gecode::SetVarArray &x, Gecode::IntVarArray &y)=0
Post propagator.
Test::Set::SetTest::str
static std::string str(Gecode::SetRelType srt)
Map set relation to string.
Definition set.hpp:46
Test::Set::SetTest::testsubsumed
bool testsubsumed
Whether to check for subsumption.
Definition set.hh:295
Test::Set::SetTest::run
virtual bool run(void)
Perform test.
Definition set.cpp:718
Test::Set::SetTest::post
virtual void post(Gecode::Space &, Gecode::SetVarArray &, Gecode::IntVarArray &, Gecode::Reify)
Post reified propagator.
Definition set.hh:314
Test::Set::SetTest::disabled
bool disabled
Whether to perform full tests for disabled propagators.
Definition set.hh:293
Test::Set::SetTest::solution
virtual bool solution(const SetAssignment &) const =0
Check for solution.
Test::Set::SetTest::SetTest
SetTest(const std::string &s, int a, const Gecode::IntSet &d, bool r=false, int w=0)
Constructor.
Definition set.hh:304
set.hh
Gecode::IntRelType
IntRelType
Relation types for integers.
Definition int.hh:925
Gecode::ReifyMode
ReifyMode
Mode for reification.
Definition int.hh:848
Gecode::SetOpType
SetOpType
Common operations for sets.
Definition set.hh:660
Gecode::SetRelType
SetRelType
Common relation types for sets.
Definition set.hh:643
Test::Set
Testing finite sets.
Definition set.cpp:42
Test
General test support.
Definition afc.cpp:39
Test::r
Region r
Definition region.cpp:65
operator<<
std::basic_ostream< Char, Traits > & operator<<(std::basic_ostream< Char, Traits > &os, const Dictionary &d)
Print statistics summary.
Definition scowl.hpp:13625
int.hh
set.hpp
test.hh