Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
union.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,2006
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 ElementUnion(Home home, IdxViewArray& iv0, View0 y0, View1 y1)
42 : Propagator(home), iv(iv0), x0(y0), x1(y1) {
43 home.notice(*this,AP_DISPOSE);
44 x0.subscribe(home,*this, PC_SET_ANY);
45 x1.subscribe(home,*this, PC_SET_ANY);
46 iv.subscribe(home,*this, PC_SET_ANY);
47 }
48
49 template<class View, class View0, class View1>
53 : Propagator(home,p) {
54 x0.update(home,p.x0);
55 x1.update(home,p.x1);
56 iv.update(home,p.iv);
57 }
58
59 template<class View, class View0, class View1>
62 const ModEventDelta&) const {
63 return PropCost::linear(PropCost::HI, iv.size()+2);
64 }
65
66 template<class View, class View0, class View1>
67 void
69 x0.reschedule(home,*this, PC_SET_ANY);
70 x1.reschedule(home,*this, PC_SET_ANY);
71 iv.reschedule(home,*this, PC_SET_ANY);
72 }
73
74 template<class View, class View0, class View1>
75 forceinline size_t
77 home.ignore(*this,AP_DISPOSE);
78 if (!home.failed()) {
79 x0.cancel(home,*this,PC_SET_ANY);
80 x1.cancel(home,*this,PC_SET_ANY);
81 iv.cancel(home,*this,PC_SET_ANY);
82 }
83 (void) Propagator::dispose(home);
84 return sizeof(*this);
85 }
86
87 template<class View, class View0, class View1>
90 post(Home home, IdxViewArray& xs, View0 x0, View1 x1) {
91 int n = xs.size();
92
93 // x0 \subseteq {1,...,n}
95 GECODE_ME_CHECK(x0.intersectI(home,s));
96 (void) new (home)
97 ElementUnion<View,View0,View1>(home,xs,x0,x1);
98 return ES_OK;
99 }
100
101 template<class View, class View0, class View1>
102 Actor*
104 return new (home) ElementUnion<View,View0,View1>(home,*this);
105 }
106
107 template<class View, class View0, class View1>
110 Region r;
111 int n = iv.size();
112
113 bool loopVar;
114 do {
115 loopVar = false;
116
117 // Cache the upper bound iterator, as we have to
118 // modify the upper bound while iterating
119 LubRanges<View0> x0ub(x0);
120 Iter::Ranges::Cache x0ubc(r,x0ub);
122
123 GlbRanges<View0> x0lb(x0);
124 Iter::Ranges::Cache x0lbc(r,x0lb);
126
127 // In the first iteration, compute in before[i] the union
128 // of all the upper bounds of the x_i. At the same time,
129 // exclude inconsistent x_i from x0 and remove them from
130 // the list, cancel their dependencies.
131
132 GLBndSet sofarBefore(home);
133 LUBndSet selectedInter(home, IntSet (Limits::min,
134 Limits::max));
135 GLBndSet* before =
136 static_cast<GLBndSet*>(r.ralloc(sizeof(GLBndSet)*n));
137
138 int j = 0;
139 int i = 0;
140
141 unsigned int maxCard = 0;
142 unsigned int minCard = Limits::card;
143
144 while ( vx0ub() ) {
145
146 // Remove vars at indices not in the upper bound
147 if (iv[i].idx < vx0ub.val()) {
148 iv[i].view.cancel(home,*this, PC_SET_ANY);
149 ++i;
150 continue;
151 }
152 assert(iv[i].idx == vx0ub.val());
153 iv[j] = iv[i];
154
155 View candidate = iv[j].view;
156 int candidateInd = iv[j].idx;
157
158 // inter = glb(candidate) & complement(lub(x1))
159 GlbRanges<View> candlb(candidate);
160 LubRanges<View1> x1ub(x1);
162 diff(candlb, x1ub);
163
164 bool selectSingleInconsistent = false;
165 if (x0.cardMax() <= 1) {
166 GlbRanges<View1> x1lb(x1);
167 LubRanges<View> candub(candidate);
169 LubRanges<View> > diff2(x1lb, candub);
170 selectSingleInconsistent =
171 diff2() || candidate.cardMax() < x1.cardMin();
172 }
173
174 // exclude inconsistent x_i
175 // an x_i is inconsistent if
176 // * at most one x_i can be selected and there are
177 // elements in x_0 that can't be in x_i
178 // (selectSingleInconsistent)
179 // * its min cardinality is greater than maxCard of x1
180 // * inter is not empty (there are elements in x_i
181 // that can't be in x_0)
182 if (selectSingleInconsistent ||
183 candidate.cardMin() > x1.cardMax() ||
184 diff()) {
185 ModEvent me = (x0.exclude(home,candidateInd));
186 loopVar |= me_modified(me);
187 GECODE_ME_CHECK(me);
188
189 iv[j].view.cancel(home,*this, PC_SET_ANY);
190 ++i;
191 ++vx0ub;
192 continue;
193 } else {
194 // if x_i is consistent, check whether we know
195 // that its index is in x0
196 if (vx0() && vx0.val()==candidateInd) {
197 // x1 >= candidate, candidate <= x1
198 GlbRanges<View> candlb(candidate);
199 ModEvent me = x1.includeI(home,candlb);
200 loopVar |= me_modified(me);
201 GECODE_ME_CHECK(me);
202
203 LubRanges<View1> x1ub(x1);
204 me = candidate.intersectI(home,x1ub);
205 loopVar |= me_modified(me);
206 GECODE_ME_CHECK(me);
207 ++vx0;
208 }
209 new (&before[j]) GLBndSet(home);
210 before[j].update(home,sofarBefore);
211 LubRanges<View> cub(candidate);
212 sofarBefore.includeI(home,cub);
213 GlbRanges<View> clb(candidate);
214 selectedInter.intersectI(home,clb);
215 maxCard = std::max(maxCard, candidate.cardMax());
216 minCard = std::min(minCard, candidate.cardMin());
217 }
218
219 ++vx0ub;
220 ++i; ++j;
221 }
222
223 // cancel the variables with index greater than
224 // max of lub(x0)
225 for (int k=i; k<n; k++) {
226 iv[k].view.cancel(home,*this, PC_SET_ANY);
227 }
228 n = j;
229 iv.size(n);
230
231 if (x0.cardMax()==0) {
232 // Selector is empty, hence the result must be empty
233 {
234 GECODE_ME_CHECK(x1.cardMax(home,0));
235 }
236 for (int i=n; i--;)
237 before[i].dispose(home);
238 return home.ES_SUBSUMED(*this);
239 }
240
241 if (x0.cardMin() > 0) {
242 // Selector is not empty, hence the intersection of the
243 // possibly selected lower bounds is contained in x1
244 BndSetRanges si(selectedInter);
245 ModEvent me = x1.includeI(home, si);
246 loopVar |= me_modified(me);
247 GECODE_ME_CHECK(me);
248 me = x1.cardMin(home, minCard);
249 loopVar |= me_modified(me);
250 GECODE_ME_CHECK(me);
251 }
252 selectedInter.dispose(home);
253
254 if (x0.cardMax() <= 1) {
255 ModEvent me = x1.cardMax(home, maxCard);
256 loopVar |= me_modified(me);
257 GECODE_ME_CHECK(me);
258 }
259
260 {
261 // x1 <= sofarBefore
262 BndSetRanges sfB(sofarBefore);
263 ModEvent me = x1.intersectI(home,sfB);
264 loopVar |= me_modified(me);
265 GECODE_ME_CHECK(me);
266 }
267
268 sofarBefore.dispose(home);
269
270 GLBndSet sofarAfter(home);
271
272 // In the second iteration, this time backwards, compute
273 // sofarAfter as the union of all lub(x_j) with j>i
274 for (int i=n; i--;) {
275 // TODO: check for size of universe here?
276 // if (sofarAfter.size() == 0) break;
277
278 // extra = inter(before[i], sofarAfter) - lub(x1)
279 BndSetRanges b(before[i]);
280 BndSetRanges s(sofarAfter);
281 GlbRanges<View1> x1lb(x1);
285 if (diff()) {
286 ModEvent me = (x0.include(home,iv[i].idx));
287 loopVar |= me_modified(me);
288 GECODE_ME_CHECK(me);
289
290 // candidate != extra
291 me = iv[i].view.includeI(home,diff);
292 loopVar |= me_modified(me);
293 GECODE_ME_CHECK(me);
294 }
295
296 LubRanges<View> iviub(iv[i].view);
297 sofarAfter.includeI(home,iviub);
298 before[i].dispose(home);
299 }
300 sofarAfter.dispose(home);
301
302 } while (loopVar);
303
304 // Test whether we determined x0 without determining x1
305 if (x0.assigned() && !x1.assigned()) {
306 int ubsize = static_cast<int>(x0.lubSize());
307 if (ubsize > 2) {
308 assert(ubsize==n);
309 ViewArray<View> is(home,ubsize);
310 for (int i=n; i--;)
311 is[i]=iv[i].view;
313 ::post(home(*this),is,x1)));
314 } else if (ubsize == 2) {
315 assert(n==2);
316 View a = iv[0].view;
317 View b = iv[1].view;
319 ::post(home(*this),a,b,x1)));
320 } else if (ubsize == 1) {
321 assert(n==1);
322 GECODE_REWRITE(*this,
323 (Rel::Eq<View1,View>::post(home(*this),x1,iv[0].view)));
324 } else {
325 GECODE_ME_CHECK(x1.cardMax(home, 0));
326 return home.ES_SUBSUMED(*this);
327 }
328 }
329
330 for (int i=iv.size(); i--;)
331 if (!iv[i].view.assigned())
332 return ES_FIX;
333 if (!x1.assigned() || !x0.assigned())
334 return ES_FIX;
335 return home.ES_SUBSUMED(*this);
336 }
337
338}}}
339
340// STATISTICS: set-prop
struct Gecode::@603::NNF::@65::@66 b
For binary nodes (and, or, eqv)
int p
Number of positive literals for node type.
int n
Number of negative literals for node type.
struct Gecode::@603::NNF::@65::@67 a
For atomic nodes.
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
int size(void) const
Return size of array (number of elements)
Definition array.hpp:1607
Home class for posting propagators
Definition core.hpp:856
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition core.hpp:3219
Integer sets.
Definition int.hh:174
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
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 singleton range.
Value iterator from range iterator.
int val(void) const
Return current value.
Range iterator for computing union (binary)
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
Range iterator for integer sets.
Definition var-imp.hpp:185
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 union
Definition element.hh:119
virtual void reschedule(Space &home)
Schedule function.
Definition union.hpp:68
Growing sets of integers.
Definition var-imp.hpp:205
bool includeI(Space &home, I &i)
Include the set represented by i in this set.
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 union
Definition rel-op.hh:219
Propagator for ternary union
Definition rel-op.hh:154
Propagator for set equality
Definition rel.hh:150
Computation spaces.
Definition core.hpp:1742
View arrays.
Definition array.hpp:253
ExecStatus ES_SUBSUMED(Propagator &p)
Definition core.hpp:3563
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition core.hpp:4074
int ModEventDelta
Modification event deltas.
Definition core.hpp:89
bool failed(void) const
Check whether space is failed.
Definition core.hpp:4044
#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
const int min
Smallest allowed integer value.
Definition int.hh:118
const int max
Largest allowed integer value.
Definition int.hh:116
const unsigned int card
Maximum cardinality of an integer set.
Definition set.hh:101
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:767
SetExpr inter(const SetVarArgs &)
Intersection of set variables.
Definition set-expr.cpp:696
TFE post(PropagatorGroup g)
Only post functions (but not propagators) from g are considered.
Definition filter.cpp:138
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:187