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