Generated on Fri Jan 28 2022 04:43:06 for Gecode by doxygen 1.8.13
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
Range iterator for the unknown set.
Definition: var-imp.hpp:402
const int min
Smallest allowed integer in integer set.
Definition: set.hh:99
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:49
Range iterator for range lists
Shrinking sets of integers.
Definition: var-imp.hpp:243
int ModEvent
Type for modification events.
Definition: core.hpp:62
Base-class for propagators.
Definition: core.hpp:1023
Base-class for advisors.
Definition: core.hpp:1251
Range iterator for the greatest lower bound.
Definition: var-imp.hpp:359
Finite integer set variable implementation.
Definition: var-imp.hpp:430
Range iterator for computing the complement (described by template arguments)
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
Computation spaces.
Definition: core.hpp:1701
Range iterator for the least upper bound.
Definition: var-imp.hpp:317
ModEvent exclude(Space &home, View &x, int s)
Prune view x to exclude all values from s.
Definition: set-op.hpp:137
Gecode::IntSet d(v, 7)
Gecode::FloatVal c(-8, 8)
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
int glbMax(void) const
Return glb maximum.
Definition: delta.hpp:52
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Gecode::IntArgs i({1, 2, 3, 4})
FloatVal intersect(const FloatVal &x, const FloatVal &y)
Definition: val.hpp:503
int PropCond
Type for propagation conditions.
Definition: core.hpp:72
void subscribe(Space &home, Propagator &p, IntSet &y)
Definition: rel.hpp:71
friend class GLBndSet
Definition: var-imp.hpp:55
A complement iterator spezialized for the BndSet limits.
Definition: var-imp.hpp:292
Sets of integers.
Definition: var-imp.hpp:89
unsigned int size(I &i)
Size of all ranges of range iterator i.
Range iterator for integer sets.
Definition: var-imp.hpp:185
unsigned int _size
The size of this set.
Definition: var-imp.hpp:95
unsigned int _card
The cardinality this set represents.
Definition: var-imp.hpp:97
bool glbAny(void) const
Test whether delta represents any domain change in glb.
Definition: delta.hpp:64
Integer sets.
Definition: int.hh:174
friend class LUBndSet
Definition: var-imp.hpp:54
int glbMin(void) const
Return glb minimum.
Definition: delta.hpp:48
Base-class for Set-variable implementations.
Definition: var-imp.hpp:139
int lubMin(void) const
Return lub minimum.
Definition: delta.hpp:56
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:67
Set view for set variables
Definition: view.hpp:56
Generic domain change information to be supplied to advisors.
Definition: core.hpp:203
ModEvent include(Space &home, View &x, int s)
Prune view x to only include values from s.
Definition: set-op.hpp:123
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:43
Growing sets of integers.
Definition: var-imp.hpp:205
int lubMax(void) const
Return lub maximum.
Definition: delta.hpp:60
bool lubAny(void) const
Test whether delta represents any domain change in lub.
Definition: delta.hpp:68
Post propagator for SetVar x
Definition: set.hh:767
Lists of ranges (intervals)
Definition: range-list.hpp:49
Gecode toplevel namespace
Range iterator for computing set difference.
Definition: ranges-diff.hpp:43
void reschedule(Space &home, Propagator &p, IntSet &y)
Definition: rel.hpp:92
SetDelta(void)
Create set delta as providing no information (if any is true)
Definition: delta.hpp:39
void update(IntSet &y, Space &home, IntSet &py)
Definition: rel.hpp:103
struct Gecode::@593::NNF::@62::@64 a
For atomic nodes.
#define GECODE_SET_EXPORT
Definition: set.hh:67
friend class SetVarImp
Definition: var-imp.hpp:53
Finite set delta information for advisors.
Definition: var-imp.hpp:52