Generated on Thu Apr 5 2018 19:44:19 for Gecode by doxygen 1.8.13
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$ by $Author$
13  * $Revision$
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 
62 
65  private:
67  int cur;
68  int i;
69  public:
73  CountableSetValues(const Gecode::IntSet& d0, int cur0)
74  : dv(d0), cur(cur0), i(1) {
75  if (! (i & cur))
76  operator++();
77  }
79  void init(const Gecode::IntSet& d0, int cur0) {
80  dv = d0;
81  cur = cur0;
82  i = 1;
83  if (! (i & cur))
84  operator++();
85  }
87  bool operator()(void) const {
88  return i<=cur;
89  }
91  void operator++(void) {
92  do {
93  ++dv;
94  i = i<<1;
95  } while (! (i & cur) && i<cur);
96  }
98  int val(void) const { return dv.val(); }
99  };
100 
103  : public Gecode::Iter::Values::ToRanges<CountableSetValues> {
104  private:
107  public:
111  CountableSetRanges(const Gecode::IntSet& d, int cur) : v(d, cur) {
113  }
115  void init(const Gecode::IntSet& d, int cur) {
116  v.init(d, cur);
118  }
119  };
120 
122  class CountableSet {
123  private:
127  unsigned int cur;
129  unsigned int lubmax;
130  public:
132  CountableSet(const Gecode::IntSet& s);
134  CountableSet(void) {}
136  void init(const Gecode::IntSet& s);
138  bool operator()(void) const { return cur<lubmax; }
140  void operator++(void);
142  int val(void) const;
143  };
144 
147  private:
149  int n;
151  CountableSet* dsv;
155  bool done;
156  public:
160  int withInt;
162  SetAssignment(int n, const Gecode::IntSet& d, int i = 0);
164  bool operator()(void) const { return !done; }
166  void operator++(void);
168  int operator[](int i) const {
169  assert((i>=0) && (i<n));
170  return dsv[i].val();
171  }
173  int intval(void) const { return ir[0]; }
175  const Test::Int::Assignment& ints(void) const { return ir; }
177  int size(void) const { return n; }
179  ~SetAssignment(void) { delete [] dsv; }
180  };
181 
182 
183  class SetTest;
184 
186  class SetTestSpace : public Gecode::Space {
187  public:
195  int withInt;
199  bool reified;
202 
212  SetTestSpace(int n, Gecode::IntSet& d0, int i, SetTest* t,
213  bool log=true);
223  SetTestSpace(int n, Gecode::IntSet& d0, int i, SetTest* t,
224  Gecode::ReifyMode rm, bool log=true);
228  virtual Gecode::Space* copy(void);
230  void post(void);
232  bool failed(void);
234  bool subsumed(bool b);
236  void rel(int i, Gecode::SetRelType srt, const Gecode::IntSet& is);
238  void cardinality(int i, int cmin, int cmax);
240  void rel(int i, Gecode::IntRelType irt, int n);
242  void rel(bool sol);
244  void assign(const SetAssignment& a);
246  bool assigned(void) const;
248  void removeFromLub(int v, int i, const SetAssignment& a);
250  void removeFromLub(int v, int i, const SetAssignment& a,
251  SetTestSpace& c);
253  void addToGlb(int v, int i, const SetAssignment& a);
255  void addToGlb(int v, int i, const SetAssignment& a,
256  SetTestSpace& c);
258  bool fixprob(void);
260  bool prune(const SetAssignment& a);
262  unsigned int propagators(void);
264  void disable(void);
266  void enable(void);
268  bool disabled(const SetAssignment& a, SetTestSpace& c);
270  bool same(SetTestSpace& c);
271  };
272 
277  class SetTest : public Base {
278  private:
280  int arity;
282  Gecode::IntSet lub;
284  bool reified;
286  int withInt;
287 
289  void removeFromLub(int v, Gecode::SetVar& x, int i,
290  const Gecode::IntSet& a);
292  void addToGlb(int v, Gecode::SetVar& x, int i, const Gecode::IntSet& a);
294  SetAssignment* make_assignment(void);
295  protected:
297  bool disabled;
300  public:
308  SetTest(const std::string& s,
309  int a, const Gecode::IntSet& d, bool r=false, int w=0)
310  : Base("Set::"+s), arity(a), lub(d), reified(r), withInt(w),
311  disabled(true), testsubsumed(true) {}
313  virtual bool solution(const SetAssignment&) const = 0;
315  virtual void post(Gecode::Space& home, Gecode::SetVarArray& x,
316  Gecode::IntVarArray& y) = 0;
321  virtual bool run(void);
322 
324 
325  static std::string str(Gecode::SetRelType srt);
328  static std::string str(Gecode::SetOpType srt);
330  static std::string str(int i);
332  static std::string str(const Gecode::IntArgs& i);
334  };
336 
338  class SetRelTypes {
339  private:
341  static const Gecode::SetRelType srts[6];
343  int i;
344  public:
346  SetRelTypes(void);
348  bool operator()(void) const;
350  void operator++(void);
352  Gecode::SetRelType srt(void) const;
353  };
354 
356  class SetOpTypes {
357  private:
359  static const Gecode::SetOpType sots[4];
361  int i;
362  public:
364  SetOpTypes(void);
366  bool operator()(void) const;
368  void operator++(void);
370  Gecode::SetOpType sot(void) const;
371  };
372 
373 }}
374 
379 std::ostream&
380 operator<<(std::ostream&, const Test::Set::SetAssignment& a);
381 
382 #include "test/set.hpp"
383 
384 #endif
385 
386 // STATISTICS: test-set
virtual void post(Gecode::Space &, Gecode::SetVarArray &, Gecode::IntVarArray &, Gecode::Reify)
Post reified propagator.
Definition: set.hh:318
Iterator for Boolean operation types.
Definition: set.hh:356
NodeType t
Type of node.
Definition: bool-expr.cpp:234
bool disabled
Whether to perform full tests for disabled propagators.
Definition: set.hh:297
CountableSetRanges(const Gecode::IntSet &d, int cur)
Initialize with set d0 and bit-pattern cur0.
Definition: set.hh:111
SetRelType
Common relation types for sets.
Definition: set.hh:645
Iterator for set relation types.
Definition: set.hh:338
bool testsubsumed
Whether to check for subsumption.
Definition: set.hh:299
void operator++(void)
Move to next value.
Definition: set.hh:91
Gecode::Reify r
Reification information.
Definition: set.hh:197
void post(Home home, Term *t, int n, FloatRelType frt, FloatVal c)
Post propagator for linear constraint over floats.
Definition: post.cpp:242
void log(Home home, FloatVar x0, FloatVar x1)
Post propagator for .
Gecode::SetVarArray x
Set variables to be tested.
Definition: set.hh:191
ExecStatus subsumed(Space &home, Propagator &p, int c, TaskArray< Task > &t)
Check for subsumption (all tasks must be assigned)
Definition: subsumption.hpp:42
CountableSet(void)
Default constructor.
Definition: set.hh:134
int val(void) const
Return current subset.
Definition: set.cpp:68
Integer variable array.
Definition: int.hh:742
bool operator()(void) const
Test if finished.
Definition: set.hh:87
SetOpType
Common operations for sets.
Definition: set.hh:662
CountableSetRanges(void)
Default constructor.
Definition: set.hh:109
Computation spaces.
Definition: core.hpp:1668
ExecStatus prune(Space &home, ViewArray< VX > &x, ConstIntView)
Definition: rel.hpp:268
SetTest(const std::string &s, int a, const Gecode::IntSet &d, bool r=false, int w=0)
Constructor.
Definition: set.hh:308
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:115
Gecode::IntSet d(v, 7)
bool reified
Whether the test is for a reified propagator.
Definition: set.hh:199
Gecode::FloatVal c(-8, 8)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
IntRelType
Relation types for integers.
Definition: int.hh:904
void init(I &i)
Initialize with value iterator i.
Range iterator from value iterator.
Reification specification.
Definition: int.hh:855
Base class for all tests to be run
Definition: test.hh:107
Gecode::IntSet lub
The common superset for all domains.
Definition: set.hh:158
Integer sets.
Definition: int.hh:174
const Test::Int::Assignment & ints(void) const
Return assignment for integer variables.
Definition: set.hh:175
CountableSetValues(void)
Default constructor.
Definition: set.hh:71
Value iterator producing subsets of an IntSet.
Definition: set.hh:64
Passing integer arguments.
Definition: int.hh:608
std::basic_ostream< Char, Traits > & operator<<(std::basic_ostream< Char, Traits > &os, const Dictionary &d)
Print statistics summary.
Definition: scowl.hpp:13621
Gecode::IntSet d
Initial domain.
Definition: set.hh:189
LinIntExpr cardinality(const SetExpr &e)
Cardinality of set expression.
Definition: set-expr.cpp:818
const int v[7]
Definition: distinct.cpp:263
General test support.
Definition: afc.cpp:43
struct Gecode::@585::NNF::@62::@63 b
For binary nodes (and, or, eqv)
int val(void) const
Return current value.
Definition: set.hh:98
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:769
int withInt
How many integer variables to iterate.
Definition: set.hh:160
Set variables
Definition: set.hh:131
struct Gecode::@585::NNF::@62::@64 a
For atomic nodes.
Base class for tests with set constraints
Definition: set.hh:277
Generate all set assignments.
Definition: set.hh:146
Region r
Definition: region.cpp:69
Base class for assignments
Definition: int.hh:63
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:47
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Definition: rel.cpp:47
bool same(const Item &i, const Item &j)
Whether two items are the same.
Definition: propagate.hpp:76
Gecode::IntVarArray y
Int variables to be tested.
Definition: set.hh:193
~SetAssignment(void)
Destructor.
Definition: set.hh:179
Value iterator for integer sets.
Definition: int.hh:313
Range iterator producing subsets of an IntSet.
Definition: set.hh:102
int withInt
How many integer variables are used by the test.
Definition: set.hh:195
Post propagator for SetVar x
Definition: set.hh:769
CountableSetValues(const Gecode::IntSet &d0, int cur0)
Initialize with set d0 and bit-pattern cur0.
Definition: set.hh:73
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:79
bool operator()(void) const
Test whether all assignments have been iterated.
Definition: set.hh:164
int size(void) const
Return arity.
Definition: set.hh:177
SetTest * test
The test currently run.
Definition: set.hh:201
Space for executing set tests.
Definition: set.hh:186
void assign(Home home, const FloatVarArgs &x, FloatAssign fa, FloatBranchFilter bf, FloatVarValPrint vvp)
Assign all x with value selection vals.
Definition: branch.cpp:115
Iterate all subsets of a given set.
Definition: set.hh:122
ReifyMode
Mode for reification.
Definition: int.hh:827
int intval(void) const
Return value for first integer variable.
Definition: set.hh:173
int operator[](int i) const
Return value for variable i.
Definition: set.hh:168
bool operator()(void) const
Check if still subsets left.
Definition: set.hh:138
Generate all assignments.
Definition: int.hh:83