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