Generated on Sat Feb 7 2015 02:01:22 for Gecode by doxygen 1.8.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  * Last modified:
10  * $Date: 2012-09-07 17:31:22 +0200 (Fri, 07 Sep 2012) $ by $Author: schulte $
11  * $Revision: 13068 $
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  FakeSpace* fs = new FakeSpace;
83  bool ret;
84  {
85  Region r(*fs);
86  Iter::Ranges::NaryUnion u(r, sel, selected);
87 
88  CountableSetRanges z(x.lub, x[4]);
89  ret = Iter::Ranges::equal(u, z);
90  }
91  delete[] sel;
92  delete fs;
93  return ret;
94  }
96  virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
97  SetVarArgs xs(x.size()-2);
98  for (int i=x.size()-2; i--;)
99  xs[i]=x[i];
100  Gecode::element(home, SOT_UNION, xs, x[x.size()-2], x[x.size()-1]);
101  }
102  };
103  ElementUnion _elementunion("Element::Union");
104 
106  class ElementUnionConst : public SetTest {
107  private:
108  const IntSet i0;
109  const IntSet i1;
110  const IntSet i2;
111  public:
113  ElementUnionConst(const char* t)
114  : SetTest(t,2,ds_13,false), i0(-3,-3), i1(-1,1), i2(0,2) {}
116  virtual bool solution(const SetAssignment& x) const {
117  int selected = 0;
118  for (CountableSetValues sel2(x.lub, x[0]); sel2();
119  ++sel2, selected++) {}
120  CountableSetValues x4v(x.lub, x[1]);
121  if (selected==0)
122  return !x4v();
123  IntSet iss[] = {i0, i1, i2};
124  IntSetRanges* sel = new IntSetRanges[selected];
125  CountableSetValues selector(x.lub, x[0]);
126  for (int i=selected; i--;++selector) {
127  if (selector.val()>=3 || selector.val()<0) {
128  delete[] sel;
129  return false;
130  }
131  sel[i].init(iss[selector.val()]);
132  }
133 
134  FakeSpace* fs = new FakeSpace;
135  bool ret;
136  {
137  Region r(*fs);
138  Iter::Ranges::NaryUnion u(r, sel, selected);
139 
140  CountableSetRanges z(x.lub, x[1]);
141  ret = Iter::Ranges::equal(u, z);
142  }
143  delete[] sel;
144  delete fs;
145  return ret;
146  }
148  virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
149  IntSetArgs xs(3);
150  xs[0] = i0; xs[1] = i1; xs[2] = i2;
151  Gecode::element(home, SOT_UNION, xs, x[0], x[1]);
152  }
153  };
154  ElementUnionConst _elementunionconst("Element::UnionConst");
155 
157  class ElementInter : public SetTest {
158  public:
160  ElementInter(const char* t)
161  : SetTest(t,5,ds_12,false) {}
163  virtual bool solution(const SetAssignment& x) const {
164  int selected = 0;
165  for (CountableSetValues sel2(x.lub, x[3]); sel2();
166  ++sel2, selected++) {}
167  CountableSetRanges x4r(x.lub, x[4]);
168  if (selected==0)
170  CountableSetRanges* sel = new CountableSetRanges[selected];
171  CountableSetValues selector(x.lub, x[3]);
172  for (int i=selected; i--;++selector) {
173  if (selector.val()>=3 || selector.val()<0) {
174  delete[] sel;
175  return false;
176  }
177  sel[i].init(x.lub, x[selector.val()]);
178  }
179  FakeSpace* fs = new FakeSpace;
180  bool ret;
181  {
182  Region r(*fs);
183  Iter::Ranges::NaryInter u(r, sel, selected);
184 
185  CountableSetRanges z(x.lub, x[4]);
186  ret = Iter::Ranges::equal(u, z);
187  }
188  delete fs;
189  delete [] sel;
190  return ret;
191  }
193  virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
194  SetVarArgs xs(x.size()-2);
195  for (int i=x.size()-2; i--;)
196  xs[i]=x[i];
197  Gecode::element(home, SOT_INTER, xs, x[x.size()-2], x[x.size()-1]);
198  }
199  };
200  ElementInter _elementinter("Element::Inter");
201 
203  class ElementInterIn : public SetTest {
204  public:
206  ElementInterIn(const char* t)
207  : SetTest(t,5,ds_12,false) {}
209  virtual bool solution(const SetAssignment& x) const {
210  int selected = 0;
211  for (CountableSetValues sel2(x.lub, x[3]); sel2();
212  ++sel2, selected++) {}
213  CountableSetRanges x4r(x.lub, x[4]);
214  if (selected==0)
215  return Iter::Ranges::size(x4r)==4;
216  CountableSetRanges* sel = new CountableSetRanges[selected];
217  CountableSetValues selector(x.lub, x[3]);
218  for (int i=selected; i--;++selector) {
219  if (selector.val()>=3 || selector.val()<0) {
220  delete[] sel;
221  return false;
222  }
223  sel[i].init(x.lub, x[selector.val()]);
224  }
225  FakeSpace* fs = new FakeSpace;
226  bool ret;
227  {
228  Region r(*fs);
229  Iter::Ranges::NaryInter u(r,sel, selected);
230 
231  CountableSetRanges z(x.lub, x[4]);
232  ret = Iter::Ranges::equal(u, z);
233  }
234  delete fs;
235  delete [] sel;
236  return ret;
237  }
239  virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
240  SetVarArgs xs(x.size()-2);
241  for (int i=x.size()-2; i--;)
242  xs[i]=x[i];
243  Gecode::element(home, SOT_INTER, xs, x[x.size()-2], x[x.size()-1],
244  ds_12);
245  }
246  };
247  ElementInterIn _elementinterin("Element::InterIn");
248 
250  class ElementDisjoint : public SetTest {
251  public:
253  ElementDisjoint(const char* t)
254  : SetTest(t,5,ds_12,false) {}
256  virtual bool solution(const SetAssignment& x) const {
257  int selected = 0;
258  for (CountableSetValues sel2(x.lub, x[3]); sel2();
259  ++sel2, selected++) {
260  if (sel2.val() < 0)
261  return false;
262  }
263  CountableSetValues x4v(x.lub, x[4]);
264  if (selected == 0)
265  return !x4v();
266  CountableSetRanges* sel = new CountableSetRanges[selected];
267  CountableSetValues selector(x.lub, x[3]);
268  unsigned int cardsum = 0;
269  for (int i=selected; i--;++selector) {
270  if (selector.val()>=3 || selector.val()<0) {
271  delete[] sel;
272  return false;
273  }
274  sel[i].init(x.lub, x[selector.val()]);
275  CountableSetRanges xicard(x.lub, x[selector.val()]);
276  cardsum += Iter::Ranges::size(xicard);
277  }
278 
279  bool ret;
280  FakeSpace* fs = new FakeSpace;
281  {
282  Region r(*fs);
283  Iter::Ranges::NaryUnion u(r, sel, selected);
284  ret = Iter::Ranges::size(u) == cardsum;
285  u.reset();
286  CountableSetRanges z(x.lub, x[4]);
287  ret &= Iter::Ranges::equal(u, z);
288  }
289  delete fs;
290  delete[] sel;
291  return ret;
292  }
294  virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
295  SetVarArgs xs(x.size()-2);
296  for (int i=x.size()-2; i--;)
297  xs[i]=x[i];
298  Gecode::element(home, SOT_DUNION, xs, x[x.size()-2], x[x.size()-1]);
299  }
300  };
301  ElementDisjoint _elementdisjoint("Element::Disjoint");
302 
304  class ElementSet : public SetTest {
305  public:
307  ElementSet(const char* t)
308  : SetTest(t,4,ds_12,false,true) {}
310  virtual bool solution(const SetAssignment& x) const {
311  if (x.intval() < 0 || x.intval() > 2)
312  return false;
313  CountableSetRanges z(x.lub, x[3]);
314  CountableSetRanges y(x.lub, x[x.intval()]);
315  return Iter::Ranges::equal(y, z);
316  }
318  virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
319  SetVarArgs xs(x.size()-1);
320  for (int i=x.size()-1; i--;)
321  xs[i]=x[i];
322  Gecode::element(home, xs, y[0], x[x.size()-1]);
323  }
324  };
325  ElementSet _elementset("Element::Set");
326 
328  class ElementSetConst : public SetTest {
329  private:
330  const IntSet i0;
331  const IntSet i1;
332  const IntSet i2;
333  public:
335  ElementSetConst(const char* t)
336  : SetTest(t,1,ds_13,false,true), i0(-3,-3), i1(-1,1), i2(0,2) {}
338  virtual bool solution(const SetAssignment& x) const {
339  if (x.intval() < 0 || x.intval() > 2)
340  return false;
341  CountableSetRanges xr(x.lub, x[0]);
342  IntSet iss[] = {i0, i1, i2};
343  IntSetRanges isr(iss[x.intval()]);
344  return Iter::Ranges::equal(xr, isr);
345  }
347  virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
348  IntSetArgs xs(3);
349  xs[0] = i0; xs[1] = i1; xs[2] = i2;
350  Gecode::element(home, xs, y[0], x[0]);
351  }
352  };
353  ElementSetConst _elementsetconst("Element::SetConst");
354 
356  class MatrixIntSet : public SetTest {
357  protected:
360  public:
363  : SetTest("Element::Matrix::IntSet",1,IntSet(0,3),false,2),
364  tm(4) {
365  tm[0]=IntSet(0,0); tm[1]=IntSet(1,1);
366  tm[2]=IntSet(2,2); tm[3]=IntSet(3,3);
367  }
369  virtual bool solution(const SetAssignment& x) const {
370  // Get integer assignment
371  const Int::Assignment& y = x.ints();
372  // x-coordinate: y[0], y-coordinate: y[1], result: x[0]
373  using namespace Gecode;
374  if ((y[0] > 1) || (y[1] > 1))
375  return false;
376  Matrix<IntSetArgs> m(tm,2,2);
377  IntSetRanges a(m(y[0],y[1]));
378  CountableSetRanges b(x.lub, x[0]);
379  return Iter::Ranges::equal(a,b);
380  }
382  virtual void post(Gecode::Space& home, Gecode::SetVarArray& x,
383  Gecode::IntVarArray& y) {
384  // x-coordinate: x[0], y-coordinate: x[1], result: x[2]
385  using namespace Gecode;
386  Matrix<IntSetArgs> m(tm,2,2);
387  element(home, m, y[0], y[1], x[0]);
388  }
389  };
390 
392 
394 
395 }}}
396 
397 // STATISTICS: test-set
Gecode::IntSetArgs tm
Array for test matrix.
Definition: element.cpp:359
Test for matrix element with integer set array and set variable
Definition: element.cpp:356
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:96
NodeType t
Type of node.
Definition: bool-expr.cpp:234
virtual void post(Space &home, SetVarArray &x, IntVarArray &)
Post constraint on x.
Definition: element.cpp:193
Range iterator for integer sets.
Definition: int.hh:271
virtual bool solution(const SetAssignment &x) const
Test whether x is solution
Definition: element.cpp:369
Fake space for creation of regions.
Definition: set.hh:58
ElementInter(const char *t)
Create and register test.
Definition: element.cpp:160
bool equal(I &i, J &j)
Check whether range iterators i and j are equal.
Test for ElementSet constraint
Definition: element.cpp:304
virtual void post(Space &home, SetVarArray &x, IntVarArray &y)
Post constraint on x.
Definition: element.cpp:318
Integer variable array.
Definition: int.hh:741
virtual bool solution(const SetAssignment &x) const
Test whether x is solution
Definition: element.cpp:163
MatrixIntSet(void)
Create and register test.
Definition: element.cpp:362
Handle to region.
Definition: region.hpp:61
const unsigned int card
Maximum cardinality of an integer set.
Definition: set.hh:103
ElementInterIn _elementinterin("Element::InterIn")
ElementUnionConst _elementunionconst("Element::UnionConst")
Computation spaces.
Definition: core.hpp:1362
virtual void post(Space &home, SetVarArray &x, IntVarArray &)
Post constraint on x.
Definition: element.cpp:148
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:127
Gecode::IntArgs i(4, 1, 2, 3, 4)
void reset(void)
Reset iterator to start.
Test for ElementUnion constraint
Definition: element.cpp:59
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
const Test::Int::Assignment & ints(void) const
Return assignment for integer variables.
Definition: set.hh:187
ElementSet _elementset("Element::Set")
virtual bool solution(const SetAssignment &x) const
Test whether x is solution
Definition: element.cpp:310
virtual bool solution(const SetAssignment &x) const
Test whether x is solution
Definition: element.cpp:65
Range iterator for union of iterators.
virtual bool solution(const SetAssignment &x) const
Test whether x is solution
Definition: element.cpp:338
ElementInterIn(const char *t)
Create and register test.
Definition: element.cpp:206
unsigned int size(I &i)
Size of all ranges of range iterator i.
virtual bool solution(const SetAssignment &x) const
Test whether x is solution
Definition: element.cpp:116
virtual void post(Space &home, SetVarArray &x, IntVarArray &y)
Post constraint on x.
Definition: element.cpp:347
virtual bool solution(const SetAssignment &x) const
Test whether x is solution
Definition: element.cpp:209
Gecode::IntSet lub
The common superset for all domains.
Definition: set.hh:170
Intersection
Definition: set.hh:664
Integer sets.
Definition: int.hh:171
void element(Home home, IntSharedArray c, IntVar x0, IntVar x1, IntConLevel)
Post domain consistent propagator for .
Definition: element.cpp:43
int val(void) const
Return current value.
Definition: set.hh:110
Test for ElementDisjoint constraint
Definition: element.cpp:250
ElementUnion _elementunion("Element::Union")
Value iterator producing subsets of an IntSet.
Definition: set.hh:76
ElementDisjoint(const char *t)
Create and register test.
Definition: element.cpp:253
ElementSetConst _elementsetconst("Element::SetConst")
union Gecode::@518::NNF::@57 u
Union depending on nodetype t.
General test support.
Definition: afc.cpp:43
int intval(void) const
Return value for first integer variable.
Definition: set.hh:185
Union.
Definition: set.hh:662
Passing set variables.
Definition: set.hh:490
ElementDisjoint _elementdisjoint("Element::Disjoint")
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
Range iterator for intersection of iterators.
Disjoint union.
Definition: set.hh:663
Base class for tests with set constraints
Definition: set.hh:271
Generate all set assignments.
Definition: set.hh:158
ElementSet(const char *t)
Create and register test.
Definition: element.cpp:307
Base class for assignments
Definition: int.hh:63
Range iterator producing subsets of an IntSet.
Definition: set.hh:114
Test for ElementInter constraint
Definition: element.cpp:157
virtual void post(Space &home, SetVarArray &x, IntVarArray &)
Post constraint on x.
Definition: element.cpp:294
Matrix-interface for arrays.
Definition: minimodel.hh:1924
Test for ElementUnionConst constraint
Definition: element.cpp:106
Set variable array
Definition: set.hh:571
struct Gecode::@518::NNF::@57::@58 b
For binary nodes (and, or, eqv)
Gecode toplevel namespace
ElementUnionConst(const char *t)
Create and register test.
Definition: element.cpp:113
MatrixIntSet _emis
Definition: element.cpp:391
ElementSetConst(const char *t)
Create and register test.
Definition: element.cpp:335
Test for ElementInter constraint
Definition: element.cpp:203
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:985
virtual void post(Gecode::Space &home, Gecode::SetVarArray &x, Gecode::IntVarArray &y)
Post constraint on x and y.
Definition: element.cpp:382
ElementInter _elementinter("Element::Inter")
struct Gecode::@518::NNF::@57::@59 a
For atomic nodes.
virtual bool solution(const SetAssignment &x) const
Test whether x is solution
Definition: element.cpp:256
virtual void post(Space &home, SetVarArray &x, IntVarArray &)
Post constraint on x.
Definition: element.cpp:239
Test for ElementSetConst constraint
Definition: element.cpp:328