Generated on Sat Feb 7 2015 02:01:16 for Gecode by doxygen 1.8.9.1
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: 2011-12-12 16:21:39 +0100 (Mon, 12 Dec 2011) $ by $Author: schulte $
11  * $Revision: 12489 $
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, IntConLevel) {
49  Limits::check(n,"Int::rel");
50  if (home.failed()) return;
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, IntConLevel) {
65  Limits::check(n,"Int::rel");
66  if (home.failed()) return;
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, IntConLevel icl) {
105  if (home.failed()) return;
106  switch (irt) {
107  case IRT_EQ:
108  if ((icl == ICL_DOM) || (icl == ICL_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  IntConLevel icl) {
132  if (home.failed()) return;
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 ((icl == ICL_DOM) || (icl == ICL_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  IntConLevel icl) {
181  if (home.failed()) return;
182  switch (irt) {
183  case IRT_EQ:
184  if ((icl == ICL_DOM) || (icl == ICL_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 (icl == ICL_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  IntConLevel icl) {
305  Limits::check(n,"Int::rel");
306  if (home.failed()) return;
307  switch (irt) {
308  case IRT_EQ:
309  if ((icl == ICL_DOM) || (icl == ICL_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 (icl == ICL_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  IntConLevel icl) {
430  if (home.failed() || ((irt != IRT_NQ) && (x.size() < 2)))
431  return;
432  switch (irt) {
433  case IRT_EQ:
434  {
435  ViewArray<IntView> xv(home,x);
436  if ((icl == ICL_DOM) || (icl == ICL_DEF)) {
438  } else {
440  }
441  }
442  break;
443  case IRT_NQ:
444  {
445  ViewArray<IntView> y(home,x);
447  }
448  break;
449  case IRT_LE:
450  {
451  ViewArray<IntView> y(home,x);
453  }
454  break;
455  case IRT_LQ:
456  {
457  ViewArray<IntView> y(home,x);
459  }
460  break;
461  case IRT_GR:
462  {
463  ViewArray<IntView> y(home,x.size());
464  for (int i=x.size(); i--; )
465  y[i] = x[x.size()-1-i];
467  }
468  for (int i=x.size()-1; i--; )
469  GECODE_ES_FAIL(Rel::Le<IntView>::post(home,x[i+1],x[i]));
470  break;
471  case IRT_GQ:
472  {
473  ViewArray<IntView> y(home,x.size());
474  for (int 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  IntConLevel icl) {
487  if (home.failed()) return;
488 
489  switch (irt) {
490  case IRT_GR:
491  {
492  ViewArray<IntView> xv(home,x), yv(home,y);
494  }
495  break;
496  case IRT_LE:
497  {
498  ViewArray<IntView> xv(home,x), yv(home,y);
500  }
501  break;
502  case IRT_GQ:
503  {
504  ViewArray<IntView> xv(home,x), yv(home,y);
505  GECODE_ES_FAIL(Rel::LexLqLe<IntView>::post(home,yv,xv,false));
506  }
507  break;
508  case IRT_LQ:
509  {
510  ViewArray<IntView> xv(home,x), yv(home,y);
511  GECODE_ES_FAIL(Rel::LexLqLe<IntView>::post(home,xv,yv,false));
512  }
513  break;
514  case IRT_EQ:
515  if (x.size() != y.size()) {
516  home.fail();
517  } else if ((icl == ICL_DOM) || (icl == ICL_DEF))
518  for (int i=x.size(); i--; ) {
520  ::post(home,x[i],y[i])));
521  }
522  else
523  for (int i=x.size(); i--; ) {
525  ::post(home,x[i],y[i])));
526  }
527  break;
528  case IRT_NQ:
529  {
530  ViewArray<IntView> xv(home,x), yv(home,y);
532  }
533  break;
534  default:
535  throw UnknownRelation("Int::rel");
536  }
537  }
538 
539 }
540 
541 // STATISTICS: int-post
bool failed(void) const
Check whether corresponding space is failed.
Definition: core.hpp:3446
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
IntConLevel
Consistency levels for integer propagators.
Definition: int.hh:937
Inverse implication for reification.
Definition: int.hh:847
ReifyMode mode(void) const
Return reification mode.
Definition: reify.hpp:60
void post(Home home, Term *t, int n, FloatRelType frt, FloatVal c)
Post propagator for linear constraint over floats.
Definition: post.cpp:228
Binary domain consistent equality propagator.
Definition: rel.hh:71
BoolVar var(void) const
Return Boolean control variable.
Definition: reify.hpp:52
Negated Boolean view.
Definition: view.hpp:1503
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1662
ModEvent eq(Space &home, int n)
Restrict domain values to be equal to n.
Definition: int.hpp:160
Less or equal ( )
Definition: int.hh:906
Reified less or equal with integer propagator.
Definition: rel.hh:549
Lexical disequality propagator.
Definition: rel.hh:628
Greater ( )
Definition: int.hh:909
n-ary domain consistent equality propagator
Definition: rel.hh:138
Greater or equal ( )
Definition: int.hh:908
Reified less or equal propagator.
Definition: rel.hh:522
Nary disequality propagator.
Definition: rel.hh:290
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:904
IntRelType
Relation types for integers.
Definition: int.hh:903
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
Reified binary domain consistent equality propagator.
Definition: rel.hh:318
Reification specification.
Definition: int.hh:854
Binary bounds consistent equality propagator.
Definition: rel.hh:107
Less or equal propagator.
Definition: rel.hh:465
Reified binary bounds consistent equality propagator.
Definition: rel.hh:344
Less ( )
Definition: int.hh:907
Passing integer variables.
Definition: int.hh:636
n-ary less and less or equal propagator
Definition: rel.hh:204
Reified bounds consistent equality with integer propagator.
Definition: rel.hh:397
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:597
Integer variables.
Definition: int.hh:350
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Definition: rel.cpp:47
The default consistency for a constraint.
Definition: int.hh:941
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:432
#define GECODE_ME_FAIL(me)
Check whether modification event me is failed, and fail space home.
Definition: macros.hpp:70
void fail(void)
Mark space as failed.
Definition: core.hpp:3437
n-ary bounds consistent equality propagator
Definition: rel.hh:170
Bounds propagation or consistency.
Definition: int.hh:939
Exception: Unknown reification mode passed as argument
Definition: exception.hpp:119
Gecode toplevel namespace
Implication for reification.
Definition: int.hh:840
Disequality ( )
Definition: int.hh:905
Less propagator.
Definition: rel.hh:490
Reified domain consistent equality with integer propagator.
Definition: rel.hh:370
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:717
#define GECODE_ES_FAIL(es)
Check whether execution status es is failed, and fail space home.
Definition: macros.hpp:96
Domain propagation or consistency.
Definition: int.hh:940
Equivalence for reification (default)
Definition: int.hh:833