Generated on Fri Jan 28 2022 04:43:06 for Gecode by doxygen 1.8.13
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  * 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 namespace Gecode { namespace Set {
41 
42  /*
43  * Creation of new variable implementations
44  *
45  */
46 
49  : SetVarImpBase(home), lub(home), glb(home) {
50  lub.card(Limits::card);
51  assert(lub.card()==lub.size());
52  }
53 
55  SetVarImp::SetVarImp(Space& home,int lbMin,int lbMax,int ubMin,int ubMax,
56  unsigned int cardMin, unsigned int cardMax)
57  : SetVarImpBase(home),
58  lub(home,ubMin,ubMax), glb(home,lbMin,lbMax) {
59  glb.card(std::max(cardMin, glb.size() ));
60  lub.card(std::min(cardMax, lub.size() ));
61  }
62 
65  const IntSet& theGlb,int ubMin,int ubMax,
66  unsigned int cardMin, unsigned int cardMax)
67  : SetVarImpBase(home),
68  lub(home,ubMin,ubMax), glb(home,theGlb) {
69  glb.card(std::max(cardMin, glb.size() ));
70  lub.card(std::min(cardMax, lub.size() ));
71  }
72 
75  int lbMin,int lbMax,const IntSet& theLub,
76  unsigned int cardMin, unsigned int cardMax)
77  : SetVarImpBase(home),
78  lub(home,theLub), glb(home,lbMin,lbMax) {
79  glb.card(std::max(cardMin, glb.size() ));
80  lub.card(std::min(cardMax, lub.size() ));
81  }
82 
85  const IntSet& theGlb,const IntSet& theLub,
86  unsigned int cardMin, unsigned int cardMax)
87  : SetVarImpBase(home), lub(home,theLub), glb(home,theGlb) {
88  glb.card(std::max(cardMin, glb.size() ));
89  lub.card(std::min(cardMax, lub.size() ));
90  }
91 
92 
93  forceinline bool
94  SetVarImp::assigned(void) const {
95  return glb.size() == lub.size();
96  }
97 
98  forceinline unsigned int
99  SetVarImp::cardMin(void) const { return glb.card(); }
100 
101  forceinline unsigned int
102  SetVarImp::cardMax(void) const { return lub.card(); }
103 
104  forceinline bool
105  SetVarImp::knownIn(int i) const { return (glb.in(i)); }
106 
107  forceinline bool
108  SetVarImp::knownOut(int i) const { return !(lub.in(i)); }
109 
110  forceinline int
111  SetVarImp::lubMin(void) const { return lub.min(); }
112 
113  forceinline int
114  SetVarImp::lubMax(void) const { return lub.max(); }
115 
116  forceinline int
117  SetVarImp::lubMinN(unsigned int n) const { return lub.minN(n); }
118 
119  forceinline int
120  SetVarImp::glbMin(void) const { return glb.min(); }
121 
122  forceinline int
123  SetVarImp::glbMax(void) const { return glb.max(); }
124 
125  forceinline unsigned int
126  SetVarImp::glbSize() const { return glb.size(); }
127 
128  forceinline unsigned int
129  SetVarImp::lubSize() const { return lub.size(); }
130 
131  /*
132  * Support for delta information
133  *
134  */
135  forceinline int
137  return static_cast<const SetDelta&>(d).glbMin();
138  }
139  forceinline int
141  return static_cast<const SetDelta&>(d).glbMax();
142  }
143  forceinline bool
145  return static_cast<const SetDelta&>(d).glbAny();
146  }
147  forceinline int
149  return static_cast<const SetDelta&>(d).lubMin();
150  }
151  forceinline int
153  return static_cast<const SetDelta&>(d).lubMax();
154  }
155  forceinline bool
157  return static_cast<const SetDelta&>(d).lubAny();
158  }
159 
161  SetVarImp::cardMin(Space& home,unsigned int newMin) {
162  if (cardMin() >= newMin)
163  return ME_SET_NONE;
164  if (newMin > cardMax())
165  return fail(home);
166  glb.card(newMin);
167  return cardMin_full(home);
168  }
169 
171  SetVarImp::cardMax(Space& home,unsigned int newMax) {
172  if (cardMax() <= newMax)
173  return ME_SET_NONE;
174  if (cardMin() > newMax)
175  return fail(home);
176  lub.card(newMax);
177  return cardMax_full(home);
178  }
179 
181  SetVarImp::intersect(Space& home,int i, int j) {
182  BndSetRanges lb(glb);
185  if (probe())
186  return fail(home);
187  if (assigned())
188  return ME_SET_NONE;
189  int oldMin = lub.min();
190  int oldMax = lub.max();
191  if (lub.intersect(home, i, j)) {
192  SetDelta d;
193  if (i == oldMin) {
194  d._lubMin = lub.max()+1;
195  d._lubMax = oldMax;
196  } else if (j == oldMax) {
197  d._lubMin = oldMin;
198  d._lubMax = lub.min()-1;
199  }
200  return processLubChange(home, d);
201  }
202  return ME_SET_NONE;
203  }
204 
207  return intersect(home, i, i);
208  }
209 
210  template<class I>
211  inline ModEvent
212  SetVarImp::intersectI(Space& home, I& iterator) {
213  if (assigned()) {
214  BndSetRanges lbi(glb);
215  Iter::Ranges::Diff<BndSetRanges,I> probe(lbi,iterator);
216  if (probe())
217  return fail(home);
218  return ME_SET_NONE;
219  }
220  if (!iterator()) {
221  if (cardMin() > 0)
222  return fail(home);
223  lub.card(0);
224  SetDelta d(1, 0, lub.min(), lub.max());
225  lub.excludeAll(home);
226  return notify(home, ME_SET_VAL, d);
227  }
228  int mi=iterator.min();
229  int ma=iterator.max();
230  ++iterator;
231  if (iterator())
232  return intersectI_full(home, mi, ma, iterator);
233  else
234  return intersect(home, mi, ma);
235  }
236 
237  template<class I>
238  ModEvent
239  SetVarImp::intersectI_full(Space& home, int mi, int ma, I& iterator) {
240  Iter::Ranges::SingletonAppend<I> si(mi,ma,iterator);
241  if (lub.intersectI(home, si)) {
242  BndSetRanges ub(lub);
243  BndSetRanges lb(glb);
244  if (!Iter::Ranges::subset(lb,ub)) {
245  glb.become(home, lub);
246  glb.card(glb.size());
247  lub.card(glb.size());
248  return fail(home);
249  }
251  if (cardMax() > lub.size()) {
252  lub.card(lub.size());
253  if (cardMin() > cardMax()) {
254  glb.become(home, lub);
255  glb.card(glb.size());
256  lub.card(glb.size());
257  return fail(home);
258  }
259  me = ME_SET_CLUB;
260  }
261  if (cardMax() == lub.size() && cardMin() == cardMax()) {
262  glb.become(home, lub);
263  me = ME_SET_VAL;
264  }
265  SetDelta d;
266  return notify(home, me, d);
267  }
268  return ME_SET_NONE;
269  }
270 
272  SetVarImp::include(Space& home, int i, int j) {
273  if (j<i)
274  return ME_SET_NONE;
275  BndSetRanges ub(lub);
276  Iter::Ranges::Singleton sij(i,j);
277  if (!Iter::Ranges::subset(sij,ub)) {
278  return fail(home);
279  }
280  SetDelta d;
281  if (glb.include(home, i, j, d))
282  return processGlbChange(home, d);
283  return ME_SET_NONE;
284  }
285 
287  SetVarImp::include(Space& home, int i) {
288  return include(home, i, i);
289  }
290 
291  template<class I> forceinline ModEvent
292  SetVarImp::includeI(Space& home, I& iterator) {
293  if (!iterator()) {
294  return ME_SET_NONE;
295  }
296  if (assigned()) {
297  BndSetRanges lbi(glb);
299  probe(iterator,lbi);
300  return probe() ? fail(home) : ME_SET_NONE;
301  }
302  int mi=iterator.min();
303  int ma=iterator.max();
304  ++iterator;
305  if (iterator())
306  return includeI_full(home, mi, ma, iterator);
307  else
308  return include(home, mi, ma);
309  }
310 
311  template<class I>
312  ModEvent
313  SetVarImp::includeI_full(Space& home, int mi, int ma, I& iterator) {
314  Iter::Ranges::SingletonAppend<I> si(mi,ma,iterator);
315  if (glb.includeI(home, si)) {
316  BndSetRanges ub(lub);
317  BndSetRanges lb(glb);
318  if (!Iter::Ranges::subset(lb,ub)) {
319  glb.become(home, lub);
320  glb.card(glb.size());
321  lub.card(glb.size());
322  return fail(home);
323  }
325  if (cardMin() < glb.size()) {
326  glb.card(glb.size());
327  if (cardMin() > cardMax()) {
328  glb.become(home, lub);
329  glb.card(glb.size());
330  lub.card(glb.size());
331  return fail(home);
332  }
333  me = ME_SET_CGLB;
334  }
335  if (cardMin() == glb.size() && cardMin() == cardMax()) {
336  lub.become(home, glb);
337  me = ME_SET_VAL;
338  }
339  SetDelta d;
340  return notify(home, me, d);
341  }
342  return ME_SET_NONE;
343  }
344 
346  SetVarImp::exclude(Space& home, int i, int j) {
347  if (j<i)
348  return ME_SET_NONE;
349  Iter::Ranges::Singleton sij(i,j);
350  BndSetRanges lb(glb);
352  if (probe())
353  return fail(home);
354  SetDelta d;
355  if (lub.exclude(home, i, j, d))
356  return processLubChange(home, d);
357  return ME_SET_NONE;
358  }
359 
361  SetVarImp::exclude(Space& home, int i) {
362  return exclude(home, i, i);
363  }
364 
365  template<class I>
366  inline ModEvent
367  SetVarImp::excludeI(Space& home, I& iterator) {
368  if (!iterator())
369  return ME_SET_NONE;
370  if (assigned()) {
371  BndSetRanges ubi(lub);
372  Iter::Ranges::Inter<BndSetRanges,I> probe(ubi,iterator);
373  return probe() ? fail(home) : ME_SET_NONE;
374  }
375  int mi=iterator.min();
376  int ma=iterator.max();
377  ++iterator;
378  if (iterator())
379  return excludeI_full(home, mi, ma, iterator);
380  else
381  return exclude(home, mi, ma);
382  }
383 
384  template<class I>
385  ModEvent
386  SetVarImp::excludeI_full(Space& home, int mi, int ma, I& iterator) {
387  Iter::Ranges::SingletonAppend<I> si(mi,ma,iterator);
388  if (lub.excludeI(home, si)) {
389  BndSetRanges ub(lub);
390  BndSetRanges lb(glb);
391  if (!Iter::Ranges::subset(lb,ub)) {
392  glb.become(home, lub);
393  glb.card(glb.size());
394  lub.card(glb.size());
395  return fail(home);
396  }
398  if (cardMax() > lub.size()) {
399  lub.card(lub.size());
400  if (cardMin() > cardMax()) {
401  glb.become(home, lub);
402  glb.card(glb.size());
403  lub.card(glb.size());
404  return fail(home);
405  }
406  me = ME_SET_CLUB;
407  }
408  if (cardMax() == lub.size() && cardMin() == cardMax()) {
409  glb.become(home, lub);
410  me = ME_SET_VAL;
411  }
412  SetDelta d;
413  return notify(home, me, d);
414  }
415  return ME_SET_NONE;
416  }
417 
418  /*
419  * Copying a variable
420  *
421  */
422 
425  return copied() ?
426  static_cast<SetVarImp*>(forward()) :
427  perform_copy(home);
428  }
429 
430  /*
431  * Iterator specializations
432  *
433  */
434 
443  template<>
444  class LubRanges<SetVarImp*> : public BndSetRanges {
445  public:
447 
448  LubRanges(void);
451  LubRanges(const SetVarImp*);
453  void init(const SetVarImp*);
455  };
456 
459 
462  : BndSetRanges(x->lub) {}
463 
464  forceinline void
466  BndSetRanges::init(x->lub);
467  }
468 
477  template<>
478  class GlbRanges<SetVarImp*> : public BndSetRanges {
479  public:
481 
482  GlbRanges(void);
485  GlbRanges(const SetVarImp* x);
487  void init(const SetVarImp*);
489  };
490 
493 
496  : BndSetRanges(x->glb) {}
497 
498  forceinline void
500  BndSetRanges::init(x->glb);
501  }
502 
503 }}
504 
505 // STATISTICS: set-var
static bool lubAny(const Delta &d)
Test whether arbitrary values got pruned from lub.
Definition: set.hpp:156
int lubMax(void) const
Return maximum of the least upper bound.
Definition: set.hpp:114
bool excludeI(Space &home, I &i)
Exclude all elements in the set represented by i from this set.
Definition: integerset.hpp:385
unsigned int cardMin(void) const
Return current cardinality minimum.
Definition: set.hpp:99
const SetInstr * si[]
Definition: mm-set.cpp:4341
ModEvent exclude(Space &home, int n)
Exclude n from the least upper bound.
Definition: set.hpp:361
VarImp * forward(void) const
Use forward pointer if variable already copied.
Definition: core.hpp:4155
const Gecode::ModEvent ME_SET_LUB
Domain operation has changed the least upper bound.
Definition: var-type.hpp:156
Range iterator for singleton range.
const FloatNum max
Largest allowed float value.
Definition: float.hh:844
int max(void) const
Return greatest element.
Definition: integerset.hpp:111
bool assigned(void) const
Test whether variable is assigned.
Definition: set.hpp:94
ModEvent excludeI(Space &home, I &i)
Exclude set described by i from the least upper bound.
Definition: set.hpp:367
bool knownOut(int) const
Test whether n is not contained in least upper bound.
Definition: set.hpp:108
int ModEvent
Type for modification events.
Definition: core.hpp:62
Range iterator for the greatest lower bound.
Definition: var-imp.hpp:359
int minN(unsigned int n) const
Return n -th smallest element.
Definition: integerset.hpp:120
Finite integer set variable implementation.
Definition: var-imp.hpp:430
bool in(int i) const
Test whether i is an element of this set.
Definition: integerset.hpp:224
#define forceinline
Definition: config.hpp:185
const unsigned int card
Maximum cardinality of an integer set.
Definition: set.hh:101
ModEvent intersect(Space &home, int n)
Exclude everything but n from the least upper bound.
Definition: set.hpp:206
Range iterator for appending a singleton with a range iterator
int lubMinN(unsigned int n) const
Return n -th smallest element in the least upper bound.
Definition: set.hpp:117
Computation spaces.
Definition: core.hpp:1701
Range iterator for the least upper bound.
Definition: var-imp.hpp:317
Gecode::IntSet d(v, 7)
const FloatNum min
Smallest allowed float value.
Definition: float.hh:846
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
unsigned int size(void) const
Return size.
Definition: integerset.hpp:93
void become(Space &home, const BndSet &s)
Make this set equal to s.
Definition: integerset.hpp:211
static bool glbAny(const Delta &d)
Test whether arbitrary values got pruned from glb.
Definition: set.hpp:144
Gecode::IntArgs i({1, 2, 3, 4})
static ModEvent me(const ModEventDelta &med)
Project modification event for this variable type from med.
Definition: core.hpp:4197
bool copied(void) const
Is variable already copied.
Definition: core.hpp:4149
unsigned int cardMax(void) const
Return current cardinality maximum.
Definition: set.hpp:102
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:292
const Gecode::ModEvent ME_SET_CGLB
Domain operation has changed the greatest lower bound and the cardinality.
Definition: var-type.hpp:186
bool intersectI(Space &home, I &i)
Exclude all elements not in the set represented by i from this set.
Definition: integerset.hpp:370
Range iterator for integer sets.
Definition: var-imp.hpp:185
void init(const BndSet &s)
Initialize with BndSet s.
Definition: integerset.hpp:247
unsigned int glbSize(void) const
Return the size of the greatest lower bound.
Definition: set.hpp:126
Integer sets.
Definition: int.hh:174
const Gecode::ModEvent ME_SET_GLB
Domain operation has changed the greatest lower bound.
Definition: var-type.hpp:164
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:287
bool exclude(Space &home, int i, int j, SetDelta &d)
Exclude the set from this set.
Definition: integerset.hpp:339
bool includeI(Space &home, I &i)
Include the set represented by i in this set.
Definition: integerset.hpp:296
int lubMin(void) const
Return minimum of the least upper bound.
Definition: set.hpp:111
Base-class for Set-variable implementations.
Definition: var-imp.hpp:139
ModEvent intersectI(Space &home, I &i)
Exclude everything but set described by i from the least upper bound.
Definition: set.hpp:212
bool intersect(Space &home, int i, int j)
Intersect this set with the set .
Definition: integerset.hpp:355
SetVarImp * copy(Space &home)
Return copy of this variable.
Definition: set.hpp:424
unsigned int lubSize(void) const
Return the size of the least upper bound.
Definition: set.hpp:129
Generic domain change information to be supplied to advisors.
Definition: core.hpp:203
int glbMin(void) const
Return minimum of the greatest lower bound.
Definition: set.hpp:120
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.
Definition: set.hpp:492
void init(const T &x)
Initialize with least upper bound ranges for set variable x.
Definition: set.hpp:465
int glbMax(void) const
Return maximum of the greatest lower bound.
Definition: set.hpp:123
bool knownIn(int n) const
Test whether n is contained in greatest lower bound.
Definition: set.hpp:105
ModEvent fail(Space &home)
Run advisors to be run on failure and returns ME_GEN_FAILED.
Definition: core.hpp:4497
Post propagator for SetVar x
Definition: set.hh:767
SetVarImp(Space &home, SetVarImp &x)
Constructor for cloning x.
Definition: set.cpp:117
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:365
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:43
LubRanges(void)
Default constructor.
Definition: set.hpp:458
const Gecode::ModEvent ME_SET_VAL
Domain operation has resulted in a value (assigned variable)
Definition: var-type.hpp:142
unsigned int card(void) const
Return cardinality.
Definition: integerset.hpp:130
int min(void) const
Return smallest element.
Definition: integerset.hpp:103
void init(const T &x)
Initialize with greatest lower bound ranges for set variable x.
Definition: set.hpp:499
bool include(Space &home, int i, int j, SetDelta &d)
Include the set in this set.
Definition: integerset.hpp:279
void excludeAll(Space &home)
Exclude all elements from this set.
Definition: integerset.hpp:395
Finite set delta information for advisors.
Definition: var-imp.hpp:52