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, 2017
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 { namespace FlatZinc {
35
36 forceinline
37 IntBoolVarBranch::IntBoolVarBranch(Select s0, double d)
38 : VarBranch<IntVar>(d), s(s0) {}
39
40 forceinline
41 IntBoolVarBranch::IntBoolVarBranch(Select s0, IntAFC i, BoolAFC b)
42 : s(s0), iafc(i), bafc(b) {}
43
44 forceinline
45 IntBoolVarBranch::IntBoolVarBranch(Select s0, IntAction i, BoolAction b)
46 : s(s0), iaction(i), baction(b) {}
47
48 forceinline
49 IntBoolVarBranch::IntBoolVarBranch(Select s0, IntCHB i, BoolCHB b)
50 : s(s0), ichb(i), bchb(b) {}
51
52 forceinline IntBoolVarBranch::Select
53 IntBoolVarBranch::select(void) const {
54 return s;
55 }
56
57 forceinline IntAFC
58 IntBoolVarBranch::intafc(void) const {
59 return iafc;
60 }
61 forceinline BoolAFC
62 IntBoolVarBranch::boolafc(void) const {
63 return bafc;
64 }
65
66 forceinline IntAction
67 IntBoolVarBranch::intaction(void) const {
68 return iaction;
69 }
70 forceinline BoolAction
71 IntBoolVarBranch::boolaction(void) const {
72 return baction;
73 }
74
75 forceinline IntCHB
76 IntBoolVarBranch::intchb(void) const {
77 return ichb;
78 }
79 forceinline BoolCHB
80 IntBoolVarBranch::boolchb(void) const {
81 return bchb;
82 }
83 forceinline void
84 IntBoolVarBranch::expand(Home home, const IntVarArgs& x, const BoolVarArgs& y) {
85 switch (select()) {
86 case IntBoolVarBranch::SEL_AFC_MAX:
87 case IntBoolVarBranch::SEL_AFC_SIZE_MAX:
88 if (!iafc)
89 iafc = IntAFC(home,x,decay());
90 if (!bafc)
91 bafc = BoolAFC(home,y,decay());
92 break;
93 case IntBoolVarBranch::SEL_ACTION_MAX:
94 case IntBoolVarBranch::SEL_ACTION_SIZE_MAX:
95 if (!iaction)
96 iaction = IntAction(home,x,decay());
97 if (!baction)
98 baction = BoolAction(home,y,decay());
99 break;
100 case IntBoolVarBranch::SEL_CHB_MAX:
101 case IntBoolVarBranch::SEL_CHB_SIZE_MAX:
102 if (!ichb)
103 ichb = IntCHB(home,x);
104 if (!bchb)
105 bchb = BoolCHB(home,y);
106 break;
107 default: ;
108 }
109 }
110
111
112
113 inline IntBoolVarBranch
114 INTBOOL_VAR_AFC_MAX(double d) {
115 return IntBoolVarBranch(IntBoolVarBranch::SEL_AFC_MAX,d);
116 }
117 inline IntBoolVarBranch
118 INTBOOL_VAR_AFC_MAX(IntAFC ia, BoolAFC ba) {
119 return IntBoolVarBranch(IntBoolVarBranch::SEL_AFC_MAX,ia,ba);
120 }
121 inline IntBoolVarBranch
122 INTBOOL_VAR_ACTION_MAX(double d) {
123 return IntBoolVarBranch(IntBoolVarBranch::SEL_ACTION_MAX,d);
124 }
125 inline IntBoolVarBranch
126 INTBOOL_VAR_ACTION_MAX(IntAction ia, BoolAction ba) {
127 return IntBoolVarBranch(IntBoolVarBranch::SEL_ACTION_MAX,ia,ba);
128 }
129 inline IntBoolVarBranch
130 INTBOOL_VAR_CHB_MAX(double d) {
131 return IntBoolVarBranch(IntBoolVarBranch::SEL_CHB_MAX,d);
132 }
133 inline IntBoolVarBranch
134 INTBOOL_VAR_CHB_MAX(IntCHB ic, BoolCHB bc) {
135 return IntBoolVarBranch(IntBoolVarBranch::SEL_CHB_MAX,ic,bc);
136 }
137 inline IntBoolVarBranch
138 INTBOOL_VAR_AFC_SIZE_MAX(double d) {
139 return IntBoolVarBranch(IntBoolVarBranch::SEL_AFC_SIZE_MAX,d);
140 }
141 inline IntBoolVarBranch
142 INTBOOL_VAR_AFC_SIZE_MAX(IntAFC ia, BoolAFC ba) {
143 return IntBoolVarBranch(IntBoolVarBranch::SEL_AFC_SIZE_MAX,ia,ba);
144 }
145 inline IntBoolVarBranch
146 INTBOOL_VAR_ACTION_SIZE_MAX(double d) {
147 return IntBoolVarBranch(IntBoolVarBranch::SEL_ACTION_SIZE_MAX,d);
148 }
149 inline IntBoolVarBranch
150 INTBOOL_VAR_ACTION_SIZE_MAX(IntAction ia, BoolAction ba) {
151 return IntBoolVarBranch(IntBoolVarBranch::SEL_ACTION_SIZE_MAX,ia,ba);
152 }
153 inline IntBoolVarBranch
154 INTBOOL_VAR_CHB_SIZE_MAX(double d) {
155 return IntBoolVarBranch(IntBoolVarBranch::SEL_CHB_SIZE_MAX,d);
156 }
157 inline IntBoolVarBranch
158 INTBOOL_VAR_CHB_SIZE_MAX(IntCHB ic, BoolCHB bc) {
159 return IntBoolVarBranch(IntBoolVarBranch::SEL_CHB_SIZE_MAX,ic,bc);
160 }
161
162
163
164 forceinline
165 MeritMaxAFC::MeritMaxAFC(Space&, const IntBoolVarBranch& ibvb)
166 : iafc(ibvb.intafc()), bafc(ibvb.boolafc()) {}
167 forceinline
168 MeritMaxAFC::MeritMaxAFC(Space&, MeritMaxAFC& m)
169 : iafc(m.iafc), bafc(m.bafc) {}
170 forceinline double
171 MeritMaxAFC::operator ()(Int::IntView x, int) const {
172 return x.afc();
173 }
174 forceinline double
175 MeritMaxAFC::operator ()(Int::BoolView x, int) const {
176 return x.afc();
177 }
178 forceinline void
179 MeritMaxAFC::dispose(void) {
180 iafc.~IntAFC();
181 bafc.~BoolAFC();
182 }
183
184
185 forceinline
186 MeritMaxAFCSize::MeritMaxAFCSize(Space&, const IntBoolVarBranch& ibvb)
187 : iafc(ibvb.intafc()), bafc(ibvb.boolafc()) {}
188 forceinline
189 MeritMaxAFCSize::MeritMaxAFCSize(Space&, MeritMaxAFCSize& m)
190 : iafc(m.iafc), bafc(m.bafc) {}
191 forceinline double
192 MeritMaxAFCSize::operator ()(Int::IntView x, int) const {
193 return x.afc() / x.size();
194 }
195 forceinline double
196 MeritMaxAFCSize::operator ()(Int::BoolView x, int) const {
197 return x.afc() / 2.0;
198 }
199 forceinline void
200 MeritMaxAFCSize::dispose(void) {
201 iafc.~IntAFC();
202 bafc.~BoolAFC();
203 }
204
205
206 forceinline
207 MeritMaxAction::MeritMaxAction(Space&, const IntBoolVarBranch& ibvb)
208 : iaction(ibvb.intaction()), baction(ibvb.boolaction()) {}
209 forceinline
210 MeritMaxAction::MeritMaxAction(Space&, MeritMaxAction& m)
211 : iaction(m.iaction), baction(m.baction) {}
212 forceinline double
213 MeritMaxAction::operator ()(Int::IntView, int i) const {
214 return iaction[i];
215 }
216 forceinline double
217 MeritMaxAction::operator ()(Int::BoolView, int i) const {
218 return baction[i];
219 }
220 forceinline void
221 MeritMaxAction::dispose(void) {
222 iaction.~IntAction();
223 baction.~BoolAction();
224 }
225
226
227 forceinline
228 MeritMaxActionSize::MeritMaxActionSize(Space&, const IntBoolVarBranch& ibvb)
229 : iaction(ibvb.intaction()), baction(ibvb.boolaction()) {}
230 forceinline
231 MeritMaxActionSize::MeritMaxActionSize(Space&, MeritMaxActionSize& m)
232 : iaction(m.iaction), baction(m.baction) {}
233 forceinline double
234 MeritMaxActionSize::operator ()(Int::IntView x, int i) const {
235 return iaction[i] / x.size();
236 }
237 forceinline double
238 MeritMaxActionSize::operator ()(Int::BoolView, int i) const {
239 return baction[i] / 2.0;
240 }
241 forceinline void
242 MeritMaxActionSize::dispose(void) {
243 iaction.~IntAction();
244 baction.~BoolAction();
245 }
246
247
248 forceinline
249 MeritMaxCHB::MeritMaxCHB(Space&, const IntBoolVarBranch& ibvb)
250 : ichb(ibvb.intchb()), bchb(ibvb.boolchb()) {}
251 forceinline
252 MeritMaxCHB::MeritMaxCHB(Space&, MeritMaxCHB& m)
253 : ichb(m.ichb), bchb(m.bchb) {}
254 forceinline double
255 MeritMaxCHB::operator ()(Int::IntView, int i) const {
256 return ichb[i];
257 }
258 forceinline double
259 MeritMaxCHB::operator ()(Int::BoolView, int i) const {
260 return bchb[i];
261 }
262 forceinline void
263 MeritMaxCHB::dispose(void) {
264 ichb.~IntCHB();
265 bchb.~BoolCHB();
266 }
267
268
269 forceinline
270 MeritMaxCHBSize::MeritMaxCHBSize(Space&, const IntBoolVarBranch& ibvb)
271 : ichb(ibvb.intchb()), bchb(ibvb.boolchb()) {}
272 forceinline
273 MeritMaxCHBSize::MeritMaxCHBSize(Space&, MeritMaxCHBSize& m)
274 : ichb(m.ichb), bchb(m.bchb) {}
275 forceinline double
276 MeritMaxCHBSize::operator ()(Int::IntView x, int i) const {
277 return ichb[i] / x.size();
278 }
279 forceinline double
280 MeritMaxCHBSize::operator ()(Int::BoolView, int i) const {
281 return bchb[i] / 2.0;
282 }
283 forceinline void
284 MeritMaxCHBSize::dispose(void) {
285 ichb.~IntCHB();
286 bchb.~BoolCHB();
287 }
288
289
290 forceinline
291 PosIntChoice::PosIntChoice(const Brancher& b, unsigned int a, int p, int n)
292 : Choice(b,a), _pos(p), _val(n) {}
293 forceinline int
294 PosIntChoice::pos(void) const {
295 return _pos;
296 }
297 forceinline int
298 PosIntChoice::val(void) const {
299 return _val;
300 }
301
302
303 forceinline
304 IntBoolBrancherBase::
305 IntBoolBrancherBase(Home home,
306 ViewArray<Int::IntView> x0,
307 ViewArray<Int::BoolView> y0,
308 ValSelCommitBase<Int::IntView,int>* xvsc0,
309 ValSelCommitBase<Int::BoolView,int>* yvsc0)
310 : Brancher(home), x(x0), y(y0), start(0), xvsc(xvsc0), yvsc(yvsc0) {
311 home.notice(*this,AP_DISPOSE,true);
312 }
313
314 forceinline
315 IntBoolBrancherBase::
316 IntBoolBrancherBase(Space& home, IntBoolBrancherBase& b)
317 : Brancher(home,b), start(b.start),
318 xvsc(b.xvsc->copy(home)), yvsc(b.yvsc->copy(home)) {
319 x.update(home,b.x);
320 y.update(home,b.y);
321 }
322
323 forceinline size_t
324 IntBoolBrancherBase::dispose(Space& home) {
325 home.ignore(*this,AP_DISPOSE,true);
326 xvsc->dispose(home);
327 yvsc->dispose(home);
328 (void) Brancher::dispose(home);
329 return sizeof(IntBoolBrancherBase);
330 }
331
332
333 template<class Merit>
334 forceinline
335 IntBoolBrancher<Merit>::
336 IntBoolBrancher(Home home,
337 ViewArray<Int::IntView> x,
338 ViewArray<Int::BoolView> y,
339 Merit& m,
340 ValSelCommitBase<Int::IntView,int>* xvsc,
341 ValSelCommitBase<Int::BoolView,int>* yvsc)
342 : IntBoolBrancherBase(home,x,y,xvsc,yvsc), merit(m) {}
343
344 template<class Merit>
345 forceinline void
346 IntBoolBrancher<Merit>::
347 post(Home home,
348 ViewArray<Int::IntView> x,
349 ViewArray<Int::BoolView> y,
350 Merit& m,
351 ValSelCommitBase<Int::IntView,int>* xvsc,
352 ValSelCommitBase<Int::BoolView,int>* yvsc) {
353 (void) new (home) IntBoolBrancher<Merit>(home, x, y, m, xvsc, yvsc);
354 }
355
356 template<class Merit>
357 forceinline
358 IntBoolBrancher<Merit>::
359 IntBoolBrancher(Space& home, IntBoolBrancher<Merit>& b)
360 : IntBoolBrancherBase(home,b), merit(home, b.merit) {
361 }
362
363 template<class Merit>
364 Actor*
365 IntBoolBrancher<Merit>::copy(Space& home) {
366 return new (home) IntBoolBrancher<Merit>(home,*this);
367 }
368
369 template<class Merit>
370 const Choice*
371 IntBoolBrancher<Merit>::choice(Space& home) {
372 int p = start;
373 double m;
374 if (p < x.size()) {
375 assert(!x[p].assigned());
376 m=merit(x[p],p);
377 for (int i=p+1; i<x.size(); i++)
378 if (!x[i].assigned()) {
379 double mi = merit(x[i],i);
380 if (mi > m) {
381 m=mi; p=i;
382 }
383 }
384 for (int i=0; i<y.size(); i++)
385 if (!y[i].assigned()) {
386 double mi = merit(y[i],i);
387 if (mi > m) {
388 m=mi; p=i+x.size();
389 }
390 }
391 } else {
392 assert(!y[p-x.size()].assigned());
393 m=merit(y[p-x.size()],p-x.size());
394 for (int i=p-x.size()+1; i<y.size(); i++)
395 if (!y[i].assigned()) {
396 double mi = merit(y[i],i);
397 if (mi > m) {
398 m=mi; p=i+x.size();
399 }
400 }
401 }
402 int v;
403 if (p < x.size()) {
404 v=xvsc->val(home,x[p],p);
405 } else {
406 v=yvsc->val(home,y[p-x.size()],p-x.size());
407 }
408 return new PosIntChoice(*this,2,p,v);
409 }
410
411 template<class Merit>
412 size_t
413 IntBoolBrancher<Merit>::dispose(Space& home) {
414 merit.dispose();
415 (void) IntBoolBrancherBase::dispose(home);
416 return sizeof(IntBoolBrancher<Merit>);
417 }
418
419
420 forceinline BoolValBranch
421 i2b(const IntValBranch& ivb) {
422 switch (ivb.select()) {
423 case IntValBranch::SEL_MIN:
424 case IntValBranch::SEL_MED:
425 case IntValBranch::SEL_SPLIT_MIN:
426 case IntValBranch::SEL_RANGE_MIN:
427 return BOOL_VAL_MIN();
428 case IntValBranch::SEL_MAX:
429 case IntValBranch::SEL_SPLIT_MAX:
430 case IntValBranch::SEL_RANGE_MAX:
431 return BOOL_VAL_MAX();
432 case IntValBranch::SEL_RND:
433 return BOOL_VAL_RND(ivb.rnd());
434 case IntValBranch::SEL_VAL_COMMIT:
435 default:
436 GECODE_NEVER;
437 }
438 GECODE_NEVER;
439 return BOOL_VAL_MIN();
440 }
441
442}}
443
444// STATISTICS: flatzinc-branch
445