Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
view.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 * Contributing authors:
7 * Guido Tack <tack@gecode.org>
8 *
9 * Copyright:
10 * Christian Schulte, 2004
11 * Guido Tack, 2004
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#include <algorithm>
39
40namespace Gecode { namespace Int { namespace Element {
41
46 template<class VA, class VC>
47 class RelTestBnd {
48 public:
49 RelTest operator ()(VA,VC);
50 };
55 template<class VA>
57 public:
59 };
60
65 template<class VA, class VC>
66 class RelTestDom {
67 public:
68 RelTest operator ()(VA,VC);
69 };
74 template<class VA>
76 public:
78 };
79
80
81 template<class VA, class VC>
84 return rtest_eq_bnd(x,y);
85 }
86 template<class VA>
91
92 template<class VA, class VC>
95 return rtest_eq_dom(x,y);
96 }
97 template<class VA>
102
103
104
105
106 /*
107 * Base class
108 *
109 */
110
111 template<class VA, class VB, class VC, PropCond pc_ac>
113 VB y0, VC y1)
114 : Propagator(home), iv(iv0), x0(y0), x1(y1) {
115 x0.subscribe(home,*this,PC_INT_DOM);
116 x1.subscribe(home,*this,pc_ac);
117 iv.subscribe(home,*this,pc_ac);
118 }
119
120 template<class VA, class VB, class VC, PropCond pc_ac>
123 : Propagator(home,p) {
124 x0.update(home,p.x0);
125 x1.update(home,p.x1);
126 iv.update(home,p.iv);
127 }
128
129 template<class VA, class VB, class VC, PropCond pc_ac>
132 // This is required for subscribing to variables in the
133 // above constructor, but this is then the only time this
134 // virtual function is ever used!
135 return PropCost::linear(PropCost::LO,iv.size()+2);
136 }
137
138 template<class VA, class VB, class VC, PropCond pc_ac>
139 void
141 x0.reschedule(home,*this,PC_INT_DOM);
142 x1.reschedule(home,*this,pc_ac);
143 iv.reschedule(home,*this,pc_ac);
144 }
145
146 template<class VA, class VB, class VC, PropCond pc_ac>
147 forceinline size_t
149 x0.cancel(home,*this,PC_INT_DOM);
150 x1.cancel(home,*this,pc_ac);
151 iv.cancel(home,*this,pc_ac);
152 (void) Propagator::dispose(home);
153 return sizeof(*this);
154 }
155
156
157
158
163 template<class View>
165 private:
166 const IdxView<View> *cur, *end;
167 public:
168 IterIdxView(void);
170 void init(const IdxView<View>*, const IdxView<View>*);
171 bool operator ()(void) const;
172 void operator ++(void);
173 int val(void) const;
174 };
175
176 template<class View>
179 template<class View>
182 const IdxView<View>* e)
183 : cur(b), end(e) {}
184 template<class View>
185 forceinline void
187 const IdxView<View>* e) {
188 cur=b; end=e;
189 }
190 template<class View>
191 forceinline bool
193 return cur < end;
194 }
195 template<class View>
196 forceinline void
198 cur++;
199 }
200 template<class View>
201 forceinline int
203 return cur->idx;
204 }
205
206
207
208
209 /*
210 * Generic scanning: does all but computing new domain for result
211 * (which is specific to bounds/domain version)
213 */
215 template<class VA, class VB, class VC, PropCond pc_ac, class RelTest>
218 VB x0, VC x1, Propagator& p, RelTest rt) {
219 assert(iv.size() > 1);
220 /*
221 * Prunes pairs of index, variable
222 * - checks for idx value removed
223 * - checks for disequal variables
224 *
225 */
226 ViewValues<VB> vx0(x0);
227 int i = 0;
228 int j = 0;
229 while (vx0() && (i < iv.size())) {
230 if (iv[i].idx < vx0.val()) {
231 iv[i].view.cancel(home,p,pc_ac);
232 ++i;
233 } else if (iv[i].idx > vx0.val()) {
234 ++vx0;
235 } else {
236 assert(iv[i].idx == vx0.val());
237 switch (rt(iv[i].view,x1)) {
238 case RT_FALSE:
239 iv[i].view.cancel(home,p,pc_ac);
240 break;
241 case RT_TRUE:
242 case RT_MAYBE:
243 iv[j++] = iv[i];
244 break;
245 default: GECODE_NEVER;
246 }
247 ++vx0; ++i;
248 }
249 }
250 while (i < iv.size())
251 iv[i++].view.cancel(home,p,pc_ac);
252 bool adjust = (j<iv.size());
253 iv.size(j);
254
255 if (iv.size() == 0)
256 return ES_FAILED;
257
258 if (iv.size() == 1) {
259 GECODE_ME_CHECK(x0.eq(home,iv[0].idx));
260 } else if (adjust) {
261 IterIdxView<VA> v(&iv[0],&iv[0]+iv.size());
262 GECODE_ME_CHECK(x0.narrow_v(home,v,false));
263 assert(x0.size() == static_cast<unsigned int>(iv.size()));
264 }
265 return ES_OK;
266 }
267
268
269
270
271 /*
272 * Bounds consistent propagator
273 *
274 */
275
276 template<class VA, class VB, class VC>
279 IdxViewArray<VA>& iv, VB x0, VC x1)
280 : View<VA,VB,VC,PC_INT_BND>(home,iv,x0,x1) {}
281
282 template<class VA, class VB, class VC>
285 IdxViewArray<VA>& iv, VB x0, VC x1) {
286 GECODE_ME_CHECK(x0.gq(home,0));
287 GECODE_ME_CHECK(x0.le(home,iv.size()));
288 if (x0.assigned()) {
289 (void) new (home) Rel::EqBnd<VA,VC>(home,iv[x0.val()].view,x1);
290 return ES_OK;
291 } else {
292 assert(iv.size()>1);
293 (void) new (home) ViewBnd<VA,VB,VC>(home,iv,x0,x1);
294 }
295 return ES_OK;
296 }
297
298
299 template<class VA, class VB, class VC>
302 : View<VA,VB,VC,PC_INT_BND>(home,p) {}
303
304 template<class VA, class VB, class VC>
305 Actor*
307 return new (home) ViewBnd<VA,VB,VC>(home,*this);
308 }
309
310 template<class VA, class VB, class VC>
313 assert(iv.size() > 1);
316 (home,iv,x0,x1,*this,rt)));
317 if (iv.size() == 1) {
318 ExecStatus es = home.ES_SUBSUMED(*this);
319 (void) new (home) Rel::EqBnd<VA,VC>(home(*this),iv[0].view,x1);
320 return es;
321 }
322 assert(iv.size() > 1);
323 // Compute new result
324 int min = iv[0].view.min();
325 int max = iv[0].view.max();
326 for (int i=1; i<iv.size(); i++) {
327 min = std::min(iv[i].view.min(),min);
328 max = std::max(iv[i].view.max(),max);
329 }
330 ExecStatus es = shared(x0,x1) ? ES_NOFIX : ES_FIX;
331 {
332 ModEvent me = x1.lq(home,max);
333 if (me_failed(me))
334 return ES_FAILED;
335 if (me_modified(me) && (x1.max() != max))
336 es = ES_NOFIX;
337 }
338 {
339 ModEvent me = x1.gq(home,min);
340 if (me_failed(me))
341 return ES_FAILED;
342 if (me_modified(me) && (x1.min() != min))
343 es = ES_NOFIX;
344 }
345 return (x1.assigned() && (min == max)) ?
346 home.ES_SUBSUMED(*this) : es;
347 }
348
349
350
351
352
353 /*
354 * Domain consistent propagator
355 *
356 */
357
358 template<class VA, class VB, class VC>
361 IdxViewArray<VA>& iv, VB x0, VC x1)
362 : View<VA,VB,VC,PC_INT_DOM>(home,iv,x0,x1) {}
363
364 template<class VA, class VB, class VC>
367 IdxViewArray<VA>& iv, VB x0, VC x1){
368 GECODE_ME_CHECK(x0.gq(home,0));
369 GECODE_ME_CHECK(x0.le(home,iv.size()));
370 if (x0.assigned()) {
371 (void) new (home) Rel::EqDom<VA,VC>(home,iv[x0.val()].view,x1);
372 return ES_OK;
373 } else {
374 assert(iv.size()>1);
375 (void) new (home) ViewDom<VA,VB,VC>(home,iv,x0,x1);
376 }
377 return ES_OK;
378 }
379
380
381 template<class VA, class VB, class VC>
384 : View<VA,VB,VC,PC_INT_DOM>(home,p) {}
385
386 template<class VA, class VB, class VC>
387 Actor*
389 return new (home) ViewDom<VA,VB,VC>(home,*this);
390 }
391
392
393 template<class VA, class VB, class VC>
395 ViewDom<VA,VB,VC>::cost(const Space&, const ModEventDelta& med) const {
396 return PropCost::linear((VA::me(med) != ME_INT_DOM) ?
397 PropCost::LO : PropCost::HI, iv.size()+2);
398 }
399
400 template<class VA, class VB, class VC>
403 assert(iv.size() > 1);
404 if (VA::me(med) != ME_INT_DOM) {
407 (home,iv,x0,x1,*this,rt)));
408 if (iv.size() == 1) {
409 ExecStatus es = home.ES_SUBSUMED(*this);
410 (void) new (home) Rel::EqDom<VA,VC>(home(*this),iv[0].view,x1);
411 return es;
412 }
413 // Compute new result
414 int min = iv[0].view.min();
415 int max = iv[0].view.max();
416 for (int i=1; i<iv.size(); i++) {
417 min = std::min(iv[i].view.min(),min);
418 max = std::max(iv[i].view.max(),max);
419 }
420 GECODE_ME_CHECK(x1.lq(home,max));
421 GECODE_ME_CHECK(x1.gq(home,min));
422 return (x1.assigned() && (min == max)) ?
423 home.ES_SUBSUMED(*this) :
424 home.ES_NOFIX_PARTIAL(*this,VA::med(ME_INT_DOM));
425 }
428 (home,iv,x0,x1,*this,rt)));
429 if (iv.size() == 1) {
430 ExecStatus es = home.ES_SUBSUMED(*this);
431 (void) new (home) Rel::EqDom<VA,VC>(home(*this),iv[0].view,x1);
432 return es;
433 }
434 assert(iv.size() > 1);
435
436 if (x1.assigned()) {
437 for (int i=0; i<iv.size(); i++)
438 if (iv[i].view.in(x1.val()))
439 return shared(x0,x1) ? ES_NOFIX : ES_FIX;
440 return ES_FAILED;
441 } else {
442 Region r;
443 ViewRanges<VA>* i_view = r.alloc<ViewRanges<VA> >(iv.size());
444 for (int i=0; i<iv.size(); i++)
445 i_view[i].init(iv[i].view);
446 Iter::Ranges::NaryUnion i_val(r, i_view, iv.size());
447 ModEvent me = x1.inter_r(home,i_val);
448 r.free<ViewRanges<VA> >(i_view,iv.size());
449 GECODE_ME_CHECK(me);
450 return (shared(x0,x1) || me_modified(me)) ? ES_NOFIX : ES_FIX;
451 }
452 }
453
454}}}
455
456// STATISTICS: int-prop
457
struct Gecode::@603::NNF::@65::@66 b
For binary nodes (and, or, eqv)
int p
Number of positive literals for node type.
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:3252
Home class for posting propagators
Definition core.hpp:856
Constant integer view.
Definition view.hpp:851
Value iterator for indices in index-view map.
Definition view.hpp:164
void init(const IdxView< View > *, const IdxView< View > *)
Definition view.hpp:186
bool operator()(void) const
Definition view.hpp:192
Class for bounds-equality test.
Definition view.hpp:47
RelTest operator()(VA, VC)
Definition view.hpp:83
Class for domain-equality test.
Definition view.hpp:66
RelTest operator()(VA, VC)
Definition view.hpp:94
Bounds consistent element propagator for array of views.
Definition element.hh:232
ViewBnd(Space &home, ViewBnd &p)
Constructor for cloning p.
Definition view.hpp:301
virtual Actor * copy(Space &home)
Perform copying during cloning.
Definition view.hpp:306
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition view.hpp:312
static ExecStatus post(Home home, IdxViewArray< VA > &iv, VB x0, VC x1)
Post propagator for .
Definition view.hpp:284
Domain consistent element propagator for array of views.
Definition element.hh:262
virtual Actor * copy(Space &home)
Perform copying during cloning.
Definition view.hpp:388
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition view.hpp:402
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition view.hpp:395
static ExecStatus post(Home home, IdxViewArray< VA > &iv, VB x0, VC x1)
Post propagator for .
Definition view.hpp:366
ViewDom(Space &home, ViewDom &p)
Constructor for cloning p.
Definition view.hpp:383
Base-class for element propagator for array of views.
Definition element.hh:203
IdxViewArray< VA > iv
Current index-view map.
Definition element.hh:206
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition view.hpp:131
virtual void reschedule(Space &home)
Schedule function.
Definition view.hpp:140
View(Space &home, View &p)
Constructor for cloning p.
Definition view.hpp:122
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition view.hpp:148
VC x1
View for result.
Definition element.hh:210
VB x0
View for index.
Definition element.hh:208
An array of IdxView pairs.
Definition idx-view.hh:67
void subscribe(Space &home, Propagator &p, PropCond pc, bool process=true)
Definition idx-view.hpp:131
void update(Space &home, IdxViewArray< View > &x)
Cloning.
Definition idx-view.hpp:153
void cancel(Space &home, Propagator &p, PropCond pc)
Definition idx-view.hpp:139
int size(void) const
Return the current size.
Definition idx-view.hpp:105
Class for pair of index and view.
Definition idx-view.hh:48
int idx
The index.
Definition idx-view.hh:51
Binary bounds consistent equality propagator.
Definition rel.hh:134
Binary domain consistent equality propagator.
Definition rel.hh:68
Range iterator for integer views.
Definition view.hpp:54
Value iterator for integer views.
Definition view.hpp:94
Range iterator for union of iterators.
Propagation cost.
Definition core.hpp:486
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition core.hpp:4796
@ HI
Expensive.
Definition core.hpp:514
Base-class for propagators.
Definition core.hpp:1064
Handle to region.
Definition region.hpp:55
Computation spaces.
Definition core.hpp:1742
ExecStatus ES_NOFIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has not computed partial fixpoint
Definition core.hpp:3576
ExecStatus ES_SUBSUMED(Propagator &p)
Definition core.hpp:3563
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
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition modevent.hpp:54
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition macros.hpp:91
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition modevent.hpp:59
ExecStatus scan(Space &home, IdxViewArray< VA > &iv, VB x0, VC x1, Propagator &p, RelTest rt)
Definition view.hpp:217
RelTest rtest_eq_dom(VX x, VY y)
Test whether views x and y are equal (use full domain information)
Definition rel-test.hpp:65
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Definition var-type.hpp:91
RelTest rtest_eq_bnd(VX x, VY y)
Test whether views x and y are equal (use bounds information)
Definition rel-test.hpp:43
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition var-type.hpp:100
const Gecode::ModEvent ME_INT_DOM
Domain operation has changed the domain.
Definition var-type.hpp:72
RelTest
Result of testing relation.
Definition view.hpp:1734
@ RT_TRUE
Relation does hold.
Definition view.hpp:1737
@ RT_MAYBE
Relation may hold or not.
Definition view.hpp:1736
@ RT_FALSE
Relation does not hold.
Definition view.hpp:1735
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:767
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Post propagator for SetVar SetOpType SetVar y
Definition set.hh:767
ExecStatus
Definition core.hpp:472
@ ES_OK
Execution is okay.
Definition core.hpp:476
@ ES_FIX
Propagation has computed fixpoint.
Definition core.hpp:477
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:474
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition core.hpp:475
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
bool shared(ViewArray< ViewX > x, ViewArray< ViewY > y)
Definition array.hpp:1466
Post propagator for SetVar x
Definition set.hh:767
int ModEvent
Type for modification events.
Definition core.hpp:62
Gecode::IntArgs i({1, 2, 3, 4})
#define forceinline
Definition config.hpp:187
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56