Generated on Sat Apr 10 2021 00:00:00 for Gecode by doxygen 1.9.1
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 
42 namespace 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 
84 namespace 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  BndSet(void);
119  BndSet(Space& home, int i, int j);
121  GECODE_SET_EXPORT BndSet(Space& home, const IntSet& s);
123 
125 
126  void dispose(Space& home);
129 
131 
132  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  bool empty(void) const;
151  bool in(int i) const;
153 
155 
156  void become(Space& home, const BndSet& s);
159 
161 
162  RangeList* ranges(void) const;
165 
166  protected:
168  template<class I> bool overwrite(Space& home,I& i);
169 
170  public:
172 
173  void update(Space& home, BndSet& x);
176 
178  GECODE_SET_EXPORT bool isConsistent(void) const;
179  };
180 
186  public:
188 
189  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  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  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  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  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>
292  class RangesCompl :
293  public Iter::Ranges::Compl<Limits::min, Limits::max, I> {
294  public:
296 
297  RangesCompl(void);
300  RangesCompl(I& i);
302  void init(I& i);
304  };
305 
317  template<class T> class LubRanges {
318  public:
320 
321  LubRanges(void);
324  LubRanges(const T& x);
326  void init(const T& x);
328 
330 
331  bool operator ()(void) const;
334  void operator ++(void);
336 
338 
339  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  GlbRanges(void);
366  GlbRanges(const T& x);
368  void init(const T& x);
370 
372 
373  bool operator ()(void) const;
376  void operator ++(void);
378 
380 
381  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  UnknownRanges(void);
412  UnknownRanges(const T& x);
414  void init(const T& x);
416  };
417 
418 }}
419 
422 
423 namespace 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  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  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  bool assigned(void) const;
517  bool knownIn(int n) const;
519  bool knownOut(int) const;
521 
522  private:
524 
525  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  GECODE_SET_EXPORT ModEvent cardMin_full(Space& home);
541  GECODE_SET_EXPORT ModEvent cardMax_full(Space& home);
543 
544  public:
545 
547 
548  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  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  SetVarImp* copy(Space& home);
610 
612 
613  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
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:249
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
NNF * r
Right subtree.
Definition: bool-expr.cpp:242
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.
Definition: ranges-diff.hpp:43
Range iterator for range lists
Base-class for propagators.
Definition: core.hpp:1064
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
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
ModEvent fail(Space &home)
Run advisors to be run on failure and returns ME_GEN_FAILED.
Definition: core.hpp:4570
int PropCond
Type for propagation conditions.
Definition: core.hpp:72
int ModEvent
Type for modification events.
Definition: core.hpp:62
#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::FloatVal c(-8, 8)
Gecode::IntArgs i({1, 2, 3, 4})
Gecode::IntSet d(v, 7)