this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Christopher Mears <chris.mears@monash.edu>
5 *
6 * Copyright:
7 * Christopher Mears, 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
34#include <gecode/int/ldsb.hh>
35#include <gecode/int/branch.hh>
36
37#include <map>
38
39namespace Gecode { namespace Int { namespace LDSB {
40
41 std::pair<int,int>
42 findVar(int *indices, unsigned int n_values, unsigned int seq_size, int index) {
43 unsigned int seq = 0;
44 unsigned int pos = 0;
45 for (unsigned int i=0U ; i<n_values ; i++) {
46 if (indices[i] == index)
47 return std::pair<int,int>(seq,pos);
48 pos++;
49 if (pos == seq_size) {
50 pos = 0;
51 seq++;
52 }
53 }
54 return std::pair<int,int>(-1,-1);
55 }
56
57}}}
58
59namespace Gecode {
60 using namespace Int::LDSB;
61
62 SymmetryHandle VariableSymmetry(const IntVarArgs& vars) {
63 ArgArray<VarImpBase*> a(vars.size());
64 for (int i = 0 ; i < vars.size() ; i++)
65 a[i] = vars[i].varimp();
66 return SymmetryHandle(new VariableSymmetryObject(a));
67 }
68 SymmetryHandle VariableSymmetry(const BoolVarArgs& vars) {
69 ArgArray<VarImpBase*> a(vars.size());
70 for (int i = 0 ; i < vars.size() ; i++)
71 a[i] = vars[i].varimp();
72 return SymmetryHandle(new VariableSymmetryObject(a));
73 }
74 SymmetryHandle VariableSymmetry(const IntVarArgs& x,
75 const IntArgs& indices) {
76 IntVarArgs xs(indices.size());
77 for (int i = 0 ; i < indices.size() ; i++)
78 xs[i] = x[indices[i]];
79 return VariableSymmetry(xs);
80 }
81 SymmetryHandle ValueSymmetry(const IntArgs& vs) {
82 return SymmetryHandle(new ValueSymmetryObject(IntSet(vs)));
83 }
84 SymmetryHandle ValueSymmetry(const IntSet& vs) {
85 return SymmetryHandle(new ValueSymmetryObject(vs));
86 }
87 SymmetryHandle ValueSymmetry(IntVar x) {
88 return ValueSymmetry(IntSet(x.min(), x.max()));
89 }
90 SymmetryHandle VariableSequenceSymmetry(const IntVarArgs& vars, int ss) {
91 ArgArray<VarImpBase*> a(vars.size());
92 for (int i = 0 ; i < vars.size() ; i++)
93 a[i] = vars[i].varimp();
94 return SymmetryHandle(new VariableSequenceSymmetryObject(a, ss));
95 }
96 SymmetryHandle VariableSequenceSymmetry(const BoolVarArgs& vars, int ss) {
97 ArgArray<VarImpBase*> a(vars.size());
98 for (int i = 0 ; i < vars.size() ; i++)
99 a[i] = vars[i].varimp();
100 return SymmetryHandle(new VariableSequenceSymmetryObject(a, ss));
101 }
102 SymmetryHandle ValueSequenceSymmetry(const IntArgs& vs, int ss) {
103 return SymmetryHandle(new ValueSequenceSymmetryObject(vs, ss));
104 }
105
106 SymmetryHandle values_reflect(int lower, int upper) {
107 int n = (upper-lower+1)/2;
108 IntArgs a(n*2);
109 int i = lower;
110 int j = upper;
111 int k = 0;
112 while (i < j) {
113 a[k] = j;
114 a[n+k] = i;
115 i++;
116 j--;
117 k++;
118 }
119 return ValueSequenceSymmetry(a,n);
120 }
121 SymmetryHandle values_reflect(const IntVar& x) {
122 return values_reflect(x.min(), x.max());
123 }
124}
125
126
127namespace Gecode { namespace Int { namespace LDSB {
128
129 /// Map from variable implementation to index
130 class VariableMap : public std::map<VarImpBase*,int> {};
131
132 /*
133 * The duplication in createIntSym/createBoolSym is undesirable,
134 * and so is the use of dynamic_cast to tell the symmetries
135 * apart.
136 */
137
138 /// Create an integer symmetry implementation from a symmetry handle
139 SymmetryImp<IntView>*
140 createIntSym(Space& home, const SymmetryHandle& s,
141 VariableMap variableMap) {
142 VariableSymmetryObject* varref =
143 dynamic_cast<VariableSymmetryObject*>(s.ref);
144 ValueSymmetryObject* valref =
145 dynamic_cast<ValueSymmetryObject*>(s.ref);
146 VariableSequenceSymmetryObject* varseqref =
147 dynamic_cast<VariableSequenceSymmetryObject*>(s.ref);
148 ValueSequenceSymmetryObject* valseqref =
149 dynamic_cast<ValueSequenceSymmetryObject*>(s.ref);
150 if (varref) {
151 int n = varref->nxs;
152 int* indices = home.alloc<int>(n);
153 for (int i = 0 ; i < n ; i++) {
154 VariableMap::const_iterator index = variableMap.find(varref->xs[i]);
155 if (index == variableMap.end())
156 throw LDSBUnbranchedVariable("VariableSymmetryObject::createInt");
157 indices[i] = index->second;
158 }
159 return new (home) VariableSymmetryImp<IntView>(home, indices, n);
160 }
161 if (valref) {
162 int n = valref->values.size();
163 int *vs = home.alloc<int>(n);
164 int i = 0;
165 for (IntSetValues v(valref->values) ; v() ; ++v) {
166 vs[i] = v.val();
167 i++;
168 }
169 return new (home) ValueSymmetryImp<IntView>(home, vs, n);
170 }
171 if (varseqref) {
172 int n = varseqref->nxs;
173 int* indices = home.alloc<int>(n);
174 for (int i = 0 ; i < n ; i++) {
175 VariableMap::const_iterator index =
176 variableMap.find(varseqref->xs[i]);
177 if (index == variableMap.end())
178 throw LDSBUnbranchedVariable("VariableSequenceSymmetryObject::createInt");
179 indices[i] = index->second;
180 }
181 return new (home) VariableSequenceSymmetryImp<IntView>(home, indices, n,
182 varseqref->seq_size);
183 }
184 if (valseqref) {
185 unsigned int n = valseqref->values.size();
186 int *vs = home.alloc<int>(n);
187 for (unsigned int i = 0 ; i < n ; i++)
188 vs[i] = valseqref->values[i];
189 return new (home) ValueSequenceSymmetryImp<IntView>(home, vs, n,
190 valseqref->seq_size);
191 }
192 GECODE_NEVER;
193 return nullptr;
194 }
195
196 /// Create a boolean symmetry implementation from a symmetry handle
197 SymmetryImp<BoolView>* createBoolSym(Space& home, const SymmetryHandle& s,
198 VariableMap variableMap) {
199 VariableSymmetryObject* varref =
200 dynamic_cast<VariableSymmetryObject*>(s.ref);
201 ValueSymmetryObject* valref =
202 dynamic_cast<ValueSymmetryObject*>(s.ref);
203 VariableSequenceSymmetryObject* varseqref =
204 dynamic_cast<VariableSequenceSymmetryObject*>(s.ref);
205 ValueSequenceSymmetryObject* valseqref =
206 dynamic_cast<ValueSequenceSymmetryObject*>(s.ref);
207 if (varref) {
208 int n = varref->nxs;
209 int* indices = home.alloc<int>(n);
210 for (int i = 0 ; i < n ; i++) {
211 VariableMap::const_iterator index = variableMap.find(varref->xs[i]);
212 if (index == variableMap.end())
213 throw LDSBUnbranchedVariable("VariableSymmetryObject::createBool");
214 indices[i] = index->second;
215 }
216 return new (home) VariableSymmetryImp<BoolView>(home, indices, n);
217 }
218 if (valref) {
219 int n = valref->values.size();
220 int *vs = home.alloc<int>(n);
221 int i = 0;
222 for (IntSetValues v(valref->values) ; v() ; ++v) {
223 vs[i] = v.val();
224 i++;
225 }
226 return new (home) ValueSymmetryImp<BoolView>(home, vs, n);
227 }
228 if (varseqref) {
229 int n = varseqref->nxs;
230 int* indices = home.alloc<int>(n);
231 for (int i = 0 ; i < n ; i++) {
232 VariableMap::const_iterator index =
233 variableMap.find(varseqref->xs[i]);
234 if (index == variableMap.end())
235 throw LDSBUnbranchedVariable("VariableSequenceSymmetryObject::createBool");
236 indices[i] = index->second;
237 }
238 return new (home) VariableSequenceSymmetryImp<BoolView>(home, indices,
239 n, varseqref->seq_size);
240 }
241 if (valseqref) {
242 unsigned int n = valseqref->values.size();
243 int *vs = home.alloc<int>(n);
244 for (unsigned int i = 0 ; i < n ; i++)
245 vs[i] = valseqref->values[i];
246 return new (home) ValueSequenceSymmetryImp<BoolView>(home, vs, n,
247 valseqref->seq_size);
248 }
249 GECODE_NEVER;
250 return nullptr;
251 }
252}}}
253
254namespace Gecode {
255
256 using namespace Int::LDSB;
257
258 void
259 branch(Home home, const IntVarArgs& x,
260 IntVarBranch vars, IntValBranch vals,
261 const Symmetries& syms,
262 IntBranchFilter bf,
263 IntVarValPrint vvp) {
264 using namespace Int;
265 if (home.failed()) return;
266 vars.expand(home,x);
267 ViewArray<IntView> xv(home,x);
268 ViewSel<IntView>* vs[1] = {
269 Branch::viewsel(home,vars)
270 };
271 switch (vals.select()) {
272 case IntValBranch::SEL_SPLIT_MIN:
273 case IntValBranch::SEL_SPLIT_MAX:
274 case IntValBranch::SEL_RANGE_MIN:
275 case IntValBranch::SEL_RANGE_MAX:
276 case IntValBranch::SEL_VALUES_MIN:
277 case IntValBranch::SEL_VALUES_MAX:
278 throw LDSBBadValueSelection("Int::LDSB::branch");
279 break;
280 case IntValBranch::SEL_VAL_COMMIT:
281 if (vals.commit())
282 throw LDSBBadValueSelection("Int::LDSB::branch");
283 // If vals.commit() is valid, it means it will commit with
284 // binary branching, which is OK for LDSB, so we
285 // fall through
286 default:
287 // Construct mapping from each variable in the array to its index
288 // in the array.
289 VariableMap variableMap;
290 for (int i = 0 ; i < x.size() ; i++)
291 variableMap[x[i].varimp()] = i;
292
293 // Convert the modelling-level Symmetries object into an array of
294 // SymmetryImp objects.
295 int n = syms.size();
296 SymmetryImp<IntView>** array =
297 static_cast<Space&>(home).alloc<SymmetryImp<IntView>* >(n);
298 for (int i = 0 ; i < n ; i++) {
299 array[i] = createIntSym(home, syms[i], variableMap);
300 }
301
302 postldsbbrancher<IntView,1,int,2>
303 (home,xv,vs,Branch::valselcommit(home,vals),
304 array,n,bf,vvp);
305 }
306 }
307
308 void
309 branch(Home home, const IntVarArgs& x,
310 TieBreak<IntVarBranch> vars, IntValBranch vals,
311 const Symmetries& syms,
312 IntBranchFilter bf,
313 IntVarValPrint vvp) {
314 using namespace Int;
315 if (home.failed()) return;
316 vars.a.expand(home,x);
317 if ((vars.a.select() == IntVarBranch::SEL_NONE) ||
318 (vars.a.select() == IntVarBranch::SEL_RND))
319 vars.b = INT_VAR_NONE();
320 vars.b.expand(home,x);
321 if ((vars.b.select() == IntVarBranch::SEL_NONE) ||
322 (vars.b.select() == IntVarBranch::SEL_RND))
323 vars.c = INT_VAR_NONE();
324 vars.c.expand(home,x);
325 if ((vars.c.select() == IntVarBranch::SEL_NONE) ||
326 (vars.c.select() == IntVarBranch::SEL_RND))
327 vars.d = INT_VAR_NONE();
328 vars.d.expand(home,x);
329 if (vars.b.select() == IntVarBranch::SEL_NONE) {
330 branch(home,x,vars.a,vals,syms,bf,vvp);
331 } else {
332 // Construct mapping from each variable in the array to its index
333 // in the array.
334 VariableMap variableMap;
335 for (int i = 0 ; i < x.size() ; i++)
336 variableMap[x[i].varimp()] = i;
337
338 // Convert the modelling-level Symmetries object into an array of
339 // SymmetryImp objects.
340 int n = syms.size();
341 SymmetryImp<IntView>** array =
342 static_cast<Space&>(home).alloc<SymmetryImp<IntView>* >(n);
343 for (int i = 0 ; i < n ; i++) {
344 array[i] = createIntSym(home, syms[i], variableMap);
345 }
346
347 ViewArray<IntView> xv(home,x);
348 if (vars.c.select() == IntVarBranch::SEL_NONE) {
349 ViewSel<IntView>* vs[2] = {
350 Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b)
351 };
352 switch (vals.select()) {
353 case IntValBranch::SEL_SPLIT_MIN:
354 case IntValBranch::SEL_SPLIT_MAX:
355 case IntValBranch::SEL_RANGE_MIN:
356 case IntValBranch::SEL_RANGE_MAX:
357 case IntValBranch::SEL_VALUES_MIN:
358 case IntValBranch::SEL_VALUES_MAX:
359 throw LDSBBadValueSelection("Int::LDSB::branch");
360 break;
361 case IntValBranch::SEL_VAL_COMMIT:
362 if (vals.commit())
363 throw LDSBBadValueSelection("Int::LDSB::branch");
364 // If vals.commit() is valid, it means it will commit with
365 // binary branching, which is OK for LDSB, so we
366 // fall through
367 default:
368 postldsbbrancher<IntView,2,int,2>
369 (home,xv,vs,Branch::valselcommit(home,vals),
370 array,n,bf,vvp);
371 }
372 } else if (vars.d.select() == IntVarBranch::SEL_NONE) {
373 ViewSel<IntView>* vs[3] = {
374 Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b),
375 Branch::viewsel(home,vars.c)
376 };
377 switch (vals.select()) {
378 case IntValBranch::SEL_SPLIT_MIN:
379 case IntValBranch::SEL_SPLIT_MAX:
380 case IntValBranch::SEL_RANGE_MIN:
381 case IntValBranch::SEL_RANGE_MAX:
382 case IntValBranch::SEL_VALUES_MIN:
383 case IntValBranch::SEL_VALUES_MAX:
384 throw LDSBBadValueSelection("Int::LDSB::branch");
385 break;
386 case IntValBranch::SEL_VAL_COMMIT:
387 if (vals.commit())
388 throw LDSBBadValueSelection("Int::LDSB::branch");
389 // If vals.commit() is valid, it means it will commit with
390 // binary branching, which is OK for LDSB, so we
391 // fall through
392 default:
393 postldsbbrancher<IntView,3,int,2>
394 (home,xv,vs,Branch::valselcommit(home,vals),
395 array,n,bf,vvp);
396 }
397 } else {
398 ViewSel<IntView>* vs[4] = {
399 Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b),
400 Branch::viewsel(home,vars.c),Branch::viewsel(home,vars.d)
401 };
402 switch (vals.select()) {
403 case IntValBranch::SEL_SPLIT_MIN:
404 case IntValBranch::SEL_SPLIT_MAX:
405 case IntValBranch::SEL_RANGE_MIN:
406 case IntValBranch::SEL_RANGE_MAX:
407 case IntValBranch::SEL_VALUES_MIN:
408 case IntValBranch::SEL_VALUES_MAX:
409 throw LDSBBadValueSelection("Int::LDSB::branch");
410 break;
411 case IntValBranch::SEL_VAL_COMMIT:
412 if (vals.commit())
413 throw LDSBBadValueSelection("Int::LDSB::branch");
414 // If vals.commit() is valid, it means it will commit with
415 // binary branching, which is OK for LDSB, so we
416 // fall through
417 default:
418 postldsbbrancher<IntView,4,int,2>
419 (home,xv,vs,Branch::valselcommit(home,vals),
420 array,n,bf,vvp);
421 }
422 }
423 }
424 }
425
426 void
427 branch(Home home, const BoolVarArgs& x,
428 BoolVarBranch vars, BoolValBranch vals,
429 const Symmetries& syms,
430 BoolBranchFilter bf,
431 BoolVarValPrint vvp) {
432 using namespace Int;
433 if (home.failed()) return;
434 vars.expand(home,x);
435 ViewArray<BoolView> xv(home,x);
436 ViewSel<BoolView>* vs[1] = {
437 Branch::viewsel(home,vars)
438 };
439
440 // Construct mapping from each variable in the array to its index
441 // in the array.
442 VariableMap variableMap;
443 for (int i = 0 ; i < x.size() ; i++)
444 variableMap[x[i].varimp()] = i;
445
446 // Convert the modelling-level Symmetries object into an array of
447 // SymmetryImp objects.
448 int n = syms.size();
449 SymmetryImp<BoolView>** array =
450 static_cast<Space&>(home).alloc<SymmetryImp<BoolView>* >(n);
451 for (int i = 0 ; i < n ; i++) {
452 array[i] = createBoolSym(home, syms[i], variableMap);
453 }
454
455 // Technically these "bad" value selection could in fact work with
456 // LDSB, because they degenerate to binary splitting for
457 // Booleans. Nonetheless, we explicitly forbid them for
458 // consistency with the integer version.
459 switch (vals.select()) {
460 case BoolValBranch::SEL_VAL_COMMIT:
461 if (vals.commit())
462 throw LDSBBadValueSelection("Int::LDSB::branch");
463 // If vals.commit() is valid, it means it will commit with
464 // binary branching, which is OK for LDSB, so we
465 // fall through
466 default:
467 postldsbbrancher<BoolView,1,int,2>
468 (home,xv,vs,Branch::valselcommit(home,vals),array,n,bf,vvp);
469 }
470 }
471
472
473 void
474 branch(Home home, const BoolVarArgs& x,
475 TieBreak<BoolVarBranch> vars, BoolValBranch vals,
476 const Symmetries& syms,
477 BoolBranchFilter bf,
478 BoolVarValPrint vvp) {
479 using namespace Int;
480 if (home.failed()) return;
481 vars.a.expand(home,x);
482 if ((vars.a.select() == BoolVarBranch::SEL_NONE) ||
483 (vars.a.select() == BoolVarBranch::SEL_RND))
484 vars.b = BOOL_VAR_NONE();
485 vars.b.expand(home,x);
486 if ((vars.b.select() == BoolVarBranch::SEL_NONE) ||
487 (vars.b.select() == BoolVarBranch::SEL_RND))
488 vars.c = BOOL_VAR_NONE();
489 vars.c.expand(home,x);
490 if ((vars.c.select() == BoolVarBranch::SEL_NONE) ||
491 (vars.c.select() == BoolVarBranch::SEL_RND))
492 vars.d = BOOL_VAR_NONE();
493 vars.d.expand(home,x);
494 if (vars.b.select() == BoolVarBranch::SEL_NONE) {
495 branch(home,x,vars.a,vals,syms,bf,vvp);
496 } else {
497 // Construct mapping from each variable in the array to its index
498 // in the array.
499 VariableMap variableMap;
500 for (int i = 0 ; i < x.size() ; i++)
501 variableMap[x[i].varimp()] = i;
502
503 // Convert the modelling-level Symmetries object into an array of
504 // SymmetryImp objects.
505 int n = syms.size();
506 SymmetryImp<BoolView>** array =
507 static_cast<Space&>(home).alloc<SymmetryImp<BoolView>* >(n);
508 for (int i = 0 ; i < n ; i++) {
509 array[i] = createBoolSym(home, syms[i], variableMap);
510 }
511
512 // Technically these "bad" value selection could in fact work with
513 // LDSB, because they degenerate to binary splitting for
514 // Booleans. Nonetheless, we explicitly forbid them for
515 // consistency with the integer version.
516 switch (vals.select()) {
517 case BoolValBranch::SEL_VAL_COMMIT:
518 if (vals.commit())
519 throw LDSBBadValueSelection("Int::LDSB::branch");
520 // If vals.commit() is valid, it means it will commit with
521 // binary branching, which is OK for LDSB, so we
522 // fall through
523 default:
524 ;
525 // Do nothing and continue.
526 }
527
528 ViewArray<BoolView> xv(home,x);
529 ValSelCommitBase<BoolView,int>*
530 vsc = Branch::valselcommit(home,vals);
531 if (vars.c.select() == BoolVarBranch::SEL_NONE) {
532 ViewSel<BoolView>* vs[2] = {
533 Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b)
534 };
535 postldsbbrancher<BoolView,2,int,2>(home,xv,vs,vsc,array,n,bf,vvp);
536 } else if (vars.d.select() == BoolVarBranch::SEL_NONE) {
537 ViewSel<BoolView>* vs[3] = {
538 Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b),
539 Branch::viewsel(home,vars.c)
540 };
541 postldsbbrancher<BoolView,3,int,2>(home,xv,vs,vsc,array,n,bf,vvp);
542 } else {
543 ViewSel<BoolView>* vs[4] = {
544 Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b),
545 Branch::viewsel(home,vars.c),Branch::viewsel(home,vars.d)
546 };
547 postldsbbrancher<BoolView,4,int,2>(home,xv,vs,vsc,array,n,bf,vvp);
548 }
549 }
550 }
551
552}
553
554
555
556// STATISTICS: int-branch