Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
inter.hpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Guido Tack <tack@gecode.org>
5 * Christian Schulte <schulte@gecode.org>
6 *
7 * Copyright:
8 * Guido Tack, 2004
9 * Christian Schulte, 2004
10 *
11 * This file is part of Gecode, the generic constraint
12 * development environment:
13 * http://www.gecode.org
14 *
15 * Permission is hereby granted, free of charge, to any person obtaining
16 * a copy of this software and associated documentation files (the
17 * "Software"), to deal in the Software without restriction, including
18 * without limitation the rights to use, copy, modify, merge, publish,
19 * distribute, sublicense, and/or sell copies of the Software, and to
20 * permit persons to whom the Software is furnished to do so, subject to
21 * the following conditions:
22 *
23 * The above copyright notice and this permission notice shall be
24 * included in all copies or substantial portions of the Software.
25 *
26 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
27 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
28 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
29 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
30 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
31 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
32 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
33 *
34 */
35
36namespace Gecode { namespace Set { namespace Element {
37
38 template<class View, class View0, class View1>
41 ElementIntersection(Home home, IdxViewArray& iv0, View0 y0, View1 y1,
42 const IntSet& theUniverse)
43 : Propagator(home), universe(theUniverse), iv(iv0), x0(y0), x1(y1) {
44 home.notice(*this,AP_DISPOSE);
45 x0.subscribe(home,*this, PC_SET_ANY);
46 x1.subscribe(home,*this, PC_SET_ANY);
47 iv.subscribe(home,*this, PC_SET_ANY);
48 }
49
50 template<class View, class View0, class View1>
54 : Propagator(home,p), universe(p.universe) {
55 x0.update(home,p.x0);
56 x1.update(home,p.x1);
57 iv.update(home,p.iv);
58 }
59
60 template<class View, class View0, class View1>
66
67 template<class View, class View0, class View1>
68 void
70 x0.reschedule(home,*this, PC_SET_ANY);
71 x1.reschedule(home,*this, PC_SET_ANY);
72 iv.reschedule(home,*this, PC_SET_ANY);
73 }
74
75 template<class View, class View0, class View1>
76 forceinline size_t
78 home.ignore(*this,AP_DISPOSE);
79 if (!home.failed()) {
80 x0.cancel(home,*this, PC_SET_ANY);
81 x1.cancel(home,*this, PC_SET_ANY);
82 iv.cancel(home,*this,PC_SET_ANY);
83 }
84 universe.~IntSet();
85 (void) Propagator::dispose(home);
86 return sizeof(*this);
87 }
88
89 template<class View, class View0, class View1>
92 post(Home home, IdxViewArray& xs, View0 x0, View1 x1,
93 const IntSet& universe) {
94 int n = xs.size();
95
96 // x0 \subseteq {1,...,n}
98 GECODE_ME_CHECK(x0.intersectI(home,s));
99 (void) new (home)
101 return ES_OK;
102 }
103
104 template<class View, class View0, class View1>
105 Actor*
109
110 template<class View, class View0, class View1>
113 const ModEventDelta&) {
114 Region r;
115 int n = iv.size();
116
117 bool loopVar;
118 do {
119 loopVar = false;
120
121 // Cache the upper bound iterator, as we have to
122 // modify the upper bound while iterating
123 LubRanges<View0> x0ub(x0);
124 Iter::Ranges::Cache x0ubc(r,x0ub);
126
127 GlbRanges<View0> x0lb(x0);
128 Iter::Ranges::Cache x0lbc(r,x0lb);
130
131 // In the first iteration, compute in before[i] the intersection
132 // of all the lower bounds of the x_i. At the same time,
133 // exclude inconsistent x_i from x0 and remove them from
134 // the list, cancel their dependencies.
135
136 LUBndSet sofarBefore(home,universe);
137 LUBndSet* before = r.alloc<LUBndSet>(n);
138
139 int j = 0;
140 int i = 0;
141 while ( vx0ub() ) {
142
143 // Remove vars at indices not in the upper bound
144 if (iv[i].idx < vx0ub.val()) {
145 iv[i].view.cancel(home,*this, PC_SET_ANY);
146 ++i;
147 continue;
148 }
149 assert(iv[i].idx == vx0ub.val());
150 iv[j] = iv[i];
151
152 View candidate = iv[j].view;
153 int candidateInd = iv[j].idx;
154
155 // inter = glb(x1) & complement(lub(candidate))
156 GlbRanges<View1> x1lb(x1);
157 LubRanges<View> candub(candidate);
159 inter(x1lb, candub);
160
161 // exclude inconsistent x_i
162 // an x_i is inconsistent if
163 // * its max cardinality is less than minCard of x1
164 // * inter is not empty (there are elements in x_0
165 // that can't be in x_i)
166 if (candidate.cardMax() < x1.cardMin() ||
167 inter()) {
168 ModEvent me = (x0.exclude(home,candidateInd));
169 loopVar |= me_modified(me);
170 GECODE_ME_CHECK(me);
171
172 iv[j].view.cancel(home,*this, PC_SET_ANY);
173 ++i;
174 ++vx0ub;
175 continue;
176 } else {
177 // if x_i is consistent, check whether we know
178 // that its index is in x0
179 if (vx0() && vx0.val()==candidateInd) {
180 // x1 <= candidate, candidate >= x1
181 GlbRanges<View1> x1lb(x1);
182 ModEvent me = candidate.includeI(home,x1lb);
183 loopVar |= me_modified(me);
184 GECODE_ME_CHECK(me);
185
186 LubRanges<View> candub(candidate);
187 me = x1.intersectI(home,candub);
188 loopVar |= me_modified(me);
189 GECODE_ME_CHECK(me);
190 ++vx0;
191 }
192 new (&before[j]) LUBndSet(home);
193 before[j].update(home,sofarBefore);
194 GlbRanges<View> clb(candidate);
195 sofarBefore.intersectI(home,clb);
196 }
197
198 ++vx0ub;
199 ++i; ++j;
200 }
201
202 // cancel the variables with index greater than
203 // max of lub(x0)
204 for (int k=i; k<n; k++) {
205 iv[k].view.cancel(home,*this, PC_SET_ANY);
206 }
207 n = j;
208 iv.size(n);
209
210 if (x0.cardMax()==0) {
211 // Elementor is empty, hence the result must be universe
212 {
214 GECODE_ME_CHECK(x1.includeI(home,uniI));
215 }
216 {
218 GECODE_ME_CHECK(x1.intersectI(home,uniI));
219 }
220 for (int i=n; i--;)
221 before[i].dispose(home);
222 return home.ES_SUBSUMED(*this);
223 }
224
225 {
226 // x1 >= sofarBefore
227 BndSetRanges sfB(sofarBefore);
228 ModEvent me = x1.includeI(home,sfB);
229 loopVar |= me_modified(me);
230 GECODE_ME_CHECK(me);
231 }
232
233 sofarBefore.dispose(home);
234
235 LUBndSet sofarAfter(home, universe);
236
237 // In the second iteration, this time backwards, compute
238 // sofarAfter as the intersection of all glb(x_j) with j>i
239 for (int i=n; i--;) {
240 if (sofarAfter.size() == 0) break;
241
242 // extra = inter(before[i], sofarAfter) - lub(x1)
243 BndSetRanges b(before[i]);
244 BndSetRanges s(sofarAfter);
245 LubRanges<View1> x1ub(x1);
248 BndSetRanges>, LubRanges<View1> > diff(inter, x1ub);
249 if (diff()) {
250 ModEvent me = (x0.include(home,iv[i].idx));
251 loopVar |= me_modified(me);
252 GECODE_ME_CHECK(me);
253
254 // candidate != extra
255 me = iv[i].view.excludeI(home,diff);
256 loopVar |= me_modified(me);
257 GECODE_ME_CHECK(me);
258 }
259
260 GlbRanges<View> ivilb(iv[i].view);
261 sofarAfter.intersectI(home,ivilb);
262 before[i].dispose(home);
263 }
264 sofarAfter.dispose(home);
265
266 } while (loopVar);
267
268 // Test whether we determined x0 without determining x1
269 if (x0.assigned() && !x1.assigned()) {
270 int ubsize = static_cast<int>(x0.lubSize());
271 if (ubsize > 2) {
272 assert(ubsize==n);
273 ViewArray<View> is(home,ubsize);
274 for (int i=n; i--;)
275 is[i]=iv[i].view;
277 ::post(home(*this),is,x1)));
278 } else if (ubsize == 2) {
279 assert(n==2);
280 View a = iv[0].view;
281 View b = iv[1].view;
283 ::post(home(*this),a,b,x1)));
284 } else if (ubsize == 1) {
285 assert(n==1);
286 GECODE_REWRITE(*this,
287 (Rel::Eq<View1,View>::post(home(*this),x1,iv[0].view)));
288 } else {
289 GECODE_ME_CHECK(x1.cardMax(home, 0));
290 return home.ES_SUBSUMED(*this);
291 }
292 }
293
294 bool allAssigned = true;
295 for (int i=iv.size(); i--;) {
296 if (!iv[i].view.assigned()) {
297 allAssigned = false;
298 break;
299 }
300 }
301 if (x1.assigned() && x0.assigned() && allAssigned) {
302 return home.ES_SUBSUMED(*this);
303 }
304
305 return ES_FIX;
306 }
307
308}}}
309
310// STATISTICS: set-prop
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
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition core.hpp:3223
Range iterator for integer sets.
Definition int.hh:292
Integer sets.
Definition int.hh:174
void update(Space &home, IdxViewArray< View > &x)
Cloning.
Definition idx-view.hpp:153
int size(void) const
Return the current size.
Definition idx-view.hpp:105
Range iterator cache
Range iterator for computing set difference.
Range iterator for computing intersection (binary)
Range iterator for singleton range.
Value iterator from range iterator.
int val(void) const
Return current value.
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:4803
@ HI
Expensive.
Definition core.hpp:514
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
Handle to region.
Definition region.hpp:55
Range iterator for integer sets.
Definition var-imp.hpp:185
unsigned int size(void) const
Return size.
void update(Space &home, BndSet &x)
Update this set to be a clone of set x.
void dispose(Space &home)
Free memory used by this set.
Propagator for element with intersection
Definition element.hh:78
ElementIntersection(Space &home, ElementIntersection &p)
Constructor for cloning p.
Gecode::Int::IdxViewArray< View > IdxViewArray
Definition element.hh:80
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition inter.hpp:106
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition inter.hpp:77
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition inter.hpp:62
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition inter.hpp:112
virtual void reschedule(Space &home)
Schedule function.
Definition inter.hpp:69
static ExecStatus post(Home home, IdxViewArray &x, View0 y, View1 z, const IntSet &u)
Definition inter.hpp:92
Range iterator for the greatest lower bound.
Definition var-imp.hpp:359
Shrinking sets of integers.
Definition var-imp.hpp:243
bool intersectI(Space &home, I &i)
Exclude all elements not in the set represented by i from this set.
Range iterator for the least upper bound.
Definition var-imp.hpp:317
Propagator for nary intersection
Definition rel-op.hh:183
Propagator for ternary intersection
Definition rel-op.hh:124
static ExecStatus post(Home home, View0 x, View1 y)
Post propagator .
Definition eq.hpp:54
Computation spaces.
Definition core.hpp:1744
View arrays.
Definition array.hpp:253
ExecStatus ES_SUBSUMED(Propagator &p)
Propagator p is subsumed
Definition core.hpp:3570
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition core.hpp:4081
int ModEventDelta
Modification event deltas.
Definition core.hpp:89
bool failed(void) const
Check whether space is failed.
Definition core.hpp:4051
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition macros.hpp:52
#define GECODE_REWRITE(prop, post)
Rewrite propagator by executing post function.
Definition macros.hpp:116
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition modevent.hpp:59
@ AP_DISPOSE
Actor must always be disposed.
Definition core.hpp:562
Set element propagators
Definition element.hh:64
Finite integer sets.
Definition var-imp.hpp:137
const Gecode::PropCond PC_SET_ANY
Propagate when any bound or the cardinality of a view changes.
Definition var-type.hpp:248
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:773
SetExpr inter(const SetVarArgs &)
Intersection of set variables.
Definition set-expr.cpp:696
ExecStatus
Definition core.hpp:472
@ ES_OK
Execution is okay.
Definition core.hpp:476
@ ES_FIX
Propagation has computed fixpoint.
Definition core.hpp:477
int ModEvent
Type for modification events.
Definition core.hpp:62
#define forceinline
Definition config.hpp:194