Generated on Sat Feb 7 2015 02:01:16 for Gecode by doxygen 1.8.9.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  * Contributing authors:
7  * Gabor Szokoli <szokoli@gecode.org>
8  *
9  * Copyright:
10  * Guido Tack, 2004, 2005
11  *
12  * Last modified:
13  * $Date: 2013-03-05 14:40:46 +0100 (Tue, 05 Mar 2013) $ by $Author: schulte $
14  * $Revision: 13435 $
15  *
16  * This file is part of Gecode, the generic constraint
17  * development environment:
18  * http://www.gecode.org
19  *
20  * Permission is hereby granted, free of charge, to any person obtaining
21  * a copy of this software and associated documentation files (the
22  * "Software"), to deal in the Software without restriction, including
23  * without limitation the rights to use, copy, modify, merge, publish,
24  * distribute, sublicense, and/or sell copies of the Software, and to
25  * permit persons to whom the Software is furnished to do so, subject to
26  * the following conditions:
27  *
28  * The above copyright notice and this permission notice shall be
29  * included in all copies or substantial portions of the Software.
30  *
31  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
32  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
33  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
34  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
35  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
36  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
37  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
38  *
39  */
40 
41 #include <gecode/set.hh>
42 #include <gecode/set/rel.hh>
43 
44 namespace Gecode {
45 
46  void
47  dom(Home home, SetVar s, SetRelType r, int i) {
48  Set::Limits::check(i, "Set::dom");
49  IntSet d(i,i);
50  dom(home, s, r, d);
51  }
52 
53  void
54  dom(Home home, const SetVarArgs& s, SetRelType r, int i) {
55  Set::Limits::check(i, "Set::dom");
56  IntSet d(i,i);
57  dom(home, s, r, d);
58  }
59 
60  void
61  dom(Home home, SetVar s, SetRelType r, int i, int j) {
62  Set::Limits::check(i, "Set::dom");
63  Set::Limits::check(j, "Set::dom");
64  IntSet d(i,j);
65  dom(home, s, r, d);
66  }
67 
68  void
69  dom(Home home, const SetVarArgs& s, SetRelType r, int i, int j) {
70  Set::Limits::check(i, "Set::dom");
71  Set::Limits::check(j, "Set::dom");
72  IntSet d(i,j);
73  dom(home, s, r, d);
74  }
75 
76  void
77  dom(Home home, SetVar s, SetRelType r, const IntSet& is) {
78  Set::Limits::check(is, "Set::dom");
79  if (home.failed()) return;
80 
81  Set::SetView _s(s);
82 
83  switch (r) {
84  case SRT_EQ:
85  {
86  if (is.ranges() == 1) {
87  GECODE_ME_FAIL(_s.include(home, is.min(), is.max()));
88  GECODE_ME_FAIL(_s.intersect(home, is.min(), is.max()));
89  } else {
90  IntSetRanges rd1(is);
91  GECODE_ME_FAIL(_s.includeI(home, rd1));
92  IntSetRanges rd2(is);
93  GECODE_ME_FAIL(_s.intersectI(home, rd2));
94  }
95  }
96  break;
97  case SRT_LQ:
98  {
99  Set::ConstSetView cv(home, is);
102  ::post(home,s,cv)));
103  }
104  break;
105  case SRT_LE:
106  {
107  Set::ConstSetView cv(home, is);
110  ::post(home,s,cv)));
111  }
112  break;
113  case SRT_GQ:
114  {
115  Set::ConstSetView cv(home, is);
118  ::post(home,cv,s)));
119  }
120  break;
121  case SRT_GR:
122  {
123  Set::ConstSetView cv(home, is);
126  ::post(home,cv,s)));
127  }
128  break;
129  case SRT_DISJ:
130  {
131  if (is.ranges() == 1) {
132  GECODE_ME_FAIL(_s.exclude(home, is.min(), is.max()));
133  } else {
134  IntSetRanges rd(is);
135  GECODE_ME_FAIL(_s.excludeI(home, rd));
136  }
137  }
138  break;
139  case SRT_NQ:
140  {
141  Set::ConstSetView cv(home, is);
144  cv)));
145  }
146  break;
147  case SRT_SUB:
148  {
149  if (is.ranges() == 1) {
150  GECODE_ME_FAIL(_s.intersect(home, is.min(), is.max()));
151  } else {
152  IntSetRanges rd(is);
153  GECODE_ME_FAIL(_s.intersectI(home, rd));
154  }
155  }
156  break;
157  case SRT_SUP:
158  {
159  if (is.ranges() == 1) {
160  GECODE_ME_FAIL(_s.include(home, is.min(), is.max()));
161  } else {
162  IntSetRanges rd(is);
163  GECODE_ME_FAIL(_s.includeI(home, rd));
164  }
165  }
166  break;
167  case SRT_CMPL:
168  {
169  if (is.ranges() == 1) {
170  GECODE_ME_FAIL(_s.exclude(home, is.min(), is.max()));
172  _s.include(home,
174  is.min()-1) );
176  _s.include(home, is.max()+1,
177  Set::Limits::max) );
178  } else {
179  IntSetRanges rd1(is);
181  GECODE_ME_FAIL(_s.includeI(home, rdC1));
182  IntSetRanges rd2(is);
184  GECODE_ME_FAIL(_s.intersectI(home, rdC2));
185  }
186  }
187  break;
188  default:
189  throw Set::UnknownRelation("Set::dom");
190  }
191  }
192 
193  void
194  dom(Home home, const SetVarArgs& s, SetRelType r, const IntSet& is) {
195  Set::Limits::check(is, "Set::dom");
196  if (home.failed()) return;
197 
198  switch (r) {
199  case SRT_EQ:
200  {
201  if (is.ranges() == 1) {
202  for (int i=s.size(); i--; ) {
203  Set::SetView _s(s[i]);
204  GECODE_ME_FAIL(_s.include(home, is.min(), is.max()));
205  GECODE_ME_FAIL(_s.intersect(home, is.min(), is.max()));
206  }
207  } else {
208  for (int i=s.size(); i--; ) {
209  Set::SetView _s(s[i]);
210  IntSetRanges rd1(is);
211  GECODE_ME_FAIL(_s.includeI(home, rd1));
212  IntSetRanges rd2(is);
213  GECODE_ME_FAIL(_s.intersectI(home, rd2));
214  }
215  }
216  }
217  break;
218  case SRT_LQ:
219  {
220  Set::ConstSetView cv(home, is);
221  for (int i=s.size(); i--; ) {
222  Set::SetView _s(s[i]);
224  ::post(home,_s,cv)));
225  }
226  }
227  break;
228  case SRT_LE:
229  {
230  Set::ConstSetView cv(home, is);
231  for (int i=s.size(); i--; ) {
232  Set::SetView _s(s[i]);
234  ::post(home,_s,cv)));
235  }
236  }
237  break;
238  case SRT_GQ:
239  {
240  Set::ConstSetView cv(home, is);
241  for (int i=s.size(); i--; ) {
242  Set::SetView _s(s[i]);
244  ::post(home,cv,_s)));
245  }
246  }
247  break;
248  case SRT_GR:
249  {
250  Set::ConstSetView cv(home, is);
251  for (int i=s.size(); i--; ) {
252  Set::SetView _s(s[i]);
254  ::post(home,cv,_s)));
255  }
256  }
257  break;
258  case SRT_DISJ:
259  {
260  if (is.ranges() == 1) {
261  for (int i=s.size(); i--; ) {
262  Set::SetView _s(s[i]);
263  GECODE_ME_FAIL(_s.exclude(home, is.min(), is.max()));
264  }
265  } else {
266  for (int i=s.size(); i--; ) {
267  Set::SetView _s(s[i]);
268  IntSetRanges rd(is);
269  GECODE_ME_FAIL(_s.excludeI(home, rd));
270  }
271  }
272  }
273  break;
274  case SRT_NQ:
275  {
276  Set::ConstSetView cv(home, is);
277  for (int i=s.size(); i--; ) {
278  Set::SetView _s(s[i]);
280  ::post(home,_s,cv)));
281  }
282  }
283  break;
284  case SRT_SUB:
285  {
286  if (is.ranges() == 1) {
287  for (int i=s.size(); i--; ) {
288  Set::SetView _s(s[i]);
289  GECODE_ME_FAIL(_s.intersect(home, is.min(), is.max()));
290  }
291  } else {
292  for (int i=s.size(); i--; ) {
293  Set::SetView _s(s[i]);
294  IntSetRanges rd(is);
295  GECODE_ME_FAIL(_s.intersectI(home, rd));
296  }
297  }
298  }
299  break;
300  case SRT_SUP:
301  {
302  if (is.ranges() == 1) {
303  for (int i=s.size(); i--; ) {
304  Set::SetView _s(s[i]);
305  GECODE_ME_FAIL(_s.include(home, is.min(), is.max()));
306  }
307  } else {
308  for (int i=s.size(); i--; ) {
309  Set::SetView _s(s[i]);
310  IntSetRanges rd(is);
311  GECODE_ME_FAIL(_s.includeI(home, rd));
312  }
313  }
314  }
315  break;
316  case SRT_CMPL:
317  {
318  if (is.ranges() == 1) {
319  for (int i=s.size(); i--; ) {
320  Set::SetView _s(s[i]);
321  GECODE_ME_FAIL(_s.exclude(home, is.min(), is.max()));
322  GECODE_ME_FAIL(_s.include(home,
324  is.min()-1) );
325  GECODE_ME_FAIL(_s.include(home, is.max()+1,
326  Set::Limits::max) );
327  }
328  } else {
329  for (int i=s.size(); i--; ) {
330  Set::SetView _s(s[i]);
331  IntSetRanges rd1(is);
333  GECODE_ME_FAIL(_s.includeI(home, rdC1));
334  IntSetRanges rd2(is);
336  GECODE_ME_FAIL(_s.intersectI(home, rdC2));
337  }
338  }
339  }
340  break;
341  default:
342  throw Set::UnknownRelation("Set::dom");
343  }
344  }
345 
346  void
347  dom(Home home, SetVar s, SetRelType rt, int i, Reify r) {
348  Set::Limits::check(i, "Set::dom");
349  IntSet d(i,i);
350  dom(home, s, rt, d, r);
351  }
352 
353  void
354  dom(Home home, SetVar s, SetRelType rt, int i, int j, Reify r) {
355  Set::Limits::check(i, "Set::dom");
356  Set::Limits::check(j, "Set::dom");
357  IntSet d(i,j);
358  dom(home, s, rt, d, r);
359  }
360 
361  void
362  dom(Home home, SetVar s, SetRelType rt, const IntSet& is, Reify r) {
363  Set::Limits::check(is, "Set::dom");
364  if (home.failed()) return;
365  switch (rt) {
366  case SRT_EQ:
367  {
368  Set::ConstSetView cv(home, is);
369  switch (r.mode()) {
370  case RM_EQV:
374  ::post(home, s, cv, r.var())));
375  break;
376  case RM_IMP:
380  ::post(home, s, cv, r.var())));
381  break;
382  case RM_PMI:
386  ::post(home, s, cv, r.var())));
387  break;
388  default: throw Gecode::Int::UnknownReifyMode("Set::dom");
389  }
390  }
391  break;
392  case SRT_LQ:
393  {
394  Set::ConstSetView cv(home, is);
395  switch (r.mode()) {
396  case RM_EQV:
399  Set::ConstSetView,RM_EQV,false>::post(home, s, cv, r.var())));
400  break;
401  case RM_IMP:
404  Set::ConstSetView,RM_IMP,false>::post(home, s, cv, r.var())));
405  break;
406  case RM_PMI:
409  Set::ConstSetView,RM_PMI,false>::post(home, s, cv, r.var())));
410  break;
411  default: throw Gecode::Int::UnknownReifyMode("Set::dom");
412  }
413  }
414  break;
415  case SRT_LE:
416  {
417  Set::ConstSetView cv(home, is);
418  switch (r.mode()) {
419  case RM_EQV:
422  Set::ConstSetView,RM_EQV,true>::post(home, s, cv, r.var())));
423  break;
424  case RM_IMP:
427  Set::ConstSetView,RM_IMP,true>::post(home, s, cv, r.var())));
428  break;
429  case RM_PMI:
432  Set::ConstSetView,RM_PMI,true>::post(home, s, cv, r.var())));
433  break;
434  default: throw Gecode::Int::UnknownReifyMode("Set::dom");
435  }
436  }
437  break;
438  case SRT_GQ:
439  {
440  Set::ConstSetView cv(home, is);
441  switch (r.mode()) {
442  case RM_EQV:
445  ::post(home,cv,s,r.var())));
446  break;
447  case RM_IMP:
450  ::post(home,cv,s,r.var())));
451  break;
452  case RM_PMI:
455  ::post(home,cv,s,r.var())));
456  break;
457  default: throw Gecode::Int::UnknownReifyMode("Set::dom");
458  }
459  }
460  break;
461  case SRT_GR:
462  {
463  Set::ConstSetView cv(home, is);
464  switch (r.mode()) {
465  case RM_EQV:
468  ::post(home,cv,s,r.var())));
469  break;
470  case RM_IMP:
473  ::post(home,cv,s,r.var())));
474  break;
475  case RM_PMI:
478  ::post(home,cv,s,r.var())));
479  break;
480  default: throw Gecode::Int::UnknownReifyMode("Set::dom");
481  }
482  }
483  break;
484  case SRT_NQ:
485  {
486  Gecode::Int::NegBoolView notb(r.var());
487  Set::ConstSetView cv(home, is);
488  switch (r.mode()) {
489  case RM_EQV:
493  ::post(home, s, cv, notb)));
494  break;
495  case RM_IMP:
499  ::post(home, s, cv, notb)));
500  break;
501  case RM_PMI:
505  ::post(home, s, cv, notb)));
506  break;
507  default: throw Gecode::Int::UnknownReifyMode("Set::dom");
508  }
509  }
510  break;
511  case SRT_SUB:
512  {
513  Set::ConstSetView cv(home, is);
514  switch (r.mode()) {
515  case RM_EQV:
518  Set::ConstSetView,RM_EQV>::post(home, s, cv, r.var())));
519  break;
520  case RM_IMP:
523  Set::ConstSetView,RM_IMP>::post(home, s, cv, r.var())));
524  break;
525  case RM_PMI:
528  Set::ConstSetView,RM_PMI>::post(home, s, cv, r.var())));
529  break;
530  default: throw Gecode::Int::UnknownReifyMode("Set::dom");
531  }
532  }
533  break;
534  case SRT_SUP:
535  {
536  Set::ConstSetView cv(home, is);
537  switch (r.mode()) {
538  case RM_EQV:
541  ::post(home, cv, s, r.var())));
542  break;
543  case RM_IMP:
546  ::post(home, cv, s, r.var())));
547  break;
548  case RM_PMI:
551  ::post(home, cv, s, r.var())));
552  break;
553  default: throw Gecode::Int::UnknownReifyMode("Set::dom");
554  }
555  }
556  break;
557  case SRT_DISJ:
558  {
559  // x||y <=> b is equivalent to
560  // ( y <= complement(x) and x<=complement(y) ) <=> b
561 
562  // compute complement of is
563  IntSetRanges dr1(is);
565  IntSet dcompl(dc1);
566  Set::ConstSetView cvcompl(home, dcompl);
567  switch (r.mode()) {
568  case RM_EQV:
571  Set::ConstSetView,RM_EQV>::post(home, s, cvcompl, r.var())));
572  break;
573  case RM_IMP:
576  Set::ConstSetView,RM_IMP>::post(home, s, cvcompl, r.var())));
577  break;
578  case RM_PMI:
581  Set::ConstSetView,RM_PMI>::post(home, s, cvcompl, r.var())));
582  break;
583  default: throw Gecode::Int::UnknownReifyMode("Set::dom");
584  }
585  }
586  break;
587  case SRT_CMPL:
588  {
589  Set::SetView sv(s);
590 
591  IntSetRanges dr1(is);
593  IntSet dcompl(dc1);
594  Set::ConstSetView cvcompl(home, dcompl);
595 
596  switch (r.mode()) {
597  case RM_EQV:
601  ::post(home, s, cvcompl, r.var())));
602  break;
603  case RM_IMP:
607  ::post(home, s, cvcompl, r.var())));
608  break;
609  case RM_PMI:
613  ::post(home, s, cvcompl, r.var())));
614  break;
615  default: throw Gecode::Int::UnknownReifyMode("Set::dom");
616  }
617  }
618  break;
619  default:
620  throw Set::UnknownRelation("Set::dom");
621  }
622  }
623 
624  void
625  dom(Home home, SetVar x, SetVar d) {
626  using namespace Set;
627  if (home.failed()) return;
628  SetView xv(x), dv(d);
629  if (!same(xv,dv)) {
630  GECODE_ME_FAIL(xv.cardMax(home,dv.cardMax()));
631  GECODE_ME_FAIL(xv.cardMin(home,dv.cardMin()));
632  GlbRanges<SetView> lb(dv);
633  GECODE_ME_FAIL(xv.includeI(home,lb));
634  LubRanges<SetView> ub(dv);
635  GECODE_ME_FAIL(xv.intersectI(home,ub));
636  }
637  }
638 
639  void
640  dom(Home home, const SetVarArgs& x, const SetVarArgs& d) {
641  using namespace Set;
642  if (x.size() != d.size())
643  throw ArgumentSizeMismatch("Set::dom");
644  for (int i=x.size(); i--; ) {
645  if (home.failed()) return;
646  SetView xv(x[i]), dv(d[i]);
647  if (!same(xv,dv)) {
648  GECODE_ME_FAIL(xv.cardMax(home,dv.cardMax()));
649  GECODE_ME_FAIL(xv.cardMin(home,dv.cardMin()));
650  GlbRanges<SetView> lb(dv);
651  GECODE_ME_FAIL(xv.includeI(home,lb));
652  LubRanges<SetView> ub(dv);
653  GECODE_ME_FAIL(xv.intersectI(home,ub));
654  }
655  }
656  }
657 
658 }
659 
660 // STATISTICS: set-post
bool failed(void) const
Check whether corresponding space is failed.
Definition: core.hpp:3446
unsigned int cardMin(void) const
Return minimum cardinality.
Definition: set.hpp:86
ModEvent include(Space &home, int i, int j)
Update greatest lower bound to include all elements between and including i and j.
Definition: set.hpp:130
void check(int n, const char *l)
Check whether integer n is in range, otherwise throw overflow exception with information l...
Definition: limits.hpp:41
SetRelType
Common relation types for sets.
Definition: set.hh:644
Inverse implication for reification.
Definition: int.hh:847
ReifyMode mode(void) const
Return reification mode.
Definition: reify.hpp:60
void post(Home home, Term *t, int n, FloatRelType frt, FloatVal c)
Post propagator for linear constraint over floats.
Definition: post.cpp:228
const int min
Smallest allowed integer in integer set.
Definition: set.hh:101
Range iterator for integer sets.
Definition: int.hh:271
BoolVar var(void) const
Return Boolean control variable.
Definition: reify.hpp:52
Negated Boolean view.
Definition: view.hpp:1503
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1662
void dom(Home home, FloatVar x, FloatVal n)
Propagates .
Definition: dom.cpp:44
unsigned int cardMax(void) const
Return maximum cardinality.
Definition: set.hpp:90
Propagator for set less than or equal
Definition: rel.hh:203
ModEvent intersect(Space &home, int i, int j)
Update least upper bound to contain at most all elements between and including i and j...
Definition: set.hpp:145
Superset ( )
Definition: set.hh:648
ModEvent excludeI(Space &home, I &i)
Remove range sequence described by i from least upper bound.
Definition: set.hpp:164
Complement.
Definition: set.hh:650
const int max
Largest allowed integer in integer set.
Definition: set.hh:99
Exception: Unknown relation passed as argument
Definition: exception.hpp:91
Reified equality propagator
Definition: rel.hh:170
Gecode::IntSet d(r, 4)
Gecode::IntArgs i(4, 1, 2, 3, 4)
Range iterator for least upper bound of set variable views
Definition: set.hpp:205
int ranges(void) const
Return number of ranges of the specification.
Definition: int-set-1.hpp:134
Range iterator for greatest lower bound of set variable views
Definition: set.hpp:236
Less or equal ( )
Definition: set.hh:651
A complement iterator spezialized for the BndSet limits.
Definition: var-imp.hpp:296
Reification specification.
Definition: int.hh:854
Subset ( )
Definition: set.hh:647
DomRange dr1(1)
Integer sets.
Definition: int.hh:171
Less ( )
Definition: set.hh:652
ModEvent includeI(Space &home, I &i)
Include range sequence described by i in greatest lower bound.
Definition: set.hpp:155
Reified propagator for set less than or equal
Definition: rel.hh:229
bool same(const ConstSetView &x, const ConstSetView &y)
Definition: const.hpp:688
ModEvent intersectI(Space &home, I &iter)
Intersect least upper bound with range sequence described by i.
Definition: set.hpp:168
Set view for set variables
Definition: view.hpp:60
Passing set variables.
Definition: set.hh:490
Greater or equal ( )
Definition: set.hh:653
Constant view.
Definition: view.hpp:190
Reified subset propagator
Definition: rel.hh:115
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
Set variables
Definition: set.hh:129
Propagator for negated equality
Definition: rel.hh:290
Greater ( )
Definition: set.hh:654
Equality ( )
Definition: set.hh:645
Disjoint ( )
Definition: set.hh:649
#define GECODE_ME_FAIL(me)
Check whether modification event me is failed, and fail space home.
Definition: macros.hpp:70
ModEvent exclude(Space &home, int i, int j)
Restrict least upper bound to not contain all elements between and including i and j...
Definition: set.hpp:160
Disequality ( )
Definition: set.hh:646
Exception: Unknown reification mode passed as argument
Definition: exception.hpp:119
Gecode toplevel namespace
Implication for reification.
Definition: int.hh:840
Home class for posting propagators
Definition: core.hpp:717
Exception: Arguments are of different size
Definition: exception.hpp:77
#define GECODE_ES_FAIL(es)
Check whether execution status es is failed, and fail space home.
Definition: macros.hpp:96
const int r[4][2]
Definition: dom.cpp:126
int max(int i) const
Return maximum of range at position i.
Definition: int-set-1.hpp:121
int min(int i) const
Return minimum of range at position i.
Definition: int-set-1.hpp:115
Equivalence for reification (default)
Definition: int.hh:833
Boolean view for Boolean variables.
Definition: view.hpp:1315