Generated on Sat Jan 20 2018 22:21:18 for Gecode by doxygen 1.8.13
inter.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
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  ElementIntersection(Home home, IdxViewArray& iv0, View0 y0, View1 y1,
46  const IntSet& theUniverse)
47  : Propagator(home), universe(theUniverse), iv(iv0), x0(y0), x1(y1) {
48  home.notice(*this,AP_DISPOSE);
49  x0.subscribe(home,*this, PC_SET_ANY);
50  x1.subscribe(home,*this, PC_SET_ANY);
51  iv.subscribe(home,*this, PC_SET_ANY);
52  }
53 
54  template<class View, class View0, class View1>
57  ElementIntersection(Space& home, bool share,
59  : Propagator(home,share,p) {
60  x0.update(home,share,p.x0);
61  x1.update(home,share,p.x1);
62  iv.update(home,share,p.iv);
63  universe.update(home,share,p.universe);
64  }
65 
66  template<class View, class View0, class View1>
67  PropCost
69  const ModEventDelta&) const {
70  return PropCost::linear(PropCost::HI, iv.size()+2);
71  }
72 
73  template<class View, class View0, class View1>
74  void
76  x0.reschedule(home,*this, PC_SET_ANY);
77  x1.reschedule(home,*this, PC_SET_ANY);
78  iv.reschedule(home,*this, PC_SET_ANY);
79  }
80 
81  template<class View, class View0, class View1>
82  forceinline size_t
84  home.ignore(*this,AP_DISPOSE);
85  if (!home.failed()) {
86  x0.cancel(home,*this, PC_SET_ANY);
87  x1.cancel(home,*this, PC_SET_ANY);
88  iv.cancel(home,*this,PC_SET_ANY);
89  }
90  universe.~IntSet();
91  (void) Propagator::dispose(home);
92  return sizeof(*this);
93  }
94 
95  template<class View, class View0, class View1>
98  post(Home home, IdxViewArray& xs, View0 x0, View1 x1,
99  const IntSet& universe) {
100  int n = xs.size();
101 
102  // x0 \subseteq {1,...,n}
103  Iter::Ranges::Singleton s(0, n-1);
104  GECODE_ME_CHECK(x0.intersectI(home,s));
105  (void) new (home)
107  return ES_OK;
108  }
109 
110  template<class View, class View0, class View1>
111  Actor*
113  return new (home) ElementIntersection<View,View0,View1>(home,share,*this);
114  }
115 
116  template<class View, class View0, class View1>
117  ExecStatus
119  const ModEventDelta&) {
120  Region r(home);
121  int n = iv.size();
122 
123  bool loopVar;
124  do {
125  loopVar = false;
126 
127  // Cache the upper bound iterator, as we have to
128  // modify the upper bound while iterating
129  LubRanges<View0> x0ub(x0);
130  Iter::Ranges::Cache x0ubc(r,x0ub);
132 
133  GlbRanges<View0> x0lb(x0);
134  Iter::Ranges::Cache x0lbc(r,x0lb);
136 
137  // In the first iteration, compute in before[i] the intersection
138  // of all the lower bounds of the x_i. At the same time,
139  // exclude inconsistent x_i from x0 and remove them from
140  // the list, cancel their dependencies.
141 
142  LUBndSet sofarBefore(home,universe);
143  LUBndSet* before = r.alloc<LUBndSet>(n);
144 
145  int j = 0;
146  int i = 0;
147  while ( vx0ub() ) {
148 
149  // Remove vars at indices not in the upper bound
150  if (iv[i].idx < vx0ub.val()) {
151  iv[i].view.cancel(home,*this, PC_SET_ANY);
152  ++i;
153  continue;
154  }
155  assert(iv[i].idx == vx0ub.val());
156  iv[j] = iv[i];
157 
158  View candidate = iv[j].view;
159  int candidateInd = iv[j].idx;
160 
161  // inter = glb(x1) & complement(lub(candidate))
162  GlbRanges<View1> x1lb(x1);
163  LubRanges<View> candub(candidate);
165  inter(x1lb, candub);
166 
167  // exclude inconsistent x_i
168  // an x_i is inconsistent if
169  // * its max cardinality is less than minCard of x1
170  // * inter is not empty (there are elements in x_0
171  // that can't be in x_i)
172  if (candidate.cardMax() < x1.cardMin() ||
173  inter()) {
174  ModEvent me = (x0.exclude(home,candidateInd));
175  loopVar |= me_modified(me);
176  GECODE_ME_CHECK(me);
177 
178  iv[j].view.cancel(home,*this, PC_SET_ANY);
179  ++i;
180  ++vx0ub;
181  continue;
182  } else {
183  // if x_i is consistent, check whether we know
184  // that its index is in x0
185  if (vx0() && vx0.val()==candidateInd) {
186  // x1 <= candidate, candidate >= x1
187  GlbRanges<View1> x1lb(x1);
188  ModEvent me = candidate.includeI(home,x1lb);
189  loopVar |= me_modified(me);
190  GECODE_ME_CHECK(me);
191 
192  LubRanges<View> candub(candidate);
193  me = x1.intersectI(home,candub);
194  loopVar |= me_modified(me);
195  GECODE_ME_CHECK(me);
196  ++vx0;
197  }
198  new (&before[j]) LUBndSet(home);
199  before[j].update(home,sofarBefore);
200  GlbRanges<View> clb(candidate);
201  sofarBefore.intersectI(home,clb);
202  }
203 
204  ++vx0ub;
205  ++i; ++j;
206  }
207 
208  // cancel the variables with index greater than
209  // max of lub(x0)
210  for (int k=i; k<n; k++) {
211  iv[k].view.cancel(home,*this, PC_SET_ANY);
212  }
213  n = j;
214  iv.size(n);
215 
216  if (x0.cardMax()==0) {
217  // Elementor is empty, hence the result must be universe
218  {
219  IntSetRanges uniI(universe);
220  GECODE_ME_CHECK(x1.includeI(home,uniI));
221  }
222  {
223  IntSetRanges uniI(universe);
224  GECODE_ME_CHECK(x1.intersectI(home,uniI));
225  }
226  for (int i=n; i--;)
227  before[i].dispose(home);
228  return home.ES_SUBSUMED(*this);
229  }
230 
231  {
232  // x1 >= sofarBefore
233  BndSetRanges sfB(sofarBefore);
234  ModEvent me = x1.includeI(home,sfB);
235  loopVar |= me_modified(me);
236  GECODE_ME_CHECK(me);
237  }
238 
239  sofarBefore.dispose(home);
240 
241  LUBndSet sofarAfter(home, universe);
242 
243  // In the second iteration, this time backwards, compute
244  // sofarAfter as the intersection of all glb(x_j) with j>i
245  for (int i=n; i--;) {
246  if (sofarAfter.size() == 0) break;
247 
248  // extra = inter(before[i], sofarAfter) - lub(x1)
249  BndSetRanges b(before[i]);
250  BndSetRanges s(sofarAfter);
251  LubRanges<View1> x1ub(x1);
254  BndSetRanges>, LubRanges<View1> > diff(inter, x1ub);
255  if (diff()) {
256  ModEvent me = (x0.include(home,iv[i].idx));
257  loopVar |= me_modified(me);
258  GECODE_ME_CHECK(me);
259 
260  // candidate != extra
261  me = iv[i].view.excludeI(home,diff);
262  loopVar |= me_modified(me);
263  GECODE_ME_CHECK(me);
264  }
265 
266  GlbRanges<View> ivilb(iv[i].view);
267  sofarAfter.intersectI(home,ivilb);
268  before[i].dispose(home);
269  }
270  sofarAfter.dispose(home);
271 
272  } while (loopVar);
273 
274  // Test whether we determined x0 without determining x1
275  if (x0.assigned() && !x1.assigned()) {
276  int ubsize = static_cast<int>(x0.lubSize());
277  if (ubsize > 2) {
278  assert(ubsize==n);
279  ViewArray<View> is(home,ubsize);
280  for (int i=n; i--;)
281  is[i]=iv[i].view;
283  ::post(home(*this),is,x1)));
284  } else if (ubsize == 2) {
285  assert(n==2);
286  View a = iv[0].view;
287  View b = iv[1].view;
289  ::post(home(*this),a,b,x1)));
290  } else if (ubsize == 1) {
291  assert(n==1);
292  GECODE_REWRITE(*this,
293  (Rel::Eq<View1,View>::post(home(*this),x1,iv[0].view)));
294  } else {
295  GECODE_ME_CHECK(x1.cardMax(home, 0));
296  return home.ES_SUBSUMED(*this);
297  }
298  }
299 
300  bool allAssigned = true;
301  for (int i=iv.size(); i--;) {
302  if (!iv[i].view.assigned()) {
303  allAssigned = false;
304  break;
305  }
306  }
307  if (x1.assigned() && x0.assigned() && allAssigned) {
308  return home.ES_SUBSUMED(*this);
309  }
310 
311  return ES_FIX;
312  }
313 
314 }}}
315 
316 // STATISTICS: set-prop
#define GECODE_REWRITE(prop, post)
Rewrite propagator by executing post function.
Definition: macros.hpp:120
static ExecStatus post(Home home, IdxViewArray &x, View0 y, View1 z, const IntSet &u)
Definition: inter.hpp:98
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
Range iterator for integer sets.
Definition: int.hh:274
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3614
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: inter.hpp:68
Actor must always be disposed.
Definition: core.hpp:630
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition: region.hpp:326
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
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
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
virtual void reschedule(Space &home)
Schedule function.
Definition: inter.hpp:75
struct Gecode::@579::NNF::@61::@63 a
For atomic nodes.
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
unsigned int size(void) const
Return size.
Definition: integerset.hpp:97
Range iterator for computing intersection (binary)
void cancel(Space &home, Propagator &p, PropCond pc)
Definition: idx-view.hpp:137
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
Integer sets.
Definition: int.hh:174
Expensive.
Definition: core.hpp:582
View arrays.
Definition: array.hpp:234
ElementIntersection(Space &home, bool share, ElementIntersection &p)
Constructor for cloning p.
Definition: inter.hpp:57
int size(void) const
Return the current size.
Definition: idx-view.hpp:103
void update(Space &home, BndSet &x)
Update this set to be a clone of set x.
Definition: integerset.hpp:144
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:56
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
Propagator for element with intersection
Definition: element.hh:82
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 update(Space &home, bool share, SharedHandle &sh)
Updating during cloning.
Definition: core.hpp:3127
void reschedule(Space &home, Propagator &p, PropCond pc)
Schedule propagator p.
Definition: idx-view.hpp:144
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition: core.hpp:4141
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:3354
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: inter.hpp:118
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
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: inter.hpp:83
#define forceinline
Definition: config.hpp:173
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
virtual Actor * copy(Space &home, bool)
Copy propagator during cloning.
Definition: inter.hpp:112
Home class for posting propagators
Definition: core.hpp:922
Propagator for nary intersection
Definition: rel-op.hh:186
Propagator for ternary intersection
Definition: rel-op.hh:126
void update(Space &home, bool share, IdxViewArray< View > &x)
Cloning.
Definition: idx-view.hpp:151