Generated on Sat Feb 7 2015 02:01:24 for Gecode by doxygen 1.8.9.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: 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 
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>
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, ReifyMode rm>
201  ReEqBin<Val,A,B,Ctrl,rm>::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, ReifyMode rm>
205  ExecStatus
206  ReEqBin<Val,A,B,Ctrl,rm>::post(Home home, A x0, B x1, Val c, Ctrl b) {
207  (void) new (home) ReEqBin<Val,A,B,Ctrl,rm>(home,x0,x1,c,b);
208  return ES_OK;
209  }
210 
211 
212  template<class Val, class A, class B, class Ctrl, ReifyMode rm>
216  : ReLinBin<Val,A,B,PC_INT_BND,Ctrl>(home,share,p) {}
217 
218  template<class Val, class A, class B, class Ctrl, ReifyMode rm>
219  Actor*
221  return new (home) ReEqBin<Val,A,B,Ctrl,rm>(home,share,*this);
222  }
223 
224  template<class Val, class A, class B, class Ctrl, ReifyMode rm>
225  ExecStatus
227  if (b.zero()) {
228  if (rm == RM_IMP)
229  return home.ES_SUBSUMED(*this);
230  GECODE_REWRITE(*this,(NqBin<Val,A,B>::post(home(*this),x0,x1,c)));
231  }
232  if (b.one()) {
233  if (rm == RM_PMI)
234  return home.ES_SUBSUMED(*this);
235  GECODE_REWRITE(*this,(EqBin<Val,A,B>::post(home(*this),x0,x1,c)));
236  }
237  if ((x0.min() + x1.min() > c) || (x0.max() + x1.max() < c)) {
238  if (rm != RM_PMI)
239  GECODE_ME_CHECK(b.zero_none(home));
240  return home.ES_SUBSUMED(*this);
241  }
242  if (x0.assigned() && x1.assigned()) {
243  assert(x0.val() + x1.val() == c);
244  if (rm != RM_IMP)
245  GECODE_ME_CHECK(b.one_none(home));
246  return home.ES_SUBSUMED(*this);
247  }
248  return ES_FIX;
249  }
250 
251 
252 
253 
254  /*
255  * Binary domain consistent linear disequality
256  *
257  */
258  template<class Val, class A, class B>
260  NqBin<Val,A,B>::NqBin(Home home, A x0, B x1, Val c)
261  : LinBin<Val,A,B,PC_INT_VAL>(home,x0,x1,c) {}
262 
263  template<class Val, class A, class B>
264  ExecStatus
265  NqBin<Val,A,B>::post(Home home, A x0, B x1, Val c) {
266  (void) new (home) NqBin<Val,A,B>(home,x0,x1,c);
267  return ES_OK;
268  }
269 
270 
271  template<class Val, class A, class B>
274  : LinBin<Val,A,B,PC_INT_VAL>(home,share,p) {}
275 
276  template<class Val, class A, class B>
277  Actor*
278  NqBin<Val,A,B>::copy(Space& home, bool share) {
279  return new (home) NqBin<Val,A,B>(home,share,*this);
280  }
281 
282  template<class Val, class A, class B>
285  A x0, B x1, Val c)
286  : LinBin<Val,A,B,PC_INT_VAL>(home,share,p,x0,x1,c) {}
287 
288 
289 
290  template<class Val, class A, class B>
291  PropCost
292  NqBin<Val,A,B>::cost(const Space&, const ModEventDelta&) const {
294  }
295 
296  template<class Val, class A, class B>
297  ExecStatus
299  if (x0.assigned()) {
300  GECODE_ME_CHECK(x1.nq(home,c-x0.val()));
301  } else {
302  assert(x1.assigned());
303  GECODE_ME_CHECK(x0.nq(home,c-x1.val()));
304  }
305  return home.ES_SUBSUMED(*this);
306  }
307 
308 
309  /*
310  * Binary domain consistent less equal
311  *
312  */
313 
314  template<class Val, class A, class B>
316  LqBin<Val,A,B>::LqBin(Home home, A x0, B x1, Val c)
317  : LinBin<Val,A,B,PC_INT_BND>(home,x0,x1,c) {}
318 
319  template<class Val, class A, class B>
320  ExecStatus
321  LqBin<Val,A,B>::post(Home home, A x0, B x1, Val c) {
322  (void) new (home) LqBin<Val,A,B>(home,x0,x1,c);
323  return ES_OK;
324  }
325 
326 
327  template<class Val, class A, class B>
330  : LinBin<Val,A,B,PC_INT_BND>(home,share,p) {}
331 
332  template<class Val, class A, class B>
333  Actor*
334  LqBin<Val,A,B>::copy(Space& home, bool share) {
335  return new (home) LqBin<Val,A,B>(home,share,*this);
336  }
337 
338  template<class Val, class A, class B>
341  A x0, B x1, Val c)
342  : LinBin<Val,A,B,PC_INT_BND>(home,share,p,x0,x1,c) {}
343 
344  template<class Val, class A, class B>
345  ExecStatus
347  GECODE_ME_CHECK(x0.lq(home,c-x1.min()));
348  GECODE_ME_CHECK(x1.lq(home,c-x0.min()));
349  return (x0.max()+x1.max() <= c) ? home.ES_SUBSUMED(*this) : ES_FIX;
350  }
351 
352 
353 
354 
355  /*
356  * Binary domain consistent greater equal
357  *
358  */
359 
360  template<class Val, class A, class B>
362  GqBin<Val,A,B>::GqBin(Home home, A x0, B x1, Val c)
363  : LinBin<Val,A,B,PC_INT_BND>(home,x0,x1,c) {}
364 
365  template<class Val, class A, class B>
366  ExecStatus
367  GqBin<Val,A,B>::post(Home home, A x0, B x1, Val c) {
368  (void) new (home) GqBin<Val,A,B>(home,x0,x1,c);
369  return ES_OK;
370  }
371 
372 
373  template<class Val, class A, class B>
376  : LinBin<Val,A,B,PC_INT_BND>(home,share,p) {}
377 
378  template<class Val, class A, class B>
379  Actor*
380  GqBin<Val,A,B>::copy(Space& home, bool share) {
381  return new (home) GqBin<Val,A,B>(home,share,*this);
382  }
383 
384  template<class Val, class A, class B>
387  A x0, B x1, Val c)
388  : LinBin<Val,A,B,PC_INT_BND>(home,share,p,x0,x1,c) {}
389 
390  template<class Val, class A, class B>
391  ExecStatus
393  GECODE_ME_CHECK(x0.gq(home,c-x1.max()));
394  GECODE_ME_CHECK(x1.gq(home,c-x0.max()));
395  return (x0.min()+x1.min() >= c) ? home.ES_SUBSUMED(*this) : ES_FIX;
396  }
397 
398 
399 
400 
401  /*
402  * Reified binary domain consistent less equal
403  *
404  */
405 
406  template<class Val, class A, class B, ReifyMode rm>
408  ReLqBin<Val,A,B,rm>::ReLqBin(Home home, A x0, B x1, Val c, BoolView b)
409  : ReLinBin<Val,A,B,PC_INT_BND,BoolView>(home,x0,x1,c,b) {}
410 
411  template<class Val, class A, class B, ReifyMode rm>
412  ExecStatus
413  ReLqBin<Val,A,B,rm>::post(Home home, A x0, B x1, Val c, BoolView b) {
414  (void) new (home) ReLqBin<Val,A,B,rm>(home,x0,x1,c,b);
415  return ES_OK;
416  }
417 
418 
419  template<class Val, class A, class B, ReifyMode rm>
422  : ReLinBin<Val,A,B,PC_INT_BND,BoolView>(home,share,p) {}
423 
424  template<class Val, class A, class B, ReifyMode rm>
425  Actor*
426  ReLqBin<Val,A,B,rm>::copy(Space& home, bool share) {
427  return new (home) ReLqBin<Val,A,B,rm>(home,share,*this);
428  }
429 
430  template<class Val, class A, class B, ReifyMode rm>
431  ExecStatus
433  if (b.one()) {
434  if (rm == RM_PMI)
435  return home.ES_SUBSUMED(*this);
436  GECODE_REWRITE(*this,(LqBin<Val,A,B>::post(home(*this),x0,x1,c)));
437  }
438  if (b.zero()) {
439  if (rm == RM_IMP)
440  return home.ES_SUBSUMED(*this);
441  GECODE_REWRITE(*this,(GqBin<Val,A,B>::post(home(*this),x0,x1,c+1)));
442  }
443  if (x0.max() + x1.max() <= c) {
444  if (rm != RM_IMP)
445  GECODE_ME_CHECK(b.one_none(home));
446  return home.ES_SUBSUMED(*this);
447  }
448  if (x0.min() + x1.min() > c) {
449  if (rm != RM_PMI)
450  GECODE_ME_CHECK(b.zero_none(home));
451  return home.ES_SUBSUMED(*this);
452  }
453  return ES_FIX;
454  }
455 
456 }}}
457 
458 // STATISTICS: int-prop
459 
virtual Actor * copy(Space &home, bool share)
Create copy during cloning.
Definition: int-bin.hpp:278
Propagator for bounds consistent binary linear disequality
Definition: linear.hh:201
#define GECODE_REWRITE(prop, post)
Rewrite propagator by executing post function.
Definition: macros.hpp:109
BinMod
Describe which view has been modified how.
Definition: int-bin.hpp:160
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as low binary)
Definition: int-bin.hpp:71
Inverse implication for reification.
Definition: int.hh:847
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:2973
Propagator for bounds consistent binary linear greater or equal
Definition: linear.hh:271
B x1
View of type B.
Definition: linear.hh:74
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: int-bin.hpp:392
static ExecStatus post(Home home, A x0, B x1, Val c, BoolView b)
Post propagator for .
Definition: int-bin.hpp:413
LqBin(Space &home, bool share, LqBin &p)
Constructor for cloning p.
Definition: int-bin.hpp:329
GqBin(Space &home, bool share, GqBin &p)
Constructor for cloning p.
Definition: int-bin.hpp:375
Base-class for propagators.
Definition: core.hpp:755
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: int-bin.hpp:432
#define GECODE_INT_PV(CASE, TELL, UPDATE)
Definition: int-bin.hpp:168
Propagation has computed fixpoint.
Definition: core.hpp:528
static PropCost unary(PropCost::Mod m)
Single variable for modifier pcm.
Definition: core.hpp:4058
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-bin.hpp:346
Base-class for binary linear propagators.
Definition: linear.hh:69
Base-class for both propagators and branchers.
Definition: core.hpp:666
Gecode::FloatVal c(-8, 8)
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: int-bin.hpp:77
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: int-bin.hpp:116
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: int-bin.hpp:226
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Definition: var-type.hpp:91
virtual Actor * copy(Space &home, bool share)
Create copy during cloning.
Definition: int-bin.hpp:220
Propagator for bounds consistent binary linear less or equal
Definition: linear.hh:237
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as low binary)
Definition: int-bin.hpp:110
ReLinBin(Space &home, bool share, ReLinBin &p)
Constructor for cloning p.
Definition: int-bin.hpp:100
static ExecStatus post(Home home, A x0, B x1, Val c, Ctrl b)
Post propagator for .
Definition: int-bin.hpp:206
B x1
View of type B.
Definition: linear.hh:105
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:45
Propagator for reified bounds consistent binary linear less or equal
Definition: linear.hh:305
virtual Actor * copy(Space &home, bool share)
Create copy during cloning.
Definition: int-bin.hpp:426
static ExecStatus post(Home home, A x0, B x1, Val c)
Post propagator for .
Definition: int-bin.hpp:136
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:2877
Propagation cost.
Definition: core.hpp:537
Base-class for reified binary linear propagators.
Definition: linear.hh:100
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: int-bin.hpp:177
ExecStatus
Definition: core.hpp:523
static ExecStatus post(Home home, A x0, B x1, Val c)
Post propagator for .
Definition: int-bin.hpp:265
virtual Actor * copy(Space &home, bool share)
Create copy during cloning.
Definition: int-bin.hpp:155
#define forceinline
Definition: config.hpp:132
Ctrl b
Control view for reification.
Definition: linear.hh:109
Propagator for reified bounds consistent binary linear equality
Definition: linear.hh:168
virtual Actor * copy(Space &home, bool share)
Create copy during cloning.
Definition: int-bin.hpp:334
Execution is okay.
Definition: core.hpp:527
A x0
View of type A.
Definition: linear.hh:72
virtual Actor * copy(Space &home, bool share)
Create copy during cloning.
Definition: int-bin.hpp:380
struct Gecode::@518::NNF::@57::@58 b
For binary nodes (and, or, eqv)
LinBin(Space &home, bool share, LinBin &p)
Constructor for cloning p.
Definition: int-bin.hpp:54
Gecode toplevel namespace
A x0
View of type A.
Definition: linear.hh:103
NqBin(Space &home, bool share, NqBin &p)
Constructor for cloning p.
Definition: int-bin.hpp:273
Implication for reification.
Definition: int.hh:840
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as low unary)
Definition: int-bin.hpp:292
static ExecStatus post(Home home, A x0, B x1, Val c)
Post propagator for .
Definition: int-bin.hpp:321
friend FloatVal max(const FloatVal &x, const FloatVal &y)
Definition: val.hpp:390
int ModEventDelta
Modification event deltas.
Definition: core.hpp:173
friend FloatVal min(const FloatVal &x, const FloatVal &y)
Definition: val.hpp:402
static ExecStatus post(Home home, A x0, B x1, Val c)
Post propagator for .
Definition: int-bin.hpp:367
ReLqBin(Space &home, bool share, ReLqBin &p)
Constructor for cloning p.
Definition: int-bin.hpp:421
Home class for posting propagators
Definition: core.hpp:717
ReEqBin(Space &home, bool share, ReEqBin &p)
Constructor for cloning p.
Definition: int-bin.hpp:214
static PropCost binary(PropCost::Mod m)
Two variables for modifier pcm.
Definition: core.hpp:4054
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: int-bin.hpp:298
EqBin(Space &home, bool share, EqBin &p)
Constructor for cloning p.
Definition: int-bin.hpp:144
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