Generated on Sat Jul 28 2018 17:18:54 for Gecode by doxygen 1.8.14
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  * Last modified:
12  * $Date: 2016-06-29 17:28:17 +0200 (Wed, 29 Jun 2016) $ by $Author: schulte $
13  * $Revision: 15137 $
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 { namespace Element {
41 
42  template<class View, class View0, class View1>
45  ElementUnion(Home home, IdxViewArray& iv0, View0 y0, View1 y1)
46  : Propagator(home), iv(iv0), x0(y0), x1(y1) {
47  home.notice(*this,AP_DISPOSE);
48  x0.subscribe(home,*this, PC_SET_ANY);
49  x1.subscribe(home,*this, PC_SET_ANY);
50  iv.subscribe(home,*this, PC_SET_ANY);
51  }
52 
53  template<class View, class View0, class View1>
57  : Propagator(home,share,p) {
58  x0.update(home,share,p.x0);
59  x1.update(home,share,p.x1);
60  iv.update(home,share,p.iv);
61  }
62 
63  template<class View, class View0, class View1>
64  PropCost
66  const ModEventDelta&) const {
67  return PropCost::linear(PropCost::HI, iv.size()+2);
68  }
69 
70  template<class View, class View0, class View1>
71  void
73  x0.reschedule(home,*this, PC_SET_ANY);
74  x1.reschedule(home,*this, PC_SET_ANY);
75  iv.reschedule(home,*this, PC_SET_ANY);
76  }
77 
78  template<class View, class View0, class View1>
79  forceinline size_t
81  home.ignore(*this,AP_DISPOSE);
82  if (!home.failed()) {
83  x0.cancel(home,*this,PC_SET_ANY);
84  x1.cancel(home,*this,PC_SET_ANY);
85  iv.cancel(home,*this,PC_SET_ANY);
86  }
87  (void) Propagator::dispose(home);
88  return sizeof(*this);
89  }
90 
91  template<class View, class View0, class View1>
94  post(Home home, IdxViewArray& xs, View0 x0, View1 x1) {
95  int n = xs.size();
96 
97  // x0 \subseteq {1,...,n}
98  Iter::Ranges::Singleton s(0, n-1);
99  GECODE_ME_CHECK(x0.intersectI(home,s));
100  (void) new (home)
101  ElementUnion<View,View0,View1>(home,xs,x0,x1);
102  return ES_OK;
103  }
104 
105  template<class View, class View0, class View1>
106  Actor*
108  return new (home) ElementUnion<View,View0,View1>(home,share,*this);
109  }
110 
111  template<class View, class View0, class View1>
112  ExecStatus
114  Region r(home);
115  int n = iv.size();
116 
117  bool loopVar;
118  do {
119  loopVar = false;
120 
121  // Cache the upper bound iterator, as we have to
122  // modify the upper bound while iterating
123  LubRanges<View0> x0ub(x0);
124  Iter::Ranges::Cache x0ubc(r,x0ub);
126 
127  GlbRanges<View0> x0lb(x0);
128  Iter::Ranges::Cache x0lbc(r,x0lb);
130 
131  // In the first iteration, compute in before[i] the union
132  // of all the upper bounds of the x_i. At the same time,
133  // exclude inconsistent x_i from x0 and remove them from
134  // the list, cancel their dependencies.
135 
136  GLBndSet sofarBefore(home);
137  LUBndSet selectedInter(home, IntSet (Limits::min,
138  Limits::max));
139  GLBndSet* before =
140  static_cast<GLBndSet*>(r.ralloc(sizeof(GLBndSet)*n));
141 
142  int j = 0;
143  int i = 0;
144 
145  unsigned int maxCard = 0;
146  unsigned int minCard = Limits::card;
147 
148  while ( vx0ub() ) {
149 
150  // Remove vars at indices not in the upper bound
151  if (iv[i].idx < vx0ub.val()) {
152  iv[i].view.cancel(home,*this, PC_SET_ANY);
153  ++i;
154  continue;
155  }
156  assert(iv[i].idx == vx0ub.val());
157  iv[j] = iv[i];
158 
159  View candidate = iv[j].view;
160  int candidateInd = iv[j].idx;
161 
162  // inter = glb(candidate) & complement(lub(x1))
163  GlbRanges<View> candlb(candidate);
164  LubRanges<View1> x1ub(x1);
166  diff(candlb, x1ub);
167 
168  bool selectSingleInconsistent = false;
169  if (x0.cardMax() <= 1) {
170  GlbRanges<View1> x1lb(x1);
171  LubRanges<View> candub(candidate);
173  LubRanges<View> > diff2(x1lb, candub);
174  selectSingleInconsistent =
175  diff2() || candidate.cardMax() < x1.cardMin();
176  }
177 
178  // exclude inconsistent x_i
179  // an x_i is inconsistent if
180  // * at most one x_i can be selected and there are
181  // elements in x_0 that can't be in x_i
182  // (selectSingleInconsistent)
183  // * its min cardinality is greater than maxCard of x1
184  // * inter is not empty (there are elements in x_i
185  // that can't be in x_0)
186  if (selectSingleInconsistent ||
187  candidate.cardMin() > x1.cardMax() ||
188  diff()) {
189  ModEvent me = (x0.exclude(home,candidateInd));
190  loopVar |= me_modified(me);
191  GECODE_ME_CHECK(me);
192 
193  iv[j].view.cancel(home,*this, PC_SET_ANY);
194  ++i;
195  ++vx0ub;
196  continue;
197  } else {
198  // if x_i is consistent, check whether we know
199  // that its index is in x0
200  if (vx0() && vx0.val()==candidateInd) {
201  // x1 >= candidate, candidate <= x1
202  GlbRanges<View> candlb(candidate);
203  ModEvent me = x1.includeI(home,candlb);
204  loopVar |= me_modified(me);
205  GECODE_ME_CHECK(me);
206 
207  LubRanges<View1> x1ub(x1);
208  me = candidate.intersectI(home,x1ub);
209  loopVar |= me_modified(me);
210  GECODE_ME_CHECK(me);
211  ++vx0;
212  }
213  new (&before[j]) GLBndSet(home);
214  before[j].update(home,sofarBefore);
215  LubRanges<View> cub(candidate);
216  sofarBefore.includeI(home,cub);
217  GlbRanges<View> clb(candidate);
218  selectedInter.intersectI(home,clb);
219  maxCard = std::max(maxCard, candidate.cardMax());
220  minCard = std::min(minCard, candidate.cardMin());
221  }
222 
223  ++vx0ub;
224  ++i; ++j;
225  }
226 
227  // cancel the variables with index greater than
228  // max of lub(x0)
229  for (int k=i; k<n; k++) {
230  iv[k].view.cancel(home,*this, PC_SET_ANY);
231  }
232  n = j;
233  iv.size(n);
234 
235  if (x0.cardMax()==0) {
236  // Selector is empty, hence the result must be empty
237  {
238  GECODE_ME_CHECK(x1.cardMax(home,0));
239  }
240  for (int i=n; i--;)
241  before[i].dispose(home);
242  return home.ES_SUBSUMED(*this);
243  }
244 
245  if (x0.cardMin() > 0) {
246  // Selector is not empty, hence the intersection of the
247  // possibly selected lower bounds is contained in x1
248  BndSetRanges si(selectedInter);
249  ModEvent me = x1.includeI(home, si);
250  loopVar |= me_modified(me);
251  GECODE_ME_CHECK(me);
252  me = x1.cardMin(home, minCard);
253  loopVar |= me_modified(me);
254  GECODE_ME_CHECK(me);
255  }
256  selectedInter.dispose(home);
257 
258  if (x0.cardMax() <= 1) {
259  ModEvent me = x1.cardMax(home, maxCard);
260  loopVar |= me_modified(me);
261  GECODE_ME_CHECK(me);
262  }
263 
264  {
265  // x1 <= sofarBefore
266  BndSetRanges sfB(sofarBefore);
267  ModEvent me = x1.intersectI(home,sfB);
268  loopVar |= me_modified(me);
269  GECODE_ME_CHECK(me);
270  }
271 
272  sofarBefore.dispose(home);
273 
274  GLBndSet sofarAfter(home);
275 
276  // In the second iteration, this time backwards, compute
277  // sofarAfter as the union of all lub(x_j) with j>i
278  for (int i=n; i--;) {
279  // TODO: check for size of universe here?
280  // if (sofarAfter.size() == 0) break;
281 
282  // extra = inter(before[i], sofarAfter) - lub(x1)
284  BndSetRanges s(sofarAfter);
285  GlbRanges<View1> x1lb(x1);
289  if (diff()) {
290  ModEvent me = (x0.include(home,iv[i].idx));
291  loopVar |= me_modified(me);
292  GECODE_ME_CHECK(me);
293 
294  // candidate != extra
295  me = iv[i].view.includeI(home,diff);
296  loopVar |= me_modified(me);
297  GECODE_ME_CHECK(me);
298  }
299 
300  LubRanges<View> iviub(iv[i].view);
301  sofarAfter.includeI(home,iviub);
302  before[i].dispose(home);
303  }
304  sofarAfter.dispose(home);
305 
306  } while (loopVar);
307 
308  // Test whether we determined x0 without determining x1
309  if (x0.assigned() && !x1.assigned()) {
310  int ubsize = static_cast<int>(x0.lubSize());
311  if (ubsize > 2) {
312  assert(ubsize==n);
313  ViewArray<View> is(home,ubsize);
314  for (int i=n; i--;)
315  is[i]=iv[i].view;
317  ::post(home(*this),is,x1)));
318  } else if (ubsize == 2) {
319  assert(n==2);
320  View a = iv[0].view;
321  View b = iv[1].view;
323  ::post(home(*this),a,b,x1)));
324  } else if (ubsize == 1) {
325  assert(n==1);
326  GECODE_REWRITE(*this,
327  (Rel::Eq<View1,View>::post(home(*this),x1,iv[0].view)));
328  } else {
329  GECODE_ME_CHECK(x1.cardMax(home, 0));
330  return home.ES_SUBSUMED(*this);
331  }
332  }
333 
334  bool allAssigned = true;
335  for (int i=iv.size(); i--;) {
336  if (!iv[i].view.assigned()) {
337  allAssigned = false;
338  break;
339  }
340  }
341  if (x1.assigned() && x0.assigned() && allAssigned) {
342  return home.ES_SUBSUMED(*this);
343  }
344 
345  return ES_FIX;
346  }
347 
348 }}}
349 
350 // STATISTICS: set-prop
#define GECODE_REWRITE(prop, post)
Rewrite propagator by executing post function.
Definition: macros.hpp:120
const SetInstr * si[]
Definition: mm-set.cpp:4340
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: union.hpp:80
Propagator for nary union
Definition: rel-op.hh:221
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1669
Range iterator for singleton range.
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition: core.hpp:4841
const int min
Smallest allowed integer in integer set.
Definition: set.hh:103
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3614
const FloatNum max
Largest allowed float value.
Definition: float.hh:848
Actor must always be disposed.
Definition: core.hpp:630
Propagator for ternary union
Definition: rel-op.hh:156
virtual void reschedule(Space &home)
Schedule function.
Definition: union.hpp:72
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:1092
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: union.hpp:113
Range iterator for the greatest lower bound.
Definition: var-imp.hpp:363
Handle to region.
Definition: region.hpp:61
Propagation has computed fixpoint.
Definition: core.hpp:545
const unsigned int card
Maximum cardinality of an integer set.
Definition: set.hh:105
const int max
Largest allowed integer in integer set.
Definition: set.hh:101
Computation spaces.
Definition: core.hpp:1748
int val(void) const
Return current value.
Range iterator for the least upper bound.
Definition: var-imp.hpp:321
Base-class for both propagators and branchers.
Definition: core.hpp:696
struct Gecode::@579::NNF::@61::@63 a
For atomic nodes.
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
const FloatNum min
Smallest allowed float value.
Definition: float.hh:850
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
virtual Actor * copy(Space &home, bool)
Copy propagator during cloning.
Definition: union.hpp:107
bool intersectI(Space &home, I &i)
Exclude all elements not in the set represented by i from this set.
Definition: integerset.hpp:374
bool failed(void) const
Check whether space is failed.
Definition: core.hpp:4095
Value iterator from range iterator.
struct Gecode::@579::NNF::@61::@62 b
For binary nodes (and, or, eqv)
Range iterator for integer sets.
Definition: var-imp.hpp:189
static ExecStatus post(Home home, IdxViewArray &x, View0 y, View1 z)
Definition: union.hpp:94
Integer sets.
Definition: int.hh:174
Expensive.
Definition: core.hpp:582
View arrays.
Definition: array.hpp:234
int size(void) const
Return the current size.
Definition: idx-view.hpp:103
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:56
bool includeI(Space &home, I &i)
Include the set represented by i in this set.
Definition: integerset.hpp:300
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition: core.hpp:3321
void dispose(Space &home)
Free memory used by this set.
Definition: integerset.hpp:64
const Gecode::PropCond PC_SET_ANY
Propagate when any bound or the cardinality of a view changes.
Definition: var-type.hpp:248
Range iterator for computing union (binary)
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:784
SetExpr inter(const SetVarArgs &x)
Intersection of set variables.
Definition: set-expr.cpp:699
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition: core.hpp:4141
Propagator for element with union
Definition: element.hh:123
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: union.hpp:65
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:3354
Propagation cost.
Definition: core.hpp:554
Range iterator cache
void subscribe(Space &home, Propagator &p, PropCond pc, bool process=true)
Definition: idx-view.hpp:129
ExecStatus
Definition: core.hpp:540
#define forceinline
Definition: config.hpp:173
Growing sets of integers.
Definition: var-imp.hpp:209
ElementUnion(Space &home, bool share, ElementUnion &p)
Constructor for cloning p.
Definition: union.hpp:56
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition: modevent.hpp:63
Propagator for set equality
Definition: rel.hh:150
Execution is okay.
Definition: core.hpp:544
An array of IdxView pairs.
Definition: idx-view.hh:71
Gecode toplevel namespace
Range iterator for computing set difference.
Definition: ranges-diff.hpp:47
int ModEventDelta
Modification event deltas.
Definition: core.hpp:169
bool before(const ConstSetView &x, const ConstSetView &y)
Definition: const.hpp:698
Home class for posting propagators
Definition: core.hpp:922
TFE post(PropagatorGroup g)
Only post functions (but not propagators) from g are considered.
void update(Space &home, bool share, IdxViewArray< View > &x)
Cloning.
Definition: idx-view.hpp:151