Generated on Fri Jan 28 2022 04:43:06 for Gecode by doxygen 1.8.13
rel.cpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  *
6  * Copyright:
7  * Christian Schulte, 2002
8  *
9  * This file is part of Gecode, the generic constraint
10  * development environment:
11  * http://www.gecode.org
12  *
13  * Permission is hereby granted, free of charge, to any person obtaining
14  * a copy of this software and associated documentation files (the
15  * "Software"), to deal in the Software without restriction, including
16  * without limitation the rights to use, copy, modify, merge, publish,
17  * distribute, sublicense, and/or sell copies of the Software, and to
18  * permit persons to whom the Software is furnished to do so, subject to
19  * the following conditions:
20  *
21  * The above copyright notice and this permission notice shall be
22  * included in all copies or substantial portions of the Software.
23  *
24  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31  *
32  */
33 
34 #include <gecode/int/rel.hh>
35 #include <gecode/int/bool.hh>
36 
37 #include <algorithm>
38 
39 namespace Gecode {
40 
41  void
42  rel(Home home, IntVar x0, IntRelType irt, int n, IntPropLevel) {
43  using namespace Int;
44  Limits::check(n,"Int::rel");
46  IntView x(x0);
47  switch (irt) {
48  case IRT_EQ: GECODE_ME_FAIL(x.eq(home,n)); break;
49  case IRT_NQ: GECODE_ME_FAIL(x.nq(home,n)); break;
50  case IRT_LQ: GECODE_ME_FAIL(x.lq(home,n)); break;
51  case IRT_LE: GECODE_ME_FAIL(x.le(home,n)); break;
52  case IRT_GQ: GECODE_ME_FAIL(x.gq(home,n)); break;
53  case IRT_GR: GECODE_ME_FAIL(x.gr(home,n)); break;
54  default: throw UnknownRelation("Int::rel");
55  }
56  }
57 
58  void
59  rel(Home home, const IntVarArgs& x, IntRelType irt, int n, IntPropLevel) {
60  using namespace Int;
61  Limits::check(n,"Int::rel");
63  switch (irt) {
64  case IRT_EQ:
65  for (int i=0; i<x.size(); i++) {
66  IntView xi(x[i]); GECODE_ME_FAIL(xi.eq(home,n));
67  }
68  break;
69  case IRT_NQ:
70  for (int i=0; i<x.size(); i++) {
71  IntView xi(x[i]); GECODE_ME_FAIL(xi.nq(home,n));
72  }
73  break;
74  case IRT_LQ:
75  for (int i=0; i<x.size(); i++) {
76  IntView xi(x[i]); GECODE_ME_FAIL(xi.lq(home,n));
77  }
78  break;
79  case IRT_LE:
80  for (int i=0; i<x.size(); i++) {
81  IntView xi(x[i]); GECODE_ME_FAIL(xi.le(home,n));
82  }
83  break;
84  case IRT_GQ:
85  for (int i=0; i<x.size(); i++) {
86  IntView xi(x[i]); GECODE_ME_FAIL(xi.gq(home,n));
87  }
88  break;
89  case IRT_GR:
90  for (int i=0; i<x.size(); i++) {
91  IntView xi(x[i]); GECODE_ME_FAIL(xi.gr(home,n));
92  }
93  break;
94  default:
95  throw UnknownRelation("Int::rel");
96  }
97  }
98 
99  void
100  rel(Home home, IntVar x0, IntRelType irt, IntVar x1, IntPropLevel ipl) {
101  using namespace Int;
102  GECODE_POST;
103  switch (irt) {
104  case IRT_EQ:
105  if ((vbd(ipl) == IPL_DOM) || (vbd(ipl) == IPL_DEF)) {
107  } else {
109  }
110  break;
111  case IRT_NQ:
112  GECODE_ES_FAIL((Rel::Nq<IntView,IntView>::post(home,x0,x1))); break;
113  case IRT_GQ:
114  std::swap(x0,x1); // Fall through
115  case IRT_LQ:
116  GECODE_ES_FAIL((Rel::Lq<IntView,IntView>::post(home,x0,x1))); break;
117  case IRT_GR:
118  std::swap(x0,x1); // Fall through
119  case IRT_LE:
120  GECODE_ES_FAIL((Rel::Le<IntView,IntView>::post(home,x0,x1))); break;
121  default:
122  throw UnknownRelation("Int::rel");
123  }
124  }
125 
126  void
127  rel(Home home, const IntVarArgs& x, IntRelType irt, IntVar y,
128  IntPropLevel ipl) {
129  using namespace Int;
130  GECODE_POST;
131  switch (irt) {
132  case IRT_EQ:
133  {
134  ViewArray<IntView> xv(home,x.size()+1);
135  xv[x.size()]=y;
136  for (int i=0; i<x.size(); i++)
137  xv[i]=x[i];
138  if ((vbd(ipl) == IPL_DOM) || (vbd(ipl) == IPL_DEF)) {
140  } else {
142  }
143  }
144  break;
145  case IRT_NQ:
146  for (int i=0; i<x.size(); i++) {
148  }
149  break;
150  case IRT_GQ:
151  for (int i=0; i<x.size(); i++) {
153  }
154  break;
155  case IRT_LQ:
156  for (int i=0; i<x.size(); i++) {
158  }
159  break;
160  case IRT_GR:
161  for (int i=0; i<x.size(); i++) {
163  }
164  break;
165  case IRT_LE:
166  for (int i=0; i<x.size(); i++) {
168  }
169  break;
170  default:
171  throw UnknownRelation("Int::rel");
172  }
173  }
174 
175 
176  void
177  rel(Home home, IntVar x0, IntRelType irt, IntVar x1, Reify r,
178  IntPropLevel ipl) {
179  using namespace Int;
180  GECODE_POST;
181  switch (irt) {
182  case IRT_EQ:
183  if ((vbd(ipl) == IPL_DOM) || (vbd(ipl) == IPL_DEF)) {
184  switch (r.mode()) {
185  case RM_EQV:
187  ::post(home,x0,x1,r.var())));
188  break;
189  case RM_IMP:
191  ::post(home,x0,x1,r.var())));
192  break;
193  case RM_PMI:
195  ::post(home,x0,x1,r.var())));
196  break;
197  default: throw UnknownReifyMode("Int::rel");
198  }
199  } else {
200  switch (r.mode()) {
201  case RM_EQV:
203  ::post(home,x0,x1,r.var())));
204  break;
205  case RM_IMP:
207  ::post(home,x0,x1,r.var())));
208  break;
209  case RM_PMI:
211  ::post(home,x0,x1,r.var())));
212  break;
213  default: throw UnknownReifyMode("Int::rel");
214  }
215  }
216  break;
217  case IRT_NQ:
218  {
219  NegBoolView n(r.var());
220  if (vbd(ipl) == IPL_BND) {
221  switch (r.mode()) {
222  case RM_EQV:
224  ::post(home,x0,x1,n)));
225  break;
226  case RM_IMP:
228  ::post(home,x0,x1,n)));
229  break;
230  case RM_PMI:
232  ::post(home,x0,x1,n)));
233  break;
234  default: throw UnknownReifyMode("Int::rel");
235  }
236  } else {
237  switch (r.mode()) {
238  case RM_EQV:
240  ::post(home,x0,x1,n)));
241  break;
242  case RM_IMP:
244  ::post(home,x0,x1,n)));
245  break;
246  case RM_PMI:
248  ::post(home,x0,x1,n)));
249  break;
250  default: throw UnknownReifyMode("Int::rel");
251  }
252  }
253  }
254  break;
255  case IRT_GQ:
256  std::swap(x0,x1); // Fall through
257  case IRT_LQ:
258  switch (r.mode()) {
259  case RM_EQV:
261  ::post(home,x0,x1,r.var())));
262  break;
263  case RM_IMP:
265  ::post(home,x0,x1,r.var())));
266  break;
267  case RM_PMI:
269  ::post(home,x0,x1,r.var())));
270  break;
271  default: throw UnknownReifyMode("Int::rel");
272  }
273  break;
274  case IRT_LE:
275  std::swap(x0,x1); // Fall through
276  case IRT_GR:
277  {
278  NegBoolView n(r.var());
279  switch (r.mode()) {
280  case RM_EQV:
282  ::post(home,x0,x1,n)));
283  break;
284  case RM_IMP:
286  ::post(home,x0,x1,n)));
287  break;
288  case RM_PMI:
290  ::post(home,x0,x1,n)));
291  break;
292  default: throw UnknownReifyMode("Int::rel");
293  }
294  }
295  break;
296  default:
297  throw UnknownRelation("Int::rel");
298  }
299  }
300 
301  void
302  rel(Home home, IntVar x, IntRelType irt, int n, Reify r,
303  IntPropLevel ipl) {
304  using namespace Int;
305  Limits::check(n,"Int::rel");
306  GECODE_POST;
307  switch (irt) {
308  case IRT_EQ:
309  if ((vbd(ipl) == IPL_DOM) || (vbd(ipl) == IPL_DEF)) {
310  switch (r.mode()) {
311  case RM_EQV:
313  ::post(home,x,n,r.var())));
314  break;
315  case RM_IMP:
317  ::post(home,x,n,r.var())));
318  break;
319  case RM_PMI:
321  ::post(home,x,n,r.var())));
322  break;
323  default: throw UnknownReifyMode("Int::rel");
324  }
325  } else {
326  switch (r.mode()) {
327  case RM_EQV:
329  ::post(home,x,n,r.var())));
330  break;
331  case RM_IMP:
333  ::post(home,x,n,r.var())));
334  break;
335  case RM_PMI:
337  ::post(home,x,n,r.var())));
338  break;
339  default: throw UnknownReifyMode("Int::rel");
340  }
341  }
342  break;
343  case IRT_NQ:
344  {
345  NegBoolView nb(r.var());
346  if (vbd(ipl) == IPL_BND) {
347  switch (r.mode()) {
348  case RM_EQV:
350  ::post(home,x,n,nb)));
351  break;
352  case RM_IMP:
354  ::post(home,x,n,nb)));
355  break;
356  case RM_PMI:
358  ::post(home,x,n,nb)));
359  break;
360  default: throw UnknownReifyMode("Int::rel");
361  }
362  } else {
363  switch (r.mode()) {
364  case RM_EQV:
366  ::post(home,x,n,nb)));
367  break;
368  case RM_IMP:
370  ::post(home,x,n,nb)));
371  break;
372  case RM_PMI:
374  ::post(home,x,n,nb)));
375  break;
376  default: throw UnknownReifyMode("Int::rel");
377  }
378  }
379  }
380  break;
381  case IRT_LE:
382  n--; // Fall through
383  case IRT_LQ:
384  switch (r.mode()) {
385  case RM_EQV:
387  ::post(home,x,n,r.var())));
388  break;
389  case RM_IMP:
391  ::post(home,x,n,r.var())));
392  break;
393  case RM_PMI:
395  ::post(home,x,n,r.var())));
396  break;
397  default: throw UnknownReifyMode("Int::rel");
398  }
399  break;
400  case IRT_GQ:
401  n--; // Fall through
402  case IRT_GR:
403  {
404  NegBoolView nb(r.var());
405  switch (r.mode()) {
406  case RM_EQV:
408  ::post(home,x,n,nb)));
409  break;
410  case RM_IMP:
412  ::post(home,x,n,nb)));
413  break;
414  case RM_PMI:
416  ::post(home,x,n,nb)));
417  break;
418  default: throw UnknownReifyMode("Int::rel");
419  }
420  }
421  break;
422  default:
423  throw UnknownRelation("Int::rel");
424  }
425  }
426 
427  void
428  rel(Home home, const IntVarArgs& x, IntRelType irt,
429  IntPropLevel ipl) {
430  using namespace Int;
431  GECODE_POST;
432  if ((irt != IRT_NQ) && (x.size() < 2))
433  return;
434  switch (irt) {
435  case IRT_EQ:
436  {
437  ViewArray<IntView> xv(home,x);
438  if ((vbd(ipl) == IPL_DOM) || (vbd(ipl) == IPL_DEF)) {
440  } else {
442  }
443  }
444  break;
445  case IRT_NQ:
446  {
447  ViewArray<IntView> y(home,x);
449  }
450  break;
451  case IRT_LE:
452  {
453  ViewArray<IntView> y(home,x);
455  }
456  break;
457  case IRT_LQ:
458  {
459  ViewArray<IntView> y(home,x);
461  }
462  break;
463  case IRT_GR:
464  {
465  ViewArray<IntView> y(home,x.size());
466  for (int i=0; i<x.size(); i++)
467  y[i] = x[x.size()-1-i];
469  }
470  break;
471  case IRT_GQ:
472  {
473  ViewArray<IntView> y(home,x.size());
474  for (int i=0; i<x.size(); i++)
475  y[i] = x[x.size()-1-i];
477  }
478  break;
479  default:
480  throw UnknownRelation("Int::rel");
481  }
482  }
483 
484  void
485  rel(Home home, const IntVarArgs& x, IntRelType irt, const IntVarArgs& y,
486  IntPropLevel ipl) {
487  using namespace Int;
488  GECODE_POST;
489 
490  switch (irt) {
491  case IRT_GR:
492  {
493  ViewArray<IntView> xv(home,x), yv(home,y);
495  ::post(home,yv,xv,true)));
496  }
497  break;
498  case IRT_LE:
499  {
500  ViewArray<IntView> xv(home,x), yv(home,y);
502  ::post(home,xv,yv,true)));
503  }
504  break;
505  case IRT_GQ:
506  {
507  ViewArray<IntView> xv(home,x), yv(home,y);
509  ::post(home,yv,xv,false)));
510  }
511  break;
512  case IRT_LQ:
513  {
514  ViewArray<IntView> xv(home,x), yv(home,y);
516  ::post(home,xv,yv,false)));
517  }
518  break;
519  case IRT_EQ:
520  if (x.size() != y.size()) {
521  home.fail();
522  } else if ((vbd(ipl) == IPL_DOM) || (vbd(ipl) == IPL_DEF))
523  for (int i=0; i<x.size(); i++) {
525  ::post(home,x[i],y[i])));
526  }
527  else
528  for (int i=0; i<x.size(); i++) {
530  ::post(home,x[i],y[i])));
531  }
532  break;
533  case IRT_NQ:
534  {
535  ViewArray<IntView> xv(home,x), yv(home,y);
537  ::post(home,xv,yv)));
538  }
539  break;
540  default:
541  throw UnknownRelation("Int::rel");
542  }
543  }
544 
545  namespace {
546 
549  viewarray(Space& home, const IntArgs& x) {
550  ViewArray<Int::ConstIntView> xv(home, x.size());
551  for (int i=0; i<x.size(); i++) {
552  Int::Limits::check(x[i],"Int::rel");
553  xv[i] = Int::ConstIntView(x[i]);
554  }
555  return xv;
556  }
557 
558  }
559 
560  void
561  rel(Home home, const IntVarArgs& x, IntRelType irt, const IntArgs& y,
562  IntPropLevel) {
563  using namespace Int;
564  GECODE_POST;
565 
566  switch (irt) {
567  case IRT_GR:
568  {
569  ViewArray<IntView> xv(home,x);
570  ViewArray<ConstIntView> yv(viewarray(home,y));
572  ::post(home,yv,xv,true)));
573  }
574  break;
575  case IRT_LE:
576  {
577  ViewArray<IntView> xv(home,x);
578  ViewArray<ConstIntView> yv(viewarray(home,y));
580  ::post(home,xv,yv,true)));
581  }
582  break;
583  case IRT_GQ:
584  {
585  ViewArray<IntView> xv(home,x);
586  ViewArray<ConstIntView> yv(viewarray(home,y));
588  ::post(home,yv,xv,false)));
589  }
590  break;
591  case IRT_LQ:
592  {
593  ViewArray<IntView> xv(home,x);
594  ViewArray<ConstIntView> yv(viewarray(home,y));
596  ::post(home,xv,yv,false)));
597  }
598  break;
599  case IRT_EQ:
600  if (x.size() != y.size()) {
601  home.fail();
602  } else {
603  for (int i=0; i<x.size(); i++)
604  GECODE_ME_FAIL(IntView(x[i]).eq(home,y[i]));
605  }
606  break;
607  case IRT_NQ:
608  {
609  ViewArray<IntView> xv(home,x);
610  ViewArray<ConstIntView> yv(viewarray(home,y));
612  ::post(home,xv,yv)));
613  }
614  break;
615  default:
616  throw UnknownRelation("Int::rel");
617  }
618  }
619 
620  void
621  rel(Home home, const IntArgs& x, IntRelType irt, const IntVarArgs& y,
622  IntPropLevel ipl) {
623  rel(home,y,irt,x,ipl);
624  }
625 
626 }
627 
628 // STATISTICS: int-post
Bounds propagation.
Definition: int.hh:978
ModEvent nq(Space &home, int n)
Restrict domain values to be different from n.
Definition: int.hpp:157
ModEvent gr(Space &home, int n)
Restrict domain values to be greater than n.
Definition: int.hpp:148
IntPropLevel vbd(IntPropLevel ipl)
Extract value, bounds, or domain propagation from propagation level.
Definition: ipl.hpp:37
Inverse implication for reification.
Definition: int.hh:869
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1569
Binary domain consistent equality propagator.
Definition: rel.hh:67
ReifyMode mode(void) const
Return reification mode.
Definition: reify.hpp:56
Negated Boolean view.
Definition: view.hpp:1574
ModEvent eq(Space &home, int n)
Restrict domain values to be equal to n.
Definition: int.hpp:166
Less or equal ( )
Definition: int.hh:928
Reified less or equal with integer propagator.
Definition: rel.hh:575
Lexical disequality propagator.
Definition: rel.hh:657
Greater ( )
Definition: int.hh:931
n-ary domain consistent equality propagator
Definition: rel.hh:164
Computation spaces.
Definition: core.hpp:1701
Greater or equal ( )
Definition: int.hh:930
Reified less or equal propagator.
Definition: rel.hh:548
Nary disequality propagator.
Definition: rel.hh:318
Exception: Unknown relation passed as argument
Definition: exception.hpp:87
ModEvent le(Space &home, int n)
Restrict domain values to be less than n.
Definition: int.hpp:130
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Equality ( )
Definition: int.hh:926
Gecode::IntArgs i({1, 2, 3, 4})
IntRelType
Relation types for integers.
Definition: int.hh:925
ModEvent lq(Space &home, int n)
Restrict domain values to be less or equal than n.
Definition: int.hpp:121
Simple propagation levels.
Definition: int.hh:976
Reified binary domain consistent equality propagator.
Definition: rel.hh:346
Reification specification.
Definition: int.hh:876
Binary bounds consistent equality propagator.
Definition: rel.hh:133
Less or equal propagator.
Definition: rel.hh:493
Reified binary bounds consistent equality propagator.
Definition: rel.hh:372
Less ( )
Definition: int.hh:929
Passing integer variables.
Definition: int.hh:656
n-ary less and less or equal propagator
Definition: rel.hh:230
Passing integer arguments.
Definition: int.hh:628
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
Reified bounds consistent equality with integer propagator.
Definition: rel.hh:425
IntPropLevel
Propagation levels for integer propagators.
Definition: int.hh:974
Constant integer view.
Definition: view.hpp:851
Integer view for integer variables.
Definition: view.hpp:129
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:767
Lexical ordering propagator.
Definition: rel.hh:623
Integer variables.
Definition: int.hh:371
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Definition: rel.cpp:43
Domain propagation Options: basic versus advanced propagation.
Definition: int.hh:979
BoolVar var(void) const
Return Boolean control variable.
Definition: reify.hpp:48
ModEvent gq(Space &home, int n)
Restrict domain values to be greater or equal than n.
Definition: int.hpp:139
Binary disequality propagator.
Definition: rel.hh:460
Post propagator for SetVar x
Definition: set.hh:767
#define GECODE_ME_FAIL(me)
Check whether modification event me is failed, and fail space home.
Definition: macros.hpp:77
void fail(void)
Mark space as failed.
Definition: core.hpp:3966
n-ary bounds consistent equality propagator
Definition: rel.hh:196
Exception: Unknown reification mode passed as argument
Definition: exception.hpp:115
Gecode toplevel namespace
Implication for reification.
Definition: int.hh:862
Disequality ( )
Definition: int.hh:927
Less propagator.
Definition: rel.hh:517
#define GECODE_POST
Check for failure in a constraint post function.
Definition: macros.hpp:40
Reified domain consistent equality with integer propagator.
Definition: rel.hh:398
void check(int n, const char *l)
Check whether n is in range, otherwise throw out of limits with information l.
Definition: limits.hpp:46
Home class for posting propagators
Definition: core.hpp:853
#define GECODE_ES_FAIL(es)
Check whether execution status es is failed, and fail space home.
Definition: macros.hpp:103
TFE post(PropagatorGroup g)
Only post functions (but not propagators) from g are considered.
Definition: filter.cpp:138
Equivalence for reification (default)
Definition: int.hh:855
IntRelType swap(IntRelType irt)
Return swapped relation type of irt.
Definition: irt.hpp:37