Generated on Fri Jul 21 2023 00:00:00 for Gecode by doxygen 1.9.6
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.
Definition: bool-expr.cpp:232
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
struct Gecode::@603::NNF::@65::@67 a
For atomic nodes.
Base-class for advisors.
Definition: core.hpp:1294
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.
Definition: ranges-diff.hpp:43
Range iterator for range lists
Base-class for propagators.
Definition: core.hpp:1066
Lists of ranges (intervals)
Definition: range-list.hpp:49
Range iterator for integer sets.
Definition: var-imp.hpp:185
BndSetRanges(void)
Default constructor.
Definition: integerset.hpp:240
void init(const BndSet &s)
Initialize with BndSet s.
Definition: integerset.hpp:247
Sets of integers.
Definition: var-imp.hpp:89
int min(void) const
Return smallest element.
Definition: integerset.hpp:103
bool isConsistent(void) const
Check whether internal invariants hold.
Definition: integerset.cpp:289
int minN(unsigned int n) const
Return n -th smallest element.
Definition: integerset.hpp:120
bool overwrite(Space &home, I &i)
Overwrite the ranges with those represented by i.
Definition: integerset.hpp:171
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.
Definition: integerset.hpp:55
unsigned int size(void) const
Return size.
Definition: integerset.hpp:93
BndSet(void)
Default constructor. Creates an empty set.
Definition: integerset.hpp:46
void update(Space &home, BndSet &x)
Update this set to be a clone of set x.
Definition: integerset.hpp:140
unsigned int _card
The cardinality this set represents.
Definition: var-imp.hpp:97
bool empty(void) const
Test whether this set is empty.
Definition: integerset.hpp:98
bool in(int i) const
Test whether i is an element of this set.
Definition: integerset.hpp:224
void become(Space &home, const BndSet &s)
Make this set equal to s.
Definition: integerset.hpp:211
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.
Definition: integerset.hpp:111
unsigned int card(void) const
Return cardinality.
Definition: integerset.hpp:130
RangeList * ranges(void) const
Return range list for iteration.
Definition: integerset.hpp:88
void dispose(Space &home)
Free memory used by this set.
Definition: integerset.hpp:60
unsigned int _size
The size of this set.
Definition: var-imp.hpp:95
RangeList * fst(void) const
Return first range.
Definition: integerset.hpp:50
Growing sets of integers.
Definition: var-imp.hpp:205
GLBndSet(void)
Default constructor. Creates an empty set.
Definition: integerset.hpp:257
bool includeI(Space &home, I &i)
Include the set represented by i in this set.
Definition: integerset.hpp:296
void init(Space &home)
Initialize as the empty set.
Definition: integerset.hpp:271
bool include(Space &home, int i, int j, SetDelta &d)
Include the set in this set.
Definition: integerset.hpp:279
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.
Definition: integerset.hpp:328
bool intersectI(Space &home, I &i)
Exclude all elements not in the set represented by i from this set.
Definition: integerset.hpp:370
bool excludeI(Space &home, I &i)
Exclude all elements in the set represented by i from this set.
Definition: integerset.hpp:385
LUBndSet(void)
Default constructor. Creates an empty set.
Definition: integerset.hpp:313
bool intersect(Space &home, int i, int j)
Intersect this set with the set .
Definition: integerset.hpp:355
void excludeAll(Space &home)
Exclude all elements from this set.
Definition: integerset.hpp:395
bool exclude(Space &home, int i, int j, SetDelta &d)
Exclude the set from this set.
Definition: integerset.hpp:339
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.
Definition: integerset.hpp:414
RangesCompl(void)
Default constructor.
Definition: integerset.hpp:405
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
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:1744
ModEvent fail(Space &home)
Run advisors to be run on failure and returns ME_GEN_FAILED.
Definition: core.hpp:4577
#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:773
int PropCond
Type for propagation conditions.
Definition: core.hpp:72
Post propagator for SetVar x
Definition: set.hh:773
int ModEvent
Type for modification events.
Definition: core.hpp:62