Generated on Sat Feb 7 2015 02:01:17 for Gecode by doxygen 1.8.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  * Last modified:
16  * $Date: 2011-09-06 10:22:20 +0200 (Tue, 06 Sep 2011) $ by $Author: tack $
17  * $Revision: 12392 $
18  *
19  * This file is part of Gecode, the generic constraint
20  * development environment:
21  * http://www.gecode.org
22  *
23  * Permission is hereby granted, free of charge, to any person obtaining
24  * a copy of this software and associated documentation files (the
25  * "Software"), to deal in the Software without restriction, including
26  * without limitation the rights to use, copy, modify, merge, publish,
27  * distribute, sublicense, and/or sell copies of the Software, and to
28  * permit persons to whom the Software is furnished to do so, subject to
29  * the following conditions:
30  *
31  * The above copyright notice and this permission notice shall be
32  * included in all copies or substantial portions of the Software.
33  *
34  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
35  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
36  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
37  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
38  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
39  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
40  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
41  *
42  */
43 
44 #include <iostream>
45 
46 namespace Gecode { namespace Set {
47 
48  class SetVarImp;
49  class LUBndSet;
50  class GLBndSet;
51 
56  class SetDelta : public Delta {
57  friend class SetVarImp;
58  friend class LUBndSet;
59  friend class GLBndSet;
60  private:
61  int _glbMin;
62  int _glbMax;
63  int _lubMin;
64  int _lubMax;
65  public:
67  SetDelta(void);
69  SetDelta(int glbMin, int glbMax, int lubMin, int lubMax);
71  int glbMin(void) const;
73  int glbMax(void) const;
75  int lubMin(void) const;
77  int lubMax(void) const;
79  bool glbAny(void) const;
81  bool lubAny(void) const;
82  };
83 
84 }}
85 
87 
88 namespace Gecode { namespace Set {
89 
93  class BndSet {
94  private:
95  RangeList* first;
96  RangeList* last;
97  protected:
99  unsigned int _size;
101  unsigned int _card;
103  void fst(RangeList* r);
105  void lst(RangeList* r);
106 
108  RangeList* fst(void) const;
110  RangeList* lst(void) const;
111 
112  public:
114  static const int MAX_OF_EMPTY = Limits::min-1;
116  static const int MIN_OF_EMPTY = Limits::max+1;
117 
119 
120  BndSet(void);
123  BndSet(Space& home, int i, int j);
125  GECODE_SET_EXPORT BndSet(Space& home, const IntSet& s);
127 
129 
130  void dispose(Space& home);
133 
135 
136  int min(void) const;
139  int max(void) const;
141  int minN(unsigned int n) const;
143  unsigned int size(void) const;
145  unsigned int card(void) const;
147  void card(unsigned int c);
149 
151 
152  bool empty(void) const;
155  bool in(int i) const;
157 
159 
160  void become(Space& home, const BndSet& s);
163 
165 
166  RangeList* ranges(void) const;
169 
170  protected:
172  template<class I> bool overwrite(Space& home,I& i);
173 
174  public:
176 
177  void update(Space& home, BndSet& x);
180 
182  GECODE_SET_EXPORT bool isConsistent(void) const;
183  };
184 
190  public:
192 
193  BndSetRanges(void);
196  BndSetRanges(const BndSet& s);
198  void init(const BndSet& s);
200  };
201 
209  class GLBndSet : public BndSet {
210  private:
212  GECODE_SET_EXPORT bool include_full(Space& home,int,int,SetDelta&);
213  public:
215 
216  GLBndSet(void);
219  GLBndSet(Space&);
221  GLBndSet(Space& home, int i, int j);
223  GLBndSet(Space& home, const IntSet& s);
225  void init(Space& home);
227 
229 
230  bool include(Space& home,int i,int j,SetDelta& d);
233  template<class I> bool includeI(Space& home,I& i);
235  private:
236  GLBndSet(const GLBndSet&);
237  const GLBndSet& operator =(const GLBndSet&);
238  };
239 
247  class LUBndSet: public BndSet{
248  private:
249  GECODE_SET_EXPORT bool exclude_full(Space& home, int, int, SetDelta&);
250  GECODE_SET_EXPORT bool intersect_full(Space& home, int i, int j);
251  public:
253 
254  LUBndSet(void);
257  LUBndSet(Space& home);
259  LUBndSet(Space& home, int i, int j);
261  LUBndSet(Space& home, const IntSet& s);
263  void init(Space& home);
265 
267 
268  bool exclude(Space& home, int i, int j, SetDelta& d);
271  bool intersect(Space& home, int i, int j);
273  template<class I> bool intersectI(Space& home, I& i);
275  template<class I> bool excludeI(Space& home, I& i);
277  void excludeAll(Space& home);
279  private:
280  LUBndSet(const LUBndSet&);
281  const LUBndSet& operator =(const LUBndSet&);
282  };
283 
284  /*
285  * Iterators
286  *
287  */
288 
289 
295  template<class I>
296  class RangesCompl :
297  public Iter::Ranges::Compl<Limits::min, Limits::max, I> {
298  public:
300 
301  RangesCompl(void);
304  RangesCompl(I& i);
306  void init(I& i);
308  };
309 
321  template<class T> class LubRanges {
322  public:
324 
325  LubRanges(void);
328  LubRanges(const T& x);
330  void init(const T& x);
332 
334 
335  bool operator ()(void) const;
338  void operator ++(void);
340 
342 
343  int min(void) const;
346  int max(void) const;
348  unsigned int width(void) const;
350  };
351 
363  template<class T> class GlbRanges {
364  public:
366 
367  GlbRanges(void);
370  GlbRanges(const T& x);
372  void init(const T& x);
374 
376 
377  bool operator ()(void) const;
380  void operator ++(void);
382 
384 
385  int min(void) const;
388  int max(void) const;
390  unsigned int width(void) const;
392  };
393 
405  template<class T>
406  class UnknownRanges : public Iter::Ranges::Diff<LubRanges<T>, GlbRanges<T> >{
407  private:
408  LubRanges<T> i1;
409  GlbRanges<T> i2;
410  public:
412 
413  UnknownRanges(void);
416  UnknownRanges(const T& x);
418  void init(const T& x);
420  };
421 
422 }}
423 
426 
427 namespace Gecode { namespace Set {
428 
434  class SetVarImp : public SetVarImpBase {
435  friend class LubRanges<SetVarImp*>;
436  friend class GlbRanges<SetVarImp*>;
437  private:
439  LUBndSet lub;
441  GLBndSet glb;
442 
443  protected:
445  SetVarImp(Space& home, bool share, SetVarImp& x);
446  public:
448 
449  SetVarImp(Space& home);
459  SetVarImp(Space& home,int glbMin,int glbMax,int lubMin,int lubMax,
460  unsigned int cardMin = 0,
461  unsigned int cardMax = Limits::card);
470  SetVarImp(Space& home,const IntSet& glbD,int lubMin,int lubMax,
471  unsigned int cardMin,unsigned int cardMax);
480  SetVarImp(Space& home,int glbMin,int glbMax,const IntSet& lubD,
481  unsigned int cardMin,unsigned int cardMax);
490  SetVarImp(Space& home,const IntSet& glbD,const IntSet& lubD,
491  unsigned int cardMin,unsigned int cardMax);
493 
495 
496  unsigned int cardMin(void) const;
499  unsigned int cardMax(void) const;
501  int lubMin(void) const;
503  int lubMax(void) const;
505  int lubMinN(unsigned int n) const;
507  int glbMin(void) const;
509  int glbMax(void) const;
511  unsigned int glbSize(void) const;
513  unsigned int lubSize(void) const;
515 
517 
518  bool assigned(void) const;
521  bool knownIn(int n) const;
523  bool knownOut(int) const;
525 
526  private:
528 
529  template<class I> ModEvent includeI_full(Space& home,int mi, int ma, I& i);
532  template<class I> ModEvent excludeI_full(Space& home,int mi, int ma, I& i);
534  template<class I> ModEvent intersectI_full(Space& home,int mi, int ma, I& i);
536 
537  GECODE_SET_EXPORT ModEvent processLubChange(Space& home, SetDelta& d);
538  GECODE_SET_EXPORT ModEvent processGlbChange(Space& home, SetDelta& d);
539 
541 
542  GECODE_SET_EXPORT ModEvent cardMin_full(Space& home);
545  GECODE_SET_EXPORT ModEvent cardMax_full(Space& home);
547 
548  public:
549 
551 
552  ModEvent include(Space& home,int n);
555  ModEvent include(Space& home,int i,int j);
557  ModEvent exclude(Space& home,int n);
559  ModEvent exclude(Space& home,int i,int j);
561  ModEvent intersect(Space& home,int n);
563  ModEvent intersect(Space& home,int i,int j);
565  ModEvent cardMin(Space& home,unsigned int n);
567  ModEvent cardMax(Space& home,unsigned int n);
569 
571 
572  template<class I> ModEvent includeI(Space& home,I& i);
575  template<class I> ModEvent excludeI(Space& home,I& i);
577  template<class I> ModEvent intersectI(Space& home,I& i);
579 
580  public:
582 
583 
590  void subscribe(Space& home, Propagator& p, PropCond pc, bool schedule=true);
592  void cancel(Space& home, Propagator& p, PropCond pc);
594  void subscribe(Space& home, Advisor& a);
596  void cancel(Space& home, Advisor& a);
598 
599  private:
601  GECODE_SET_EXPORT SetVarImp* perform_copy(Space& home, bool share);
602 
603  public:
605 
606  SetVarImp* copy(Space& home, bool share);
609 
611 
612  static int glbMin(const Delta& d);
615  static int glbMax(const Delta& d);
617  static bool glbAny(const Delta& d);
619  static int lubMin(const Delta& d);
621  static int lubMax(const Delta& d);
623  static bool lubAny(const Delta& d);
625 
626  };
627 
628  class SetView;
629 
630 }}
631 
633 
634 // STATISTICS: set-var
bool in(int i) const
Test whether i is an element of this set.
Definition: integerset.hpp:228
static bool lubAny(const Delta &d)
Test whether arbitrary values got pruned from lub.
Definition: set.hpp:160
bool excludeI(Space &home, I &i)
Exclude all elements in the set represented by i from this set.
Definition: integerset.hpp:389
RangeList * lst(void) const
Return last range.
Definition: integerset.hpp:59
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to variable.
Definition: set.hpp:513
BndSetRanges(void)
Default constructor.
Definition: integerset.hpp:244
ModEvent exclude(Space &home, int n)
Exclude n from the least upper bound.
Definition: set.hpp:365
Range iterator for the unknown set.
Definition: var-imp.hpp:406
const int min
Smallest allowed integer in integer set.
Definition: set.hh:101
bool isConsistent(void) const
Check whether internal invariants hold.
Definition: integerset.cpp:293
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p with propagation condition pc.
Definition: set.hpp:517
SetVarImp * copy(Space &home, bool share)
Return copy of this variable.
Definition: set.hpp:428
int glbMin(void) const
Return minimum of the greatest lower bound.
Definition: set.hpp:124
bool operator()(void) const
Test whether iterator is still at a range or done.
SetVarImp(Space &home, bool share, SetVarImp &x)
Constructor for cloning x.
Definition: set.cpp:121
int max(void) const
Return largest value of range.
int lubMinN(unsigned int n) const
Return n -th smallest element in the least upper bound.
Definition: set.hpp:121
ModEvent excludeI(Space &home, I &i)
Exclude set described by i from the least upper bound.
Definition: set.hpp:371
Range iterator for range lists
Shrinking sets of integers.
Definition: var-imp.hpp:247
RangesCompl(void)
Default constructor.
Definition: integerset.hpp:409
int ModEvent
Type for modification events.
Definition: core.hpp:146
static void schedule(Space &home, Propagator &p, ModEvent me, bool force=false)
Schedule propagator p with modification event me.
Base-class for propagators.
Definition: core.hpp:755
Base-class for advisors.
Definition: core.hpp:926
Range iterator for the greatest lower bound.
Definition: var-imp.hpp:363
int min(void) const
Return smallest value of range.
Finite integer set variable implementation.
Definition: var-imp.hpp:434
unsigned int card(void) const
Return cardinality.
Definition: integerset.hpp:134
static const int MIN_OF_EMPTY
Returned by empty sets when asked for their minimum element.
Definition: var-imp.hpp:116
Range iterator for computing the complement (described by template arguments)
const unsigned int card
Maximum cardinality of an integer set.
Definition: set.hh:103
ModEvent intersect(Space &home, int n)
Exclude everything but n from the least upper bound.
Definition: set.hpp:210
const int max
Largest allowed integer in integer set.
Definition: set.hh:99
Computation spaces.
Definition: core.hpp:1362
Range iterator for the least upper bound.
Definition: var-imp.hpp:321
int glbMax(void) const
Return maximum of the greatest lower bound.
Definition: set.hpp:127
int minN(unsigned int n) const
Return n -th smallest element.
Definition: integerset.hpp:124
bool glbAny(void) const
Test whether delta represents any domain change in glb.
Definition: delta.hpp:68
Gecode::IntSet d(v, 7)
int min(void) const
Return smallest value of range.
static const int MAX_OF_EMPTY
Returned by empty sets when asked for their maximum element.
Definition: var-imp.hpp:114
Gecode::FloatVal c(-8, 8)
unsigned int size(void) const
Return size.
Definition: integerset.hpp:97
int lubMax(void) const
Return maximum of the least upper bound.
Definition: set.hpp:118
int max(void) const
Return largest value of range.
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Gecode::IntArgs i(4, 1, 2, 3, 4)
void init(const T &x)
Initialize with unknown set ranges for set variable x.
Definition: iter.hpp:54
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
unsigned int cardMax(void) const
Return current cardinality maximum.
Definition: set.hpp:106
void become(Space &home, const BndSet &s)
Make this set equal to s.
Definition: integerset.hpp:215
bool empty(void) const
Test whether this set is empty.
Definition: integerset.hpp:102
static bool glbAny(const Delta &d)
Test whether arbitrary values got pruned from glb.
Definition: set.hpp:148
unsigned int cardMin(void) const
Return current cardinality minimum.
Definition: set.hpp:103
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
bool operator()(void) const
Test whether iterator is still at a range or done.
ModEvent includeI(Space &home, I &i)
Include set described by i in the greatest lower bound.
Definition: set.hpp:296
int PropCond
Type for propagation conditions.
Definition: core.hpp:156
void init(Space &home)
Initialize as the empty set.
Definition: integerset.hpp:275
int glbMax(void) const
Return glb maximum.
Definition: delta.hpp:56
bool intersectI(Space &home, I &i)
Exclude all elements not in the set represented by i from this set.
Definition: integerset.hpp:374
UnknownRanges(void)
Default constructor.
Definition: iter.hpp:44
A complement iterator spezialized for the BndSet limits.
Definition: var-imp.hpp:296
int glbMin(void) const
Return glb minimum.
Definition: delta.hpp:52
void operator++(void)
Move iterator to next range (if possible)
RangeList * fst(void) const
Return first range.
Definition: integerset.hpp:54
Sets of integers.
Definition: var-imp.hpp:93
Range iterator for integer sets.
Definition: var-imp.hpp:189
void operator++(void)
Move iterator to next range (if possible)
void init(const BndSet &s)
Initialize with BndSet s.
Definition: integerset.hpp:251
unsigned int _size
The size of this set.
Definition: var-imp.hpp:99
void init(I &i)
Initialize with iterator i.
Definition: integerset.hpp:418
unsigned int _card
The cardinality this set represents.
Definition: var-imp.hpp:101
RangeList * ranges(void) const
Return range list for iteration.
Definition: integerset.hpp:92
Integer sets.
Definition: int.hh:171
bool knownOut(int) const
Test whether n is not contained in least upper bound.
Definition: set.hpp:112
GLBndSet(void)
Default constructor. Creates an empty set.
Definition: integerset.hpp:261
LUBndSet(void)
Default constructor. Creates an empty set.
Definition: integerset.hpp:317
void update(Space &home, BndSet &x)
Update this set to be a clone of set x.
Definition: integerset.hpp:144
void init(Space &home)
Initialize as the full set including everything between Limits::min and Limits::max.
Definition: integerset.hpp:332
ModEvent include(Space &home, int n)
Include n in the greatest lower bound.
Definition: set.hpp:291
bool exclude(Space &home, int i, int j, SetDelta &d)
Exclude the set from this set.
Definition: integerset.hpp:343
bool includeI(Space &home, I &i)
Include the set represented by i in this set.
Definition: integerset.hpp:300
bool knownIn(int n) const
Test whether n is contained in greatest lower bound.
Definition: set.hpp:109
void dispose(Space &home)
Free memory used by this set.
Definition: integerset.hpp:64
Base-class for Set-variable implementations.
Definition: var-imp.hpp:117
Set view for set variables
Definition: view.hpp:60
ModEvent intersectI(Space &home, I &i)
Exclude everything but set described by i from the least upper bound.
Definition: set.hpp:216
int lubMin(void) const
Return lub minimum.
Definition: delta.hpp:60
bool intersect(Space &home, int i, int j)
Intersect this set with the set .
Definition: integerset.hpp:359
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
Generic domain change information to be supplied to advisors.
Definition: core.hpp:275
unsigned int lubSize(void) const
Return the size of the least upper bound.
Definition: set.hpp:133
GlbRanges(void)
Default constructor.
int min(void) const
Return smallest element.
Definition: integerset.hpp:107
int lubMax(void) const
Return lub maximum.
Definition: delta.hpp:64
void init(const T &x)
Initialize with least upper bound ranges for set variable x.
int lubMin(void) const
Return minimum of the least upper bound.
Definition: set.hpp:115
Growing sets of integers.
Definition: var-imp.hpp:209
unsigned int glbSize(void) const
Return the size of the greatest lower bound.
Definition: set.hpp:130
Lists of ranges (intervals)
Definition: range-list.hpp:53
Gecode toplevel namespace
bool overwrite(Space &home, I &i)
Overwrite the ranges with those represented by i.
Definition: integerset.hpp:175
Range iterator for computing set difference.
Definition: ranges-diff.hpp:47
LubRanges(void)
Default constructor.
BndSet(void)
Default constructor. Creates an empty set.
Definition: integerset.hpp:50
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
bool assigned(void) const
Test whether variable is assigned.
Definition: set.hpp:98
SetDelta(void)
Create set delta as providing no information (if any is true)
Definition: delta.hpp:43
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
int max(void) const
Return greatest element.
Definition: integerset.hpp:115
struct Gecode::@518::NNF::@57::@59 a
For atomic nodes.
#define GECODE_SET_EXPORT
Definition: set.hh:69
void init(const T &x)
Initialize with greatest lower bound ranges for set variable x.
bool include(Space &home, int i, int j, SetDelta &d)
Include the set in this set.
Definition: integerset.hpp:283
bool lubAny(void) const
Test whether delta represents any domain change in lub.
Definition: delta.hpp:72
void excludeAll(Space &home)
Exclude all elements from this set.
Definition: integerset.hpp:399
Finite set delta information for advisors.
Definition: var-imp.hpp:56