Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
set.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 * Gabor Szokoli <szokoli@gecode.org>
6 *
7 * Contributing authors:
8 * Christian Schulte <schulte@gecode.org>
9 *
10 * Copyright:
11 * Guido Tack, 2004
12 * Christian Schulte, 2004
13 * Gabor Szokoli, 2004
14 *
15 * This file is part of Gecode, the generic constraint
16 * development environment:
17 * http://www.gecode.org
18 *
19 * Permission is hereby granted, free of charge, to any person obtaining
20 * a copy of this software and associated documentation files (the
21 * "Software"), to deal in the Software without restriction, including
22 * without limitation the rights to use, copy, modify, merge, publish,
23 * distribute, sublicense, and/or sell copies of the Software, and to
24 * permit persons to whom the Software is furnished to do so, subject to
25 * the following conditions:
26 *
27 * The above copyright notice and this permission notice shall be
28 * included in all copies or substantial portions of the Software.
29 *
30 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37 *
38 */
39
40namespace Gecode { namespace Set {
41
42 /*
43 * Creation of new variable implementations
44 *
45 */
46
49 : SetVarImpBase(home), lub(home), glb(home) {
50 lub.card(Limits::card);
51 assert(lub.card()==lub.size());
52 }
53
55 SetVarImp::SetVarImp(Space& home,int lbMin,int lbMax,int ubMin,int ubMax,
56 unsigned int cardMin, unsigned int cardMax)
57 : SetVarImpBase(home),
58 lub(home,ubMin,ubMax), glb(home,lbMin,lbMax) {
59 glb.card(std::max(cardMin, glb.size() ));
60 lub.card(std::min(cardMax, lub.size() ));
61 }
62
65 const IntSet& theGlb,int ubMin,int ubMax,
66 unsigned int cardMin, unsigned int cardMax)
67 : SetVarImpBase(home),
68 lub(home,ubMin,ubMax), glb(home,theGlb) {
69 glb.card(std::max(cardMin, glb.size() ));
70 lub.card(std::min(cardMax, lub.size() ));
71 }
72
75 int lbMin,int lbMax,const IntSet& theLub,
76 unsigned int cardMin, unsigned int cardMax)
77 : SetVarImpBase(home),
78 lub(home,theLub), glb(home,lbMin,lbMax) {
79 glb.card(std::max(cardMin, glb.size() ));
80 lub.card(std::min(cardMax, lub.size() ));
81 }
82
85 const IntSet& theGlb,const IntSet& theLub,
86 unsigned int cardMin, unsigned int cardMax)
87 : SetVarImpBase(home), lub(home,theLub), glb(home,theGlb) {
88 glb.card(std::max(cardMin, glb.size() ));
89 lub.card(std::min(cardMax, lub.size() ));
90 }
91
92
93 forceinline bool
94 SetVarImp::assigned(void) const {
95 return glb.size() == lub.size();
96 }
97
98 forceinline unsigned int
99 SetVarImp::cardMin(void) const { return glb.card(); }
100
101 forceinline unsigned int
102 SetVarImp::cardMax(void) const { return lub.card(); }
103
104 forceinline bool
105 SetVarImp::knownIn(int i) const { return (glb.in(i)); }
106
107 forceinline bool
108 SetVarImp::knownOut(int i) const { return !(lub.in(i)); }
109
110 forceinline int
111 SetVarImp::lubMin(void) const { return lub.min(); }
112
113 forceinline int
114 SetVarImp::lubMax(void) const { return lub.max(); }
115
116 forceinline int
117 SetVarImp::lubMinN(unsigned int n) const { return lub.minN(n); }
118
119 forceinline int
120 SetVarImp::glbMin(void) const { return glb.min(); }
121
122 forceinline int
123 SetVarImp::glbMax(void) const { return glb.max(); }
124
125 forceinline unsigned int
126 SetVarImp::glbSize() const { return glb.size(); }
127
128 forceinline unsigned int
129 SetVarImp::lubSize() const { return lub.size(); }
130
131 /*
132 * Support for delta information
133 *
134 */
135 forceinline int
137 return static_cast<const SetDelta&>(d).glbMin();
138 }
139 forceinline int
141 return static_cast<const SetDelta&>(d).glbMax();
142 }
143 forceinline bool
145 return static_cast<const SetDelta&>(d).glbAny();
146 }
147 forceinline int
149 return static_cast<const SetDelta&>(d).lubMin();
150 }
151 forceinline int
153 return static_cast<const SetDelta&>(d).lubMax();
154 }
155 forceinline bool
157 return static_cast<const SetDelta&>(d).lubAny();
158 }
159
161 SetVarImp::cardMin(Space& home,unsigned int newMin) {
162 if (cardMin() >= newMin)
163 return ME_SET_NONE;
164 if (newMin > cardMax())
165 return fail(home);
166 glb.card(newMin);
167 return cardMin_full(home);
168 }
169
171 SetVarImp::cardMax(Space& home,unsigned int newMax) {
172 if (cardMax() <= newMax)
173 return ME_SET_NONE;
174 if (cardMin() > newMax)
175 return fail(home);
176 lub.card(newMax);
177 return cardMax_full(home);
178 }
179
181 SetVarImp::intersect(Space& home,int i, int j) {
182 BndSetRanges lb(glb);
185 if (probe())
186 return fail(home);
187 if (assigned())
188 return ME_SET_NONE;
189 int oldMin = lub.min();
190 int oldMax = lub.max();
191 if (lub.intersect(home, i, j)) {
192 SetDelta d;
193 if (i == oldMin) {
194 d._lubMin = lub.max()+1;
195 d._lubMax = oldMax;
196 } else if (j == oldMax) {
197 d._lubMin = oldMin;
198 d._lubMax = lub.min()-1;
199 }
200 return processLubChange(home, d);
201 }
202 return ME_SET_NONE;
203 }
204
207 return intersect(home, i, i);
208 }
209
210 template<class I>
211 inline ModEvent
212 SetVarImp::intersectI(Space& home, I& iterator) {
213 if (assigned()) {
214 BndSetRanges lbi(glb);
215 Iter::Ranges::Diff<BndSetRanges,I> probe(lbi,iterator);
216 if (probe())
217 return fail(home);
218 return ME_SET_NONE;
219 }
220 if (!iterator()) {
221 if (cardMin() > 0)
222 return fail(home);
223 lub.card(0);
224 SetDelta d(1, 0, lub.min(), lub.max());
225 lub.excludeAll(home);
226 return notify(home, ME_SET_VAL, d);
227 }
228 int mi=iterator.min();
229 int ma=iterator.max();
230 ++iterator;
231 if (iterator())
232 return intersectI_full(home, mi, ma, iterator);
233 else
234 return intersect(home, mi, ma);
235 }
236
237 template<class I>
239 SetVarImp::intersectI_full(Space& home, int mi, int ma, I& iterator) {
240 Iter::Ranges::SingletonAppend<I> si(mi,ma,iterator);
241 if (lub.intersectI(home, si)) {
242 BndSetRanges ub(lub);
243 BndSetRanges lb(glb);
244 if (!Iter::Ranges::subset(lb,ub)) {
245 glb.become(home, lub);
246 glb.card(glb.size());
247 lub.card(glb.size());
248 return fail(home);
249 }
251 if (cardMax() > lub.size()) {
252 lub.card(lub.size());
253 if (cardMin() > cardMax()) {
254 glb.become(home, lub);
255 glb.card(glb.size());
256 lub.card(glb.size());
257 return fail(home);
258 }
259 me = ME_SET_CLUB;
260 }
261 if (cardMax() == lub.size() && cardMin() == cardMax()) {
262 glb.become(home, lub);
263 me = ME_SET_VAL;
264 }
265 SetDelta d;
266 return notify(home, me, d);
267 }
268 return ME_SET_NONE;
269 }
270
272 SetVarImp::include(Space& home, int i, int j) {
273 if (j<i)
274 return ME_SET_NONE;
275 BndSetRanges ub(lub);
277 if (!Iter::Ranges::subset(sij,ub)) {
278 return fail(home);
279 }
280 SetDelta d;
281 if (glb.include(home, i, j, d))
282 return processGlbChange(home, d);
283 return ME_SET_NONE;
284 }
285
287 SetVarImp::include(Space& home, int i) {
288 return include(home, i, i);
289 }
290
291 template<class I> forceinline ModEvent
292 SetVarImp::includeI(Space& home, I& iterator) {
293 if (!iterator()) {
294 return ME_SET_NONE;
295 }
296 if (assigned()) {
297 BndSetRanges lbi(glb);
299 probe(iterator,lbi);
300 return probe() ? fail(home) : ME_SET_NONE;
301 }
302 int mi=iterator.min();
303 int ma=iterator.max();
304 ++iterator;
305 if (iterator())
306 return includeI_full(home, mi, ma, iterator);
307 else
308 return include(home, mi, ma);
309 }
310
311 template<class I>
313 SetVarImp::includeI_full(Space& home, int mi, int ma, I& iterator) {
314 Iter::Ranges::SingletonAppend<I> si(mi,ma,iterator);
315 if (glb.includeI(home, si)) {
316 BndSetRanges ub(lub);
317 BndSetRanges lb(glb);
318 if (!Iter::Ranges::subset(lb,ub)) {
319 glb.become(home, lub);
320 glb.card(glb.size());
321 lub.card(glb.size());
322 return fail(home);
323 }
325 if (cardMin() < glb.size()) {
326 glb.card(glb.size());
327 if (cardMin() > cardMax()) {
328 glb.become(home, lub);
329 glb.card(glb.size());
330 lub.card(glb.size());
331 return fail(home);
332 }
333 me = ME_SET_CGLB;
334 }
335 if (cardMin() == glb.size() && cardMin() == cardMax()) {
336 lub.become(home, glb);
337 me = ME_SET_VAL;
338 }
339 SetDelta d;
340 return notify(home, me, d);
341 }
342 return ME_SET_NONE;
343 }
344
346 SetVarImp::exclude(Space& home, int i, int j) {
347 if (j<i)
348 return ME_SET_NONE;
350 BndSetRanges lb(glb);
352 if (probe())
353 return fail(home);
354 SetDelta d;
355 if (lub.exclude(home, i, j, d))
356 return processLubChange(home, d);
357 return ME_SET_NONE;
358 }
359
361 SetVarImp::exclude(Space& home, int i) {
362 return exclude(home, i, i);
363 }
364
365 template<class I>
366 inline ModEvent
367 SetVarImp::excludeI(Space& home, I& iterator) {
368 if (!iterator())
369 return ME_SET_NONE;
370 if (assigned()) {
371 BndSetRanges ubi(lub);
372 Iter::Ranges::Inter<BndSetRanges,I> probe(ubi,iterator);
373 return probe() ? fail(home) : ME_SET_NONE;
374 }
375 int mi=iterator.min();
376 int ma=iterator.max();
377 ++iterator;
378 if (iterator())
379 return excludeI_full(home, mi, ma, iterator);
380 else
381 return exclude(home, mi, ma);
382 }
383
384 template<class I>
386 SetVarImp::excludeI_full(Space& home, int mi, int ma, I& iterator) {
387 Iter::Ranges::SingletonAppend<I> si(mi,ma,iterator);
388 if (lub.excludeI(home, si)) {
389 BndSetRanges ub(lub);
390 BndSetRanges lb(glb);
391 if (!Iter::Ranges::subset(lb,ub)) {
392 glb.become(home, lub);
393 glb.card(glb.size());
394 lub.card(glb.size());
395 return fail(home);
396 }
398 if (cardMax() > lub.size()) {
399 lub.card(lub.size());
400 if (cardMin() > cardMax()) {
401 glb.become(home, lub);
402 glb.card(glb.size());
403 lub.card(glb.size());
404 return fail(home);
405 }
406 me = ME_SET_CLUB;
407 }
408 if (cardMax() == lub.size() && cardMin() == cardMax()) {
409 glb.become(home, lub);
410 me = ME_SET_VAL;
411 }
412 SetDelta d;
413 return notify(home, me, d);
414 }
415 return ME_SET_NONE;
416 }
417
418 /*
419 * Copying a variable
420 *
421 */
422
423 forceinline SetVarImp*
425 return copied() ?
426 static_cast<SetVarImp*>(forward()) :
427 perform_copy(home);
428 }
429
430 /*
431 * Iterator specializations
432 *
433 */
434
443 template<>
445 public:
447
448
449 LubRanges(void);
451 LubRanges(const SetVarImp*);
453 void init(const SetVarImp*);
455 };
456
459
463
464 forceinline void
468
477 template<>
479 public:
481
482
483 GlbRanges(void);
485 GlbRanges(const SetVarImp* x);
487 void init(const SetVarImp*);
489 };
490
493
497
498 forceinline void
502
503}}
504
505// STATISTICS: set-var
int n
Number of negative literals for node type.
Generic domain change information to be supplied to advisors.
Definition core.hpp:204
Integer sets.
Definition int.hh:174
Range iterator for computing set difference.
Range iterator for computing intersection (binary)
Range iterator for appending a singleton with a range iterator
Range iterator for singleton range.
Range iterator for integer sets.
Definition var-imp.hpp:185
void init(const BndSet &s)
Initialize with BndSet s.
int min(void) const
Return smallest element.
int minN(unsigned int n) const
Return n -th smallest element.
unsigned int size(void) const
Return size.
bool in(int i) const
Test whether i is an element of this set.
void become(Space &home, const BndSet &s)
Make this set equal to s.
int max(void) const
Return greatest element.
unsigned int card(void) const
Return cardinality.
bool includeI(Space &home, I &i)
Include the set represented by i in this set.
bool include(Space &home, int i, int j, SetDelta &d)
Include the set in this set.
Range iterator for the greatest lower bound.
Definition var-imp.hpp:359
void init(const T &x)
Initialize with greatest lower bound ranges for set variable x.
GlbRanges(void)
Default constructor.
bool intersectI(Space &home, I &i)
Exclude all elements not in the set represented by i from this set.
bool excludeI(Space &home, I &i)
Exclude all elements in the set represented by i from this set.
bool intersect(Space &home, int i, int j)
Intersect this set with the set .
void excludeAll(Space &home)
Exclude all elements from this set.
bool exclude(Space &home, int i, int j, SetDelta &d)
Exclude the set from this set.
Range iterator for the least upper bound.
Definition var-imp.hpp:317
LubRanges(void)
Default constructor.
void init(const T &x)
Initialize with least upper bound ranges for set variable x.
Finite set delta information for advisors.
Definition var-imp.hpp:52
Base-class for Set-variable implementations.
Definition var-imp.hpp:139
Gecode::ModEvent notify(Gecode::Space &home, Gecode::ModEvent me, Gecode::Delta &d)
Notify that variable implementation has been modified with modification event me and delta informatio...
Definition var-imp.hpp:365
Finite integer set variable implementation.
Definition var-imp.hpp:430
bool knownIn(int n) const
Test whether n is contained in greatest lower bound.
Definition set.hpp:105
int glbMin(void) const
Return minimum of the greatest lower bound.
Definition set.hpp:120
ModEvent intersect(Space &home, int n)
Exclude everything but n from the least upper bound.
Definition set.hpp:206
int lubMinN(unsigned int n) const
Return n -th smallest element in the least upper bound.
Definition set.hpp:117
static bool lubAny(const Delta &d)
Test whether arbitrary values got pruned from lub.
Definition set.hpp:156
unsigned int cardMax(void) const
Return current cardinality maximum.
Definition set.hpp:102
SetVarImp * copy(Space &home)
Return copy of this variable.
Definition set.hpp:424
unsigned int lubSize(void) const
Return the size of the least upper bound.
Definition set.hpp:129
int lubMin(void) const
Return minimum of the least upper bound.
Definition set.hpp:111
bool assigned(void) const
Test whether variable is assigned.
Definition set.hpp:94
int lubMax(void) const
Return maximum of the least upper bound.
Definition set.hpp:114
int glbMax(void) const
Return maximum of the greatest lower bound.
Definition set.hpp:123
ModEvent excludeI(Space &home, I &i)
Exclude set described by i from the least upper bound.
Definition set.hpp:367
static bool glbAny(const Delta &d)
Test whether arbitrary values got pruned from glb.
Definition set.hpp:144
bool knownOut(int) const
Test whether n is not contained in least upper bound.
Definition set.hpp:108
ModEvent includeI(Space &home, I &i)
Include set described by i in the greatest lower bound.
Definition set.hpp:292
unsigned int glbSize(void) const
Return the size of the greatest lower bound.
Definition set.hpp:126
ModEvent intersectI(Space &home, I &i)
Exclude everything but set described by i from the least upper bound.
Definition set.hpp:212
ModEvent exclude(Space &home, int n)
Exclude n from the least upper bound.
Definition set.hpp:361
ModEvent include(Space &home, int n)
Include n in the greatest lower bound.
Definition set.hpp:287
unsigned int cardMin(void) const
Return current cardinality minimum.
Definition set.hpp:99
SetVarImp(Space &home, SetVarImp &x)
Constructor for cloning x.
Definition set.cpp:117
Computation spaces.
Definition core.hpp:1742
static ModEvent me(const ModEventDelta &med)
Definition core.hpp:4270
bool subset(I &i, J &j)
Check whether range iterator i is subset of range iterator j.
const unsigned int card
Maximum cardinality of an integer set.
Definition set.hh:101
const Gecode::ModEvent ME_SET_CLUB
Domain operation has changed the least upper bound and the cardinality.
Definition var-type.hpp:179
const Gecode::ModEvent ME_SET_NONE
Domain operation has not changed domain.
Definition var-type.hpp:140
const Gecode::ModEvent ME_SET_VAL
Domain operation has resulted in a value (assigned variable)
Definition var-type.hpp:142
const Gecode::ModEvent ME_SET_GLB
Domain operation has changed the greatest lower bound.
Definition var-type.hpp:164
const Gecode::ModEvent ME_SET_CGLB
Domain operation has changed the greatest lower bound and the cardinality.
Definition var-type.hpp:186
const Gecode::ModEvent ME_SET_LUB
Domain operation has changed the least upper bound.
Definition var-type.hpp:156
Gecode toplevel namespace
Post propagator for SetVar x
Definition set.hh:767
int ModEvent
Type for modification events.
Definition core.hpp:62
Gecode::IntSet d(v, 7)
#define forceinline
Definition config.hpp:187