Generated on Thu Mar 16 2017 03:24:16 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-05-23 22:18:23 +0200 (Mon, 23 May 2016) $ by $Author: schulte $
11  * $Revision: 15073 $
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  using namespace Int;
46 
47  void
48  rel(Home home, IntVar x0, IntRelType irt, int n, IntPropLevel) {
49  Limits::check(n,"Int::rel");
51  IntView x(x0);
52  switch (irt) {
53  case IRT_EQ: GECODE_ME_FAIL(x.eq(home,n)); break;
54  case IRT_NQ: GECODE_ME_FAIL(x.nq(home,n)); break;
55  case IRT_LQ: GECODE_ME_FAIL(x.lq(home,n)); break;
56  case IRT_LE: GECODE_ME_FAIL(x.le(home,n)); break;
57  case IRT_GQ: GECODE_ME_FAIL(x.gq(home,n)); break;
58  case IRT_GR: GECODE_ME_FAIL(x.gr(home,n)); break;
59  default: throw UnknownRelation("Int::rel");
60  }
61  }
62 
63  void
64  rel(Home home, const IntVarArgs& x, IntRelType irt, int n, IntPropLevel) {
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  GECODE_POST;
106  switch (irt) {
107  case IRT_EQ:
108  if ((vbd(ipl) == IPL_DOM) || (vbd(ipl) == IPL_DEF)) {
110  } else {
112  }
113  break;
114  case IRT_NQ:
115  GECODE_ES_FAIL(Rel::Nq<IntView>::post(home,x0,x1)); break;
116  case IRT_GQ:
117  std::swap(x0,x1); // Fall through
118  case IRT_LQ:
119  GECODE_ES_FAIL(Rel::Lq<IntView>::post(home,x0,x1)); break;
120  case IRT_GR:
121  std::swap(x0,x1); // Fall through
122  case IRT_LE:
123  GECODE_ES_FAIL(Rel::Le<IntView>::post(home,x0,x1)); break;
124  default:
125  throw UnknownRelation("Int::rel");
126  }
127  }
128 
129  void
130  rel(Home home, const IntVarArgs& x, IntRelType irt, IntVar y,
131  IntPropLevel ipl) {
132  GECODE_POST;
133  switch (irt) {
134  case IRT_EQ:
135  {
136  ViewArray<IntView> xv(home,x.size()+1);
137  xv[x.size()]=y;
138  for (int i=x.size(); i--; )
139  xv[i]=x[i];
140  if ((vbd(ipl) == IPL_DOM) || (vbd(ipl) == IPL_DEF)) {
142  } else {
144  }
145  }
146  break;
147  case IRT_NQ:
148  for (int i=x.size(); i--; ) {
150  }
151  break;
152  case IRT_GQ:
153  for (int i=x.size(); i--; ) {
155  }
156  break;
157  case IRT_LQ:
158  for (int i=x.size(); i--; ) {
160  }
161  break;
162  case IRT_GR:
163  for (int i=x.size(); i--; ) {
165  }
166  break;
167  case IRT_LE:
168  for (int i=x.size(); i--; ) {
170  }
171  break;
172  default:
173  throw UnknownRelation("Int::rel");
174  }
175  }
176 
177 
178  void
179  rel(Home home, IntVar x0, IntRelType irt, IntVar x1, Reify r,
180  IntPropLevel ipl) {
181  GECODE_POST;
182  switch (irt) {
183  case IRT_EQ:
184  if ((vbd(ipl) == IPL_DOM) || (vbd(ipl) == IPL_DEF)) {
185  switch (r.mode()) {
186  case RM_EQV:
188  ::post(home,x0,x1,r.var())));
189  break;
190  case RM_IMP:
192  ::post(home,x0,x1,r.var())));
193  break;
194  case RM_PMI:
196  ::post(home,x0,x1,r.var())));
197  break;
198  default: throw UnknownReifyMode("Int::rel");
199  }
200  } else {
201  switch (r.mode()) {
202  case RM_EQV:
204  ::post(home,x0,x1,r.var())));
205  break;
206  case RM_IMP:
208  ::post(home,x0,x1,r.var())));
209  break;
210  case RM_PMI:
212  ::post(home,x0,x1,r.var())));
213  break;
214  default: throw UnknownReifyMode("Int::rel");
215  }
216  }
217  break;
218  case IRT_NQ:
219  {
220  NegBoolView n(r.var());
221  if (vbd(ipl) == IPL_BND) {
222  switch (r.mode()) {
223  case RM_EQV:
225  ::post(home,x0,x1,n)));
226  break;
227  case RM_IMP:
229  ::post(home,x0,x1,n)));
230  break;
231  case RM_PMI:
233  ::post(home,x0,x1,n)));
234  break;
235  default: throw UnknownReifyMode("Int::rel");
236  }
237  } else {
238  switch (r.mode()) {
239  case RM_EQV:
241  ::post(home,x0,x1,n)));
242  break;
243  case RM_IMP:
245  ::post(home,x0,x1,n)));
246  break;
247  case RM_PMI:
249  ::post(home,x0,x1,n)));
250  break;
251  default: throw UnknownReifyMode("Int::rel");
252  }
253  }
254  }
255  break;
256  case IRT_GQ:
257  std::swap(x0,x1); // Fall through
258  case IRT_LQ:
259  switch (r.mode()) {
260  case RM_EQV:
262  ::post(home,x0,x1,r.var())));
263  break;
264  case RM_IMP:
266  ::post(home,x0,x1,r.var())));
267  break;
268  case RM_PMI:
270  ::post(home,x0,x1,r.var())));
271  break;
272  default: throw UnknownReifyMode("Int::rel");
273  }
274  break;
275  case IRT_LE:
276  std::swap(x0,x1); // Fall through
277  case IRT_GR:
278  {
279  NegBoolView n(r.var());
280  switch (r.mode()) {
281  case RM_EQV:
283  ::post(home,x0,x1,n)));
284  break;
285  case RM_IMP:
287  ::post(home,x0,x1,n)));
288  break;
289  case RM_PMI:
291  ::post(home,x0,x1,n)));
292  break;
293  default: throw UnknownReifyMode("Int::rel");
294  }
295  }
296  break;
297  default:
298  throw UnknownRelation("Int::rel");
299  }
300  }
301 
302  void
303  rel(Home home, IntVar x, IntRelType irt, int n, Reify r,
304  IntPropLevel ipl) {
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  GECODE_POST;
431  if ((irt != IRT_NQ) && (x.size() < 2))
432  return;
433  switch (irt) {
434  case IRT_EQ:
435  {
436  ViewArray<IntView> xv(home,x);
437  if ((vbd(ipl) == IPL_DOM) || (vbd(ipl) == IPL_DEF)) {
439  } else {
441  }
442  }
443  break;
444  case IRT_NQ:
445  {
446  ViewArray<IntView> y(home,x);
448  }
449  break;
450  case IRT_LE:
451  {
452  ViewArray<IntView> y(home,x);
454  }
455  break;
456  case IRT_LQ:
457  {
458  ViewArray<IntView> y(home,x);
460  }
461  break;
462  case IRT_GR:
463  {
464  ViewArray<IntView> y(home,x.size());
465  for (int i=x.size(); i--; )
466  y[i] = x[x.size()-1-i];
468  }
469  for (int i=x.size()-1; i--; )
470  GECODE_ES_FAIL(Rel::Le<IntView>::post(home,x[i+1],x[i]));
471  break;
472  case IRT_GQ:
473  {
474  ViewArray<IntView> y(home,x.size());
475  for (int i=x.size(); i--; )
476  y[i] = x[x.size()-1-i];
478  }
479  break;
480  default:
481  throw UnknownRelation("Int::rel");
482  }
483  }
484 
485  void
486  rel(Home home, const IntVarArgs& x, IntRelType irt, const IntVarArgs& y,
487  IntPropLevel ipl) {
488  GECODE_POST;
489 
490  switch (irt) {
491  case IRT_GR:
492  {
493  ViewArray<IntView> xv(home,x), yv(home,y);
495  }
496  break;
497  case IRT_LE:
498  {
499  ViewArray<IntView> xv(home,x), yv(home,y);
501  }
502  break;
503  case IRT_GQ:
504  {
505  ViewArray<IntView> xv(home,x), yv(home,y);
506  GECODE_ES_FAIL(Rel::LexLqLe<IntView>::post(home,yv,xv,false));
507  }
508  break;
509  case IRT_LQ:
510  {
511  ViewArray<IntView> xv(home,x), yv(home,y);
512  GECODE_ES_FAIL(Rel::LexLqLe<IntView>::post(home,xv,yv,false));
513  }
514  break;
515  case IRT_EQ:
516  if (x.size() != y.size()) {
517  home.fail();
518  } else if ((vbd(ipl) == IPL_DOM) || (vbd(ipl) == IPL_DEF))
519  for (int i=x.size(); i--; ) {
521  ::post(home,x[i],y[i])));
522  }
523  else
524  for (int i=x.size(); i--; ) {
526  ::post(home,x[i],y[i])));
527  }
528  break;
529  case IRT_NQ:
530  {
531  ViewArray<IntView> xv(home,x), yv(home,y);
533  }
534  break;
535  default:
536  throw UnknownRelation("Int::rel");
537  }
538  }
539 
540 }
541 
542 // STATISTICS: int-post
Bounds propagation.
Definition: int.hh:945
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:848
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:907
Reified less or equal with integer propagator.
Definition: rel.hh:581
Lexical disequality propagator.
Definition: rel.hh:662
Greater ( )
Definition: int.hh:910
n-ary domain consistent equality propagator
Definition: rel.hh:168
Greater or equal ( )
Definition: int.hh:909
Reified less or equal propagator.
Definition: rel.hh:554
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:905
IntRelType
Relation types for integers.
Definition: int.hh:904
ModEvent lq(Space &home, int n)
Restrict domain values to be less or equal than n.
Definition: int.hpp:115
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
Simple propagation levels.
Definition: int.hh:943
Reified binary domain consistent equality propagator.
Definition: rel.hh:350
Reification specification.
Definition: int.hh:855
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:908
Passing integer variables.
Definition: int.hh:637
n-ary less and less or equal propagator
Definition: rel.hh:234
Reified bounds consistent equality with integer propagator.
Definition: rel.hh:429
IntPropLevel
Propagation levels for integer propagators.
Definition: int.hh:941
Integer view for integer variables.
Definition: view.hpp:129
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
Lexical ordering propagator.
Definition: rel.hh:629
Integer variables.
Definition: int.hh:351
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:946
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
#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:3958
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:841
Disequality ( )
Definition: int.hh:906
Less propagator.
Definition: rel.hh:522
#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:905
#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:834