Generated on Thu Apr 5 2018 19:44:19 for Gecode by doxygen 1.8.13
dom.hpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  *
6  * Contributing authors:
7  * Mikael Lagerkvist <lagerkvist@gecode.org>
8  *
9  * Copyright:
10  * Christian Schulte, 2006
11  * Mikael Lagerkvist, 2006
12  *
13  * Last modified:
14  * $Date$ by $Author$
15  * $Revision$
16  *
17  * This file is part of Gecode, the generic constraint
18  * development environment:
19  * http://www.gecode.org
20  *
21  * Permission is hereby granted, free of charge, to any person obtaining
22  * a copy of this software and associated documentation files (the
23  * "Software"), to deal in the Software without restriction, including
24  * without limitation the rights to use, copy, modify, merge, publish,
25  * distribute, sublicense, and/or sell copies of the Software, and to
26  * permit persons to whom the Software is furnished to do so, subject to
27  * the following conditions:
28  *
29  * The above copyright notice and this permission notice shall be
30  * included in all copies or substantial portions of the Software.
31  *
32  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
33  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
34  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
35  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
36  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
37  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
38  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
39  *
40  */
41 
42 namespace Gecode { namespace Int { namespace Channel {
43 
48  template<class View, class Offset>
49  class DomInfo {
50  public:
52  View view;
54  unsigned int size;
56  int min;
58  int max;
60  void init(View x, int n);
62  void update(Space& home, DomInfo<View,Offset>& vcb);
64  bool doval(void) const;
66  bool dodom(void) const;
68  void assigned(void);
70  void removed(int i);
72  void done(Offset& o);
73  };
74 
75  template<class View, class Offset>
76  forceinline void
78  view = x;
79  size = static_cast<unsigned int>(n);
80  min = 0;
81  max = n-1;
82  }
83 
84  template<class View, class Offset>
85  forceinline void
87  view.update(home,di.view);
88  size = di.size;
89  min = di.min;
90  max = di.max;
91  }
92 
93  template<class View, class Offset>
94  forceinline bool
96  return (size != 1) && view.assigned();
97  }
98 
99  template<class View, class Offset>
100  forceinline bool
102  return size != view.size();
103  }
104 
105  template<class View, class Offset>
106  forceinline void
108  size = 1;
109  }
110 
111  template<class View, class Offset>
112  forceinline void
114  size--;
115  if (i == min)
116  min++;
117  else if (i == max)
118  max--;
119  }
120 
121  template<class View, class Offset>
122  forceinline void
124  size = view.size();
125  min = o(view).min();
126  max = o(view).max();
127  }
128 
129  // Propagate domain information from x to y
130  template<class View, class Offset>
131  ExecStatus
134  for (int i = n; i--; )
135  // Only views with not yet propagated missing values
136  if (x[i].dodom()) {
137  // Iterate the values in the complement of x[i]
139  xir(ox(x[i].view));
141  xirc(x[i].min,x[i].max,xir);
144  while (jv()) {
145  // j is not in the domain of x[i], so prune i from y[j]
146  int j = jv.val();
147  ModEvent me = oy(y[j].view).nq(home,i);
148  if (me_failed(me))
149  return ES_FAILED;
150  if (me_modified(me)) {
151  if (me == ME_INT_VAL) {
152  // Record that y[j] has been assigned and must be propagated
153  ya.push(j);
154  } else {
155  // Obvious as x[i] is different from j
156  y[j].removed(i);
157  }
158  }
159  ++jv;
160  }
161  // Update which values have been propagated and what are the new bounds
162  x[i].done(ox);
163  }
164  return ES_OK;
165  }
166 
167  /*
168  * The actual propagator
169  *
170  */
171  template<class View, class Offset, bool shared>
174  Offset& ox, Offset& oy)
175  : Base<DomInfo<View,Offset>,Offset,PC_INT_DOM>(home,n,xy,ox,oy) {}
176 
177  template<class View, class Offset, bool shared>
181 
182  template<class View, class Offset, bool shared>
183  Actor*
185  return new (home) Dom<View,Offset,shared>(home,*this);
186  }
187 
188  template<class View, class Offset, bool shared>
189  PropCost
191  const ModEventDelta& med) const {
192  if (View::me(med) == ME_INT_VAL)
194  else
196  }
197 
198  template<class View, class Offset, bool shared>
199  ExecStatus
201  Region r;
202  ProcessStack xa(r,n);
203  ProcessStack ya(r,n);
204 
207 
208  if (View::me(med) == ME_INT_VAL) {
209  // Scan x and y for assigned but not yet propagated views
210  for (int i = n; i--; ) {
211  if (x[i].doval()) xa.push(i);
212  if (y[i].doval()) ya.push(i);
213  }
214 
215  if (shared) {
216  do {
217  // Propagate assigned views for x
219  (home,n,x,ox,y,oy,n_na,xa,ya)));
220  // Propagate assigned views for y
222  (home,n,y,oy,x,ox,n_na,ya,xa)));
223  assert(ya.empty());
224  } while (!xa.empty() || !ya.empty());
225  return home.ES_NOFIX_PARTIAL(*this,View::med(ME_INT_DOM));
226  } else {
227  do {
228  // Propagate assigned views for x
230  (home,n,x,ox,y,oy,n_na,xa,ya)));
231  // Propagate assigned views for y
233  (home,n,y,oy,x,ox,n_na,ya,xa)));
234  assert(ya.empty());
235  } while (!xa.empty());
236  return home.ES_FIX_PARTIAL(*this,View::med(ME_INT_DOM));
237  }
238  }
239 
240  // Process changed views for y
241  // This propagates from y to x and possibly records xs that
242  // got assigned
243  GECODE_ES_CHECK(prop_dom(home,n,y,oy,x,ox,xa));
244 
245  // Process assigned views for x
247  (home,n,x,ox,y,oy,n_na,xa,ya)));
248 
249  // Perform domain consistent propagation for distinct on the x views
250  if (dc.available()) {
251  GECODE_ES_CHECK(dc.sync());
252  } else {
253  ViewArray<View> xv(r,n);
254  for (int i=n; i--; )
255  xv[i] = x[i].view;
256  GECODE_ES_CHECK(dc.init(home,xv));
257  }
258  bool assigned;
259  GECODE_ES_CHECK(dc.propagate(home,assigned));
260  if (assigned) {
261  // This has assigned some more views in x which goes unnoticed
262  // (that is, not recorded in xa). This must be checked and propagated
263  // to the y views, however the distinctness on x is already
264  // propagated.
265  for (int i=n; i--; )
266  if (x[i].doval()) {
267  int j = ox(x[i].view).val();
268  // Assign the y variable to i (or test if already assigned!)
269  ModEvent me = oy(y[j].view).eq(home,i);
270  if (me_failed(me))
271  return ES_FAILED;
272  if (me_modified(me)) {
273  // Record that y[j] has been assigned and must be propagated
274  assert(me == ME_INT_VAL);
275  // Otherwise the modification event would not be ME_INT_VAL
276  ya.push(j);
277  }
278  x[i].assigned(); n_na--;
279  }
280  }
281 
282  // Process changed views for x
283  // This propagates from x to y and possibly records ys that
284  // got assigned
285  GECODE_ES_CHECK(prop_dom(home,n,x,ox,y,oy,ya));
286 
287  // Process assigned view again (some might have been found above)
288  while (!xa.empty() || !ya.empty()) {
289  // Process assigned views for x
291  (home,n,x,ox,y,oy,n_na,xa,ya)));
292  // Process assigned views for y
294  (home,n,y,oy,x,ox,n_na,ya,xa)));
295  };
296 
297  if (shared) {
298  for (int i=2*n; i--; )
299  if (!xy[i].view.assigned())
300  return ES_NOFIX;
301  return home.ES_SUBSUMED(*this);
302  } else {
303  return (n_na == 0) ? home.ES_SUBSUMED(*this) : ES_FIX;
304  }
305  }
306 
307  template<class View, class Offset, bool shared>
308  ExecStatus
310  Offset& ox, Offset& oy) {
311  assert(n > 0);
312  if (n == 1) {
313  GECODE_ME_CHECK(ox(xy[0].view).eq(home,0));
314  GECODE_ME_CHECK(oy(xy[1].view).eq(home,0));
315  return ES_OK;
316  }
317  for (int i=n; i--; ) {
318  GECODE_ME_CHECK(ox(xy[i ].view).gq(home,0));
319  GECODE_ME_CHECK(ox(xy[i ].view).le(home,n));
320  GECODE_ME_CHECK(oy(xy[i+n].view).gq(home,0));
321  GECODE_ME_CHECK(oy(xy[i+n].view).le(home,n));
322  }
323  (void) new (home) Dom<View,Offset,shared>(home,n,xy,ox,oy);
324  return ES_OK;
325  }
326 
327 }}}
328 
329 // STATISTICS: int-prop
330 
void push(const T &x)
Push element x on top of stack.
ExecStatus prop_val(Space &home, int n, Info *x, Offset &ox, Info *y, Offset &oy, int &n_na, ProcessStack &xa, ProcessStack &ya)
Definition: val.hpp:173
Distinct::DomCtrl< View > dc
Propagation controller for propagating distinct.
Definition: channel.hh:146
static PropCost quadratic(PropCost::Mod m, unsigned int n)
Quadratic complexity for modifier m and size measure n.
Definition: core.hpp:4634
bool dodom(void) const
Check whether propagation for domain is to be done.
Definition: dom.hpp:101
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3433
ExecStatus ES_NOFIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has not computed partial fixpoint
Definition: core.hpp:3446
Offset ox
Offset transformation for x variables.
Definition: channel.hh:66
bool doval(void) const
Check whether propagation for assignment is to be done.
Definition: dom.hpp:95
bool empty(void) const
Test whether stack is empty.
int ModEvent
Type for modification events.
Definition: core.hpp:64
DomInfo< View, Offset > * xy
View and information for both x and y.
Definition: channel.hh:70
Offset oy
Offset transformation for y variables.
Definition: channel.hh:68
void done(Offset &o)
Update the size and bounds information after pruning.
Definition: dom.hpp:123
Handle to region.
Definition: region.hpp:57
#define forceinline
Definition: config.hpp:182
Propagation has computed fixpoint.
Definition: core.hpp:469
void update(Space &home, DomInfo< View, Offset > &vcb)
Update during cloning.
Definition: dom.hpp:86
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: dom.hpp:190
Computation spaces.
Definition: core.hpp:1668
Base-class for both propagators and branchers.
Definition: core.hpp:620
Range iterator for integer views.
Definition: view.hpp:54
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition: macros.hpp:95
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Gecode::IntArgs i(4, 1, 2, 3, 4)
void assigned(void)
Record that view got assigned.
Definition: dom.hpp:107
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Execution has resulted in failure.
Definition: core.hpp:466
int n
Number of views (actually twice as many for both x and y)
Definition: channel.hh:62
const Gecode::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable)
Definition: var-type.hpp:56
ExecStatus prop_dom(Space &home, int n, DomInfo< View, Offset > *x, Offset &ox, DomInfo< View, Offset > *y, Offset &oy, ProcessStack &ya)
Definition: dom.hpp:132
ModEventDelta med
A set of modification events (used during propagation)
Definition: core.hpp:1027
static ExecStatus post(Home home, int n, DomInfo< View, Offset > *xy, Offset &ox, Offset &oy)
Post propagator for channeling on xy.
Definition: dom.hpp:309
Value iterator from range iterator.
Domain consistent channel propagator.
Definition: channel.hh:138
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition: var-type.hpp:100
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: dom.hpp:200
Expensive.
Definition: core.hpp:506
View arrays.
Definition: array.hpp:228
unsigned int size
Last propagated size.
Definition: dom.hpp:54
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:56
ExecStatus ES_FIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has computed partial fixpoint
Definition: core.hpp:3439
Converter with fixed offset.
Definition: view.hpp:623
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:769
Combine view with information for domain propagation.
Definition: dom.hpp:49
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:769
Base-class for channel propagators.
Definition: channel.hh:59
Propagation cost.
Definition: core.hpp:478
const Gecode::ModEvent ME_INT_DOM
Domain operation has changed the domain.
Definition: var-type.hpp:72
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition: dom.hpp:184
ExecStatus
Definition: core.hpp:464
void init(View x, int n)
Initialize.
Definition: dom.hpp:77
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:47
int max
Last propagated maximum.
Definition: dom.hpp:58
Stack with fixed number of elements.
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition: modevent.hpp:63
int min
Last propagated minimum.
Definition: dom.hpp:56
Post propagator for SetVar x
Definition: set.hh:769
Execution is okay.
Definition: core.hpp:468
View view
The view.
Definition: dom.hpp:52
Propagation has not computed fixpoint.
Definition: core.hpp:467
Dom(Space &home, Dom &p)
Constructor for cloning p.
bool shared(const ConstView< ViewA > &, const ConstView< ViewB > &)
Test whether views share same variable.
Definition: view.hpp:702
Gecode toplevel namespace
void removed(int i)
Record that one value got removed.
Definition: dom.hpp:113
int ModEventDelta
Modification event deltas.
Definition: core.hpp:91
Home class for posting propagators
Definition: core.hpp:846
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition: modevent.hpp:58
int n_na
Total number of not assigned views (not known to be assigned)
Definition: channel.hh:64
Range iterator for computing the complement (described by values)