Generated on Sat May 25 2013 18:00:37 for Gecode by doxygen 1.8.3.1
ldsb.cpp
Go to the documentation of this file.
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  * Last modified:
10  * $Date: 2013-03-12 20:16:24 +0100 (Tue, 12 Mar 2013) $ by $Author: schulte $
11  * $Revision: 13513 $
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 #include <gecode/int/ldsb.hh>
39 #include <gecode/int/branch.hh>
40 
41 #include <map>
42 
43 namespace Gecode { namespace Int { namespace LDSB {
44 
45  std::pair<int,int>
46  findVar(int *indices, unsigned int n_values, unsigned int seq_size, int index) {
47  unsigned int seq = 0;
48  unsigned int pos = 0;
49  for (unsigned int i = 0 ; i < n_values ; i++) {
50  if (indices[i] == index)
51  return std::pair<int,int>(seq,pos);
52  pos++;
53  if (pos == seq_size) {
54  pos = 0;
55  seq++;
56  }
57  }
58  return std::pair<int,int>(-1,-1);
59  }
60 
61 }}}
62 
63 namespace Gecode {
64  using namespace Int::LDSB;
65 
68  for (int i = 0 ; i < vars.size() ; i++)
69  a[i] = vars[i].varimp();
71  }
74  for (int i = 0 ; i < vars.size() ; i++)
75  a[i] = vars[i].varimp();
77  }
79  const IntArgs& indices) {
80  IntVarArgs xs(indices.size());
81  for (int i = 0 ; i < indices.size() ; i++)
82  xs[i] = x[indices[i]];
83  return VariableSymmetry(xs);
84  }
86  return SymmetryHandle(new ValueSymmetryObject(IntSet(vs)));
87  }
89  return SymmetryHandle(new ValueSymmetryObject(vs));
90  }
92  return ValueSymmetry(IntSet(x.min(), x.max()));
93  }
96  for (int i = 0 ; i < vars.size() ; i++)
97  a[i] = vars[i].varimp();
99  }
101  ArgArray<VarImpBase*> a(vars.size());
102  for (int i = 0 ; i < vars.size() ; i++)
103  a[i] = vars[i].varimp();
105  }
107  return SymmetryHandle(new ValueSequenceSymmetryObject(vs, ss));
108  }
109 
110  SymmetryHandle values_reflect(int lower, int upper) {
111  int n = upper-lower+1;
112  IntArgs a(n*2);
113  int i = lower;
114  int j = upper;
115  int k = 0;
116  while (i < j) {
117  a[k] = j;
118  a[n+k] = i;
119  i++;
120  j--;
121  }
122  return ValueSequenceSymmetry(a,n);
123  }
125  return values_reflect(x.min(), x.max());
126  }
127 }
128 
129 
130 namespace Gecode { namespace Int { namespace LDSB {
131 
133  class VariableMap : public std::map<VarImpBase*,int> {};
134 
135  /*
136  * The duplication in createIntSym/createBoolSym is undesirable,
137  * and so is the use of dynamic_cast to tell the symmetries
138  * apart.
139  */
140 
144  VariableMap variableMap) {
145  VariableSymmetryObject* varref =
146  dynamic_cast<VariableSymmetryObject*>(s.ref);
147  ValueSymmetryObject* valref =
148  dynamic_cast<ValueSymmetryObject*>(s.ref);
149  VariableSequenceSymmetryObject* varseqref =
150  dynamic_cast<VariableSequenceSymmetryObject*>(s.ref);
151  ValueSequenceSymmetryObject* valseqref =
152  dynamic_cast<ValueSequenceSymmetryObject*>(s.ref);
153  if (varref) {
154  int n = varref->nxs;
155  int* indices = home.alloc<int>(n);
156  for (int i = 0 ; i < n ; i++) {
157  VariableMap::const_iterator index = variableMap.find(varref->xs[i]);
158  if (index == variableMap.end())
159  throw LDSBUnbranchedVariable("VariableSymmetryObject::createInt");
160  indices[i] = index->second;
161  }
162  return new (home) VariableSymmetryImp<IntView>(home, indices, n);
163  }
164  if (valref) {
165  int n = valref->values.size();
166  int *vs = home.alloc<int>(n);
167  int i = 0;
168  for (IntSetValues v(valref->values) ; v() ; ++v) {
169  vs[i] = v.val();
170  i++;
171  }
172  return new (home) ValueSymmetryImp<IntView>(home, vs, n);
173  }
174  if (varseqref) {
175  int n = varseqref->nxs;
176  int* indices = home.alloc<int>(n);
177  for (int i = 0 ; i < n ; i++) {
178  VariableMap::const_iterator index =
179  variableMap.find(varseqref->xs[i]);
180  if (index == variableMap.end())
181  throw LDSBUnbranchedVariable("VariableSequenceSymmetryObject::createInt");
182  indices[i] = index->second;
183  }
184  return new (home) VariableSequenceSymmetryImp<IntView>(home, indices, n,
185  varseqref->seq_size);
186  }
187  if (valseqref) {
188  unsigned int n = valseqref->values.size();
189  int *vs = home.alloc<int>(n);
190  for (unsigned int i = 0 ; i < n ; i++)
191  vs[i] = valseqref->values[i];
192  return new (home) ValueSequenceSymmetryImp<IntView>(home, vs, n,
193  valseqref->seq_size);
194  }
195  GECODE_NEVER;
196  return NULL;
197  }
198 
201  VariableMap variableMap) {
202  VariableSymmetryObject* varref =
203  dynamic_cast<VariableSymmetryObject*>(s.ref);
204  ValueSymmetryObject* valref =
205  dynamic_cast<ValueSymmetryObject*>(s.ref);
206  VariableSequenceSymmetryObject* varseqref =
207  dynamic_cast<VariableSequenceSymmetryObject*>(s.ref);
208  ValueSequenceSymmetryObject* valseqref =
209  dynamic_cast<ValueSequenceSymmetryObject*>(s.ref);
210  if (varref) {
211  int n = varref->nxs;
212  int* indices = home.alloc<int>(n);
213  for (int i = 0 ; i < n ; i++) {
214  VariableMap::const_iterator index = variableMap.find(varref->xs[i]);
215  if (index == variableMap.end())
216  throw LDSBUnbranchedVariable("VariableSymmetryObject::createBool");
217  indices[i] = index->second;
218  }
219  return new (home) VariableSymmetryImp<BoolView>(home, indices, n);
220  }
221  if (valref) {
222  int n = valref->values.size();
223  int *vs = home.alloc<int>(n);
224  int i = 0;
225  for (IntSetValues v(valref->values) ; v() ; ++v) {
226  vs[i] = v.val();
227  i++;
228  }
229  return new (home) ValueSymmetryImp<BoolView>(home, vs, n);
230  }
231  if (varseqref) {
232  int n = varseqref->nxs;
233  int* indices = home.alloc<int>(n);
234  for (int i = 0 ; i < n ; i++) {
235  VariableMap::const_iterator index =
236  variableMap.find(varseqref->xs[i]);
237  if (index == variableMap.end())
238  throw LDSBUnbranchedVariable("VariableSequenceSymmetryObject::createBool");
239  indices[i] = index->second;
240  }
241  return new (home) VariableSequenceSymmetryImp<BoolView>(home, indices,
242  n, varseqref->seq_size);
243  }
244  if (valseqref) {
245  unsigned int n = valseqref->values.size();
246  int *vs = home.alloc<int>(n);
247  for (unsigned int i = 0 ; i < n ; i++)
248  vs[i] = valseqref->values[i];
249  return new (home) ValueSequenceSymmetryImp<BoolView>(home, vs, n,
250  valseqref->seq_size);
251  }
252  GECODE_NEVER;
253  return NULL;
254  }
255 }}}
256 
257 namespace Gecode {
258 
259  using namespace Int::LDSB;
260 
261  BrancherHandle
262  branch(Home home, const IntVarArgs& x,
263  IntVarBranch vars, IntValBranch vals,
264  const Symmetries& syms, IntBranchFilter bf) {
265  using namespace Int;
266  if (home.failed()) return BrancherHandle();
267  ViewArray<IntView> xv(home,x);
268  ViewSel<IntView>* vs[1] = {
269  Branch::viewselint(home,vars)
270  };
271  switch (vals.select()) {
278  throw LDSBBadValueSelection("Int::LDSB::branch");
279  break;
281  if (vals.commit() != NULL)
282  throw LDSBBadValueSelection("Int::LDSB::branch");
283  // If vals.commit() returns NULL, it means it will commit with
284  // binary branching, which is OK for LDSB, so we fall through.
285  default:
286  // Construct mapping from each variable in the array to its index
287  // in the array.
288  VariableMap variableMap;
289  for (int i = 0 ; i < x.size() ; i++)
290  variableMap[x[i].varimp()] = i;
291 
292  // Convert the modelling-level Symmetries object into an array of
293  // SymmetryImp objects.
294  int n = syms.size();
295  SymmetryImp<IntView>** array =
296  static_cast<Space&>(home).alloc<SymmetryImp<IntView>* >(n);
297  for (int i = 0 ; i < n ; i++) {
298  array[i] = createIntSym(home, syms[i], variableMap);
299  }
300 
302  (home,xv,vs,Branch::valselcommitint(home,x.size(),vals),array,n,bf);
303  }
304  }
305 
306  BrancherHandle
307  branch(Home home, const IntVarArgs& x,
309  const Symmetries& syms, IntBranchFilter bf) {
310  using namespace Int;
311  if (home.failed()) return BrancherHandle();
312  vars.a.expand(home,x);
313  if ((vars.a.select() == IntVarBranch::SEL_NONE) ||
314  (vars.a.select() == IntVarBranch::SEL_RND))
315  vars.b = INT_VAR_NONE();
316  vars.b.expand(home,x);
317  if ((vars.b.select() == IntVarBranch::SEL_NONE) ||
318  (vars.b.select() == IntVarBranch::SEL_RND))
319  vars.c = INT_VAR_NONE();
320  vars.c.expand(home,x);
321  if ((vars.c.select() == IntVarBranch::SEL_NONE) ||
322  (vars.c.select() == IntVarBranch::SEL_RND))
323  vars.d = INT_VAR_NONE();
324  vars.d.expand(home,x);
325  if (vars.b.select() == IntVarBranch::SEL_NONE) {
326  return branch(home,x,vars.a,vals,syms,bf);
327  } else {
328  // Construct mapping from each variable in the array to its index
329  // in the array.
330  VariableMap variableMap;
331  for (int i = 0 ; i < x.size() ; i++)
332  variableMap[x[i].varimp()] = i;
333 
334  // Convert the modelling-level Symmetries object into an array of
335  // SymmetryImp objects.
336  int n = syms.size();
337  SymmetryImp<IntView>** array =
338  static_cast<Space&>(home).alloc<SymmetryImp<IntView>* >(n);
339  for (int i = 0 ; i < n ; i++) {
340  array[i] = createIntSym(home, syms[i], variableMap);
341  }
342 
343  ViewArray<IntView> xv(home,x);
344  if (vars.c.select() == IntVarBranch::SEL_NONE) {
345  ViewSel<IntView>* vs[2] = {
346  Branch::viewselint(home,vars.a),Branch::viewselint(home,vars.b)
347  };
348  switch (vals.select()) {
355  throw LDSBBadValueSelection("Int::LDSB::branch");
356  break;
358  if (vals.commit() != NULL)
359  throw LDSBBadValueSelection("Int::LDSB::branch");
360  // If vals.commit() returns NULL, it means it will commit with
361  // binary branching, which is OK for LDSB, so we fall through.
362  default:
364  ::post(home,xv,vs,Branch::valselcommitint(home,x.size(),vals),
365  array,n,bf);
366  }
367  } else if (vars.d.select() == IntVarBranch::SEL_NONE) {
368  ViewSel<IntView>* vs[3] = {
369  Branch::viewselint(home,vars.a),Branch::viewselint(home,vars.b),
370  Branch::viewselint(home,vars.c)
371  };
372  switch (vals.select()) {
379  throw LDSBBadValueSelection("Int::LDSB::branch");
380  break;
382  if (vals.commit() != NULL)
383  throw LDSBBadValueSelection("Int::LDSB::branch");
384  // If vals.commit() returns NULL, it means it will commit with
385  // binary branching, which is OK for LDSB, so we fall through.
386  default:
388  ::post(home,xv,vs,Branch::valselcommitint(home,x.size(),vals),
389  array,n,bf);
390  }
391  } else {
392  ViewSel<IntView>* vs[4] = {
393  Branch::viewselint(home,vars.a),Branch::viewselint(home,vars.b),
394  Branch::viewselint(home,vars.c),Branch::viewselint(home,vars.d)
395  };
396  switch (vals.select()) {
403  throw LDSBBadValueSelection("Int::LDSB::branch");
404  break;
406  if (vals.commit() != NULL)
407  throw LDSBBadValueSelection("Int::LDSB::branch");
408  // If vals.commit() returns NULL, it means it will commit with
409  // binary branching, which is OK for LDSB, so we fall through.
410  default:
412  ::post(home,xv,vs,Branch::valselcommitint(home,x.size(),vals),
413  array,n,bf);
414  }
415  }
416  }
417  GECODE_NEVER;
418  return BrancherHandle();
419  }
420 
421  BrancherHandle
422  branch(Home home, const BoolVarArgs& x,
423  IntVarBranch vars, IntValBranch vals,
424  const Symmetries& syms, BoolBranchFilter bf) {
425  using namespace Int;
426  if (home.failed()) return BrancherHandle();
427  ViewArray<BoolView> xv(home,x);
428  ViewSel<BoolView>* vs[1] = {
429  Branch::viewselbool(home,vars)
430  };
431 
432  // Construct mapping from each variable in the array to its index
433  // in the array.
434  VariableMap variableMap;
435  for (int i = 0 ; i < x.size() ; i++)
436  variableMap[x[i].varimp()] = i;
437 
438  // Convert the modelling-level Symmetries object into an array of
439  // SymmetryImp objects.
440  int n = syms.size();
441  SymmetryImp<BoolView>** array =
442  static_cast<Space&>(home).alloc<SymmetryImp<BoolView>* >(n);
443  for (int i = 0 ; i < n ; i++) {
444  array[i] = createBoolSym(home, syms[i], variableMap);
445  }
446 
447  // Technically these "bad" value selection could in fact work with
448  // LDSB, because they degenerate to binary splitting for
449  // Booleans. Nonetheless, we explicitly forbid them for
450  // consistency with the integer version.
451  switch (vals.select()) {
458  throw LDSBBadValueSelection("Int::LDSB::branch");
459  break;
461  if (vals.commit() != NULL)
462  throw LDSBBadValueSelection("Int::LDSB::branch");
463  // If vals.commit() returns NULL, it means it will commit with
464  // binary branching, which is OK for LDSB, so we fall through.
465  default:
467  (home,xv,vs,Branch::valselcommitbool(home,x.size(),vals),array,n,bf);
468  }
469  GECODE_NEVER;
470  return BrancherHandle();
471  }
472 
473 
474  BrancherHandle
475  branch(Home home, const BoolVarArgs& x,
477  const Symmetries& syms, BoolBranchFilter bf) {
478  using namespace Int;
479  if (home.failed()) return BrancherHandle();
480  vars.a.expand(home,x);
481  if ((vars.a.select() == IntVarBranch::SEL_NONE) ||
482  (vars.a.select() == IntVarBranch::SEL_RND))
483  vars.b = INT_VAR_NONE();
484  vars.b.expand(home,x);
485  if ((vars.b.select() == IntVarBranch::SEL_NONE) ||
486  (vars.b.select() == IntVarBranch::SEL_RND))
487  vars.c = INT_VAR_NONE();
488  vars.c.expand(home,x);
489  if ((vars.c.select() == IntVarBranch::SEL_NONE) ||
490  (vars.c.select() == IntVarBranch::SEL_RND))
491  vars.d = INT_VAR_NONE();
492  vars.d.expand(home,x);
493  if (vars.b.select() == IntVarBranch::SEL_NONE) {
494  return branch(home,x,vars.a,vals,syms,bf);
495  } else {
496  // Construct mapping from each variable in the array to its index
497  // in the array.
498  VariableMap variableMap;
499  for (int i = 0 ; i < x.size() ; i++)
500  variableMap[x[i].varimp()] = i;
501 
502  // Convert the modelling-level Symmetries object into an array of
503  // SymmetryImp objects.
504  int n = syms.size();
505  SymmetryImp<BoolView>** array =
506  static_cast<Space&>(home).alloc<SymmetryImp<BoolView>* >(n);
507  for (int i = 0 ; i < n ; i++) {
508  array[i] = createBoolSym(home, syms[i], variableMap);
509  }
510 
511  // Technically these "bad" value selection could in fact work with
512  // LDSB, because they degenerate to binary splitting for
513  // Booleans. Nonetheless, we explicitly forbid them for
514  // consistency with the integer version.
515  switch (vals.select()) {
522  throw LDSBBadValueSelection("Int::LDSB::branch");
523  break;
525  if (vals.commit() != NULL)
526  throw LDSBBadValueSelection("Int::LDSB::branch");
527  // If vals.commit() returns NULL, it means it will commit with
528  // binary branching, which is OK for LDSB, so we fall through.
529  default:
530  ;
531  // Do nothing and continue.
532  }
533 
534  ViewArray<BoolView> xv(home,x);
536  vsc = Branch::valselcommitbool(home,x.size(),vals);
537  if (vars.c.select() == IntVarBranch::SEL_NONE) {
538  ViewSel<BoolView>* vs[2] = {
539  Branch::viewselbool(home,vars.a),Branch::viewselbool(home,vars.b)
540  };
541  return
542  LDSBBrancher<BoolView,2,int,2>::post(home,xv,vs,vsc,array,n,bf);
543  } else if (vars.d.select() == IntVarBranch::SEL_NONE) {
544  ViewSel<BoolView>* vs[3] = {
545  Branch::viewselbool(home,vars.a),Branch::viewselbool(home,vars.b),
546  Branch::viewselbool(home,vars.c)
547  };
548  return
549  LDSBBrancher<BoolView,3,int,2>::post(home,xv,vs,vsc,array,n,bf);
550  } else {
551  ViewSel<BoolView>* vs[4] = {
552  Branch::viewselbool(home,vars.a),Branch::viewselbool(home,vars.b),
553  Branch::viewselbool(home,vars.c),Branch::viewselbool(home,vars.d)
554  };
555  return
556  LDSBBrancher<BoolView,4,int,2>::post(home,xv,vs,vsc,array,n,bf);
557  }
558  }
559  GECODE_NEVER;
560  return BrancherHandle();
561  }
562 
563 }
564 
565 
566 
567 // STATISTICS: int-branch