Generated on Sat Feb 7 2015 02:01:29 for Gecode by doxygen 1.8.9.1
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  * Last modified:
16  * $Date: 2012-09-07 17:31:22 +0200 (Fri, 07 Sep 2012) $ by $Author: schulte $
17  * $Revision: 13068 $
18  *
19  * This file is part of Gecode, the generic constraint
20  * development environment:
21  * http://www.gecode.org
22  *
23  * Permission is hereby granted, free of charge, to any person obtaining
24  * a copy of this software and associated documentation files (the
25  * "Software"), to deal in the Software without restriction, including
26  * without limitation the rights to use, copy, modify, merge, publish,
27  * distribute, sublicense, and/or sell copies of the Software, and to
28  * permit persons to whom the Software is furnished to do so, subject to
29  * the following conditions:
30  *
31  * The above copyright notice and this permission notice shall be
32  * included in all copies or substantial portions of the Software.
33  *
34  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
35  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
36  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
37  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
38  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
39  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
40  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
41  *
42  */
43 
44 namespace Gecode { namespace Set { namespace RelOp {
45 
46  /*
47  * "Ternary intersection" propagator
48  *
49  */
50 
51  template<class View0, class View1, class View2> ExecStatus
53  View0 x0,View1 x1,View2 x2) {
54  (void) new (home) Intersection<View0,View1,View2>(home,x0,x1,x2);
55  return ES_OK;
56  }
57 
58  template<class View0, class View1, class View2>
59  Actor*
61  return new (home) Intersection(home,share,*this);
62  }
63 
64  template<class View0, class View1, class View2>
67  // This propagator implements the constraint
68  // x2 = x0 \cap x1
69 
70  bool x0ass = x0.assigned();
71  bool x1ass = x1.assigned();
72  bool x2ass = x2.assigned();
73 
74  ModEvent me0 = View0::me(med);
75  ModEvent me1 = View1::me(med);
76  ModEvent me2 = View2::me(med);
77 
78  bool x0lbmod = false;
79  bool x1lbmod = false;
80  bool modified = false;
81 
82  do {
83 
84  modified = false;
85  do {
86  // 4) glb(x2) <= glb(x0) \cap glb(x1)
87  {
88  GlbRanges<View0> x0lb(x0);
89  GlbRanges<View1> x1lb(x1);
91  i2(x0lb,x1lb);
92  GECODE_ME_CHECK_MODIFIED(modified, x2.includeI(home,i2) );
93  }
94 
95  if (modified || Rel::testSetEventLB(me2) )
96  {
97  modified = false;
98  // 5) x2 <= x0
99  GlbRanges<View2> x2lb1(x2);
100  GECODE_ME_CHECK_MODIFIED(modified, x0.includeI(home,x2lb1) );
101  x0lbmod |= modified;
102 
103  // 6) x2 <= x1
104  bool modified2=false;
105  GlbRanges<View2> x2lb2(x2);
106  GECODE_ME_CHECK_MODIFIED(modified2, x1.includeI(home,x2lb2) );
107  x1lbmod |= modified2;
108  modified |= modified2;
109  }
110 
111  } while (modified);
112 
113  modified = false;
114  do {
115  bool modifiedOld = modified;
116  modified = false;
117 
119  || x0lbmod || modifiedOld)
120  {
121  // 1) lub(x2) \ glb(x0) => lub(x1)
122  GlbRanges<View0> x0lb(x0);
123  LubRanges<View2> x2ub(x2);
125  diff(x0lb, x2ub);
126  GECODE_ME_CHECK_MODIFIED(modified, x1.excludeI(home,diff) );
127  }
128 
130  || x1lbmod || modifiedOld)
131  {
132  // 2) lub(x2) \ glb(x1) => lub(x0)
133  GlbRanges<View1> x1lb(x1);
134  LubRanges<View2> x2ub(x2);
136  diff(x1lb, x2ub);
137  GECODE_ME_CHECK_MODIFIED(modified, x0.excludeI(home,diff) );
138  }
139 
140  if (Rel::testSetEventUB(me0,me1) || modified)
141  {
142  // modified = false;
143  // 3) lub(x0) \cap lub(x1) <= lub(x2)
144  LubRanges<View0> x0ub(x0);
145  LubRanges<View1> x1ub(x1);
147  i1(x0ub,x1ub);
148  GECODE_ME_CHECK_MODIFIED(modified, x2.intersectI(home,i1) );
149  }
150 
151  } while(modified);
152 
153  modified = false;
154  {
155  // cardinality
156  ExecStatus ret = interCard(home,modified, x0, x1, x2);
157  GECODE_ES_CHECK(ret);
158  }
159 
160  if (x2.cardMin() == Set::Limits::card) {
161  GECODE_ME_CHECK( x0.cardMin(home, Set::Limits::card) );
162  GECODE_ME_CHECK( x1.cardMin(home, Set::Limits::card) );
163  return home.ES_SUBSUMED(*this);
164  }
165 
166  if (x0.cardMin() == Set::Limits::card)
167  GECODE_REWRITE(*this,(Rel::Eq<View1,View2>::post(home(*this),x1,x2)));
168  if (x1.cardMin() == Set::Limits::card)
169  GECODE_REWRITE(*this,(Rel::Eq<View0,View2>::post(home(*this),x0,x2)));
170 
171  } while(modified);
172 
173  if (shared(x0,x1,x2)) {
174  return (x0ass && x1ass && x2ass) ? home.ES_SUBSUMED(*this) : ES_NOFIX;
175  } else {
176  if (x0ass && x1ass && x2ass)
177  return home.ES_SUBSUMED(*this);
178  if (x0ass != x0.assigned() ||
179  x1ass != x1.assigned() ||
180  x2ass != x2.assigned()) {
181  return ES_NOFIX;
182  } else {
183  return ES_FIX;
184  }
185  }
186  }
187 
188  template<class View0, class View1, class View2>
191  View0 y0,View1 y1,View2 y2)
193  View2,PC_SET_ANY>(home,y0,y1,y2) {}
194 
195  template<class View0, class View1, class View2>
200  View2,PC_SET_ANY>(home,share,p) {}
201 
202  /*
203  * "Nary intersection" propagator
204  *
205  */
206 
207  template<class View0, class View1>
210  View1 y)
211  : MixNaryOnePropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home,x,y),
212  intOfDets(home) {
213  shared = x.shared(home) || viewarrayshared(home,x,y);
214  }
215 
216  template<class View0, class View1>
219  const IntSet& z, View1 y)
220  : MixNaryOnePropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home,x,y),
221  intOfDets(home) {
222  shared = x.shared(home) || viewarrayshared(home,x,y);
223  IntSetRanges rz(z);
224  intOfDets.intersectI(home, rz);
225  }
226 
227  template<class View0, class View1>
230  IntersectionN& p)
231  : MixNaryOnePropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home,share,p),
232  shared(p.shared),
233  intOfDets() {
234  intOfDets.update(home, p.intOfDets);
235  }
236 
237  template<class View0, class View1>
238  ExecStatus
240  ViewArray<View0>& x, View1 y) {
241  switch (x.size()) {
242  case 0:
243  GECODE_ME_CHECK(y.cardMin(home, Limits::card));
244  return ES_OK;
245  case 1:
246  return Rel::Eq<View0,View1>::post(home, x[0], y);
247  case 2:
248  return Intersection<View0,View0,View1>::post(home, x[0], x[1], y);
249  default:
250  (void) new (home) IntersectionN<View0,View1>(home,x,y);
251  return ES_OK;
252  }
253  }
254 
255  template<class View0, class View1>
256  ExecStatus
258  const IntSet& z, View1 y) {
259  (void) new (home) IntersectionN<View0,View1>(home,x,z,y);
260  return ES_OK;
261  }
262 
263  template<class View0, class View1>
264  Actor*
266  return new (home) IntersectionN<View0,View1>(home,share,*this);
267  }
268 
269  template<class View0, class View1>
270  PropCost
272  return PropCost::quadratic(PropCost::HI, x.size()+1);
273  }
274 
275  template<class View0, class View1>
276  ExecStatus
278  bool repeat = false;
279  do {
280  repeat = false;
281  int xsize = x.size();
282  if (xsize == 0)
283  goto size0;
284  for (int i = xsize; i--; ) {
285  GECODE_ME_CHECK( y.cardMax(home,x[i].cardMax()) );
286  GECODE_ME_CHECK( x[i].cardMin(home,y.cardMin()) );
287  if (x[i].cardMax()==0) {
288  GECODE_ME_CHECK( y.cardMax(home, 0));
289  intOfDets.dispose(home);
290  return home.ES_SUBSUMED(*this);
291  }
292  }
293  {
294  Region r(home);
295  GlbRanges<View0>* xLBs = r.alloc<GlbRanges<View0> >(xsize);
296  LubRanges<View0>* xUBs = r.alloc<LubRanges<View0> >(xsize);
297  for (int i = xsize; i--; ) {
298  GlbRanges<View0> lb(x[i]);
299  LubRanges<View0> ub(x[i]);
300  xLBs[i]=lb;
301  xUBs[i]=ub;
302  }
303  {
304  Iter::Ranges::NaryInter lbi(r,xLBs,xsize);
305  BndSetRanges dets(intOfDets);
306  lbi &= dets;
307  GECODE_ME_CHECK(y.includeI(home,lbi));
308  }
309  {
310  Iter::Ranges::NaryInter ubi(r,xUBs,xsize);
311  BndSetRanges dets(intOfDets);
312  ubi &= dets;
313  GECODE_ME_CHECK(y.intersectI(home,ubi));
314  }
315  }
316 
317  for (int i = xsize; i--; ) {
318  GlbRanges<View1> ylb(y);
319  GECODE_ME_CHECK( x[i].includeI(home,ylb) );
320  }
321 
322  // xi.exclude (Intersection(xj.lb) - y.ub)
323  {
324  Region r(home);
325  GLBndSet* rightSet =
326  static_cast<GLBndSet*>(r.ralloc(sizeof(GLBndSet)*xsize));
327  new (&rightSet[xsize-1]) GLBndSet(home);
328  rightSet[xsize-1].update(home,intOfDets);
329  for (int i=xsize-1;i--;) {
330  GlbRanges<View0> xilb(x[i+1]);
331  BndSetRanges prev(rightSet[i+1]);
333  BndSetRanges> inter(xilb,prev);
334  new (&rightSet[i]) GLBndSet(home);
335  rightSet[i].includeI(home,inter);
336  }
337 
338  LUBndSet leftAcc(home);
339 
340  for (int i=0;i<xsize;i++) {
341  BndSetRanges left(leftAcc);
342  BndSetRanges right(rightSet[i]);
344  BndSetRanges> inter(left, right);
345  LubRanges<View1> yub(y);
347  BndSetRanges>, LubRanges<View1> >
348  forbidden(inter, yub);
349  GECODE_ME_CHECK( x[i].excludeI(home,forbidden) );
350  GlbRanges<View0> xlb(x[i]);
351  leftAcc.intersectI(home,xlb);
352  }
353  for (int i=xsize; i--;)
354  rightSet[i].dispose(home);
355  leftAcc.dispose(home);
356  }
357 
358 
359  for(int i=0;i<x.size();i++){
360  //Do not reverse! Eats away the end of the array!
361  while (i<x.size() && x[i].assigned()) {
362  GlbRanges<View0> det(x[i]);
363  if (intOfDets.intersectI(home,det)) {repeat = true;}
364  x.move_lst(i);
365  if (intOfDets.size()==0) {
366  GECODE_ME_CHECK( y.cardMax(home,0) );
367  intOfDets.dispose(home);
368  return home.ES_SUBSUMED(*this);
369  }
370  }
371  }
372  size0:
373  if (x.size()==0) {
374  BndSetRanges all1(intOfDets);
375  GECODE_ME_CHECK( y.intersectI(home,all1) );
376  BndSetRanges all2(intOfDets);
377  GECODE_ME_CHECK( y.includeI(home,all2) );
378  intOfDets.dispose(home);
379  return home.ES_SUBSUMED(*this);
380  }
381 
382  } while (repeat);
383 
384  return shared ? ES_NOFIX : ES_FIX;
385  }
386 
387 }}}
388 
389 // STATISTICS: set-prop
virtual Actor * copy(Space &home, bool)
Copy propagator during cloning.
Definition: inter.hpp:60
#define GECODE_REWRITE(prop, post)
Rewrite propagator by executing post function.
Definition: macros.hpp:109
IntersectionN(Space &home, bool share, IntersectionN &p)
Constructor for cloning p.
Definition: inter.hpp:229
static PropCost quadratic(PropCost::Mod m, unsigned int n)
Quadratic complexity for modifier m and size measure n.
Definition: core.hpp:4032
bool shared
Whether the any views share a variable implementation.
Definition: rel-op.hh:192
Range iterator for integer sets.
Definition: int.hh:271
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:2973
static ExecStatus post(Home home, ViewArray< View0 > &y, View1 x)
Post propagator .
Definition: inter.hpp:239
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition: region.hpp:326
Intersection(Space &home, bool share, Intersection &p)
Constructor for cloning p.
Definition: inter.hpp:197
Shrinking sets of integers.
Definition: var-imp.hpp:247
Mixed (n+1)-ary propagator.
Definition: propagator.hpp:268
int ModEvent
Type for modification events.
Definition: core.hpp:146
virtual Actor * copy(Space &home, bool)
Copy propagator during cloning.
Definition: inter.hpp:265
Expensive.
Definition: core.hpp:564
Range iterator for the greatest lower bound.
Definition: var-imp.hpp:363
ExecStatus interCard(Space &home, bool &retmodified, View0 &x0, View1 &x1, View2 &x2)
Definition: common.hpp:94
Handle to region.
Definition: region.hpp:61
Propagation has computed fixpoint.
Definition: core.hpp:528
const unsigned int card
Maximum cardinality of an integer set.
Definition: set.hh:103
Computation spaces.
Definition: core.hpp:1362
#define GECODE_ME_CHECK_MODIFIED(modified, me)
Check whether me is failed or modified, and forward failure.
Definition: macros.hpp:57
Range iterator for the least upper bound.
Definition: var-imp.hpp:321
Base-class for both propagators and branchers.
Definition: core.hpp:666
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition: macros.hpp:84
static ExecStatus post(Home home, View0 x, View1 y, View2 z)
Post propagator .
Definition: inter.hpp:52
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: inter.hpp:66
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Gecode::IntArgs i(4, 1, 2, 3, 4)
Range iterator for computing intersection (binary)
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
Mixed ternary propagator.
Definition: propagator.hpp:235
bool shared(const Space &home) const
Test whether array contains shared views.
Definition: array.hpp:1511
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as low linear)
Definition: inter.hpp:271
bool intersectI(Space &home, I &i)
Exclude all elements not in the set represented by i from this set.
Definition: integerset.hpp:374
Range iterator for integer sets.
Definition: var-imp.hpp:189
LUBndSet intOfDets
Intersection of the determined (which are dropped)
Definition: rel-op.hh:194
Integer sets.
Definition: int.hh:171
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:45
bool includeI(Space &home, I &i)
Include the set represented by i in this set.
Definition: integerset.hpp:300
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
bool shared(View0 v0, View1 v1, View2 v2)
Definition: common.hpp:89
SetExpr inter(const SetVarArgs &x)
Intersection of set variables.
Definition: set-expr.cpp:696
bool testSetEventLB(ModEvent me0, ModEvent me1, ModEvent me2)
Definition: common.hpp:75
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
Range iterator for intersection of iterators.
Propagation cost.
Definition: core.hpp:537
ExecStatus
Definition: core.hpp:523
#define forceinline
Definition: config.hpp:132
Growing sets of integers.
Definition: var-imp.hpp:209
Propagator for set equality
Definition: rel.hh:146
Execution is okay.
Definition: core.hpp:527
Propagation has not computed fixpoint.
Definition: core.hpp:526
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1215
Gecode toplevel namespace
bool testSetEventUB(ModEvent me0, ModEvent me1, ModEvent me2)
Definition: common.hpp:79
Range iterator for computing set difference.
Definition: ranges-diff.hpp:47
int ModEventDelta
Modification event deltas.
Definition: core.hpp:173
Home class for posting propagators
Definition: core.hpp:717
static ExecStatus post(Home home, View0, View1)
Post propagator .
Definition: eq.hpp:58
void * ralloc(size_t s)
Allocate memory from region.
Definition: region.hpp:302
Propagator for nary intersection
Definition: rel-op.hh:186
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: inter.hpp:277
bool viewarrayshared(const Space &home, const ViewArray< View0 > &va, const View1 &y)
Definition: common.hpp:51
Propagator for ternary intersection
Definition: rel-op.hh:126