Generated on Mon Feb 8 2021 00:00:00 for Gecode by doxygen 1.8.20
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  * This file is part of Gecode, the generic constraint
13  * development environment:
14  * http://www.gecode.org
15  *
16  * Permission is hereby granted, free of charge, to any person obtaining
17  * a copy of this software and associated documentation files (the
18  * "Software"), to deal in the Software without restriction, including
19  * without limitation the rights to use, copy, modify, merge, publish,
20  * distribute, sublicense, and/or sell copies of the Software, and to
21  * permit persons to whom the Software is furnished to do so, subject to
22  * the following conditions:
23  *
24  * The above copyright notice and this permission notice shall be
25  * included in all copies or substantial portions of the Software.
26  *
27  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
28  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
29  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
30  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
31  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
32  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
33  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
34  *
35  */
36 
37 #include <gecode/set.hh>
38 #include <gecode/set/rel.hh>
39 
40 namespace Gecode {
41 
42  void
43  dom(Home home, SetVar s, SetRelType r, int i) {
44  Set::Limits::check(i, "Set::dom");
45  IntSet d(i,i);
46  dom(home, s, r, d);
47  }
48 
49  void
50  dom(Home home, const SetVarArgs& s, SetRelType r, int i) {
51  Set::Limits::check(i, "Set::dom");
52  IntSet d(i,i);
53  dom(home, s, r, d);
54  }
55 
56  void
57  dom(Home home, SetVar s, SetRelType r, int i, int j) {
58  Set::Limits::check(i, "Set::dom");
59  Set::Limits::check(j, "Set::dom");
60  IntSet d(i,j);
61  dom(home, s, r, d);
62  }
63 
64  void
65  dom(Home home, const SetVarArgs& s, SetRelType r, int i, int j) {
66  Set::Limits::check(i, "Set::dom");
67  Set::Limits::check(j, "Set::dom");
68  IntSet d(i,j);
69  dom(home, s, r, d);
70  }
71 
72  void
73  dom(Home home, SetVar s, SetRelType r, const IntSet& is) {
74  Set::Limits::check(is, "Set::dom");
76 
77  Set::SetView _s(s);
78 
79  switch (r) {
80  case SRT_EQ:
81  {
82  if (is.ranges() == 1) {
83  GECODE_ME_FAIL(_s.include(home, is.min(), is.max()));
84  GECODE_ME_FAIL(_s.intersect(home, is.min(), is.max()));
85  } else {
86  IntSetRanges rd1(is);
87  GECODE_ME_FAIL(_s.includeI(home, rd1));
88  IntSetRanges rd2(is);
89  GECODE_ME_FAIL(_s.intersectI(home, rd2));
90  }
91  }
92  break;
93  case SRT_LQ:
94  {
95  Set::ConstSetView cv(home, is);
98  ::post(home,s,cv)));
99  }
100  break;
101  case SRT_LE:
102  {
103  Set::ConstSetView cv(home, is);
106  ::post(home,s,cv)));
107  }
108  break;
109  case SRT_GQ:
110  {
111  Set::ConstSetView cv(home, is);
114  ::post(home,cv,s)));
115  }
116  break;
117  case SRT_GR:
118  {
119  Set::ConstSetView cv(home, is);
122  ::post(home,cv,s)));
123  }
124  break;
125  case SRT_DISJ:
126  {
127  if (is.ranges() == 1) {
128  GECODE_ME_FAIL(_s.exclude(home, is.min(), is.max()));
129  } else {
130  IntSetRanges rd(is);
131  GECODE_ME_FAIL(_s.excludeI(home, rd));
132  }
133  }
134  break;
135  case SRT_NQ:
136  {
137  Set::ConstSetView cv(home, is);
140  cv)));
141  }
142  break;
143  case SRT_SUB:
144  {
145  if (is.ranges() == 1) {
146  GECODE_ME_FAIL(_s.intersect(home, is.min(), is.max()));
147  } else {
148  IntSetRanges rd(is);
149  GECODE_ME_FAIL(_s.intersectI(home, rd));
150  }
151  }
152  break;
153  case SRT_SUP:
154  {
155  if (is.ranges() == 1) {
156  GECODE_ME_FAIL(_s.include(home, is.min(), is.max()));
157  } else {
158  IntSetRanges rd(is);
159  GECODE_ME_FAIL(_s.includeI(home, rd));
160  }
161  }
162  break;
163  case SRT_CMPL:
164  {
165  if (is.ranges() == 1) {
166  GECODE_ME_FAIL(_s.exclude(home, is.min(), is.max()));
168  _s.include(home,
170  is.min()-1) );
172  _s.include(home, is.max()+1,
173  Set::Limits::max) );
174  } else {
175  IntSetRanges rd1(is);
177  GECODE_ME_FAIL(_s.includeI(home, rdC1));
178  IntSetRanges rd2(is);
180  GECODE_ME_FAIL(_s.intersectI(home, rdC2));
181  }
182  }
183  break;
184  default:
185  throw Set::UnknownRelation("Set::dom");
186  }
187  }
188 
189  void
190  dom(Home home, const SetVarArgs& s, SetRelType r, const IntSet& is) {
191  Set::Limits::check(is, "Set::dom");
192  GECODE_POST;
193 
194  switch (r) {
195  case SRT_EQ:
196  {
197  if (is.ranges() == 1) {
198  for (int i=s.size(); i--; ) {
199  Set::SetView _s(s[i]);
200  GECODE_ME_FAIL(_s.include(home, is.min(), is.max()));
201  GECODE_ME_FAIL(_s.intersect(home, is.min(), is.max()));
202  }
203  } else {
204  for (int i=s.size(); i--; ) {
205  Set::SetView _s(s[i]);
206  IntSetRanges rd1(is);
207  GECODE_ME_FAIL(_s.includeI(home, rd1));
208  IntSetRanges rd2(is);
209  GECODE_ME_FAIL(_s.intersectI(home, rd2));
210  }
211  }
212  }
213  break;
214  case SRT_LQ:
215  {
216  Set::ConstSetView cv(home, is);
217  for (int i=s.size(); i--; ) {
218  Set::SetView _s(s[i]);
220  ::post(home,_s,cv)));
221  }
222  }
223  break;
224  case SRT_LE:
225  {
226  Set::ConstSetView cv(home, is);
227  for (int i=s.size(); i--; ) {
228  Set::SetView _s(s[i]);
230  ::post(home,_s,cv)));
231  }
232  }
233  break;
234  case SRT_GQ:
235  {
236  Set::ConstSetView cv(home, is);
237  for (int i=s.size(); i--; ) {
238  Set::SetView _s(s[i]);
240  ::post(home,cv,_s)));
241  }
242  }
243  break;
244  case SRT_GR:
245  {
246  Set::ConstSetView cv(home, is);
247  for (int i=s.size(); i--; ) {
248  Set::SetView _s(s[i]);
250  ::post(home,cv,_s)));
251  }
252  }
253  break;
254  case SRT_DISJ:
255  {
256  if (is.ranges() == 1) {
257  for (int i=s.size(); i--; ) {
258  Set::SetView _s(s[i]);
259  GECODE_ME_FAIL(_s.exclude(home, is.min(), is.max()));
260  }
261  } else {
262  for (int i=s.size(); i--; ) {
263  Set::SetView _s(s[i]);
264  IntSetRanges rd(is);
265  GECODE_ME_FAIL(_s.excludeI(home, rd));
266  }
267  }
268  }
269  break;
270  case SRT_NQ:
271  {
272  Set::ConstSetView cv(home, is);
273  for (int i=s.size(); i--; ) {
274  Set::SetView _s(s[i]);
276  ::post(home,_s,cv)));
277  }
278  }
279  break;
280  case SRT_SUB:
281  {
282  if (is.ranges() == 1) {
283  for (int i=s.size(); i--; ) {
284  Set::SetView _s(s[i]);
285  GECODE_ME_FAIL(_s.intersect(home, is.min(), is.max()));
286  }
287  } else {
288  for (int i=s.size(); i--; ) {
289  Set::SetView _s(s[i]);
290  IntSetRanges rd(is);
291  GECODE_ME_FAIL(_s.intersectI(home, rd));
292  }
293  }
294  }
295  break;
296  case SRT_SUP:
297  {
298  if (is.ranges() == 1) {
299  for (int i=s.size(); i--; ) {
300  Set::SetView _s(s[i]);
301  GECODE_ME_FAIL(_s.include(home, is.min(), is.max()));
302  }
303  } else {
304  for (int i=s.size(); i--; ) {
305  Set::SetView _s(s[i]);
306  IntSetRanges rd(is);
307  GECODE_ME_FAIL(_s.includeI(home, rd));
308  }
309  }
310  }
311  break;
312  case SRT_CMPL:
313  {
314  if (is.ranges() == 1) {
315  for (int i=s.size(); i--; ) {
316  Set::SetView _s(s[i]);
317  GECODE_ME_FAIL(_s.exclude(home, is.min(), is.max()));
318  GECODE_ME_FAIL(_s.include(home,
320  is.min()-1) );
321  GECODE_ME_FAIL(_s.include(home, is.max()+1,
322  Set::Limits::max) );
323  }
324  } else {
325  for (int i=s.size(); i--; ) {
326  Set::SetView _s(s[i]);
327  IntSetRanges rd1(is);
329  GECODE_ME_FAIL(_s.includeI(home, rdC1));
330  IntSetRanges rd2(is);
332  GECODE_ME_FAIL(_s.intersectI(home, rdC2));
333  }
334  }
335  }
336  break;
337  default:
338  throw Set::UnknownRelation("Set::dom");
339  }
340  }
341 
342  void
343  dom(Home home, SetVar s, SetRelType rt, int i, Reify r) {
344  Set::Limits::check(i, "Set::dom");
345  IntSet d(i,i);
346  dom(home, s, rt, d, r);
347  }
348 
349  void
350  dom(Home home, SetVar s, SetRelType rt, int i, int j, Reify r) {
351  Set::Limits::check(i, "Set::dom");
352  Set::Limits::check(j, "Set::dom");
353  IntSet d(i,j);
354  dom(home, s, rt, d, r);
355  }
356 
357  void
358  dom(Home home, SetVar s, SetRelType rt, const IntSet& is, Reify r) {
359  Set::Limits::check(is, "Set::dom");
360  GECODE_POST;
361  switch (rt) {
362  case SRT_EQ:
363  {
364  Set::ConstSetView cv(home, is);
365  switch (r.mode()) {
366  case RM_EQV:
370  ::post(home, s, cv, r.var())));
371  break;
372  case RM_IMP:
376  ::post(home, s, cv, r.var())));
377  break;
378  case RM_PMI:
382  ::post(home, s, cv, r.var())));
383  break;
384  default: throw Gecode::Int::UnknownReifyMode("Set::dom");
385  }
386  }
387  break;
388  case SRT_LQ:
389  {
390  Set::ConstSetView cv(home, is);
391  switch (r.mode()) {
392  case RM_EQV:
395  Set::ConstSetView,RM_EQV,false>::post(home, s, cv, r.var())));
396  break;
397  case RM_IMP:
400  Set::ConstSetView,RM_IMP,false>::post(home, s, cv, r.var())));
401  break;
402  case RM_PMI:
405  Set::ConstSetView,RM_PMI,false>::post(home, s, cv, r.var())));
406  break;
407  default: throw Gecode::Int::UnknownReifyMode("Set::dom");
408  }
409  }
410  break;
411  case SRT_LE:
412  {
413  Set::ConstSetView cv(home, is);
414  switch (r.mode()) {
415  case RM_EQV:
418  Set::ConstSetView,RM_EQV,true>::post(home, s, cv, r.var())));
419  break;
420  case RM_IMP:
423  Set::ConstSetView,RM_IMP,true>::post(home, s, cv, r.var())));
424  break;
425  case RM_PMI:
428  Set::ConstSetView,RM_PMI,true>::post(home, s, cv, r.var())));
429  break;
430  default: throw Gecode::Int::UnknownReifyMode("Set::dom");
431  }
432  }
433  break;
434  case SRT_GQ:
435  {
436  Set::ConstSetView cv(home, is);
437  switch (r.mode()) {
438  case RM_EQV:
441  ::post(home,cv,s,r.var())));
442  break;
443  case RM_IMP:
446  ::post(home,cv,s,r.var())));
447  break;
448  case RM_PMI:
451  ::post(home,cv,s,r.var())));
452  break;
453  default: throw Gecode::Int::UnknownReifyMode("Set::dom");
454  }
455  }
456  break;
457  case SRT_GR:
458  {
459  Set::ConstSetView cv(home, is);
460  switch (r.mode()) {
461  case RM_EQV:
464  ::post(home,cv,s,r.var())));
465  break;
466  case RM_IMP:
469  ::post(home,cv,s,r.var())));
470  break;
471  case RM_PMI:
474  ::post(home,cv,s,r.var())));
475  break;
476  default: throw Gecode::Int::UnknownReifyMode("Set::dom");
477  }
478  }
479  break;
480  case SRT_NQ:
481  {
482  Gecode::Int::NegBoolView notb(r.var());
483  Set::ConstSetView cv(home, is);
484  switch (r.mode()) {
485  case RM_EQV:
489  ::post(home, s, cv, notb)));
490  break;
491  case RM_IMP:
495  ::post(home, s, cv, notb)));
496  break;
497  case RM_PMI:
501  ::post(home, s, cv, notb)));
502  break;
503  default: throw Gecode::Int::UnknownReifyMode("Set::dom");
504  }
505  }
506  break;
507  case SRT_SUB:
508  {
509  Set::ConstSetView cv(home, is);
510  switch (r.mode()) {
511  case RM_EQV:
515  ::post(home, s, cv, r.var())));
516  break;
517  case RM_IMP:
521  ::post(home, s, cv, r.var())));
522  break;
523  case RM_PMI:
527  ::post(home, s, cv, r.var())));
528  break;
529  default: throw Gecode::Int::UnknownReifyMode("Set::dom");
530  }
531  }
532  break;
533  case SRT_SUP:
534  {
535  Set::ConstSetView cv(home, is);
536  switch (r.mode()) {
537  case RM_EQV:
541  ::post(home, cv, s, r.var())));
542  break;
543  case RM_IMP:
547  ::post(home, cv, s, r.var())));
548  break;
549  case RM_PMI:
553  ::post(home, cv, s, r.var())));
554  break;
555  default: throw Gecode::Int::UnknownReifyMode("Set::dom");
556  }
557  }
558  break;
559  case SRT_DISJ:
560  {
561  // x||y <=> b is equivalent to
562  // ( y <= complement(x) and x<=complement(y) ) <=> b
563 
564  // compute complement of is
565  IntSetRanges dr1(is);
567  IntSet dcompl(dc1);
568  Set::ConstSetView cvcompl(home, dcompl);
569  switch (r.mode()) {
570  case RM_EQV:
574  ::post(home, s, cvcompl, r.var())));
575  break;
576  case RM_IMP:
580  ::post(home, s, cvcompl, r.var())));
581  break;
582  case RM_PMI:
586  ::post(home, s, cvcompl, r.var())));
587  break;
588  default: throw Gecode::Int::UnknownReifyMode("Set::dom");
589  }
590  }
591  break;
592  case SRT_CMPL:
593  {
594  Set::SetView sv(s);
595 
596  IntSetRanges dr1(is);
598  IntSet dcompl(dc1);
599  Set::ConstSetView cvcompl(home, dcompl);
600 
601  switch (r.mode()) {
602  case RM_EQV:
606  ::post(home, s, cvcompl, r.var())));
607  break;
608  case RM_IMP:
612  ::post(home, s, cvcompl, r.var())));
613  break;
614  case RM_PMI:
618  ::post(home, s, cvcompl, r.var())));
619  break;
620  default: throw Gecode::Int::UnknownReifyMode("Set::dom");
621  }
622  }
623  break;
624  default:
625  throw Set::UnknownRelation("Set::dom");
626  }
627  }
628 
629  void
630  dom(Home home, SetVar x, SetVar d) {
631  using namespace Set;
632  GECODE_POST;
633  SetView xv(x), dv(d);
634  if (xv != dv) {
635  GECODE_ME_FAIL(xv.cardMax(home,dv.cardMax()));
636  GECODE_ME_FAIL(xv.cardMin(home,dv.cardMin()));
637  GlbRanges<SetView> lb(dv);
638  GECODE_ME_FAIL(xv.includeI(home,lb));
639  LubRanges<SetView> ub(dv);
640  GECODE_ME_FAIL(xv.intersectI(home,ub));
641  }
642  }
643 
644  void
645  dom(Home home, const SetVarArgs& x, const SetVarArgs& d) {
646  using namespace Set;
647  if (x.size() != d.size())
648  throw ArgumentSizeMismatch("Set::dom");
649  for (int i=x.size(); i--; ) {
650  GECODE_POST;
651  SetView xv(x[i]), dv(d[i]);
652  if (xv != dv) {
653  GECODE_ME_FAIL(xv.cardMax(home,dv.cardMax()));
654  GECODE_ME_FAIL(xv.cardMin(home,dv.cardMin()));
655  GlbRanges<SetView> lb(dv);
656  GECODE_ME_FAIL(xv.includeI(home,lb));
657  LubRanges<SetView> ub(dv);
658  GECODE_ME_FAIL(xv.intersectI(home,ub));
659  }
660  }
661  }
662 
663 }
664 
665 // STATISTICS: set-post
Exception: Unknown reification mode passed as argument
Definition: exception.hpp:115
Negated Boolean view.
Definition: view.hpp:1574
Post propagator for SetVar x
Definition: set.hh:767
Exception: Arguments are of different size
Definition: exception.hpp:73
unsigned int cardMax(void) const
Return maximum cardinality.
Definition: set.hpp:86
int min(int i) const
Return minimum of range at position i.
Definition: int-set-1.hpp:152
@ RM_PMI
Inverse implication for reification.
Definition: int.hh:869
#define GECODE_ES_FAIL(es)
Check whether execution status es is failed, and fail space home.
Definition: macros.hpp:103
Constant view.
Definition: view.hpp:186
Range iterator for least upper bound of set variable views
Definition: set.hpp:211
int max(int i) const
Return maximum of range at position i.
Definition: int-set-1.hpp:158
const int min
Smallest allowed integer in integer set.
Definition: set.hh:99
@ RM_IMP
Implication for reification.
Definition: int.hh:862
Passing set variables.
Definition: set.hh:488
@ SRT_LQ
Less or equal ( )
Definition: set.hh:650
@ SRT_GQ
Greater or equal ( )
Definition: set.hh:652
@ SRT_SUB
Subset ( )
Definition: set.hh:646
Range iterator for greatest lower bound of set variable views
Definition: set.hpp:242
@ SRT_SUP
Superset ( )
Definition: set.hh:647
Range iterator for integer sets.
Definition: int.hh:292
unsigned int size(void) const
Return size (cardinality) of set.
Definition: int-set-1.hpp:198
@ SRT_DISJ
Disjoint ( )
Definition: set.hh:648
Boolean view for Boolean variables.
Definition: view.hpp:1380
Gecode toplevel namespace
Integer sets.
Definition: int.hh:174
const int max
Largest allowed integer in integer set.
Definition: set.hh:97
unsigned int cardMin(void) const
Return minimum cardinality.
Definition: set.hpp:82
A complement iterator spezialized for the BndSet limits.
Definition: var-imp.hpp:293
@ SRT_EQ
Equality ( )
Definition: set.hh:644
Reification specification.
Definition: int.hh:876
RegDistinct rd
@ RM_EQV
Equivalence for reification (default)
Definition: int.hh:855
Home class for posting propagators
Definition: core.hpp:856
void dom(Home home, FloatVar x, FloatVal n)
Propagates .
Definition: dom.cpp:40
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
TFE post(PropagatorGroup g)
Only post functions (but not propagators) from g are considered.
Definition: filter.cpp:138
Set variables
Definition: set.hh:127
Reified equality propagator
Definition: rel.hh:174
SetRelType
Common relation types for sets.
Definition: set.hh:643
@ SRT_LE
Less ( )
Definition: set.hh:651
@ SRT_GR
Greater ( )
Definition: set.hh:653
@ SRT_NQ
Disequality ( )
Definition: set.hh:645
@ SRT_CMPL
Complement.
Definition: set.hh:649
Set view for set variables
Definition: view.hpp:56
Reified propagator for set less than or equal
Definition: rel.hh:234
Propagator for negated equality
Definition: rel.hh:296
void check(int n, const char *l)
Check whether integer n is in range, otherwise throw overflow exception with information l.
Definition: limits.hpp:37
#define GECODE_POST
Check for failure in a constraint post function.
Definition: macros.hpp:40
Gecode::IntSet d(r, 4)
#define GECODE_ME_FAIL(me)
Check whether modification event me is failed, and fail space home.
Definition: macros.hpp:77
Exception: Unknown relation passed as argument
Definition: exception.hpp:87
Propagator for set less than or equal
Definition: rel.hh:208
Reified subset propagator
Definition: rel.hh:115
Gecode::IntArgs i({1, 2, 3, 4})
DomRange dr1(1)
int ranges(void) const
Return number of ranges of the specification.
Definition: int-set-1.hpp:171