Generated on Thu Jan 20 2022 00:00:00 for Gecode by doxygen 1.9.1
union.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 union" propagator
44  *
45  */
46 
47  template<class View0, class View1, class View2>
49  Union<View0,View1,View2>::Union(Home home, View0 y0,View1 y1,View2 y2)
51  View2,PC_SET_ANY>(home,y0,y1,y2) {}
52 
53  template<class View0, class View1, class View2>
58  View2,PC_SET_ANY>(home,p) {}
59 
60  template<class View0, class View1, class View2>
62  View1 x1, View2 x2) {
63  (void) new (home) Union<View0,View1,View2>(home,x0,x1,x2);
64  return ES_OK;
65  }
66 
67  template<class View0, class View1, class View2>
68  Actor*
70  return new (home) Union(home,*this);
71  }
72 
73  template<class View0, class View1, class View2>
76  // This propagator implements the constraint
77  // x2 = x0 u x1
78 
79  bool x0ass = x0.assigned();
80  bool x1ass = x1.assigned();
81  bool x2ass = x2.assigned();
82 
83  ModEvent me0 = View0::me(med);
84  ModEvent me1 = View1::me(med);
85  ModEvent me2 = View2::me(med);
86 
87  bool x0ubmod = false;
88  bool x1ubmod = false;
89  bool modified = false;
90 
91  do {
92 
93  modified = false;
94  do {
95  // 4) lub(x2) <= lub(x0) u lub(x1)
96  {
97  LubRanges<View0> x0ub(x0);
98  LubRanges<View1> x1ub(x1);
100  GECODE_ME_CHECK_MODIFIED(modified, x2.intersectI(home,u2) );
101  }
102 
103  if (modified || Rel::testSetEventUB(me2) )
104  {
105  modified = false;
106  // 5) x0 <= x2
107  LubRanges<View2> x2ub1(x2);
108  GECODE_ME_CHECK_MODIFIED(modified, x0.intersectI(home,x2ub1) );
109  x0ubmod |= modified;
110 
111  // 6) x1 <= x2
112  bool modified2=false;
113  LubRanges<View2> x2ub2(x2);
114  GECODE_ME_CHECK_MODIFIED(modified2, x1.intersectI(home,x2ub2) );
115  x1ubmod |= modified2;
116  modified |= modified2;
117  }
118 
119  } while (modified);
120 
121  modified = false;
122  do {
123  bool modifiedOld = modified;
124  modified = false;
125 
127  || x0ubmod || modifiedOld)
128  {
129  // 1) glb(x0) \ lub(x1) <= glb(x2)
130  GlbRanges<View2> x2lb(x2);
131  LubRanges<View0> x0ub(x0);
133  diff(x2lb, x0ub);
134  GECODE_ME_CHECK_MODIFIED(modified, x1.includeI(home,diff) );
135  }
136 
138  || x1ubmod || modifiedOld)
139  {
140  // 2) glb(x0) \ lub(x2) <= glb(x1)
141  GlbRanges<View2> x2lb(x2);
142  LubRanges<View1> x1ub(x1);
144  diff(x2lb, x1ub);
145  GECODE_ME_CHECK_MODIFIED(modified, x0.includeI(home,diff) );
146  }
147 
148  if (Rel::testSetEventLB(me0,me1) || modified)
149  {
150  // modified = false;
151  // 3) glb(x1) u glb(x2) <= glb(x0)
152  GlbRanges<View0> x0lb(x0);
153  GlbRanges<View1> x1lb(x1);
155  u1(x0lb,x1lb);
156  GECODE_ME_CHECK_MODIFIED(modified, x2.includeI(home,u1) );
157  }
158 
159  } while(modified);
160 
161  modified = false;
162  {
163  // cardinality
164  ExecStatus ret = unionCard(home,modified, x0, x1, x2);
165  GECODE_ES_CHECK(ret);
166  }
167 
168  if (x2.cardMax() == 0) {
169  GECODE_ME_CHECK( x0.cardMax(home, 0) );
170  GECODE_ME_CHECK( x1.cardMax(home, 0) );
171  return home.ES_SUBSUMED(*this);
172  }
173 
174  if (x0.cardMax() == 0)
175  GECODE_REWRITE(*this,(Rel::Eq<View1,View2>::post(home(*this),x1,x2)));
176  if (x1.cardMax() == 0)
177  GECODE_REWRITE(*this,(Rel::Eq<View0,View2>::post(home(*this),x0,x2)));
178 
179  } while(modified);
180 
181  if (shared(x0,x1,x2)) {
182  return (x0ass && x1ass && x2ass) ? home.ES_SUBSUMED(*this) : ES_NOFIX;
183  } else {
184  if (x0ass && x1ass && x2ass)
185  return home.ES_SUBSUMED(*this);
186  if (x0ass != x0.assigned() ||
187  x1ass != x1.assigned() ||
188  x2ass != x2.assigned()) {
189  return ES_NOFIX;
190  } else {
191  return ES_FIX;
192  }
193  }
194  }
195 
196 
197  /*
198  * "Nary union" propagator
199  *
200  */
201 
202  template<class View0, class View1>
205  : MixNaryOnePropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home,x,y) {
207  }
208 
209  template<class View0, class View1>
212  const IntSet& z, View1 y)
213  : MixNaryOnePropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home,x,y) {
215  IntSetRanges rz(z);
216  unionOfDets.includeI(home, rz);
217  }
218 
219  template<class View0, class View1>
222  : MixNaryOnePropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home,p),
223  shared(p.shared) {
224  unionOfDets.update(home,p.unionOfDets);
225  }
226 
227  template<class View0, class View1>
228  Actor*
230  return new (home) UnionN<View0,View1>(home,*this);
231  }
232 
233  template<class View0, class View1>
234  ExecStatus
236  switch (x.size()) {
237  case 0:
238  GECODE_ME_CHECK(y.cardMax(home, 0));
239  return ES_OK;
240  case 1:
241  return Rel::Eq<View0,View1>::post(home, x[0], y);
242  case 2:
243  return Union<View0,View0,View1>::post(home, x[0], x[1], y);
244  default:
245  (void) new (home) UnionN<View0,View1>(home,x,y);
246  return ES_OK;
247  }
248  }
249 
250  template<class View0, class View1>
251  ExecStatus
253  const IntSet& z, View1 y) {
254  (void) new (home) UnionN<View0,View1>(home,x,z,y);
255  return ES_OK;
256  }
257 
258  template<class View0, class View1>
259  PropCost
261  return PropCost::quadratic(PropCost::LO, x.size()+1);
262  }
263 
264  template<class View0, class View1>
265  ExecStatus
267  ModEvent me0 = View0::me(med);
268  ModEvent me1 = View1::me(med);
269  bool ubevent = Rel::testSetEventUB(me0, me1);
270  bool lbevent = Rel::testSetEventLB(me0, me1);
271  bool anybevent = Rel::testSetEventAnyB(me0, me1);
272  bool cardevent = Rel::testSetEventCard(me0, me1);
273 
274  bool modified = false;
275  bool oldModified = false;
276 
277  do {
278  do {
279  oldModified = modified;
280  modified = false;
281  if (modified || oldModified || ubevent)
282  GECODE_ES_CHECK(unionNXiUB(home, modified, x, y,unionOfDets));
283  if (modified || oldModified || ubevent)
284  GECODE_ES_CHECK(partitionNYUB(home, modified, x, y,unionOfDets));
285  if (modified || oldModified || anybevent)
286  GECODE_ES_CHECK(partitionNXiLB(home, modified, x, y,unionOfDets));
287  if (modified || oldModified || lbevent)
288  GECODE_ES_CHECK(partitionNYLB(home, modified, x, y,unionOfDets));
289  if (modified || oldModified || cardevent || ubevent) {
290  GECODE_ES_CHECK(unionNCard(home, modified, x, y, unionOfDets));
291  }
292  } while (modified);
293 
294  for(int i=0;i<x.size();i++) {
295  //Do not reverse! Eats away the end of the array!
296  while (i<x.size() && x[i].assigned()) {
297  GlbRanges<View0> det(x[i]);
298  unionOfDets.includeI(home,det);
299  x.move_lst(i);
300  modified = true;
301  }
302  }
303 
304  } while (modified);
305  // When we run out of variables, make a final check and disolve:
306  if (x.size()==0) {
307  BndSetRanges all1(unionOfDets);
308  GECODE_ME_CHECK( y.intersectI(home,all1) );
309  BndSetRanges all2(unionOfDets);
310  GECODE_ME_CHECK( y.includeI(home,all2) );
311  unionOfDets.dispose(home);
312  return home.ES_SUBSUMED(*this);
313  }
314 
315  return shared ? ES_NOFIX : ES_FIX;
316  }
317 
318 }}}
319 
320 // STATISTICS: set-prop
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:249
Base-class for both propagators and branchers.
Definition: core.hpp:628
Home class for posting propagators
Definition: core.hpp:856
Range iterator for integer sets.
Definition: int.hh:292
Integer sets.
Definition: int.hh:174
Range iterator for computing set difference.
Definition: ranges-diff.hpp:43
Range iterator for computing union (binary)
Mixed (n+1)-ary propagator.
Definition: pattern.hpp:272
Mixed ternary propagator.
Definition: pattern.hpp:237
Propagation cost.
Definition: core.hpp:486
static PropCost quadratic(PropCost::Mod m, unsigned int n)
Quadratic complexity for modifier m and size measure n.
Definition: core.hpp:4787
@ LO
Cheap.
Definition: core.hpp:513
unsigned int cardMax(void) const
Return cardinality maximum.
Definition: set.hpp:81
Range iterator for integer sets.
Definition: var-imp.hpp:185
void update(Space &home, BndSet &x)
Update this set to be a clone of set x.
Definition: integerset.hpp:140
bool includeI(Space &home, I &i)
Include the set represented by i in this set.
Definition: integerset.hpp:296
Range iterator for the greatest lower bound.
Definition: var-imp.hpp:359
Range iterator for the least upper bound.
Definition: var-imp.hpp:317
Propagator for nary union
Definition: rel-op.hh:219
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: union.hpp:260
static ExecStatus post(Home home, ViewArray< View0 > &y, View1 x)
Post propagator .
Definition: union.hpp:235
GLBndSet unionOfDets
Union of the determined (which are dropped)
Definition: rel-op.hh:226
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: union.hpp:266
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition: union.hpp:229
bool shared
Whether the any views share a variable implementation.
Definition: rel-op.hh:224
UnionN(Space &home, UnionN &p)
Constructor for cloning p.
Definition: union.hpp:221
Propagator for ternary union
Definition: rel-op.hh:154
static ExecStatus post(Home home, View0 x, View1 y, View2 z)
Post propagator .
Definition: union.hpp:61
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition: union.hpp:69
Union(Space &home, Union &p)
Constructor for cloning p.
Definition: union.hpp:55
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: union.hpp:75
Propagator for set equality
Definition: rel.hh:150
static ExecStatus post(Home home, View0 x, View1 y)
Post propagator .
Definition: eq.hpp:54
Computation spaces.
Definition: core.hpp:1742
ExecStatus
Definition: core.hpp:472
@ ES_OK
Execution is okay.
Definition: core.hpp:476
@ ES_FIX
Propagation has computed fixpoint.
Definition: core.hpp:477
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition: core.hpp:475
int ModEvent
Type for modification events.
Definition: core.hpp:62
Post propagator for SetVar SetOpType SetVar SetRelType SetVar z
Definition: set.hh:767
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:767
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3563
int ModEventDelta
Modification event deltas.
Definition: core.hpp:89
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:52
#define GECODE_REWRITE(prop, post)
Rewrite propagator by executing post function.
Definition: macros.hpp:116
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition: macros.hpp:91
#define GECODE_ME_CHECK_MODIFIED(modified, me)
Check whether me is failed or modified, and forward failure.
Definition: macros.hpp:64
bool shared(const IntSet &, VX)
Definition: view-base.hpp:118
bool shared(View0 v0, View1 v1, View2 v2)
Definition: common.hpp:84
ExecStatus partitionNYLB(Space &home, bool &modified, ViewArray< View0 > &x, View1 &y, GLBndSet &unionOfDets)
Definition: common.hpp:560
ExecStatus unionNCard(Space &home, bool &modified, ViewArray< View0 > &x, View1 &y, GLBndSet &unionOfDets)
Definition: common.hpp:193
ExecStatus unionNXiUB(Space &home, bool &modified, ViewArray< View0 > &x, View1 &y, GLBndSet &)
Definition: common.hpp:294
ExecStatus unionCard(Space &home, bool &retmodified, View0 &x0, View1 &x1, View2 &x2)
Definition: common.hpp:145
ExecStatus partitionNXiLB(Space &home, bool &modified, ViewArray< View0 > &x, View1 &y, GLBndSet &unionOfDets)
Definition: common.hpp:513
ExecStatus partitionNYUB(Space &home, bool &modified, ViewArray< View0 > &x, View1 &y, GLBndSet &unionOfDets)
Definition: common.hpp:587
bool testSetEventLB(ModEvent me0, ModEvent me1, ModEvent me2)
Definition: common.hpp:83
bool testSetEventCard(ModEvent me0, ModEvent me1, ModEvent me2)
Definition: common.hpp:95
bool testSetEventUB(ModEvent me0, ModEvent me1, ModEvent me2)
Definition: common.hpp:87
bool testSetEventAnyB(ModEvent me0, ModEvent me1, ModEvent me2)
Definition: common.hpp:91
const Gecode::PropCond PC_SET_ANY
Propagate when any bound or the cardinality of a view changes.
Definition: var-type.hpp:248
Gecode::IntArgs i({1, 2, 3, 4})
bool viewarrayshared(const ViewArray< View0 > &va, const View1 &y)
Definition: common.hpp:47
#define forceinline
Definition: config.hpp:194