this repo has no description
dekker.one
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
38namespace Gecode { namespace Int { namespace Channel {
39
40 /**
41 * \brief Combine view with information for value propagation
42 *
43 */
44 template<class View>
45 class ValInfo {
46 public:
47 /// The view
48 View view;
49 /// Whether it has been propagated that view is assigned
50 bool a;
51 /// Initialize
52 void init(View x, int n);
53 /// Update during cloning
54 void update(Space& home, ValInfo<View>& vi);
55 /// Check whether propagation for assignment is to be done
56 bool doval(void) const;
57 /// Check whether propagation for domain is to be done
58 bool dodom(void) const;
59 /// Record that view got assigned
60 void assigned(void);
61 /// Record that one value got removed
62 void removed(int i);
63 /// Update the cardinality and bounds information after pruning
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
75 ValInfo<View>::update(Space& home, ValInfo<View>& vi) {
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
93 ValInfo<View>::assigned(void) {
94 a = true;
95 }
96
97 template<class View>
98 forceinline void
99 ValInfo<View>::removed(int) {}
100
101 template<class View>
102 forceinline void
103 ValInfo<View>::done(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>
168 forceinline ExecStatus
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>
181 forceinline
182 Val<View,Offset,shared>::Val(Home home, int n, ValInfo<View>* xy,
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>
187 forceinline
188 Val<View,Offset,shared>::Val(Space& home, Val<View,Offset,shared>& p)
189 : Base<ValInfo<View>,Offset,PC_INT_VAL>(home,p) {}
190
191 template<class View, class Offset, bool shared>
192 Actor*
193 Val<View,Offset,shared>::copy(Space& home) {
194 return new (home) Val<View,Offset,shared>(home,*this);
195 }
196
197 template<class View, class Offset, bool shared>
198 ExecStatus
199 Val<View,Offset,shared>::propagate(Space& home, const ModEventDelta&) {
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
215 GECODE_ES_CHECK((prop_val<View,Offset,ValInfo<View> >
216 (home,n,x,ox,y,oy,n_na,xa,ya)));
217 // Propagate assigned views for y
218 GECODE_ES_CHECK((prop_val<View,Offset,ValInfo<View> >
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
230 Val<View,Offset,shared>::post(Home home, int n, ValInfo<View>* xy,
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