Generated on Sat Nov 9 2013 19:18:26 for Gecode by doxygen 1.8.4
dom.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: 2013-02-27 16:45:34 +0100 (Wed, 27 Feb 2013) $ by $Author: schulte $
11  * $Revision: 13424 $
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 "test/set.hh"
39 
40 using namespace Gecode;
41 
42 namespace Test { namespace Set {
43 
45  namespace Dom {
46 
52 
53  static const int d1r[4][2] = {
54  {-4,-3},{-1,-1},{1,1},{3,5}
55  };
56  static IntSet d1(d1r,4);
57 
58  static const int d1cr[5][2] = {
60  {-2,-2},{0,0},{2,2},
62  };
63  static IntSet d1c(d1cr,5);
64 
65  static IntSet ds_33(-3,3);
66 
67  static const int d2r[2][2] = {
69  };
70  static IntSet ds_33c(d2r,2);
71 
72  namespace {
73  static int minSymDiff(const SetAssignment& x, int i, const IntSet& is) {
75  CountableSetRanges xr00(x.lub, x[i]);
76  IntSetRanges xr10(is);
77  DiffA a(xr00,xr10);
79  CountableSetRanges xr01(x.lub, x[i]);
80  IntSetRanges xr11(is);
81  DiffB b(xr11,xr01);
83  return u() ? u.min() : Gecode::Set::Limits::max+1;
84  }
85  template<class I>
86  static bool in(int i, I& c, bool eq=false) {
87  if (eq && i==Gecode::Set::Limits::max+1)
88  return true;
90  return Iter::Ranges::subset(s,c);
91  }
92  }
93 
95  class DomRange : public SetTest {
96  private:
98  IntSet is;
99  public:
101  DomRange(SetRelType srt0, int n) :
102  SetTest("Dom::Range::"+str(srt0)+"::"+str(n),n,ds_33,(n == 1)),
103  srt(srt0), is(srt == Gecode::SRT_CMPL ? ds_33c: ds_33) {}
105  virtual bool solution(const SetAssignment& x) const {
106  for (int i=x.size(); i--; ) {
107  CountableSetRanges xr(x.lub, x[i]);
108  IntSetRanges dr(is);
109  switch (srt) {
110  case SRT_EQ:
111  if (!Iter::Ranges::equal(xr, dr))
112  return false;
113  break;
114  case SRT_LQ:
115  if (!((!xr()) || in(minSymDiff(x,i,is),dr,true)))
116  return false;
117  break;
118  case SRT_LE:
119  if (!(xr() ? in(minSymDiff(x,i,is),dr) : dr()))
120  return false;
121  break;
122  case SRT_GQ:
123  if (!((!dr()) || in(minSymDiff(x,i,is),xr,true)))
124  return false;
125  break;
126  case SRT_GR:
127  if (!(dr() ? in(minSymDiff(x,i,is),xr) : xr()))
128  return false;
129  break;
130  case SRT_NQ:
131  if (Iter::Ranges::equal(xr, dr))
132  return false;
133  break;
134  case SRT_SUB:
135  if (!Iter::Ranges::subset(xr, dr))
136  return false;
137  break;
138  case SRT_SUP:
139  if (!Iter::Ranges::subset(dr, xr))
140  return false;
141  break;
142  case SRT_DISJ:
143  {
145  inter(xr, dr);
146  if (inter())
147  return false;
148  }
149  break;
150  case SRT_CMPL:
151  {
153  if (!Iter::Ranges::equal(xr,drc))
154  return false;
155  }
156  break;
157  }
158  }
159  return true;
160  }
162  virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
163  if (x.size() == 1)
164  Gecode::dom(home, x[0], srt, is);
165  else
166  Gecode::dom(home, x, srt, is);
167  }
169  virtual void post(Space& home, SetVarArray& x, IntVarArray&, Reify r) {
170  assert(x.size() == 1);
171  Gecode::dom(home, x[0], srt, is, r);
172  }
173  };
174 
176  class DomIntRange : public SetTest {
177  private:
178  Gecode::SetRelType srt;
179  public:
182  : SetTest("Dom::IntRange::"+str(srt0)+"::"+str(n),1,ds_33,n==1),
183  srt(srt0) {}
185  virtual bool solution(const SetAssignment& x) const {
186  for (int i=x.size(); i--; ) {
187  CountableSetRanges xr(x.lub, x[i]);
188  IntSet is(-3,-1);
189  IntSetRanges dr(is);
190  switch (srt) {
191  case SRT_EQ:
192  if (!Iter::Ranges::equal(xr, dr))
193  return false;
194  break;
195  case SRT_LQ:
196  if (!((!xr()) || in(minSymDiff(x,i,is),dr,true)))
197  return false;
198  break;
199  case SRT_LE:
200  if (!(xr() ? in(minSymDiff(x,i,is),dr) : dr()))
201  return false;
202  break;
203  case SRT_GQ:
204  if (!((!dr()) || in(minSymDiff(x,i,is),xr,true)))
205  return false;
206  break;
207  case SRT_GR:
208  if (!(dr() ? in(minSymDiff(x,i,is),xr) : xr()))
209  return false;
210  break;
211  case SRT_NQ:
212  if (!(!Iter::Ranges::equal(xr, dr)))
213  return false;
214  break;
215  case SRT_SUB:
216  if (!(Iter::Ranges::subset(xr, dr)))
217  return false;
218  break;
219  case SRT_SUP:
220  if (!(Iter::Ranges::subset(dr, xr)))
221  return false;
222  break;
223  case SRT_DISJ:
224  {
226  inter(xr, dr);
227  if (inter())
228  return false;
229  }
230  break;
231  case SRT_CMPL:
232  {
234  if (!Iter::Ranges::equal(xr,drc))
235  return false;
236  }
237  break;
238  }
239  }
240  return true;
241  }
243  virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
244  if (x.size() == 1)
245  Gecode::dom(home, x[0], srt, -3, -1);
246  else
247  Gecode::dom(home, x, srt, -3, -1);
248  }
250  virtual void post(Space& home, SetVarArray& x, IntVarArray&, Reify r) {
251  assert(x.size() == 1);
252  Gecode::dom(home, x[0], srt, -3, -1, r);
253  }
254  };
255 
257  class DomInt : public SetTest {
258  private:
259  Gecode::SetRelType srt;
260  public:
263  SetTest("Dom::Int::"+str(srt0)+"::"+str(n),n,ds_33,n==1),
264  srt(srt0) {}
266  virtual bool solution(const SetAssignment& x) const {
267  IntSet is(-3,-3);
268  for (int i=x.size(); i--; ) {
269  CountableSetRanges xr(x.lub, x[i]);
270  IntSetRanges dr(is);
271  switch (srt) {
272  case SRT_EQ:
273  if (!Iter::Ranges::equal(xr, dr))
274  return false;
275  break;
276  case SRT_LQ:
277  if (!((!xr()) || in(minSymDiff(x,i,is),dr,true)))
278  return false;
279  break;
280  case SRT_LE:
281  if (!(xr() ? in(minSymDiff(x,i,is),dr) : dr()))
282  return false;
283  break;
284  case SRT_GQ:
285  if (!((!dr()) || in(minSymDiff(x,i,is),xr,true)))
286  return false;
287  break;
288  case SRT_GR:
289  if (!(dr() ? in(minSymDiff(x,i,is),xr) : xr()))
290  return false;
291  break;
292  case SRT_NQ:
293  if (Iter::Ranges::equal(xr, dr))
294  return false;
295  break;
296  case SRT_SUB:
297  if (!(Iter::Ranges::subset(xr, dr)))
298  return false;
299  break;
300  case SRT_SUP:
301  if (!(Iter::Ranges::subset(dr, xr)))
302  return false;
303  break;
304  case SRT_DISJ:
305  {
307  inter(xr, dr);
308 
309  if (inter())
310  return false;
311  break;
312  }
313  case SRT_CMPL:
314  {
316 
317  if (!Iter::Ranges::equal(xr,drc))
318  return false;
319  break;
320  }
321  }
322  }
323  return true;
324  }
326  virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
327  if (x.size() == 1)
328  Gecode::dom(home, x[0], srt, -3);
329  else
330  Gecode::dom(home, x, srt, -3);
331  }
333  virtual void post(Space& home, SetVarArray& x, IntVarArray&, Reify r) {
334  assert(x.size() == 1);
335  Gecode::dom(home, x[0], srt, -3, r);
336  }
337  };
338 
340  class DomDom : public SetTest {
341  private:
342  Gecode::SetRelType srt;
343  Gecode::IntSet is;
344  public:
347  SetTest("Dom::Dom::"+str(srt0)+"::"+str(n),n,d1,(n == 1)),
348  srt(srt0), is(srt == Gecode::SRT_CMPL ? d1c: d1) {}
350  virtual bool solution(const SetAssignment& x) const {
351  for (int i=x.size(); i--; ) {
352  CountableSetRanges xr(x.lub, x[i]);
353  IntSetRanges dr(is);
354  switch (srt) {
355  case SRT_EQ:
356  if (!Iter::Ranges::equal(xr, dr))
357  return false;
358  break;
359  case SRT_LQ:
360  if (!((!xr()) || in(minSymDiff(x,i,is),dr,true)))
361  return false;
362  break;
363  case SRT_LE:
364  if (!(xr() ? in(minSymDiff(x,i,is),dr) : dr()))
365  return false;
366  break;
367  case SRT_GQ:
368  if (!((!dr()) || in(minSymDiff(x,i,is),xr,true)))
369  return false;
370  break;
371  case SRT_GR:
372  if (!(dr() ? in(minSymDiff(x,i,is),xr) : xr()))
373  return false;
374  break;
375  case SRT_NQ:
376  if (Iter::Ranges::equal(xr, dr))
377  return false;
378  break;
379  case SRT_SUB:
380  if (!Iter::Ranges::subset(xr, dr))
381  return false;
382  break;
383  case SRT_SUP:
384  if (!Iter::Ranges::subset(dr, xr))
385  return false;
386  break;
387  case SRT_DISJ:
388  {
390  inter(xr, dr);
391  if (inter())
392  return false;
393  }
394  break;
395  case SRT_CMPL:
396  {
398  if (!Iter::Ranges::equal(xr,drc))
399  return false;
400  }
401  break;
402  }
403  }
404  return true;
405  }
407  virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
408  if (x.size() == 1)
409  Gecode::dom(home, x[0], srt, is);
410  else
411  Gecode::dom(home, x, srt, is);
412  }
414  virtual void post(Space& home, SetVarArray& x, IntVarArray&, Reify r) {
415  assert(x.size() == 1);
416  Gecode::dom(home, x[0], srt, is, r);
417  }
418  };
419 
421  class CardRange : public SetTest {
422  public:
425  : SetTest("Dom::CardRange::"+str(n),n,d1,false) {}
427  virtual bool solution(const SetAssignment& x) const {
428  for (int i=x.size(); i--; ) {
429  CountableSetRanges xr(x.lub, x[i]);
430  unsigned int card = Iter::Ranges::size(xr);
431  if ((card < 2) || (card > 3))
432  return false;
433  }
434  return true;
435  }
437  virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
438  if (x.size() == 1)
439  Gecode::cardinality(home, x[0], 2, 3);
440  else
441  Gecode::cardinality(home, x, 2, 3);
442  }
443  };
444 
445  DomRange _domrange_eq1(SRT_EQ,1);
446  DomRange _domrange_lq1(SRT_LQ,1);
447  DomRange _domrange_le1(SRT_LE,1);
448  DomRange _domrange_gq1(SRT_GQ,1);
449  DomRange _domrange_gr1(SRT_GR,1);
450  DomRange _domrange_nq1(SRT_NQ,1);
451  DomRange _domrange_sub1(SRT_SUB,1);
452  DomRange _domrange_sup1(SRT_SUP,1);
453  DomRange _domrange_disj1(SRT_DISJ,1);
454  DomRange _domrange_cmpl1(SRT_CMPL,1);
455  DomRange _domrange_eq2(SRT_EQ,2);
456  DomRange _domrange_lq2(SRT_LQ,2);
457  DomRange _domrange_le2(SRT_LE,2);
458  DomRange _domrange_gq2(SRT_GQ,2);
459  DomRange _domrange_gr2(SRT_GR,2);
460  DomRange _domrange_nq2(SRT_NQ,2);
461  DomRange _domrange_sub2(SRT_SUB,2);
462  DomRange _domrange_sup2(SRT_SUP,2);
463  DomRange _domrange_disj2(SRT_DISJ,2);
464  DomRange _domrange_cmpl2(SRT_CMPL,2);
465 
466  DomIntRange _domintrange_eq1(SRT_EQ,1);
467  DomIntRange _domintrange_lq1(SRT_LQ,1);
468  DomIntRange _domintrange_le1(SRT_LE,1);
469  DomIntRange _domintrange_gq1(SRT_GQ,1);
470  DomIntRange _domintrange_gr1(SRT_GR,1);
471  DomIntRange _domintrange_nq1(SRT_NQ,1);
472  DomIntRange _domintrange_sub1(SRT_SUB,1);
473  DomIntRange _domintrange_sup1(SRT_SUP,1);
474  DomIntRange _domintrange_disj1(SRT_DISJ,1);
475  DomIntRange _domintrange_cmpl1(SRT_CMPL,1);
476  DomIntRange _domintrange_eq2(SRT_EQ,2);
477  DomIntRange _domintrange_lq2(SRT_LQ,2);
478  DomIntRange _domintrange_le2(SRT_LE,2);
479  DomIntRange _domintrange_gq2(SRT_GQ,2);
480  DomIntRange _domintrange_gr2(SRT_GR,2);
481  DomIntRange _domintrange_nq2(SRT_NQ,2);
482  DomIntRange _domintrange_sub2(SRT_SUB,2);
483  DomIntRange _domintrange_sup2(SRT_SUP,2);
484  DomIntRange _domintrange_disj2(SRT_DISJ,2);
485  DomIntRange _domintrange_cmpl2(SRT_CMPL,2);
486 
487  DomInt _domint_eq1(SRT_EQ,1);
488  DomInt _domint_lq1(SRT_LQ,1);
489  DomInt _domint_le1(SRT_LE,1);
490  DomInt _domint_gq1(SRT_GQ,1);
491  DomInt _domint_gr1(SRT_GR,1);
492  DomInt _domint_nq1(SRT_NQ,1);
493  DomInt _domint_sub1(SRT_SUB,1);
494  DomInt _domint_sup1(SRT_SUP,1);
495  DomInt _domint_disj1(SRT_DISJ,1);
496  DomInt _domint_cmpl1(SRT_CMPL,1);
497  DomInt _domint_eq2(SRT_EQ,2);
498  DomInt _domint_lq2(SRT_LQ,2);
499  DomInt _domint_le2(SRT_LE,2);
500  DomInt _domint_gq2(SRT_GQ,2);
501  DomInt _domint_gr2(SRT_GR,2);
502  DomInt _domint_nq2(SRT_NQ,2);
503  DomInt _domint_sub2(SRT_SUB,2);
504  DomInt _domint_sup2(SRT_SUP,2);
505  DomInt _domint_disj2(SRT_DISJ,2);
506  DomInt _domint_cmpl2(SRT_CMPL,2);
507 
508  DomDom _domdom_eq1(SRT_EQ,1);
509  DomDom _domdom_lq1(SRT_LQ,1);
510  DomDom _domdom_le1(SRT_LE,1);
511  DomDom _domdom_gq1(SRT_GQ,1);
512  DomDom _domdom_gr1(SRT_GR,1);
513  DomDom _domdom_nq1(SRT_NQ,1);
514  DomDom _domdom_sub1(SRT_SUB,1);
515  DomDom _domdom_sup1(SRT_SUP,1);
516  DomDom _domdom_disj1(SRT_DISJ,1);
517  DomDom _domdom_cmpl1(SRT_CMPL,1);
518  DomDom _domdom_eq2(SRT_EQ,2);
519  DomDom _domdom_lq2(SRT_LQ,2);
520  DomDom _domdom_le2(SRT_LE,2);
521  DomDom _domdom_gq2(SRT_GQ,2);
522  DomDom _domdom_gr2(SRT_GR,2);
523  DomDom _domdom_nq2(SRT_NQ,2);
524  DomDom _domdom_sub2(SRT_SUB,2);
525  DomDom _domdom_sup2(SRT_SUP,2);
526  DomDom _domdom_disj2(SRT_DISJ,2);
527  DomDom _domdom_cmpl2(SRT_CMPL,2);
528 
529  CardRange _cr1(1);
530  CardRange _cr2(2);
531 
532 }}}
533 
534 // STATISTICS: test-set