Generated on Thu Jan 20 2022 00:00:00 for Gecode by doxygen 1.9.1
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 
43 namespace Test {
44 
46  namespace Set {
47 
58 
61  private:
63  int cur;
64  int i;
65  public:
69  CountableSetValues(const Gecode::IntSet& d0, int cur0)
70  : dv(d0), cur(cur0), i(1) {
71  if (! (i & cur))
72  operator++();
73  }
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  }
83  bool operator()(void) const {
84  return i<=cur;
85  }
87  void operator++(void) {
88  do {
89  ++dv;
90  i = i<<1;
91  } while (! (i & cur) && i<cur);
92  }
94  int val(void) const { return dv.val(); }
95  };
96 
99  : public Gecode::Iter::Values::ToRanges<CountableSetValues> {
100  private:
103  public:
107  CountableSetRanges(const Gecode::IntSet& d, int cur) : v(d, cur) {
109  }
111  void init(const Gecode::IntSet& d, int cur) {
112  v.init(d, cur);
114  }
115  };
116 
118  class CountableSet {
119  private:
121  Gecode::IntSet d;
123  unsigned int cur;
125  unsigned int lubmax;
126  public:
128  CountableSet(const Gecode::IntSet& s);
130  CountableSet(void) {}
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:
156  int withInt;
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  }
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 
182  class SetTestSpace : public Gecode::Space {
183  public:
191  int withInt;
195  bool reified;
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:
293  bool disabled;
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) {}
309  virtual bool solution(const SetAssignment&) const = 0;
311  virtual void post(Gecode::Space& home, Gecode::SetVarArray& x,
312  Gecode::IntVarArray& y) = 0;
317  virtual bool run(void);
318 
320 
321  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  };
332 
334  class SetRelTypes {
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 
352  class SetOpTypes {
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 
375 std::ostream&
376 operator<<(std::ostream&, const Test::Set::SetAssignment& a);
377 
378 #include "test/set.hpp"
379 
380 #endif
381 
382 // STATISTICS: test-set
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
NodeType t
Type of node.
Definition: bool-expr.cpp:230
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:249
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
std::basic_ostream< Char, Traits > & operator<<(std::basic_ostream< Char, Traits > &os, const FloatView &x)
Print float variable view.
Passing integer arguments.
Definition: int.hh:628
Value iterator for integer sets.
Definition: int.hh:333
Integer sets.
Definition: int.hh:174
Integer variable array.
Definition: int.hh:763
int val(void) const
Return current value.
Range iterator from value iterator.
void init(I &i)
Initialize with value iterator i.
Reification specification.
Definition: int.hh:876
Set variable array
Definition: set.hh:570
Set variables
Definition: set.hh:127
Computation spaces.
Definition: core.hpp:1742
struct Gecode::Space::@61::@63 c
Data available only during copying.
Base class for all tests to be run
Definition: test.hh:103
Base class for assignments
Definition: int.hh:59
Generate all assignments.
Definition: int.hh:79
Range iterator producing subsets of an IntSet.
Definition: set.hh:99
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
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
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
const Test::Int::Assignment & ints(void) const
Return assignment for integer variables.
Definition: set.hh:171
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
Iterator for Boolean operation types.
Definition: set.hh:352
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
Iterator for set relation types.
Definition: set.hh:334
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
Space for executing set tests.
Definition: set.hh:182
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:925
ReifyMode
Mode for reification.
Definition: int.hh:848
SetOpType
Common operations for sets.
Definition: set.hh:660
SetRelType
Common relation types for sets.
Definition: set.hh:643
Gecode::IntArgs i({1, 2, 3, 4})
Gecode::IntSet d(v, 7)
const int v[7]
Definition: distinct.cpp:259
General test support.
Definition: afc.cpp:39
Region r
Definition: region.cpp:65