Generated on Mon Feb 8 2021 00:00:00 for Gecode by doxygen 1.8.20
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  * Contributing authors:
8  * Gabor Szokoli <szokoli@gecode.org>
9  *
10  * Copyright:
11  * Guido Tack, 2004
12  * Christian Schulte, 2004
13  * Gabor Szokoli, 2004
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 RelOp {
41 
42  /*
43  * "Ternary intersection" propagator
44  *
45  */
46 
47  template<class View0, class View1, class View2> ExecStatus
49  View0 x0,View1 x1,View2 x2) {
50  (void) new (home) Intersection<View0,View1,View2>(home,x0,x1,x2);
51  return ES_OK;
52  }
53 
54  template<class View0, class View1, class View2>
55  Actor*
57  return new (home) Intersection(home,*this);
58  }
59 
60  template<class View0, class View1, class View2>
63  // This propagator implements the constraint
64  // x2 = x0 \cap x1
65 
66  bool x0ass = x0.assigned();
67  bool x1ass = x1.assigned();
68  bool x2ass = x2.assigned();
69 
70  ModEvent me0 = View0::me(med);
71  ModEvent me1 = View1::me(med);
72  ModEvent me2 = View2::me(med);
73 
74  bool x0lbmod = false;
75  bool x1lbmod = false;
76  bool modified = false;
77 
78  do {
79 
80  modified = false;
81  do {
82  // 4) glb(x2) <= glb(x0) \cap glb(x1)
83  {
84  GlbRanges<View0> x0lb(x0);
85  GlbRanges<View1> x1lb(x1);
87  i2(x0lb,x1lb);
88  GECODE_ME_CHECK_MODIFIED(modified, x2.includeI(home,i2) );
89  }
90 
91  if (modified || Rel::testSetEventLB(me2) )
92  {
93  modified = false;
94  // 5) x2 <= x0
95  GlbRanges<View2> x2lb1(x2);
96  GECODE_ME_CHECK_MODIFIED(modified, x0.includeI(home,x2lb1) );
97  x0lbmod |= modified;
98 
99  // 6) x2 <= x1
100  bool modified2=false;
101  GlbRanges<View2> x2lb2(x2);
102  GECODE_ME_CHECK_MODIFIED(modified2, x1.includeI(home,x2lb2) );
103  x1lbmod |= modified2;
104  modified |= modified2;
105  }
106 
107  } while (modified);
108 
109  modified = false;
110  do {
111  bool modifiedOld = modified;
112  modified = false;
113 
115  || x0lbmod || modifiedOld)
116  {
117  // 1) lub(x2) \ glb(x0) => lub(x1)
118  GlbRanges<View0> x0lb(x0);
119  LubRanges<View2> x2ub(x2);
121  diff(x0lb, x2ub);
122  GECODE_ME_CHECK_MODIFIED(modified, x1.excludeI(home,diff) );
123  }
124 
126  || x1lbmod || modifiedOld)
127  {
128  // 2) lub(x2) \ glb(x1) => lub(x0)
129  GlbRanges<View1> x1lb(x1);
130  LubRanges<View2> x2ub(x2);
132  diff(x1lb, x2ub);
133  GECODE_ME_CHECK_MODIFIED(modified, x0.excludeI(home,diff) );
134  }
135 
136  if (Rel::testSetEventUB(me0,me1) || modified)
137  {
138  // modified = false;
139  // 3) lub(x0) \cap lub(x1) <= lub(x2)
140  LubRanges<View0> x0ub(x0);
141  LubRanges<View1> x1ub(x1);
143  i1(x0ub,x1ub);
144  GECODE_ME_CHECK_MODIFIED(modified, x2.intersectI(home,i1) );
145  }
146 
147  } while(modified);
148 
149  modified = false;
150  {
151  // cardinality
152  ExecStatus ret = interCard(home,modified, x0, x1, x2);
153  GECODE_ES_CHECK(ret);
154  }
155 
156  if (x2.cardMin() == Set::Limits::card) {
157  GECODE_ME_CHECK( x0.cardMin(home, Set::Limits::card) );
158  GECODE_ME_CHECK( x1.cardMin(home, Set::Limits::card) );
159  return home.ES_SUBSUMED(*this);
160  }
161 
162  if (x0.cardMin() == Set::Limits::card)
163  GECODE_REWRITE(*this,(Rel::Eq<View1,View2>::post(home(*this),x1,x2)));
164  if (x1.cardMin() == Set::Limits::card)
165  GECODE_REWRITE(*this,(Rel::Eq<View0,View2>::post(home(*this),x0,x2)));
166 
167  } while(modified);
168 
169  if (shared(x0,x1,x2)) {
170  return (x0ass && x1ass && x2ass) ? home.ES_SUBSUMED(*this) : ES_NOFIX;
171  } else {
172  if (x0ass && x1ass && x2ass)
173  return home.ES_SUBSUMED(*this);
174  if (x0ass != x0.assigned() ||
175  x1ass != x1.assigned() ||
176  x2ass != x2.assigned()) {
177  return ES_NOFIX;
178  } else {
179  return ES_FIX;
180  }
181  }
182  }
183 
184  template<class View0, class View1, class View2>
187  View0 y0,View1 y1,View2 y2)
189  View2,PC_SET_ANY>(home,y0,y1,y2) {}
190 
191  template<class View0, class View1, class View2>
196  View2,PC_SET_ANY>(home,p) {}
197 
198  /*
199  * "Nary intersection" propagator
200  *
201  */
202 
203  template<class View0, class View1>
206  View1 y)
207  : MixNaryOnePropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home,x,y),
208  intOfDets(home) {
210  }
211 
212  template<class View0, class View1>
215  const IntSet& z, View1 y)
216  : MixNaryOnePropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home,x,y),
217  intOfDets(home) {
219  IntSetRanges rz(z);
220  intOfDets.intersectI(home, rz);
221  }
222 
223  template<class View0, class View1>
226  IntersectionN& p)
227  : MixNaryOnePropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home,p),
228  shared(p.shared),
229  intOfDets() {
230  intOfDets.update(home, p.intOfDets);
231  }
232 
233  template<class View0, class View1>
234  ExecStatus
236  ViewArray<View0>& x, View1 y) {
237  switch (x.size()) {
238  case 0:
240  return ES_OK;
241  case 1:
242  return Rel::Eq<View0,View1>::post(home, x[0], y);
243  case 2:
244  return Intersection<View0,View0,View1>::post(home, x[0], x[1], y);
245  default:
246  (void) new (home) IntersectionN<View0,View1>(home,x,y);
247  return ES_OK;
248  }
249  }
250 
251  template<class View0, class View1>
252  ExecStatus
254  const IntSet& z, View1 y) {
255  (void) new (home) IntersectionN<View0,View1>(home,x,z,y);
256  return ES_OK;
257  }
258 
259  template<class View0, class View1>
260  Actor*
262  return new (home) IntersectionN<View0,View1>(home,*this);
263  }
264 
265  template<class View0, class View1>
266  PropCost
268  return PropCost::quadratic(PropCost::HI, x.size()+1);
269  }
270 
271  template<class View0, class View1>
272  ExecStatus
274  bool repeat = false;
275  do {
276  repeat = false;
277  int xsize = x.size();
278  if (xsize == 0)
279  goto size0;
280  for (int i = xsize; i--; ) {
281  GECODE_ME_CHECK( y.cardMax(home,x[i].cardMax()) );
282  GECODE_ME_CHECK( x[i].cardMin(home,y.cardMin()) );
283  if (x[i].cardMax()==0) {
284  GECODE_ME_CHECK( y.cardMax(home, 0));
285  intOfDets.dispose(home);
286  return home.ES_SUBSUMED(*this);
287  }
288  }
289  {
290  Region r;
291  GlbRanges<View0>* xLBs = r.alloc<GlbRanges<View0> >(xsize);
292  LubRanges<View0>* xUBs = r.alloc<LubRanges<View0> >(xsize);
293  for (int i = xsize; i--; ) {
294  GlbRanges<View0> lb(x[i]);
295  LubRanges<View0> ub(x[i]);
296  xLBs[i]=lb;
297  xUBs[i]=ub;
298  }
299  {
300  Iter::Ranges::NaryInter lbi(r,xLBs,xsize);
301  BndSetRanges dets(intOfDets);
302  lbi &= dets;
303  GECODE_ME_CHECK(y.includeI(home,lbi));
304  }
305  {
306  Iter::Ranges::NaryInter ubi(r,xUBs,xsize);
307  BndSetRanges dets(intOfDets);
308  ubi &= dets;
309  GECODE_ME_CHECK(y.intersectI(home,ubi));
310  }
311  }
312 
313  for (int i = xsize; i--; ) {
314  GlbRanges<View1> ylb(y);
315  GECODE_ME_CHECK( x[i].includeI(home,ylb) );
316  }
317 
318  // xi.exclude (Intersection(xj.lb) - y.ub)
319  {
320  Region r;
321  GLBndSet* rightSet =
322  static_cast<GLBndSet*>(r.ralloc(sizeof(GLBndSet)*xsize));
323  new (&rightSet[xsize-1]) GLBndSet(home);
324  rightSet[xsize-1].update(home,intOfDets);
325  for (int i=xsize-1;i--;) {
326  GlbRanges<View0> xilb(x[i+1]);
327  BndSetRanges prev(rightSet[i+1]);
329  BndSetRanges> inter(xilb,prev);
330  new (&rightSet[i]) GLBndSet(home);
331  rightSet[i].includeI(home,inter);
332  }
333 
334  LUBndSet leftAcc(home);
335 
336  for (int i=0;i<xsize;i++) {
337  BndSetRanges left(leftAcc);
338  BndSetRanges right(rightSet[i]);
340  BndSetRanges> inter(left, right);
341  LubRanges<View1> yub(y);
344  forbidden(inter, yub);
345  GECODE_ME_CHECK( x[i].excludeI(home,forbidden) );
346  GlbRanges<View0> xlb(x[i]);
347  leftAcc.intersectI(home,xlb);
348  }
349  for (int i=xsize; i--;)
350  rightSet[i].dispose(home);
351  leftAcc.dispose(home);
352  }
353 
354 
355  for(int i=0;i<x.size();i++) {
356  //Do not reverse! Eats away the end of the array!
357  while (i<x.size() && x[i].assigned()) {
358  GlbRanges<View0> det(x[i]);
359  if (intOfDets.intersectI(home,det)) {repeat = true;}
360  x.move_lst(i);
361  if (intOfDets.size()==0) {
362  GECODE_ME_CHECK( y.cardMax(home,0) );
363  intOfDets.dispose(home);
364  return home.ES_SUBSUMED(*this);
365  }
366  }
367  }
368  size0:
369  if (x.size()==0) {
370  BndSetRanges all1(intOfDets);
371  GECODE_ME_CHECK( y.intersectI(home,all1) );
372  BndSetRanges all2(intOfDets);
373  GECODE_ME_CHECK( y.includeI(home,all2) );
374  intOfDets.dispose(home);
375  return home.ES_SUBSUMED(*this);
376  }
377 
378  } while (repeat);
379 
380  return shared ? ES_NOFIX : ES_FIX;
381  }
382 
383 }}}
384 
385 // STATISTICS: set-prop
View1 y
Single view.
Definition: pattern.hpp:277
Propagator for nary intersection
Definition: rel-op.hh:183
Post propagator for SetVar x
Definition: set.hh:767
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:767
#define GECODE_ME_CHECK_MODIFIED(modified, me)
Check whether me is failed or modified, and forward failure.
Definition: macros.hpp:64
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: inter.hpp:267
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3563
bool includeI(Space &home, I &i)
Include the set represented by i in this set.
Definition: integerset.hpp:296
static ExecStatus post(Home home, View0 x, View1 y, View2 z)
Post propagator .
Definition: inter.hpp:48
bool intersectI(Space &home, I &i)
Exclude all elements not in the set represented by i from this set.
Definition: integerset.hpp:370
ViewArray< View0 > x
Array of views.
Definition: pattern.hpp:275
Post propagator for SetVar SetOpType SetVar SetRelType SetVar z
Definition: set.hh:767
unsigned int cardMin(void) const
Return cardinality minimum.
Definition: set.hpp:78
Propagator for set equality
Definition: rel.hh:150
bool shared(View0 v0, View1 v1, View2 v2)
Definition: common.hpp:84
bool viewarrayshared(const ViewArray< View0 > &va, const View1 &y)
Definition: common.hpp:47
Computation spaces.
Definition: core.hpp:1742
Base-class for both propagators and branchers.
Definition: core.hpp:628
static PropCost quadratic(PropCost::Mod m, unsigned int n)
Quadratic complexity for modifier m and size measure n.
Definition: core.hpp:4787
bool assigned(void) const
Test whether view is assigned.
Definition: var.hpp:111
Mixed (n+1)-ary propagator.
Definition: pattern.hpp:272
Range iterator for integer sets.
Definition: int.hh:292
Mixed ternary propagator.
Definition: pattern.hpp:237
Gecode toplevel namespace
Integer sets.
Definition: int.hh:174
bool testSetEventUB(ModEvent me0, ModEvent me1, ModEvent me2)
Definition: common.hpp:87
const unsigned int card
Maximum cardinality of an integer set.
Definition: set.hh:101
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition: macros.hpp:91
Propagator for ternary intersection
Definition: rel-op.hh:124
Home class for posting propagators
Definition: core.hpp:856
Handle to region.
Definition: region.hpp:55
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
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: inter.hpp:273
unsigned int cardMax(void) const
Return cardinality maximum.
Definition: set.hpp:81
Range iterator for the greatest lower bound.
Definition: var-imp.hpp:359
LUBndSet intOfDets
Intersection of the determined (which are dropped)
Definition: rel-op.hh:190
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition: inter.hpp:56
int ModEvent
Type for modification events.
Definition: core.hpp:62
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition: inter.hpp:261
void dispose(Space &home)
Free memory used by this set.
Definition: integerset.hpp:60
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: inter.hpp:62
Propagation cost.
Definition: core.hpp:486
Intersection(Space &home, Intersection &p)
Constructor for cloning p.
Definition: inter.hpp:193
bool shared(ViewArray< ViewX > x, ViewArray< ViewY > y)
Definition: array.hpp:1466
@ ES_FIX
Propagation has computed fixpoint.
Definition: core.hpp:477
Range iterator for the least upper bound.
Definition: var-imp.hpp:317
Range iterator for integer sets.
Definition: var-imp.hpp:185
Range iterator for intersection of iterators.
#define forceinline
Definition: config.hpp:192
Growing sets of integers.
Definition: var-imp.hpp:205
bool shared
Whether the any views share a variable implementation.
Definition: rel-op.hh:188
const Gecode::PropCond PC_SET_ANY
Propagate when any bound or the cardinality of a view changes.
Definition: var-type.hpp:248
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:52
bool testSetEventLB(ModEvent me0, ModEvent me1, ModEvent me2)
Definition: common.hpp:83
static ExecStatus post(Home home, ViewArray< View0 > &y, View1 x)
Post propagator .
Definition: inter.hpp:235
@ HI
Expensive.
Definition: core.hpp:514
ExecStatus interCard(Space &home, bool &retmodified, View0 &x0, View1 &x1, View2 &x2)
Definition: common.hpp:89
Shrinking sets of integers.
Definition: var-imp.hpp:243
IntersectionN(Space &home, IntersectionN &p)
Constructor for cloning p.
Definition: inter.hpp:225
int ModEventDelta
Modification event deltas.
Definition: core.hpp:89
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition: core.hpp:475
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
static ExecStatus post(Home home, View0 x, View1 y)
Post propagator .
Definition: eq.hpp:54
ExecStatus
Definition: core.hpp:472