Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
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 * 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>
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>
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>
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>
73
74 template<class Val, class A, class B, class C, PropCond pc>
75 void
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
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>
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>
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>
113 : LinTer<Val,A,B,C,PC_INT_BND>(home,p) {}
114
115 template<class Val, class A, class B, class C>
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*
124 return new (home) EqTer<Val,A,B,C>(home,*this);
125 }
126
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>
148 int bm = TM_ALL;
149 do {
150 GECODE_INT_PV(TM_X0_MIN, x0.gq(home,c-x1.max()-x2.max()),
152 GECODE_INT_PV(TM_X1_MIN, x1.gq(home,c-x0.max()-x2.max()),
154 GECODE_INT_PV(TM_X2_MIN, x2.gq(home,c-x0.max()-x1.max()),
156 GECODE_INT_PV(TM_X0_MAX, x0.lq(home,c-x1.min()-x2.min()),
158 GECODE_INT_PV(TM_X1_MAX, x1.lq(home,c-x0.min()-x2.min()),
160 GECODE_INT_PV(TM_X2_MAX, x2.lq(home,c-x0.min()-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>
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>
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>
192 : LinTer<Val,A,B,C,PC_INT_VAL>(home,p) {}
193
194 template<class Val, class A, class B, class C>
195 Actor*
197 return new (home) NqTer<Val,A,B,C>(home,*this);
198 }
199
200 template<class Val, class A, class B, class C>
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>
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>
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>
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>
248 : LinTer<Val,A,B,C,PC_INT_BND>(home,p) {}
249
250 template<class Val, class A, class B, class C>
251 Actor*
253 return new (home) LqTer<Val,A,B,C>(home,*this);
254 }
255
256
257 template<class Val, class A, class B, class C>
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>
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
Base-class for both propagators and branchers.
Definition core.hpp:628
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition core.hpp:3256
Home class for posting propagators
Definition core.hpp:856
Propagator for bounds consistent ternary linear equality
Definition linear.hh:384
EqTer(Space &home, EqTer &p)
Constructor for cloning p.
static ExecStatus post(Home home, A x0, B x1, C x2, Val c)
Post propagator for .
Definition int-ter.hpp:104
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition int-ter.hpp:147
virtual Actor * copy(Space &home)
Create copy during cloning.
Definition int-ter.hpp:123
Base-class for ternary linear propagators.
Definition linear.hh:346
C x2
View of type C.
Definition linear.hh:353
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as low ternary)
Definition int-ter.hpp:70
LinTer(Space &home, LinTer &p)
Constructor for cloning p.
A x0
View of type A.
Definition linear.hh:349
Val c
Value of type Val.
Definition linear.hh:355
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition int-ter.hpp:84
virtual void reschedule(Space &home)
Schedule function.
Definition int-ter.hpp:76
B x1
View of type B.
Definition linear.hh:351
Propagator for bounds consistent ternary linear less or equal
Definition linear.hh:454
virtual Actor * copy(Space &home)
Create copy during cloning.
Definition int-ter.hpp:252
static ExecStatus post(Home home, A x0, B x1, C x2, Val c)
Post propagator for .
Definition int-ter.hpp:239
LqTer(Space &home, LqTer &p)
Constructor for cloning p.
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition int-ter.hpp:265
Propagator for bounds consistent ternary linear disquality
Definition linear.hh:419
virtual Actor * copy(Space &home)
Create copy during cloning.
Definition int-ter.hpp:196
static ExecStatus post(Home home, A x0, B x1, C x2, Val c)
Post propagator for .
Definition int-ter.hpp:183
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition int-ter.hpp:209
NqTer(Space &home, NqTer &p)
Constructor for cloning p.
Propagation cost.
Definition core.hpp:486
static PropCost ternary(PropCost::Mod m)
Three variables for modifier pcm.
Definition core.hpp:4812
Base-class for propagators.
Definition core.hpp:1066
friend class Space
Definition core.hpp:1068
Propagator(Home home)
Constructor for posting.
Definition core.hpp:3505
Computation spaces.
Definition core.hpp:1744
ExecStatus ES_SUBSUMED(Propagator &p)
Propagator p is subsumed
Definition core.hpp:3570
int ModEventDelta
Modification event deltas.
Definition core.hpp:89
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition macros.hpp:52
#define GECODE_INT_PV(CASE, TELL, UPDATE)
Definition int-bin.hpp:179
Linear propagators
TerMod
Describe which view has been modified how.
Definition int-ter.hpp:128
Finite domain integers.
const Gecode::PropCond PC_INT_VAL
Propagate when a view becomes assigned (single value)
Definition var-type.hpp:82
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Definition var-type.hpp:91
Gecode toplevel namespace
ExecStatus
Definition core.hpp:472
@ ES_OK
Execution is okay.
Definition core.hpp:476
@ ES_FIX
Propagation has computed fixpoint.
Definition core.hpp:477
#define forceinline
Definition config.hpp:194