Generated on Tue Jan 28 2020 00:00:00 for Gecode by doxygen 1.8.17
disjoint.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: 2016-06-29 17:28:17 +0200 (Wed, 29 Jun 2016) $ by $Author: schulte $
13  * $Revision: 15137 $
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 SView, class RView>
45  IdxViewArray& iv0,
46  RView y1)
47  : Propagator(home), iv(iv0), x1(y1) {
48 
49  x1.subscribe(home,*this, PC_SET_ANY);
50  iv.subscribe(home,*this, PC_SET_ANY);
51  }
52 
53  template<class SView, class RView>
57  : Propagator(home,share,p) {
58  x1.update(home,share,p.x1);
59  iv.update(home,share,p.iv);
60  }
61 
62  template<class SView, class RView>
65  RView x1) {
66  int n = xs.size();
67 
68  // s2 \subseteq {0,...,n-1}
69  Iter::Ranges::Singleton s(0, n-1);
70  GECODE_ME_CHECK(x1.intersectI(home,s));
71  (void) new (home)
72  ElementDisjoint(home,xs,x1);
73  return ES_OK;
74  }
75 
76  template<class SView, class RView>
77  PropCost
79  return PropCost::quadratic(PropCost::LO, iv.size()+2);
80  }
81 
82  template<class SView, class RView>
83  void
85  x1.reschedule(home,*this, PC_SET_ANY);
86  iv.reschedule(home,*this, PC_SET_ANY);
87  }
88 
89  template<class SView, class RView>
90  forceinline size_t
92  x1.cancel(home,*this, PC_SET_ANY);
93  iv.cancel(home,*this,PC_SET_ANY);
94  (void) Propagator::dispose(home);
95  return sizeof(*this);
96  }
97 
98  template<class SView, class RView>
99  Actor*
101  return new (home) ElementDisjoint(home,share,*this);
102  }
103 
104  template<class SView, class RView>
105  ExecStatus
107  int n = iv.size();
108 
109  Region r(home);
110 
111  bool fix_flag = false;
112  do {
113  fix_flag = false;
114  // Compute union of all selected elements' lower bounds
115  GlbRanges<RView> x1lb(x1);
117  GLBndSet unionOfSelected(home);
118  for(int i=0; vx1lb(); ++vx1lb) {
119  while (iv[i].idx < vx1lb.val()) i++;
120  GlbRanges<SView> clb(iv[i].view);
121  unionOfSelected.includeI(home,clb);
122  }
123 
124  {
125  LubRanges<RView> x1ub(x1);
127  int i=0;
128  int j=0;
129  // Cancel all elements that are no longer in the upper bound
130  while (vx1ub()) {
131  if (iv[i].idx < vx1ub.val()) {
132  iv[i].view.cancel(home,*this, PC_SET_ANY);
133  i++;
134  continue;
135  }
136  iv[j] = iv[i];
137  ++vx1ub;
138  ++i; ++j;
139  }
140 
141  // cancel the variables with index greater than
142  // max of lub(x1)
143  for (int k=i; k<n; k++) {
144  iv[k].view.cancel(home,*this, PC_SET_ANY);
145  }
146  n = j;
147  iv.size(n);
148  }
149 
150  {
151  UnknownRanges<RView> x1u(x1);
152  Iter::Ranges::Cache x1uc(r,x1u);
154  vx1u(x1uc);
155  int i=0;
156  int j=0;
157  while (vx1u()) {
158  while (iv[i].idx < vx1u.val()) {
159  iv[j] = iv[i];
160  i++; j++;
161  }
162  assert(iv[i].idx == vx1u.val());
163 
164  SView candidate = iv[i].view;
165  int candidateInd = iv[i].idx;
166 
167  GlbRanges<SView> clb(candidate);
168  BndSetRanges uos(unionOfSelected);
170  inter(clb, uos);
171  if (inter()) {
172  ModEvent me = x1.exclude(home,candidateInd);
173  fix_flag |= me_modified(me);
174  GECODE_ME_CHECK(me);
175 
176  candidate.cancel(home,*this, PC_SET_ANY);
177  ++i;
178  ++vx1u;
179  continue;
180  }
181  iv[j] = iv[i];
182  ++vx1u;
183  ++i; ++j;
184  }
185 
186  unionOfSelected.dispose(home);
187 
188  // copy remaining variables
189  for (int k=i; k<n; k++) {
190  iv[j] = iv[k];
191  j++;
192  }
193  n = j;
194  iv.size(n);
195  }
196 
197  if (x1.cardMax()==0) {
198  // Selector is empty, we're done
199  return home.ES_SUBSUMED(*this);
200  }
201 
202  {
203  // remove all elements in a selected variable from
204  // all other selected variables
205  GlbRanges<RView> x1lb(x1);
207  int i=0;
208  for (; vx1lb(); ++vx1lb) {
209  while (iv[i].idx < vx1lb.val()) i++;
210  assert(iv[i].idx==vx1lb.val());
211  GlbRanges<RView> x1lb2(x1);
213  for (int j=0; vx1lb2(); ++vx1lb2) {
214  while (iv[j].idx < vx1lb2.val()) j++;
215  assert(iv[j].idx==vx1lb2.val());
216  if (iv[i].idx!=iv[j].idx) {
217  GlbRanges<SView> xilb(iv[i].view);
218  ModEvent me = iv[j].view.excludeI(home,xilb);
219  fix_flag |= me_modified(me);
220  GECODE_ME_CHECK(me);
221  }
222  }
223  }
224  }
225 
226  // remove all elements from the selector that overlap
227  // with all other possibly selected elements, if
228  // at least two more elements need to be selected
229  if (x1.cardMin()-x1.glbSize() > 1) {
230  UnknownRanges<RView> x1u(x1);
231  Iter::Ranges::Cache x1uc(r,x1u);
233  vx1u(x1uc);
234 
235  for (; vx1u() && x1.cardMin()-x1.glbSize() > 1; ++vx1u) {
236  int i = 0;
237  while (iv[i].idx < vx1u.val()) i++;
238  assert(iv[i].idx == vx1u.val());
239  bool flag=true;
240 
241  UnknownRanges<RView> x1u2(x1);
243  for (; vx1u2(); ++vx1u2) {
244  int j = 0;
245  while (iv[j].idx < vx1u2.val()) j++;
246  assert(iv[j].idx == vx1u2.val());
247  if (iv[i].idx!=iv[j].idx) {
248  GlbRanges<SView> xjlb(iv[j].view);
249  GlbRanges<SView> xilb(iv[i].view);
251  inter(xjlb, xilb);
252  if (!inter()) {
253  flag = false;
254  goto here;
255  }
256  }
257  }
258  here:
259  if (flag) {
260  ModEvent me = x1.exclude(home,iv[i].idx);
261  fix_flag |= me_modified(me);
262  GECODE_ME_CHECK(me);
263  }
264  }
265  }
266 
267  // if exactly two more elements need to be selected
268  // and there is a possible element i such that all other pairs of
269  // elements overlap, select i
270  UnknownRanges<RView> x1u(x1);
271  Iter::Ranges::Cache x1uc(r,x1u);
273  vx1u(x1uc);
274 
275  for (; x1.cardMin()-x1.glbSize() == 2 && vx1u(); ++vx1u) {
276  int i = 0;
277  while (iv[i].idx < vx1u.val()) i++;
278  assert (iv[i].idx == vx1u.val());
279  bool flag=true;
280 
281  UnknownRanges<RView> x1u2(x1);
283  for (; vx1u2(); ++vx1u2) {
284  int j = 0;
285  while (iv[j].idx < vx1u2.val()) j++;
286  assert (iv[j].idx == vx1u2.val());
287  if (iv[i].idx!=iv[j].idx) {
288  UnknownRanges<RView> x1u3(x1);
290  for (; vx1u3(); ++vx1u3) {
291  int k = 0;
292  while (iv[k].idx < vx1u3.val()) k++;
293  assert (iv[k].idx == vx1u3.val());
294  if (iv[j].idx!=iv[k].idx && iv[i].idx!=iv[k].idx) {
295  GlbRanges<SView> xjlb(iv[j].view);
296  GlbRanges<SView> xilb(iv[k].view);
298  inter(xjlb, xilb);
299  if (!inter()) {
300  flag = false;
301  goto here2;
302  }
303  }
304  }
305  }
306  }
307  here2:
308  if (flag) {
309  ModEvent me = x1.include(home,iv[i].idx);
310  fix_flag |= me_modified(me);
311  GECODE_ME_CHECK(me);
312  }
313  }
314  } while (fix_flag);
315 
316  bool allAssigned = true;
317  for (int i=iv.size(); i--;)
318  if (!iv[i].view.assigned()) {
319  allAssigned = false;
320  break;
321  }
322  if (!x1.assigned())
323  allAssigned = false;
324 
325  return allAssigned ? home.ES_SUBSUMED(*this) : ES_FIX;
326  }
327 
328 
329 }}}
330 
331 // STATISTICS: set-prop
Propagator for element with disjointness
Definition: element.hh:198
#define forceinline
Definition: config.hpp:173
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3614
bool includeI(Space &home, I &i)
Include the set represented by i in this set.
Definition: integerset.hpp:300
virtual Actor * copy(Space &home, bool)
Copy propagator during cloning.
Definition: disjoint.hpp:100
Gecode::IntArgs i(4, 1, 2, 3, 4)
@ LO
Cheap.
Definition: core.hpp:581
Range iterator for the unknown set.
Definition: var-imp.hpp:406
Computation spaces.
Definition: core.hpp:1748
Base-class for both propagators and branchers.
Definition: core.hpp:696
static PropCost quadratic(PropCost::Mod m, unsigned int n)
Quadratic complexity for modifier m and size measure n.
Definition: core.hpp:4832
virtual void reschedule(Space &home)
Schedule function.
Definition: disjoint.hpp:84
int val(void) const
Return current value.
Gecode toplevel namespace
Base-class for propagators.
Definition: core.hpp:1092
ElementDisjoint(Space &home, bool share, ElementDisjoint &p)
Constructor for cloning p.
Definition: disjoint.hpp:55
Home class for posting propagators
Definition: core.hpp:922
Value iterator from range iterator.
Handle to region.
Definition: region.hpp:61
Range iterator for computing intersection (binary)
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:784
Range iterator for the greatest lower bound.
Definition: var-imp.hpp:363
int size(void) const
Return the current size.
Definition: idx-view.hpp:103
int ModEvent
Type for modification events.
Definition: core.hpp:142
void dispose(Space &home)
Free memory used by this set.
Definition: integerset.hpp:64
Range iterator cache
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: disjoint.hpp:91
Propagation cost.
Definition: core.hpp:554
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: disjoint.hpp:78
@ ES_FIX
Propagation has computed fixpoint.
Definition: core.hpp:545
Range iterator for the least upper bound.
Definition: var-imp.hpp:321
void subscribe(Space &home, Propagator &p, PropCond pc, bool process=true)
Definition: idx-view.hpp:129
Range iterator for integer sets.
Definition: var-imp.hpp:189
Growing sets of integers.
Definition: var-imp.hpp:209
const Gecode::PropCond PC_SET_ANY
Propagate when any bound or the cardinality of a view changes.
Definition: var-type.hpp:248
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: disjoint.hpp:106
Range iterator for singleton range.
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:56
RView x1
Definition: element.hh:203
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:3354
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition: modevent.hpp:63
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
int ModEventDelta
Modification event deltas.
Definition: core.hpp:169
SetExpr inter(const SetVarArgs &x)
Intersection of set variables.
Definition: set-expr.cpp:699
@ ES_OK
Execution is okay.
Definition: core.hpp:544
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
void update(Space &home, bool share, IdxViewArray< View > &x)
Cloning.
Definition: idx-view.hpp:151
static ExecStatus post(Home home, IdxViewArray &x, RView y)
Post propagator for .
Definition: disjoint.hpp:64
ExecStatus
Definition: core.hpp:540
IdxViewArray iv
Definition: element.hh:202