Generated on Tue Jan 26 2021 00:00:00 for Gecode by doxygen 1.9.1
val.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>
45  class ValInfo {
46  public:
48  View view;
50  bool a;
52  void init(View x, int n);
54  void update(Space& home, ValInfo<View>& vi);
56  bool doval(void) const;
58  bool dodom(void) const;
60  void assigned(void);
62  void removed(int i);
64  void done(void);
65  };
66 
67  template<class View>
68  forceinline void
69  ValInfo<View>::init(View x, int) {
70  view = x; a = false;
71  }
72 
73  template<class View>
74  forceinline void
76  view.update(home,vi.view); a = vi.a;
77  }
78 
79  template<class View>
80  forceinline bool
81  ValInfo<View>::doval(void) const {
82  return !a && view.assigned();
83  }
84 
85  template<class View>
86  forceinline bool
87  ValInfo<View>::dodom(void) const {
88  return false;
89  }
90 
91  template<class View>
92  forceinline void
94  a = true;
95  }
96 
97  template<class View>
98  forceinline void
100 
101  template<class View>
102  forceinline void
104 
105 
106  // Propagate assigned views for x
107  template<class View, class Offset, class Info>
108  ExecStatus
109  doprop_val(Space& home, int n, Info* x, Offset& ox,
110  Info* y, Offset& oy,
111  int& n_na, ProcessStack& xa, ProcessStack& ya) {
112  do {
113  int i = xa.pop();
114  int j = ox(x[i].view).val();
115  // Assign the y variable to i (or test if already assigned!)
116  {
117  ModEvent me = oy(y[j].view).eq(home,i);
118  if (me_failed(me)) {
119  return ES_FAILED;
120  }
121  // Record that y[j] has been assigned and must be propagated
122  if (me_modified(me))
123  ya.push(j);
124  }
125  // Prune the value j from all x variables
126  for (int k=0; k<i; k++) {
127  ModEvent me = ox(x[k].view).nq(home,j);
128  if (me_failed(me)) {
129  return ES_FAILED;
130  }
131  if (me_modified(me)) {
132  if (me == ME_INT_VAL) {
133  // Record that x[k] has been assigned and must be propagated
134  xa.push(k);
135  } else {
136  // One value has been removed and this removal does not need
137  // to be propagated again: after all y[j] = i, so it holds
138  // that y[j] != k.
139  x[k].removed(j);
140  }
141  }
142  }
143  // The same for the other views
144  for (int k=i+1; k<n; k++) {
145  ModEvent me = ox(x[k].view).nq(home,j);
146  if (me_failed(me)) {
147  return ES_FAILED;
148  }
149  if (me_modified(me)) {
150  if (me == ME_INT_VAL) {
151  // Record that x[k] has been assigned and must be propagated
152  xa.push(k);
153  } else {
154  // One value has been removed and this removal does not need
155  // to be propagated again: after all y[j] = i, so it holds
156  // that y[j] != k.
157  x[k].removed(j);
158  }
159  }
160  }
161  x[i].assigned(); n_na--;
162  } while (!xa.empty());
163  return ES_OK;
164  }
165 
166  // Just do a test whether a call to the routine is necessary
167  template<class View, class Offset, class Info>
169  prop_val(Space& home, int n, Info* x, Offset& ox, Info* y, Offset& oy,
170  int& n_na, ProcessStack& xa, ProcessStack& ya) {
171  if (xa.empty())
172  return ES_OK;
173  return doprop_val<View,Offset,Info>(home,n,x,ox,y,oy,n_na,xa,ya);
174  }
175 
176  /*
177  * The actual propagator
178  *
179  */
180  template<class View, class Offset, bool shared>
183  Offset& ox, Offset& oy)
184  : Base<ValInfo<View>,Offset,PC_INT_VAL>(home,n,xy,ox,oy) {}
185 
186  template<class View, class Offset, bool shared>
189  : Base<ValInfo<View>,Offset,PC_INT_VAL>(home,p) {}
190 
191  template<class View, class Offset, bool shared>
192  Actor*
194  return new (home) Val<View,Offset,shared>(home,*this);
195  }
196 
197  template<class View, class Offset, bool shared>
198  ExecStatus
200  Region r;
201  ProcessStack xa(r,n);
202  ProcessStack ya(r,n);
203 
204  ValInfo<View>* x = xy;
205  ValInfo<View>* y = xy+n;
206 
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  do {
214  // Propagate assigned views for x
216  (home,n,x,ox,y,oy,n_na,xa,ya)));
217  // Propagate assigned views for y
219  (home,n,y,oy,x,ox,n_na,ya,xa)));
220  assert(ya.empty());
221  } while (!xa.empty());
222 
223  if (n_na == 0)
224  return home.ES_SUBSUMED(*this);
225  return shared ? ES_NOFIX : ES_FIX;
226  }
227 
228  template<class View, class Offset, bool shared>
229  ExecStatus
231  Offset& ox, Offset& oy) {
232  assert(n > 0);
233  if (n == 1) {
234  GECODE_ME_CHECK(ox(xy[0].view).eq(home,0));
235  GECODE_ME_CHECK(oy(xy[1].view).eq(home,0));
236  return ES_OK;
237  }
238  for (int i=0; i<n; i++) {
239  GECODE_ME_CHECK(ox(xy[i ].view).gq(home,0));
240  GECODE_ME_CHECK(ox(xy[i ].view).le(home,n));
241  GECODE_ME_CHECK(oy(xy[i+n].view).gq(home,0));
242  GECODE_ME_CHECK(oy(xy[i+n].view).le(home,n));
243  }
244  (void) new (home) Val<View,Offset,shared>(home,n,xy,ox,oy);
245  return ES_OK;
246  }
247 
248 }}}
249 
250 // STATISTICS: int-prop
251 
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
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
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 value propagation.
Definition: val.hpp:45
void done(void)
Update the cardinality and bounds information after pruning.
Definition: val.hpp:103
bool a
Whether it has been propagated that view is assigned.
Definition: val.hpp:50
View view
The view.
Definition: val.hpp:48
void init(View x, int n)
Initialize.
Definition: val.hpp:69
void assigned(void)
Record that view got assigned.
Definition: val.hpp:93
void removed(int i)
Record that one value got removed.
Definition: val.hpp:99
bool dodom(void) const
Check whether propagation for domain is to be done.
Definition: val.hpp:87
bool doval(void) const
Check whether propagation for assignment is to be done.
Definition: val.hpp:81
void update(Space &home, ValInfo< View > &vi)
Update during cloning.
Definition: val.hpp:75
Naive channel propagator.
Definition: channel.hh:97
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition: val.hpp:193
static ExecStatus post(Home home, int n, ValInfo< View > *xy, Offset &ox, Offset &oy)
Post propagator for channeling.
Definition: val.hpp:230
Val(Space &home, Val &p)
Constructor for cloning p.
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: val.hpp:199
Converter with fixed offset.
Definition: view.hpp:650
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.
T pop(void)
Pop topmost element from stack and return it.
bool empty(void) const
Test whether stack is empty.
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_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
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 doprop_val(Space &home, int n, Info *x, Offset &ox, Info *y, Offset &oy, int &n_na, ProcessStack &xa, ProcessStack &ya)
Definition: val.hpp:109
bool shared(const IntSet &, VX)
Definition: view-base.hpp:118
const Gecode::PropCond PC_INT_VAL
Propagate when a view becomes assigned (single value)
Definition: var-type.hpp:82
const Gecode::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable)
Definition: var-type.hpp:56
Gecode::IntArgs i({1, 2, 3, 4})
#define forceinline
Definition: config.hpp:185