Generated on Fri Jan 10 2020 11:38:25 for Gecode by doxygen 1.8.16
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
bool knownOut(int) const
Test whether n is not contained in least upper bound.
Definition: set.hpp:108
int min(void) const
Return smallest element.
Definition: integerset.hpp:103
GLBndSet(void)
Default constructor. Creates an empty set.
Definition: integerset.hpp:257
Post propagator for SetVar x
Definition: set.hh:767
SetVarImp(Space &home, SetVarImp &x)
Constructor for cloning x.
Definition: set.cpp:117
bool include(Space &home, int i, int j, SetDelta &d)
Include the set in this set.
Definition: integerset.hpp:279
UnknownRanges(void)
Default constructor.
Definition: iter.hpp:40
bool operator()(void) const
Test whether iterator is still at a range or done.
LUBndSet(void)
Default constructor. Creates an empty set.
Definition: integerset.hpp:313
int lubMinN(unsigned int n) const
Return n -th smallest element in the least upper bound.
Definition: set.hpp:117
void init(Space &home)
Initialize as the full set including everything between Limits::min and Limits::max.
Definition: integerset.hpp:328
int lubMax(void) const
Return maximum of the least upper bound.
Definition: set.hpp:114
bool exclude(Space &home, int i, int j, SetDelta &d)
Exclude the set from this set.
Definition: integerset.hpp:339
BndSetRanges(void)
Default constructor.
Definition: integerset.hpp:240
bool lubAny(void) const
Test whether delta represents any domain change in lub.
Definition: delta.hpp:68
bool includeI(Space &home, I &i)
Include the set represented by i in this set.
Definition: integerset.hpp:296
unsigned int cardMin(void) const
Return current cardinality minimum.
Definition: set.hpp:99
int max(void) const
Return greatest element.
Definition: integerset.hpp:111
ModEvent fail(Space &home)
Run advisors to be run on failure and returns ME_GEN_FAILED.
Definition: core.hpp:4570
bool intersectI(Space &home, I &i)
Exclude all elements not in the set represented by i from this set.
Definition: integerset.hpp:370
const int min
Smallest allowed integer in integer set.
Definition: set.hh:99
LubRanges(void)
Default constructor.
void init(I &i)
Initialize with iterator i.
Definition: integerset.hpp:414
static bool lubAny(const Delta &d)
Test whether arbitrary values got pruned from lub.
Definition: set.hpp:156
void init(Space &home)
Initialize as the empty set.
Definition: integerset.hpp:271
RangeList * lst(void) const
Return last range.
Definition: integerset.hpp:55
ModEvent intersect(Space &home, int n)
Exclude everything but n from the least upper bound.
Definition: set.hpp:206
unsigned int cardMax(void) const
Return current cardinality maximum.
Definition: set.hpp:102
RangeList * ranges(void) const
Return range list for iteration.
Definition: integerset.hpp:88
static bool glbAny(const Delta &d)
Test whether arbitrary values got pruned from glb.
Definition: set.hpp:144
Range iterator for the unknown set.
Definition: var-imp.hpp:402
Computation spaces.
Definition: core.hpp:1742
ModEvent exclude(Space &home, int n)
Exclude n from the least upper bound.
Definition: set.hpp:361
void init(const T &x)
Initialize with least upper bound ranges for set variable x.
void excludeAll(Space &home)
Exclude all elements from this set.
Definition: integerset.hpp:395
int minN(unsigned int n) const
Return n -th smallest element.
Definition: integerset.hpp:120
static const int MIN_OF_EMPTY
Returned by empty sets when asked for their minimum element.
Definition: var-imp.hpp:112
bool in(int i) const
Test whether i is an element of this set.
Definition: integerset.hpp:224
Range iterator for computing the complement (described by template arguments)
RangeList * fst(void) const
Return first range.
Definition: integerset.hpp:50
void become(Space &home, const BndSet &s)
Make this set equal to s.
Definition: integerset.hpp:211
Gecode toplevel namespace
Base-class for propagators.
Definition: core.hpp:1064
bool assigned(void) const
Test whether variable is assigned.
Definition: set.hpp:94
int lubMin(void) const
Return minimum of the least upper bound.
Definition: set.hpp:111
Integer sets.
Definition: int.hh:174
const int max
Largest allowed integer in integer set.
Definition: set.hh:97
int max(void) const
Return largest value of range.
const unsigned int card
Maximum cardinality of an integer set.
Definition: set.hh:101
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
A complement iterator spezialized for the BndSet limits.
Definition: var-imp.hpp:292
static const int MAX_OF_EMPTY
Returned by empty sets when asked for their maximum element.
Definition: var-imp.hpp:110
GlbRanges(void)
Default constructor.
Generic domain change information to be supplied to advisors.
Definition: core.hpp:204
ModEvent intersectI(Space &home, I &i)
Exclude everything but set described by i from the least upper bound.
Definition: set.hpp:212
unsigned int size(void) const
Return size.
Definition: integerset.hpp:93
unsigned int _card
The cardinality this set represents.
Definition: var-imp.hpp:97
bool isConsistent(void) const
Check whether internal invariants hold.
Definition: integerset.cpp:289
#define GECODE_SET_EXPORT
Definition: set.hh:67
SetVarImp * copy(Space &home)
Return copy of this variable.
Definition: set.hpp:424
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
Range iterator for computing set difference.
Definition: ranges-diff.hpp:43
bool excludeI(Space &home, I &i)
Exclude all elements in the set represented by i from this set.
Definition: integerset.hpp:385
void update(Space &home, BndSet &x)
Update this set to be a clone of set x.
Definition: integerset.hpp:140
int glbMax(void) const
Return maximum of the greatest lower bound.
Definition: set.hpp:123
static void schedule(Gecode::Space &home, Gecode::Propagator &p, Gecode::ModEvent me)
Schedule propagator p.
Definition: var-imp.hpp:356
Range iterator for the greatest lower bound.
Definition: var-imp.hpp:359
void init(const BndSet &s)
Initialize with BndSet s.
Definition: integerset.hpp:247
unsigned int _size
The size of this set.
Definition: var-imp.hpp:95
int max(void) const
Return largest value of range.
SetDelta(void)
Create set delta as providing no information (if any is true)
Definition: delta.hpp:39
int glbMin(void) const
Return minimum of the greatest lower bound.
Definition: set.hpp:120
int ModEvent
Type for modification events.
Definition: core.hpp:62
int min(void) const
Return smallest value of range.
void reschedule(Space &home, Propagator &p, PropCond pc)
Re-schedule propagator p with propagation condition pc.
Definition: set.cpp:149
int glbMin(void) const
Return glb minimum.
Definition: delta.hpp:48
void dispose(Space &home)
Free memory used by this set.
Definition: integerset.hpp:60
ModEvent includeI(Space &home, I &i)
Include set described by i in the greatest lower bound.
Definition: set.hpp:292
bool glbAny(void) const
Test whether delta represents any domain change in glb.
Definition: delta.hpp:64
int PropCond
Type for propagation conditions.
Definition: core.hpp:72
I i
Iterator to compute complement for.
Base-class for Set-variable implementations.
Definition: var-imp.hpp:139
int glbMax(void) const
Return glb maximum.
Definition: delta.hpp:52
Set view for set variables
Definition: view.hpp:56
unsigned int glbSize(void) const
Return the size of the greatest lower bound.
Definition: set.hpp:126
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to variable.
Definition: set.cpp:140
void operator++(void)
Move iterator to next range (if possible)
Finite set delta information for advisors.
Definition: var-imp.hpp:52
Gecode::IntSet d(v, 7)
Base-class for advisors.
Definition: core.hpp:1292
Range iterator for the least upper bound.
Definition: var-imp.hpp:317
int lubMin(void) const
Return lub minimum.
Definition: delta.hpp:56
Finite integer set variable implementation.
Definition: var-imp.hpp:430
Range iterator for integer sets.
Definition: var-imp.hpp:185
int lubMax(void) const
Return lub maximum.
Definition: delta.hpp:60
Growing sets of integers.
Definition: var-imp.hpp:205
void init(const T &x)
Initialize with unknown set ranges for set variable x.
Definition: iter.hpp:50
bool knownIn(int n) const
Test whether n is contained in greatest lower bound.
Definition: set.hpp:105
RangesCompl(void)
Default constructor.
Definition: integerset.hpp:405
bool operator()(void) const
Test whether iterator is still at a range or done.
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
bool empty(void) const
Test whether this set is empty.
Definition: integerset.hpp:98
Gecode::FloatVal c(-8, 8)
Range iterator for range lists
Shrinking sets of integers.
Definition: var-imp.hpp:243
void operator++(void)
Move iterator to next range (if possible)
void init(const T &x)
Initialize with greatest lower bound ranges for set variable x.
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
ModEvent include(Space &home, int n)
Include n in the greatest lower bound.
Definition: set.hpp:287
Lists of ranges (intervals)
Definition: range-list.hpp:49
bool overwrite(Space &home, I &i)
Overwrite the ranges with those represented by i.
Definition: integerset.hpp:171
int min(void) const
Return smallest value of range.
Gecode::IntArgs i({1, 2, 3, 4})
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
BndSet(void)
Default constructor. Creates an empty set.
Definition: integerset.hpp:46
ModEvent excludeI(Space &home, I &i)
Exclude set described by i from the least upper bound.
Definition: set.hpp:367
unsigned int card(void) const
Return cardinality.
Definition: integerset.hpp:130
Sets of integers.
Definition: var-imp.hpp:89
bool intersect(Space &home, int i, int j)
Intersect this set with the set .
Definition: integerset.hpp:355
unsigned int lubSize(void) const
Return the size of the least upper bound.
Definition: set.hpp:129