Generated on Sat Nov 9 2013 19:18:29 for Gecode by doxygen 1.8.4
int.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-10-19 05:58:26 +0200 (Fri, 19 Oct 2012) $ by $Author: tack $
11  * $Revision: 13156 $
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 #include "test/int.hh"
40 #include <gecode/minimodel.hh>
41 
42 using namespace Gecode;
43 
44 namespace Test { namespace Set {
45 
47  namespace Int {
48 
54 
55  static const int d1r[4][2] = {
56  {-4,-3},{-1,-1},{1,1},{3,5}
57  };
58  static IntSet d1(d1r,4);
59 
60  static IntSet d2(-1,3);
61  static IntSet d3(0,3);
62 
63  static IntSet d4(0,4);
64 
65  static IntSet ds_33(-3,3);
66 
68  class Card : public SetTest {
69  public:
71  Card(const char* t)
72  : SetTest(t,1,ds_33,false,1) {}
74  virtual bool solution(const SetAssignment& x) const {
75  unsigned int s = 0;
76  for (CountableSetRanges xr(x.lub, x[0]);xr();++xr) s+= xr.width();
77  if (x.intval() < 0)
78  return false;
79  return s==(unsigned int)x.intval();
80  }
82  virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
83  Gecode::cardinality(home, x[0], y[0]);
84  }
85  };
86  Card _card("Int::Card");
87 
89  class Min : public SetTest {
90  public:
92  Min(const char* t)
93  : SetTest(t,1,ds_33,true,1) {}
95  virtual bool solution(const SetAssignment& x) const {
96  CountableSetRanges xr0(x.lub, x[0]);
97  return xr0() && xr0.min()==x.intval();
98  }
100  virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
101  Gecode::min(home, x[0], y[0]);
102  }
104  virtual void post(Space& home, SetVarArray& x, IntVarArray& y,
105  Reify r) {
106  Gecode::min(home, x[0], y[0], r);
107  }
108  };
109  Min _min("Int::Min");
110 
112  class NotMin : public SetTest {
113  public:
115  NotMin(const char* t)
116  : SetTest(t,1,ds_33,false,1) {}
118  virtual bool solution(const SetAssignment& x) const {
119  CountableSetRanges xr0(x.lub, x[0]);
120  return !(xr0() && xr0.min()==x.intval());
121  }
123  virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
124  Gecode::notMin(home, x[0], y[0]);
125  }
126  };
127  NotMin _notmin("Int::NotMin");
128 
130  class Max : public SetTest {
131  public:
133  Max(const char* t)
134  : SetTest(t,1,ds_33,true,1) {}
136  virtual bool solution(const SetAssignment& x) const {
137  CountableSetRanges xr0(x.lub, x[0]);
138  IntSet x0(xr0);
139  return x0.ranges() > 0 && x0.max()==x.intval();
140  }
142  virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
143  Gecode::max(home, x[0], y[0]);
144  }
146  virtual void post(Space& home, SetVarArray& x, IntVarArray& y,
147  Reify r) {
148  Gecode::max(home, x[0], y[0], r);
149  }
150  };
151  Max _max("Int::Max");
152 
154  class NotMax : public SetTest {
155  public:
157  NotMax(const char* t)
158  : SetTest(t,1,ds_33,false,1) {}
160  virtual bool solution(const SetAssignment& x) const {
161  CountableSetRanges xr0(x.lub, x[0]);
162  IntSet x0(xr0);
163  return !(x0.ranges() > 0 && x0.max()==x.intval());
164  }
166  virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
167  Gecode::notMax(home, x[0], y[0]);
168  }
169  };
170  NotMax _notmax("Int::NotMax");
171 
173  class Elem : public SetTest {
174  public:
176  Elem(const char* t)
177  : SetTest(t,1,ds_33,true,1) {}
179  virtual bool solution(const SetAssignment& x) const {
180  for (CountableSetValues xr(x.lub, x[0]);xr();++xr)
181  if (xr.val()==x.intval())
182  return true;
183  return false;
184  }
186  virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
187  Gecode::rel(home, x[0], SRT_SUP, y[0]);
188  }
190  virtual void post(Space& home, SetVarArray& x, IntVarArray& y,
191  Reify r) {
192  Gecode::rel(home, x[0], SRT_SUP, y[0], r);
193  }
194  };
195  Elem _elem("Int::Elem");
196 
198  class NoElem : public SetTest {
199  public:
201  NoElem(const char* t)
202  : SetTest(t,1,ds_33,false,1) {}
204  virtual bool solution(const SetAssignment& x) const {
205  for (CountableSetValues xr(x.lub, x[0]);xr();++xr)
206  if (xr.val()==x.intval())
207  return false;
208  return true;
209  }
211  virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
212  Gecode::rel(home, x[0], SRT_DISJ, y[0]);
213  }
214  };
215  NoElem _noelem("Int::NoElem");
216 
218  class Rel : public SetTest {
219  private:
220  Gecode::SetRelType srt;
221  bool inverse;
222  public:
224  Rel(Gecode::SetRelType srt0, bool inverse0)
225  : SetTest("Int::Rel::"+str(srt0)+(inverse0 ? "::i" : ""),
226  1,ds_33,true,1)
227  , srt(srt0)
228  , inverse(inverse0) {}
230  virtual bool solution(const SetAssignment& x) const {
231  CountableSetRanges xr(x.lub, x[0]);
232  IntSet is(x.intval(), x.intval());
233  IntSetRanges dr(is);
234  Gecode::SetRelType rsrt = srt;
235  if (inverse) {
236  switch (srt) {
237  case SRT_SUB: rsrt = SRT_SUP; break;
238  case SRT_SUP: rsrt = SRT_SUB; break;
239  default: break;
240  }
241  }
242  switch (rsrt) {
243  case SRT_EQ: return Iter::Ranges::equal(xr, dr);
244  case SRT_NQ: return !Iter::Ranges::equal(xr, dr);
245  case SRT_SUB: return Iter::Ranges::subset(xr, dr);
246  case SRT_SUP: return Iter::Ranges::subset(dr, xr);
247  case SRT_DISJ:
248  {
250  inter(xr, dr);
251  return !inter();
252  }
253  case SRT_CMPL:
254  {
256  return Iter::Ranges::equal(xr,drc);
257  }
258  }
259  GECODE_NEVER;
260  return false;
261  }
263  virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
264  if (!inverse)
265  Gecode::rel(home, x[0], srt, y[0]);
266  else
267  Gecode::rel(home, y[0], srt, x[0]);
268  }
270  virtual void post(Space& home, SetVarArray& x, IntVarArray& y,
271  Reify r) {
272  if (!inverse)
273  Gecode::rel(home, x[0], srt, y[0], r);
274  else
275  Gecode::rel(home, y[0], srt, x[0], r);
276  }
277  };
278  Rel _rel_eq(Gecode::SRT_EQ,false);
279  Rel _rel_nq(Gecode::SRT_NQ,false);
280  Rel _rel_sub(Gecode::SRT_SUB,false);
281  Rel _rel_sup(Gecode::SRT_SUP,false);
282  Rel _rel_disj(Gecode::SRT_DISJ,false);
283  Rel _rel_cmpl(Gecode::SRT_CMPL,false);
284  Rel _rel_eqi(Gecode::SRT_EQ,true);
285  Rel _rel_nqi(Gecode::SRT_NQ,true);
286  Rel _rel_subi(Gecode::SRT_SUB,true);
287  Rel _rel_supi(Gecode::SRT_SUP,true);
288  Rel _rel_disji(Gecode::SRT_DISJ,true);
289  Rel _rel_cmpli(Gecode::SRT_CMPL,true);
290 
292  class IntRel : public SetTest {
293  private:
294  Gecode::IntRelType irt;
295  bool inverse;
296  public:
298  IntRel(Gecode::IntRelType irt0, bool inverse0)
299  : SetTest("Int::IntRel::"+Test::Int::Test::str(irt0)+
300  (inverse0 ? "::i" : ""),1,ds_33,false,1)
301  , irt(irt0)
302  , inverse(inverse0) {}
304  virtual bool solution(const SetAssignment& x) const {
305  CountableSetValues xr(x.lub, x[0]);
306  if (!xr())
307  return false;
308  for (; xr(); ++xr) {
309  switch (irt) {
310  case Gecode::IRT_EQ:
311  if (xr.val() != x.intval()) return false;
312  break;
313  case Gecode::IRT_NQ:
314  if (xr.val() == x.intval()) return false;
315  break;
316  case Gecode::IRT_GR:
317  if (!inverse && xr.val() <= x.intval()) return false;
318  if (inverse && xr.val() >= x.intval()) return false;
319  break;
320  case Gecode::IRT_GQ:
321  if (!inverse && xr.val() < x.intval()) return false;
322  if (inverse && xr.val() > x.intval()) return false;
323  break;
324  case Gecode::IRT_LE:
325  if (!inverse && xr.val() >= x.intval()) return false;
326  if (inverse && xr.val() <= x.intval()) return false;
327  break;
328  case Gecode::IRT_LQ:
329  if (!inverse && xr.val() > x.intval()) return false;
330  if (inverse && xr.val() < x.intval()) return false;
331  break;
332  default:
333  GECODE_NEVER;
334  return false;
335  }
336  }
337  return true;
338  }
340  virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
341  if (!inverse)
342  Gecode::rel(home, x[0], irt, y[0]);
343  else
344  Gecode::rel(home, y[0], irt, x[0]);
345  }
346  };
347  IntRel _intrel_eq(Gecode::IRT_EQ,false);
348  IntRel _intrel_nq(Gecode::IRT_NQ,false);
349  IntRel _intrel_gr(Gecode::IRT_GR,false);
350  IntRel _intrel_gq(Gecode::IRT_GQ,false);
351  IntRel _intrel_le(Gecode::IRT_LE,false);
352  IntRel _intrel_lq(Gecode::IRT_LQ,false);
353  IntRel _intrel_eqi(Gecode::IRT_EQ,true);
354  IntRel _intrel_nqi(Gecode::IRT_NQ,true);
355  IntRel _intrel_gri(Gecode::IRT_GR,true);
356  IntRel _intrel_gqi(Gecode::IRT_GQ,true);
357  IntRel _intrel_lei(Gecode::IRT_LE,true);
358  IntRel _intrel_lqi(Gecode::IRT_LQ,true);
359 
360 
361  template<class I>
362  int weightI(const IntArgs& elements,
363  const IntArgs& weights,
364  I& iter) {
365  int sum = 0;
366  int i = 0;
367  for (Iter::Ranges::ToValues<I> v(iter); v(); ++v) {
368  // Skip all elements below the current
369  while (elements[i]<v.val()) i++;
370  assert(elements[i] == v.val());
371  sum += weights[i];
372  }
373  return sum;
374  }
375 
377  class Weights : public SetTest {
378  public:
384  Weights(const char* t, IntArgs& el, IntArgs& w,
385  int min = -10000, int max = 10000)
386  : SetTest(t,1,ds_33,false,1),
387  elements(el), weights(w), minWeight(min), maxWeight(max) {}
389  virtual bool solution(const SetAssignment& x) const {
390  CountableSetRanges x0(x.lub, x[0]);
391  return x.intval()==weightI(elements,weights,x0) &&
392  x.intval() >= minWeight && x.intval() <= maxWeight;
393  }
395  virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
396  Gecode::rel(home, minWeight <= y[0]);
397  Gecode::rel(home, maxWeight >= y[0]);
398  Gecode::weights(home, elements, weights, x[0], y[0]);
399  }
400  };
401 
402  const int el1v[] = {-3,-2,-1,0,1,2,3};
403  IntArgs el1(7,el1v);
404  const int w1v[] = {1,-2,1,1,1,6,1};
405  IntArgs w1(7,w1v);
406  Weights _weights1("Int::Weights::1", el1, w1);
407 
408  const int w2v[] = {-1,-1,-1,10,-1,-1,-1};
409  IntArgs w2(7,w2v);
410  Weights _weights2("Int::Weights::2", el1, w2);
411  Weights _weights3("Int::Weights::3", el1, w2, 3);
412 
413  const int w4v[] = {1,1,0,0,0,0,0};
414  IntArgs w4(7,w4v);
415  Weights _weights4("Int::Weights::4", el1, w4);
416 
417 }}}
418 
419 // STATISTICS: test-set