Generated on Thu Mar 7 2013 10:21:30 for Gecode by doxygen 1.8.3.1
int-bin.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 
38 namespace Gecode { namespace Int { namespace Linear {
39 
40  /*
41  * Binary linear propagators
42  *
43  */
44  template<class Val, class A, class B, PropCond pc>
46  LinBin<Val,A,B,pc>::LinBin(Home home, A y0, B y1, Val c0)
47  : Propagator(home), x0(y0), x1(y1), c(c0) {
48  x0.subscribe(home,*this,pc);
49  x1.subscribe(home,*this,pc);
50  }
51 
52  template<class Val, class A, class B, PropCond pc>
55  : Propagator(home,share,p), c(p.c) {
56  x0.update(home,share,p.x0);
57  x1.update(home,share,p.x1);
58  }
59 
60  template<class Val, class A, class B, PropCond pc>
63  A y0, B y1, Val c0)
64  : Propagator(home,share,p), c(c0) {
65  x0.update(home,share,y0);
66  x1.update(home,share,y1);
67  }
68 
69  template<class Val, class A, class B, PropCond pc>
70  PropCost
73  }
74 
75  template<class Val, class A, class B, PropCond pc>
76  forceinline size_t
78  x0.cancel(home,*this,pc);
79  x1.cancel(home,*this,pc);
80  (void) Propagator::dispose(home);
81  return sizeof(*this);
82  }
83 
84 
85  /*
86  * Binary reified linear propagators
87  *
88  */
89  template<class Val, class A, class B, PropCond pc, class Ctrl>
91  ReLinBin<Val,A,B,pc,Ctrl>::ReLinBin(Home home, A y0, B y1, Val c0, Ctrl b0)
92  : Propagator(home), x0(y0), x1(y1), c(c0), b(b0) {
93  x0.subscribe(home,*this,pc);
94  x1.subscribe(home,*this,pc);
95  b.subscribe(home,*this,PC_INT_VAL);
96  }
97 
98  template<class Val, class A, class B, PropCond pc, class Ctrl>
102  : Propagator(home,share,p), c(p.c) {
103  x0.update(home,share,p.x0);
104  x1.update(home,share,p.x1);
105  b.update(home,share,p.b);
106  }
107 
108  template<class Val, class A, class B, PropCond pc, class Ctrl>
109  PropCost
112  }
113 
114  template<class Val, class A, class B, PropCond pc, class Ctrl>
115  forceinline size_t
117  x0.cancel(home,*this,pc);
118  x1.cancel(home,*this,pc);
119  b.cancel(home,*this,PC_BOOL_VAL);
120  (void) Propagator::dispose(home);
121  return sizeof(*this);
122  }
123 
124  /*
125  * Binary bounds consistent linear equality
126  *
127  */
128 
129  template<class Val, class A, class B>
131  EqBin<Val,A,B>::EqBin(Home home, A x0, B x1, Val c)
132  : LinBin<Val,A,B,PC_INT_BND>(home,x0,x1,c) {}
133 
134  template<class Val, class A, class B>
135  ExecStatus
136  EqBin<Val,A,B>::post(Home home, A x0, B x1, Val c) {
137  (void) new (home) EqBin<Val,A,B>(home,x0,x1,c);
138  return ES_OK;
139  }
140 
141 
142  template<class Val, class A, class B>
145  : LinBin<Val,A,B,PC_INT_BND>(home,share,p) {}
146 
147  template<class Val, class A, class B>
149  EqBin<Val,A,B>::EqBin(Space& home, bool share, Propagator& p,
150  A x0, B x1, Val c)
151  : LinBin<Val,A,B,PC_INT_BND>(home,share,p,x0,x1,c) {}
152 
153  template<class Val, class A, class B>
154  Actor*
155  EqBin<Val,A,B>::copy(Space& home, bool share) {
156  return new (home) EqBin<Val,A,B>(home,share,*this);
157  }
158 
160  enum BinMod {
161  BM_X0_MIN = 1<<0,
162  BM_X0_MAX = 1<<1,
163  BM_X1_MIN = 1<<2,
164  BM_X1_MAX = 1<<3,
166  };
167 
168 #define GECODE_INT_PV(CASE,TELL,UPDATE) \
169  if (bm & (CASE)) { \
170  bm -= (CASE); ModEvent me = (TELL); \
171  if (me_failed(me)) return ES_FAILED; \
172  if (me_modified(me)) bm |= (UPDATE); \
173  }
174 
175  template<class Val, class A, class B>
176  ExecStatus
178  int bm = BM_ALL;
179  do {
180  GECODE_INT_PV(BM_X0_MIN, x0.gq(home,c-x1.max()), BM_X1_MAX);
181  GECODE_INT_PV(BM_X1_MIN, x1.gq(home,c-x0.max()), BM_X0_MAX);
182  GECODE_INT_PV(BM_X0_MAX, x0.lq(home,c-x1.min()), BM_X1_MIN);
183  GECODE_INT_PV(BM_X1_MAX, x1.lq(home,c-x0.min()), BM_X0_MIN);
184  } while (bm);
185  return x0.assigned() ? home.ES_SUBSUMED(*this) : ES_FIX;
186  }
187 
188 #undef GECODE_INT_PV
189 
190 
191 
192 
193 
194  /*
195  * Reified binary bounds consistent linear equality
196  *
197  */
198 
199  template<class Val, class A, class B, class Ctrl>
201  ReEqBin<Val,A,B,Ctrl>::ReEqBin(Home home, A x0, B x1, Val c, Ctrl b)
202  : ReLinBin<Val,A,B,PC_INT_BND,Ctrl>(home,x0,x1,c,b) {}
203 
204  template<class Val, class A, class B, class Ctrl>
205  ExecStatus
206  ReEqBin<Val,A,B,Ctrl>::post(Home home, A x0, B x1, Val c, Ctrl b) {
207  (void) new (home) ReEqBin<Val,A,B,Ctrl>(home,x0,x1,c,b);
208  return ES_OK;
209  }
210 
211 
212  template<class Val, class A, class B, class Ctrl>
216  : ReLinBin<Val,A,B,PC_INT_BND,Ctrl>(home,share,p) {}
217 
218  template<class Val, class A, class B, class Ctrl>
219  Actor*
220  ReEqBin<Val,A,B,Ctrl>::copy(Space& home, bool share) {
221  return new (home) ReEqBin<Val,A,B,Ctrl>(home,share,*this);
222  }
223 
224  template<class Val, class A, class B, class Ctrl>
225  ExecStatus
227  if (b.zero())
228  GECODE_REWRITE(*this,(NqBin<Val,A,B>::post(home(*this),x0,x1,c)));
229  if (b.one())
230  GECODE_REWRITE(*this,(EqBin<Val,A,B>::post(home(*this),x0,x1,c)));
231  if ((x0.min() + x1.min() > c) || (x0.max() + x1.max() < c)) {
232  GECODE_ME_CHECK(b.zero_none(home)); return home.ES_SUBSUMED(*this);
233  }
234  if (x0.assigned() && x1.assigned()) {
235  assert(x0.val() + x1.val() == c);
236  GECODE_ME_CHECK(b.one_none(home)); return home.ES_SUBSUMED(*this);
237  }
238  return ES_FIX;
239  }
240 
241 
242 
243 
244  /*
245  * Binary domain consistent linear disequality
246  *
247  */
248  template<class Val, class A, class B>
250  NqBin<Val,A,B>::NqBin(Home home, A x0, B x1, Val c)
251  : LinBin<Val,A,B,PC_INT_VAL>(home,x0,x1,c) {}
252 
253  template<class Val, class A, class B>
254  ExecStatus
255  NqBin<Val,A,B>::post(Home home, A x0, B x1, Val c) {
256  (void) new (home) NqBin<Val,A,B>(home,x0,x1,c);
257  return ES_OK;
258  }
259 
260 
261  template<class Val, class A, class B>
264  : LinBin<Val,A,B,PC_INT_VAL>(home,share,p) {}
265 
266  template<class Val, class A, class B>
267  Actor*
268  NqBin<Val,A,B>::copy(Space& home, bool share) {
269  return new (home) NqBin<Val,A,B>(home,share,*this);
270  }
271 
272  template<class Val, class A, class B>
274  NqBin<Val,A,B>::NqBin(Space& home, bool share, Propagator& p,
275  A x0, B x1, Val c)
276  : LinBin<Val,A,B,PC_INT_VAL>(home,share,p,x0,x1,c) {}
277 
278 
279 
280  template<class Val, class A, class B>
281  PropCost
282  NqBin<Val,A,B>::cost(const Space&, const ModEventDelta&) const {
284  }
285 
286  template<class Val, class A, class B>
287  ExecStatus
289  if (x0.assigned()) {
290  GECODE_ME_CHECK(x1.nq(home,c-x0.val()));
291  } else {
292  assert(x1.assigned());
293  GECODE_ME_CHECK(x0.nq(home,c-x1.val()));
294  }
295  return home.ES_SUBSUMED(*this);
296  }
297 
298 
299  /*
300  * Binary domain consistent less equal
301  *
302  */
303 
304  template<class Val, class A, class B>
306  LqBin<Val,A,B>::LqBin(Home home, A x0, B x1, Val c)
307  : LinBin<Val,A,B,PC_INT_BND>(home,x0,x1,c) {}
308 
309  template<class Val, class A, class B>
310  ExecStatus
311  LqBin<Val,A,B>::post(Home home, A x0, B x1, Val c) {
312  (void) new (home) LqBin<Val,A,B>(home,x0,x1,c);
313  return ES_OK;
314  }
315 
316 
317  template<class Val, class A, class B>
320  : LinBin<Val,A,B,PC_INT_BND>(home,share,p) {}
321 
322  template<class Val, class A, class B>
323  Actor*
324  LqBin<Val,A,B>::copy(Space& home, bool share) {
325  return new (home) LqBin<Val,A,B>(home,share,*this);
326  }
327 
328  template<class Val, class A, class B>
330  LqBin<Val,A,B>::LqBin(Space& home, bool share, Propagator& p,
331  A x0, B x1, Val c)
332  : LinBin<Val,A,B,PC_INT_BND>(home,share,p,x0,x1,c) {}
333 
334  template<class Val, class A, class B>
335  ExecStatus
337  GECODE_ME_CHECK(x0.lq(home,c-x1.min()));
338  GECODE_ME_CHECK(x1.lq(home,c-x0.min()));
339  return (x0.max()+x1.max() <= c) ? home.ES_SUBSUMED(*this) : ES_FIX;
340  }
341 
342 
343 
344 
345  /*
346  * Binary domain consistent greater equal
347  *
348  */
349 
350  template<class Val, class A, class B>
352  GqBin<Val,A,B>::GqBin(Home home, A x0, B x1, Val c)
353  : LinBin<Val,A,B,PC_INT_BND>(home,x0,x1,c) {}
354 
355  template<class Val, class A, class B>
356  ExecStatus
357  GqBin<Val,A,B>::post(Home home, A x0, B x1, Val c) {
358  (void) new (home) GqBin<Val,A,B>(home,x0,x1,c);
359  return ES_OK;
360  }
361 
362 
363  template<class Val, class A, class B>
366  : LinBin<Val,A,B,PC_INT_BND>(home,share,p) {}
367 
368  template<class Val, class A, class B>
369  Actor*
370  GqBin<Val,A,B>::copy(Space& home, bool share) {
371  return new (home) GqBin<Val,A,B>(home,share,*this);
372  }
373 
374  template<class Val, class A, class B>
376  GqBin<Val,A,B>::GqBin(Space& home, bool share, Propagator& p,
377  A x0, B x1, Val c)
378  : LinBin<Val,A,B,PC_INT_BND>(home,share,p,x0,x1,c) {}
379 
380  template<class Val, class A, class B>
381  ExecStatus
383  GECODE_ME_CHECK(x0.gq(home,c-x1.max()));
384  GECODE_ME_CHECK(x1.gq(home,c-x0.max()));
385  return (x0.min()+x1.min() >= c) ? home.ES_SUBSUMED(*this) : ES_FIX;
386  }
387 
388 
389 
390 
391  /*
392  * Reified binary domain consistent less equal
393  *
394  */
395 
396  template<class Val, class A, class B>
398  ReLqBin<Val,A,B>::ReLqBin(Home home, A x0, B x1, Val c, BoolView b)
399  : ReLinBin<Val,A,B,PC_INT_BND,BoolView>(home,x0,x1,c,b) {}
400 
401  template<class Val, class A, class B>
402  ExecStatus
403  ReLqBin<Val,A,B>::post(Home home, A x0, B x1, Val c, BoolView b) {
404  (void) new (home) ReLqBin<Val,A,B>(home,x0,x1,c,b);
405  return ES_OK;
406  }
407 
408 
409  template<class Val, class A, class B>
412  : ReLinBin<Val,A,B,PC_INT_BND,BoolView>(home,share,p) {}
413 
414  template<class Val, class A, class B>
415  Actor*
416  ReLqBin<Val,A,B>::copy(Space& home, bool share) {
417  return new (home) ReLqBin<Val,A,B>(home,share,*this);
418  }
419 
420  template<class Val, class A, class B>
421  ExecStatus
423  if (b.one())
424  GECODE_REWRITE(*this,(LqBin<Val,A,B>::post(home(*this),x0,x1,c)));
425  if (b.zero())
426  GECODE_REWRITE(*this,(GqBin<Val,A,B>::post(home(*this),x0,x1,c+1)));
427  if (x0.max() + x1.max() <= c) {
428  GECODE_ME_CHECK(b.one_none(home)); return home.ES_SUBSUMED(*this);
429  }
430  if (x0.min() + x1.min() > c) {
431  GECODE_ME_CHECK(b.zero_none(home)); return home.ES_SUBSUMED(*this);
432  }
433  return ES_FIX;
434  }
435 
436 }}}
437 
438 // STATISTICS: int-prop
439