Generated on Mon Aug 27 2012 17:15:45 for Gecode by doxygen 1.8.1.2
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: 2011-02-22 20:26:48 +1100 (Tue, 22 Feb 2011) $ by $Author: tack $
11  * $Revision: 11761 $
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  BoolVar b) {
106  Gecode::min(home, x[0], y[0], b);
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  BoolVar b) {
148  Gecode::max(home, x[0], y[0], b);
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, BoolVar b) {
191  Gecode::rel(home, x[0], SRT_SUP, y[0], b);
192  }
193  };
194  Elem _elem("Int::Elem");
195 
197  class NoElem : public SetTest {
198  public:
200  NoElem(const char* t)
201  : SetTest(t,1,ds_33,false,1) {}
203  virtual bool solution(const SetAssignment& x) const {
204  for (CountableSetValues xr(x.lub, x[0]);xr();++xr)
205  if (xr.val()==x.intval())
206  return false;
207  return true;
208  }
210  virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
211  Gecode::rel(home, x[0], SRT_DISJ, y[0]);
212  }
213  };
214  NoElem _noelem("Int::NoElem");
215 
217  class Rel : public SetTest {
218  private:
219  Gecode::SetRelType srt;
220  bool inverse;
221  public:
223  Rel(Gecode::SetRelType srt0, bool inverse0)
224  : SetTest("Int::Rel::"+str(srt0)+(inverse0 ? "::i" : ""),
225  1,ds_33,true,1)
226  , srt(srt0)
227  , inverse(inverse0) {}
229  virtual bool solution(const SetAssignment& x) const {
230  CountableSetRanges xr(x.lub, x[0]);
231  IntSet is(x.intval(), x.intval());
232  IntSetRanges dr(is);
233  Gecode::SetRelType rsrt = srt;
234  if (inverse) {
235  switch (srt) {
236  case SRT_SUB: rsrt = SRT_SUP; break;
237  case SRT_SUP: rsrt = SRT_SUB; break;
238  default: break;
239  }
240  }
241  switch (rsrt) {
242  case SRT_EQ: return Iter::Ranges::equal(xr, dr);
243  case SRT_NQ: return !Iter::Ranges::equal(xr, dr);
244  case SRT_SUB: return Iter::Ranges::subset(xr, dr);
245  case SRT_SUP: return Iter::Ranges::subset(dr, xr);
246  case SRT_DISJ:
247  {
249  inter(xr, dr);
250  return !inter();
251  }
252  case SRT_CMPL:
253  {
255  return Iter::Ranges::equal(xr,drc);
256  }
257  }
258  GECODE_NEVER;
259  return false;
260  }
262  virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
263  if (!inverse)
264  Gecode::rel(home, x[0], srt, y[0]);
265  else
266  Gecode::rel(home, y[0], srt, x[0]);
267  }
269  virtual void post(Space& home, SetVarArray& x, IntVarArray& y,
270  BoolVar b) {
271  if (!inverse)
272  Gecode::rel(home, x[0], srt, y[0], b);
273  else
274  Gecode::rel(home, y[0], srt, x[0], b);
275  }
276  };
277  Rel _rel_eq(Gecode::SRT_EQ,false);
278  Rel _rel_nq(Gecode::SRT_NQ,false);
279  Rel _rel_sub(Gecode::SRT_SUB,false);
280  Rel _rel_sup(Gecode::SRT_SUP,false);
281  Rel _rel_disj(Gecode::SRT_DISJ,false);
282  Rel _rel_cmpl(Gecode::SRT_CMPL,false);
283  Rel _rel_eqi(Gecode::SRT_EQ,true);
284  Rel _rel_nqi(Gecode::SRT_NQ,true);
285  Rel _rel_subi(Gecode::SRT_SUB,true);
286  Rel _rel_supi(Gecode::SRT_SUP,true);
287  Rel _rel_disji(Gecode::SRT_DISJ,true);
288  Rel _rel_cmpli(Gecode::SRT_CMPL,true);
289 
291  class IntRel : public SetTest {
292  private:
293  Gecode::IntRelType irt;
294  bool inverse;
295  public:
297  IntRel(Gecode::IntRelType irt0, bool inverse0)
298  : SetTest("Int::IntRel::"+Test::Int::Test::str(irt0)+
299  (inverse0 ? "::i" : ""),1,ds_33,false,1)
300  , irt(irt0)
301  , inverse(inverse0) {}
303  virtual bool solution(const SetAssignment& x) const {
304  CountableSetValues xr(x.lub, x[0]);
305  if (!xr())
306  return false;
307  for (; xr(); ++xr) {
308  switch (irt) {
309  case Gecode::IRT_EQ:
310  if (xr.val() != x.intval()) return false;
311  break;
312  case Gecode::IRT_NQ:
313  if (xr.val() == x.intval()) return false;
314  break;
315  case Gecode::IRT_GR:
316  if (!inverse && xr.val() <= x.intval()) return false;
317  if (inverse && xr.val() >= x.intval()) return false;
318  break;
319  case Gecode::IRT_GQ:
320  if (!inverse && xr.val() < x.intval()) return false;
321  if (inverse && xr.val() > x.intval()) return false;
322  break;
323  case Gecode::IRT_LE:
324  if (!inverse && xr.val() >= x.intval()) return false;
325  if (inverse && xr.val() <= x.intval()) return false;
326  break;
327  case Gecode::IRT_LQ:
328  if (!inverse && xr.val() > x.intval()) return false;
329  if (inverse && xr.val() < x.intval()) return false;
330  break;
331  default:
332  GECODE_NEVER;
333  return false;
334  }
335  }
336  return true;
337  }
339  virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
340  if (!inverse)
341  Gecode::rel(home, x[0], irt, y[0]);
342  else
343  Gecode::rel(home, y[0], irt, x[0]);
344  }
345  };
346  IntRel _intrel_eq(Gecode::IRT_EQ,false);
347  IntRel _intrel_nq(Gecode::IRT_NQ,false);
348  IntRel _intrel_gr(Gecode::IRT_GR,false);
349  IntRel _intrel_gq(Gecode::IRT_GQ,false);
350  IntRel _intrel_le(Gecode::IRT_LE,false);
351  IntRel _intrel_lq(Gecode::IRT_LQ,false);
352  IntRel _intrel_eqi(Gecode::IRT_EQ,true);
353  IntRel _intrel_nqi(Gecode::IRT_NQ,true);
354  IntRel _intrel_gri(Gecode::IRT_GR,true);
355  IntRel _intrel_gqi(Gecode::IRT_GQ,true);
356  IntRel _intrel_lei(Gecode::IRT_LE,true);
357  IntRel _intrel_lqi(Gecode::IRT_LQ,true);
358 
359 
360  template<class I>
361  int weightI(const IntArgs& elements,
362  const IntArgs& weights,
363  I& iter) {
364  int sum = 0;
365  int i = 0;
366  for (Iter::Ranges::ToValues<I> v(iter); v(); ++v) {
367  // Skip all elements below the current
368  while (elements[i]<v.val()) i++;
369  assert(elements[i] == v.val());
370  sum += weights[i];
371  }
372  return sum;
373  }
374 
376  class Weights : public SetTest {
377  public:
383  Weights(const char* t, IntArgs& el, IntArgs& w,
384  int min = -10000, int max = 10000)
385  : SetTest(t,1,ds_33,false,1),
386  elements(el), weights(w), minWeight(min), maxWeight(max) {}
388  virtual bool solution(const SetAssignment& x) const {
389  CountableSetRanges x0(x.lub, x[0]);
390  return x.intval()==weightI(elements,weights,x0) &&
391  x.intval() >= minWeight && x.intval() <= maxWeight;
392  }
394  virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
395  Gecode::rel(home, minWeight <= y[0]);
396  Gecode::rel(home, maxWeight >= y[0]);
397  Gecode::weights(home, elements, weights, x[0], y[0]);
398  }
399  };
400 
401  const int el1v[] = {-3,-2,-1,0,1,2,3};
402  IntArgs el1(7,el1v);
403  const int w1v[] = {1,-2,1,1,1,6,1};
404  IntArgs w1(7,w1v);
405  Weights _weights1("Int::Weights::1", el1, w1);
406 
407  const int w2v[] = {-1,-1,-1,10,-1,-1,-1};
408  IntArgs w2(7,w2v);
409  Weights _weights2("Int::Weights::2", el1, w2);
410  Weights _weights3("Int::Weights::3", el1, w2, 3);
411 
412  const int w4v[] = {1,1,0,0,0,0,0};
413  IntArgs w4(7,w4v);
414  Weights _weights4("Int::Weights::4", el1, w4);
415 
417  class Match : public SetTest {
418  public:
420  Match(const char* t)
421  : SetTest(t,1,ds_33,false,3) {}
423  virtual bool solution(const SetAssignment& x) const {
424  if (x.ints()[0]>=x.ints()[1] ||
425  x.ints()[1]>=x.ints()[2])
426  return false;
427  CountableSetValues xr(x.lub, x[0]);
428  if (!xr())
429  return false;
430  if (xr.val() != x.ints()[0])
431  return false;
432  ++xr;
433  if (!xr())
434  return false;
435  if (xr.val() != x.ints()[1])
436  return false;
437  ++xr;
438  if (!xr())
439  return false;
440  if (xr.val() != x.ints()[2])
441  return false;
442  ++xr;
443  if (xr())
444  return false;
445  return true;
446  }
448  virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
449  Gecode::channelSorted(home, y, x[0]);
450  }
451  };
452  Match _match("Int::Match");
453 
455  class ChannelInt : public SetTest {
456  private:
457  int ssize, isize;
458  public:
460  ChannelInt(const char* t, const IntSet& d, int _ssize, int _isize)
461  : SetTest(t,_ssize,d,false,_isize), ssize(_ssize), isize(_isize) {}
463  virtual bool solution(const SetAssignment& x) const {
464  for (int i=0; i<isize; i++) {
465  if (x.ints()[i] < 0 || x.ints()[i] >= ssize)
466  return false;
467  Iter::Ranges::Singleton single(i,i);
468  CountableSetRanges csr(x.lub, x[x.ints()[i]]);
469  if (!Iter::Ranges::subset(single, csr))
470  return false;
471  }
472  for (int i=0; i<ssize; i++) {
473  int size = 0;
474  for (CountableSetValues csv(x.lub, x[i]); csv(); ++csv) {
475  if (csv.val() < 0 || csv.val() >= isize) return false;
476  if (x.ints()[csv.val()] != i) return false;
477  size++;
478  }
479  }
480  return true;
481  }
483  virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
484  Gecode::channel(home, y, x);
485  }
486  };
487 
488  ChannelInt _channelint1("Int::Channel::Int::1", d2, 2, 3);
489  ChannelInt _channelint2("Int::Channel::Int::2", d3, 3, 3);
490 
492  class ChannelBool : public SetTest {
493  private:
494  int isize;
495  public:
497  ChannelBool(const char* t, const IntSet& d, int _isize)
498  : SetTest(t,1,d,false,_isize), isize(_isize) {}
500  virtual bool solution(const SetAssignment& x) const {
501  for (int i=0; i<isize; i++) {
502  if (x.ints()[i] < 0 || x.ints()[i] > 1)
503  return false;
504  }
505  int cur = 0;
506  for (CountableSetValues csv(x.lub, x[0]); csv(); ++csv) {
507  if (csv.val() < 0 || csv.val() >= isize) return false;
508  if (x.ints()[csv.val()] != 1) return false;
509  for (; cur<csv.val(); cur++)
510  if (x.ints()[cur] != 0) return false;
511  cur = csv.val() + 1;
512  }
513  for (; cur<isize; cur++)
514  if (x.ints()[cur] != 0) return false;
515  return true;
516  }
518  virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
519  BoolVarArgs b(y.size());
520  for (int i=y.size(); i--;)
521  b[i] = channel(home, y[i]);
522  Gecode::channel(home, b, x[0]);
523  }
524  };
525 
526  ChannelBool _channelbool1("Int::Channel::Bool::1", d2, 3);
527  ChannelBool _channelbool2("Int::Channel::Bool::2", d3, 3);
528  ChannelBool _channelbool3("Int::Channel::Bool::3", d4, 5);
529 
530 }}}
531 
532 // STATISTICS: test-set