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 *
6 * Contributing authors:
7 * Christian Schulte <schulte@gecode.org>
8 * Gabor Szokoli <szokoli@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
40#include <iostream>
41
42namespace Gecode { namespace Set {
43
44 class SetVarImp;
45 class LUBndSet;
46 class GLBndSet;
47
48 /**
49 * \brief Finite set delta information for advisors
50 *
51 */
52 class SetDelta : public Delta {
53 friend class SetVarImp;
54 friend class LUBndSet;
55 friend class GLBndSet;
56 private:
57 int _glbMin; ///< Minimum glb value just pruned
58 int _glbMax; ///< Largest glb value just pruned
59 int _lubMin; ///< Minimum lub value just pruned
60 int _lubMax; ///< Largest lub value just pruned
61 public:
62 /// Create set delta as providing no information (if \a any is true)
63 SetDelta(void);
64 /// Create set delta with \a min and \a max
65 SetDelta(int glbMin, int glbMax, int lubMin, int lubMax);
66 /// Return glb minimum
67 int glbMin(void) const;
68 /// Return glb maximum
69 int glbMax(void) const;
70 /// Return lub minimum
71 int lubMin(void) const;
72 /// Return lub maximum
73 int lubMax(void) const;
74 /// Test whether delta represents any domain change in glb
75 bool glbAny(void) const;
76 /// Test whether delta represents any domain change in lub
77 bool lubAny(void) const;
78 };
79
80}}
81
82#include <gecode/set/var-imp/delta.hpp>
83
84namespace Gecode { namespace Set {
85
86 /**
87 * \brief Sets of integers
88 */
89 class BndSet {
90 private:
91 RangeList* first;
92 RangeList* last;
93 protected:
94 /// The size of this set
95 unsigned int _size;
96 /// The cardinality this set represents
97 unsigned int _card;
98 /// Set first range to \a r
99 void fst(RangeList* r);
100 /// Set last range to \a r
101 void lst(RangeList* r);
102
103 /// Return first range
104 RangeList* fst(void) const;
105 /// Return last range
106 RangeList* lst(void) const;
107
108 public:
109 /// Returned by empty sets when asked for their maximum element
110 static const int MAX_OF_EMPTY = Limits::min-1;
111 /// Returned by empty sets when asked for their minimum element
112 static const int MIN_OF_EMPTY = Limits::max+1;
113
114 /// \name Constructors and initialization
115 //@{
116 /// Default constructor. Creates an empty set.
117 BndSet(void);
118 /// Initialize as the set \f$ \{i,\dots,j\}\f$
119 BndSet(Space& home, int i, int j);
120 /// Initialize as the set represented by \a s
121 GECODE_SET_EXPORT BndSet(Space& home, const IntSet& s);
122 //@}
123
124 /// \name Memory management
125 //@{
126 /// Free memory used by this set
127 void dispose(Space& home);
128 //@}
129
130 /// \name Value access
131 //@{
132 /// Return smallest element
133 int min(void) const;
134 /// Return greatest element
135 int max(void) const;
136 /// Return \a n -th smallest element
137 int minN(unsigned int n) const;
138 /// Return size
139 unsigned int size(void) const;
140 /// Return cardinality
141 unsigned int card(void) const;
142 /// Set cardinality
143 void card(unsigned int c);
144 //@}
145
146 /// \name Tests
147 //@{
148 /// Test whether this set is empty
149 bool empty(void) const;
150 /// Test whether \a i is an element of this set
151 bool in(int i) const;
152 //@}
153
154 /// \name Update operations
155 //@{
156 /// Make this set equal to \a s
157 void become(Space& home, const BndSet& s);
158 //@}
159
160 /// \name Range list access for iteration
161 //@{
162 /// Return range list for iteration
163 RangeList* ranges(void) const;
164 //@}
165
166 protected:
167 /// Overwrite the ranges with those represented by \a i
168 template<class I> bool overwrite(Space& home,I& i);
169
170 public:
171 /// \name Cloning
172 //@{
173 /// Update this set to be a clone of set \a x
174 void update(Space& home, BndSet& x);
175 //@}
176
177 /// Check whether internal invariants hold
178 GECODE_SET_EXPORT bool isConsistent(void) const;
179 };
180
181 /**
182 * \brief Range iterator for integer sets
183 *
184 */
185 class BndSetRanges : public Iter::Ranges::RangeList {
186 public:
187 /// \name Constructors and initialization
188 //@{
189 /// Default constructor
190 BndSetRanges(void);
191 /// Initialize with BndSet \a s
192 BndSetRanges(const BndSet& s);
193 /// Initialize with BndSet \a s
194 void init(const BndSet& s);
195 //@}
196 };
197
198 /**
199 * \brief Growing sets of integers
200 *
201 * These sets provide operations for monotonically growing the set.
202 * Growing sets are used for implementing the greatest lower bound of
203 * set variables.
204 */
205 class GLBndSet : public BndSet {
206 private:
207 /// Include the set \f$\{i,\dots,j\}\f$ in this set
208 GECODE_SET_EXPORT bool include_full(Space& home,int,int,SetDelta&);
209 public:
210 /// \name Constructors and initialization
211 //@{
212 /// Default constructor. Creates an empty set.
213 GLBndSet(void);
214 /// Default constructor. Creates an empty set.
215 GLBndSet(Space&);
216 /// Initialize as the set \f$ \{i,\dots,j\}\f$
217 GLBndSet(Space& home, int i, int j);
218 /// Initialize as the set represented by \a s
219 GLBndSet(Space& home, const IntSet& s);
220 /// Initialize as the empty set
221 void init(Space& home);
222 //@}
223
224 /// \name Update operations
225 //@{
226 /// Include the set \f$\{i,\dots,j\}\f$ in this set
227 bool include(Space& home,int i,int j,SetDelta& d);
228 /// Include the set represented by \a i in this set
229 template<class I> bool includeI(Space& home,I& i);
230 //@}
231 private:
232 GLBndSet(const GLBndSet&);
233 const GLBndSet& operator =(const GLBndSet&);
234 };
235
236 /**
237 * \brief Shrinking sets of integers
238 *
239 * These sets provide operations for monotonically shrinking the set.
240 * Shrinking sets are used for implementing the least upper bound of
241 * set variables.
242 */
243 class LUBndSet: public BndSet{
244 private:
245 GECODE_SET_EXPORT bool exclude_full(Space& home, int, int, SetDelta&);
246 GECODE_SET_EXPORT bool intersect_full(Space& home, int i, int j);
247 public:
248 /// \name Constructors and initialization
249 //@{
250 /// Default constructor. Creates an empty set.
251 LUBndSet(void);
252 /// Initialize as the full set including everything between Limits::min and Limits::max
253 LUBndSet(Space& home);
254 /// Initialize as the set \f$ \{i,\dots,j\}\f$
255 LUBndSet(Space& home, int i, int j);
256 /// Initialize as the set represented by \a s
257 LUBndSet(Space& home, const IntSet& s);
258 /// Initialize as the full set including everything between Limits::min and Limits::max
259 void init(Space& home);
260 //@}
261
262 /// \name Update operations
263 //@{
264 /// Exclude the set \f$\{i,\dots,j\}\f$ from this set
265 bool exclude(Space& home, int i, int j, SetDelta& d);
266 /// Intersect this set with the set \f$\{i,\dots,j\}\f$
267 bool intersect(Space& home, int i, int j);
268 /// Exclude all elements not in the set represented by \a i from this set
269 template<class I> bool intersectI(Space& home, I& i);
270 /// Exclude all elements in the set represented by \a i from this set
271 template<class I> bool excludeI(Space& home, I& i);
272 /// Exclude all elements from this set
273 void excludeAll(Space& home);
274 //@}
275 private:
276 LUBndSet(const LUBndSet&);
277 const LUBndSet& operator =(const LUBndSet&);
278 };
279
280 /*
281 * Iterators
282 *
283 */
284
285
286 /**
287 * \brief A complement iterator spezialized for the %BndSet limits
288 *
289 * \ingroup TaskActorSet
290 */
291 template<class I>
292 class RangesCompl :
293 public Iter::Ranges::Compl<Limits::min, Limits::max, I> {
294 public:
295 /// \name Constructors and initialization
296 //@{
297 /// Default constructor
298 RangesCompl(void);
299 /// Initialize with iterator \a i
300 RangesCompl(I& i);
301 /// Initialize with iterator \a i
302 void init(I& i);
303 //@}
304 };
305
306 /**
307 * \brief Range iterator for the least upper bound
308 *
309 * This class provides (by specialization) a range iterator
310 * for the least upper bounds of all set views.
311 *
312 * Note that this template class serves only as a specification
313 * of the interface of the various specializations.
314 *
315 * \ingroup TaskActorSet
316 */
317 template<class T> class LubRanges {
318 public:
319 /// \name Constructors and initialization
320 //@{
321 /// Default constructor
322 LubRanges(void);
323 /// Initialize with least upper bound ranges for set variable \a x
324 LubRanges(const T& x);
325 /// Initialize with least upper bound ranges for set variable \a x
326 void init(const T& x);
327 //@}
328
329 /// \name Iteration control
330 //@{
331 /// Test whether iterator is still at a range or done
332 bool operator ()(void) const;
333 /// Move iterator to next range (if possible)
334 void operator ++(void);
335 //@}
336
337 /// \name Range access
338 //@{
339 /// Return smallest value of range
340 int min(void) const;
341 /// Return largest value of range
342 int max(void) const;
343 /// Return width of range (distance between minimum and maximum)
344 unsigned int width(void) const;
345 //@}
346 };
347
348 /**
349 * \brief Range iterator for the greatest lower bound
350 *
351 * This class provides (by specialization) a range iterator
352 * for the greatest lower bounds of all set views.
353 *
354 * Note that this template class serves only as a specification
355 * of the interface of the various specializations.
356 *
357 * \ingroup TaskActorSet
358 */
359 template<class T> class GlbRanges {
360 public:
361 /// \name Constructors and initialization
362 //@{
363 /// Default constructor
364 GlbRanges(void);
365 /// Initialize with greatest lower bound ranges for set variable \a x
366 GlbRanges(const T& x);
367 /// Initialize with greatest lower bound ranges for set variable \a x
368 void init(const T& x);
369 //@}
370
371 /// \name Iteration control
372 //@{
373 /// Test whether iterator is still at a range or done
374 bool operator ()(void) const;
375 /// Move iterator to next range (if possible)
376 void operator ++(void);
377 //@}
378
379 /// \name Range access
380 //@{
381 /// Return smallest value of range
382 int min(void) const;
383 /// Return largest value of range
384 int max(void) const;
385 /// Return width of range (distance between minimum and maximum)
386 unsigned int width(void) const;
387 //@}
388 };
389
390 /**
391 * \brief Range iterator for the unknown set
392 *
393 * This class provides a range iterator
394 * for the unknown set of all set views. The unknown set is the
395 * difference between least upper and greatest lower bound, i.e.
396 * those elements which still may be in the set, but are not yet
397 * known to be in.
398 *
399 * \ingroup TaskActorSet
400 */
401 template<class T>
402 class UnknownRanges : public Iter::Ranges::Diff<LubRanges<T>, GlbRanges<T> >{
403 private:
404 LubRanges<T> i1;
405 GlbRanges<T> i2;
406 public:
407 /// \name Constructors and initialization
408 //@{
409 /// Default constructor
410 UnknownRanges(void);
411 /// Initialize with unknown set ranges for set variable \a x
412 UnknownRanges(const T& x);
413 /// Initialize with unknown set ranges for set variable \a x
414 void init(const T& x);
415 //@}
416 };
417
418}}
419
420#include <gecode/set/var-imp/integerset.hpp>
421#include <gecode/set/var-imp/iter.hpp>
422
423namespace Gecode { namespace Set {
424
425 /**
426 * \brief Finite integer set variable implementation
427 *
428 * \ingroup Other
429 */
430 class SetVarImp : public SetVarImpBase {
431 friend class LubRanges<SetVarImp*>;
432 friend class GlbRanges<SetVarImp*>;
433 private:
434 /// The least upper bound of the domain
435 LUBndSet lub;
436 /// The greatest lower bound of the domain
437 GLBndSet glb;
438
439 protected:
440 /// Constructor for cloning \a x
441 SetVarImp(Space& home, SetVarImp& x);
442 public:
443 /// \name Constructors and initialization
444 //@{
445 /// Initialize with empty lower and full upper bound
446 SetVarImp(Space& home);
447 /**
448 * \brief Initialize with given bounds and cardinality
449 *
450 * Creates a set variable \f$s\f$ with
451 * \f$\mathit{glb}(s)=\{\mathit{glbMin},\dots,\mathit{glbMax}\}\f$,
452 * \f$\mathit{lub}(s)=\{\mathit{lubMin},\dots,\mathit{lubMax}\}\f$, and
453 * \f$\mathit{cardMin}\leq |s|\leq\mathit{cardMax}\f$
454 */
455 SetVarImp(Space& home,int glbMin,int glbMax,int lubMin,int lubMax,
456 unsigned int cardMin = 0,
457 unsigned int cardMax = Limits::card);
458 /**
459 * \brief Initialize with given bounds and cardinality
460 *
461 * Creates a set variable \f$s\f$ with
462 * \f$\mathit{glb}(s)=\mathit{glbD}\f$,
463 * \f$\mathit{lub}(s)=\{\mathit{lubMin},\dots,\mathit{lubMax}\}\f$, and
464 * \f$\mathit{cardMin}\leq |s|\leq\mathit{cardMax}\f$
465 */
466 SetVarImp(Space& home,const IntSet& glbD,int lubMin,int lubMax,
467 unsigned int cardMin,unsigned int cardMax);
468 /**
469 * \brief Initialize with given bounds and cardinality
470 *
471 * Creates a set variable \f$s\f$ with
472 * \f$\mathit{glb}(s)=\{\mathit{glbMin},\dots,\mathit{glbMax}\}\f$,
473 * \f$\mathit{lub}(s)=\mathit{lubD}\f$, and
474 * \f$\mathit{cardMin}\leq |s|\leq\mathit{cardMax}\f$
475 */
476 SetVarImp(Space& home,int glbMin,int glbMax,const IntSet& lubD,
477 unsigned int cardMin,unsigned int cardMax);
478 /**
479 * \brief Initialize with given bounds and cardinality
480 *
481 * Creates a set variable \f$s\f$ with
482 * \f$\mathit{glb}(s)=\mathit{glbD}\f$,
483 * \f$\mathit{lub}(s)=\mathit{lubD}\f$, and
484 * \f$\mathit{cardMin}\leq |s|\leq\mathit{cardMax}\f$
485 */
486 SetVarImp(Space& home,const IntSet& glbD,const IntSet& lubD,
487 unsigned int cardMin,unsigned int cardMax);
488 //@}
489
490 /// \name Value access
491 //@{
492 /// Return current cardinality minimum
493 unsigned int cardMin(void) const;
494 /// Return current cardinality maximum
495 unsigned int cardMax(void) const;
496 /// Return minimum of the least upper bound
497 int lubMin(void) const;
498 /// Return maximum of the least upper bound
499 int lubMax(void) const;
500 /// Return \a n -th smallest element in the least upper bound
501 int lubMinN(unsigned int n) const;
502 /// Return minimum of the greatest lower bound
503 int glbMin(void) const;
504 /// Return maximum of the greatest lower bound
505 int glbMax(void) const;
506 /// Return the size of the greatest lower bound
507 unsigned int glbSize(void) const;
508 /// Return the size of the least upper bound
509 unsigned int lubSize(void) const;
510 //@}
511
512 /// \name Domain tests
513 //@{
514 /// Test whether variable is assigned
515 bool assigned(void) const;
516 /// Test whether \a n is contained in greatest lower bound
517 bool knownIn(int n) const;
518 /// Test whether \a n is not contained in least upper bound
519 bool knownOut(int) const;
520 //@}
521
522 private:
523 /// \name Domain update by range iterator, implementations
524 //@{
525 /// Include set described by \a i in the greatest lower bound
526 template<class I> ModEvent includeI_full(Space& home,int mi, int ma, I& i);
527 /// Exclude set described by \a i from the least upper bound
528 template<class I> ModEvent excludeI_full(Space& home,int mi, int ma, I& i);
529 /// Exclude everything but set described by \a i from the least upper bound
530 template<class I> ModEvent intersectI_full(Space& home,int mi, int ma, I& i);
531 //@}
532
533 GECODE_SET_EXPORT ModEvent processLubChange(Space& home, SetDelta& d);
534 GECODE_SET_EXPORT ModEvent processGlbChange(Space& home, SetDelta& d);
535
536 /// \name Cardinality update implementation
537 //@{
538 /// Restrict cardinality to be at least n
539 GECODE_SET_EXPORT ModEvent cardMin_full(Space& home);
540 /// Restrict cardinality to be at most n
541 GECODE_SET_EXPORT ModEvent cardMax_full(Space& home);
542 //@}
543
544 public:
545
546 /// \name Domain update by value
547 //@{
548 /// Include \a n in the greatest lower bound
549 ModEvent include(Space& home,int n);
550 /// Include the range \f$\{i,\dots,j\}\f$ in the greatest lower bound
551 ModEvent include(Space& home,int i,int j);
552 /// Exclude \a n from the least upper bound
553 ModEvent exclude(Space& home,int n);
554 /// Exclude the range \f$\{i,\dots,j\}\f$ from the least upper bound
555 ModEvent exclude(Space& home,int i,int j);
556 /// Exclude everything but \a n from the least upper bound
557 ModEvent intersect(Space& home,int n);
558 /// Exclude everything but the range \f$\{i,\dots,j\}\f$ from the least upper bound
559 ModEvent intersect(Space& home,int i,int j);
560 /// Restrict cardinality to be at least n
561 ModEvent cardMin(Space& home,unsigned int n);
562 /// Restrict cardinality to be at most n
563 ModEvent cardMax(Space& home,unsigned int n);
564 //@}
565
566 /// \name Domain update by range iterator
567 //@{
568 /// Include set described by \a i in the greatest lower bound
569 template<class I> ModEvent includeI(Space& home,I& i);
570 /// Exclude set described by \a i from the least upper bound
571 template<class I> ModEvent excludeI(Space& home,I& i);
572 /// Exclude everything but set described by \a i from the least upper bound
573 template<class I> ModEvent intersectI(Space& home,I& i);
574 //@}
575
576 public:
577 /// \name Dependencies
578 //@{
579 /**
580 * \brief Subscribe propagator \a p with propagation condition \a pc to variable
581 *
582 * In case \a schedule is false, the propagator is just subscribed but
583 * not scheduled for execution (this must be used when creating
584 * subscriptions during propagation).
585 */
586 GECODE_SET_EXPORT void subscribe(Space& home, Propagator& p, PropCond pc, bool schedule=true);
587 /// Re-schedule propagator \a p with propagation condition \a pc
588 GECODE_SET_EXPORT void reschedule(Space& home, Propagator& p, PropCond pc);
589 /** \brief Subscribe advisor \a a to variable
590 *
591 * The advisor \a a is only subscribed if \a assigned is false.
592 *
593 * If \a fail is true, the advisor \a a is also run when a variable
594 * operation triggers failure. This feature is undocumented.
595 *
596 */
597 GECODE_SET_EXPORT void subscribe(Space& home, Advisor& a, bool fail);
598 //@}
599
600 private:
601 /// Return copy of not-yet copied variable
602 GECODE_SET_EXPORT SetVarImp* perform_copy(Space& home);
603
604 public:
605 /// \name Cloning
606 //@{
607 /// Return copy of this variable
608 SetVarImp* copy(Space& home);
609 //@}
610
611 /// \name Delta information for advisors
612 //@{
613 /// Return minimum value just pruned from glb
614 static int glbMin(const Delta& d);
615 /// Return maximum value just pruned from glb
616 static int glbMax(const Delta& d);
617 /// Test whether arbitrary values got pruned from glb
618 static bool glbAny(const Delta& d);
619 /// Return minimum value just pruned from lub
620 static int lubMin(const Delta& d);
621 /// Return maximum value just pruned from lub
622 static int lubMax(const Delta& d);
623 /// Test whether arbitrary values got pruned from lub
624 static bool lubAny(const Delta& d);
625 //@}
626
627 };
628
629 class SetView;
630
631}}
632
633#include <gecode/set/var-imp/set.hpp>
634
635// STATISTICS: set-var