sequence.cpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Guido Tack <tack@gecode.org>
*
* Copyright:
* Guido Tack, 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.
*
*/
#include "test/set.hh"
using namespace Gecode;
namespace Test { namespace Set {
namespace Sequence {
static IntSet ds_33(-1,2);
class Sequence : public SetTest {
public:
Sequence(const char* t)
: SetTest(t,4,ds_33,false) {}
virtual bool solution(const SetAssignment& x) const {
int max = Gecode::Set::Limits::min - 1;
for (int i=0; i<4; i++) {
CountableSetRanges xir(x.lub, x[i]);
IntSet xi(xir);
if (xi.ranges() > 0) {
int oldMax = max;
max = xi.max();
if (xi.min() <= oldMax)
return false;
}
}
return true;
}
virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
Gecode::sequence(home, x);
}
};
Sequence _sequence("Sequence::Sequence");
class SeqU : public SetTest {
private:
int n;
public:
SeqU(int n0)
: SetTest("Sequence::SeqU"+str(n0),n0+1,ds_33,false), n(n0) {}
virtual bool solution(const SetAssignment& x) const {
int max = Gecode::Set::Limits::min - 1;
for (int i=0; i<n; i++) {
CountableSetRanges xir(x.lub, x[i]);
IntSet xi(xir);
if (xi.ranges() > 0) {
int oldMax = max;
max = xi.max();
if (xi.min() <= oldMax)
return false;
}
}
CountableSetRanges* isrs = new CountableSetRanges[n];
for (int i=n; i--; )
isrs[i].init(x.lub, x[i]);
bool ret;
{
Region r;
Iter::Ranges::NaryUnion u(r, isrs, n);
CountableSetRanges xnr(x.lub, x[n]);
ret = Iter::Ranges::equal(u, xnr);
}
delete[] isrs;
return ret;
}
virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
SetVarArgs xs(x.size()-1);
for (int i=x.size()-1; i--;)
xs[i]=x[i];
Gecode::sequence(home, xs, x[x.size()-1]);
}
};
SeqU _sequ0(0);
SeqU _sequ1(1);
SeqU _sequ3(3);
}}}
// STATISTICS: test-set
Gecode::IntSet
Integer sets.
Definition int.hh:174
Gecode::IntSet::min
int min(int i) const
Return minimum of range at position i.
Definition int-set-1.hpp:152
Gecode::IntSet::max
int max(int i) const
Return maximum of range at position i.
Definition int-set-1.hpp:158
Gecode::IntSet::ranges
int ranges(void) const
Return number of ranges of the specification.
Definition int-set-1.hpp:171
Gecode::IntVarArray
Integer variable array.
Definition int.hh:763
Gecode::Iter::Ranges::NaryUnion
Range iterator for union of iterators.
Definition ranges-union.hpp:74
Gecode::SetVarArgs
Passing set variables.
Definition set.hh:488
Gecode::SetVarArray
Set variable array
Definition set.hh:570
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Gecode::VarArray::size
int size(void) const
Return size of array (number of elements).
Definition array.hpp:926
Test::Region
Test for Region memory area
Definition region.cpp:42
Test::Set::CountableSetRanges
Range iterator producing subsets of an IntSet.
Definition set.hh:99
Test::Set::Sequence::SeqU
Test for sequential-union constraint
Definition sequence.cpp:80
Test::Set::Sequence::SeqU::solution
virtual bool solution(const SetAssignment &x) const
Test whether x is solution
Definition sequence.cpp:88
Test::Set::Sequence::SeqU::SeqU
SeqU(int n0)
Create and register test.
Definition sequence.cpp:85
Test::Set::Sequence::SeqU::post
virtual void post(Space &home, SetVarArray &x, IntVarArray &)
Post constraint on x.
Definition sequence.cpp:114
Test::Set::Sequence::Sequence
Test for sequence constraint
Definition sequence.cpp:52
Test::Set::Sequence::Sequence::solution
virtual bool solution(const SetAssignment &x) const
Test whether x is solution
Definition sequence.cpp:58
Test::Set::Sequence::Sequence::Sequence
Sequence(const char *t)
Create and register test.
Definition sequence.cpp:55
Test::Set::Sequence::Sequence::post
virtual void post(Space &home, SetVarArray &x, IntVarArray &)
Post constraint on x.
Definition sequence.cpp:73
Test::Set::SetAssignment
Generate all set assignments.
Definition set.hh:142
Test::Set::SetAssignment::lub
Gecode::IntSet lub
The common superset for all domains.
Definition set.hh:154
Test::Set::SetTest::str
static std::string str(Gecode::SetRelType srt)
Map set relation to string.
Definition set.hpp:46
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
Gecode::Iter::Ranges::equal
bool equal(I &i, J &j)
Check whether range iterators i and j are equal.
Definition ranges-operations.hpp:84
Gecode::Set::Limits::min
const int min
Smallest allowed integer in integer set.
Definition set.hh:99
Gecode
Gecode toplevel namespace
Gecode::sequence
void sequence(Home home, const IntVarArgs &x, const IntSet &s, int q, int l, int u, IntPropLevel ipl=IPL_DEF)
Post propagator for .
Definition sequence.cpp:47
Gecode::max
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition arithmetic.cpp:49
Test::Set::Sequence::_sequ3
SeqU _sequ3(3)
Test::Set::Sequence::_sequ1
SeqU _sequ1(1)
Test::Set::Sequence::_sequ0
SeqU _sequ0(0)
Test::Set::Sequence::_sequence
Sequence _sequence("Sequence::Sequence")
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
set.hh