this repo has no description
dekker.one
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 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.org
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
34namespace Gecode { namespace Int { namespace Linear {
35
36 /*
37 * Ternary linear propagators
38 *
39 */
40 template<class Val, class A, class B, class C, PropCond pc>
41 forceinline
42 LinTer<Val,A,B,C,pc>::LinTer(Home home, A y0, B y1, C y2, Val c0)
43 : Propagator(home), x0(y0), x1(y1), x2(y2), c(c0) {
44 x0.subscribe(home,*this,pc);
45 x1.subscribe(home,*this,pc);
46 x2.subscribe(home,*this,pc);
47 }
48
49 template<class Val, class A, class B, class C, PropCond pc>
50 forceinline
51 LinTer<Val,A,B,C,pc>::LinTer(Space& home, LinTer<Val,A,B,C,pc>& p)
52 : Propagator(home,p), c(p.c) {
53 x0.update(home,p.x0);
54 x1.update(home,p.x1);
55 x2.update(home,p.x2);
56 }
57
58 template<class Val, class A, class B, class C, PropCond pc>
59 forceinline
60 LinTer<Val,A,B,C,pc>::LinTer(Space& home, Propagator& p,
61 A y0, B y1, C y2, Val c0)
62 : Propagator(home,p), c(c0) {
63 x0.update(home,y0);
64 x1.update(home,y1);
65 x2.update(home,y2);
66 }
67
68 template<class Val, class A, class B, class C, PropCond pc>
69 PropCost
70 LinTer<Val,A,B,C,pc>::cost(const Space&, const ModEventDelta&) const {
71 return PropCost::ternary(PropCost::LO);
72 }
73
74 template<class Val, class A, class B, class C, PropCond pc>
75 void
76 LinTer<Val,A,B,C,pc>::reschedule(Space& home) {
77 x0.reschedule(home,*this,pc);
78 x1.reschedule(home,*this,pc);
79 x2.reschedule(home,*this,pc);
80 }
81
82 template<class Val, class A, class B, class C, PropCond pc>
83 forceinline size_t
84 LinTer<Val,A,B,C,pc>::dispose(Space& home) {
85 x0.cancel(home,*this,pc);
86 x1.cancel(home,*this,pc);
87 x2.cancel(home,*this,pc);
88 (void) Propagator::dispose(home);
89 return sizeof(*this);
90 }
91
92 /*
93 * Equality propagator
94 *
95 */
96
97 template<class Val, class A, class B, class C>
98 forceinline
99 EqTer<Val,A,B,C>::EqTer(Home home, A x0, B x1, C x2, Val c)
100 : LinTer<Val,A,B,C,PC_INT_BND>(home,x0,x1,x2,c) {}
101
102 template<class Val, class A, class B, class C>
103 ExecStatus
104 EqTer<Val,A,B,C>::post(Home home, A x0, B x1, C x2, Val c) {
105 (void) new (home) EqTer<Val,A,B,C>(home,x0,x1,x2,c);
106 return ES_OK;
107 }
108
109
110 template<class Val, class A, class B, class C>
111 forceinline
112 EqTer<Val,A,B,C>::EqTer(Space& home, EqTer<Val,A,B,C>& p)
113 : LinTer<Val,A,B,C,PC_INT_BND>(home,p) {}
114
115 template<class Val, class A, class B, class C>
116 forceinline
117 EqTer<Val,A,B,C>::EqTer(Space& home, Propagator& p,
118 A x0, B x1, C x2, Val c)
119 : LinTer<Val,A,B,C,PC_INT_BND>(home,p,x0,x1,x2,c) {}
120
121 template<class Val, class A, class B, class C>
122 Actor*
123 EqTer<Val,A,B,C>::copy(Space& home) {
124 return new (home) EqTer<Val,A,B,C>(home,*this);
125 }
126
127 /// Describe which view has been modified how
128 enum TerMod {
129 TM_X0_MIN = 1<<0,
130 TM_X0_MAX = 1<<1,
131 TM_X1_MIN = 1<<2,
132 TM_X1_MAX = 1<<3,
133 TM_X2_MIN = 1<<4,
134 TM_X2_MAX = 1<<5,
135 TM_ALL = TM_X0_MIN|TM_X0_MAX|TM_X1_MIN|TM_X1_MAX|TM_X2_MIN|TM_X2_MAX
136 };
137
138#define GECODE_INT_PV(CASE,TELL,UPDATE) \
139 if (bm & (CASE)) { \
140 bm -= (CASE); ModEvent me = (TELL); \
141 if (me_failed(me)) return ES_FAILED; \
142 if (me_modified(me)) bm |= (UPDATE); \
143 }
144
145 template<class Val, class A, class B, class C>
146 ExecStatus
147 EqTer<Val,A,B,C>::propagate(Space& home, const ModEventDelta&) {
148 int bm = TM_ALL;
149 do {
150 GECODE_INT_PV(TM_X0_MIN, x0.gq(home,c-x1.max()-x2.max()),
151 TM_X1_MAX | TM_X2_MAX);
152 GECODE_INT_PV(TM_X1_MIN, x1.gq(home,c-x0.max()-x2.max()),
153 TM_X0_MAX | TM_X2_MAX);
154 GECODE_INT_PV(TM_X2_MIN, x2.gq(home,c-x0.max()-x1.max()),
155 TM_X0_MAX | TM_X1_MAX);
156 GECODE_INT_PV(TM_X0_MAX, x0.lq(home,c-x1.min()-x2.min()),
157 TM_X1_MIN | TM_X2_MIN);
158 GECODE_INT_PV(TM_X1_MAX, x1.lq(home,c-x0.min()-x2.min()),
159 TM_X0_MIN | TM_X2_MIN);
160 GECODE_INT_PV(TM_X2_MAX, x2.lq(home,c-x0.min()-x1.min()),
161 TM_X0_MIN | TM_X1_MIN);
162 } while (bm);
163 return (x0.assigned() && x1.assigned()) ?
164 home.ES_SUBSUMED(*this) : ES_FIX;
165 }
166
167#undef GECODE_INT_PV
168
169
170
171 /*
172 * Disequality propagator
173 *
174 */
175
176 template<class Val, class A, class B, class C>
177 forceinline
178 NqTer<Val,A,B,C>::NqTer(Home home, A x0, B x1, C x2, Val c)
179 : LinTer<Val,A,B,C,PC_INT_VAL>(home,x0,x1,x2,c) {}
180
181 template<class Val, class A, class B, class C>
182 ExecStatus
183 NqTer<Val,A,B,C>::post(Home home, A x0, B x1, C x2, Val c) {
184 (void) new (home) NqTer<Val,A,B,C>(home,x0,x1,x2,c);
185 return ES_OK;
186 }
187
188
189 template<class Val, class A, class B, class C>
190 forceinline
191 NqTer<Val,A,B,C>::NqTer(Space& home, NqTer<Val,A,B,C>& p)
192 : LinTer<Val,A,B,C,PC_INT_VAL>(home,p) {}
193
194 template<class Val, class A, class B, class C>
195 Actor*
196 NqTer<Val,A,B,C>::copy(Space& home) {
197 return new (home) NqTer<Val,A,B,C>(home,*this);
198 }
199
200 template<class Val, class A, class B, class C>
201 forceinline
202 NqTer<Val,A,B,C>::NqTer(Space& home, Propagator& p,
203 A x0, B x1, C x2, Val c)
204 : LinTer<Val,A,B,C,PC_INT_VAL>(home,p,x0,x1,x2,c) {}
205
206
207 template<class Val, class A, class B, class C>
208 ExecStatus
209 NqTer<Val,A,B,C>::propagate(Space& home, const ModEventDelta&) {
210 if (x0.assigned() && x1.assigned()) {
211 GECODE_ME_CHECK(x2.nq(home,c-x0.val()-x1.val()));
212 return home.ES_SUBSUMED(*this);
213 }
214 if (x0.assigned() && x2.assigned()) {
215 GECODE_ME_CHECK(x1.nq(home,c-x0.val()-x2.val()));
216 return home.ES_SUBSUMED(*this);
217 }
218 if (x1.assigned() && x2.assigned()) {
219 GECODE_ME_CHECK(x0.nq(home,c-x1.val()-x2.val()));
220 return home.ES_SUBSUMED(*this);
221 }
222 return ES_FIX;
223 }
224
225
226
227 /*
228 * Inequality propagator
229 *
230 */
231
232 template<class Val, class A, class B, class C>
233 forceinline
234 LqTer<Val,A,B,C>::LqTer(Home home, A x0, B x1, C x2, Val c)
235 : LinTer<Val,A,B,C,PC_INT_BND>(home,x0,x1,x2,c) {}
236
237 template<class Val, class A, class B, class C>
238 ExecStatus
239 LqTer<Val,A,B,C>::post(Home home, A x0, B x1, C x2, Val c) {
240 (void) new (home) LqTer<Val,A,B,C>(home,x0,x1,x2,c);
241 return ES_OK;
242 }
243
244
245 template<class Val, class A, class B, class C>
246 forceinline
247 LqTer<Val,A,B,C>::LqTer(Space& home, LqTer<Val,A,B,C>& p)
248 : LinTer<Val,A,B,C,PC_INT_BND>(home,p) {}
249
250 template<class Val, class A, class B, class C>
251 Actor*
252 LqTer<Val,A,B,C>::copy(Space& home) {
253 return new (home) LqTer<Val,A,B,C>(home,*this);
254 }
255
256
257 template<class Val, class A, class B, class C>
258 forceinline
259 LqTer<Val,A,B,C>::LqTer(Space& home, Propagator& p,
260 A x0, B x1, C x2, Val c)
261 : LinTer<Val,A,B,C,PC_INT_BND>(home,p,x0,x1,x2,c) {}
262
263 template<class Val, class A, class B, class C>
264 ExecStatus
265 LqTer<Val,A,B,C>::propagate(Space& home, const ModEventDelta&) {
266 GECODE_ME_CHECK(x0.lq(home,c-x1.min()-x2.min()));
267 GECODE_ME_CHECK(x1.lq(home,c-x0.min()-x2.min()));
268 GECODE_ME_CHECK(x2.lq(home,c-x0.min()-x1.min()));
269 return (x0.max()+x1.max()+x2.max() <= c) ?
270 home.ES_SUBSUMED(*this) : ES_FIX;
271 }
272
273}}}
274
275// STATISTICS: int-prop
276