Generated on Thu Jan 20 2022 00:00:00 for Gecode by doxygen 1.9.1
union.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  * Christian Schulte <schulte@gecode.org>
6  *
7  * Copyright:
8  * Guido Tack, 2004,2006
9  * Christian Schulte, 2004
10  *
11  * This file is part of Gecode, the generic constraint
12  * development environment:
13  * http://www.gecode.org
14  *
15  * Permission is hereby granted, free of charge, to any person obtaining
16  * a copy of this software and associated documentation files (the
17  * "Software"), to deal in the Software without restriction, including
18  * without limitation the rights to use, copy, modify, merge, publish,
19  * distribute, sublicense, and/or sell copies of the Software, and to
20  * permit persons to whom the Software is furnished to do so, subject to
21  * the following conditions:
22  *
23  * The above copyright notice and this permission notice shall be
24  * included in all copies or substantial portions of the Software.
25  *
26  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
27  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
28  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
29  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
30  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
31  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
32  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
33  *
34  */
35 
36 namespace Gecode { namespace Set { namespace Element {
37 
38  template<class View, class View0, class View1>
41  ElementUnion(Home home, IdxViewArray& iv0, View0 y0, View1 y1)
42  : Propagator(home), iv(iv0), x0(y0), x1(y1) {
43  home.notice(*this,AP_DISPOSE);
44  x0.subscribe(home,*this, PC_SET_ANY);
45  x1.subscribe(home,*this, PC_SET_ANY);
46  iv.subscribe(home,*this, PC_SET_ANY);
47  }
48 
49  template<class View, class View0, class View1>
53  : Propagator(home,p) {
54  x0.update(home,p.x0);
55  x1.update(home,p.x1);
56  iv.update(home,p.iv);
57  }
58 
59  template<class View, class View0, class View1>
60  PropCost
62  const ModEventDelta&) const {
63  return PropCost::linear(PropCost::HI, iv.size()+2);
64  }
65 
66  template<class View, class View0, class View1>
67  void
69  x0.reschedule(home,*this, PC_SET_ANY);
70  x1.reschedule(home,*this, PC_SET_ANY);
71  iv.reschedule(home,*this, PC_SET_ANY);
72  }
73 
74  template<class View, class View0, class View1>
75  forceinline size_t
77  home.ignore(*this,AP_DISPOSE);
78  if (!home.failed()) {
79  x0.cancel(home,*this,PC_SET_ANY);
80  x1.cancel(home,*this,PC_SET_ANY);
81  iv.cancel(home,*this,PC_SET_ANY);
82  }
83  (void) Propagator::dispose(home);
84  return sizeof(*this);
85  }
86 
87  template<class View, class View0, class View1>
90  post(Home home, IdxViewArray& xs, View0 x0, View1 x1) {
91  int n = xs.size();
92 
93  // x0 \subseteq {1,...,n}
94  Iter::Ranges::Singleton s(0, n-1);
95  GECODE_ME_CHECK(x0.intersectI(home,s));
96  (void) new (home)
97  ElementUnion<View,View0,View1>(home,xs,x0,x1);
98  return ES_OK;
99  }
100 
101  template<class View, class View0, class View1>
102  Actor*
104  return new (home) ElementUnion<View,View0,View1>(home,*this);
105  }
106 
107  template<class View, class View0, class View1>
108  ExecStatus
110  Region r;
111  int n = iv.size();
112 
113  bool loopVar;
114  do {
115  loopVar = false;
116 
117  // Cache the upper bound iterator, as we have to
118  // modify the upper bound while iterating
119  LubRanges<View0> x0ub(x0);
120  Iter::Ranges::Cache x0ubc(r,x0ub);
122 
123  GlbRanges<View0> x0lb(x0);
124  Iter::Ranges::Cache x0lbc(r,x0lb);
126 
127  // In the first iteration, compute in before[i] the union
128  // of all the upper bounds of the x_i. At the same time,
129  // exclude inconsistent x_i from x0 and remove them from
130  // the list, cancel their dependencies.
131 
132  GLBndSet sofarBefore(home);
133  LUBndSet selectedInter(home, IntSet (Limits::min,
134  Limits::max));
135  GLBndSet* before =
136  static_cast<GLBndSet*>(r.ralloc(sizeof(GLBndSet)*n));
137 
138  int j = 0;
139  int i = 0;
140 
141  unsigned int maxCard = 0;
142  unsigned int minCard = Limits::card;
143 
144  while ( vx0ub() ) {
145 
146  // Remove vars at indices not in the upper bound
147  if (iv[i].idx < vx0ub.val()) {
148  iv[i].view.cancel(home,*this, PC_SET_ANY);
149  ++i;
150  continue;
151  }
152  assert(iv[i].idx == vx0ub.val());
153  iv[j] = iv[i];
154 
155  View candidate = iv[j].view;
156  int candidateInd = iv[j].idx;
157 
158  // inter = glb(candidate) & complement(lub(x1))
159  GlbRanges<View> candlb(candidate);
160  LubRanges<View1> x1ub(x1);
162  diff(candlb, x1ub);
163 
164  bool selectSingleInconsistent = false;
165  if (x0.cardMax() <= 1) {
166  GlbRanges<View1> x1lb(x1);
167  LubRanges<View> candub(candidate);
169  LubRanges<View> > diff2(x1lb, candub);
170  selectSingleInconsistent =
171  diff2() || candidate.cardMax() < x1.cardMin();
172  }
173 
174  // exclude inconsistent x_i
175  // an x_i is inconsistent if
176  // * at most one x_i can be selected and there are
177  // elements in x_0 that can't be in x_i
178  // (selectSingleInconsistent)
179  // * its min cardinality is greater than maxCard of x1
180  // * inter is not empty (there are elements in x_i
181  // that can't be in x_0)
182  if (selectSingleInconsistent ||
183  candidate.cardMin() > x1.cardMax() ||
184  diff()) {
185  ModEvent me = (x0.exclude(home,candidateInd));
186  loopVar |= me_modified(me);
187  GECODE_ME_CHECK(me);
188 
189  iv[j].view.cancel(home,*this, PC_SET_ANY);
190  ++i;
191  ++vx0ub;
192  continue;
193  } else {
194  // if x_i is consistent, check whether we know
195  // that its index is in x0
196  if (vx0() && vx0.val()==candidateInd) {
197  // x1 >= candidate, candidate <= x1
198  GlbRanges<View> candlb(candidate);
199  ModEvent me = x1.includeI(home,candlb);
200  loopVar |= me_modified(me);
201  GECODE_ME_CHECK(me);
202 
203  LubRanges<View1> x1ub(x1);
204  me = candidate.intersectI(home,x1ub);
205  loopVar |= me_modified(me);
206  GECODE_ME_CHECK(me);
207  ++vx0;
208  }
209  new (&before[j]) GLBndSet(home);
210  before[j].update(home,sofarBefore);
211  LubRanges<View> cub(candidate);
212  sofarBefore.includeI(home,cub);
213  GlbRanges<View> clb(candidate);
214  selectedInter.intersectI(home,clb);
215  maxCard = std::max(maxCard, candidate.cardMax());
216  minCard = std::min(minCard, candidate.cardMin());
217  }
218 
219  ++vx0ub;
220  ++i; ++j;
221  }
222 
223  // cancel the variables with index greater than
224  // max of lub(x0)
225  for (int k=i; k<n; k++) {
226  iv[k].view.cancel(home,*this, PC_SET_ANY);
227  }
228  n = j;
229  iv.size(n);
230 
231  if (x0.cardMax()==0) {
232  // Selector is empty, hence the result must be empty
233  {
234  GECODE_ME_CHECK(x1.cardMax(home,0));
235  }
236  for (int i=n; i--;)
237  before[i].dispose(home);
238  return home.ES_SUBSUMED(*this);
239  }
240 
241  if (x0.cardMin() > 0) {
242  // Selector is not empty, hence the intersection of the
243  // possibly selected lower bounds is contained in x1
244  BndSetRanges si(selectedInter);
245  ModEvent me = x1.includeI(home, si);
246  loopVar |= me_modified(me);
247  GECODE_ME_CHECK(me);
248  me = x1.cardMin(home, minCard);
249  loopVar |= me_modified(me);
250  GECODE_ME_CHECK(me);
251  }
252  selectedInter.dispose(home);
253 
254  if (x0.cardMax() <= 1) {
255  ModEvent me = x1.cardMax(home, maxCard);
256  loopVar |= me_modified(me);
257  GECODE_ME_CHECK(me);
258  }
259 
260  {
261  // x1 <= sofarBefore
262  BndSetRanges sfB(sofarBefore);
263  ModEvent me = x1.intersectI(home,sfB);
264  loopVar |= me_modified(me);
265  GECODE_ME_CHECK(me);
266  }
267 
268  sofarBefore.dispose(home);
269 
270  GLBndSet sofarAfter(home);
271 
272  // In the second iteration, this time backwards, compute
273  // sofarAfter as the union of all lub(x_j) with j>i
274  for (int i=n; i--;) {
275  // TODO: check for size of universe here?
276  // if (sofarAfter.size() == 0) break;
277 
278  // extra = inter(before[i], sofarAfter) - lub(x1)
279  BndSetRanges b(before[i]);
280  BndSetRanges s(sofarAfter);
281  GlbRanges<View1> x1lb(x1);
285  if (diff()) {
286  ModEvent me = (x0.include(home,iv[i].idx));
287  loopVar |= me_modified(me);
288  GECODE_ME_CHECK(me);
289 
290  // candidate != extra
291  me = iv[i].view.includeI(home,diff);
292  loopVar |= me_modified(me);
293  GECODE_ME_CHECK(me);
294  }
295 
296  LubRanges<View> iviub(iv[i].view);
297  sofarAfter.includeI(home,iviub);
298  before[i].dispose(home);
299  }
300  sofarAfter.dispose(home);
301 
302  } while (loopVar);
303 
304  // Test whether we determined x0 without determining x1
305  if (x0.assigned() && !x1.assigned()) {
306  int ubsize = static_cast<int>(x0.lubSize());
307  if (ubsize > 2) {
308  assert(ubsize==n);
309  ViewArray<View> is(home,ubsize);
310  for (int i=n; i--;)
311  is[i]=iv[i].view;
313  ::post(home(*this),is,x1)));
314  } else if (ubsize == 2) {
315  assert(n==2);
316  View a = iv[0].view;
317  View b = iv[1].view;
319  ::post(home(*this),a,b,x1)));
320  } else if (ubsize == 1) {
321  assert(n==1);
322  GECODE_REWRITE(*this,
323  (Rel::Eq<View1,View>::post(home(*this),x1,iv[0].view)));
324  } else {
325  GECODE_ME_CHECK(x1.cardMax(home, 0));
326  return home.ES_SUBSUMED(*this);
327  }
328  }
329 
330  for (int i=iv.size(); i--;)
331  if (!iv[i].view.assigned())
332  return ES_FIX;
333  if (!x1.assigned() || !x0.assigned())
334  return ES_FIX;
335  return home.ES_SUBSUMED(*this);
336  }
337 
338 }}}
339 
340 // STATISTICS: set-prop
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
NNF * r
Right subtree.
Definition: bool-expr.cpp:242
Base-class for both propagators and branchers.
Definition: core.hpp:628
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:3252
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1607
Home class for posting propagators
Definition: core.hpp:856
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition: core.hpp:3219
Integer sets.
Definition: int.hh:174
An array of IdxView pairs.
Definition: idx-view.hh:67
void subscribe(Space &home, Propagator &p, PropCond pc, bool process=true)
Definition: idx-view.hpp:131
void update(Space &home, IdxViewArray< View > &x)
Cloning.
Definition: idx-view.hpp:153
int size(void) const
Return the current size.
Definition: idx-view.hpp:105
Range iterator cache
Range iterator for computing set difference.
Definition: ranges-diff.hpp:43
Range iterator for singleton range.
Value iterator from range iterator.
int val(void) const
Return current value.
Range iterator for computing union (binary)
Propagation cost.
Definition: core.hpp:486
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition: core.hpp:4796
@ HI
Expensive.
Definition: core.hpp:514
Base-class for propagators.
Definition: core.hpp:1064
Handle to region.
Definition: region.hpp:55
Range iterator for integer sets.
Definition: var-imp.hpp:185
void update(Space &home, BndSet &x)
Update this set to be a clone of set x.
Definition: integerset.hpp:140
void dispose(Space &home)
Free memory used by this set.
Definition: integerset.hpp:60
Propagator for element with union
Definition: element.hh:119
virtual void reschedule(Space &home)
Schedule function.
Definition: union.hpp:68
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: union.hpp:109
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: union.hpp:76
static ExecStatus post(Home home, IdxViewArray &x, View0 y, View1 z)
Definition: union.hpp:90
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: union.hpp:61
ElementUnion(Space &home, ElementUnion &p)
Constructor for cloning p.
Definition: union.hpp:52
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition: union.hpp:103
Growing sets of integers.
Definition: var-imp.hpp:205
bool includeI(Space &home, I &i)
Include the set represented by i in this set.
Definition: integerset.hpp:296
Range iterator for the greatest lower bound.
Definition: var-imp.hpp:359
Shrinking sets of integers.
Definition: var-imp.hpp:243
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 the least upper bound.
Definition: var-imp.hpp:317
Propagator for nary union
Definition: rel-op.hh:219
Propagator for ternary union
Definition: rel-op.hh:154
Propagator for set equality
Definition: rel.hh:150
Computation spaces.
Definition: core.hpp:1742
View arrays.
Definition: array.hpp:253
ExecStatus
Definition: core.hpp:472
@ ES_OK
Execution is okay.
Definition: core.hpp:476
@ ES_FIX
Propagation has computed fixpoint.
Definition: core.hpp:477
int ModEvent
Type for modification events.
Definition: core.hpp:62
void post(Home home, Term *t, int n, FloatRelType frt, FloatVal c)
Post propagator for linear constraint over floats.
Definition: post.cpp:238
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3563
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition: core.hpp:4074
int ModEventDelta
Modification event deltas.
Definition: core.hpp:89
bool failed(void) const
Check whether space is failed.
Definition: core.hpp:4044
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:52
#define GECODE_REWRITE(prop, post)
Rewrite propagator by executing post function.
Definition: macros.hpp:116
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition: modevent.hpp:59
@ AP_DISPOSE
Actor must always be disposed.
Definition: core.hpp:562
const FloatNum max
Largest allowed float value.
Definition: float.hh:844
const FloatNum min
Smallest allowed float value.
Definition: float.hh:846
const int min
Smallest allowed integer in integer set.
Definition: set.hh:99
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
const Gecode::PropCond PC_SET_ANY
Propagate when any bound or the cardinality of a view changes.
Definition: var-type.hpp:248
Gecode::IntArgs i({1, 2, 3, 4})
const SetInstr * si[]
Definition: mm-set.cpp:4341
SetExpr inter(const SetVarArgs &x)
Intersection of set variables.
Definition: set-expr.cpp:696
#define forceinline
Definition: config.hpp:194