Generated on Sat Jun 2 2018 07:17:44 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=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=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=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=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=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=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=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=x.size(); i--; ) {
148  }
149  break;
150  case IRT_GQ:
151  for (int i=x.size(); i--; ) {
153  }
154  break;
155  case IRT_LQ:
156  for (int i=x.size(); i--; ) {
158  }
159  break;
160  case IRT_GR:
161  for (int i=x.size(); i--; ) {
163  }
164  break;
165  case IRT_LE:
166  for (int 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=x.size(); i--; )
467  y[i] = x[x.size()-1-i];
469  }
470  for (int i=x.size()-1; i--; )
472  break;
473  case IRT_GQ:
474  {
475  ViewArray<IntView> y(home,x.size());
476  for (int i=x.size(); i--; )
477  y[i] = x[x.size()-1-i];
479  }
480  break;
481  default:
482  throw UnknownRelation("Int::rel");
483  }
484  }
485 
486  void
487  rel(Home home, const IntVarArgs& x, IntRelType irt, const IntVarArgs& y,
488  IntPropLevel ipl) {
489  using namespace Int;
490  GECODE_POST;
491 
492  switch (irt) {
493  case IRT_GR:
494  {
495  ViewArray<IntView> xv(home,x), yv(home,y);
497  ::post(home,yv,xv,true)));
498  }
499  break;
500  case IRT_LE:
501  {
502  ViewArray<IntView> xv(home,x), yv(home,y);
504  ::post(home,xv,yv,true)));
505  }
506  break;
507  case IRT_GQ:
508  {
509  ViewArray<IntView> xv(home,x), yv(home,y);
511  ::post(home,yv,xv,false)));
512  }
513  break;
514  case IRT_LQ:
515  {
516  ViewArray<IntView> xv(home,x), yv(home,y);
518  ::post(home,xv,yv,false)));
519  }
520  break;
521  case IRT_EQ:
522  if (x.size() != y.size()) {
523  home.fail();
524  } else if ((vbd(ipl) == IPL_DOM) || (vbd(ipl) == IPL_DEF))
525  for (int i=x.size(); i--; ) {
527  ::post(home,x[i],y[i])));
528  }
529  else
530  for (int i=x.size(); i--; ) {
532  ::post(home,x[i],y[i])));
533  }
534  break;
535  case IRT_NQ:
536  {
537  ViewArray<IntView> xv(home,x), yv(home,y);
539  ::post(home,xv,yv)));
540  }
541  break;
542  default:
543  throw UnknownRelation("Int::rel");
544  }
545  }
546 
547  namespace {
548 
551  viewarray(Space& home, const IntArgs& x) {
552  ViewArray<Int::ConstIntView> xv(home, x.size());
553  for (int i = x.size(); i--; ) {
554  Int::Limits::check(x[i],"Int::rel");
555  xv[i] = Int::ConstIntView(x[i]);
556  }
557  return xv;
558  }
559 
560  }
561 
562  void
563  rel(Home home, const IntVarArgs& x, IntRelType irt, const IntArgs& y,
564  IntPropLevel) {
565  using namespace Int;
566  GECODE_POST;
567 
568  switch (irt) {
569  case IRT_GR:
570  {
571  ViewArray<IntView> xv(home,x);
572  ViewArray<ConstIntView> yv(viewarray(home,y));
574  ::post(home,yv,xv,true)));
575  }
576  break;
577  case IRT_LE:
578  {
579  ViewArray<IntView> xv(home,x);
580  ViewArray<ConstIntView> yv(viewarray(home,y));
582  ::post(home,xv,yv,true)));
583  }
584  break;
585  case IRT_GQ:
586  {
587  ViewArray<IntView> xv(home,x);
588  ViewArray<ConstIntView> yv(viewarray(home,y));
590  ::post(home,yv,xv,false)));
591  }
592  break;
593  case IRT_LQ:
594  {
595  ViewArray<IntView> xv(home,x);
596  ViewArray<ConstIntView> yv(viewarray(home,y));
598  ::post(home,xv,yv,false)));
599  }
600  break;
601  case IRT_EQ:
602  if (x.size() != y.size()) {
603  home.fail();
604  } else {
605  for (int i=x.size(); i--; )
606  GECODE_ME_FAIL(IntView(x[i]).eq(home,y[i]));
607  }
608  break;
609  case IRT_NQ:
610  {
611  ViewArray<IntView> xv(home,x);
612  ViewArray<ConstIntView> yv(viewarray(home,y));
614  ::post(home,xv,yv)));
615  }
616  break;
617  default:
618  throw UnknownRelation("Int::rel");
619  }
620  }
621 
622  void
623  rel(Home home, const IntArgs& x, IntRelType irt, const IntVarArgs& y,
624  IntPropLevel ipl) {
625  rel(home,y,irt,x,ipl);
626  }
627 
628 }
629 
630 // STATISTICS: int-post
Bounds propagation.
Definition: int.hh:953
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:844
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1653
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:1543
ModEvent eq(Space &home, int n)
Restrict domain values to be equal to n.
Definition: int.hpp:166
Less or equal ( )
Definition: int.hh:903
Reified less or equal with integer propagator.
Definition: rel.hh:579
Lexical disequality propagator.
Definition: rel.hh:661
Greater ( )
Definition: int.hh:906
n-ary domain consistent equality propagator
Definition: rel.hh:164
Computation spaces.
Definition: core.hpp:1701
Greater or equal ( )
Definition: int.hh:905
Reified less or equal propagator.
Definition: rel.hh:552
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
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Equality ( )
Definition: int.hh:901
IntRelType
Relation types for integers.
Definition: int.hh:900
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:951
Reified binary domain consistent equality propagator.
Definition: rel.hh:346
Reification specification.
Definition: int.hh:851
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:904
Passing integer variables.
Definition: int.hh:633
n-ary less and less or equal propagator
Definition: rel.hh:230
Passing integer arguments.
Definition: int.hh:604
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:765
Reified bounds consistent equality with integer propagator.
Definition: rel.hh:425
IntPropLevel
Propagation levels for integer propagators.
Definition: int.hh:949
Constant integer view.
Definition: view.hpp:828
Integer view for integer variables.
Definition: view.hpp:129
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:765
Lexical ordering propagator.
Definition: rel.hh:627
Integer variables.
Definition: int.hh:347
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:954
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:765
#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:3958
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:837
Disequality ( )
Definition: int.hh:902
Less propagator.
Definition: rel.hh:519
#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:830
IntRelType swap(IntRelType irt)
Return swapped relation type of irt.
Definition: irt.hpp:37