Generated on Sat Feb 7 2015 02:01:22 for Gecode by doxygen 1.8.9.1
set.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  * Gabor Szokoli <szokoli@gecode.org>
6  *
7  * Contributing authors:
8  * Christian Schulte <schulte@gecode.org>
9  *
10  * Copyright:
11  * Guido Tack, 2004
12  * Christian Schulte, 2004
13  * Gabor Szokoli, 2004
14  *
15  * Last modified:
16  * $Date: 2010-07-28 17:35:33 +0200 (Wed, 28 Jul 2010) $ by $Author: schulte $
17  * $Revision: 11294 $
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 namespace Gecode { namespace Set {
45 
46  /*
47  * Creation of new variable implementations
48  *
49  */
50 
53  : SetVarImpBase(home), lub(home), glb(home) {
54  lub.card(Limits::card);
55  assert(lub.card()==lub.size());
56  }
57 
59  SetVarImp::SetVarImp(Space& home,int lbMin,int lbMax,int ubMin,int ubMax,
60  unsigned int cardMin, unsigned int cardMax)
61  : SetVarImpBase(home),
62  lub(home,ubMin,ubMax), glb(home,lbMin,lbMax) {
63  glb.card(std::max(cardMin, glb.size() ));
64  lub.card(std::min(cardMax, lub.size() ));
65  }
66 
69  const IntSet& theGlb,int ubMin,int ubMax,
70  unsigned int cardMin, unsigned int cardMax)
71  : SetVarImpBase(home),
72  lub(home,ubMin,ubMax), glb(home,theGlb) {
73  glb.card(std::max(cardMin, glb.size() ));
74  lub.card(std::min(cardMax, lub.size() ));
75  }
76 
79  int lbMin,int lbMax,const IntSet& theLub,
80  unsigned int cardMin, unsigned int cardMax)
81  : SetVarImpBase(home),
82  lub(home,theLub), glb(home,lbMin,lbMax) {
83  glb.card(std::max(cardMin, glb.size() ));
84  lub.card(std::min(cardMax, lub.size() ));
85  }
86 
89  const IntSet& theGlb,const IntSet& theLub,
90  unsigned int cardMin, unsigned int cardMax)
91  : SetVarImpBase(home), lub(home,theLub), glb(home,theGlb) {
92  glb.card(std::max(cardMin, glb.size() ));
93  lub.card(std::min(cardMax, lub.size() ));
94  }
95 
96 
97  forceinline bool
98  SetVarImp::assigned(void) const {
99  return glb.size() == lub.size();
100  }
101 
102  forceinline unsigned int
103  SetVarImp::cardMin(void) const { return glb.card(); }
104 
105  forceinline unsigned int
106  SetVarImp::cardMax(void) const { return lub.card(); }
107 
108  forceinline bool
109  SetVarImp::knownIn(int i) const { return (glb.in(i)); }
110 
111  forceinline bool
112  SetVarImp::knownOut(int i) const { return !(lub.in(i)); }
113 
114  forceinline int
115  SetVarImp::lubMin(void) const { return lub.min(); }
116 
117  forceinline int
118  SetVarImp::lubMax(void) const { return lub.max(); }
119 
120  forceinline int
121  SetVarImp::lubMinN(unsigned int n) const { return lub.minN(n); }
122 
123  forceinline int
124  SetVarImp::glbMin(void) const { return glb.min(); }
125 
126  forceinline int
127  SetVarImp::glbMax(void) const { return glb.max(); }
128 
129  forceinline unsigned int
130  SetVarImp::glbSize() const { return glb.size(); }
131 
132  forceinline unsigned int
133  SetVarImp::lubSize() const { return lub.size(); }
134 
135  /*
136  * Support for delta information
137  *
138  */
139  forceinline int
141  return static_cast<const SetDelta&>(d).glbMin();
142  }
143  forceinline int
145  return static_cast<const SetDelta&>(d).glbMax();
146  }
147  forceinline bool
149  return static_cast<const SetDelta&>(d).glbAny();
150  }
151  forceinline int
153  return static_cast<const SetDelta&>(d).lubMin();
154  }
155  forceinline int
157  return static_cast<const SetDelta&>(d).lubMax();
158  }
159  forceinline bool
161  return static_cast<const SetDelta&>(d).lubAny();
162  }
163 
165  SetVarImp::cardMin(Space& home,unsigned int newMin) {
166  if (cardMin() >= newMin)
167  return ME_SET_NONE;
168  if (newMin > cardMax())
169  return ME_SET_FAILED;
170  glb.card(newMin);
171  return cardMin_full(home);
172  }
173 
175  SetVarImp::cardMax(Space& home,unsigned int newMax) {
176  if (cardMax() <= newMax)
177  return ME_SET_NONE;
178  if (cardMin() > newMax)
179  return ME_SET_FAILED;
180  lub.card(newMax);
181  return cardMax_full(home);
182  }
183 
185  SetVarImp::intersect(Space& home,int i, int j) {
186  BndSetRanges lb(glb);
189  if (probe())
190  return ME_SET_FAILED;
191  if (assigned())
192  return ME_SET_NONE;
193  int oldMin = lub.min();
194  int oldMax = lub.max();
195  if (lub.intersect(home, i, j)) {
196  SetDelta d;
197  if (i == oldMin) {
198  d._lubMin = lub.max()+1;
199  d._lubMax = oldMax;
200  } else if (j == oldMax) {
201  d._lubMin = oldMin;
202  d._lubMax = lub.min()-1;
203  }
204  return processLubChange(home, d);
205  }
206  return ME_SET_NONE;
207  }
208 
211  return intersect(home, i, i);
212  }
213 
214  template<class I>
215  inline ModEvent
216  SetVarImp::intersectI(Space& home, I& iterator) {
217  if (assigned()) {
218  BndSetRanges lbi(glb);
219  Iter::Ranges::Diff<BndSetRanges,I> probe(lbi,iterator);
220  if (probe())
221  return ME_SET_FAILED;
222  return ME_SET_NONE;
223  }
224  if (!iterator()) {
225  if (cardMin() > 0)
226  return ME_SET_FAILED;
227  lub.card(0);
228  SetDelta d(1, 0, lub.min(), lub.max());
229  lub.excludeAll(home);
230  return notify(home, ME_SET_VAL, d);
231  }
232  int mi=iterator.min();
233  int ma=iterator.max();
234  ++iterator;
235  if (iterator())
236  return intersectI_full(home, mi, ma, iterator);
237  else
238  return intersect(home, mi, ma);
239  }
240 
241  template<class I>
242  ModEvent
243  SetVarImp::intersectI_full(Space& home, int mi, int ma, I& iterator) {
244  Iter::Ranges::SingletonAppend<I> si(mi,ma,iterator);
245  if (lub.intersectI(home, si)) {
246  BndSetRanges ub(lub);
247  BndSetRanges lb(glb);
248  if (!Iter::Ranges::subset(lb,ub)) {
249  glb.become(home, lub);
250  glb.card(glb.size());
251  lub.card(glb.size());
252  return ME_SET_FAILED;
253  }
255  if (cardMax() > lub.size()) {
256  lub.card(lub.size());
257  if (cardMin() > cardMax()) {
258  glb.become(home, lub);
259  glb.card(glb.size());
260  lub.card(glb.size());
261  return ME_SET_FAILED;
262  }
263  me = ME_SET_CLUB;
264  }
265  if (cardMax() == lub.size() && cardMin() == cardMax()) {
266  glb.become(home, lub);
267  me = ME_SET_VAL;
268  }
269  SetDelta d;
270  return notify(home, me, d);
271  }
272  return ME_SET_NONE;
273  }
274 
276  SetVarImp::include(Space& home, int i, int j) {
277  if (j<i)
278  return ME_SET_NONE;
279  BndSetRanges ub(lub);
280  Iter::Ranges::Singleton sij(i,j);
281  if (!Iter::Ranges::subset(sij,ub)) {
282  return ME_SET_FAILED;
283  }
284  SetDelta d;
285  if (glb.include(home, i, j, d))
286  return processGlbChange(home, d);
287  return ME_SET_NONE;
288  }
289 
291  SetVarImp::include(Space& home, int i) {
292  return include(home, i, i);
293  }
294 
295  template<class I> forceinline ModEvent
296  SetVarImp::includeI(Space& home, I& iterator) {
297  if (!iterator()) {
298  return ME_SET_NONE;
299  }
300  if (assigned()) {
301  BndSetRanges lbi(glb);
303  probe(iterator,lbi);
304  return probe() ? ME_SET_FAILED : ME_SET_NONE;
305  }
306  int mi=iterator.min();
307  int ma=iterator.max();
308  ++iterator;
309  if (iterator())
310  return includeI_full(home, mi, ma, iterator);
311  else
312  return include(home, mi, ma);
313  }
314 
315  template<class I>
316  ModEvent
317  SetVarImp::includeI_full(Space& home, int mi, int ma, I& iterator) {
318  Iter::Ranges::SingletonAppend<I> si(mi,ma,iterator);
319  if (glb.includeI(home, si)) {
320  BndSetRanges ub(lub);
321  BndSetRanges lb(glb);
322  if (!Iter::Ranges::subset(lb,ub)) {
323  glb.become(home, lub);
324  glb.card(glb.size());
325  lub.card(glb.size());
326  return ME_SET_FAILED;
327  }
328  ModEvent me = ME_SET_GLB;
329  if (cardMin() < glb.size()) {
330  glb.card(glb.size());
331  if (cardMin() > cardMax()) {
332  glb.become(home, lub);
333  glb.card(glb.size());
334  lub.card(glb.size());
335  return ME_SET_FAILED;
336  }
337  me = ME_SET_CGLB;
338  }
339  if (cardMin() == glb.size() && cardMin() == cardMax()) {
340  lub.become(home, glb);
341  me = ME_SET_VAL;
342  }
343  SetDelta d;
344  return notify(home, me, d);
345  }
346  return ME_SET_NONE;
347  }
348 
350  SetVarImp::exclude(Space& home, int i, int j) {
351  if (j<i)
352  return ME_SET_NONE;
353  Iter::Ranges::Singleton sij(i,j);
354  BndSetRanges lb(glb);
356  if (probe())
357  return ME_SET_FAILED;
358  SetDelta d;
359  if (lub.exclude(home, i, j, d))
360  return processLubChange(home, d);
361  return ME_SET_NONE;
362  }
363 
365  SetVarImp::exclude(Space& home, int i) {
366  return exclude(home, i, i);
367  }
368 
369  template<class I>
370  inline ModEvent
371  SetVarImp::excludeI(Space& home, I& iterator) {
372  if (!iterator())
373  return ME_SET_NONE;
374  if (assigned()) {
375  BndSetRanges ubi(lub);
376  Iter::Ranges::Inter<BndSetRanges,I> probe(ubi,iterator);
377  return probe() ? ME_SET_FAILED : ME_SET_NONE;
378  }
379  int mi=iterator.min();
380  int ma=iterator.max();
381  ++iterator;
382  if (iterator())
383  return excludeI_full(home, mi, ma, iterator);
384  else
385  return exclude(home, mi, ma);
386  }
387 
388  template<class I>
389  ModEvent
390  SetVarImp::excludeI_full(Space& home, int mi, int ma, I& iterator) {
391  Iter::Ranges::SingletonAppend<I> si(mi,ma,iterator);
392  if (lub.excludeI(home, si)) {
393  BndSetRanges ub(lub);
394  BndSetRanges lb(glb);
395  if (!Iter::Ranges::subset(lb,ub)) {
396  glb.become(home, lub);
397  glb.card(glb.size());
398  lub.card(glb.size());
399  return ME_SET_FAILED;
400  }
401  ModEvent me = ME_SET_LUB;
402  if (cardMax() > lub.size()) {
403  lub.card(lub.size());
404  if (cardMin() > cardMax()) {
405  glb.become(home, lub);
406  glb.card(glb.size());
407  lub.card(glb.size());
408  return ME_SET_FAILED;
409  }
410  me = ME_SET_CLUB;
411  }
412  if (cardMax() == lub.size() && cardMin() == cardMax()) {
413  glb.become(home, lub);
414  me = ME_SET_VAL;
415  }
416  SetDelta d;
417  return notify(home, me, d);
418  }
419  return ME_SET_NONE;
420  }
421 
422  /*
423  * Copying a variable
424  *
425  */
426 
427  forceinline SetVarImp*
428  SetVarImp::copy(Space& home, bool share) {
429  return copied() ?
430  static_cast<SetVarImp*>(forward()) :
431  perform_copy(home,share);
432  }
433 
434  /*
435  * Iterator specializations
436  *
437  */
438 
447  template<>
448  class LubRanges<SetVarImp*> : public BndSetRanges {
449  public:
451 
452  LubRanges(void);
455  LubRanges(const SetVarImp*);
457  void init(const SetVarImp*);
459  };
460 
463 
466  : BndSetRanges(x->lub) {}
467 
468  forceinline void
470  BndSetRanges::init(x->lub);
471  }
472 
481  template<>
482  class GlbRanges<SetVarImp*> : public BndSetRanges {
483  public:
485 
486  GlbRanges(void);
489  GlbRanges(const SetVarImp* x);
491  void init(const SetVarImp*);
493  };
494 
497 
500  : BndSetRanges(x->glb) {}
501 
502  forceinline void
504  BndSetRanges::init(x->glb);
505  }
506 
507 
508  /*
509  * Dependencies
510  *
511  */
512  forceinline void
513  SetVarImp::subscribe(Space& home, Propagator& p, PropCond pc, bool schedule) {
514  SetVarImpBase::subscribe(home,p,pc,assigned(),schedule);
515  }
516  forceinline void
518  SetVarImpBase::cancel(home,p,pc,assigned());
519  }
520  forceinline void
523  }
524  forceinline void
527  }
528 
529 }}
530 
531 // 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
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to variable.
Definition: set.hpp:513
const Gecode::ModEvent ME_SET_FAILED
Domain operation has resulted in failure.
Definition: var-type.hpp:138
const SetInstr * si[]
Definition: mm-set.cpp:4340
ModEvent exclude(Space &home, int n)
Exclude n from the least upper bound.
Definition: set.hpp:365
const Gecode::ModEvent ME_SET_LUB
Domain operation has changed the least upper bound.
Definition: var-type.hpp:156
Range iterator for singleton range.
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
const FloatNum max
Largest allowed float value.
Definition: float.hh:831
SetVarImp(Space &home, bool share, SetVarImp &x)
Constructor for cloning x.
Definition: set.cpp:121
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
int ModEvent
Type for modification events.
Definition: core.hpp:146
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
Finite integer set variable implementation.
Definition: var-imp.hpp:434
unsigned int card(void) const
Return cardinality.
Definition: integerset.hpp:134
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
Range iterator for appending a singleton with a range iterator
Computation spaces.
Definition: core.hpp:1362
Range iterator for the least upper bound.
Definition: var-imp.hpp:321
void subscribe(Gecode::Space &home, Gecode::Propagator &p, Gecode::PropCond pc, bool assigned, bool schedule)
Subscribe propagator p with propagation condition pc.
Definition: var-imp.hpp:285
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
void cancel(Space &home)
Cancel all subscriptions when variable implementation is assigned.
Gecode::IntSet d(v, 7)
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 p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
const FloatNum min
Smallest allowed float value.
Definition: float.hh:833
Gecode::IntArgs i(4, 1, 2, 3, 4)
bool copied(void) const
Is variable already copied.
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
static bool glbAny(const Delta &d)
Test whether arbitrary values got pruned from glb.
Definition: set.hpp:148
static ModEvent me(const ModEventDelta &med)
Project modification event for this variable type from med.
unsigned int cardMin(void) const
Return current cardinality minimum.
Definition: set.hpp:103
Range iterator for computing intersection (binary)
ModEvent includeI(Space &home, I &i)
Include set described by i in the greatest lower bound.
Definition: set.hpp:296
const Gecode::ModEvent ME_SET_CGLB
Domain operation has changed the greatest lower bound and the cardinality.
Definition: var-type.hpp:186
int PropCond
Type for propagation conditions.
Definition: core.hpp:156
bool intersectI(Space &home, I &i)
Exclude all elements not in the set represented by i from this set.
Definition: integerset.hpp:374
Range iterator for integer sets.
Definition: var-imp.hpp:189
void init(const BndSet &s)
Initialize with BndSet s.
Definition: integerset.hpp:251
Integer sets.
Definition: int.hh:171
const Gecode::ModEvent ME_SET_GLB
Domain operation has changed the greatest lower bound.
Definition: var-type.hpp:164
bool knownOut(int) const
Test whether n is not contained in least upper bound.
Definition: set.hpp:112
const Gecode::ModEvent ME_SET_NONE
Domain operation has not changed domain.
Definition: var-type.hpp:140
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
Base-class for Set-variable implementations.
Definition: var-imp.hpp:117
ModEvent intersectI(Space &home, I &i)
Exclude everything but set described by i from the least upper bound.
Definition: set.hpp:216
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
const Gecode::ModEvent ME_SET_CLUB
Domain operation has changed the least upper bound and the cardinality.
Definition: var-type.hpp:179
GlbRanges(void)
Default constructor.
int min(void) const
Return smallest element.
Definition: integerset.hpp:107
#define forceinline
Definition: config.hpp:132
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
Gecode::ModEvent notify(Gecode::Space &home, Gecode::ModEvent me, Gecode::Delta &d)
Notify that variable implementation has been modified with modification event me and delta informatio...
Definition: var-imp.hpp:294
unsigned int glbSize(void) const
Return the size of the greatest lower bound.
Definition: set.hpp:130
bool subset(I &i, J &j)
Check whether range iterator i is subset of range iterator j.
Gecode toplevel namespace
Range iterator for computing set difference.
Definition: ranges-diff.hpp:47
LubRanges(void)
Default constructor.
const Gecode::ModEvent ME_SET_VAL
Domain operation has resulted in a value (assigned variable)
Definition: var-type.hpp:142
bool assigned(void) const
Test whether variable is assigned.
Definition: set.hpp:98
int max(void) const
Return greatest element.
Definition: integerset.hpp:115
struct Gecode::@518::NNF::@57::@59 a
For atomic nodes.
void init(const T &x)
Initialize with greatest lower bound ranges for set variable x.
VarImp * forward(void) const
Use forward pointer if variable already copied.
bool include(Space &home, int i, int j, SetDelta &d)
Include the set in this set.
Definition: integerset.hpp:283
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