Generated on Tue Oct 22 2013 00:49:07 for Gecode by doxygen 1.8.4
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: 2012-09-07 17:31:22 +0200 (Fri, 07 Sep 2012) $ by $Author: schulte $
13  * $Revision: 13068 $
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  forceinline size_t
76  home.ignore(*this,AP_DISPOSE);
77  if (!home.failed()) {
78  x0.cancel(home,*this, PC_SET_ANY);
79  x1.cancel(home,*this, PC_SET_ANY);
80  iv.cancel(home,*this,PC_SET_ANY);
81  }
82  universe.~IntSet();
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  const IntSet& universe) {
92  int n = xs.size();
93 
94  // x0 \subseteq {1,...,n}
95  Iter::Ranges::Singleton s(0, n-1);
96  GECODE_ME_CHECK(x0.intersectI(home,s));
97  (void) new (home)
98  ElementIntersection<View,View0,View1>(home,xs,x0,x1,universe);
99  return ES_OK;
100  }
101 
102  template<class View, class View0, class View1>
103  Actor*
105  return new (home) ElementIntersection<View,View0,View1>(home,share,*this);
106  }
107 
108  template<class View, class View0, class View1>
109  ExecStatus
111  const ModEventDelta&) {
112  Region r(home);
113  int n = iv.size();
114 
115  bool loopVar;
116  do {
117  loopVar = false;
118 
119  // Cache the upper bound iterator, as we have to
120  // modify the upper bound while iterating
121  LubRanges<View0> x0ub(x0);
122  Iter::Ranges::Cache x0ubc(r,x0ub);
124 
125  GlbRanges<View0> x0lb(x0);
126  Iter::Ranges::Cache x0lbc(r,x0lb);
128 
129  // In the first iteration, compute in before[i] the intersection
130  // of all the lower bounds of the x_i. At the same time,
131  // exclude inconsistent x_i from x0 and remove them from
132  // the list, cancel their dependencies.
133 
134  LUBndSet sofarBefore(home,universe);
135  LUBndSet* before = r.alloc<LUBndSet>(n);
136 
137  int j = 0;
138  int i = 0;
139  while ( vx0ub() ) {
140 
141  // Remove vars at indices not in the upper bound
142  if (iv[i].idx < vx0ub.val()) {
143  iv[i].view.cancel(home,*this, PC_SET_ANY);
144  ++i;
145  continue;
146  }
147  assert(iv[i].idx == vx0ub.val());
148  iv[j] = iv[i];
149 
150  View candidate = iv[j].view;
151  int candidateInd = iv[j].idx;
152 
153  // inter = glb(x1) & complement(lub(candidate))
154  GlbRanges<View1> x1lb(x1);
155  LubRanges<View> candub(candidate);
157  inter(x1lb, candub);
158 
159  // exclude inconsistent x_i
160  // an x_i is inconsistent if
161  // * its max cardinality is less than minCard of x1
162  // * inter is not empty (there are elements in x_0
163  // that can't be in x_i)
164  if (candidate.cardMax() < x1.cardMin() ||
165  inter()) {
166  ModEvent me = (x0.exclude(home,candidateInd));
167  loopVar |= me_modified(me);
168  GECODE_ME_CHECK(me);
169 
170  iv[j].view.cancel(home,*this, PC_SET_ANY);
171  ++i;
172  ++vx0ub;
173  continue;
174  } else {
175  // if x_i is consistent, check whether we know
176  // that its index is in x0
177  if (vx0() && vx0.val()==candidateInd) {
178  // x1 <= candidate, candidate >= x1
179  GlbRanges<View1> x1lb(x1);
180  ModEvent me = candidate.includeI(home,x1lb);
181  loopVar |= me_modified(me);
182  GECODE_ME_CHECK(me);
183 
184  LubRanges<View> candub(candidate);
185  me = x1.intersectI(home,candub);
186  loopVar |= me_modified(me);
187  GECODE_ME_CHECK(me);
188  ++vx0;
189  }
190  new (&before[j]) LUBndSet(home);
191  before[j].update(home,sofarBefore);
192  GlbRanges<View> clb(candidate);
193  sofarBefore.intersectI(home,clb);
194  }
195 
196  ++vx0ub;
197  ++i; ++j;
198  }
199 
200  // cancel the variables with index greater than
201  // max of lub(x0)
202  for (int k=i; k<n; k++) {
203  iv[k].view.cancel(home,*this, PC_SET_ANY);
204  }
205  n = j;
206  iv.size(n);
207 
208  if (x0.cardMax()==0) {
209  // Elementor is empty, hence the result must be universe
210  {
211  IntSetRanges uniI(universe);
212  GECODE_ME_CHECK(x1.includeI(home,uniI));
213  }
214  {
215  IntSetRanges uniI(universe);
216  GECODE_ME_CHECK(x1.intersectI(home,uniI));
217  }
218  for (int i=n; i--;)
219  before[i].dispose(home);
220  return home.ES_SUBSUMED(*this);
221  }
222 
223  {
224  // x1 >= sofarBefore
225  BndSetRanges sfB(sofarBefore);
226  ModEvent me = x1.includeI(home,sfB);
227  loopVar |= me_modified(me);
228  GECODE_ME_CHECK(me);
229  }
230 
231  sofarBefore.dispose(home);
232 
233  LUBndSet sofarAfter(home, universe);
234 
235  // In the second iteration, this time backwards, compute
236  // sofarAfter as the intersection of all glb(x_j) with j>i
237  for (int i=n; i--;) {
238  if (sofarAfter.size() == 0) break;
239 
240  // extra = inter(before[i], sofarAfter) - lub(x1)
241  BndSetRanges b(before[i]);
242  BndSetRanges s(sofarAfter);
243  LubRanges<View1> x1ub(x1);
246  BndSetRanges>, LubRanges<View1> > diff(inter, x1ub);
247  if (diff()) {
248  ModEvent me = (x0.include(home,iv[i].idx));
249  loopVar |= me_modified(me);
250  GECODE_ME_CHECK(me);
251 
252  // candidate != extra
253  me = iv[i].view.excludeI(home,diff);
254  loopVar |= me_modified(me);
255  GECODE_ME_CHECK(me);
256  }
257 
258  GlbRanges<View> ivilb(iv[i].view);
259  sofarAfter.intersectI(home,ivilb);
260  before[i].dispose(home);
261  }
262  sofarAfter.dispose(home);
263 
264  } while (loopVar);
265 
266  // Test whether we determined x0 without determining x1
267  if (x0.assigned() && !x1.assigned()) {
268  int ubsize = static_cast<int>(x0.lubSize());
269  if (ubsize > 2) {
270  assert(ubsize==n);
271  ViewArray<View> is(home,ubsize);
272  for (int i=n; i--;)
273  is[i]=iv[i].view;
275  ::post(home(*this),is,x1)));
276  } else if (ubsize == 2) {
277  assert(n==2);
278  View a = iv[0].view;
279  View b = iv[1].view;
281  ::post(home(*this),a,b,x1)));
282  } else if (ubsize == 1) {
283  assert(n==1);
284  GECODE_REWRITE(*this,
285  (Rel::Eq<View1,View>::post(home(*this),x1,iv[0].view)));
286  } else {
287  GECODE_ME_CHECK(x1.cardMax(home, 0));
288  return home.ES_SUBSUMED(*this);
289  }
290  }
291 
292  bool allAssigned = true;
293  for (int i=iv.size(); i--;) {
294  if (!iv[i].view.assigned()) {
295  allAssigned = false;
296  break;
297  }
298  }
299  if (x1.assigned() && x0.assigned() && allAssigned) {
300  return home.ES_SUBSUMED(*this);
301  }
302 
303  return ES_FIX;
304  }
305 
306 }}}
307 
308 // STATISTICS: set-prop