Generated on Sat Apr 10 2021 00:00:00 for Gecode by doxygen 1.9.1
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  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 namespace Gecode { namespace Int { namespace Channel {
39 
44  template<class View, class Offset>
45  class DomInfo {
46  public:
48  View view;
50  unsigned int size;
52  int min;
54  int max;
56  void init(View x, int n);
58  void update(Space& home, DomInfo<View,Offset>& vcb);
60  bool doval(void) const;
62  bool dodom(void) const;
64  void assigned(void);
66  void removed(int i);
68  void done(Offset& o);
69  };
70 
71  template<class View, class Offset>
72  forceinline void
74  view = x;
75  size = static_cast<unsigned int>(n);
76  min = 0;
77  max = n-1;
78  }
79 
80  template<class View, class Offset>
81  forceinline void
83  view.update(home,di.view);
84  size = di.size;
85  min = di.min;
86  max = di.max;
87  }
88 
89  template<class View, class Offset>
90  forceinline bool
92  return (size != 1) && view.assigned();
93  }
94 
95  template<class View, class Offset>
96  forceinline bool
98  return size != view.size();
99  }
100 
101  template<class View, class Offset>
102  forceinline void
104  size = 1;
105  }
106 
107  template<class View, class Offset>
108  forceinline void
110  size--;
111  if (i == min)
112  min++;
113  else if (i == max)
114  max--;
115  }
116 
117  template<class View, class Offset>
118  forceinline void
120  size = view.size();
121  min = o(view).min();
122  max = o(view).max();
123  }
124 
125  // Propagate domain information from x to y
126  template<class View, class Offset>
127  ExecStatus
130  for (int i=0; i<n; i++)
131  // Only views with not yet propagated missing values
132  if (x[i].dodom()) {
133  // Iterate the values in the complement of x[i]
135  xir(ox(x[i].view));
137  xirc(x[i].min,x[i].max,xir);
140  while (jv()) {
141  // j is not in the domain of x[i], so prune i from y[j]
142  int j = jv.val();
143  ModEvent me = oy(y[j].view).nq(home,i);
144  if (me_failed(me))
145  return ES_FAILED;
146  if (me_modified(me)) {
147  if (me == ME_INT_VAL) {
148  // Record that y[j] has been assigned and must be propagated
149  ya.push(j);
150  } else {
151  // Obvious as x[i] is different from j
152  y[j].removed(i);
153  }
154  }
155  ++jv;
156  }
157  // Update which values have been propagated and what are the new bounds
158  x[i].done(ox);
159  }
160  return ES_OK;
161  }
162 
163  /*
164  * The actual propagator
165  *
166  */
167  template<class View, class Offset, bool shared>
170  Offset& ox, Offset& oy)
171  : Base<DomInfo<View,Offset>,Offset,PC_INT_DOM>(home,n,xy,ox,oy) {}
172 
173  template<class View, class Offset, bool shared>
176  : Base<DomInfo<View,Offset>,Offset,PC_INT_DOM>(home,p) {}
177 
178  template<class View, class Offset, bool shared>
179  Actor*
181  return new (home) Dom<View,Offset,shared>(home,*this);
182  }
183 
184  template<class View, class Offset, bool shared>
185  PropCost
187  const ModEventDelta& med) const {
188  if (View::me(med) == ME_INT_VAL)
190  else
192  }
193 
194  template<class View, class Offset, bool shared>
195  ExecStatus
197  // MSVC in non-permissive mode needs this, no idea why...
198  const int n = this->n;
199  Region r;
200  ProcessStack xa(r,n);
201  ProcessStack ya(r,n);
202 
203  DomInfo<View,Offset>* x = xy;
204  DomInfo<View,Offset>* y = xy+n;
205 
206  if (View::me(med) == ME_INT_VAL) {
207  // Scan x and y for assigned but not yet propagated views
208  for (int i=0; i<n; i++) {
209  if (x[i].doval()) xa.push(i);
210  if (y[i].doval()) ya.push(i);
211  }
212 
213  if (shared) {
214  do {
215  // Propagate assigned views for x
217  (home,n,x,ox,y,oy,n_na,xa,ya)));
218  // Propagate assigned views for y
220  (home,n,y,oy,x,ox,n_na,ya,xa)));
221  assert(ya.empty());
222  } while (!xa.empty() || !ya.empty());
223  return home.ES_NOFIX_PARTIAL(*this,View::med(ME_INT_DOM));
224  } else {
225  do {
226  // Propagate assigned views for x
228  (home,n,x,ox,y,oy,n_na,xa,ya)));
229  // Propagate assigned views for y
231  (home,n,y,oy,x,ox,n_na,ya,xa)));
232  assert(ya.empty());
233  } while (!xa.empty());
234  return home.ES_FIX_PARTIAL(*this,View::med(ME_INT_DOM));
235  }
236  }
237 
238  // Process changed views for y
239  // This propagates from y to x and possibly records xs that
240  // got assigned
241  GECODE_ES_CHECK(prop_dom(home,n,y,oy,x,ox,xa));
242 
243  // Process assigned views for x
245  (home,n,x,ox,y,oy,n_na,xa,ya)));
246 
247  // Perform domain consistent propagation for distinct on the x views
248  if (dc.available()) {
249  GECODE_ES_CHECK(dc.sync());
250  } else {
251  ViewArray<View> xv(r,n);
252  for (int i=0; i<n; i++)
253  xv[i] = x[i].view;
254  GECODE_ES_CHECK(dc.init(home,xv));
255  }
256  bool assigned;
257  GECODE_ES_CHECK(dc.propagate(home,assigned));
258  if (assigned) {
259  // This has assigned some more views in x which goes unnoticed
260  // (that is, not recorded in xa). This must be checked and propagated
261  // to the y views, however the distinctness on x is already
262  // propagated.
263  for (int i=0; i<n; i++)
264  if (x[i].doval()) {
265  int j = ox(x[i].view).val();
266  // Assign the y variable to i (or test if already assigned!)
267  ModEvent me = oy(y[j].view).eq(home,i);
268  if (me_failed(me))
269  return ES_FAILED;
270  if (me_modified(me)) {
271  // Record that y[j] has been assigned and must be propagated
272  assert(me == ME_INT_VAL);
273  // Otherwise the modification event would not be ME_INT_VAL
274  ya.push(j);
275  }
276  x[i].assigned(); n_na--;
277  }
278  }
279 
280  // Process changed views for x
281  // This propagates from x to y and possibly records ys that
282  // got assigned
283  GECODE_ES_CHECK(prop_dom(home,n,x,ox,y,oy,ya));
284 
285  // Process assigned view again (some might have been found above)
286  while (!xa.empty() || !ya.empty()) {
287  // Process assigned views for x
289  (home,n,x,ox,y,oy,n_na,xa,ya)));
290  // Process assigned views for y
292  (home,n,y,oy,x,ox,n_na,ya,xa)));
293  };
294 
295  if (shared) {
296  for (int i=0; i<2*n; i++)
297  if (!xy[i].view.assigned())
298  return ES_NOFIX;
299  return home.ES_SUBSUMED(*this);
300  } else {
301  return (n_na == 0) ? home.ES_SUBSUMED(*this) : ES_FIX;
302  }
303  }
304 
305  template<class View, class Offset, bool shared>
306  ExecStatus
308  Offset& ox, Offset& oy) {
309  assert(n > 0);
310  if (n == 1) {
311  GECODE_ME_CHECK(ox(xy[0].view).eq(home,0));
312  GECODE_ME_CHECK(oy(xy[1].view).eq(home,0));
313  return ES_OK;
314  }
315  for (int i=0; i<n; i++) {
316  GECODE_ME_CHECK(ox(xy[i ].view).gq(home,0));
317  GECODE_ME_CHECK(ox(xy[i ].view).le(home,n));
318  GECODE_ME_CHECK(oy(xy[i+n].view).gq(home,0));
319  GECODE_ME_CHECK(oy(xy[i+n].view).le(home,n));
320  }
321  (void) new (home) Dom<View,Offset,shared>(home,n,xy,ox,oy);
322  return ES_OK;
323  }
324 
325 }}}
326 
327 // STATISTICS: int-prop
328 
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
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:249
NNF * r
Right subtree.
Definition: bool-expr.cpp:242
Base-class for both propagators and branchers.
Definition: core.hpp:628
Home class for posting propagators
Definition: core.hpp:856
Base-class for channel propagators.
Definition: channel.hh:55
Combine view with information for domain propagation.
Definition: dom.hpp:45
View view
The view.
Definition: dom.hpp:48
void update(Space &home, DomInfo< View, Offset > &vcb)
Update during cloning.
Definition: dom.hpp:82
unsigned int size
Last propagated size.
Definition: dom.hpp:50
void removed(int i)
Record that one value got removed.
Definition: dom.hpp:109
void assigned(void)
Record that view got assigned.
Definition: dom.hpp:103
void done(Offset &o)
Update the size and bounds information after pruning.
Definition: dom.hpp:119
int min
Last propagated minimum.
Definition: dom.hpp:52
bool doval(void) const
Check whether propagation for assignment is to be done.
Definition: dom.hpp:91
void init(View x, int n)
Initialize.
Definition: dom.hpp:73
bool dodom(void) const
Check whether propagation for domain is to be done.
Definition: dom.hpp:97
int max
Last propagated maximum.
Definition: dom.hpp:54
Domain consistent channel propagator.
Definition: channel.hh:134
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: dom.hpp:196
static ExecStatus post(Home home, int n, DomInfo< View, Offset > *xy, Offset &ox, Offset &oy)
Post propagator for channeling on xy.
Definition: dom.hpp:307
Dom(Space &home, Dom &p)
Constructor for cloning p.
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition: dom.hpp:180
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: dom.hpp:186
Converter with fixed offset.
Definition: view.hpp:650
Range iterator for integer views.
Definition: view.hpp:54
Range iterator for computing the complement (described by values)
Value iterator from range iterator.
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
@ HI
Expensive.
Definition: core.hpp:514
Handle to region.
Definition: region.hpp:55
Computation spaces.
Definition: core.hpp:1742
Stack with fixed number of elements.
void push(const T &x)
Push element x on top of stack.
bool empty(void) const
Test whether stack is empty.
View arrays.
Definition: array.hpp:253
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_FAILED
Execution has resulted in failure.
Definition: core.hpp:474
@ 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 y
Definition: set.hh:767
ExecStatus ES_NOFIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has not computed partial fixpoint
Definition: core.hpp:3576
ExecStatus ES_FIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has computed partial fixpoint
Definition: core.hpp:3569
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
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition: modevent.hpp:54
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition: macros.hpp:91
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition: modevent.hpp:59
const FloatNum max
Largest allowed float value.
Definition: float.hh:844
const FloatNum min
Smallest allowed float value.
Definition: float.hh:846
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:169
ExecStatus prop_dom(Space &home, int n, DomInfo< View, Offset > *x, Offset &ox, DomInfo< View, Offset > *y, Offset &oy, ProcessStack &ya)
Definition: dom.hpp:128
bool shared(const IntSet &, VX)
Definition: view-base.hpp:118
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:43
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition: var-type.hpp:100
const Gecode::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable)
Definition: var-type.hpp:56
const Gecode::ModEvent ME_INT_DOM
Domain operation has changed the domain.
Definition: var-type.hpp:72
unsigned int size(I &i)
Size of all ranges of range iterator i.
Gecode::IntArgs i({1, 2, 3, 4})
#define forceinline
Definition: config.hpp:192