Generated on Mon Jul 27 2020 00:00:00 for Gecode by doxygen 1.8.18
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  * 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  ElementIntersection(Home home, IdxViewArray& iv0, View0 y0, View1 y1,
42  const IntSet& theUniverse)
43  : Propagator(home), universe(theUniverse), iv(iv0), x0(y0), x1(y1) {
44  home.notice(*this,AP_DISPOSE);
45  x0.subscribe(home,*this, PC_SET_ANY);
46  x1.subscribe(home,*this, PC_SET_ANY);
47  iv.subscribe(home,*this, PC_SET_ANY);
48  }
49 
50  template<class View, class View0, class View1>
54  : Propagator(home,p), universe(p.universe) {
55  x0.update(home,p.x0);
56  x1.update(home,p.x1);
57  iv.update(home,p.iv);
58  }
59 
60  template<class View, class View0, class View1>
61  PropCost
63  const ModEventDelta&) const {
64  return PropCost::linear(PropCost::HI, iv.size()+2);
65  }
66 
67  template<class View, class View0, class View1>
68  void
70  x0.reschedule(home,*this, PC_SET_ANY);
71  x1.reschedule(home,*this, PC_SET_ANY);
72  iv.reschedule(home,*this, PC_SET_ANY);
73  }
74 
75  template<class View, class View0, class View1>
76  forceinline size_t
78  home.ignore(*this,AP_DISPOSE);
79  if (!home.failed()) {
80  x0.cancel(home,*this, PC_SET_ANY);
81  x1.cancel(home,*this, PC_SET_ANY);
82  iv.cancel(home,*this,PC_SET_ANY);
83  }
84  universe.~IntSet();
85  (void) Propagator::dispose(home);
86  return sizeof(*this);
87  }
88 
89  template<class View, class View0, class View1>
92  post(Home home, IdxViewArray& xs, View0 x0, View1 x1,
93  const IntSet& universe) {
94  int n = xs.size();
95 
96  // x0 \subseteq {1,...,n}
97  Iter::Ranges::Singleton s(0, n-1);
98  GECODE_ME_CHECK(x0.intersectI(home,s));
99  (void) new (home)
100  ElementIntersection<View,View0,View1>(home,xs,x0,x1,universe);
101  return ES_OK;
102  }
103 
104  template<class View, class View0, class View1>
105  Actor*
107  return new (home) ElementIntersection<View,View0,View1>(home,*this);
108  }
109 
110  template<class View, class View0, class View1>
111  ExecStatus
113  const ModEventDelta&) {
114  Region r;
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 intersection
132  // of all the lower 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  LUBndSet sofarBefore(home,universe);
137  LUBndSet* before = r.alloc<LUBndSet>(n);
138 
139  int j = 0;
140  int i = 0;
141  while ( vx0ub() ) {
142 
143  // Remove vars at indices not in the upper bound
144  if (iv[i].idx < vx0ub.val()) {
145  iv[i].view.cancel(home,*this, PC_SET_ANY);
146  ++i;
147  continue;
148  }
149  assert(iv[i].idx == vx0ub.val());
150  iv[j] = iv[i];
151 
152  View candidate = iv[j].view;
153  int candidateInd = iv[j].idx;
154 
155  // inter = glb(x1) & complement(lub(candidate))
156  GlbRanges<View1> x1lb(x1);
157  LubRanges<View> candub(candidate);
159  inter(x1lb, candub);
160 
161  // exclude inconsistent x_i
162  // an x_i is inconsistent if
163  // * its max cardinality is less than minCard of x1
164  // * inter is not empty (there are elements in x_0
165  // that can't be in x_i)
166  if (candidate.cardMax() < x1.cardMin() ||
167  inter()) {
168  ModEvent me = (x0.exclude(home,candidateInd));
169  loopVar |= me_modified(me);
170  GECODE_ME_CHECK(me);
171 
172  iv[j].view.cancel(home,*this, PC_SET_ANY);
173  ++i;
174  ++vx0ub;
175  continue;
176  } else {
177  // if x_i is consistent, check whether we know
178  // that its index is in x0
179  if (vx0() && vx0.val()==candidateInd) {
180  // x1 <= candidate, candidate >= x1
181  GlbRanges<View1> x1lb(x1);
182  ModEvent me = candidate.includeI(home,x1lb);
183  loopVar |= me_modified(me);
184  GECODE_ME_CHECK(me);
185 
186  LubRanges<View> candub(candidate);
187  me = x1.intersectI(home,candub);
188  loopVar |= me_modified(me);
189  GECODE_ME_CHECK(me);
190  ++vx0;
191  }
192  new (&before[j]) LUBndSet(home);
193  before[j].update(home,sofarBefore);
194  GlbRanges<View> clb(candidate);
195  sofarBefore.intersectI(home,clb);
196  }
197 
198  ++vx0ub;
199  ++i; ++j;
200  }
201 
202  // cancel the variables with index greater than
203  // max of lub(x0)
204  for (int k=i; k<n; k++) {
205  iv[k].view.cancel(home,*this, PC_SET_ANY);
206  }
207  n = j;
208  iv.size(n);
209 
210  if (x0.cardMax()==0) {
211  // Elementor is empty, hence the result must be universe
212  {
213  IntSetRanges uniI(universe);
214  GECODE_ME_CHECK(x1.includeI(home,uniI));
215  }
216  {
217  IntSetRanges uniI(universe);
218  GECODE_ME_CHECK(x1.intersectI(home,uniI));
219  }
220  for (int i=n; i--;)
221  before[i].dispose(home);
222  return home.ES_SUBSUMED(*this);
223  }
224 
225  {
226  // x1 >= sofarBefore
227  BndSetRanges sfB(sofarBefore);
228  ModEvent me = x1.includeI(home,sfB);
229  loopVar |= me_modified(me);
230  GECODE_ME_CHECK(me);
231  }
232 
233  sofarBefore.dispose(home);
234 
235  LUBndSet sofarAfter(home, universe);
236 
237  // In the second iteration, this time backwards, compute
238  // sofarAfter as the intersection of all glb(x_j) with j>i
239  for (int i=n; i--;) {
240  if (sofarAfter.size() == 0) break;
241 
242  // extra = inter(before[i], sofarAfter) - lub(x1)
243  BndSetRanges b(before[i]);
244  BndSetRanges s(sofarAfter);
245  LubRanges<View1> x1ub(x1);
248  BndSetRanges>, LubRanges<View1> > diff(inter, x1ub);
249  if (diff()) {
250  ModEvent me = (x0.include(home,iv[i].idx));
251  loopVar |= me_modified(me);
252  GECODE_ME_CHECK(me);
253 
254  // candidate != extra
255  me = iv[i].view.excludeI(home,diff);
256  loopVar |= me_modified(me);
257  GECODE_ME_CHECK(me);
258  }
259 
260  GlbRanges<View> ivilb(iv[i].view);
261  sofarAfter.intersectI(home,ivilb);
262  before[i].dispose(home);
263  }
264  sofarAfter.dispose(home);
265 
266  } while (loopVar);
267 
268  // Test whether we determined x0 without determining x1
269  if (x0.assigned() && !x1.assigned()) {
270  int ubsize = static_cast<int>(x0.lubSize());
271  if (ubsize > 2) {
272  assert(ubsize==n);
273  ViewArray<View> is(home,ubsize);
274  for (int i=n; i--;)
275  is[i]=iv[i].view;
277  ::post(home(*this),is,x1)));
278  } else if (ubsize == 2) {
279  assert(n==2);
280  View a = iv[0].view;
281  View b = iv[1].view;
283  ::post(home(*this),a,b,x1)));
284  } else if (ubsize == 1) {
285  assert(n==1);
286  GECODE_REWRITE(*this,
287  (Rel::Eq<View1,View>::post(home(*this),x1,iv[0].view)));
288  } else {
289  GECODE_ME_CHECK(x1.cardMax(home, 0));
290  return home.ES_SUBSUMED(*this);
291  }
292  }
293 
294  bool allAssigned = true;
295  for (int i=iv.size(); i--;) {
296  if (!iv[i].view.assigned()) {
297  allAssigned = false;
298  break;
299  }
300  }
301  if (x1.assigned() && x0.assigned() && allAssigned) {
302  return home.ES_SUBSUMED(*this);
303  }
304 
305  return ES_FIX;
306  }
307 
308 }}}
309 
310 // STATISTICS: set-prop
Propagator for nary intersection
Definition: rel-op.hh:183
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition: core.hpp:3219
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3563
Propagator for element with intersection
Definition: element.hh:78
An array of IdxView pairs.
Definition: idx-view.hh:67
IdxViewArray iv
Definition: element.hh:83
bool intersectI(Space &home, I &i)
Exclude all elements not in the set represented by i from this set.
Definition: integerset.hpp:370
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: inter.hpp:62
void update(Space &home, IdxViewArray< View > &x)
Cloning.
Definition: idx-view.hpp:153
static ExecStatus post(Home home, IdxViewArray &x, View0 y, View1 z, const IntSet &u)
Definition: inter.hpp:92
Propagator for set equality
Definition: rel.hh:150
Computation spaces.
Definition: core.hpp:1742
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition: core.hpp:4796
Base-class for both propagators and branchers.
Definition: core.hpp:628
int val(void) const
Return current value.
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition: inter.hpp:106
virtual void reschedule(Space &home)
Schedule function.
Definition: inter.hpp:69
Range iterator for integer sets.
Definition: int.hh:292
Gecode toplevel namespace
Base-class for propagators.
Definition: core.hpp:1064
Integer sets.
Definition: int.hh:174
Propagator for ternary intersection
Definition: rel-op.hh:124
Home class for posting propagators
Definition: core.hpp:856
unsigned int size(void) const
Return size.
Definition: integerset.hpp:93
Value iterator from range iterator.
Handle to region.
Definition: region.hpp:55
@ AP_DISPOSE
Actor must always be disposed.
Definition: core.hpp:562
Range iterator for computing intersection (binary)
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
Range iterator for computing set difference.
Definition: ranges-diff.hpp:43
void update(Space &home, BndSet &x)
Update this set to be a clone of set x.
Definition: integerset.hpp:140
TFE post(PropagatorGroup g)
Only post functions (but not propagators) from g are considered.
Definition: filter.cpp:138
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: inter.hpp:112
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
Range iterator for the greatest lower bound.
Definition: var-imp.hpp:359
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: inter.hpp:77
ElementIntersection(Space &home, ElementIntersection &p)
Constructor for cloning p.
Definition: inter.hpp:53
int size(void) const
Return the current size.
Definition: idx-view.hpp:105
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
int ModEvent
Type for modification events.
Definition: core.hpp:62
void dispose(Space &home)
Free memory used by this set.
Definition: integerset.hpp:60
Range iterator cache
bool failed(void) const
Check whether space is failed.
Definition: core.hpp:4044
Propagation cost.
Definition: core.hpp:486
@ ES_FIX
Propagation has computed fixpoint.
Definition: core.hpp:477
Range iterator for the least upper bound.
Definition: var-imp.hpp:317
void subscribe(Space &home, Propagator &p, PropCond pc, bool process=true)
Definition: idx-view.hpp:131
Range iterator for integer sets.
Definition: var-imp.hpp:185
#define forceinline
Definition: config.hpp:185
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 singleton range.
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition: core.hpp:4074
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:52
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:3252
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition: modevent.hpp:59
@ HI
Expensive.
Definition: core.hpp:514
View arrays.
Definition: array.hpp:253
Shrinking sets of integers.
Definition: var-imp.hpp:243
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
View0 x0
Definition: element.hh:84
View1 x1
Definition: element.hh:85
int ModEventDelta
Modification event deltas.
Definition: core.hpp:89
Gecode::IntArgs i({1, 2, 3, 4})
SetExpr inter(const SetVarArgs &x)
Intersection of set variables.
Definition: set-expr.cpp:696
#define GECODE_REWRITE(prop, post)
Rewrite propagator by executing post function.
Definition: macros.hpp:116
@ ES_OK
Execution is okay.
Definition: core.hpp:476
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
ExecStatus
Definition: core.hpp:472