Generated on Mon Aug 27 2012 17:15:42 for Gecode by doxygen 1.8.1.2
int-nary.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, 2003
8  *
9  * Last modified:
10  * $Date: 2010-03-04 03:32:21 +1100 (Thu, 04 Mar 2010) $ by $Author: schulte $
11  * $Revision: 10364 $
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 
39 
40 namespace Gecode { namespace Int { namespace Linear {
41 
46  template<class P, class N>
47  forceinline bool
48  isunit(ViewArray<P>&, ViewArray<N>&) { return false; }
49  template<>
50  forceinline bool
52  template<>
53  forceinline bool
55  template<>
56  forceinline bool
58 
59  /*
60  * Linear propagators
61  *
62  */
63  template<class Val, class P, class N, PropCond pc>
66  : Propagator(home), x(x0), y(y0), c(c0) {
67  x.subscribe(home,*this,pc);
68  y.subscribe(home,*this,pc);
69  }
70 
71  template<class Val, class P, class N, PropCond pc>
74  : Propagator(home,share,p), c(p.c) {
75  x.update(home,share,p.x);
76  y.update(home,share,p.y);
77  }
78 
79  template<class Val, class P, class N, PropCond pc>
80  PropCost
81  Lin<Val,P,N,pc>::cost(const Space&, const ModEventDelta&) const {
82  return PropCost::linear(PropCost::LO, x.size()+y.size());
83  }
84 
85  template<class Val, class P, class N, PropCond pc>
86  forceinline size_t
88  x.cancel(home,*this,pc);
89  y.cancel(home,*this,pc);
90  (void) Propagator::dispose(home);
91  return sizeof(*this);
92  }
93 
94  /*
95  * Reified linear propagators
96  *
97  */
98  template<class Val, class P, class N, PropCond pc, class Ctrl>
101  (Home home, ViewArray<P>& x, ViewArray<N>& y, Val c, Ctrl b0)
102  : Lin<Val,P,N,pc>(home,x,y,c), b(b0) {
103  b.subscribe(home,*this,PC_INT_VAL);
104  }
105 
106  template<class Val, class P, class N, PropCond pc, class Ctrl>
109  (Space& home, bool share, ReLin<Val,P,N,pc,Ctrl>& p)
110  : Lin<Val,P,N,pc>(home,share,p) {
111  b.update(home,share,p.b);
112  }
113 
114  template<class Val, class P, class N, PropCond pc, class Ctrl>
115  forceinline size_t
117  b.cancel(home,*this,PC_BOOL_VAL);
118  (void) Lin<Val,P,N,pc>::dispose(home);
119  return sizeof(*this);
120  }
121 
122  /*
123  * Computing bounds
124  *
125  */
126 
127  template<class Val, class View>
128  void
129  bounds_p(ModEventDelta med, ViewArray<View>& x, Val& c, Val& sl, Val& su) {
130  int n = x.size();
131  if (IntView::me(med) == ME_INT_VAL) {
132  for (int i = n; i--; ) {
133  Val m = x[i].min();
134  if (x[i].assigned()) {
135  c -= m; x[i] = x[--n];
136  } else {
137  sl -= m; su -= x[i].max();
138  }
139  }
140  x.size(n);
141  } else {
142  for (int i = n; i--; ) {
143  sl -= x[i].min(); su -= x[i].max();
144  }
145  }
146  }
147 
148  template<class Val, class View>
149  void
150  bounds_n(ModEventDelta med, ViewArray<View>& y, Val& c, Val& sl, Val& su) {
151  int n = y.size();
152  if (IntView::me(med) == ME_INT_VAL) {
153  for (int i = n; i--; ) {
154  Val m = y[i].max();
155  if (y[i].assigned()) {
156  c += m; y[i] = y[--n];
157  } else {
158  sl += m; su += y[i].min();
159  }
160  }
161  y.size(n);
162  } else {
163  for (int i = n; i--; ) {
164  sl += y[i].max(); su += y[i].min();
165  }
166  }
167  }
168 
169 
170  template<class Val, class P, class N>
171  ExecStatus
173  ViewArray<P>& x, ViewArray<N>& y, Val& c) {
174  // Eliminate singletons
175  Val sl = 0;
176  Val su = 0;
177 
178  bounds_p<Val,P>(med, x, c, sl, su);
179  bounds_n<Val,N>(med, y, c, sl, su);
180 
181  if ((IntView::me(med) == ME_INT_VAL) && ((x.size() + y.size()) <= 1)) {
182  if (x.size() == 1) {
183  GECODE_ME_CHECK(x[0].eq(home,c));
184  return home.ES_SUBSUMED(p);
185  }
186  if (y.size() == 1) {
187  GECODE_ME_CHECK(y[0].eq(home,-c));
188  return home.ES_SUBSUMED(p);
189  }
190  return (c == static_cast<Val>(0)) ?
191  home.ES_SUBSUMED(p) : ES_FAILED;
192  }
193 
194  sl += c; su += c;
195 
196  const int mod_sl = 1;
197  const int mod_su = 2;
198 
199  int mod = mod_sl | mod_su;
200 
201  do {
202  if (mod & mod_sl) {
203  mod -= mod_sl;
204  // Propagate upper bound for positive variables
205  for (int i = x.size(); i--; ) {
206  const Val xi_max = x[i].max();
207  ModEvent me = x[i].lq(home,sl + x[i].min());
208  if (me_failed(me))
209  return ES_FAILED;
210  if (me_modified(me)) {
211  su += xi_max - x[i].max();
212  mod |= mod_su;
213  }
214  }
215  // Propagate lower bound for negative variables
216  for (int i = y.size(); i--; ) {
217  const Val yi_min = y[i].min();
218  ModEvent me = y[i].gq(home,y[i].max() - sl);
219  if (me_failed(me))
220  return ES_FAILED;
221  if (me_modified(me)) {
222  su += y[i].min() - yi_min;
223  mod |= mod_su;
224  }
225  }
226  }
227  if (mod & mod_su) {
228  mod -= mod_su;
229  // Propagate lower bound for positive variables
230  for (int i = x.size(); i--; ) {
231  const Val xi_min = x[i].min();
232  ModEvent me = x[i].gq(home,su + x[i].max());
233  if (me_failed(me))
234  return ES_FAILED;
235  if (me_modified(me)) {
236  sl += xi_min - x[i].min();
237  mod |= mod_sl;
238  }
239  }
240  // Propagate upper bound for negative variables
241  for (int i = y.size(); i--; ) {
242  const Val yi_max = y[i].max();
243  ModEvent me = y[i].lq(home,y[i].min() - su);
244  if (me_failed(me))
245  return ES_FAILED;
246  if (me_modified(me)) {
247  sl += y[i].max() - yi_max;
248  mod |= mod_sl;
249  }
250  }
251  }
252  } while (mod);
253 
254  return (sl == su) ? home.ES_SUBSUMED(p) : ES_FIX;
255  }
256 
257  /*
258  * Bound consistent linear equation
259  *
260  */
261 
262  template<class Val, class P, class N>
265  : Lin<Val,P,N,PC_INT_BND>(home,x,y,c) {}
266 
267  template<class Val, class P, class N>
268  ExecStatus
270  ViewArray<NoView> nva;
271  if (y.size() == 0) {
272  (void) new (home) Eq<Val,P,NoView>(home,x,nva,c);
273  } else if (x.size() == 0) {
274  (void) new (home) Eq<Val,N,NoView>(home,y,nva,-c);
275  } else {
276  (void) new (home) Eq<Val,P,N>(home,x,y,c);
277  }
278  return ES_OK;
279  }
280 
281 
282  template<class Val, class P, class N>
284  Eq<Val,P,N>::Eq(Space& home, bool share, Eq<Val,P,N>& p)
285  : Lin<Val,P,N,PC_INT_BND>(home,share,p) {}
286 
291  template<class Val, class P, class N>
294  return NULL;
295  }
296  template<class Val>
298  eqtobin(Space& home, bool share, Propagator& p,
300  assert(x.size() == 2);
301  return new (home) EqBin<Val,IntView,IntView>
302  (home,share,p,x[0],x[1],c);
303  }
304  template<class Val>
306  eqtobin(Space& home, bool share, Propagator& p,
308  assert(y.size() == 2);
309  return new (home) EqBin<Val,IntView,IntView>
310  (home,share,p,y[0],y[1],-c);
311  }
312  template<class Val>
314  eqtobin(Space& home, bool share, Propagator& p,
315  ViewArray<IntView>& x, ViewArray<IntView>& y, Val c) {
316  if (x.size() == 2)
317  return new (home) EqBin<Val,IntView,IntView>
318  (home,share,p,x[0],x[1],c);
319  if (x.size() == 1)
320  return new (home) EqBin<Val,IntView,MinusView>
321  (home,share,p,x[0],MinusView(y[0]),c);
322  return new (home) EqBin<Val,IntView,IntView>
323  (home,share,p,y[0],y[1],-c);
324  }
325 
330  template<class Val, class P, class N>
333  return NULL;
334  }
335  template<class Val>
337  eqtoter(Space& home, bool share, Propagator& p,
339  assert(x.size() == 3);
340  return new (home) EqTer<Val,IntView,IntView,IntView>
341  (home,share,p,x[0],x[1],x[2],c);
342  }
343  template<class Val>
345  eqtoter(Space& home, bool share, Propagator& p,
347  assert(y.size() == 3);
348  return new (home) EqTer<Val,IntView,IntView,IntView>
349  (home,share,p,y[0],y[1],y[2],-c);
350  }
351  template<class Val>
353  eqtoter(Space& home, bool share, Propagator& p,
354  ViewArray<IntView>& x, ViewArray<IntView>& y, Val c) {
355  if (x.size() == 3)
356  return new (home) EqTer<Val,IntView,IntView,IntView>
357  (home,share,p,x[0],x[1],x[2],c);
358  if (x.size() == 2)
359  return new (home) EqTer<Val,IntView,IntView,MinusView>
360  (home,share,p,x[0],x[1],MinusView(y[0]),c);
361  if (x.size() == 1)
362  return new (home) EqTer<Val,IntView,IntView,MinusView>
363  (home,share,p,y[0],y[1],MinusView(x[0]),-c);
364  return new (home) EqTer<Val,IntView,IntView,IntView>
365  (home,share,p,y[0],y[1],y[2],-c);
366  }
367 
368  template<class Val, class P, class N>
369  Actor*
370  Eq<Val,P,N>::copy(Space& home, bool share) {
371  if (isunit(x,y)) {
372  // Check whether rewriting is possible
373  if (x.size() + y.size() == 2)
374  return eqtobin(home,share,*this,x,y,c);
375  if (x.size() + y.size() == 3)
376  return eqtoter(home,share,*this,x,y,c);
377  }
378  return new (home) Eq<Val,P,N>(home,share,*this);
379  }
380 
381  template<class Val, class P, class N>
382  ExecStatus
384  return prop_bnd<Val,P,N>(home,med,*this,x,y,c);
385  }
386 
387  /*
388  * Reified bound consistent linear equation
389  *
390  */
391 
392  template<class Val, class P, class N, class Ctrl>
395  ViewArray<P>& x, ViewArray<N>& y, Val c, Ctrl b)
396  : ReLin<Val,P,N,PC_INT_BND,Ctrl>(home,x,y,c,b) {}
397 
398  template<class Val, class P, class N, class Ctrl>
399  ExecStatus
401  ViewArray<P>& x, ViewArray<N>& y, Val c, Ctrl b) {
402  ViewArray<NoView> nva;
403  if (y.size() == 0) {
404  (void) new (home) ReEq<Val,P,NoView,Ctrl>(home,x,nva,c,b);
405  } else if (x.size() == 0) {
406  (void) new (home) ReEq<Val,N,NoView,Ctrl>(home,y,nva,-c,b);
407  } else {
408  (void) new (home) ReEq<Val,P,N,Ctrl>(home,x,y,c,b);
409  }
410  return ES_OK;
411  }
412 
413 
414  template<class Val, class P, class N, class Ctrl>
417  : ReLin<Val,P,N,PC_INT_BND,Ctrl>(home,share,p) {}
418 
419  template<class Val, class P, class N, class Ctrl>
420  Actor*
421  ReEq<Val,P,N,Ctrl>::copy(Space& home, bool share) {
422  return new (home) ReEq<Val,P,N,Ctrl>(home,share,*this);
423  }
424 
425  template<class Val, class P, class N, class Ctrl>
426  ExecStatus
428  if (b.zero())
429  GECODE_REWRITE(*this,(Nq<Val,P,N>::post(home(*this),x,y,c)));
430  if (b.one())
431  GECODE_REWRITE(*this,(Eq<Val,P,N>::post(home(*this),x,y,c)));
432 
433  Val sl = 0;
434  Val su = 0;
435 
436  bounds_p<Val,P>(med, x, c, sl, su);
437  bounds_n<Val,N>(med, y, c, sl, su);
438 
439  if ((-sl == c) && (-su == c)) {
440  GECODE_ME_CHECK(b.one_none(home));
441  return home.ES_SUBSUMED(*this);
442  }
443  if ((-sl > c) || (-su < c)) {
444  GECODE_ME_CHECK(b.zero_none(home));
445  return home.ES_SUBSUMED(*this);
446  }
447  return ES_FIX;
448  }
449 
450 
451  /*
452  * Domain consistent linear disequation
453  *
454  */
455 
456  template<class Val, class P, class N>
459  : Lin<Val,P,N,PC_INT_VAL>(home,x,y,c) {}
460 
461  template<class Val, class P, class N>
462  ExecStatus
464  ViewArray<NoView> nva;
465  if (y.size() == 0) {
466  (void) new (home) Nq<Val,P,NoView>(home,x,nva,c);
467  } else if (x.size() == 0) {
468  (void) new (home) Nq<Val,N,NoView>(home,y,nva,-c);
469  } else {
470  (void) new (home) Nq<Val,P,N>(home,x,y,c);
471  }
472  return ES_OK;
473  }
474 
475 
476  template<class Val, class P, class N>
478  Nq<Val,P,N>::Nq(Space& home, bool share, Nq<Val,P,N>& p)
479  : Lin<Val,P,N,PC_INT_VAL>(home,share,p) {}
480 
485  template<class Val, class P, class N>
488  return NULL;
489  }
490  template<class Val>
492  nqtobin(Space& home, bool share, Propagator& p,
494  assert(x.size() == 2);
495  return new (home) NqBin<Val,IntView,IntView>
496  (home,share,p,x[0],x[1],c);
497  }
498  template<class Val>
500  nqtobin(Space& home, bool share, Propagator& p,
502  assert(y.size() == 2);
503  return new (home) NqBin<Val,IntView,IntView>
504  (home,share,p,y[0],y[1],-c);
505  }
506  template<class Val>
508  nqtobin(Space& home, bool share, Propagator& p,
509  ViewArray<IntView>& x, ViewArray<IntView>& y, Val c) {
510  if (x.size() == 2)
511  return new (home) NqBin<Val,IntView,IntView>
512  (home,share,p,x[0],x[1],c);
513  if (x.size() == 1)
514  return new (home) NqBin<Val,IntView,MinusView>
515  (home,share,p,x[0],MinusView(y[0]),c);
516  return new (home) NqBin<Val,IntView,IntView>
517  (home,share,p,y[0],y[1],-c);
518  }
519 
524  template<class Val, class P, class N>
527  return NULL;
528  }
529  template<class Val>
531  nqtoter(Space& home, bool share, Propagator& p,
533  assert(x.size() == 3);
534  return new (home) NqTer<Val,IntView,IntView,IntView>
535  (home,share,p,x[0],x[1],x[2],c);
536  }
537  template<class Val>
539  nqtoter(Space& home, bool share, Propagator& p,
541  assert(y.size() == 3);
542  return new (home) NqTer<Val,IntView,IntView,IntView>
543  (home,share,p,y[0],y[1],y[2],-c);
544  }
545  template<class Val>
547  nqtoter(Space& home, bool share, Propagator& p,
548  ViewArray<IntView>& x, ViewArray<IntView>& y, Val c) {
549  if (x.size() == 3)
550  return new (home) NqTer<Val,IntView,IntView,IntView>
551  (home,share,p,x[0],x[1],x[2],c);
552  if (x.size() == 2)
553  return new (home) NqTer<Val,IntView,IntView,MinusView>
554  (home,share,p,x[0],x[1],MinusView(y[0]),c);
555  if (x.size() == 1)
556  return new (home) NqTer<Val,IntView,IntView,MinusView>
557  (home,share,p,y[0],y[1],MinusView(x[0]),-c);
558  return new (home) NqTer<Val,IntView,IntView,IntView>
559  (home,share,p,y[0],y[1],y[2],-c);
560  }
561 
562  template<class Val, class P, class N>
563  Actor*
564  Nq<Val,P,N>::copy(Space& home, bool share) {
565  if (isunit(x,y)) {
566  // Check whether rewriting is possible
567  if (x.size() + y.size() == 2)
568  return nqtobin(home,share,*this,x,y,c);
569  if (x.size() + y.size() == 3)
570  return nqtoter(home,share,*this,x,y,c);
571  }
572  return new (home) Nq<Val,P,N>(home,share,*this);
573  }
574 
575  template<class Val, class P, class N>
576  ExecStatus
578  for (int i = x.size(); i--; )
579  if (x[i].assigned()) {
580  c -= x[i].val(); x.move_lst(i);
581  }
582  for (int i = y.size(); i--; )
583  if (y[i].assigned()) {
584  c += y[i].val(); y.move_lst(i);
585  }
586  if (x.size() + y.size() <= 1) {
587  if (x.size() == 1) {
588  GECODE_ME_CHECK(x[0].nq(home,c)); return home.ES_SUBSUMED(*this);
589  }
590  if (y.size() == 1) {
591  GECODE_ME_CHECK(y[0].nq(home,-c)); return home.ES_SUBSUMED(*this);
592  }
593  return (c == static_cast<Val>(0)) ?
594  ES_FAILED : home.ES_SUBSUMED(*this);
595  }
596  return ES_FIX;
597  }
598 
599 
600  /*
601  * Bound consistent linear inequation
602  *
603  */
604 
605  template<class Val, class P, class N>
608  : Lin<Val,P,N,PC_INT_BND>(home,x,y,c) {}
609 
610  template<class Val, class P, class N>
611  ExecStatus
613  ViewArray<NoView> nva;
614  if (y.size() == 0) {
615  (void) new (home) Lq<Val,P,NoView>(home,x,nva,c);
616  } else if (x.size() == 0) {
617  (void) new (home) Lq<Val,NoView,N>(home,nva,y,c);
618  } else {
619  (void) new (home) Lq<Val,P,N>(home,x,y,c);
620  }
621  return ES_OK;
622  }
623 
624 
625  template<class Val, class P, class N>
627  Lq<Val,P,N>::Lq(Space& home, bool share, Lq<Val,P,N>& p)
628  : Lin<Val,P,N,PC_INT_BND>(home,share,p) {}
629 
634  template<class Val, class P, class N>
637  return NULL;
638  }
639  template<class Val>
641  lqtobin(Space& home, bool share, Propagator& p,
643  assert(x.size() == 2);
644  return new (home) LqBin<Val,IntView,IntView>
645  (home,share,p,x[0],x[1],c);
646  }
647  template<class Val>
649  lqtobin(Space& home, bool share, Propagator& p,
651  assert(y.size() == 2);
652  return new (home) LqBin<Val,MinusView,MinusView>
653  (home,share,p,MinusView(y[0]),MinusView(y[1]),c);
654  }
655  template<class Val>
657  lqtobin(Space& home, bool share, Propagator& p,
658  ViewArray<IntView>& x, ViewArray<IntView>& y, Val c) {
659  if (x.size() == 2)
660  return new (home) LqBin<Val,IntView,IntView>
661  (home,share,p,x[0],x[1],c);
662  if (x.size() == 1)
663  return new (home) LqBin<Val,IntView,MinusView>
664  (home,share,p,x[0],MinusView(y[0]),c);
665  return new (home) LqBin<Val,MinusView,MinusView>
666  (home,share,p,MinusView(y[0]),MinusView(y[1]),c);
667  }
668 
673  template<class Val, class P, class N>
676  return NULL;
677  }
678  template<class Val>
680  lqtoter(Space& home, bool share, Propagator& p,
682  assert(x.size() == 3);
683  return new (home) LqTer<Val,IntView,IntView,IntView>
684  (home,share,p,x[0],x[1],x[2],c);
685  }
686  template<class Val>
688  lqtoter(Space& home, bool share, Propagator& p,
690  assert(y.size() == 3);
692  (home,share,p,MinusView(y[0]),MinusView(y[1]),MinusView(y[2]),c);
693  }
694  template<class Val>
696  lqtoter(Space& home, bool share, Propagator& p,
697  ViewArray<IntView>& x, ViewArray<IntView>& y, Val c) {
698  if (x.size() == 3)
699  return new (home) LqTer<Val,IntView,IntView,IntView>
700  (home,share,p,x[0],x[1],x[2],c);
701  if (x.size() == 2)
702  return new (home) LqTer<Val,IntView,IntView,MinusView>
703  (home,share,p,x[0],x[1],MinusView(y[0]),c);
704  if (x.size() == 1)
706  (home,share,p,x[0],MinusView(y[0]),MinusView(y[1]),c);
708  (home,share,p,MinusView(y[0]),MinusView(y[1]),MinusView(y[2]),c);
709  }
710 
711  template<class Val, class P, class N>
712  Actor*
713  Lq<Val,P,N>::copy(Space& home, bool share) {
714  if (isunit(x,y)) {
715  // Check whether rewriting is possible
716  if (x.size() + y.size() == 2)
717  return lqtobin(home,share,*this,x,y,c);
718  if (x.size() + y.size() == 3)
719  return lqtoter(home,share,*this,x,y,c);
720  }
721  return new (home) Lq<Val,P,N>(home,share,*this);
722  }
723 
724  template<class Val, class P, class N>
725  ExecStatus
727  // Eliminate singletons
728  Val sl = 0;
729 
730  if (IntView::me(med) == ME_INT_VAL) {
731  for (int i = x.size(); i--; ) {
732  Val m = x[i].min();
733  if (x[i].assigned()) {
734  c -= m; x.move_lst(i);
735  } else {
736  sl -= m;
737  }
738  }
739  for (int i = y.size(); i--; ) {
740  Val m = y[i].max();
741  if (y[i].assigned()) {
742  c += m; y.move_lst(i);
743  } else {
744  sl += m;
745  }
746  }
747  if ((x.size() + y.size()) <= 1) {
748  if (x.size() == 1) {
749  GECODE_ME_CHECK(x[0].lq(home,c));
750  return home.ES_SUBSUMED(*this);
751  }
752  if (y.size() == 1) {
753  GECODE_ME_CHECK(y[0].gq(home,-c));
754  return home.ES_SUBSUMED(*this);
755  }
756  return (c >= static_cast<Val>(0)) ?
757  home.ES_SUBSUMED(*this) : ES_FAILED;
758  }
759  } else {
760  for (int i = x.size(); i--; )
761  sl -= x[i].min();
762  for (int i = y.size(); i--; )
763  sl += y[i].max();
764  }
765 
766  sl += c;
767 
768  ExecStatus es = ES_FIX;
769  bool assigned = true;
770  for (int i = x.size(); i--; ) {
771  assert(!x[i].assigned());
772  Val slx = sl + x[i].min();
773  ModEvent me = x[i].lq(home,slx);
774  if (me == ME_INT_FAILED)
775  return ES_FAILED;
776  if (me != ME_INT_VAL)
777  assigned = false;
778  if (me_modified(me) && (slx != x[i].max()))
779  es = ES_NOFIX;
780  }
781 
782  for (int i = y.size(); i--; ) {
783  assert(!y[i].assigned());
784  Val sly = y[i].max() - sl;
785  ModEvent me = y[i].gq(home,sly);
786  if (me == ME_INT_FAILED)
787  return ES_FAILED;
788  if (me != ME_INT_VAL)
789  assigned = false;
790  if (me_modified(me) && (sly != y[i].min()))
791  es = ES_NOFIX;
792  }
793  return assigned ? home.ES_SUBSUMED(*this) : es;
794  }
795 
796  /*
797  * Reified bound consistent linear inequation
798  *
799  */
800 
801  template<class Val, class P, class N>
804  (Home home, ViewArray<P>& x, ViewArray<N>& y, Val c, BoolView b)
805  : ReLin<Val,P,N,PC_INT_BND,BoolView>(home,x,y,c,b) {}
806 
807  template<class Val, class P, class N>
808  ExecStatus
810  (Home home, ViewArray<P>& x, ViewArray<N>& y, Val c, BoolView b) {
811  ViewArray<NoView> nva;
812  if (y.size() == 0) {
813  (void) new (home) ReLq<Val,P,NoView>(home,x,nva,c,b);
814  } else if (x.size() == 0) {
815  (void) new (home) ReLq<Val,NoView,N>(home,nva,y,c,b);
816  } else {
817  (void) new (home) ReLq<Val,P,N>(home,x,y,c,b);
818  }
819  return ES_OK;
820  }
821 
822 
823  template<class Val, class P, class N>
825  ReLq<Val,P,N>::ReLq(Space& home, bool share, ReLq<Val,P,N>& p)
826  : ReLin<Val,P,N,PC_INT_BND,BoolView>(home,share,p) {}
827 
828  template<class Val, class P, class N>
829  Actor*
830  ReLq<Val,P,N>::copy(Space& home, bool share) {
831  return new (home) ReLq<Val,P,N>(home,share,*this);
832  }
833 
834  template<class Val, class P, class N>
835  ExecStatus
837  if (b.zero())
838  GECODE_REWRITE(*this,(Lq<Val,N,P>::post(home(*this),y,x,-c-1)));
839  if (b.one())
840  GECODE_REWRITE(*this,(Lq<Val,P,N>::post(home(*this),x,y,c)));
841 
842  // Eliminate singletons
843  Val sl = 0;
844  Val su = 0;
845 
846  bounds_p<Val,P>(med,x,c,sl,su);
847  bounds_n<Val,N>(med,y,c,sl,su);
848 
849  if (-sl > c) {
850  GECODE_ME_CHECK(b.zero_none(home));
851  return home.ES_SUBSUMED(*this);
852  }
853  if (-su <= c) {
854  GECODE_ME_CHECK(b.one_none(home));
855  return home.ES_SUBSUMED(*this);
856  }
857 
858  return ES_FIX;
859  }
860 
861 }}}
862 
863 // STATISTICS: int-prop
864