Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
var-imp.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 *
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
52 class SetDelta : public Delta {
53 friend class SetVarImp;
54 friend class LUBndSet;
55 friend class GLBndSet;
56 private:
57 int _glbMin;
58 int _glbMax;
59 int _lubMin;
60 int _lubMax;
61 public:
63 SetDelta(void);
65 SetDelta(int glbMin, int glbMax, int lubMin, int lubMax);
67 int glbMin(void) const;
69 int glbMax(void) const;
71 int lubMin(void) const;
73 int lubMax(void) const;
75 bool glbAny(void) const;
77 bool lubAny(void) const;
78 };
79
80}}
81
83
84namespace Gecode { namespace Set {
85
89 class BndSet {
90 private:
91 RangeList* first;
92 RangeList* last;
93 protected:
95 unsigned int _size;
97 unsigned int _card;
99 void fst(RangeList* r);
101 void lst(RangeList* r);
102
104 RangeList* fst(void) const;
106 RangeList* lst(void) const;
107
108 public:
110 static const int MAX_OF_EMPTY = Limits::min-1;
112 static const int MIN_OF_EMPTY = Limits::max+1;
113
115
116
117 BndSet(void);
119 BndSet(Space& home, int i, int j);
121 GECODE_SET_EXPORT BndSet(Space& home, const IntSet& s);
123
125
126
127 void dispose(Space& home);
129
131
132
133 int min(void) const;
135 int max(void) const;
137 int minN(unsigned int n) const;
139 unsigned int size(void) const;
141 unsigned int card(void) const;
143 void card(unsigned int c);
145
147
148
149 bool empty(void) const;
151 bool in(int i) const;
153
155
156
157 void become(Space& home, const BndSet& s);
159
161
162
163 RangeList* ranges(void) const;
165
166 protected:
168 template<class I> bool overwrite(Space& home,I& i);
169
170 public:
172
173
174 void update(Space& home, BndSet& x);
176
178 GECODE_SET_EXPORT bool isConsistent(void) const;
179 };
180
186 public:
188
189
190 BndSetRanges(void);
192 BndSetRanges(const BndSet& s);
194 void init(const BndSet& s);
196 };
197
205 class GLBndSet : public BndSet {
206 private:
208 GECODE_SET_EXPORT bool include_full(Space& home,int,int,SetDelta&);
209 public:
211
212
213 GLBndSet(void);
215 GLBndSet(Space&);
217 GLBndSet(Space& home, int i, int j);
219 GLBndSet(Space& home, const IntSet& s);
221 void init(Space& home);
223
225
226
227 bool include(Space& home,int i,int j,SetDelta& d);
229 template<class I> bool includeI(Space& home,I& i);
231 private:
232 GLBndSet(const GLBndSet&);
233 const GLBndSet& operator =(const GLBndSet&);
234 };
235
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:
249
250
251 LUBndSet(void);
253 LUBndSet(Space& home);
255 LUBndSet(Space& home, int i, int j);
257 LUBndSet(Space& home, const IntSet& s);
259 void init(Space& home);
261
263
264
265 bool exclude(Space& home, int i, int j, SetDelta& d);
267 bool intersect(Space& home, int i, int j);
269 template<class I> bool intersectI(Space& home, I& i);
271 template<class I> bool excludeI(Space& home, I& i);
273 void excludeAll(Space& home);
275 private:
276 LUBndSet(const LUBndSet&);
277 const LUBndSet& operator =(const LUBndSet&);
278 };
279
280 /*
281 * Iterators
282 *
283 */
284
285
291 template<class I>
293 public Iter::Ranges::Compl<Limits::min, Limits::max, I> {
294 public:
296
297
298 RangesCompl(void);
300 RangesCompl(I& i);
302 void init(I& i);
304 };
305
317 template<class T> class LubRanges {
318 public:
320
321
324 LubRanges(const T& x);
326 void init(const T& x);
328
330
331
332 bool operator ()(void) const;
334 void operator ++(void);
336
338
339
340 int min(void) const;
342 int max(void) const;
344 unsigned int width(void) const;
346 };
347
359 template<class T> class GlbRanges {
360 public:
362
363
366 GlbRanges(const T& x);
368 void init(const T& x);
370
372
373
374 bool operator ()(void) const;
376 void operator ++(void);
378
380
381
382 int min(void) const;
384 int max(void) const;
386 unsigned int width(void) const;
388 };
389
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:
408
409
410 UnknownRanges(void);
412 UnknownRanges(const T& x);
414 void init(const T& x);
416 };
417
418}}
419
422
423namespace Gecode { namespace Set {
424
430 class SetVarImp : public SetVarImpBase {
431 friend class LubRanges<SetVarImp*>;
432 friend class GlbRanges<SetVarImp*>;
433 private:
435 LUBndSet lub;
437 GLBndSet glb;
438
439 protected:
441 SetVarImp(Space& home, SetVarImp& x);
442 public:
444
445
446 SetVarImp(Space& home);
455 SetVarImp(Space& home,int glbMin,int glbMax,int lubMin,int lubMax,
456 unsigned int cardMin = 0,
457 unsigned int cardMax = Limits::card);
466 SetVarImp(Space& home,const IntSet& glbD,int lubMin,int lubMax,
467 unsigned int cardMin,unsigned int cardMax);
476 SetVarImp(Space& home,int glbMin,int glbMax,const IntSet& lubD,
477 unsigned int cardMin,unsigned int cardMax);
486 SetVarImp(Space& home,const IntSet& glbD,const IntSet& lubD,
487 unsigned int cardMin,unsigned int cardMax);
489
491
492
493 unsigned int cardMin(void) const;
495 unsigned int cardMax(void) const;
497 int lubMin(void) const;
499 int lubMax(void) const;
501 int lubMinN(unsigned int n) const;
503 int glbMin(void) const;
505 int glbMax(void) const;
507 unsigned int glbSize(void) const;
509 unsigned int lubSize(void) const;
511
513
514
515 bool assigned(void) const;
517 bool knownIn(int n) const;
519 bool knownOut(int) const;
521
522 private:
524
525
526 template<class I> ModEvent includeI_full(Space& home,int mi, int ma, I& i);
528 template<class I> ModEvent excludeI_full(Space& home,int mi, int ma, I& i);
530 template<class I> ModEvent intersectI_full(Space& home,int mi, int ma, I& i);
532
533 GECODE_SET_EXPORT ModEvent processLubChange(Space& home, SetDelta& d);
534 GECODE_SET_EXPORT ModEvent processGlbChange(Space& home, SetDelta& d);
535
537
538
539 GECODE_SET_EXPORT ModEvent cardMin_full(Space& home);
541 GECODE_SET_EXPORT ModEvent cardMax_full(Space& home);
543
544 public:
545
547
548
549 ModEvent include(Space& home,int n);
551 ModEvent include(Space& home,int i,int j);
553 ModEvent exclude(Space& home,int n);
555 ModEvent exclude(Space& home,int i,int j);
557 ModEvent intersect(Space& home,int n);
559 ModEvent intersect(Space& home,int i,int j);
561 ModEvent cardMin(Space& home,unsigned int n);
563 ModEvent cardMax(Space& home,unsigned int n);
565
567
568
569 template<class I> ModEvent includeI(Space& home,I& i);
571 template<class I> ModEvent excludeI(Space& home,I& i);
573 template<class I> ModEvent intersectI(Space& home,I& i);
575
576 public:
578
579
586 GECODE_SET_EXPORT void subscribe(Space& home, Propagator& p, PropCond pc, bool schedule=true);
597 GECODE_SET_EXPORT void subscribe(Space& home, Advisor& a, bool fail);
599
600 private:
602 GECODE_SET_EXPORT SetVarImp* perform_copy(Space& home);
603
604 public:
606
607
608 SetVarImp* copy(Space& home);
610
612
613
614 static int glbMin(const Delta& d);
616 static int glbMax(const Delta& d);
618 static bool glbAny(const Delta& d);
620 static int lubMin(const Delta& d);
622 static int lubMax(const Delta& d);
624 static bool lubAny(const Delta& d);
626
627 };
628
629 class SetView;
630
631}}
632
634
635// STATISTICS: set-var
int p
Number of positive literals for node type.
int n
Number of negative literals for node type.
struct Gecode::@603::NNF::@65::@67 a
For atomic nodes.
Base-class for advisors.
Definition core.hpp:1292
Generic domain change information to be supplied to advisors.
Definition core.hpp:204
Integer sets.
Definition int.hh:174
Range iterator for computing the complement (described by template arguments)
Range iterator for computing set difference.
Range iterator for range lists
Base-class for propagators.
Definition core.hpp:1064
Lists of ranges (intervals)
Range iterator for integer sets.
Definition var-imp.hpp:185
BndSetRanges(void)
Default constructor.
void init(const BndSet &s)
Initialize with BndSet s.
Sets of integers.
Definition var-imp.hpp:89
int min(void) const
Return smallest element.
bool isConsistent(void) const
Check whether internal invariants hold.
int minN(unsigned int n) const
Return n -th smallest element.
bool overwrite(Space &home, I &i)
Overwrite the ranges with those represented by i.
static const int MAX_OF_EMPTY
Returned by empty sets when asked for their maximum element.
Definition var-imp.hpp:110
RangeList * lst(void) const
Return last range.
unsigned int size(void) const
Return size.
BndSet(void)
Default constructor. Creates an empty set.
void update(Space &home, BndSet &x)
Update this set to be a clone of set x.
unsigned int _card
The cardinality this set represents.
Definition var-imp.hpp:97
bool empty(void) const
Test whether this set is empty.
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.
static const int MIN_OF_EMPTY
Returned by empty sets when asked for their minimum element.
Definition var-imp.hpp:112
int max(void) const
Return greatest element.
unsigned int card(void) const
Return cardinality.
RangeList * ranges(void) const
Return range list for iteration.
void dispose(Space &home)
Free memory used by this set.
unsigned int _size
The size of this set.
Definition var-imp.hpp:95
RangeList * fst(void) const
Return first range.
Growing sets of integers.
Definition var-imp.hpp:205
GLBndSet(void)
Default constructor. Creates an empty set.
bool includeI(Space &home, I &i)
Include the set represented by i in this set.
void init(Space &home)
Initialize as the empty 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
bool operator()(void) const
Test whether iterator is still at a range or done.
void init(const T &x)
Initialize with greatest lower bound ranges for set variable x.
int min(void) const
Return smallest value of range.
int max(void) const
Return largest value of range.
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
void operator++(void)
Move iterator to next range (if possible)
GlbRanges(const T &x)
Initialize with greatest lower bound ranges for set variable x.
GlbRanges(void)
Default constructor.
Shrinking sets of integers.
Definition var-imp.hpp:243
void init(Space &home)
Initialize as the full set including everything between Limits::min and Limits::max.
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.
LUBndSet(void)
Default constructor. Creates an empty 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
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
LubRanges(void)
Default constructor.
void init(const T &x)
Initialize with least upper bound ranges for set variable x.
int max(void) const
Return largest value of range.
bool operator()(void) const
Test whether iterator is still at a range or done.
void operator++(void)
Move iterator to next range (if possible)
LubRanges(const T &x)
Initialize with least upper bound ranges for set variable x.
int min(void) const
Return smallest value of range.
A complement iterator spezialized for the BndSet limits.
Definition var-imp.hpp:293
void init(I &i)
Initialize with iterator i.
RangesCompl(void)
Default constructor.
Finite set delta information for advisors.
Definition var-imp.hpp:52
bool glbAny(void) const
Test whether delta represents any domain change in glb.
Definition delta.hpp:64
bool lubAny(void) const
Test whether delta represents any domain change in lub.
Definition delta.hpp:68
int lubMax(void) const
Return lub maximum.
Definition delta.hpp:60
int glbMin(void) const
Return glb minimum.
Definition delta.hpp:48
SetDelta(void)
Create set delta as providing no information (if any is true)
Definition delta.hpp:39
int lubMin(void) const
Return lub minimum.
Definition delta.hpp:56
int glbMax(void) const
Return glb maximum.
Definition delta.hpp:52
Base-class for Set-variable implementations.
Definition var-imp.hpp:139
static void schedule(Gecode::Space &home, Gecode::Propagator &p, Gecode::ModEvent me)
Schedule propagator p.
Definition var-imp.hpp:356
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
void reschedule(Space &home, Propagator &p, PropCond pc)
Re-schedule propagator p with propagation condition pc.
Definition set.cpp:149
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
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to variable.
Definition set.cpp:140
SetVarImp(Space &home, SetVarImp &x)
Constructor for cloning x.
Definition set.cpp:117
Set view for set variables
Definition view.hpp:56
Range iterator for the unknown set.
Definition var-imp.hpp:402
void init(const T &x)
Initialize with unknown set ranges for set variable x.
Definition iter.hpp:50
UnknownRanges(void)
Default constructor.
Definition iter.hpp:40
Computation spaces.
Definition core.hpp:1742
#define GECODE_SET_EXPORT
Definition set.hh:67
const int min
Smallest allowed integer in integer set.
Definition set.hh:99
const unsigned int card
Maximum cardinality of an integer set.
Definition set.hh:101
const int max
Largest allowed integer in integer set.
Definition set.hh:97
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:767
int PropCond
Type for propagation conditions.
Definition core.hpp:72
Post propagator for SetVar x
Definition set.hh:767
int ModEvent
Type for modification events.
Definition core.hpp:62