Generated on Thu Mar 16 2017 03:24:17 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  * Last modified:
16  * $Date: 2016-06-29 17:28:17 +0200 (Wed, 29 Jun 2016) $ by $Author: schulte $
17  * $Revision: 15137 $
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 reschedule(Space& home, Propagator& p, PropCond pc);
596  void subscribe(Space& home, Advisor& a);
598  void cancel(Space& home, Advisor& a);
600 
601  private:
603  GECODE_SET_EXPORT SetVarImp* perform_copy(Space& home, bool share);
604 
605  public:
607 
608  SetVarImp* copy(Space& home, bool share);
611 
613 
614  static int glbMin(const Delta& d);
617  static int glbMax(const Delta& d);
619  static bool glbAny(const Delta& d);
621  static int lubMin(const Delta& d);
623  static int lubMax(const Delta& d);
625  static bool lubAny(const Delta& d);
627 
628  };
629 
630  class SetView;
631 
632 }}
633 
635 
636 // STATISTICS: set-var
Range iterator for the unknown set.
Definition: var-imp.hpp:406
const int min
Smallest allowed integer in integer set.
Definition: set.hh:101
void cancel(Space &home, Propagator &p, IntSet &y)
Definition: rel.hpp:85
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:57
Range iterator for range lists
Shrinking sets of integers.
Definition: var-imp.hpp:247
int ModEvent
Type for modification events.
Definition: core.hpp:142
Base-class for propagators.
Definition: core.hpp:1012
Base-class for advisors.
Definition: core.hpp:1212
Range iterator for the greatest lower bound.
Definition: var-imp.hpp:363
Finite integer set variable implementation.
Definition: var-imp.hpp:434
Range iterator for computing the complement (described by template arguments)
const unsigned int card
Maximum cardinality of an integer set.
Definition: set.hh:103
const int max
Largest allowed integer in integer set.
Definition: set.hh:99
Computation spaces.
Definition: core.hpp:1672
Range iterator for the least upper bound.
Definition: var-imp.hpp:321
ModEvent exclude(Space &home, View &x, int s)
Prune view x to exclude all values from s.
Definition: set-op.hpp:141
Gecode::IntSet d(v, 7)
Gecode::FloatVal c(-8, 8)
struct Gecode::@554::NNF::@60::@62 a
For atomic nodes.
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
int glbMax(void) const
Return glb maximum.
Definition: delta.hpp:56
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
FloatVal intersect(const FloatVal &x, const FloatVal &y)
Definition: val.hpp:507
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
int PropCond
Type for propagation conditions.
Definition: core.hpp:152
void subscribe(Space &home, Propagator &p, IntSet &y)
Definition: rel.hpp:75
friend class GLBndSet
Definition: var-imp.hpp:59
A complement iterator spezialized for the BndSet limits.
Definition: var-imp.hpp:296
Sets of integers.
Definition: var-imp.hpp:93
unsigned int size(I &i)
Size of all ranges of range iterator i.
Range iterator for integer sets.
Definition: var-imp.hpp:189
unsigned int _size
The size of this set.
Definition: var-imp.hpp:99
unsigned int _card
The cardinality this set represents.
Definition: var-imp.hpp:101
bool glbAny(void) const
Test whether delta represents any domain change in glb.
Definition: delta.hpp:68
Integer sets.
Definition: int.hh:172
friend class LUBndSet
Definition: var-imp.hpp:58
int glbMin(void) const
Return glb minimum.
Definition: delta.hpp:52
Base-class for Set-variable implementations.
Definition: var-imp.hpp:139
int lubMin(void) const
Return lub minimum.
Definition: delta.hpp:60
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:75
Set view for set variables
Definition: view.hpp:60
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:277
ModEvent include(Space &home, View &x, int s)
Prune view x to only include values from s.
Definition: set-op.hpp:127
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:47
Growing sets of integers.
Definition: var-imp.hpp:209
int lubMax(void) const
Return lub maximum.
Definition: delta.hpp:64
bool lubAny(void) const
Test whether delta represents any domain change in lub.
Definition: delta.hpp:72
Lists of ranges (intervals)
Definition: range-list.hpp:53
Gecode toplevel namespace
Range iterator for computing set difference.
Definition: ranges-diff.hpp:47
void reschedule(Space &home, Propagator &p, IntSet &y)
Definition: rel.hpp:96
SetDelta(void)
Create set delta as providing no information (if any is true)
Definition: delta.hpp:43
#define GECODE_SET_EXPORT
Definition: set.hh:69
friend class SetVarImp
Definition: var-imp.hpp:57
Finite set delta information for advisors.
Definition: var-imp.hpp:56