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