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 * Copyright:
7 * Christian Schulte, 2012
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.org
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
34namespace Gecode {
35
36 /**
37 * \defgroup TaskBranchViewVal Generic brancher based on view and value selection
38 *
39 * Implements view-based brancher for an array of views and value.
40 * \ingroup TaskActor
41 */
42
43 //@{
44 /// %Choice storing position and value
45 template<class Val>
46 class GECODE_VTABLE_EXPORT PosValChoice : public PosChoice {
47 private:
48 /// Value to assign to
49 const Val _val;
50 public:
51 /// Initialize choice for brancher \a b, number of alternatives \a a, position \a p, and value \a n
52 PosValChoice(const Brancher& b, unsigned int a, const Pos& p, const Val& n);
53 const Val& val(void) const;
54 /// Archive into \a e
55 virtual void archive(Archive& e) const;
56 };
57
58
59 /// View-value no-good literal
60 template<class View, class Val, PropCond pc>
61 class ViewValNGL : public NGL {
62 protected:
63 /// The stored view
64 View x;
65 /// The stored value
66 Val n;
67 public:
68 /// Initialize for propagator \a p with view \a x and value \a n
69 ViewValNGL(Space& home, View x, Val n);
70 /// Constructor for cloning \a ngl
71 ViewValNGL(Space& home, ViewValNGL& ngl);
72 /// Create subscription for no-good literal
73 virtual void subscribe(Space& home, Propagator& p);
74 /// Cancel subscription for no-good literal
75 virtual void cancel(Space& home, Propagator& p);
76 /// Schedule propagator \a p
77 virtual void reschedule(Space& home, Propagator& p);
78 /// Dispose
79 virtual size_t dispose(Space& home);
80 };
81
82 /**
83 * \brief Generic brancher by view and value selection
84 *
85 * Implements view-based branching for an array of views (of type
86 * \a View) and value (of type \a Val).
87 *
88 */
89 template<class View, int n, class Val, unsigned int a,
90 class Filter, class Print>
91 class ViewValBrancher : public ViewBrancher<View,Filter,n> {
92 protected:
93 using ViewBrancher<View,Filter,n>::vs;
94 using ViewBrancher<View,Filter,n>::x;
95 using ViewBrancher<View,Filter,n>::f;
96 /// The corresponding variable
97 typedef typename View::VarType Var;
98 /// Value selection and commit object
99 ValSelCommitBase<View,Val>* vsc;
100 /// Print function
101 Print p;
102 /// Constructor for cloning \a b
103 ViewValBrancher(Space& home, ViewValBrancher& b);
104 /// Constructor for creation
105 ViewValBrancher(Home home,
106 ViewArray<View>& x,
107 ViewSel<View>* vs[n],
108 ValSelCommitBase<View,Val>* vsc,
109 BranchFilter<Var> bf,
110 VarValPrint<Var,Val> vvp);
111 public:
112 /// Return choice
113 virtual const Choice* choice(Space& home);
114 /// Return choice
115 virtual const Choice* choice(const Space& home, Archive& e);
116 /// Perform commit for choice \a c and alternative \a b
117 virtual ExecStatus commit(Space& home, const Choice& c, unsigned int b);
118 /// Create no-good literal for choice \a c and alternative \a b
119 virtual NGL* ngl(Space& home, const Choice& c, unsigned int b) const;
120 /**
121 * \brief Print branch for choice \a c and alternative \a b
122 *
123 * Prints an explanation of the alternative \a b of choice \a c
124 * on the stream \a o.
125 *
126 */
127 virtual void print(const Space& home, const Choice& c, unsigned int b,
128 std::ostream& o) const;
129 /// Perform cloning
130 virtual Actor* copy(Space& home);
131 /// Delete brancher and return its size
132 virtual size_t dispose(Space& home);
133 /// Brancher post function
134 static void post(Home home,
135 ViewArray<View>& x,
136 ViewSel<View>* vs[n],
137 ValSelCommitBase<View,Val>* vsc,
138 BranchFilter<Var> bf,
139 VarValPrint<Var,Val> vvp);
140 };
141
142 /// Post view value brancher
143 template<class View, int n, class Val, unsigned int a>
144 void
145 postviewvalbrancher(Home home,
146 ViewArray<View>& x,
147 ViewSel<View>* vs[n],
148 ValSelCommitBase<View,Val>* vsc,
149 BranchFilter<typename View::VarType> bf,
150 VarValPrint<typename View::VarType,Val> vvp);
151 //@}
152
153 /*
154 * %Choice with position and value
155 *
156 */
157 template<class Val>
158 forceinline
159 PosValChoice<Val>::PosValChoice(const Brancher& b, unsigned int a,
160 const Pos& p, const Val& n)
161 : PosChoice(b,a,p), _val(n) {}
162
163 template<class Val>
164 forceinline const Val&
165 PosValChoice<Val>::val(void) const {
166 return _val;
167 }
168
169 template<class Val>
170 forceinline void
171 PosValChoice<Val>::archive(Archive& e) const {
172 PosChoice::archive(e);
173 e << _val;
174 }
175
176
177 /*
178 * View-value no-good literal
179 *
180 */
181 template<class View, class Val, PropCond pc>
182 forceinline
183 ViewValNGL<View,Val,pc>::ViewValNGL(Space& home, View x0, Val n0)
184 : NGL(home), x(x0), n(n0) {}
185
186 template<class View, class Val, PropCond pc>
187 forceinline
188 ViewValNGL<View,Val,pc>::ViewValNGL(Space& home, ViewValNGL& ngl)
189 : NGL(home,ngl), n(ngl.n) {
190 x.update(home,ngl.x);
191 }
192
193 template<class View, class Val, PropCond pc>
194 void
195 ViewValNGL<View,Val,pc>::subscribe(Space& home, Propagator& p) {
196 x.subscribe(home,p,pc);
197 }
198
199 template<class View, class Val, PropCond pc>
200 void
201 ViewValNGL<View,Val,pc>::cancel(Space& home, Propagator& p) {
202 x.cancel(home,p,pc);
203 }
204
205 template<class View, class Val, PropCond pc>
206 void
207 ViewValNGL<View,Val,pc>::reschedule(Space& home, Propagator& p) {
208 x.reschedule(home,p,pc);
209 }
210
211 template<class View, class Val, PropCond pc>
212 size_t
213 ViewValNGL<View,Val,pc>::dispose(Space& home) {
214 (void) NGL::dispose(home);
215 return sizeof(*this);
216 }
217
218
219
220 /*
221 * Generic brancher based on variable/value selection
222 *
223 */
224 template<class View, int n, class Val, unsigned int a,
225 class Filter, class Print>
226 forceinline
227 ViewValBrancher<View,n,Val,a,Filter,Print>::
228 ViewValBrancher(Home home,
229 ViewArray<View>& x,
230 ViewSel<View>* vs[n],
231 ValSelCommitBase<View,Val>* vsc0,
232 BranchFilter<Var> bf,
233 VarValPrint<Var,Val> vvp)
234 : ViewBrancher<View,Filter,n>(home,x,vs,bf), vsc(vsc0), p(vvp) {
235 if (vsc->notice() || f.notice() || p.notice())
236 home.notice(*this,AP_DISPOSE,true);
237 }
238
239 template<class View, int n, class Val, unsigned int a,
240 class Filter, class Print>
241 forceinline void
242 ViewValBrancher<View,n,Val,a,Filter,Print>::
243 post(Home home, ViewArray<View>& x,
244 ViewSel<View>* vs[n], ValSelCommitBase<View,Val>* vsc,
245 BranchFilter<Var> bf,
246 VarValPrint<Var,Val> vvp) {
247 (void) new (home) ViewValBrancher<View,n,Val,a,Filter,Print>
248 (home,x,vs,vsc,bf,vvp);
249 }
250
251 template<class View, int n, class Val, unsigned int a,
252 class Filter, class Print>
253 forceinline
254 ViewValBrancher<View,n,Val,a,Filter,Print>::
255 ViewValBrancher(Space& home,
256 ViewValBrancher<View,n,Val,a,Filter,Print>& b)
257 : ViewBrancher<View,Filter,n>(home,b),
258 vsc(b.vsc->copy(home)), p(b.p) {}
259
260 template<class View, int n, class Val, unsigned int a,
261 class Filter, class Print>
262 Actor*
263 ViewValBrancher<View,n,Val,a,Filter,Print>::copy(Space& home) {
264 return new (home) ViewValBrancher<View,n,Val,a,Filter,Print>
265 (home,*this);
266 }
267
268 template<class View, int n, class Val, unsigned int a,
269 class Filter, class Print>
270 const Choice*
271 ViewValBrancher<View,n,Val,a,Filter,Print>::choice(Space& home) {
272 Pos p = ViewBrancher<View,Filter,n>::pos(home);
273 View v = ViewBrancher<View,Filter,n>::view(p);
274 return new PosValChoice<Val>(*this,a,p,vsc->val(home,v,p.pos));
275 }
276
277 template<class View, int n, class Val, unsigned int a,
278 class Filter, class Print>
279 const Choice*
280 ViewValBrancher<View,n,Val,a,Filter,Print>::choice(const Space& home,
281 Archive& e) {
282 (void) home;
283 int p; e >> p;
284 Val v; e >> v;
285 return new PosValChoice<Val>(*this,a,p,v);
286 }
287
288 template<class View, int n, class Val, unsigned int a,
289 class Filter, class Print>
290 ExecStatus
291 ViewValBrancher<View,n,Val,a,Filter,Print>
292 ::commit(Space& home, const Choice& c, unsigned int b) {
293 const PosValChoice<Val>& pvc
294 = static_cast<const PosValChoice<Val>&>(c);
295 return me_failed(vsc->commit(home,b,
296 ViewBrancher<View,Filter,n>::view(pvc.pos()),
297 pvc.pos().pos,
298 pvc.val()))
299 ? ES_FAILED : ES_OK;
300 }
301
302 template<class View, int n, class Val, unsigned int a,
303 class Filter, class Print>
304 NGL*
305 ViewValBrancher<View,n,Val,a,Filter,Print>
306 ::ngl(Space& home, const Choice& c, unsigned int b) const {
307 const PosValChoice<Val>& pvc
308 = static_cast<const PosValChoice<Val>&>(c);
309 return vsc->ngl(home,b,
310 ViewBrancher<View,Filter,n>::view(pvc.pos()),pvc.val());
311 }
312
313 template<class View, int n, class Val, unsigned int a,
314 class Filter, class Print>
315 void
316 ViewValBrancher<View,n,Val,a,Filter,Print>
317 ::print(const Space& home, const Choice& c, unsigned int b,
318 std::ostream& o) const {
319 const PosValChoice<Val>& pvc
320 = static_cast<const PosValChoice<Val>&>(c);
321 View xi = ViewBrancher<View,Filter,n>::view(pvc.pos());
322 if (p)
323 p(home,*this,b,xi,pvc.pos().pos,pvc.val(),o);
324 else
325 vsc->print(home,b,xi,pvc.pos().pos,pvc.val(),o);
326 }
327
328 template<class View, int n, class Val, unsigned int a,
329 class Filter, class Print>
330 forceinline size_t
331 ViewValBrancher<View,n,Val,a,Filter,Print>::dispose(Space& home) {
332 if (vsc->notice() || f.notice() || p.notice())
333 home.ignore(*this,AP_DISPOSE,true);
334 vsc->dispose(home);
335 (void) ViewBrancher<View,Filter,n>::dispose(home);
336 return sizeof(ViewValBrancher<View,n,Val,a,Filter,Print>);
337 }
338
339 template<class View, int n, class Val, unsigned int a>
340 forceinline void
341 postviewvalbrancher(Home home,
342 ViewArray<View>& x,
343 ViewSel<View>* vs[n],
344 ValSelCommitBase<View,Val>* vsc,
345 BranchFilter<typename View::VarType> bf,
346 VarValPrint<typename View::VarType,Val> vvp) {
347 if (bf) {
348 if (vvp) {
349 ViewValBrancher<View,n,Val,a,
350 BrancherFilter<View>,BrancherPrint<View,Val> >
351 ::post(home,x,vs,vsc,bf,vvp);
352 } else {
353 ViewValBrancher<View,n,Val,a,
354 BrancherFilter<View>,BrancherNoPrint<View,Val> >
355 ::post(home,x,vs,vsc,bf,vvp);
356 }
357 } else {
358 if (vvp)
359 ViewValBrancher<View,n,Val,a,
360 BrancherNoFilter<View>,BrancherPrint<View,Val> >
361 ::post(home,x,vs,vsc,bf,vvp);
362 else
363 ViewValBrancher<View,n,Val,a,
364 BrancherNoFilter<View>,BrancherNoPrint<View,Val> >
365 ::post(home,x,vs,vsc,bf,vvp);
366 }
367 }
368
369}
370
371// STATISTICS: kernel-branch