Generated on Wed Jan 24 2018 21:22:26 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  * Last modified:
10  * $Date: 2016-11-08 17:23:24 +0100 (Tue, 08 Nov 2016) $ by $Author: schulte $
11  * $Revision: 15253 $
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 <gecode/int/rel.hh>
39 #include <gecode/int/bool.hh>
40 
41 #include <algorithm>
42 
43 namespace Gecode {
44 
45  void
46  rel(Home home, IntVar x0, IntRelType irt, int n, IntPropLevel) {
47  using namespace Int;
48  Limits::check(n,"Int::rel");
50  IntView x(x0);
51  switch (irt) {
52  case IRT_EQ: GECODE_ME_FAIL(x.eq(home,n)); break;
53  case IRT_NQ: GECODE_ME_FAIL(x.nq(home,n)); break;
54  case IRT_LQ: GECODE_ME_FAIL(x.lq(home,n)); break;
55  case IRT_LE: GECODE_ME_FAIL(x.le(home,n)); break;
56  case IRT_GQ: GECODE_ME_FAIL(x.gq(home,n)); break;
57  case IRT_GR: GECODE_ME_FAIL(x.gr(home,n)); break;
58  default: throw UnknownRelation("Int::rel");
59  }
60  }
61 
62  void
63  rel(Home home, const IntVarArgs& x, IntRelType irt, int n, IntPropLevel) {
64  using namespace Int;
65  Limits::check(n,"Int::rel");
67  switch (irt) {
68  case IRT_EQ:
69  for (int i=x.size(); i--; ) {
70  IntView xi(x[i]); GECODE_ME_FAIL(xi.eq(home,n));
71  }
72  break;
73  case IRT_NQ:
74  for (int i=x.size(); i--; ) {
75  IntView xi(x[i]); GECODE_ME_FAIL(xi.nq(home,n));
76  }
77  break;
78  case IRT_LQ:
79  for (int i=x.size(); i--; ) {
80  IntView xi(x[i]); GECODE_ME_FAIL(xi.lq(home,n));
81  }
82  break;
83  case IRT_LE:
84  for (int i=x.size(); i--; ) {
85  IntView xi(x[i]); GECODE_ME_FAIL(xi.le(home,n));
86  }
87  break;
88  case IRT_GQ:
89  for (int i=x.size(); i--; ) {
90  IntView xi(x[i]); GECODE_ME_FAIL(xi.gq(home,n));
91  }
92  break;
93  case IRT_GR:
94  for (int i=x.size(); i--; ) {
95  IntView xi(x[i]); GECODE_ME_FAIL(xi.gr(home,n));
96  }
97  break;
98  default:
99  throw UnknownRelation("Int::rel");
100  }
101  }
102 
103  void
104  rel(Home home, IntVar x0, IntRelType irt, IntVar x1, IntPropLevel ipl) {
105  using namespace Int;
106  GECODE_POST;
107  switch (irt) {
108  case IRT_EQ:
109  if ((vbd(ipl) == IPL_DOM) || (vbd(ipl) == IPL_DEF)) {
111  } else {
113  }
114  break;
115  case IRT_NQ:
116  GECODE_ES_FAIL((Rel::Nq<IntView,IntView>::post(home,x0,x1))); break;
117  case IRT_GQ:
118  std::swap(x0,x1); // Fall through
119  case IRT_LQ:
120  GECODE_ES_FAIL((Rel::Lq<IntView,IntView>::post(home,x0,x1))); break;
121  case IRT_GR:
122  std::swap(x0,x1); // Fall through
123  case IRT_LE:
124  GECODE_ES_FAIL((Rel::Le<IntView,IntView>::post(home,x0,x1))); break;
125  default:
126  throw UnknownRelation("Int::rel");
127  }
128  }
129 
130  void
131  rel(Home home, const IntVarArgs& x, IntRelType irt, IntVar y,
132  IntPropLevel ipl) {
133  using namespace Int;
134  GECODE_POST;
135  switch (irt) {
136  case IRT_EQ:
137  {
138  ViewArray<IntView> xv(home,x.size()+1);
139  xv[x.size()]=y;
140  for (int i=x.size(); i--; )
141  xv[i]=x[i];
142  if ((vbd(ipl) == IPL_DOM) || (vbd(ipl) == IPL_DEF)) {
144  } else {
146  }
147  }
148  break;
149  case IRT_NQ:
150  for (int i=x.size(); i--; ) {
152  }
153  break;
154  case IRT_GQ:
155  for (int i=x.size(); i--; ) {
157  }
158  break;
159  case IRT_LQ:
160  for (int i=x.size(); i--; ) {
162  }
163  break;
164  case IRT_GR:
165  for (int i=x.size(); i--; ) {
167  }
168  break;
169  case IRT_LE:
170  for (int i=x.size(); i--; ) {
172  }
173  break;
174  default:
175  throw UnknownRelation("Int::rel");
176  }
177  }
178 
179 
180  void
181  rel(Home home, IntVar x0, IntRelType irt, IntVar x1, Reify r,
182  IntPropLevel ipl) {
183  using namespace Int;
184  GECODE_POST;
185  switch (irt) {
186  case IRT_EQ:
187  if ((vbd(ipl) == IPL_DOM) || (vbd(ipl) == IPL_DEF)) {
188  switch (r.mode()) {
189  case RM_EQV:
191  ::post(home,x0,x1,r.var())));
192  break;
193  case RM_IMP:
195  ::post(home,x0,x1,r.var())));
196  break;
197  case RM_PMI:
199  ::post(home,x0,x1,r.var())));
200  break;
201  default: throw UnknownReifyMode("Int::rel");
202  }
203  } else {
204  switch (r.mode()) {
205  case RM_EQV:
207  ::post(home,x0,x1,r.var())));
208  break;
209  case RM_IMP:
211  ::post(home,x0,x1,r.var())));
212  break;
213  case RM_PMI:
215  ::post(home,x0,x1,r.var())));
216  break;
217  default: throw UnknownReifyMode("Int::rel");
218  }
219  }
220  break;
221  case IRT_NQ:
222  {
223  NegBoolView n(r.var());
224  if (vbd(ipl) == IPL_BND) {
225  switch (r.mode()) {
226  case RM_EQV:
228  ::post(home,x0,x1,n)));
229  break;
230  case RM_IMP:
232  ::post(home,x0,x1,n)));
233  break;
234  case RM_PMI:
236  ::post(home,x0,x1,n)));
237  break;
238  default: throw UnknownReifyMode("Int::rel");
239  }
240  } else {
241  switch (r.mode()) {
242  case RM_EQV:
244  ::post(home,x0,x1,n)));
245  break;
246  case RM_IMP:
248  ::post(home,x0,x1,n)));
249  break;
250  case RM_PMI:
252  ::post(home,x0,x1,n)));
253  break;
254  default: throw UnknownReifyMode("Int::rel");
255  }
256  }
257  }
258  break;
259  case IRT_GQ:
260  std::swap(x0,x1); // Fall through
261  case IRT_LQ:
262  switch (r.mode()) {
263  case RM_EQV:
265  ::post(home,x0,x1,r.var())));
266  break;
267  case RM_IMP:
269  ::post(home,x0,x1,r.var())));
270  break;
271  case RM_PMI:
273  ::post(home,x0,x1,r.var())));
274  break;
275  default: throw UnknownReifyMode("Int::rel");
276  }
277  break;
278  case IRT_LE:
279  std::swap(x0,x1); // Fall through
280  case IRT_GR:
281  {
282  NegBoolView n(r.var());
283  switch (r.mode()) {
284  case RM_EQV:
286  ::post(home,x0,x1,n)));
287  break;
288  case RM_IMP:
290  ::post(home,x0,x1,n)));
291  break;
292  case RM_PMI:
294  ::post(home,x0,x1,n)));
295  break;
296  default: throw UnknownReifyMode("Int::rel");
297  }
298  }
299  break;
300  default:
301  throw UnknownRelation("Int::rel");
302  }
303  }
304 
305  void
306  rel(Home home, IntVar x, IntRelType irt, int n, Reify r,
307  IntPropLevel ipl) {
308  using namespace Int;
309  Limits::check(n,"Int::rel");
310  GECODE_POST;
311  switch (irt) {
312  case IRT_EQ:
313  if ((vbd(ipl) == IPL_DOM) || (vbd(ipl) == IPL_DEF)) {
314  switch (r.mode()) {
315  case RM_EQV:
317  ::post(home,x,n,r.var())));
318  break;
319  case RM_IMP:
321  ::post(home,x,n,r.var())));
322  break;
323  case RM_PMI:
325  ::post(home,x,n,r.var())));
326  break;
327  default: throw UnknownReifyMode("Int::rel");
328  }
329  } else {
330  switch (r.mode()) {
331  case RM_EQV:
333  ::post(home,x,n,r.var())));
334  break;
335  case RM_IMP:
337  ::post(home,x,n,r.var())));
338  break;
339  case RM_PMI:
341  ::post(home,x,n,r.var())));
342  break;
343  default: throw UnknownReifyMode("Int::rel");
344  }
345  }
346  break;
347  case IRT_NQ:
348  {
349  NegBoolView nb(r.var());
350  if (vbd(ipl) == IPL_BND) {
351  switch (r.mode()) {
352  case RM_EQV:
354  ::post(home,x,n,nb)));
355  break;
356  case RM_IMP:
358  ::post(home,x,n,nb)));
359  break;
360  case RM_PMI:
362  ::post(home,x,n,nb)));
363  break;
364  default: throw UnknownReifyMode("Int::rel");
365  }
366  } else {
367  switch (r.mode()) {
368  case RM_EQV:
370  ::post(home,x,n,nb)));
371  break;
372  case RM_IMP:
374  ::post(home,x,n,nb)));
375  break;
376  case RM_PMI:
378  ::post(home,x,n,nb)));
379  break;
380  default: throw UnknownReifyMode("Int::rel");
381  }
382  }
383  }
384  break;
385  case IRT_LE:
386  n--; // Fall through
387  case IRT_LQ:
388  switch (r.mode()) {
389  case RM_EQV:
391  ::post(home,x,n,r.var())));
392  break;
393  case RM_IMP:
395  ::post(home,x,n,r.var())));
396  break;
397  case RM_PMI:
399  ::post(home,x,n,r.var())));
400  break;
401  default: throw UnknownReifyMode("Int::rel");
402  }
403  break;
404  case IRT_GQ:
405  n--; // Fall through
406  case IRT_GR:
407  {
408  NegBoolView nb(r.var());
409  switch (r.mode()) {
410  case RM_EQV:
412  ::post(home,x,n,nb)));
413  break;
414  case RM_IMP:
416  ::post(home,x,n,nb)));
417  break;
418  case RM_PMI:
420  ::post(home,x,n,nb)));
421  break;
422  default: throw UnknownReifyMode("Int::rel");
423  }
424  }
425  break;
426  default:
427  throw UnknownRelation("Int::rel");
428  }
429  }
430 
431  void
432  rel(Home home, const IntVarArgs& x, IntRelType irt,
433  IntPropLevel ipl) {
434  using namespace Int;
435  GECODE_POST;
436  if ((irt != IRT_NQ) && (x.size() < 2))
437  return;
438  switch (irt) {
439  case IRT_EQ:
440  {
441  ViewArray<IntView> xv(home,x);
442  if ((vbd(ipl) == IPL_DOM) || (vbd(ipl) == IPL_DEF)) {
444  } else {
446  }
447  }
448  break;
449  case IRT_NQ:
450  {
451  ViewArray<IntView> y(home,x);
453  }
454  break;
455  case IRT_LE:
456  {
457  ViewArray<IntView> y(home,x);
459  }
460  break;
461  case IRT_LQ:
462  {
463  ViewArray<IntView> y(home,x);
465  }
466  break;
467  case IRT_GR:
468  {
469  ViewArray<IntView> y(home,x.size());
470  for (int i=x.size(); i--; )
471  y[i] = x[x.size()-1-i];
473  }
474  for (int i=x.size()-1; i--; )
476  break;
477  case IRT_GQ:
478  {
479  ViewArray<IntView> y(home,x.size());
480  for (int i=x.size(); i--; )
481  y[i] = x[x.size()-1-i];
483  }
484  break;
485  default:
486  throw UnknownRelation("Int::rel");
487  }
488  }
489 
490  void
491  rel(Home home, const IntVarArgs& x, IntRelType irt, const IntVarArgs& y,
492  IntPropLevel ipl) {
493  using namespace Int;
494  GECODE_POST;
495 
496  switch (irt) {
497  case IRT_GR:
498  {
499  ViewArray<IntView> xv(home,x), yv(home,y);
501  ::post(home,yv,xv,true)));
502  }
503  break;
504  case IRT_LE:
505  {
506  ViewArray<IntView> xv(home,x), yv(home,y);
508  ::post(home,xv,yv,true)));
509  }
510  break;
511  case IRT_GQ:
512  {
513  ViewArray<IntView> xv(home,x), yv(home,y);
515  ::post(home,yv,xv,false)));
516  }
517  break;
518  case IRT_LQ:
519  {
520  ViewArray<IntView> xv(home,x), yv(home,y);
522  ::post(home,xv,yv,false)));
523  }
524  break;
525  case IRT_EQ:
526  if (x.size() != y.size()) {
527  home.fail();
528  } else if ((vbd(ipl) == IPL_DOM) || (vbd(ipl) == IPL_DEF))
529  for (int i=x.size(); i--; ) {
531  ::post(home,x[i],y[i])));
532  }
533  else
534  for (int i=x.size(); i--; ) {
536  ::post(home,x[i],y[i])));
537  }
538  break;
539  case IRT_NQ:
540  {
541  ViewArray<IntView> xv(home,x), yv(home,y);
543  ::post(home,xv,yv)));
544  }
545  break;
546  default:
547  throw UnknownRelation("Int::rel");
548  }
549  }
550 
551  namespace {
552 
555  viewarray(Space& home, const IntArgs& x) {
556  ViewArray<Int::ConstIntView> xv(home, x.size());
557  for (int i = x.size(); i--; ) {
558  Int::Limits::check(x[i],"Int::rel");
559  xv[i] = Int::ConstIntView(x[i]);
560  }
561  return xv;
562  }
563 
564  }
565 
566  void
567  rel(Home home, const IntVarArgs& x, IntRelType irt, const IntArgs& y,
568  IntPropLevel) {
569  using namespace Int;
570  GECODE_POST;
571 
572  switch (irt) {
573  case IRT_GR:
574  {
575  ViewArray<IntView> xv(home,x);
576  ViewArray<ConstIntView> yv(viewarray(home,y));
578  ::post(home,yv,xv,true)));
579  }
580  break;
581  case IRT_LE:
582  {
583  ViewArray<IntView> xv(home,x);
584  ViewArray<ConstIntView> yv(viewarray(home,y));
586  ::post(home,xv,yv,true)));
587  }
588  break;
589  case IRT_GQ:
590  {
591  ViewArray<IntView> xv(home,x);
592  ViewArray<ConstIntView> yv(viewarray(home,y));
594  ::post(home,yv,xv,false)));
595  }
596  break;
597  case IRT_LQ:
598  {
599  ViewArray<IntView> xv(home,x);
600  ViewArray<ConstIntView> yv(viewarray(home,y));
602  ::post(home,xv,yv,false)));
603  }
604  break;
605  case IRT_EQ:
606  if (x.size() != y.size()) {
607  home.fail();
608  } else {
609  for (int i=x.size(); i--; )
610  GECODE_ME_FAIL(IntView(x[i]).eq(home,y[i]));
611  }
612  break;
613  case IRT_NQ:
614  {
615  ViewArray<IntView> xv(home,x);
616  ViewArray<ConstIntView> yv(viewarray(home,y));
618  ::post(home,xv,yv)));
619  }
620  break;
621  default:
622  throw UnknownRelation("Int::rel");
623  }
624  }
625 
626  void
627  rel(Home home, const IntArgs& x, IntRelType irt, const IntVarArgs& y,
628  IntPropLevel ipl) {
629  rel(home,y,irt,x,ipl);
630  }
631 
632 }
633 
634 // STATISTICS: int-post
Bounds propagation.
Definition: int.hh:959
ModEvent nq(Space &home, int n)
Restrict domain values to be different from n.
Definition: int.hpp:151
ModEvent gr(Space &home, int n)
Restrict domain values to be greater than n.
Definition: int.hpp:142
IntPropLevel vbd(IntPropLevel ipl)
Extract value, bounds, or domain propagation from propagation level.
Definition: ipl.hpp:41
Inverse implication for reification.
Definition: int.hh:850
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1669
Binary domain consistent equality propagator.
Definition: rel.hh:71
ReifyMode mode(void) const
Return reification mode.
Definition: reify.hpp:60
Negated Boolean view.
Definition: view.hpp:1503
ModEvent eq(Space &home, int n)
Restrict domain values to be equal to n.
Definition: int.hpp:160
Less or equal ( )
Definition: int.hh:909
Reified less or equal with integer propagator.
Definition: rel.hh:583
Lexical disequality propagator.
Definition: rel.hh:665
Greater ( )
Definition: int.hh:912
n-ary domain consistent equality propagator
Definition: rel.hh:168
Computation spaces.
Definition: core.hpp:1748
Greater or equal ( )
Definition: int.hh:911
Reified less or equal propagator.
Definition: rel.hh:556
Nary disequality propagator.
Definition: rel.hh:322
Exception: Unknown relation passed as argument
Definition: exception.hpp:91
ModEvent le(Space &home, int n)
Restrict domain values to be less than n.
Definition: int.hpp:124
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Equality ( )
Definition: int.hh:907
IntRelType
Relation types for integers.
Definition: int.hh:906
ModEvent lq(Space &home, int n)
Restrict domain values to be less or equal than n.
Definition: int.hpp:115
Simple propagation levels.
Definition: int.hh:957
Reified binary domain consistent equality propagator.
Definition: rel.hh:350
Reification specification.
Definition: int.hh:857
Binary bounds consistent equality propagator.
Definition: rel.hh:137
Less or equal propagator.
Definition: rel.hh:497
Reified binary bounds consistent equality propagator.
Definition: rel.hh:376
Less ( )
Definition: int.hh:910
Passing integer variables.
Definition: int.hh:639
n-ary less and less or equal propagator
Definition: rel.hh:234
Passing integer arguments.
Definition: int.hh:610
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:784
Reified bounds consistent equality with integer propagator.
Definition: rel.hh:429
IntPropLevel
Propagation levels for integer propagators.
Definition: int.hh:955
Constant integer view.
Definition: view.hpp:804
Integer view for integer variables.
Definition: view.hpp:129
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:784
Lexical ordering propagator.
Definition: rel.hh:631
Integer variables.
Definition: int.hh:353
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Definition: rel.cpp:47
Domain propagation Preferences: prefer speed or memory.
Definition: int.hh:960
BoolVar var(void) const
Return Boolean control variable.
Definition: reify.hpp:52
ModEvent gq(Space &home, int n)
Restrict domain values to be greater or equal than n.
Definition: int.hpp:133
Binary disequality propagator.
Definition: rel.hh:464
Post propagator for SetVar x
Definition: set.hh:784
#define GECODE_ME_FAIL(me)
Check whether modification event me is failed, and fail space home.
Definition: macros.hpp:81
void fail(void)
Mark space as failed.
Definition: core.hpp:4090
n-ary bounds consistent equality propagator
Definition: rel.hh:200
Exception: Unknown reification mode passed as argument
Definition: exception.hpp:119
Gecode toplevel namespace
Implication for reification.
Definition: int.hh:843
Disequality ( )
Definition: int.hh:908
Less propagator.
Definition: rel.hh:523
#define GECODE_POST
Check for failure in a constraint post function.
Definition: macros.hpp:44
Reified domain consistent equality with integer propagator.
Definition: rel.hh:402
void check(int n, const char *l)
Check whether n is in range, otherwise throw out of limits with information l.
Definition: limits.hpp:50
Home class for posting propagators
Definition: core.hpp:922
#define GECODE_ES_FAIL(es)
Check whether execution status es is failed, and fail space home.
Definition: macros.hpp:107
TFE post(PropagatorGroup g)
Only post functions (but not propagators) from g are considered.
Equivalence for reification (default)
Definition: int.hh:836
IntRelType swap(IntRelType irt)
Return swapped relation type of irt.
Definition: irt.hpp:41