Generated on Sat Jul 29 2017 12:41:24 for Gecode by doxygen 1.8.13
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: 2017-03-10 10:15:56 +0100 (Fri, 10 Mar 2017) $ by $Author: schulte $
11  * $Revision: 15566 $
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,true,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  }
86  virtual void post(Space& home, SetVarArray& x, IntVarArray& y,
87  Reify r) {
88  Gecode::cardinality(home, x[0], y[0], r);
89  }
90  };
91  Card _card("Int::Card");
92 
94  class Min : public SetTest {
95  public:
97  Min(const char* t)
98  : SetTest(t,1,ds_33,true,1) {}
100  virtual bool solution(const SetAssignment& x) const {
101  CountableSetRanges xr0(x.lub, x[0]);
102  return xr0() && xr0.min()==x.intval();
103  }
105  virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
106  Gecode::min(home, x[0], y[0]);
107  }
109  virtual void post(Space& home, SetVarArray& x, IntVarArray& y,
110  Reify r) {
111  Gecode::min(home, x[0], y[0], r);
112  }
113  };
114  Min _min("Int::Min");
115 
117  class NotMin : public SetTest {
118  public:
120  NotMin(const char* t)
121  : SetTest(t,1,ds_33,false,1) {}
123  virtual bool solution(const SetAssignment& x) const {
124  CountableSetRanges xr0(x.lub, x[0]);
125  return !(xr0() && xr0.min()==x.intval());
126  }
128  virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
129  Gecode::notMin(home, x[0], y[0]);
130  }
131  };
132  NotMin _notmin("Int::NotMin");
133 
135  class Max : public SetTest {
136  public:
138  Max(const char* t)
139  : SetTest(t,1,ds_33,true,1) {}
141  virtual bool solution(const SetAssignment& x) const {
142  CountableSetRanges xr0(x.lub, x[0]);
143  IntSet x0(xr0);
144  return x0.ranges() > 0 && x0.max()==x.intval();
145  }
147  virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
148  Gecode::max(home, x[0], y[0]);
149  }
151  virtual void post(Space& home, SetVarArray& x, IntVarArray& y,
152  Reify r) {
153  Gecode::max(home, x[0], y[0], r);
154  }
155  };
156  Max _max("Int::Max");
157 
159  class NotMax : public SetTest {
160  public:
162  NotMax(const char* t)
163  : SetTest(t,1,ds_33,false,1) {}
165  virtual bool solution(const SetAssignment& x) const {
166  CountableSetRanges xr0(x.lub, x[0]);
167  IntSet x0(xr0);
168  return !(x0.ranges() > 0 && x0.max()==x.intval());
169  }
171  virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
172  Gecode::notMax(home, x[0], y[0]);
173  }
174  };
175  NotMax _notmax("Int::NotMax");
176 
178  class Elem : public SetTest {
179  public:
181  Elem(const char* t)
182  : SetTest(t,1,ds_33,true,1) {}
184  virtual bool solution(const SetAssignment& x) const {
185  for (CountableSetValues xr(x.lub, x[0]);xr();++xr)
186  if (xr.val()==x.intval())
187  return true;
188  return false;
189  }
191  virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
192  Gecode::rel(home, x[0], SRT_SUP, y[0]);
193  }
195  virtual void post(Space& home, SetVarArray& x, IntVarArray& y,
196  Reify r) {
197  Gecode::rel(home, x[0], SRT_SUP, y[0], r);
198  }
199  };
200  Elem _elem("Int::Elem");
201 
203  class NoElem : public SetTest {
204  public:
206  NoElem(const char* t)
207  : SetTest(t,1,ds_33,false,1) {}
209  virtual bool solution(const SetAssignment& x) const {
210  for (CountableSetValues xr(x.lub, x[0]);xr();++xr)
211  if (xr.val()==x.intval())
212  return false;
213  return true;
214  }
216  virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
217  Gecode::rel(home, x[0], SRT_DISJ, y[0]);
218  }
219  };
220  NoElem _noelem("Int::NoElem");
221 
223  class Rel : public SetTest {
224  private:
226  Gecode::SetRelType srt;
228  bool swapped;
229  public:
231  Rel(Gecode::SetRelType srt0, bool s)
232  : SetTest("Int::Rel::"+str(srt0)+(s ? "::s" : ""),
233  1,ds_33,true,1),
234  srt(srt0), swapped(s) {}
236  virtual bool solution(const SetAssignment& x) const {
237  CountableSetRanges xr(x.lub, x[0]);
238  IntSet is(x.intval(), x.intval());
239  IntSetRanges dr(is);
240  Gecode::SetRelType rsrt = srt;
241  if (swapped) {
242  switch (srt) {
243  case SRT_SUB: rsrt = SRT_SUP; break;
244  case SRT_SUP: rsrt = SRT_SUB; break;
245  default: break;
246  }
247  }
248  switch (rsrt) {
249  case SRT_EQ: return Iter::Ranges::equal(xr, dr);
250  case SRT_NQ: return !Iter::Ranges::equal(xr, dr);
251  case SRT_SUB: return Iter::Ranges::subset(xr, dr);
252  case SRT_SUP: return Iter::Ranges::subset(dr, xr);
253  case SRT_DISJ:
254  {
256  inter(xr, dr);
257  return !inter();
258  }
259  case SRT_CMPL:
260  {
262  return Iter::Ranges::equal(xr,drc);
263  }
264  }
265  GECODE_NEVER;
266  return false;
267  }
269  virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
270  if (!swapped)
271  Gecode::rel(home, x[0], srt, y[0]);
272  else
273  Gecode::rel(home, y[0], srt, x[0]);
274  }
276  virtual void post(Space& home, SetVarArray& x, IntVarArray& y,
277  Reify r) {
278  if (!swapped)
279  Gecode::rel(home, x[0], srt, y[0], r);
280  else
281  Gecode::rel(home, y[0], srt, x[0], r);
282  }
283  };
284  Rel _rel_eq(Gecode::SRT_EQ,false);
285  Rel _rel_nq(Gecode::SRT_NQ,false);
296 
298  class IntRel : public SetTest {
299  private:
301  Gecode::IntRelType irt;
303  bool swapped;
304  public:
307  : SetTest("Int::IntRel::"+Test::Int::Test::str(irt0)+
308  (s ? "::s" : ""),1,ds_33,true,1),
309  irt(irt0), swapped(s) {
310  testsubsumed = false;
311  }
313  virtual bool solution(const SetAssignment& x) const {
314  CountableSetValues xr(x.lub, x[0]);
315  if (!xr())
316  return false;
317  for (; xr(); ++xr)
318  switch (irt) {
319  case Gecode::IRT_EQ:
320  if (xr.val() != x.intval()) return false;
321  break;
322  case Gecode::IRT_NQ:
323  if (xr.val() == x.intval()) return false;
324  break;
325  case Gecode::IRT_GR:
326  if (!swapped && xr.val() <= x.intval()) return false;
327  if (swapped && xr.val() >= x.intval()) return false;
328  break;
329  case Gecode::IRT_GQ:
330  if (!swapped && xr.val() < x.intval()) return false;
331  if (swapped && xr.val() > x.intval()) return false;
332  break;
333  case Gecode::IRT_LE:
334  if (!swapped && xr.val() >= x.intval()) return false;
335  if (swapped && xr.val() <= x.intval()) return false;
336  break;
337  case Gecode::IRT_LQ:
338  if (!swapped && xr.val() > x.intval()) return false;
339  if (swapped && xr.val() < x.intval()) return false;
340  break;
341  default:
342  GECODE_NEVER;
343  return false;
344  }
345  return true;
346  }
348  virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
349  if (!swapped)
350  Gecode::rel(home, x[0], irt, y[0]);
351  else
352  Gecode::rel(home, y[0], irt, x[0]);
353  }
355  virtual void post(Space& home, SetVarArray& x, IntVarArray& y,
356  Reify r) {
357  if (!swapped)
358  Gecode::rel(home, x[0], irt, y[0], r);
359  else
360  Gecode::rel(home, y[0], irt, x[0], r);
361  }
362  };
375 
376 
377  template<class I>
378  int weightI(const IntArgs& elements,
379  const IntArgs& weights,
380  I& iter) {
381  int sum = 0;
382  int i = 0;
383  for (Iter::Ranges::ToValues<I> v(iter); v(); ++v) {
384  // Skip all elements below the current
385  while (elements[i]<v.val()) i++;
386  assert(elements[i] == v.val());
387  sum += weights[i];
388  }
389  return sum;
390  }
391 
393  class Weights : public SetTest {
394  public:
400  Weights(const char* t, IntArgs& el, IntArgs& w,
401  int min = -10000, int max = 10000)
402  : SetTest(t,1,ds_33,false,1),
403  elements(el), weights(w), minWeight(min), maxWeight(max) {}
405  virtual bool solution(const SetAssignment& x) const {
406  CountableSetRanges x0(x.lub, x[0]);
407  return x.intval()==weightI(elements,weights,x0) &&
408  x.intval() >= minWeight && x.intval() <= maxWeight;
409  }
411  virtual void post(Space& home, SetVarArray& x, IntVarArray& y) {
412  Gecode::rel(home, minWeight <= y[0]);
413  Gecode::rel(home, maxWeight >= y[0]);
414  Gecode::weights(home, elements, weights, x[0], y[0]);
415  }
416  };
417 
418  const int el1v[] = {-3,-2,-1,0,1,2,3};
419  IntArgs el1(7,el1v);
420  const int w1v[] = {1,-2,1,1,1,6,1};
421  IntArgs w1(7,w1v);
422  Weights _weights1("Int::Weights::1", el1, w1);
423 
424  const int w2v[] = {-1,-1,-1,10,-1,-1,-1};
425  IntArgs w2(7,w2v);
426  Weights _weights2("Int::Weights::2", el1, w2);
427  Weights _weights3("Int::Weights::3", el1, w2, 3);
428 
429  const int w4v[] = {1,1,0,0,0,0,0};
430  IntArgs w4(7,w4v);
431  Weights _weights4("Int::Weights::4", el1, w4);
432 
433 }}}
434 
435 // STATISTICS: test-set
Rel _rel_sub(Gecode::SRT_SUB, false)
const int w1v[]
Definition: int.cpp:420
Rel _rel_sups(Gecode::SRT_SUP, true)
Rel _rel_nq(Gecode::SRT_NQ, false)
virtual void post(Space &home, SetVarArray &x, IntVarArray &y)
Post constraint on x.
Definition: int.cpp:105
NotMax(const char *t)
Create and register test.
Definition: int.cpp:162
virtual void post(Space &home, SetVarArray &x, IntVarArray &y, Reify r)
Post reified constraint on x for r.
Definition: int.cpp:355
Elem _elem("Int::Elem")
NodeType t
Type of node.
Definition: bool-expr.cpp:234
SetRelType
Common relation types for sets.
Definition: set.hh:645
void notMin(Home home, SetVar s, IntVar x)
Definition: int.cpp:239
Weights(const char *t, IntArgs &el, IntArgs &w, int min=-10000, int max=10000)
Create and register test.
Definition: int.cpp:400
Rel _rel_eqs(Gecode::SRT_EQ, true)
virtual void post(Space &home, SetVarArray &x, IntVarArray &y, Reify r)
Post reified constraint on x.
Definition: int.cpp:86
virtual void post(Space &home, SetVarArray &x, IntVarArray &y)
Post constraint on x.
Definition: int.cpp:171
Range iterator for integer sets.
Definition: int.hh:274
virtual bool solution(const SetAssignment &x) const
Test whether x is solution
Definition: int.cpp:74
Max(const char *t)
Create and register test.
Definition: int.cpp:138
Elem(const char *t)
Create and register test.
Definition: int.cpp:181
virtual bool solution(const SetAssignment &x) const
Test whether x is solution
Definition: int.cpp:209
IntArgs w1(7, w1v)
IntRel _intrel_nq(Gecode::IRT_NQ, false)
virtual bool solution(const SetAssignment &x) const
Test whether x is solution
Definition: int.cpp:313
Test for integer relation constraint
Definition: int.cpp:298
IntRel _intrel_eq(Gecode::IRT_EQ, false)
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:53
virtual void post(Space &home, SetVarArray &x, IntVarArray &y)
Post constraint on x.
Definition: int.cpp:147
Less or equal ( )
Definition: int.hh:909
int weightI(const IntArgs &elements, const IntArgs &weights, I &iter)
Definition: int.cpp:378
IntRel(Gecode::IntRelType irt0, bool s)
Create and register test.
Definition: int.cpp:306
Test for set weight constraint
Definition: int.cpp:393
bool equal(I &i, J &j)
Check whether range iterators i and j are equal.
virtual void post(Space &home, SetVarArray &x, IntVarArray &y)
Post constraint on x.
Definition: int.cpp:411
Test for negated maximal element constraint
Definition: int.cpp:159
Rel(Gecode::SetRelType srt0, bool s)
Create and register test.
Definition: int.cpp:231
Integer variable array.
Definition: int.hh:744
IntRel _intrel_lqs(Gecode::IRT_LQ, true)
IntArgs w2(7, w2v)
virtual void post(Space &home, SetVarArray &x, IntVarArray &y, Reify r)
Post reified constraint on x for b.
Definition: int.cpp:195
Card(const char *t)
Create and register test.
Definition: int.cpp:71
Rel _rel_cmpl(Gecode::SRT_CMPL, false)
virtual bool solution(const SetAssignment &x) const
Test whether x is solution
Definition: int.cpp:165
Greater ( )
Definition: int.hh:912
Superset ( )
Definition: set.hh:649
NoElem _noelem("Int::NoElem")
virtual void post(Space &home, SetVarArray &x, IntVarArray &y, Reify r)
Post reified constraint on x.
Definition: int.cpp:151
Complement.
Definition: set.hh:651
IntRel _intrel_eqs(Gecode::IRT_EQ, true)
Computation spaces.
Definition: core.hpp:1748
Greater or equal ( )
Definition: int.hh:911
IntRel _intrel_gr(Gecode::IRT_GR, false)
NotMax _notmax("Int::NotMax")
virtual void post(Space &home, SetVarArray &x, IntVarArray &y)
Post constraint on x.
Definition: int.cpp:216
Min _min("Int::Min")
virtual bool solution(const SetAssignment &x) const
Test whether x is solution
Definition: int.cpp:184
IntRel _intrel_gqs(Gecode::IRT_GQ, true)
virtual bool solution(const SetAssignment &x) const
Test whether x is solution
Definition: int.cpp:236
Test for maximal element constraint
Definition: int.cpp:135
Gecode::IntArgs i(4, 1, 2, 3, 4)
Equality ( )
Definition: int.hh:907
Max _max("Int::Max")
IntRelType
Relation types for integers.
Definition: int.hh:906
Range iterator for computing intersection (binary)
IntArgs w4(7, w4v)
virtual bool solution(const SetAssignment &x) const
Test whether x is solution
Definition: int.cpp:100
Rel _rel_eq(Gecode::SRT_EQ, false)
int max(int i) const
Return maximum of range at position i.
Definition: int-set-1.hpp:121
virtual bool solution(const SetAssignment &x) const
Test whether x is solution
Definition: int.cpp:405
NotMin _notmin("Int::NotMin")
A complement iterator spezialized for the BndSet limits.
Definition: var-imp.hpp:296
Rel _rel_disjs(Gecode::SRT_DISJ, true)
Rel _rel_disj(Gecode::SRT_DISJ, false)
IntRel _intrel_le(Gecode::IRT_LE, false)
Weights _weights3("Int::Weights::3", el1, w2, 3)
Value iterator from range iterator.
Reification specification.
Definition: int.hh:857
Rel _rel_subs(Gecode::SRT_SUB, true)
IntRel _intrel_grs(Gecode::IRT_GR, true)
Card _card("Int::Card")
Subset ( )
Definition: set.hh:648
IntRel _intrel_lq(Gecode::IRT_LQ, false)
virtual void post(Space &home, SetVarArray &x, IntVarArray &y)
Post constraint on x.
Definition: int.cpp:82
Gecode::IntSet lub
The common superset for all domains.
Definition: set.hh:170
NoElem(const char *t)
Create and register test.
Definition: int.cpp:206
Less ( )
Definition: int.hh:910
Integer sets.
Definition: int.hh:174
IntArgs el1(7, el1v)
Rel _rel_sup(Gecode::SRT_SUP, false)
virtual bool solution(const SetAssignment &x) const
Test whether x is solution
Definition: int.cpp:123
Value iterator producing subsets of an IntSet.
Definition: set.hh:76
Passing integer arguments.
Definition: int.hh:610
const int w4v[]
Definition: int.cpp:429
virtual void post(Space &home, SetVarArray &x, IntVarArray &y)
Post constraint on x.
Definition: int.cpp:128
Rel _rel_cmpls(Gecode::SRT_CMPL, true)
Weights _weights1("Int::Weights::1", el1, w1)
LinIntExpr cardinality(const SetExpr &e)
Cardinality of set expression.
Definition: set-expr.cpp:818
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:784
SetExpr inter(const SetVarArgs &x)
Intersection of set variables.
Definition: set-expr.cpp:699
const int v[7]
Definition: distinct.cpp:263
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:71
virtual bool solution(const SetAssignment &x) const
Test whether x is solution
Definition: int.cpp:141
General test support.
Definition: afc.cpp:43
int val(void) const
Return current value.
Definition: set.hh:110
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:784
IntRel _intrel_nqs(Gecode::IRT_NQ, true)
Min(const char *t)
Create and register test.
Definition: int.cpp:97
Base class for tests with set constraints
Definition: set.hh:289
Generate all set assignments.
Definition: set.hh:158
Weights _weights4("Int::Weights::4", el1, w4)
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Definition: rel.cpp:47
Test for negated minimal element constraint
Definition: int.cpp:117
const int el1v[]
Definition: int.cpp:418
Range iterator producing subsets of an IntSet.
Definition: set.hh:114
IntRel _intrel_les(Gecode::IRT_LE, true)
Equality ( )
Definition: set.hh:646
Disjoint ( )
Definition: set.hh:650
void notMax(Home home, SetVar s, IntVar x)
Definition: int.cpp:271
Post propagator for SetVar x
Definition: set.hh:784
IntRel _intrel_gq(Gecode::IRT_GQ, false)
int ranges(void) const
Return number of ranges of the specification.
Definition: int-set-1.hpp:134
bool subset(I &i, J &j)
Check whether range iterator i is subset of range iterator j.
Set variable array
Definition: set.hh:572
Disequality ( )
Definition: set.hh:647
Test for negated element constraint
Definition: int.cpp:203
Gecode toplevel namespace
LinFloatExpr sum(const FloatVarArgs &x)
Construct linear float expression as sum of float variables.
Definition: float-expr.cpp:548
virtual void post(Space &home, SetVarArray &x, IntVarArray &y, Reify r)
Post reified constraint on x for r.
Definition: int.cpp:276
void weights(Home home, IntSharedArray elements, IntSharedArray weights, SetVar x, IntVar y)
Definition: int.cpp:296
Test for minimal element constraint
Definition: int.cpp:94
virtual void post(Space &home, SetVarArray &x, IntVarArray &y)
Post constraint on x.
Definition: int.cpp:269
Disequality ( )
Definition: int.hh:908
virtual void post(Space &home, SetVarArray &x, IntVarArray &y)
Post constraint on x.
Definition: int.cpp:191
int min(void) const
Return smallest value of range.
Rel _rel_nqs(Gecode::SRT_NQ, true)
virtual void post(Space &home, SetVarArray &x, IntVarArray &y, Reify r)
Post reified constraint on x.
Definition: int.cpp:109
Test for cardinality constraint
Definition: int.cpp:68
virtual void post(Space &home, SetVarArray &x, IntVarArray &y)
Post constraint on x.
Definition: int.cpp:348
NotMin(const char *t)
Create and register test.
Definition: int.cpp:120
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:60
Test for relation constraint
Definition: int.cpp:223
int intval(void) const
Return value for first integer variable.
Definition: set.hh:185
Test for element constraint
Definition: int.cpp:178
const int w2v[]
Definition: int.cpp:424
Weights _weights2("Int::Weights::2", el1, w2)