Generated on Wed Sep 5 2012 18:51:44 for Gecode by doxygen 1.8.1.1
eq.hpp
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, 2004
8  *
9  * Last modified:
10  * $Date: 2011-08-09 02:04:53 +1000 (Tue, 09 Aug 2011) $ by $Author: schulte $
11  * $Revision: 12253 $
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 namespace Gecode { namespace Int { namespace Rel {
39 
40  /*
41  * Binary bounds consistent equality
42  *
43  */
44 
45  template<class View0, class View1>
47  EqBnd<View0,View1>::EqBnd(Home home, View0 x0, View1 x1)
48  : MixBinaryPropagator<View0,PC_INT_BND,View1,PC_INT_BND>(home,x0,x1) {}
49 
50  template<class View0, class View1>
52  EqBnd<View0,View1>::post(Home home, View0 x0, View1 x1){
53  if (x0.assigned()) {
54  GECODE_ME_CHECK(x1.eq(home,x0.val()));
55  } else if (x1.assigned()) {
56  GECODE_ME_CHECK(x0.eq(home,x1.val()));
57  } else if (!same(x0,x1)) {
58  GECODE_ME_CHECK(x0.lq(home,x1.max()));
59  GECODE_ME_CHECK(x1.lq(home,x0.max()));
60  GECODE_ME_CHECK(x0.gq(home,x1.min()));
61  GECODE_ME_CHECK(x1.gq(home,x0.min()));
62  (void) new (home) EqBnd<View0,View1>(home,x0,x1);
63  }
64  return ES_OK;
65  }
66 
67  template<class View0, class View1>
70  : MixBinaryPropagator<View0,PC_INT_BND,View1,PC_INT_BND>(home,share,p) {}
71 
72  template<class View0, class View1>
75  View0 x0, View1 x1)
76  : MixBinaryPropagator<View0,PC_INT_BND,View1,PC_INT_BND>(home,share,p,
77  x0,x1) {}
78 
79  template<class View0, class View1>
80  Actor*
81  EqBnd<View0,View1>::copy(Space& home, bool share) {
82  return new (home) EqBnd<View0,View1>(home,share,*this);
83  }
84 
85  template<class View0, class View1>
88  if (x0.assigned()) {
89  GECODE_ME_CHECK(x1.eq(home,x0.val()));
90  } else if (x1.assigned()) {
91  GECODE_ME_CHECK(x0.eq(home,x1.val()));
92  } else {
93  do {
94  GECODE_ME_CHECK(x0.gq(home,x1.min()));
95  GECODE_ME_CHECK(x1.gq(home,x0.min()));
96  } while (x0.min() != x1.min());
97  do {
98  GECODE_ME_CHECK(x0.lq(home,x1.max()));
99  GECODE_ME_CHECK(x1.lq(home,x0.max()));
100  } while (x0.max() != x1.max());
101  if (!x0.assigned())
102  return ES_FIX;
103  }
104  assert(x0.assigned() && x1.assigned());
105  return home.ES_SUBSUMED(*this);
106  }
107 
108  /*
109  * Binary domain consistent equality
110  *
111  */
112 
113  template<class View0, class View1>
115  EqDom<View0,View1>::EqDom(Home home, View0 x0, View1 x1)
116  : MixBinaryPropagator<View0,PC_INT_DOM,View1,PC_INT_DOM>(home,x0,x1) {}
117 
118  template<class View0, class View1>
119  ExecStatus
120  EqDom<View0,View1>::post(Home home, View0 x0, View1 x1){
121  if (x0.assigned()) {
122  GECODE_ME_CHECK(x1.eq(home,x0.val()));
123  } else if (x1.assigned()) {
124  GECODE_ME_CHECK(x0.eq(home,x1.val()));
125  } else if (!same(x0,x1)) {
126  GECODE_ME_CHECK(x0.lq(home,x1.max()));
127  GECODE_ME_CHECK(x1.lq(home,x0.max()));
128  GECODE_ME_CHECK(x0.gq(home,x1.min()));
129  GECODE_ME_CHECK(x1.gq(home,x0.min()));
130  (void) new (home) EqDom<View0,View1>(home,x0,x1);
131  }
132  return ES_OK;
133  }
134 
135 
136  template<class View0, class View1>
139  : MixBinaryPropagator<View0,PC_INT_DOM,View1,PC_INT_DOM>(home,share,p) {}
140 
141  template<class View0, class View1>
144  View0 x0, View1 x1)
145  : MixBinaryPropagator<View0,PC_INT_DOM,View1,PC_INT_DOM>(home,share,p,
146  x0,x1) {}
147 
148  template<class View0, class View1>
149  Actor*
150  EqDom<View0,View1>::copy(Space& home, bool share) {
151  return new (home) EqDom<View0,View1>(home,share,*this);
152  }
153 
154  template<class View0, class View1>
155  PropCost
156  EqDom<View0,View1>::cost(const Space&, const ModEventDelta& med) const {
157  if ((View0::me(med) == ME_INT_VAL) || (View1::me(med) == ME_INT_VAL))
159  else if ((View0::me(med) == ME_INT_DOM) || (View1::me(med) == ME_INT_DOM))
161  else
163  }
164 
165  template<class View0, class View1>
166  ExecStatus
168  if (x0.assigned()) {
169  GECODE_ME_CHECK(x1.eq(home,x0.val()));
170  return home.ES_SUBSUMED(*this);
171  }
172  if (x1.assigned()) {
173  GECODE_ME_CHECK(x0.eq(home,x1.val()));
174  return home.ES_SUBSUMED(*this);
175  }
176  if ((View0::me(med) != ME_INT_DOM) && (View1::me(med) != ME_INT_DOM)) {
177  do {
178  GECODE_ME_CHECK(x0.gq(home,x1.min()));
179  GECODE_ME_CHECK(x1.gq(home,x0.min()));
180  } while (x0.min() != x1.min());
181  do {
182  GECODE_ME_CHECK(x0.lq(home,x1.max()));
183  GECODE_ME_CHECK(x1.lq(home,x0.max()));
184  } while (x0.max() != x1.max());
185  if (x0.assigned())
186  return home.ES_SUBSUMED(*this);
187  if (x0.range() && x1.range())
188  return ES_FIX;
189  return home.ES_FIX_PARTIAL(*this,View0::med(ME_INT_DOM));
190  }
191  ViewRanges<View0> r0(x0);
192  GECODE_ME_CHECK(x1.inter_r(home,r0,shared(x0,x1)));
193  ViewRanges<View1> r1(x1);
194  GECODE_ME_CHECK(x0.narrow_r(home,r1,shared(x0,x1)));
195  if (x0.assigned())
196  return home.ES_SUBSUMED(*this);
197  return ES_FIX;
198  }
199 
200 
201 
202  /*
203  * Nary domain consistent equality
204  *
205  */
206 
207  template<class View>
210  : NaryPropagator<View,PC_INT_DOM>(home,x) {}
211 
212  template<class View>
213  ExecStatus
215  x.unique(home);
216  if (x.size() == 2) {
217  return EqDom<View,View>::post(home,x[0],x[1]);
218  } else if (x.size() > 2) {
219  int l = x[0].min();
220  int u = x[0].max();
221  for (int i=x.size(); i-- > 1; ) {
222  l = std::max(l,x[i].min());
223  u = std::min(u,x[i].max());
224  }
225  for (int i=x.size(); i--; ) {
226  GECODE_ME_CHECK(x[i].gq(home,l));
227  GECODE_ME_CHECK(x[i].lq(home,u));
228  }
229  (void) new (home) NaryEqDom<View>(home,x);
230  }
231  return ES_OK;
232  }
233 
234  template<class View>
237  : NaryPropagator<View,PC_INT_DOM>(home,share,p) {}
238 
239  template<class View>
240  Actor*
241  NaryEqDom<View>::copy(Space& home, bool share) {
242  return new (home) NaryEqDom<View>(home,share,*this);
243  }
244 
245  template<class View>
246  PropCost
247  NaryEqDom<View>::cost(const Space&, const ModEventDelta& med) const {
248  if (View::me(med) == ME_INT_VAL)
250  else
251  return PropCost::linear((View::me(med) == ME_INT_DOM) ?
252  PropCost::LO : PropCost::HI, x.size());
253  }
254 
255  template<class View>
256  ExecStatus
258  assert(x.size() > 2);
259 
260  ModEvent me = View::me(med);
261  if (me == ME_INT_VAL) {
262  // One of the variables is assigned
263  for (int i = 0; ; i++)
264  if (x[i].assigned()) {
265  int n = x[i].val();
266  x.move_lst(i);
267  for (int j = x.size(); j--; )
268  GECODE_ME_CHECK(x[j].eq(home,n));
269  return home.ES_SUBSUMED(*this);
270  }
271  GECODE_NEVER;
272  }
273 
274  if (me == ME_INT_BND) {
275  {
276  // One of the mins has changed
277  int mn = x[0].min();
278  restart_min:
279  for (int i = x.size(); i--; ) {
280  GECODE_ME_CHECK(x[i].gq(home,mn));
281  if (mn < x[i].min()) {
282  mn = x[i].min();
283  goto restart_min;
284  }
285  }
286  }
287  {
288  // One of the maxs has changed
289  int mx = x[0].max();
290  restart_max:
291  for (int i = x.size(); i--; ) {
292  GECODE_ME_CHECK(x[i].lq(home,mx));
293  if (mx > x[i].max()) {
294  mx = x[i].max();
295  goto restart_max;
296  }
297  }
298  }
299  if (x[0].assigned())
300  return home.ES_SUBSUMED(*this);
301  return home.ES_FIX_PARTIAL(*this,View::med(ME_INT_DOM));
302  }
303 
304  int n = x.size();
305 
306  Region re(home);
307  ViewRanges<View>* i_x = re.alloc<ViewRanges<View> >(n);
308  for (int i = n; i--; ) {
309  ViewRanges<View> i_xi(x[i]);
310  i_x[i] = i_xi;
311  }
312  Iter::Ranges::NaryInter r(re,i_x,n);
313 
314  if (!r())
315  return ES_FAILED;
316  ++r;
317  if (!r()) {
318  r.reset();
319  for (int i = n; i--; ) {
320  GECODE_ME_CHECK(x[i].gq(home,r.min()));
321  GECODE_ME_CHECK(x[i].lq(home,r.max()));
322  }
323  } else {
324  for (int i = n; i--; ) {
325  r.reset();
326  GECODE_ME_CHECK(x[i].narrow_r(home,r,false));
327  }
328  }
329  return ES_FIX;
330  }
331 
332 
333 
334  /*
335  * Nary bound consistent equality
336  *
337  */
338 
339  template<class View>
342  : NaryPropagator<View,PC_INT_BND>(home,x) {}
343 
344  template<class View>
345  ExecStatus
347  x.unique(home);
348  if (x.size() == 2) {
349  return EqBnd<View,View>::post(home,x[0],x[1]);
350  } else if (x.size() > 2) {
351  int l = x[0].min();
352  int u = x[0].max();
353  for (int i=x.size(); i-- > 1; ) {
354  l = std::max(l,x[i].min());
355  u = std::min(u,x[i].max());
356  }
357  for (int i=x.size(); i--; ) {
358  GECODE_ME_CHECK(x[i].gq(home,l));
359  GECODE_ME_CHECK(x[i].lq(home,u));
360  }
361  (void) new (home) NaryEqBnd<View>(home,x);
362  }
363  return ES_OK;
364  }
365 
366  template<class View>
369  : NaryPropagator<View,PC_INT_BND>(home,share,p) {}
370 
371  template<class View>
372  Actor*
373  NaryEqBnd<View>::copy(Space& home, bool share) {
374  return new (home) NaryEqBnd<View>(home,share,*this);
375  }
376 
377  template<class View>
378  PropCost
379  NaryEqBnd<View>::cost(const Space&, const ModEventDelta& med) const {
380  if (View::me(med) == ME_INT_VAL)
382  else
383  return PropCost::linear(PropCost::LO, x.size());
384  }
385 
386  template<class View>
387  ExecStatus
389  assert(x.size() > 2);
390  if (View::me(med) == ME_INT_VAL) {
391  // One of the variables is assigned
392  for (int i = 0; ; i++)
393  if (x[i].assigned()) {
394  int n = x[i].val();
395  x.move_lst(i);
396  for (int j = x.size(); j--; )
397  GECODE_ME_CHECK(x[j].eq(home,n));
398  return home.ES_SUBSUMED(*this);
399  }
400  GECODE_NEVER;
401  }
402 
403  int mn = x[0].min();
404  restart_min:
405  for (int i = x.size(); i--; ) {
406  GECODE_ME_CHECK(x[i].gq(home,mn));
407  if (mn < x[i].min()) {
408  mn = x[i].min();
409  goto restart_min;
410  }
411  }
412  int mx = x[0].max();
413  restart_max:
414  for (int i = x.size(); i--; ) {
415  GECODE_ME_CHECK(x[i].lq(home,mx));
416  if (mx > x[i].max()) {
417  mx = x[i].max();
418  goto restart_max;
419  }
420  }
421  return x[0].assigned() ? home.ES_SUBSUMED(*this) : ES_FIX;
422  }
423 
424 
425 
426  /*
427  * Reified domain consistent equality
428  *
429  */
430 
431  template<class View, class CtrlView>
433  ReEqDom<View,CtrlView>::ReEqDom(Home home, View x0, View x1, CtrlView b)
434  : ReBinaryPropagator<View,PC_INT_DOM,CtrlView>(home,x0,x1,b) {}
435 
436  template<class View, class CtrlView>
437  ExecStatus
438  ReEqDom<View,CtrlView>::post(Home home, View x0, View x1, CtrlView b) {
439  if (b.one())
440  return EqDom<View,View>::post(home,x0,x1);
441  if (b.zero())
442  return Nq<View>::post(home,x0,x1);
443  if (!same(x0,x1)) {
444  (void) new (home) ReEqDom(home,x0,x1,b);
445  } else {
446  GECODE_ME_CHECK(b.one(home));
447  }
448  return ES_OK;
449  }
450 
451 
452  template<class View, class CtrlView>
455  : ReBinaryPropagator<View,PC_INT_DOM,CtrlView>(home,share,p) {}
456 
457  template<class View, class CtrlView>
458  Actor*
459  ReEqDom<View,CtrlView>::copy(Space& home, bool share) {
460  return new (home) ReEqDom<View,CtrlView>(home,share,*this);
461  }
462 
463  template<class View, class CtrlView>
464  ExecStatus
466  if (b.one())
467  GECODE_REWRITE(*this,(EqDom<View,View>::post(home(*this),x0,x1)));
468  if (b.zero())
469  GECODE_REWRITE(*this,Nq<View>::post(home(*this),x0,x1));
470  switch (rtest_eq_dom(x0,x1)) {
471  case RT_TRUE:
472  GECODE_ME_CHECK(b.one_none(home)); return home.ES_SUBSUMED(*this);
473  case RT_FALSE:
474  GECODE_ME_CHECK(b.zero_none(home)); return home.ES_SUBSUMED(*this);
475  case RT_MAYBE:
476  break;
477  default: GECODE_NEVER;
478  }
479  return ES_FIX;
480  }
481 
482 
483 
484  /*
485  * Reified bounds consistent equality
486  *
487  */
488 
489  template<class View, class CtrlView>
491  ReEqBnd<View,CtrlView>::ReEqBnd(Home home, View x0, View x1, CtrlView b)
492  : ReBinaryPropagator<View,PC_INT_BND,CtrlView>(home,x0,x1,b) {}
493 
494  template<class View, class CtrlView>
495  ExecStatus
496  ReEqBnd<View,CtrlView>::post(Home home, View x0, View x1, CtrlView b){
497  if (b.one())
498  return EqBnd<View,View>::post(home,x0,x1);
499  if (b.zero())
500  return Nq<View>::post(home,x0,x1);
501  if (!same(x0,x1)) {
502  (void) new (home) ReEqBnd(home,x0,x1,b);
503  } else {
504  GECODE_ME_CHECK(b.one(home));
505  }
506  return ES_OK;
507  }
508 
509 
510  template<class View, class CtrlView>
513  : ReBinaryPropagator<View,PC_INT_BND,CtrlView>(home,share,p) {}
514 
515  template<class View, class CtrlView>
516  Actor*
517  ReEqBnd<View,CtrlView>::copy(Space& home, bool share) {
518  return new (home) ReEqBnd<View,CtrlView>(home,share,*this);
519  }
520 
521  template<class View, class CtrlView>
522  ExecStatus
524  if (b.one())
525  GECODE_REWRITE(*this,(EqBnd<View,View>::post(home(*this),x0,x1)));
526  if (b.zero())
527  GECODE_REWRITE(*this,Nq<View>::post(home(*this),x0,x1));
528  switch (rtest_eq_bnd(x0,x1)) {
529  case RT_TRUE:
530  GECODE_ME_CHECK(b.one_none(home)); return home.ES_SUBSUMED(*this);
531  case RT_FALSE:
532  GECODE_ME_CHECK(b.zero_none(home)); return home.ES_SUBSUMED(*this);
533  case RT_MAYBE:
534  break;
535  default: GECODE_NEVER;
536  }
537  return ES_FIX;
538  }
539 
540 
541 
542 
543  /*
544  * Reified domain consistent equality (one variable)
545  *
546  */
547 
548  template<class View, class CtrlView>
551  (Home home, View x, int c0, CtrlView b)
553 
554  template<class View, class CtrlView>
555  ExecStatus
556  ReEqDomInt<View,CtrlView>::post(Home home, View x, int c, CtrlView b) {
557  if (b.one()) {
558  GECODE_ME_CHECK(x.eq(home,c));
559  } else if (b.zero()) {
560  GECODE_ME_CHECK(x.nq(home,c));
561  } else if (x.assigned()) {
562  assert(b.none());
563  if (x.val() == c) {
564  GECODE_ME_CHECK(b.one_none(home));
565  } else {
566  GECODE_ME_CHECK(b.zero_none(home));
567  }
568  } else {
569  (void) new (home) ReEqDomInt(home,x,c,b);
570  }
571  return ES_OK;
572  }
573 
574 
575  template<class View, class CtrlView>
578  : ReUnaryPropagator<View,PC_INT_DOM,CtrlView>(home,share,p), c(p.c) {}
579 
580  template<class View, class CtrlView>
581  Actor*
583  return new (home) ReEqDomInt<View,CtrlView>(home,share,*this);
584  }
585 
586  template<class View, class CtrlView>
587  ExecStatus
589  if (b.one()) {
590  GECODE_ME_CHECK(x0.eq(home,c));
591  } else if (b.zero()) {
592  GECODE_ME_CHECK(x0.nq(home,c));
593  } else {
594  switch (rtest_eq_dom(x0,c)) {
595  case RT_TRUE:
596  GECODE_ME_CHECK(b.one_none(home)); break;
597  case RT_FALSE:
598  GECODE_ME_CHECK(b.zero_none(home)); break;
599  case RT_MAYBE:
600  return ES_FIX;
601  default: GECODE_NEVER;
602  }
603  }
604  return home.ES_SUBSUMED(*this);
605  }
606 
607 
608 
609 
610  /*
611  * Reified bounds consistent equality (one variable)
612  *
613  */
614 
615  template<class View, class CtrlView>
618  (Home home, View x, int c0, CtrlView b)
620 
621  template<class View, class CtrlView>
622  ExecStatus
623  ReEqBndInt<View,CtrlView>::post(Home home, View x, int c, CtrlView b) {
624  if (b.one()) {
625  GECODE_ME_CHECK(x.eq(home,c));
626  } else if (b.zero()) {
627  GECODE_ME_CHECK(x.nq(home,c));
628  } else if (x.assigned()) {
629  assert(b.none());
630  if (x.val() == c) {
631  GECODE_ME_CHECK(b.one_none(home));
632  } else {
633  GECODE_ME_CHECK(b.zero_none(home));
634  }
635  } else {
636  (void) new (home) ReEqBndInt(home,x,c,b);
637  }
638  return ES_OK;
639  }
640 
641 
642  template<class View, class CtrlView>
645  : ReUnaryPropagator<View,PC_INT_BND,CtrlView>(home,share,p), c(p.c) {}
646 
647  template<class View, class CtrlView>
648  Actor*
650  return new (home) ReEqBndInt<View,CtrlView>(home,share,*this);
651  }
652 
653  template<class View, class CtrlView>
654  ExecStatus
656  if (b.one()) {
657  GECODE_ME_CHECK(x0.eq(home,c));
658  } else if (b.zero()) {
659  GECODE_ME_CHECK(x0.nq(home,c));
660  } else {
661  switch (rtest_eq_bnd(x0,c)) {
662  case RT_TRUE:
663  GECODE_ME_CHECK(b.one_none(home)); break;
664  case RT_FALSE:
665  GECODE_ME_CHECK(b.zero_none(home)); break;
666  case RT_MAYBE:
667  return ES_FIX;
668  default: GECODE_NEVER;
669  }
670  }
671  return home.ES_SUBSUMED(*this);
672  }
673 
674 }}}
675 
676 // STATISTICS: int-prop