Generated on Sun Aug 26 2012 08:42:52 for Gecode by doxygen 1.8.1.1
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: 2011-08-25 01:04:35 +1000 (Thu, 25 Aug 2011) $ by $Author: tack $
11  * $Revision: 12347 $
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  static IntSet ds_55(-5,5);
72 
73  namespace {
74  static int minSymDiff(const SetAssignment& x, const IntSet& is) {
76  CountableSetRanges xr00(x.lub, x[0]);
77  IntSetRanges xr10(is);
78  DiffA a(xr00,xr10);
80  CountableSetRanges xr01(x.lub, x[0]);
81  IntSetRanges xr11(is);
82  DiffB b(xr11,xr01);
84  return u() ? u.min() : Gecode::Set::Limits::max+1;
85  }
86  template<class I>
87  static bool in(int i, I& c, bool eq=false) {
88  if (eq && i==Gecode::Set::Limits::max+1)
89  return true;
91  return Iter::Ranges::subset(s,c);
92  }
93  }
94 
96  class DomRange : public SetTest {
97  private:
99  IntSet is;
100  public:
103  : SetTest("Dom::Range::"+str(srt0),1,ds_55,true), srt(srt0)
104  , is(srt == Gecode::SRT_CMPL ? ds_33c: ds_33) {}
106  virtual bool solution(const SetAssignment& x) const {
107  CountableSetRanges xr(x.lub, x[0]);
108  IntSetRanges dr(is);
109  switch (srt) {
110  case SRT_EQ: return Iter::Ranges::equal(xr, dr);
111  case SRT_LQ: return (!xr()) || in(minSymDiff(x,is),dr,true);
112  case SRT_LE: return xr() ? in(minSymDiff(x,is),dr) : dr();
113  case SRT_GQ: return (!dr()) || in(minSymDiff(x,is),xr,true);
114  case SRT_GR: return dr() ? in(minSymDiff(x,is),xr) : xr();
115  case SRT_NQ: return !Iter::Ranges::equal(xr, dr);
116  case SRT_SUB: return Iter::Ranges::subset(xr, dr);
117  case SRT_SUP: return Iter::Ranges::subset(dr, xr);
118  case SRT_DISJ:
119  {
121  inter(xr, dr);
122  return !inter();
123  }
124  case SRT_CMPL:
125  {
127  return Iter::Ranges::equal(xr,drc);
128  }
129  }
130  GECODE_NEVER;
131  return false;
132  }
134  virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
135  Gecode::dom(home, x[0], srt, is);
136  }
138  virtual void post(Space& home, SetVarArray& x, IntVarArray&,BoolVar b) {
139  Gecode::dom(home, x[0], srt, is, b);
140  }
141  };
142  DomRange _domrange_eq(SRT_EQ);
143  DomRange _domrange_lq(SRT_LQ);
144  DomRange _domrange_le(SRT_LE);
145  DomRange _domrange_gq(SRT_GQ);
146  DomRange _domrange_gr(SRT_GR);
147  DomRange _domrange_nq(SRT_NQ);
148  DomRange _domrange_sub(SRT_SUB);
149  DomRange _domrange_sup(SRT_SUP);
150  DomRange _domrange_disj(SRT_DISJ);
151  DomRange _domrange_cmpl(SRT_CMPL);
152 
154  class DomIntRange : public SetTest {
155  private:
156  Gecode::SetRelType srt;
157  public:
160  : SetTest("Dom::IntRange::"+str(srt0),1,ds_55,true), srt(srt0) {}
162  virtual bool solution(const SetAssignment& x) const {
163  CountableSetRanges xr(x.lub, x[0]);
164  IntSet is(-3,-1);
165  IntSetRanges dr(is);
166  switch (srt) {
167  case SRT_EQ: return Iter::Ranges::equal(xr, dr);
168  case SRT_LQ: return (!xr()) || in(minSymDiff(x,is),dr,true);
169  case SRT_LE: return xr() ? in(minSymDiff(x,is),dr) : dr();
170  case SRT_GQ: return (!dr()) || in(minSymDiff(x,is),xr,true);
171  case SRT_GR: return dr() ? in(minSymDiff(x,is),xr) : xr();
172  case SRT_NQ: return !Iter::Ranges::equal(xr, dr);
173  case SRT_SUB: return Iter::Ranges::subset(xr, dr);
174  case SRT_SUP: return Iter::Ranges::subset(dr, xr);
175  case SRT_DISJ:
176  {
178  inter(xr, dr);
179  return !inter();
180  }
181  case SRT_CMPL:
182  {
184  return Iter::Ranges::equal(xr,drc);
185  }
186  }
187  GECODE_NEVER;
188  return false;
189  }
191  virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
192  Gecode::dom(home, x[0], srt, -3, -1);
193  }
195  virtual void post(Space& home, SetVarArray& x, IntVarArray&,BoolVar b) {
196  Gecode::dom(home, x[0], srt, -3, -1, b);
197  }
198  };
199  DomIntRange _domintrange_eq(SRT_EQ);
200  DomIntRange _domintrange_lq(SRT_LQ);
201  DomIntRange _domintrange_le(SRT_LE);
202  DomIntRange _domintrange_gq(SRT_GQ);
203  DomIntRange _domintrange_gr(SRT_GR);
204  DomIntRange _domintrange_nq(SRT_NQ);
205  DomIntRange _domintrange_sub(SRT_SUB);
206  DomIntRange _domintrange_sup(SRT_SUP);
207  DomIntRange _domintrange_disj(SRT_DISJ);
208  DomIntRange _domintrange_cmpl(SRT_CMPL);
209 
211  class DomInt : public SetTest {
212  private:
213  Gecode::SetRelType srt;
214  public:
217  : SetTest("Dom::Int::"+str(srt0),1,ds_55,true), srt(srt0) {}
219  virtual bool solution(const SetAssignment& x) const {
220  CountableSetRanges xr(x.lub, x[0]);
221  IntSet is(-3,-3);
222  IntSetRanges dr(is);
223  switch (srt) {
224  case SRT_EQ: return Iter::Ranges::equal(xr, dr);
225  case SRT_LQ: return (!xr()) || in(minSymDiff(x,is),dr,true);
226  case SRT_LE: return xr() ? in(minSymDiff(x,is),dr) : dr();
227  case SRT_GQ: return (!dr()) || in(minSymDiff(x,is),xr,true);
228  case SRT_GR: return dr() ? in(minSymDiff(x,is),xr) : xr();
229  case SRT_NQ: return !Iter::Ranges::equal(xr, dr);
230  case SRT_SUB: return Iter::Ranges::subset(xr, dr);
231  case SRT_SUP: return Iter::Ranges::subset(dr, xr);
232  case SRT_DISJ:
233  {
235  inter(xr, dr);
236  return !inter();
237  }
238  case SRT_CMPL:
239  {
241  return Iter::Ranges::equal(xr,drc);
242  }
243  }
244  GECODE_NEVER;
245  return false;
246  }
248  virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
249  Gecode::dom(home, x[0], srt, -3);
250  }
252  virtual void post(Space& home, SetVarArray& x, IntVarArray&,BoolVar b) {
253  Gecode::dom(home, x[0], srt, -3, b);
254  }
255  };
256  DomInt _domint_eq(SRT_EQ);
257  DomInt _domint_lq(SRT_LQ);
258  DomInt _domint_le(SRT_LE);
259  DomInt _domint_gq(SRT_GQ);
260  DomInt _domint_gr(SRT_GR);
261  DomInt _domint_nq(SRT_NQ);
262  DomInt _domint_sub(SRT_SUB);
263  DomInt _domint_sup(SRT_SUP);
264  DomInt _domint_disj(SRT_DISJ);
265  DomInt _domint_cmpl(SRT_CMPL);
266 
268  class DomDom : public SetTest {
269  private:
270  Gecode::SetRelType srt;
271  Gecode::IntSet is;
272  public:
275  : SetTest("Dom::Dom::"+str(srt0),1,d1,true), srt(srt0)
276  , is(srt == Gecode::SRT_CMPL ? d1c: d1) {}
278  virtual bool solution(const SetAssignment& x) const {
279  CountableSetRanges xr(x.lub, x[0]);
280  IntSetRanges dr(is);
281  switch (srt) {
282  case SRT_EQ: return Iter::Ranges::equal(xr, dr);
283  case SRT_LQ: return (!xr()) || in(minSymDiff(x,is),dr,true);
284  case SRT_LE: return xr() ? in(minSymDiff(x,is),dr) : dr();
285  case SRT_GQ: return (!dr()) || in(minSymDiff(x,is),xr,true);
286  case SRT_GR: return dr() ? in(minSymDiff(x,is),xr) : xr();
287  case SRT_NQ: return !Iter::Ranges::equal(xr, dr);
288  case SRT_SUB: return Iter::Ranges::subset(xr, dr);
289  case SRT_SUP: return Iter::Ranges::subset(dr, xr);
290  case SRT_DISJ:
291  {
293  inter(xr, dr);
294  return !inter();
295  }
296  case SRT_CMPL:
297  {
299  return Iter::Ranges::equal(xr,drc);
300  }
301  }
302  GECODE_NEVER;
303  return false;
304  }
306  virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
307  Gecode::dom(home, x[0], srt, is);
308  }
310  virtual void post(Space& home, SetVarArray& x, IntVarArray&,BoolVar b) {
311  Gecode::dom(home, x[0], srt, is, b);
312  }
313  };
314  DomDom _domdom_eq(SRT_EQ);
315  DomDom _domdom_lq(SRT_LQ);
316  DomDom _domdom_le(SRT_LE);
317  DomDom _domdom_gq(SRT_GQ);
318  DomDom _domdom_gr(SRT_GR);
319  DomDom _domdom_nq(SRT_NQ);
320  DomDom _domdom_sub(SRT_SUB);
321  DomDom _domdom_sup(SRT_SUP);
322  DomDom _domdom_disj(SRT_DISJ);
323  DomDom _domdom_cmpl(SRT_CMPL);
324 
326  class CardRange : public SetTest {
327  public:
329  CardRange(void)
330  : SetTest("Dom::CardRange",1,d1,false) {}
332  virtual bool solution(const SetAssignment& x) const {
333  CountableSetRanges xr(x.lub, x[0]);
334  unsigned int card = Iter::Ranges::size(xr);
335  return card >= 2 && card <= 3;
336  }
338  virtual void post(Space& home, SetVarArray& x, IntVarArray&) {
339  Gecode::cardinality(home, x[0], 2, 3);
340  }
341  };
343 
344 }}}
345 
346 // STATISTICS: test-set