Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.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
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
Generic domain change information to be supplied to advisors.
Definition core.hpp:204
Integer sets.
Definition int.hh:174
int min(int i) const
Return minimum of range at position i.
int max(int i) const
Return maximum of range at position i.
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
BndSetRanges(void)
Default constructor.
void init(const BndSet &s)
Initialize with BndSet s.
unsigned int size(void) const
Return size.
void become(Space &home, const BndSet &s)
Make this set equal to s.
unsigned int card(void) const
Return cardinality.
bool includeI(Space &home, I &i)
Include the set represented by i in this set.
void init(const SetVarImp *)
Initialize with ranges for variable implementation x.
Definition set.hpp:499
GlbRanges(void)
Default constructor.
Definition set.hpp:492
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.
void init(const SetVarImp *)
Initialize with ranges for variable implementation x.
Definition set.hpp:465
LubRanges(void)
Default constructor.
Definition set.hpp:458
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
SetVarImpBase(Gecode::Space &home, SetVarImpBase &x)
Constructor for cloning x.
Definition var-imp.hpp:343
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:1744
static ModEvent me(const ModEventDelta &med)
Definition core.hpp:4277
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
Finite integer sets.
Definition var-imp.hpp:137
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:773
int ModEvent
Type for modification events.
Definition core.hpp:62
Gecode::IntSet d(v, 7)
#define forceinline
Definition config.hpp:194