Generated on Sat Feb 7 2015 02:01:24 for Gecode by doxygen 1.8.9.1
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: 2012-10-18 16:02:42 +0200 (Thu, 18 Oct 2012) $ by $Author: schulte $
11  * $Revision: 13154 $
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, ReifyMode rm>
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, ReifyMode rm>
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,rm>(home,x,nva,c,b);
405  } else if (x.size() == 0) {
406  (void) new (home) ReEq<Val,N,NoView,Ctrl,rm>(home,y,nva,-c,b);
407  } else {
408  (void) new (home) ReEq<Val,P,N,Ctrl,rm>(home,x,y,c,b);
409  }
410  return ES_OK;
411  }
412 
413 
414  template<class Val, class P, class N, class Ctrl, ReifyMode rm>
416  ReEq<Val,P,N,Ctrl,rm>::ReEq(Space& home, bool share,
418  : ReLin<Val,P,N,PC_INT_BND,Ctrl>(home,share,p) {}
419 
420  template<class Val, class P, class N, class Ctrl, ReifyMode rm>
421  Actor*
422  ReEq<Val,P,N,Ctrl,rm>::copy(Space& home, bool share) {
423  return new (home) ReEq<Val,P,N,Ctrl,rm>(home,share,*this);
424  }
425 
426  template<class Val, class P, class N, class Ctrl, ReifyMode rm>
427  ExecStatus
429  if (b.zero()) {
430  if (rm == RM_IMP)
431  return home.ES_SUBSUMED(*this);
432  GECODE_REWRITE(*this,(Nq<Val,P,N>::post(home(*this),x,y,c)));
433  }
434  if (b.one()) {
435  if (rm == RM_PMI)
436  return home.ES_SUBSUMED(*this);
437  GECODE_REWRITE(*this,(Eq<Val,P,N>::post(home(*this),x,y,c)));
438  }
439 
440  Val sl = 0;
441  Val su = 0;
442 
443  bounds_p<Val,P>(med, x, c, sl, su);
444  bounds_n<Val,N>(med, y, c, sl, su);
445 
446  if ((-sl == c) && (-su == c)) {
447  if (rm != RM_IMP)
448  GECODE_ME_CHECK(b.one_none(home));
449  return home.ES_SUBSUMED(*this);
450  }
451  if ((-sl > c) || (-su < c)) {
452  if (rm != RM_PMI)
453  GECODE_ME_CHECK(b.zero_none(home));
454  return home.ES_SUBSUMED(*this);
455  }
456  return ES_FIX;
457  }
458 
459 
460  /*
461  * Domain consistent linear disequation
462  *
463  */
464 
465  template<class Val, class P, class N>
468  : Lin<Val,P,N,PC_INT_VAL>(home,x,y,c) {}
469 
470  template<class Val, class P, class N>
471  ExecStatus
473  ViewArray<NoView> nva;
474  if (y.size() == 0) {
475  (void) new (home) Nq<Val,P,NoView>(home,x,nva,c);
476  } else if (x.size() == 0) {
477  (void) new (home) Nq<Val,N,NoView>(home,y,nva,-c);
478  } else {
479  (void) new (home) Nq<Val,P,N>(home,x,y,c);
480  }
481  return ES_OK;
482  }
483 
484 
485  template<class Val, class P, class N>
487  Nq<Val,P,N>::Nq(Space& home, bool share, Nq<Val,P,N>& p)
488  : Lin<Val,P,N,PC_INT_VAL>(home,share,p) {}
489 
494  template<class Val, class P, class N>
497  return NULL;
498  }
499  template<class Val>
501  nqtobin(Space& home, bool share, Propagator& p,
503  assert(x.size() == 2);
504  return new (home) NqBin<Val,IntView,IntView>
505  (home,share,p,x[0],x[1],c);
506  }
507  template<class Val>
509  nqtobin(Space& home, bool share, Propagator& p,
511  assert(y.size() == 2);
512  return new (home) NqBin<Val,IntView,IntView>
513  (home,share,p,y[0],y[1],-c);
514  }
515  template<class Val>
517  nqtobin(Space& home, bool share, Propagator& p,
518  ViewArray<IntView>& x, ViewArray<IntView>& y, Val c) {
519  if (x.size() == 2)
520  return new (home) NqBin<Val,IntView,IntView>
521  (home,share,p,x[0],x[1],c);
522  if (x.size() == 1)
523  return new (home) NqBin<Val,IntView,MinusView>
524  (home,share,p,x[0],MinusView(y[0]),c);
525  return new (home) NqBin<Val,IntView,IntView>
526  (home,share,p,y[0],y[1],-c);
527  }
528 
533  template<class Val, class P, class N>
536  return NULL;
537  }
538  template<class Val>
540  nqtoter(Space& home, bool share, Propagator& p,
542  assert(x.size() == 3);
543  return new (home) NqTer<Val,IntView,IntView,IntView>
544  (home,share,p,x[0],x[1],x[2],c);
545  }
546  template<class Val>
548  nqtoter(Space& home, bool share, Propagator& p,
550  assert(y.size() == 3);
551  return new (home) NqTer<Val,IntView,IntView,IntView>
552  (home,share,p,y[0],y[1],y[2],-c);
553  }
554  template<class Val>
556  nqtoter(Space& home, bool share, Propagator& p,
557  ViewArray<IntView>& x, ViewArray<IntView>& y, Val c) {
558  if (x.size() == 3)
559  return new (home) NqTer<Val,IntView,IntView,IntView>
560  (home,share,p,x[0],x[1],x[2],c);
561  if (x.size() == 2)
562  return new (home) NqTer<Val,IntView,IntView,MinusView>
563  (home,share,p,x[0],x[1],MinusView(y[0]),c);
564  if (x.size() == 1)
565  return new (home) NqTer<Val,IntView,IntView,MinusView>
566  (home,share,p,y[0],y[1],MinusView(x[0]),-c);
567  return new (home) NqTer<Val,IntView,IntView,IntView>
568  (home,share,p,y[0],y[1],y[2],-c);
569  }
570 
571  template<class Val, class P, class N>
572  Actor*
573  Nq<Val,P,N>::copy(Space& home, bool share) {
574  if (isunit(x,y)) {
575  // Check whether rewriting is possible
576  if (x.size() + y.size() == 2)
577  return nqtobin(home,share,*this,x,y,c);
578  if (x.size() + y.size() == 3)
579  return nqtoter(home,share,*this,x,y,c);
580  }
581  return new (home) Nq<Val,P,N>(home,share,*this);
582  }
583 
584  template<class Val, class P, class N>
585  ExecStatus
587  for (int i = x.size(); i--; )
588  if (x[i].assigned()) {
589  c -= x[i].val(); x.move_lst(i);
590  }
591  for (int i = y.size(); i--; )
592  if (y[i].assigned()) {
593  c += y[i].val(); y.move_lst(i);
594  }
595  if (x.size() + y.size() <= 1) {
596  if (x.size() == 1) {
597  GECODE_ME_CHECK(x[0].nq(home,c)); return home.ES_SUBSUMED(*this);
598  }
599  if (y.size() == 1) {
600  GECODE_ME_CHECK(y[0].nq(home,-c)); return home.ES_SUBSUMED(*this);
601  }
602  return (c == static_cast<Val>(0)) ?
603  ES_FAILED : home.ES_SUBSUMED(*this);
604  }
605  return ES_FIX;
606  }
607 
608 
609  /*
610  * Bound consistent linear inequation
611  *
612  */
613 
614  template<class Val, class P, class N>
617  : Lin<Val,P,N,PC_INT_BND>(home,x,y,c) {}
618 
619  template<class Val, class P, class N>
620  ExecStatus
622  ViewArray<NoView> nva;
623  if (y.size() == 0) {
624  (void) new (home) Lq<Val,P,NoView>(home,x,nva,c);
625  } else if (x.size() == 0) {
626  (void) new (home) Lq<Val,NoView,N>(home,nva,y,c);
627  } else {
628  (void) new (home) Lq<Val,P,N>(home,x,y,c);
629  }
630  return ES_OK;
631  }
632 
633 
634  template<class Val, class P, class N>
636  Lq<Val,P,N>::Lq(Space& home, bool share, Lq<Val,P,N>& p)
637  : Lin<Val,P,N,PC_INT_BND>(home,share,p) {}
638 
643  template<class Val, class P, class N>
646  return NULL;
647  }
648  template<class Val>
650  lqtobin(Space& home, bool share, Propagator& p,
652  assert(x.size() == 2);
653  return new (home) LqBin<Val,IntView,IntView>
654  (home,share,p,x[0],x[1],c);
655  }
656  template<class Val>
658  lqtobin(Space& home, bool share, Propagator& p,
660  assert(y.size() == 2);
661  return new (home) LqBin<Val,MinusView,MinusView>
662  (home,share,p,MinusView(y[0]),MinusView(y[1]),c);
663  }
664  template<class Val>
666  lqtobin(Space& home, bool share, Propagator& p,
667  ViewArray<IntView>& x, ViewArray<IntView>& y, Val c) {
668  if (x.size() == 2)
669  return new (home) LqBin<Val,IntView,IntView>
670  (home,share,p,x[0],x[1],c);
671  if (x.size() == 1)
672  return new (home) LqBin<Val,IntView,MinusView>
673  (home,share,p,x[0],MinusView(y[0]),c);
674  return new (home) LqBin<Val,MinusView,MinusView>
675  (home,share,p,MinusView(y[0]),MinusView(y[1]),c);
676  }
677 
682  template<class Val, class P, class N>
685  return NULL;
686  }
687  template<class Val>
689  lqtoter(Space& home, bool share, Propagator& p,
691  assert(x.size() == 3);
692  return new (home) LqTer<Val,IntView,IntView,IntView>
693  (home,share,p,x[0],x[1],x[2],c);
694  }
695  template<class Val>
697  lqtoter(Space& home, bool share, Propagator& p,
699  assert(y.size() == 3);
701  (home,share,p,MinusView(y[0]),MinusView(y[1]),MinusView(y[2]),c);
702  }
703  template<class Val>
705  lqtoter(Space& home, bool share, Propagator& p,
706  ViewArray<IntView>& x, ViewArray<IntView>& y, Val c) {
707  if (x.size() == 3)
708  return new (home) LqTer<Val,IntView,IntView,IntView>
709  (home,share,p,x[0],x[1],x[2],c);
710  if (x.size() == 2)
711  return new (home) LqTer<Val,IntView,IntView,MinusView>
712  (home,share,p,x[0],x[1],MinusView(y[0]),c);
713  if (x.size() == 1)
715  (home,share,p,x[0],MinusView(y[0]),MinusView(y[1]),c);
717  (home,share,p,MinusView(y[0]),MinusView(y[1]),MinusView(y[2]),c);
718  }
719 
720  template<class Val, class P, class N>
721  Actor*
722  Lq<Val,P,N>::copy(Space& home, bool share) {
723  if (isunit(x,y)) {
724  // Check whether rewriting is possible
725  if (x.size() + y.size() == 2)
726  return lqtobin(home,share,*this,x,y,c);
727  if (x.size() + y.size() == 3)
728  return lqtoter(home,share,*this,x,y,c);
729  }
730  return new (home) Lq<Val,P,N>(home,share,*this);
731  }
732 
733  template<class Val, class P, class N>
734  ExecStatus
736  // Eliminate singletons
737  Val sl = 0;
738 
739  if (IntView::me(med) == ME_INT_VAL) {
740  for (int i = x.size(); i--; ) {
741  Val m = x[i].min();
742  if (x[i].assigned()) {
743  c -= m; x.move_lst(i);
744  } else {
745  sl -= m;
746  }
747  }
748  for (int i = y.size(); i--; ) {
749  Val m = y[i].max();
750  if (y[i].assigned()) {
751  c += m; y.move_lst(i);
752  } else {
753  sl += m;
754  }
755  }
756  if ((x.size() + y.size()) <= 1) {
757  if (x.size() == 1) {
758  GECODE_ME_CHECK(x[0].lq(home,c));
759  return home.ES_SUBSUMED(*this);
760  }
761  if (y.size() == 1) {
762  GECODE_ME_CHECK(y[0].gq(home,-c));
763  return home.ES_SUBSUMED(*this);
764  }
765  return (c >= static_cast<Val>(0)) ?
766  home.ES_SUBSUMED(*this) : ES_FAILED;
767  }
768  } else {
769  for (int i = x.size(); i--; )
770  sl -= x[i].min();
771  for (int i = y.size(); i--; )
772  sl += y[i].max();
773  }
774 
775  sl += c;
776 
777  ExecStatus es = ES_FIX;
778  bool assigned = true;
779  for (int i = x.size(); i--; ) {
780  assert(!x[i].assigned());
781  Val slx = sl + x[i].min();
782  ModEvent me = x[i].lq(home,slx);
783  if (me == ME_INT_FAILED)
784  return ES_FAILED;
785  if (me != ME_INT_VAL)
786  assigned = false;
787  if (me_modified(me) && (slx != x[i].max()))
788  es = ES_NOFIX;
789  }
790 
791  for (int i = y.size(); i--; ) {
792  assert(!y[i].assigned());
793  Val sly = y[i].max() - sl;
794  ModEvent me = y[i].gq(home,sly);
795  if (me == ME_INT_FAILED)
796  return ES_FAILED;
797  if (me != ME_INT_VAL)
798  assigned = false;
799  if (me_modified(me) && (sly != y[i].min()))
800  es = ES_NOFIX;
801  }
802  return assigned ? home.ES_SUBSUMED(*this) : es;
803  }
804 
805  /*
806  * Reified bound consistent linear inequation
807  *
808  */
809 
810  template<class Val, class P, class N, ReifyMode rm>
813  ViewArray<P>& x, ViewArray<N>& y, Val c, BoolView b)
814  : ReLin<Val,P,N,PC_INT_BND,BoolView>(home,x,y,c,b) {}
815 
816  template<class Val, class P, class N, ReifyMode rm>
817  ExecStatus
819  ViewArray<P>& x, ViewArray<N>& y, Val c, BoolView b) {
820  ViewArray<NoView> nva;
821  if (y.size() == 0) {
822  (void) new (home) ReLq<Val,P,NoView,rm>(home,x,nva,c,b);
823  } else if (x.size() == 0) {
824  (void) new (home) ReLq<Val,NoView,N,rm>(home,nva,y,c,b);
825  } else {
826  (void) new (home) ReLq<Val,P,N,rm>(home,x,y,c,b);
827  }
828  return ES_OK;
829  }
830 
831 
832  template<class Val, class P, class N, ReifyMode rm>
835  : ReLin<Val,P,N,PC_INT_BND,BoolView>(home,share,p) {}
836 
837  template<class Val, class P, class N, ReifyMode rm>
838  Actor*
839  ReLq<Val,P,N,rm>::copy(Space& home, bool share) {
840  return new (home) ReLq<Val,P,N,rm>(home,share,*this);
841  }
842 
843  template<class Val, class P, class N, ReifyMode rm>
844  ExecStatus
846  if (b.zero()) {
847  if (rm == RM_IMP)
848  return home.ES_SUBSUMED(*this);
849  GECODE_REWRITE(*this,(Lq<Val,N,P>::post(home(*this),y,x,-c-1)));
850  }
851  if (b.one()) {
852  if (rm == RM_PMI)
853  return home.ES_SUBSUMED(*this);
854  GECODE_REWRITE(*this,(Lq<Val,P,N>::post(home(*this),x,y,c)));
855  }
856 
857  // Eliminate singletons
858  Val sl = 0;
859  Val su = 0;
860 
861  bounds_p<Val,P>(med,x,c,sl,su);
862  bounds_n<Val,N>(med,y,c,sl,su);
863 
864  if (-sl > c) {
865  if (rm != RM_PMI)
866  GECODE_ME_CHECK(b.zero_none(home));
867  return home.ES_SUBSUMED(*this);
868  }
869  if (-su <= c) {
870  if (rm != RM_IMP)
871  GECODE_ME_CHECK(b.one_none(home));
872  return home.ES_SUBSUMED(*this);
873  }
874 
875  return ES_FIX;
876  }
877 
878 }}}
879 
880 // STATISTICS: int-prop
881 
Propagator for bounds consistent binary linear disequality
Definition: linear.hh:201
ReEq(Space &home, bool share, ReEq &p)
Constructor for cloning p.
Definition: int-nary.hpp:416
#define GECODE_REWRITE(prop, post)
Rewrite propagator by executing post function.
Definition: macros.hpp:109
bool isunit(ViewArray< P > &, ViewArray< N > &)
Test if only unit-coefficient arrays used.
Definition: int-nary.hpp:48
void update(Space &, bool share, ViewArray< View > &a)
Update array to be a clone of array a.
Definition: array.hpp:1387
static ExecStatus post(Home home, ViewArray< P > &x, ViewArray< N > &y, Val c)
Post propagator for .
Definition: int-nary.hpp:472
Propagator for bounds consistent n-ary linear equality
Definition: linear.hh:569
Lq(Space &home, bool share, Lq &p)
Constructor for cloning p.
Definition: int-nary.hpp:636
Inverse implication for reification.
Definition: int.hh:847
void mod(Home home, IntVar x0, IntVar x1, IntVar x2, IntConLevel icl)
Post propagator for .
Definition: arithmetic.cpp:213
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition: core.hpp:4041
ViewArray< N > y
Array of negative views.
Definition: linear.hh:500
Propagator for reified bounds consistent n-ary linear less or equal
Definition: linear.hh:741
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:2973
static ExecStatus post(Home home, ViewArray< P > &x, ViewArray< N > &y, Val c)
Post propagator for .
Definition: int-nary.hpp:269
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1662
Propagator for bounds consistent n-ary linear disequality
Definition: linear.hh:675
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:57
Propagator for bounds consistent ternary linear equality
Definition: linear.hh:382
ExecStatus prop_bnd(Space &home, ModEventDelta med, Propagator &p, ViewArray< P > &x, ViewArray< N > &y, Val &c)
Definition: int-nary.hpp:172
int ModEvent
Type for modification events.
Definition: core.hpp:146
Base-class for reified n-ary linear propagators.
Definition: linear.hh:525
Base-class for propagators.
Definition: core.hpp:755
Actor * lqtobin(Space &, bool, Propagator &, ViewArray< P > &, ViewArray< N > &, Val)
Rewriting of inequality to binary propagators.
Definition: int-nary.hpp:645
Base-class for n-ary linear propagators.
Definition: linear.hh:495
Propagation has computed fixpoint.
Definition: core.hpp:528
Propagator for bounds consistent binary linear equality
Definition: linear.hh:134
Computation spaces.
Definition: core.hpp:1362
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: int-nary.hpp:586
Actor * lqtoter(Space &, bool, Propagator &, ViewArray< P > &, ViewArray< N > &, Val)
Rewriting of inequality to ternary propagators.
Definition: int-nary.hpp:684
Base-class for both propagators and branchers.
Definition: core.hpp:666
Actor * eqtoter(Space &, bool, Propagator &, ViewArray< P > &, ViewArray< N > &, Val)
Rewriting of equality to ternary propagators.
Definition: int-nary.hpp:332
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: int-nary.hpp:428
ViewArray< P > x
Array of positive views.
Definition: linear.hh:498
const Gecode::ModEvent ME_INT_FAILED
Domain operation has resulted in failure.
Definition: var-type.hpp:52
virtual Actor * copy(Space &home, bool share)
Create copy during cloning.
Definition: int-nary.hpp:370
Propagator for bounds consistent ternary linear less or equal
Definition: linear.hh:452
Gecode::FloatVal c(-8, 8)
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: int-nary.hpp:383
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Gecode::IntArgs i(4, 1, 2, 3, 4)
static ExecStatus post(Home home, ViewArray< P > &x, ViewArray< N > &y, Val c, BoolView b)
Post propagator for .
Definition: int-nary.hpp:818
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Execution has resulted in failure.
Definition: core.hpp:525
void bounds_n(ModEventDelta med, ViewArray< View > &y, Val &c, Val &sl, Val &su)
Definition: int-nary.hpp:150
void subscribe(Space &home, Propagator &p, PropCond pc, bool process=true)
Subscribe propagator p with propagation condition pc to variable.
Definition: array.hpp:1400
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Definition: var-type.hpp:91
Actor * eqtobin(Space &, bool, Propagator &, ViewArray< P > &, ViewArray< N > &, Val)
Rewriting of equality to binary propagators.
Definition: int-nary.hpp:293
const Gecode::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable)
Definition: var-type.hpp:56
Propagator for bounds consistent binary linear less or equal
Definition: linear.hh:237
virtual Actor * copy(Space &home, bool share)
Create copy during cloning.
Definition: int-nary.hpp:573
size_t size
The size of the propagator (used during subsumption)
Definition: core.hpp:766
Propagator for reified bounds consistent n-ary linear equality
Definition: linear.hh:641
Nq(Space &home, bool share, Nq &p)
Constructor for cloning p.
Definition: int-nary.hpp:487
void bounds_p(ModEventDelta med, ViewArray< View > &x, Val &c, Val &sl, Val &su)
Definition: int-nary.hpp:129
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:45
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: int-nary.hpp:116
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as low linear)
Definition: int-nary.hpp:81
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: int-nary.hpp:735
Lin(Space &home, bool share, Lin< Val, P, N, pc > &p)
Constructor for cloning p.
Definition: int-nary.hpp:73
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:75
Eq(Space &home, bool share, Eq &p)
Constructor for cloning p.
Definition: int-nary.hpp:284
static ExecStatus post(Home home, ViewArray< P > &x, ViewArray< N > &y, Val c, Ctrl b)
Post propagator for .
Definition: int-nary.hpp:400
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:2877
static ExecStatus post(Home home, ViewArray< P > &x, ViewArray< N > &y, Val c)
Post propagator for .
Definition: int-nary.hpp:621
Propagation cost.
Definition: core.hpp:537
virtual Actor * copy(Space &home, bool share)
Create copy during cloning.
Definition: int-nary.hpp:839
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: int-nary.hpp:845
ExecStatus
Definition: core.hpp:523
Minus integer view.
Definition: view.hpp:276
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:47
ReLq(Space &home, bool share, ReLq &p)
Constructor for cloning p.
Definition: int-nary.hpp:834
static ModEvent me(const ModEventDelta &med)
Return modification event for view type in med.
#define forceinline
Definition: config.hpp:132
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition: modevent.hpp:63
Execution is okay.
Definition: core.hpp:527
Propagation has not computed fixpoint.
Definition: core.hpp:526
Ctrl b
Control view for reification.
Definition: linear.hh:528
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1215
virtual Actor * copy(Space &home, bool share)
Create copy during cloning.
Definition: int-nary.hpp:722
ReLin(Space &home, bool share, ReLin &p)
Constructor for cloning p.
Definition: int-nary.hpp:109
struct Gecode::@518::NNF::@57::@58 b
For binary nodes (and, or, eqv)
Gecode toplevel namespace
Propagator for bounds consistent n-ary linear less or equal
Definition: linear.hh:708
Actor * nqtoter(Space &, bool, Propagator &, ViewArray< P > &, ViewArray< N > &, Val)
Rewriting of disequality to ternary propagators.
Definition: int-nary.hpp:535
Implication for reification.
Definition: int.hh:840
virtual Actor * copy(Space &home, bool share)
Create copy during cloning.
Definition: int-nary.hpp:422
Propagator for bounds consistent ternary linear disquality
Definition: linear.hh:417
int ModEventDelta
Modification event deltas.
Definition: core.hpp:173
Home class for posting propagators
Definition: core.hpp:717
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: int-nary.hpp:87
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition: modevent.hpp:58
Actor * nqtobin(Space &, bool, Propagator &, ViewArray< P > &, ViewArray< N > &, Val)
Rewriting of disequality to binary propagators.
Definition: int-nary.hpp:496
const Gecode::PropCond PC_INT_VAL
Propagate when a view becomes assigned (single value)
Definition: var-type.hpp:82
const Gecode::PropCond PC_BOOL_VAL
Propagate when a view becomes assigned (single value)
Definition: var-type.hpp:126
Boolean view for Boolean variables.
Definition: view.hpp:1315