Generated on Wed Jan 24 2018 21:22:26 for Gecode by doxygen 1.8.13
int-ter.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: 2016-06-29 17:28:17 +0200 (Wed, 29 Jun 2016) $ by $Author: schulte $
11  * $Revision: 15137 $
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  * Ternary linear propagators
42  *
43  */
44  template<class Val, class A, class B, class C, PropCond pc>
46  LinTer<Val,A,B,C,pc>::LinTer(Home home, A y0, B y1, C y2, Val c0)
47  : Propagator(home), x0(y0), x1(y1), x2(y2), c(c0) {
48  x0.subscribe(home,*this,pc);
49  x1.subscribe(home,*this,pc);
50  x2.subscribe(home,*this,pc);
51  }
52 
53  template<class Val, class A, class B, class C, PropCond pc>
57  : Propagator(home,share,p), c(p.c) {
58  x0.update(home,share,p.x0);
59  x1.update(home,share,p.x1);
60  x2.update(home,share,p.x2);
61  }
62 
63  template<class Val, class A, class B, class C, PropCond pc>
66  A y0, B y1, C y2, Val c0)
67  : Propagator(home,share,p), c(c0) {
68  x0.update(home,share,y0);
69  x1.update(home,share,y1);
70  x2.update(home,share,y2);
71  }
72 
73  template<class Val, class A, class B, class C, PropCond pc>
74  PropCost
76  return PropCost::ternary(PropCost::LO);
77  }
78 
79  template<class Val, class A, class B, class C, PropCond pc>
80  void
82  x0.reschedule(home,*this,pc);
83  x1.reschedule(home,*this,pc);
84  x2.reschedule(home,*this,pc);
85  }
86 
87  template<class Val, class A, class B, class C, PropCond pc>
88  forceinline size_t
90  x0.cancel(home,*this,pc);
91  x1.cancel(home,*this,pc);
92  x2.cancel(home,*this,pc);
93  (void) Propagator::dispose(home);
94  return sizeof(*this);
95  }
96 
97  /*
98  * Equality propagator
99  *
100  */
101 
102  template<class Val, class A, class B, class C>
104  EqTer<Val,A,B,C>::EqTer(Home home, A x0, B x1, C x2, Val c)
105  : LinTer<Val,A,B,C,PC_INT_BND>(home,x0,x1,x2,c) {}
106 
107  template<class Val, class A, class B, class C>
108  ExecStatus
109  EqTer<Val,A,B,C>::post(Home home, A x0, B x1, C x2, Val c) {
110  (void) new (home) EqTer<Val,A,B,C>(home,x0,x1,x2,c);
111  return ES_OK;
112  }
113 
114 
115  template<class Val, class A, class B, class C>
118  : LinTer<Val,A,B,C,PC_INT_BND>(home,share,p) {}
119 
120  template<class Val, class A, class B, class C>
123  A x0, B x1, C x2, Val c)
124  : LinTer<Val,A,B,C,PC_INT_BND>(home,share,p,x0,x1,x2,c) {}
125 
126  template<class Val, class A, class B, class C>
127  Actor*
128  EqTer<Val,A,B,C>::copy(Space& home, bool share) {
129  return new (home) EqTer<Val,A,B,C>(home,share,*this);
130  }
131 
133  enum TerMod {
134  TM_X0_MIN = 1<<0,
135  TM_X0_MAX = 1<<1,
136  TM_X1_MIN = 1<<2,
137  TM_X1_MAX = 1<<3,
138  TM_X2_MIN = 1<<4,
139  TM_X2_MAX = 1<<5,
141  };
142 
143 #define GECODE_INT_PV(CASE,TELL,UPDATE) \
144  if (bm & (CASE)) { \
145  bm -= (CASE); ModEvent me = (TELL); \
146  if (me_failed(me)) return ES_FAILED; \
147  if (me_modified(me)) bm |= (UPDATE); \
148  }
149 
150  template<class Val, class A, class B, class C>
151  ExecStatus
153  int bm = TM_ALL;
154  do {
155  GECODE_INT_PV(TM_X0_MIN, x0.gq(home,c-x1.max()-x2.max()),
156  TM_X1_MAX | TM_X2_MAX);
157  GECODE_INT_PV(TM_X1_MIN, x1.gq(home,c-x0.max()-x2.max()),
158  TM_X0_MAX | TM_X2_MAX);
159  GECODE_INT_PV(TM_X2_MIN, x2.gq(home,c-x0.max()-x1.max()),
160  TM_X0_MAX | TM_X1_MAX);
161  GECODE_INT_PV(TM_X0_MAX, x0.lq(home,c-x1.min()-x2.min()),
162  TM_X1_MIN | TM_X2_MIN);
163  GECODE_INT_PV(TM_X1_MAX, x1.lq(home,c-x0.min()-x2.min()),
164  TM_X0_MIN | TM_X2_MIN);
165  GECODE_INT_PV(TM_X2_MAX, x2.lq(home,c-x0.min()-x1.min()),
166  TM_X0_MIN | TM_X1_MIN);
167  } while (bm);
168  return (x0.assigned() && x1.assigned()) ?
169  home.ES_SUBSUMED(*this) : ES_FIX;
170  }
171 
172 #undef GECODE_INT_PV
173 
174 
175 
176  /*
177  * Disequality propagator
178  *
179  */
180 
181  template<class Val, class A, class B, class C>
183  NqTer<Val,A,B,C>::NqTer(Home home, A x0, B x1, C x2, Val c)
184  : LinTer<Val,A,B,C,PC_INT_VAL>(home,x0,x1,x2,c) {}
185 
186  template<class Val, class A, class B, class C>
187  ExecStatus
188  NqTer<Val,A,B,C>::post(Home home, A x0, B x1, C x2, Val c) {
189  (void) new (home) NqTer<Val,A,B,C>(home,x0,x1,x2,c);
190  return ES_OK;
191  }
192 
193 
194  template<class Val, class A, class B, class C>
197  : LinTer<Val,A,B,C,PC_INT_VAL>(home,share,p) {}
198 
199  template<class Val, class A, class B, class C>
200  Actor*
201  NqTer<Val,A,B,C>::copy(Space& home, bool share) {
202  return new (home) NqTer<Val,A,B,C>(home,share,*this);
203  }
204 
205  template<class Val, class A, class B, class C>
208  A x0, B x1, C x2, Val c)
209  : LinTer<Val,A,B,C,PC_INT_VAL>(home,share,p,x0,x1,x2,c) {}
210 
211 
212  template<class Val, class A, class B, class C>
213  ExecStatus
215  if (x0.assigned() && x1.assigned()) {
216  GECODE_ME_CHECK(x2.nq(home,c-x0.val()-x1.val()));
217  return home.ES_SUBSUMED(*this);
218  }
219  if (x0.assigned() && x2.assigned()) {
220  GECODE_ME_CHECK(x1.nq(home,c-x0.val()-x2.val()));
221  return home.ES_SUBSUMED(*this);
222  }
223  if (x1.assigned() && x2.assigned()) {
224  GECODE_ME_CHECK(x0.nq(home,c-x1.val()-x2.val()));
225  return home.ES_SUBSUMED(*this);
226  }
227  return ES_FIX;
228  }
229 
230 
231 
232  /*
233  * Inequality propagator
234  *
235  */
236 
237  template<class Val, class A, class B, class C>
239  LqTer<Val,A,B,C>::LqTer(Home home, A x0, B x1, C x2, Val c)
240  : LinTer<Val,A,B,C,PC_INT_BND>(home,x0,x1,x2,c) {}
241 
242  template<class Val, class A, class B, class C>
243  ExecStatus
244  LqTer<Val,A,B,C>::post(Home home, A x0, B x1, C x2, Val c) {
245  (void) new (home) LqTer<Val,A,B,C>(home,x0,x1,x2,c);
246  return ES_OK;
247  }
248 
249 
250  template<class Val, class A, class B, class C>
253  : LinTer<Val,A,B,C,PC_INT_BND>(home,share,p) {}
254 
255  template<class Val, class A, class B, class C>
256  Actor*
257  LqTer<Val,A,B,C>::copy(Space& home, bool share) {
258  return new (home) LqTer<Val,A,B,C>(home,share,*this);
259  }
260 
261 
262  template<class Val, class A, class B, class C>
265  A x0, B x1, C x2, Val c)
266  : LinTer<Val,A,B,C,PC_INT_BND>(home,share,p,x0,x1,x2,c) {}
267 
268  template<class Val, class A, class B, class C>
269  ExecStatus
271  GECODE_ME_CHECK(x0.lq(home,c-x1.min()-x2.min()));
272  GECODE_ME_CHECK(x1.lq(home,c-x0.min()-x2.min()));
273  GECODE_ME_CHECK(x2.lq(home,c-x0.min()-x1.min()));
274  return (x0.max()+x1.max()+x2.max() <= c) ?
275  home.ES_SUBSUMED(*this) : ES_FIX;
276  }
277 
278 }}}
279 
280 // STATISTICS: int-prop
281 
static ExecStatus post(Home home, A x0, B x1, C x2, Val c)
Post propagator for .
Definition: int-ter.hpp:188
virtual Actor * copy(Space &home, bool share)
Create copy during cloning.
Definition: int-ter.hpp:257
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3614
virtual Actor * copy(Space &home, bool share)
Create copy during cloning.
Definition: int-ter.hpp:201
Propagator for bounds consistent ternary linear equality
Definition: linear.hh:388
Base-class for propagators.
Definition: core.hpp:1092
Base-class for ternary linear propagators.
Definition: linear.hh:350
Propagation has computed fixpoint.
Definition: core.hpp:545
EqTer(Space &home, bool share, EqTer &p)
Constructor for cloning p.
Definition: int-ter.hpp:117
Computation spaces.
Definition: core.hpp:1748
LinTer(Space &home, bool share, LinTer &p)
Constructor for cloning p.
Definition: int-ter.hpp:55
Base-class for both propagators and branchers.
Definition: core.hpp:696
Propagator for bounds consistent ternary linear less or equal
Definition: linear.hh:458
Gecode::FloatVal c(-8, 8)
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Definition: var-type.hpp:91
static ExecStatus post(Home home, A x0, B x1, C x2, Val c)
Post propagator for .
Definition: int-ter.hpp:244
A x0
View of type A.
Definition: linear.hh:353
NqTer(Space &home, bool share, NqTer &p)
Constructor for cloning p.
Definition: int-ter.hpp:196
B x1
View of type B.
Definition: linear.hh:355
TerMod
Describe which view has been modified how.
Definition: int-ter.hpp:133
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:56
virtual Actor * copy(Space &home, bool share)
Create copy during cloning.
Definition: int-ter.hpp:128
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: int-ter.hpp:270
Propagation cost.
Definition: core.hpp:554
static ExecStatus post(Home home, A x0, B x1, C x2, Val c)
Post propagator for .
Definition: int-ter.hpp:109
ExecStatus
Definition: core.hpp:540
#define forceinline
Definition: config.hpp:173
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: int-ter.hpp:152
Execution is okay.
Definition: core.hpp:544
Gecode toplevel namespace
void reschedule(Space &home, Propagator &p, IntSet &y)
Definition: rel.hpp:96
Propagator for bounds consistent ternary linear disquality
Definition: linear.hh:423
int ModEventDelta
Modification event deltas.
Definition: core.hpp:169
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: int-ter.hpp:214
Home class for posting propagators
Definition: core.hpp:922
C x2
View of type C.
Definition: linear.hh:357
#define GECODE_INT_PV(CASE, TELL, UPDATE)
Definition: int-ter.hpp:143
LqTer(Space &home, bool share, LqTer &p)
Constructor for cloning p.
Definition: int-ter.hpp:252
const Gecode::PropCond PC_INT_VAL
Propagate when a view becomes assigned (single value)
Definition: var-type.hpp:82