Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
set.hh
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Guido Tack <tack@gecode.org>
5 * Christian Schulte <schulte@gecode.org>
6 *
7 * Copyright:
8 * Guido Tack, 2005
9 * Christian Schulte, 2005
10 *
11 * This file is part of Gecode, the generic constraint
12 * development environment:
13 * http://www.gecode.org
14 *
15 * Permission is hereby granted, free of charge, to any person obtaining
16 * a copy of this software and associated documentation files (the
17 * "Software"), to deal in the Software without restriction, including
18 * without limitation the rights to use, copy, modify, merge, publish,
19 * distribute, sublicense, and/or sell copies of the Software, and to
20 * permit persons to whom the Software is furnished to do so, subject to
21 * the following conditions:
22 *
23 * The above copyright notice and this permission notice shall be
24 * included in all copies or substantial portions of the Software.
25 *
26 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
27 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
28 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
29 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
30 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
31 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
32 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
33 *
34 */
35
36#ifndef __GECODE_TEST_SET_HH__
37#define __GECODE_TEST_SET_HH__
38
39#include <gecode/set.hh>
40#include "test/test.hh"
41#include "test/int.hh"
42
43namespace Test {
44
46 namespace Set {
47
52
58
61 private:
63 int cur;
64 int i;
65 public:
70 : dv(d0), cur(cur0), i(1) {
71 if (! (i & cur))
72 operator++();
73 }
74
75 void init(const Gecode::IntSet& d0, int cur0) {
76 dv = d0;
77 cur = cur0;
78 i = 1;
79 if (! (i & cur))
80 operator++();
81 }
82
83 bool operator()(void) const {
84 return i<=cur;
85 }
86
87 void operator++(void) {
88 do {
89 ++dv;
90 i = i<<1;
91 } while (! (i & cur) && i<cur);
92 }
93
94 int val(void) const { return dv.val(); }
95 };
96
99 : public Gecode::Iter::Values::ToRanges<CountableSetValues> {
100 private:
103 public:
110
111 void init(const Gecode::IntSet& d, int cur) {
112 v.init(d, cur);
114 }
115 };
116
119 private:
123 unsigned int cur;
125 unsigned int lubmax;
126 public:
132 void init(const Gecode::IntSet& s);
134 bool operator()(void) const { return cur<lubmax; }
136 void operator++(void);
138 int val(void) const;
139 };
140
143 private:
145 int n;
147 CountableSet* dsv;
151 bool done;
152 public:
158 SetAssignment(int n, const Gecode::IntSet& d, int i = 0);
160 bool operator()(void) const { return !done; }
162 void operator++(void);
164 int operator[](int i) const {
165 assert((i>=0) && (i<n));
166 return dsv[i].val();
167 }
168
169 int intval(void) const { return ir[0]; }
171 const Test::Int::Assignment& ints(void) const { return ir; }
173 int size(void) const { return n; }
175 ~SetAssignment(void) { delete [] dsv; }
176 };
177
178
179 class SetTest;
180
183 public:
198
208 SetTestSpace(int n, Gecode::IntSet& d0, int i, SetTest* t,
209 bool log=true);
219 SetTestSpace(int n, Gecode::IntSet& d0, int i, SetTest* t,
220 Gecode::ReifyMode rm, bool log=true);
224 virtual Gecode::Space* copy(void);
226 void post(void);
228 bool failed(void);
230 bool subsumed(bool b);
232 void rel(int i, Gecode::SetRelType srt, const Gecode::IntSet& is);
234 void cardinality(int i, int cmin, int cmax);
236 void rel(int i, Gecode::IntRelType irt, int n);
238 void rel(bool sol);
240 void assign(const SetAssignment& a);
242 bool assigned(void) const;
244 void removeFromLub(int v, int i, const SetAssignment& a);
246 void removeFromLub(int v, int i, const SetAssignment& a,
247 SetTestSpace& c);
249 void addToGlb(int v, int i, const SetAssignment& a);
251 void addToGlb(int v, int i, const SetAssignment& a,
252 SetTestSpace& c);
254 bool fixprob(void);
256 bool prune(const SetAssignment& a);
258 unsigned int propagators(void);
260 void disable(void);
262 void enable(void);
264 bool disabled(const SetAssignment& a, SetTestSpace& c);
266 bool same(SetTestSpace& c);
267 };
268
273 class SetTest : public Base {
274 private:
276 int arity;
278 Gecode::IntSet lub;
280 bool reified;
282 int withInt;
283
285 void removeFromLub(int v, Gecode::SetVar& x, int i,
286 const Gecode::IntSet& a);
288 void addToGlb(int v, Gecode::SetVar& x, int i, const Gecode::IntSet& a);
290 SetAssignment* make_assignment(void);
291 protected:
296 public:
304 SetTest(const std::string& s,
305 int a, const Gecode::IntSet& d, bool r=false, int w=0)
306 : Base("Set::"+s), arity(a), lub(d), reified(r), withInt(w),
307 disabled(true), testsubsumed(true) {}
308
309 virtual bool solution(const SetAssignment&) const = 0;
311 virtual void post(Gecode::Space& home, Gecode::SetVarArray& x,
312 Gecode::IntVarArray& y) = 0;
316
317 virtual bool run(void);
318
320
321
322 static std::string str(Gecode::SetRelType srt);
324 static std::string str(Gecode::SetOpType srt);
326 static std::string str(int i);
328 static std::string str(const Gecode::IntArgs& i);
330 };
331
332
335 private:
337 static const Gecode::SetRelType srts[6];
339 int i;
340 public:
342 SetRelTypes(void);
344 bool operator()(void) const;
346 void operator++(void);
348 Gecode::SetRelType srt(void) const;
349 };
350
353 private:
355 static const Gecode::SetOpType sots[4];
357 int i;
358 public:
360 SetOpTypes(void);
362 bool operator()(void) const;
364 void operator++(void);
366 Gecode::SetOpType sot(void) const;
367 };
368
369}}
370
375std::ostream&
376operator<<(std::ostream&, const Test::Set::SetAssignment& a);
377
378#include "test/set.hpp"
379
380#endif
381
382// STATISTICS: test-set
Passing integer arguments.
Definition int.hh:634
Value iterator for integer sets.
Definition int.hh:333
Integer sets.
Definition int.hh:174
Integer variable array.
Definition int.hh:772
Range iterator from value iterator.
void init(I &i)
Initialize with value iterator i.
Reification specification.
Definition int.hh:891
Set variable array
Definition set.hh:573
Set variables
Definition set.hh:127
Computation spaces.
Definition core.hpp:1744
struct Gecode::Space::@055132133326276162005044145100211202071356247106::@155123175027073262103111264343315000271204104107 c
Data available only during copying.
Base(const std::string &s)
Create and register test with name s.
Definition test.cpp:59
Base class for assignments
Definition int.hh:59
Generate all assignments.
Definition int.hh:79
void init(const Gecode::IntSet &d, int cur)
Initialize with set d0 and bit-pattern cur0.
Definition set.hh:111
CountableSetRanges(const Gecode::IntSet &d, int cur)
Initialize with set d0 and bit-pattern cur0.
Definition set.hh:107
CountableSetRanges(void)
Default constructor.
Definition set.hh:105
Value iterator producing subsets of an IntSet.
Definition set.hh:60
int val(void) const
Return current value.
Definition set.hh:94
void init(const Gecode::IntSet &d0, int cur0)
Initialize with set d0 and bit-pattern cur0.
Definition set.hh:75
bool operator()(void) const
Test if finished.
Definition set.hh:83
CountableSetValues(void)
Default constructor.
Definition set.hh:67
void operator++(void)
Move to next value.
Definition set.hh:87
CountableSetValues(const Gecode::IntSet &d0, int cur0)
Initialize with set d0 and bit-pattern cur0.
Definition set.hh:69
Iterate all subsets of a given set.
Definition set.hh:118
int val(void) const
Return current subset.
Definition set.cpp:64
CountableSet(void)
Default constructor.
Definition set.hh:130
CountableSet(const Gecode::IntSet &s)
Initialize with set s.
Definition set.cpp:44
bool operator()(void) const
Check if still subsets left.
Definition set.hh:134
void init(const Gecode::IntSet &s)
Initialize with set s.
Definition set.cpp:55
void operator++(void)
Move to next subset.
Definition set.cpp:51
Generate all set assignments.
Definition set.hh:142
int intval(void) const
Return value for first integer variable.
Definition set.hh:169
const Test::Int::Assignment & ints(void) const
Return assignment for integer variables.
Definition set.hh:171
void operator++(void)
Move to next assignment.
Definition set.cpp:76
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
int size(void) const
Return arity.
Definition set.hh:173
int operator[](int i) const
Return value for variable i.
Definition set.hh:164
int withInt
How many integer variables to iterate.
Definition set.hh:156
bool operator()(void) const
Test whether all assignments have been iterated.
Definition set.hh:160
~SetAssignment(void)
Destructor.
Definition set.hh:175
Gecode::IntSet lub
The common superset for all domains.
Definition set.hh:154
SetOpTypes(void)
Initialize iterator.
Definition set.hpp:100
Gecode::SetOpType sot(void) const
Return current operation type.
Definition set.hpp:111
void operator++(void)
Increment to next operation type.
Definition set.hpp:107
bool operator()(void) const
Test whether iterator is done.
Definition set.hpp:103
SetRelTypes(void)
Initialize iterator.
Definition set.hpp:84
void operator++(void)
Increment to next relation type.
Definition set.hpp:91
Gecode::SetRelType srt(void) const
Return current relation type.
Definition set.hpp:95
bool operator()(void) const
Test whether iterator is done.
Definition set.hpp:87
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
bool subsumed(bool b)
Check for subsumption if b is true.
Definition set.cpp:197
void post(void)
Post propagator.
Definition set.cpp:170
SetTest * test
The test currently run.
Definition set.hh:197
Gecode::SetVarArray x
Set variables to be tested.
Definition set.hh:187
bool assigned(void) const
Test whether all variables are assigned.
Definition set.cpp:274
Gecode::IntSet d
Initial domain.
Definition set.hh:185
void removeFromLub(int v, int i, const SetAssignment &a)
Remove value v from the upper bound of x[i].
Definition set.cpp:285
bool fixprob(void)
Perform fixpoint computation.
Definition set.cpp:341
virtual Gecode::Space * copy(void)
Copy space during cloning.
Definition set.cpp:165
Gecode::Reify r
Reification information.
Definition set.hh:193
SetTestSpace(int n, Gecode::IntSet &d0, int i, SetTest *t, bool log=true)
Create test space without reification.
Definition set.cpp:120
Gecode::IntVarArray y
Int variables to be tested.
Definition set.hh:189
bool failed(void)
Compute a fixpoint and check for failure.
Definition set.cpp:183
void disable(void)
Disable propagators in space and compute fixpoint (make all idle)
Definition set.cpp:695
void rel(int i, Gecode::SetRelType srt, const Gecode::IntSet &is)
Perform set tell operation on x[i].
Definition set.cpp:202
bool reified
Whether the test is for a reified propagator.
Definition set.hh:195
bool prune(const SetAssignment &a)
Perform random pruning.
Definition set.cpp:405
void addToGlb(int v, int i, const SetAssignment &a)
Remove value v from the lower bound of x[i].
Definition set.cpp:313
bool same(SetTestSpace &c)
Check whether propagation is the same as in c.
Definition set.cpp:374
void cardinality(int i, int cmin, int cmax)
Perform cardinality tell operation on x[i].
Definition set.cpp:223
void assign(const SetAssignment &a)
Assign all variables to values in a.
Definition set.cpp:258
void enable(void)
Enable propagators in space.
Definition set.cpp:690
unsigned int propagators(void)
Return the number of propagators.
Definition set.cpp:685
int withInt
How many integer variables are used by the test.
Definition set.hh:191
Base class for tests with set constraints
Definition set.hh:273
virtual void post(Gecode::Space &home, Gecode::SetVarArray &x, Gecode::IntVarArray &y)=0
Post propagator.
static std::string str(Gecode::SetRelType srt)
Map set relation to string.
Definition set.hpp:46
bool testsubsumed
Whether to check for subsumption.
Definition set.hh:295
virtual bool run(void)
Perform test.
Definition set.cpp:718
virtual void post(Gecode::Space &, Gecode::SetVarArray &, Gecode::IntVarArray &, Gecode::Reify)
Post reified propagator.
Definition set.hh:314
bool disabled
Whether to perform full tests for disabled propagators.
Definition set.hh:293
virtual bool solution(const SetAssignment &) const =0
Check for solution.
SetTest(const std::string &s, int a, const Gecode::IntSet &d, bool r=false, int w=0)
Constructor.
Definition set.hh:304
IntRelType
Relation types for integers.
Definition int.hh:940
ReifyMode
Mode for reification.
Definition int.hh:863
SetOpType
Common operations for sets.
Definition set.hh:666
SetRelType
Common relation types for sets.
Definition set.hh:649
Testing finite sets.
Definition set.cpp:42
General test support.
Definition afc.cpp:39
Region r
Definition region.cpp:65
std::basic_ostream< Char, Traits > & operator<<(std::basic_ostream< Char, Traits > &os, const Dictionary &d)
Print statistics summary.
Definition scowl.hpp:13625