Generated on Thu Apr 5 2018 19:44:19 for Gecode by doxygen 1.8.13
element.cpp
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  *
6  * Copyright:
7  * Guido Tack, 2005
8  *
9  * Last modified:
10  * $Date$ by $Author$
11  * $Revision$
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 #include <gecode/minimodel.hh>
39 
40 #include "test/set.hh"
41 
42 using namespace Gecode;
43 
44 namespace Test { namespace Set {
45 
47  namespace Element {
48 
54 
55  static IntSet ds_12(-1,2);
56  static IntSet ds_13(-1,3);
57 
59  class ElementUnion : public SetTest {
60  public:
62  ElementUnion(const char* t)
63  : SetTest(t,5,ds_12,false) {}
65  virtual bool solution(const SetAssignment& x) const {
66  int selected = 0;
67  for (CountableSetValues sel2(x.lub, x[3]); sel2();
68  ++sel2, selected++) {}
69  CountableSetValues x4v(x.lub, x[4]);
70  if (selected==0)
71  return !x4v();
72  CountableSetRanges* sel = new CountableSetRanges[selected];
73  CountableSetValues selector(x.lub, x[3]);
74  for (int i=selected; i--;++selector) {
75  if (selector.val()>=3 || selector.val()<0) {
76  delete[] sel;
77  return false;
78  }
79  sel[i].init(x.lub, x[selector.val()]);
80  }
81 
82  bool ret;
83  {
84  Region r;
85  Iter::Ranges::NaryUnion u(r, sel, selected);
86 
87  CountableSetRanges z(x.lub, x[4]);
88  ret = Iter::Ranges::equal(u, z);
89  }
90  delete[] sel;
91  return ret;
92  }
94  virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
95  SetVarArgs xs(x.size()-2);
96  for (int i=x.size()-2; i--;)
97  xs[i]=x[i];
98  Gecode::element(home, SOT_UNION, xs, x[x.size()-2], x[x.size()-1]);
99  }
100  };
101  ElementUnion _elementunion("Element::Union");
102 
104  class ElementUnionConst : public SetTest {
105  private:
106  const IntSet i0;
107  const IntSet i1;
108  const IntSet i2;
109  public:
111  ElementUnionConst(const char* t)
112  : SetTest(t,2,ds_13,false), i0(-3,-3), i1(-1,1), i2(0,2) {}
114  virtual bool solution(const SetAssignment& x) const {
115  int selected = 0;
116  for (CountableSetValues sel2(x.lub, x[0]); sel2();
117  ++sel2, selected++) {}
118  CountableSetValues x4v(x.lub, x[1]);
119  if (selected==0)
120  return !x4v();
121  IntSet iss[] = {i0, i1, i2};
122  IntSetRanges* sel = new IntSetRanges[selected];
123  CountableSetValues selector(x.lub, x[0]);
124  for (int i=selected; i--;++selector) {
125  if (selector.val()>=3 || selector.val()<0) {
126  delete[] sel;
127  return false;
128  }
129  sel[i].init(iss[selector.val()]);
130  }
131 
132  bool ret;
133  {
134  Region r;
135  Iter::Ranges::NaryUnion u(r, sel, selected);
136 
137  CountableSetRanges z(x.lub, x[1]);
138  ret = Iter::Ranges::equal(u, z);
139  }
140  delete[] sel;
141  return ret;
142  }
144  virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
145  IntSetArgs xs(3);
146  xs[0] = i0; xs[1] = i1; xs[2] = i2;
147  Gecode::element(home, SOT_UNION, xs, x[0], x[1]);
148  }
149  };
150  ElementUnionConst _elementunionconst("Element::UnionConst");
151 
153  class ElementInter : public SetTest {
154  public:
156  ElementInter(const char* t)
157  : SetTest(t,5,ds_12,false) {}
159  virtual bool solution(const SetAssignment& x) const {
160  int selected = 0;
161  for (CountableSetValues sel2(x.lub, x[3]); sel2();
162  ++sel2, selected++) {}
163  CountableSetRanges x4r(x.lub, x[4]);
164  if (selected==0)
166  CountableSetRanges* sel = new CountableSetRanges[selected];
167  CountableSetValues selector(x.lub, x[3]);
168  for (int i=selected; i--;++selector) {
169  if (selector.val()>=3 || selector.val()<0) {
170  delete[] sel;
171  return false;
172  }
173  sel[i].init(x.lub, x[selector.val()]);
174  }
175  bool ret;
176  {
177  Region r;
178  Iter::Ranges::NaryInter u(r, sel, selected);
179 
180  CountableSetRanges z(x.lub, x[4]);
181  ret = Iter::Ranges::equal(u, z);
182  }
183  delete [] sel;
184  return ret;
185  }
187  virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
188  SetVarArgs xs(x.size()-2);
189  for (int i=x.size()-2; i--;)
190  xs[i]=x[i];
191  Gecode::element(home, SOT_INTER, xs, x[x.size()-2], x[x.size()-1]);
192  }
193  };
194  ElementInter _elementinter("Element::Inter");
195 
197  class ElementInterIn : public SetTest {
198  public:
200  ElementInterIn(const char* t)
201  : SetTest(t,5,ds_12,false) {}
203  virtual bool solution(const SetAssignment& x) const {
204  int selected = 0;
205  for (CountableSetValues sel2(x.lub, x[3]); sel2();
206  ++sel2, selected++) {}
207  CountableSetRanges x4r(x.lub, x[4]);
208  if (selected==0)
209  return Iter::Ranges::size(x4r)==4;
210  CountableSetRanges* sel = new CountableSetRanges[selected];
211  CountableSetValues selector(x.lub, x[3]);
212  for (int i=selected; i--;++selector) {
213  if (selector.val()>=3 || selector.val()<0) {
214  delete[] sel;
215  return false;
216  }
217  sel[i].init(x.lub, x[selector.val()]);
218  }
219  bool ret;
220  {
221  Region r;
222  Iter::Ranges::NaryInter u(r,sel, selected);
223 
224  CountableSetRanges z(x.lub, x[4]);
225  ret = Iter::Ranges::equal(u, z);
226  }
227  delete [] sel;
228  return ret;
229  }
231  virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
232  SetVarArgs xs(x.size()-2);
233  for (int i=x.size()-2; i--;)
234  xs[i]=x[i];
235  Gecode::element(home, SOT_INTER, xs, x[x.size()-2], x[x.size()-1],
236  ds_12);
237  }
238  };
239  ElementInterIn _elementinterin("Element::InterIn");
240 
242  class ElementDisjoint : public SetTest {
243  public:
245  ElementDisjoint(const char* t)
246  : SetTest(t,5,ds_12,false) {}
248  virtual bool solution(const SetAssignment& x) const {
249  int selected = 0;
250  for (CountableSetValues sel2(x.lub, x[3]); sel2();
251  ++sel2, selected++) {
252  if (sel2.val() < 0)
253  return false;
254  }
255  CountableSetValues x4v(x.lub, x[4]);
256  if (selected == 0)
257  return !x4v();
258  CountableSetRanges* sel = new CountableSetRanges[selected];
259  CountableSetValues selector(x.lub, x[3]);
260  unsigned int cardsum = 0;
261  for (int i=selected; i--;++selector) {
262  if (selector.val()>=3 || selector.val()<0) {
263  delete[] sel;
264  return false;
265  }
266  sel[i].init(x.lub, x[selector.val()]);
267  CountableSetRanges xicard(x.lub, x[selector.val()]);
268  cardsum += Iter::Ranges::size(xicard);
269  }
270 
271  bool ret;
272  {
273  Region r;
274  Iter::Ranges::NaryUnion u(r, sel, selected);
275  ret = Iter::Ranges::size(u) == cardsum;
276  u.reset();
277  CountableSetRanges z(x.lub, x[4]);
278  ret &= Iter::Ranges::equal(u, z);
279  }
280  delete[] sel;
281  return ret;
282  }
284  virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
285  SetVarArgs xs(x.size()-2);
286  for (int i=x.size()-2; i--;)
287  xs[i]=x[i];
288  Gecode::element(home, SOT_DUNION, xs, x[x.size()-2], x[x.size()-1]);
289  }
290  };
291  ElementDisjoint _elementdisjoint("Element::Disjoint");
292 
294  class ElementSet : public SetTest {
295  public:
297  ElementSet(const char* t)
298  : SetTest(t,4,ds_12,false,true) {}
300  virtual bool solution(const SetAssignment& x) const {
301  if (x.intval() < 0 || x.intval() > 2)
302  return false;
303  CountableSetRanges z(x.lub, x[3]);
304  CountableSetRanges y(x.lub, x[x.intval()]);
305  return Iter::Ranges::equal(y, z);
306  }
308  virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
309  SetVarArgs xs(x.size()-1);
310  for (int i=x.size()-1; i--;)
311  xs[i]=x[i];
312  Gecode::element(home, xs, y[0], x[x.size()-1]);
313  }
314  };
315  ElementSet _elementset("Element::Set");
316 
318  class ElementSetConst : public SetTest {
319  private:
320  const IntSet i0;
321  const IntSet i1;
322  const IntSet i2;
323  public:
325  ElementSetConst(const char* t)
326  : SetTest(t,1,ds_13,false,true), i0(-3,-3), i1(-1,1), i2(0,2) {}
328  virtual bool solution(const SetAssignment& x) const {
329  if (x.intval() < 0 || x.intval() > 2)
330  return false;
331  CountableSetRanges xr(x.lub, x[0]);
332  IntSet iss[] = {i0, i1, i2};
333  IntSetRanges isr(iss[x.intval()]);
334  return Iter::Ranges::equal(xr, isr);
335  }
337  virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
338  IntSetArgs xs(3);
339  xs[0] = i0; xs[1] = i1; xs[2] = i2;
340  Gecode::element(home, xs, y[0], x[0]);
341  }
342  };
343  ElementSetConst _elementsetconst("Element::SetConst");
344 
346  class MatrixIntSet : public SetTest {
347  protected:
350  public:
353  : SetTest("Element::Matrix::IntSet",1,IntSet(0,3),false,2),
354  tm(4) {
355  tm[0]=IntSet(0,0); tm[1]=IntSet(1,1);
356  tm[2]=IntSet(2,2); tm[3]=IntSet(3,3);
357  }
359  virtual bool solution(const SetAssignment& x) const {
360  // Get integer assignment
361  const Int::Assignment& y = x.ints();
362  // x-coordinate: y[0], y-coordinate: y[1], result: x[0]
363  using namespace Gecode;
364  if ((y[0] > 1) || (y[1] > 1))
365  return false;
366  Matrix<IntSetArgs> m(tm,2,2);
367  IntSetRanges a(m(y[0],y[1]));
368  CountableSetRanges b(x.lub, x[0]);
369  return Iter::Ranges::equal(a,b);
370  }
372  virtual void post(Gecode::Space& home, Gecode::SetVarArray& x,
374  // x-coordinate: x[0], y-coordinate: x[1], result: x[2]
375  using namespace Gecode;
376  Matrix<IntSetArgs> m(tm,2,2);
377  element(home, m, y[0], y[1], x[0]);
378  }
379  };
380 
382 
384 
385 }}}
386 
387 // STATISTICS: test-set
Gecode::IntSetArgs tm
Array for test matrix.
Definition: element.cpp:349
Test for matrix element with integer set array and set variable
Definition: element.cpp:346
virtual bool solution(const SetAssignment &x) const
Test whether x is solution
Definition: element.cpp:248
ElementUnion(const char *t)
Create and register test.
Definition: element.cpp:62
virtual void post(Space &home, SetVarArray &x, IntVarArray &)
Post constraint on x.
Definition: element.cpp:94
NodeType t
Type of node.
Definition: bool-expr.cpp:234
virtual bool solution(const SetAssignment &x) const
Test whether x is solution
Definition: element.cpp:159
virtual bool solution(const SetAssignment &x) const
Test whether x is solution
Definition: element.cpp:114
virtual void post(Space &home, SetVarArray &x, IntVarArray &)
Post constraint on x.
Definition: element.cpp:187
Range iterator for integer sets.
Definition: int.hh:272
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:973
ElementInter(const char *t)
Create and register test.
Definition: element.cpp:156
bool equal(I &i, J &j)
Check whether range iterators i and j are equal.
Test for ElementSet constraint
Definition: element.cpp:294
virtual void post(Space &home, SetVarArray &x, IntVarArray &y)
Post constraint on x.
Definition: element.cpp:308
Integer variable array.
Definition: int.hh:742
MatrixIntSet(void)
Create and register test.
Definition: element.cpp:352
const unsigned int card
Maximum cardinality of an integer set.
Definition: set.hh:105
ElementInterIn _elementinterin("Element::InterIn")
ElementUnionConst _elementunionconst("Element::UnionConst")
Computation spaces.
Definition: core.hpp:1668
virtual void post(Space &home, SetVarArray &x, IntVarArray &)
Post constraint on x.
Definition: element.cpp:144
void init(const IntSet &s)
Initialize with ranges for set s.
Definition: int-set-1.hpp:181
void init(const Gecode::IntSet &d, int cur)
Initialize with set d0 and bit-pattern cur0.
Definition: set.hh:115
Test for Region memory area
Definition: region.cpp:46
Gecode::IntArgs i(4, 1, 2, 3, 4)
void reset(void)
Reset iterator to start.
Test for ElementUnion constraint
Definition: element.cpp:59
virtual bool solution(const SetAssignment &x) const
Test whether x is solution
Definition: element.cpp:300
virtual bool solution(const SetAssignment &x) const
Test whether x is solution
Definition: element.cpp:65
ElementSet _elementset("Element::Set")
Range iterator for union of iterators.
ElementInterIn(const char *t)
Create and register test.
Definition: element.cpp:200
unsigned int size(I &i)
Size of all ranges of range iterator i.
virtual void post(Space &home, SetVarArray &x, IntVarArray &y)
Post constraint on x.
Definition: element.cpp:337
Gecode::IntSet lub
The common superset for all domains.
Definition: set.hh:158
Intersection
Definition: set.hh:665
union Gecode::@585::NNF::@62 u
Union depending on nodetype t.
Integer sets.
Definition: int.hh:174
Post propagator for SetVar SetOpType SetVar SetRelType SetVar z
Definition: set.hh:769
const Test::Int::Assignment & ints(void) const
Return assignment for integer variables.
Definition: set.hh:175
Test for ElementDisjoint constraint
Definition: element.cpp:242
ElementUnion _elementunion("Element::Union")
Value iterator producing subsets of an IntSet.
Definition: set.hh:64
virtual bool solution(const SetAssignment &x) const
Test whether x is solution
Definition: element.cpp:359
ElementDisjoint(const char *t)
Create and register test.
Definition: element.cpp:245
ElementSetConst _elementsetconst("Element::SetConst")
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:769
virtual bool solution(const SetAssignment &x) const
Test whether x is solution
Definition: element.cpp:203
General test support.
Definition: afc.cpp:43
Union.
Definition: set.hh:663
struct Gecode::@585::NNF::@62::@63 b
For binary nodes (and, or, eqv)
int val(void) const
Return current value.
Definition: set.hh:98
Passing set variables.
Definition: set.hh:492
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:769
ElementDisjoint _elementdisjoint("Element::Disjoint")
struct Gecode::@585::NNF::@62::@64 a
For atomic nodes.
Range iterator for intersection of iterators.
Disjoint union.
Definition: set.hh:664
Base class for tests with set constraints
Definition: set.hh:277
Generate all set assignments.
Definition: set.hh:146
ElementSet(const char *t)
Create and register test.
Definition: element.cpp:297
Base class for assignments
Definition: int.hh:63
Range iterator producing subsets of an IntSet.
Definition: set.hh:102
Test for ElementInter constraint
Definition: element.cpp:153
Post propagator for SetVar x
Definition: set.hh:769
virtual void post(Space &home, SetVarArray &x, IntVarArray &)
Post constraint on x.
Definition: element.cpp:284
Matrix-interface for arrays.
Definition: minimodel.hh:2052
Test for ElementUnionConst constraint
Definition: element.cpp:104
Set variable array
Definition: set.hh:572
Gecode toplevel namespace
virtual bool solution(const SetAssignment &x) const
Test whether x is solution
Definition: element.cpp:328
ElementUnionConst(const char *t)
Create and register test.
Definition: element.cpp:111
MatrixIntSet _emis
Definition: element.cpp:381
ElementSetConst(const char *t)
Create and register test.
Definition: element.cpp:325
Test for ElementInter constraint
Definition: element.cpp:197
virtual void post(Gecode::Space &home, Gecode::SetVarArray &x, Gecode::IntVarArray &y)
Post constraint on x and y.
Definition: element.cpp:372
int intval(void) const
Return value for first integer variable.
Definition: set.hh:173
ElementInter _elementinter("Element::Inter")
void element(Home home, IntSharedArray c, IntVar x0, IntVar x1, IntPropLevel)
Post domain consistent propagator for .
Definition: element.cpp:43
virtual void post(Space &home, SetVarArray &x, IntVarArray &)
Post constraint on x.
Definition: element.cpp:231
Test for ElementSetConst constraint
Definition: element.cpp:318