this repo has no description
dekker.one
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
47 forceinline
48 SetVarImp::SetVarImp(Space& home)
49 : SetVarImpBase(home), lub(home), glb(home) {
50 lub.card(Limits::card);
51 assert(lub.card()==lub.size());
52 }
53
54 forceinline
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
63 forceinline
64 SetVarImp::SetVarImp(Space& home,
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
73 forceinline
74 SetVarImp::SetVarImp(Space& home,
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
83 forceinline
84 SetVarImp::SetVarImp(Space& home,
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
136 SetVarImp::glbMin(const Delta& d) {
137 return static_cast<const SetDelta&>(d).glbMin();
138 }
139 forceinline int
140 SetVarImp::glbMax(const Delta& d) {
141 return static_cast<const SetDelta&>(d).glbMax();
142 }
143 forceinline bool
144 SetVarImp::glbAny(const Delta& d) {
145 return static_cast<const SetDelta&>(d).glbAny();
146 }
147 forceinline int
148 SetVarImp::lubMin(const Delta& d) {
149 return static_cast<const SetDelta&>(d).lubMin();
150 }
151 forceinline int
152 SetVarImp::lubMax(const Delta& d) {
153 return static_cast<const SetDelta&>(d).lubMax();
154 }
155 forceinline bool
156 SetVarImp::lubAny(const Delta& d) {
157 return static_cast<const SetDelta&>(d).lubAny();
158 }
159
160 forceinline ModEvent
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
170 forceinline ModEvent
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
180 forceinline ModEvent
181 SetVarImp::intersect(Space& home,int i, int j) {
182 BndSetRanges lb(glb);
183 Iter::Ranges::Singleton s(i,j);
184 Iter::Ranges::Diff<BndSetRanges, Iter::Ranges::Singleton> probe(lb, s);
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
205 forceinline ModEvent
206 SetVarImp::intersect(Space& home,int i) {
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>
238 ModEvent
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 }
250 ModEvent me = ME_SET_LUB;
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
271 forceinline ModEvent
272 SetVarImp::include(Space& home, int i, int j) {
273 if (j<i)
274 return ME_SET_NONE;
275 BndSetRanges ub(lub);
276 Iter::Ranges::Singleton sij(i,j);
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
286 forceinline ModEvent
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);
298 Iter::Ranges::Diff<I,BndSetRanges>
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>
312 ModEvent
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 }
324 ModEvent me = ME_SET_GLB;
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
345 forceinline ModEvent
346 SetVarImp::exclude(Space& home, int i, int j) {
347 if (j<i)
348 return ME_SET_NONE;
349 Iter::Ranges::Singleton sij(i,j);
350 BndSetRanges lb(glb);
351 Iter::Ranges::Inter<Iter::Ranges::Singleton,BndSetRanges> probe(sij,lb);
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
360 forceinline ModEvent
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>
385 ModEvent
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 }
397 ModEvent me = ME_SET_LUB;
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*
424 SetVarImp::copy(Space& home) {
425 return copied() ?
426 static_cast<SetVarImp*>(forward()) :
427 perform_copy(home);
428 }
429
430 /*
431 * Iterator specializations
432 *
433 */
434
435 /**
436 * \brief Range iterator for the least upper bound of a set variable implementation
437 *
438 * This class provides (by specialization) a range iterator
439 * for the least upper bounds of set variable implementations.
440 *
441 * \ingroup TaskActorSet
442 */
443 template<>
444 class LubRanges<SetVarImp*> : public BndSetRanges {
445 public:
446 /// \name Constructors and initialization
447 //@{
448 /// Default constructor
449 LubRanges(void);
450 /// Initialize with ranges for variable implementation \a x
451 LubRanges(const SetVarImp*);
452 /// Initialize with ranges for variable implementation \a x
453 void init(const SetVarImp*);
454 //@}
455 };
456
457 forceinline
458 LubRanges<SetVarImp*>::LubRanges(void) {}
459
460 forceinline
461 LubRanges<SetVarImp*>::LubRanges(const SetVarImp* x)
462 : BndSetRanges(x->lub) {}
463
464 forceinline void
465 LubRanges<SetVarImp*>::init(const SetVarImp* x) {
466 BndSetRanges::init(x->lub);
467 }
468
469 /**
470 * \brief Range iterator for the greatest lower bound of a set variable implementation
471 *
472 * This class provides (by specialization) a range iterator
473 * for the greatest lower bounds of set variable implementations.
474 *
475 * \ingroup TaskActorSet
476 */
477 template<>
478 class GlbRanges<SetVarImp*> : public BndSetRanges {
479 public:
480 /// \name Constructors and initialization
481 //@{
482 /// Default constructor
483 GlbRanges(void);
484 /// Initialize with ranges for variable implementation \a x
485 GlbRanges(const SetVarImp* x);
486 /// Initialize with ranges for variable implementation \a x
487 void init(const SetVarImp*);
488 //@}
489 };
490
491 forceinline
492 GlbRanges<SetVarImp*>::GlbRanges(void) {}
493
494 forceinline
495 GlbRanges<SetVarImp*>::GlbRanges(const SetVarImp* x)
496 : BndSetRanges(x->glb) {}
497
498 forceinline void
499 GlbRanges<SetVarImp*>::init(const SetVarImp* x) {
500 BndSetRanges::init(x->glb);
501 }
502
503}}
504
505// STATISTICS: set-var