Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
unionConst.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,2007
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 SView, class RView>
41 ElementUnionConst(Home home, SView y0,
42 const IntSetArgs& iv0,
43 RView y1)
44 : Propagator(home), x0(y0), n_iv(iv0.size()), x1(y1) {
45 home.notice(*this,AP_DISPOSE);
46 x0.subscribe(home,*this, PC_SET_ANY);
47 x1.subscribe(home,*this, PC_SET_ANY);
48 iv=static_cast<Space&>(home).alloc<IntSet>(n_iv);
49 for (unsigned int i=iv0.size(); i--;)
50 iv[i]=iv0[i];
51 }
52
53 template<class SView, class RView>
57 : Propagator(home,p), n_iv(p.n_iv) {
58 x0.update(home,p.x0);
59 x1.update(home,p.x1);
60 iv=home.alloc<IntSet>(n_iv);
61 for (unsigned int i=n_iv; i--;)
62 iv[i]=p.iv[i];
63 }
64
65 template<class SView, class RView>
70
71 template<class SView, class RView>
72 void
74 x0.reschedule(home,*this, PC_SET_ANY);
75 x1.reschedule(home,*this, PC_SET_ANY);
76 }
77
78 template<class SView, class RView>
79 forceinline size_t
81 home.ignore(*this,AP_DISPOSE);
82 if (!home.failed()) {
83 x0.cancel(home,*this, PC_SET_ANY);
84 x1.cancel(home,*this, PC_SET_ANY);
85 }
86 for (unsigned int i=n_iv; i--;)
87 iv[i].~IntSet();
88 (void) Propagator::dispose(home);
89 return sizeof(*this);
90 }
91
92 template<class SView, class RView>
95 post(Home home, SView x0, const IntSetArgs& xs,
96 RView x1) {
97 int n = xs.size();
98
99 // s2 \subseteq {1,...,n}
100 Iter::Ranges::Singleton s(0, n-1);
101 GECODE_ME_CHECK(x1.intersectI(home,s));
102 (void) new (home)
104 return ES_OK;
105 }
106
107 template<class SView, class RView>
108 Actor*
110 return new (home) ElementUnionConst<SView,RView>(home,*this);
111 }
112
113 template<class SView, class RView>
116 Region r;
117
118 bool* stillSelected = r.alloc<bool>(n_iv);
119
120 bool loopVar;
121 do {
122 loopVar = false;
123 for (int i=n_iv; i--;)
124 stillSelected[i] = false;
125
126 // Cache the upper bound iterator, as we have to
127 // modify the upper bound while iterating
128 LubRanges<RView> x1ub(x1);
129 Iter::Ranges::Cache x1ubc(r,x1ub);
131 vx1ub(x1ubc);
132
133 GlbRanges<RView> x1lb(x1);
134 Iter::Ranges::Cache x1lbc(r,x1lb);
136 vx1(x1lbc);
137
138 // In the first iteration, compute in before[i] the union
139 // of all the upper bounds of the x_i. At the same time,
140 // exclude inconsistent x_i from x1.
141
142 GLBndSet sofarBefore(home);
143 LUBndSet selectedInter(home, IntSet (Limits::min,
144 Limits::max));
145 GLBndSet* before =
146 static_cast<GLBndSet*>(r.ralloc(sizeof(GLBndSet)*n_iv));
147
148 unsigned int maxCard = 0;
149 unsigned int minCard = Limits::card;
150
151 while (vx1ub()) {
152 int i = vx1ub.val();
153
154 IntSetRanges candCardR(iv[i]);
155 unsigned int candidateCard = Iter::Ranges::size(candCardR);
156
157 IntSetRanges candlb(iv[i]);
158 LubRanges<SView> x0ub(x0);
160 LubRanges<SView> > diff(candlb, x0ub);
161
162 bool selectSingleInconsistent = false;
163 if (x1.cardMax() <= 1) {
164 GlbRanges<SView> x0lb(x0);
165 IntSetRanges candub(iv[i]);
167 IntSetRanges > diff2(x0lb, candub);
168 selectSingleInconsistent = diff2() || candidateCard < x0.cardMin();
169 }
170
171 // exclude inconsistent x_i
172 // an x_i is inconsistent if
173 // * at most one x_i can be selected and there are
174 // elements in x_0 that can't be in x_i
175 // (selectSingleInconsistent)
176 // * its min cardinality is greater than maxCard of x0
177 // * inter is not empty (there are elements in x_i
178 // that can't be in x_0)
179 if (selectSingleInconsistent ||
180 candidateCard > x0.cardMax() ||
181 diff()) {
182 ModEvent me = (x1.exclude(home,i));
183 loopVar |= me_modified(me);
184 GECODE_ME_CHECK(me);
185 } else {
186 stillSelected[i] = true;
187 // if x_i is consistent, check whether we know
188 // that its index is in x1
189 if (vx1() && vx1.val()==i) {
190 // x0 >= candidate, candidate <= x0
191 // GlbRanges<SView> candlb(candidate);
192 IntSetRanges candlb(iv[i]);
193 ModEvent me = x0.includeI(home,candlb);
194 loopVar |= me_modified(me);
195 GECODE_ME_CHECK(me);
196 ++vx1;
197 }
198 new (&before[i]) GLBndSet(home);
199 before[i].update(home,sofarBefore);
200 IntSetRanges cub(iv[i]);
201 sofarBefore.includeI(home,cub);
202 IntSetRanges clb(iv[i]);
203 selectedInter.intersectI(home,clb);
204 maxCard = std::max(maxCard, candidateCard);
205 minCard = std::min(minCard, candidateCard);
206 }
207
208 ++vx1ub;
209 }
210
211 if (x1.cardMax()==0) {
212 // Selector is empty, hence the result must be empty
213 {
214 GECODE_ME_CHECK(x0.cardMax(home,0));
215 }
216 for (int i=n_iv; i--;)
217 if (stillSelected[i])
218 before[i].dispose(home);
219 selectedInter.dispose(home);
220 sofarBefore.dispose(home);
221 return home.ES_SUBSUMED(*this);
222 }
223
224 if (x1.cardMin() > 0) {
225 // Selector is not empty, hence the intersection of the
226 // possibly selected lower bounds is contained in x0
227 BndSetRanges si(selectedInter);
228 ModEvent me = x0.includeI(home, si);
229 loopVar |= me_modified(me);
230 GECODE_ME_CHECK(me);
231 me = x0.cardMin(home, minCard);
232 loopVar |= me_modified(me);
233 GECODE_ME_CHECK(me);
234 }
235 selectedInter.dispose(home);
236
237 if (x1.cardMax() <= 1) {
238 ModEvent me = x0.cardMax(home, maxCard);
239 loopVar |= me_modified(me);
240 GECODE_ME_CHECK(me);
241 }
242
243 {
244 // x0 <= sofarBefore
245 BndSetRanges sfB(sofarBefore);
246 ModEvent me = x0.intersectI(home,sfB);
247 loopVar |= me_modified(me);
248 GECODE_ME_CHECK(me);
249 }
250
251 sofarBefore.dispose(home);
252
253 GLBndSet sofarAfter(home);
254
255 // In the second iteration, this time backwards, compute
256 // sofarAfter as the union of all lub(x_j) with j>i
257 for (int i=n_iv; i--;) {
258 if (!stillSelected[i])
259 continue;
260 BndSetRanges b(before[i]);
261 BndSetRanges s(sofarAfter);
262 GlbRanges<SView> x0lb(x0);
266 if (diff()) {
267 ModEvent me = (x1.include(home,i));
268 loopVar |= me_modified(me);
269 GECODE_ME_CHECK(me);
270
271 // candidate != extra
272 IntSetRanges ivi(iv[i]);
273 if (!Iter::Ranges::subset(diff, ivi))
275 }
276
277 IntSetRanges iviub(iv[i]);
278 sofarAfter.includeI(home,iviub);
279 before[i].dispose(home);
280 }
281 sofarAfter.dispose(home);
282
283 } while (loopVar);
284
285 if (x1.assigned()) {
286 assert(x0.assigned());
287 return home.ES_SUBSUMED(*this);
288 }
289
290 return ES_FIX;
291 }
292
293}}}
294
295// 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
int size(void) const
Return size of array (number of elements)
Definition array.hpp:1613
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
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:4803
@ HI
Expensive.
Definition core.hpp:514
size_t size
The size of the propagator (used during subsumption)
Definition core.hpp:1079
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
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.
ElementUnionConst(Space &home, ElementUnionConst &p)
Constructor for cloning p.
virtual void reschedule(Space &home)
Schedule function.
virtual size_t dispose(Space &home)
Delete propagator and return its size.
virtual Actor * copy(Space &home)
Copy propagator during cloning.
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
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
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition core.hpp:2841
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
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
bool subset(I &i, J &j)
Check whether range iterator i is subset of range iterator j.
unsigned int size(I &i)
Size of all ranges of range iterator i.
Set element propagators
Definition element.hh:64
const int min
Smallest allowed integer in integer set.
Definition set.hh:99
const unsigned int card
Maximum cardinality of an integer set.
Definition set.hh:101
const int max
Largest allowed integer in integer set.
Definition set.hh:97
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
const Gecode::ModEvent ME_SET_FAILED
Domain operation has resulted in failure.
Definition var-type.hpp:138
Gecode toplevel namespace
ArgArray< IntSet > IntSetArgs
Passing set arguments.
Definition int.hh:625
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