Generated on Fri Jul 13 2018 06:08:31 for Gecode by doxygen 1.8.14
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  * Last modified:
12  * $Date: 2017-03-10 10:15:56 +0100 (Fri, 10 Mar 2017) $ by $Author: schulte $
13  * $Revision: 15566 $
14  *
15  * This file is part of Gecode, the generic constraint
16  * development environment:
17  * http://www.gecode.org
18  *
19  * Permission is hereby granted, free of charge, to any person obtaining
20  * a copy of this software and associated documentation files (the
21  * "Software"), to deal in the Software without restriction, including
22  * without limitation the rights to use, copy, modify, merge, publish,
23  * distribute, sublicense, and/or sell copies of the Software, and to
24  * permit persons to whom the Software is furnished to do so, subject to
25  * the following conditions:
26  *
27  * The above copyright notice and this permission notice shall be
28  * included in all copies or substantial portions of the Software.
29  *
30  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37  *
38  */
39 
40 #ifndef __GECODE_TEST_SET_HH__
41 #define __GECODE_TEST_SET_HH__
42 
43 #include <gecode/set.hh>
44 #include "test/test.hh"
45 #include "test/int.hh"
46 
47 namespace Test {
48 
50  namespace Set {
51 
57  class FakeSpace : public Gecode::Space {
59  public:
61  FakeSpace(void) {}
63  virtual Gecode::Space* copy(bool share) {
64  (void) share;
65  return NULL;
66  }
67  };
68 
74 
77  private:
79  int cur;
80  int i;
81  public:
85  CountableSetValues(const Gecode::IntSet& d0, int cur0)
86  : dv(d0), cur(cur0), i(1) {
87  if (! (i & cur))
88  operator++();
89  }
91  void init(const Gecode::IntSet& d0, int cur0) {
92  dv = d0;
93  cur = cur0;
94  i = 1;
95  if (! (i & cur))
96  operator++();
97  }
99  bool operator()(void) const {
100  return i<=cur;
101  }
103  void operator++(void) {
104  do {
105  ++dv;
106  i = i<<1;
107  } while (! (i & cur) && i<cur);
108  }
110  int val(void) const { return dv.val(); }
111  };
112 
115  : public Gecode::Iter::Values::ToRanges<CountableSetValues> {
116  private:
119  public:
123  CountableSetRanges(const Gecode::IntSet& d, int cur) : v(d, cur) {
125  }
127  void init(const Gecode::IntSet& d, int cur) {
128  v.init(d, cur);
130  }
131  };
132 
134  class CountableSet {
135  private:
137  Gecode::IntSet d;
139  unsigned int cur;
141  unsigned int lubmax;
142  public:
144  CountableSet(const Gecode::IntSet& s);
146  CountableSet(void) {}
148  void init(const Gecode::IntSet& s);
150  bool operator()(void) const { return cur<lubmax; }
152  void operator++(void);
154  int val(void) const;
155  };
156 
159  private:
161  int n;
163  CountableSet* dsv;
167  bool done;
168  public:
172  int withInt;
174  SetAssignment(int n, const Gecode::IntSet& d, int i = 0);
176  bool operator()(void) const { return !done; }
178  void operator++(void);
180  int operator[](int i) const {
181  assert((i>=0) && (i<n));
182  return dsv[i].val();
183  }
185  int intval(void) const { return ir[0]; }
187  const Test::Int::Assignment& ints(void) const { return ir; }
189  int size(void) const { return n; }
191  ~SetAssignment(void) { delete [] dsv; }
192  };
193 
194 
195  class SetTest;
196 
198  class SetTestSpace : public Gecode::Space {
199  public:
207  int withInt;
211  bool reified;
214 
224  SetTestSpace(int n, Gecode::IntSet& d0, int i, SetTest* t,
225  bool log=true);
235  SetTestSpace(int n, Gecode::IntSet& d0, int i, SetTest* t,
236  Gecode::ReifyMode rm, bool log=true);
238  SetTestSpace(bool share, SetTestSpace& s);
240  virtual Gecode::Space* copy(bool share);
242  void post(void);
244  bool failed(void);
246  bool subsumed(bool b);
248  void rel(int i, Gecode::SetRelType srt, const Gecode::IntSet& is);
250  void cardinality(int i, int cmin, int cmax);
252  void rel(int i, Gecode::IntRelType irt, int n);
254  void rel(bool sol);
256  void assign(const SetAssignment& a);
258  bool assigned(void) const;
260  void removeFromLub(int v, int i, const SetAssignment& a);
262  void removeFromLub(int v, int i, const SetAssignment& a,
263  SetTestSpace& c);
265  void addToGlb(int v, int i, const SetAssignment& a);
267  void addToGlb(int v, int i, const SetAssignment& a,
268  SetTestSpace& c);
270  bool fixprob(void);
272  bool prune(const SetAssignment& a);
274  unsigned int propagators(void);
276  void disable(void);
278  void enable(void);
280  bool disabled(const SetAssignment& a, SetTestSpace& c);
282  bool same(SetTestSpace& c);
283  };
284 
289  class SetTest : public Base {
290  private:
292  int arity;
294  Gecode::IntSet lub;
296  bool reified;
298  int withInt;
299 
301  void removeFromLub(int v, Gecode::SetVar& x, int i,
302  const Gecode::IntSet& a);
304  void addToGlb(int v, Gecode::SetVar& x, int i, const Gecode::IntSet& a);
306  SetAssignment* make_assignment(void);
307  protected:
309  bool disabled;
312  public:
320  SetTest(const std::string& s,
321  int a, const Gecode::IntSet& d, bool r=false, int w=0)
322  : Base("Set::"+s), arity(a), lub(d), reified(r), withInt(w),
323  disabled(true), testsubsumed(true) {}
325  virtual bool solution(const SetAssignment&) const = 0;
327  virtual void post(Gecode::Space& home, Gecode::SetVarArray& x,
328  Gecode::IntVarArray& y) = 0;
333  virtual bool run(void);
334 
336 
337  static std::string str(Gecode::SetRelType srt);
340  static std::string str(Gecode::SetOpType srt);
342  static std::string str(int i);
344  static std::string str(const Gecode::IntArgs& i);
346  };
348 
350  class SetRelTypes {
351  private:
353  static const Gecode::SetRelType srts[6];
355  int i;
356  public:
358  SetRelTypes(void);
360  bool operator()(void) const;
362  void operator++(void);
364  Gecode::SetRelType srt(void) const;
365  };
366 
368  class SetOpTypes {
369  private:
371  static const Gecode::SetOpType sots[4];
373  int i;
374  public:
376  SetOpTypes(void);
378  bool operator()(void) const;
380  void operator++(void);
382  Gecode::SetOpType sot(void) const;
383  };
384 
385 }}
386 
391 std::ostream&
392 operator<<(std::ostream&, const Test::Set::SetAssignment& a);
393 
394 #include "test/set.hpp"
395 
396 #endif
397 
398 // STATISTICS: test-set
void removeFromLub(int v, int i, const SetAssignment &a)
Remove value v from the upper bound of x[i].
Definition: set.cpp:289
virtual void post(Gecode::Space &, Gecode::SetVarArray &, Gecode::IntVarArray &, Gecode::Reify)
Post reified propagator.
Definition: set.hh:330
void operator++(void)
Move to next subset.
Definition: set.cpp:55
void cardinality(int i, int cmin, int cmax)
Perform cardinality tell operation on x[i].
Definition: set.cpp:227
Iterator for Boolean operation types.
Definition: set.hh:368
NodeType t
Type of node.
Definition: bool-expr.cpp:234
bool disabled
Whether to perform full tests for disabled propagators.
Definition: set.hh:309
CountableSetRanges(const Gecode::IntSet &d, int cur)
Initialize with set d0 and bit-pattern cur0.
Definition: set.hh:123
void disable(void)
Disable propagators in space and compute fixpoint (make all idle)
Definition: set.cpp:699
SetRelType
Common relation types for sets.
Definition: set.hh:645
Iterator for set relation types.
Definition: set.hh:350
bool testsubsumed
Whether to check for subsumption.
Definition: set.hh:311
void operator++(void)
Move to next value.
Definition: set.hh:103
Gecode::Reify r
Reification information.
Definition: set.hh:209
void log(Home home, FloatVar x0, FloatVar x1)
Post propagator for .
Gecode::SetVarArray x
Set variables to be tested.
Definition: set.hh:203
void enable(void)
Enable propagators in space.
Definition: set.cpp:694
void assign(const SetAssignment &a)
Assign all variables to values in a.
Definition: set.cpp:262
static std::string str(Gecode::SetRelType srt)
Map set relation to string.
Definition: set.hpp:50
CountableSet(void)
Default constructor.
Definition: set.hh:146
bool same(SetTestSpace &c)
Check whether propagation is the same as in c.
Definition: set.cpp:378
int val(void) const
Return current subset.
Definition: set.cpp:68
Integer variable array.
Definition: int.hh:744
bool operator()(void) const
Test if finished.
Definition: set.hh:99
SetOpType
Common operations for sets.
Definition: set.hh:662
CountableSetRanges(void)
Default constructor.
Definition: set.hh:121
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:72
Computation spaces.
Definition: core.hpp:1748
SetTest(const std::string &s, int a, const Gecode::IntSet &d, bool r=false, int w=0)
Constructor.
Definition: set.hh:320
int val(void) const
Return current value.
void init(const Gecode::IntSet &d, int cur)
Initialize with set d0 and bit-pattern cur0.
Definition: set.hh:127
SetRelTypes(void)
Initialize iterator.
Definition: set.hpp:88
Gecode::IntSet d(v, 7)
bool reified
Whether the test is for a reified propagator.
Definition: set.hh:211
bool operator()(void) const
Test whether iterator is done.
Definition: set.hpp:91
struct Gecode::@579::NNF::@61::@63 a
For atomic nodes.
void rel(int i, Gecode::SetRelType srt, const Gecode::IntSet &is)
Perform set tell operation on x[i].
Definition: set.cpp:206
Gecode::IntArgs i(4, 1, 2, 3, 4)
SetOpTypes(void)
Initialize iterator.
Definition: set.hpp:104
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
IntRelType
Relation types for integers.
Definition: int.hh:906
void init(I &i)
Initialize with value iterator i.
void operator++(void)
Increment to next operation type.
Definition: set.hpp:111
void post(void)
Post propagator.
Definition: set.cpp:174
bool failed(void)
Compute a fixpoint and check for failure.
Definition: set.cpp:187
Range iterator from value iterator.
Reification specification.
Definition: int.hh:857
struct Gecode::@579::NNF::@61::@62 b
For binary nodes (and, or, eqv)
Base class for all tests to be run
Definition: test.hh:107
virtual bool run(void)
Perform test.
Definition: set.cpp:722
Gecode::IntSet lub
The common superset for all domains.
Definition: set.hh:170
Integer sets.
Definition: int.hh:174
const Test::Int::Assignment & ints(void) const
Return assignment for integer variables.
Definition: set.hh:187
CountableSetValues(void)
Default constructor.
Definition: set.hh:83
Value iterator producing subsets of an IntSet.
Definition: set.hh:76
bool assigned(void) const
Test whether all variables are assigned.
Definition: set.cpp:278
Passing integer arguments.
Definition: int.hh:610
virtual Gecode::Space * copy(bool share)
Faked copy function.
Definition: set.hh:63
Gecode::IntSet d
Initial domain.
Definition: set.hh:201
SetTestSpace(int n, Gecode::IntSet &d0, int i, SetTest *t, bool log=true)
Create test space without reification.
Definition: set.cpp:124
Gecode::SetOpType sot(void) const
Return current operation type.
Definition: set.hpp:115
const int v[7]
Definition: distinct.cpp:263
bool prune(const SetAssignment &a)
Perform random pruning.
Definition: set.cpp:409
General test support.
Definition: afc.cpp:43
int val(void) const
Return current value.
Definition: set.hh:110
unsigned int propagators(void)
Return the number of propagators.
Definition: set.cpp:689
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:784
int withInt
How many integer variables to iterate.
Definition: set.hh:172
void addToGlb(int v, int i, const SetAssignment &a)
Remove value v from the lower bound of x[i].
Definition: set.cpp:317
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:545
FakeSpace(void)
Faked constructor.
Definition: set.hh:61
Set variables
Definition: set.hh:131
virtual void post(Gecode::Space &home, Gecode::SetVarArray &x, Gecode::IntVarArray &y)=0
Post propagator.
Base class for tests with set constraints
Definition: set.hh:289
Generate all set assignments.
Definition: set.hh:158
Region r
Definition: region.cpp:82
void operator++(void)
Move to next assignment.
Definition: set.cpp:80
bool fixprob(void)
Perform fixpoint computation.
Definition: set.cpp:345
Base class for assignments
Definition: int.hh:63
bool operator()(void) const
Test whether iterator is done.
Definition: set.hpp:107
Gecode::IntVarArray y
Int variables to be tested.
Definition: set.hh:205
bool subsumed(bool b)
Check for subsumption if b is true.
Definition: set.cpp:201
~SetAssignment(void)
Destructor.
Definition: set.hh:191
struct Gecode::Space::@56::@58 c
Data available only during copying.
Value iterator for integer sets.
Definition: int.hh:315
Range iterator producing subsets of an IntSet.
Definition: set.hh:114
int withInt
How many integer variables are used by the test.
Definition: set.hh:207
Post propagator for SetVar x
Definition: set.hh:784
CountableSetValues(const Gecode::IntSet &d0, int cur0)
Initialize with set d0 and bit-pattern cur0.
Definition: set.hh:85
Set variable array
Definition: set.hh:572
void init(const Gecode::IntSet &d0, int cur0)
Initialize with set d0 and bit-pattern cur0.
Definition: set.hh:91
std::basic_ostream< Char, Traits > & operator<<(std::basic_ostream< Char, Traits > &os, const FloatView &x)
Print float variable view.
Definition: print.hpp:62
bool operator()(void) const
Test whether all assignments have been iterated.
Definition: set.hh:176
int size(void) const
Return arity.
Definition: set.hh:189
virtual bool solution(const SetAssignment &) const =0
Check for solution.
SetTest * test
The test currently run.
Definition: set.hh:213
Space for executing set tests.
Definition: set.hh:198
Iterate all subsets of a given set.
Definition: set.hh:134
ReifyMode
Mode for reification.
Definition: int.hh:829
int intval(void) const
Return value for first integer variable.
Definition: set.hh:185
int operator[](int i) const
Return value for variable i.
Definition: set.hh:180
bool operator()(void) const
Check if still subsets left.
Definition: set.hh:150
Gecode::SetRelType srt(void) const
Return current relation type.
Definition: set.hpp:99
Generate all assignments.
Definition: int.hh:83
virtual Gecode::Space * copy(bool share)
Copy space during cloning.
Definition: set.cpp:169
void operator++(void)
Increment to next relation type.
Definition: set.hpp:95
void init(const Gecode::IntSet &s)
Initialize with set s.
Definition: set.cpp:59