Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
disjoint.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 SView, class RView>
41 IdxViewArray& iv0,
42 RView y1)
43 : Propagator(home), iv(iv0), x1(y1) {
44
45 x1.subscribe(home,*this, PC_SET_ANY);
46 iv.subscribe(home,*this, PC_SET_ANY);
47 }
48
49 template<class SView, class RView>
53 : Propagator(home,p) {
54 x1.update(home,p.x1);
55 iv.update(home,p.iv);
56 }
57
58 template<class SView, class RView>
61 RView x1) {
62 int n = xs.size();
63
64 // s2 \subseteq {0,...,n-1}
66 GECODE_ME_CHECK(x1.intersectI(home,s));
67 (void) new (home)
68 ElementDisjoint(home,xs,x1);
69 return ES_OK;
70 }
71
72 template<class SView, class RView>
75 return PropCost::quadratic(PropCost::LO, iv.size()+2);
76 }
77
78 template<class SView, class RView>
79 void
81 x1.reschedule(home,*this, PC_SET_ANY);
82 iv.reschedule(home,*this, PC_SET_ANY);
83 }
84
85 template<class SView, class RView>
86 forceinline size_t
88 x1.cancel(home,*this, PC_SET_ANY);
89 iv.cancel(home,*this,PC_SET_ANY);
90 (void) Propagator::dispose(home);
91 return sizeof(*this);
92 }
93
94 template<class SView, class RView>
95 Actor*
97 return new (home) ElementDisjoint(home,*this);
98 }
99
100 template<class SView, class RView>
103 int n = iv.size();
104
105 Region r;
106
107 bool fix_flag = false;
108 do {
109 fix_flag = false;
110 // Compute union of all selected elements' lower bounds
111 GlbRanges<RView> x1lb(x1);
113 GLBndSet unionOfSelected(home);
114 for(int i=0; vx1lb(); ++vx1lb) {
115 while (iv[i].idx < vx1lb.val()) i++;
116 GlbRanges<SView> clb(iv[i].view);
117 unionOfSelected.includeI(home,clb);
118 }
119
120 {
121 LubRanges<RView> x1ub(x1);
123 int i=0;
124 int j=0;
125 // Cancel all elements that are no longer in the upper bound
126 while (vx1ub()) {
127 if (iv[i].idx < vx1ub.val()) {
128 iv[i].view.cancel(home,*this, PC_SET_ANY);
129 i++;
130 continue;
131 }
132 iv[j] = iv[i];
133 ++vx1ub;
134 ++i; ++j;
135 }
136
137 // cancel the variables with index greater than
138 // max of lub(x1)
139 for (int k=i; k<n; k++) {
140 iv[k].view.cancel(home,*this, PC_SET_ANY);
141 }
142 n = j;
143 iv.size(n);
144 }
145
146 {
147 UnknownRanges<RView> x1u(x1);
148 Iter::Ranges::Cache x1uc(r,x1u);
150 vx1u(x1uc);
151 int i=0;
152 int j=0;
153 while (vx1u()) {
154 while (iv[i].idx < vx1u.val()) {
155 iv[j] = iv[i];
156 i++; j++;
157 }
158 assert(iv[i].idx == vx1u.val());
159
160 SView candidate = iv[i].view;
161 int candidateInd = iv[i].idx;
162
163 GlbRanges<SView> clb(candidate);
164 BndSetRanges uos(unionOfSelected);
166 inter(clb, uos);
167 if (inter()) {
168 ModEvent me = x1.exclude(home,candidateInd);
169 fix_flag |= me_modified(me);
170 GECODE_ME_CHECK(me);
171
172 candidate.cancel(home,*this, PC_SET_ANY);
173 ++i;
174 ++vx1u;
175 continue;
176 }
177 iv[j] = iv[i];
178 ++vx1u;
179 ++i; ++j;
180 }
181
182 unionOfSelected.dispose(home);
183
184 // copy remaining variables
185 for (int k=i; k<n; k++) {
186 iv[j] = iv[k];
187 j++;
188 }
189 n = j;
190 iv.size(n);
191 }
192
193 if (x1.cardMax()==0) {
194 // Selector is empty, we're done
195 return home.ES_SUBSUMED(*this);
196 }
197
198 {
199 // remove all elements in a selected variable from
200 // all other selected variables
201 GlbRanges<RView> x1lb(x1);
203 int i=0;
204 for (; vx1lb(); ++vx1lb) {
205 while (iv[i].idx < vx1lb.val()) i++;
206 assert(iv[i].idx==vx1lb.val());
207 GlbRanges<RView> x1lb2(x1);
209 for (int j=0; vx1lb2(); ++vx1lb2) {
210 while (iv[j].idx < vx1lb2.val()) j++;
211 assert(iv[j].idx==vx1lb2.val());
212 if (iv[i].idx!=iv[j].idx) {
213 GlbRanges<SView> xilb(iv[i].view);
214 ModEvent me = iv[j].view.excludeI(home,xilb);
215 fix_flag |= me_modified(me);
216 GECODE_ME_CHECK(me);
217 }
218 }
219 }
220 }
221
222 // remove all elements from the selector that overlap
223 // with all other possibly selected elements, if
224 // at least two more elements need to be selected
225 if (x1.cardMin()-x1.glbSize() > 1) {
226 UnknownRanges<RView> x1u(x1);
227 Iter::Ranges::Cache x1uc(r,x1u);
229 vx1u(x1uc);
230
231 for (; vx1u() && x1.cardMin()-x1.glbSize() > 1; ++vx1u) {
232 int i = 0;
233 while (iv[i].idx < vx1u.val()) i++;
234 assert(iv[i].idx == vx1u.val());
235 bool flag=true;
236
237 UnknownRanges<RView> x1u2(x1);
239 for (; vx1u2(); ++vx1u2) {
240 int j = 0;
241 while (iv[j].idx < vx1u2.val()) j++;
242 assert(iv[j].idx == vx1u2.val());
243 if (iv[i].idx!=iv[j].idx) {
244 GlbRanges<SView> xjlb(iv[j].view);
245 GlbRanges<SView> xilb(iv[i].view);
247 inter(xjlb, xilb);
248 if (!inter()) {
249 flag = false;
250 goto here;
251 }
252 }
253 }
254 here:
255 if (flag) {
256 ModEvent me = x1.exclude(home,iv[i].idx);
257 fix_flag |= me_modified(me);
258 GECODE_ME_CHECK(me);
259 }
260 }
261 }
262
263 // if exactly two more elements need to be selected
264 // and there is a possible element i such that all other pairs of
265 // elements overlap, select i
266 UnknownRanges<RView> x1u(x1);
267 Iter::Ranges::Cache x1uc(r,x1u);
269 vx1u(x1uc);
270
271 for (; x1.cardMin()-x1.glbSize() == 2 && vx1u(); ++vx1u) {
272 int i = 0;
273 while (iv[i].idx < vx1u.val()) i++;
274 assert (iv[i].idx == vx1u.val());
275 bool flag=true;
276
277 UnknownRanges<RView> x1u2(x1);
279 for (; vx1u2(); ++vx1u2) {
280 int j = 0;
281 while (iv[j].idx < vx1u2.val()) j++;
282 assert (iv[j].idx == vx1u2.val());
283 if (iv[i].idx!=iv[j].idx) {
284 UnknownRanges<RView> x1u3(x1);
286 for (; vx1u3(); ++vx1u3) {
287 int k = 0;
288 while (iv[k].idx < vx1u3.val()) k++;
289 assert (iv[k].idx == vx1u3.val());
290 if (iv[j].idx!=iv[k].idx && iv[i].idx!=iv[k].idx) {
291 GlbRanges<SView> xjlb(iv[j].view);
292 GlbRanges<SView> xilb(iv[k].view);
294 inter(xjlb, xilb);
295 if (!inter()) {
296 flag = false;
297 goto here2;
298 }
299 }
300 }
301 }
302 }
303 here2:
304 if (flag) {
305 ModEvent me = x1.include(home,iv[i].idx);
306 fix_flag |= me_modified(me);
307 GECODE_ME_CHECK(me);
308 }
309 }
310 } while (fix_flag);
311
312 for (int i=iv.size(); i--;)
313 if (!iv[i].view.assigned())
314 return ES_FIX;
315 if (!x1.assigned())
316 return ES_FIX;
317 return home.ES_SUBSUMED(*this);
318 }
319
320
321}}}
322
323// STATISTICS: set-prop
int p
Number of positive literals for node type.
int n
Number of negative 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
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 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 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 quadratic(PropCost::Mod m, unsigned int n)
Quadratic complexity for modifier m and size measure n.
Definition core.hpp:4787
Base-class for propagators.
Definition core.hpp:1064
size_t size
The size of the propagator (used during subsumption)
Definition core.hpp:1077
Handle to region.
Definition region.hpp:55
Range iterator for integer sets.
Definition var-imp.hpp:185
void dispose(Space &home)
Free memory used by this set.
Propagator for element with disjointness
Definition element.hh:194
virtual void reschedule(Space &home)
Schedule function.
Definition disjoint.hpp:80
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
Range iterator for the least upper bound.
Definition var-imp.hpp:317
Range iterator for the unknown set.
Definition var-imp.hpp:402
Computation spaces.
Definition core.hpp:1742
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_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition modevent.hpp:59
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
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