00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038 #include <gecode/int/ldsb.hh>
00039 #include <gecode/int/branch.hh>
00040
00041 #include <map>
00042
00043 namespace Gecode { namespace Int { namespace LDSB {
00044
00045 std::pair<int,int>
00046 findVar(int *indices, unsigned int n_values, unsigned int seq_size, int index) {
00047 unsigned int seq = 0;
00048 unsigned int pos = 0;
00049 for (unsigned int i = 0 ; i < n_values ; i++) {
00050 if (indices[i] == index)
00051 return std::pair<int,int>(seq,pos);
00052 pos++;
00053 if (pos == seq_size) {
00054 pos = 0;
00055 seq++;
00056 }
00057 }
00058 return std::pair<int,int>(-1,-1);
00059 }
00060
00061 }}}
00062
00063 namespace Gecode {
00064 using namespace Int::LDSB;
00065
00066 SymmetryHandle VariableSymmetry(const IntVarArgs& vars) {
00067 ArgArray<VarImpBase*> a(vars.size());
00068 for (int i = 0 ; i < vars.size() ; i++)
00069 a[i] = vars[i].varimp();
00070 return SymmetryHandle(new VariableSymmetryObject(a));
00071 }
00072 SymmetryHandle VariableSymmetry(const BoolVarArgs& vars) {
00073 ArgArray<VarImpBase*> a(vars.size());
00074 for (int i = 0 ; i < vars.size() ; i++)
00075 a[i] = vars[i].varimp();
00076 return SymmetryHandle(new VariableSymmetryObject(a));
00077 }
00078 SymmetryHandle VariableSymmetry(const IntVarArgs& x,
00079 const IntArgs& indices) {
00080 IntVarArgs xs(indices.size());
00081 for (int i = 0 ; i < indices.size() ; i++)
00082 xs[i] = x[indices[i]];
00083 return VariableSymmetry(xs);
00084 }
00085 SymmetryHandle ValueSymmetry(const IntArgs& vs) {
00086 return SymmetryHandle(new ValueSymmetryObject(IntSet(vs)));
00087 }
00088 SymmetryHandle ValueSymmetry(const IntSet& vs) {
00089 return SymmetryHandle(new ValueSymmetryObject(vs));
00090 }
00091 SymmetryHandle ValueSymmetry(IntVar x) {
00092 return ValueSymmetry(IntSet(x.min(), x.max()));
00093 }
00094 SymmetryHandle VariableSequenceSymmetry(const IntVarArgs& vars, int ss) {
00095 ArgArray<VarImpBase*> a(vars.size());
00096 for (int i = 0 ; i < vars.size() ; i++)
00097 a[i] = vars[i].varimp();
00098 return SymmetryHandle(new VariableSequenceSymmetryObject(a, ss));
00099 }
00100 SymmetryHandle VariableSequenceSymmetry(const BoolVarArgs& vars, int ss) {
00101 ArgArray<VarImpBase*> a(vars.size());
00102 for (int i = 0 ; i < vars.size() ; i++)
00103 a[i] = vars[i].varimp();
00104 return SymmetryHandle(new VariableSequenceSymmetryObject(a, ss));
00105 }
00106 SymmetryHandle ValueSequenceSymmetry(const IntArgs& vs, int ss) {
00107 return SymmetryHandle(new ValueSequenceSymmetryObject(vs, ss));
00108 }
00109
00110 SymmetryHandle values_reflect(int lower, int upper) {
00111 int n = (upper-lower+1)/2;
00112 IntArgs a(n*2);
00113 int i = lower;
00114 int j = upper;
00115 int k = 0;
00116 while (i < j) {
00117 a[k] = j;
00118 a[n+k] = i;
00119 i++;
00120 j--;
00121 k++;
00122 }
00123 return ValueSequenceSymmetry(a,n);
00124 }
00125 SymmetryHandle values_reflect(const IntVar& x) {
00126 return values_reflect(x.min(), x.max());
00127 }
00128 }
00129
00130
00131 namespace Gecode { namespace Int { namespace LDSB {
00132
00134 class VariableMap : public std::map<VarImpBase*,int> {};
00135
00136
00137
00138
00139
00140
00141
00143 SymmetryImp<IntView>*
00144 createIntSym(Space& home, const SymmetryHandle& s,
00145 VariableMap variableMap) {
00146 VariableSymmetryObject* varref =
00147 dynamic_cast<VariableSymmetryObject*>(s.ref);
00148 ValueSymmetryObject* valref =
00149 dynamic_cast<ValueSymmetryObject*>(s.ref);
00150 VariableSequenceSymmetryObject* varseqref =
00151 dynamic_cast<VariableSequenceSymmetryObject*>(s.ref);
00152 ValueSequenceSymmetryObject* valseqref =
00153 dynamic_cast<ValueSequenceSymmetryObject*>(s.ref);
00154 if (varref) {
00155 int n = varref->nxs;
00156 int* indices = home.alloc<int>(n);
00157 for (int i = 0 ; i < n ; i++) {
00158 VariableMap::const_iterator index = variableMap.find(varref->xs[i]);
00159 if (index == variableMap.end())
00160 throw LDSBUnbranchedVariable("VariableSymmetryObject::createInt");
00161 indices[i] = index->second;
00162 }
00163 return new (home) VariableSymmetryImp<IntView>(home, indices, n);
00164 }
00165 if (valref) {
00166 int n = valref->values.size();
00167 int *vs = home.alloc<int>(n);
00168 int i = 0;
00169 for (IntSetValues v(valref->values) ; v() ; ++v) {
00170 vs[i] = v.val();
00171 i++;
00172 }
00173 return new (home) ValueSymmetryImp<IntView>(home, vs, n);
00174 }
00175 if (varseqref) {
00176 int n = varseqref->nxs;
00177 int* indices = home.alloc<int>(n);
00178 for (int i = 0 ; i < n ; i++) {
00179 VariableMap::const_iterator index =
00180 variableMap.find(varseqref->xs[i]);
00181 if (index == variableMap.end())
00182 throw LDSBUnbranchedVariable("VariableSequenceSymmetryObject::createInt");
00183 indices[i] = index->second;
00184 }
00185 return new (home) VariableSequenceSymmetryImp<IntView>(home, indices, n,
00186 varseqref->seq_size);
00187 }
00188 if (valseqref) {
00189 unsigned int n = valseqref->values.size();
00190 int *vs = home.alloc<int>(n);
00191 for (unsigned int i = 0 ; i < n ; i++)
00192 vs[i] = valseqref->values[i];
00193 return new (home) ValueSequenceSymmetryImp<IntView>(home, vs, n,
00194 valseqref->seq_size);
00195 }
00196 GECODE_NEVER;
00197 return NULL;
00198 }
00199
00201 SymmetryImp<BoolView>* createBoolSym(Space& home, const SymmetryHandle& s,
00202 VariableMap variableMap) {
00203 VariableSymmetryObject* varref =
00204 dynamic_cast<VariableSymmetryObject*>(s.ref);
00205 ValueSymmetryObject* valref =
00206 dynamic_cast<ValueSymmetryObject*>(s.ref);
00207 VariableSequenceSymmetryObject* varseqref =
00208 dynamic_cast<VariableSequenceSymmetryObject*>(s.ref);
00209 ValueSequenceSymmetryObject* valseqref =
00210 dynamic_cast<ValueSequenceSymmetryObject*>(s.ref);
00211 if (varref) {
00212 int n = varref->nxs;
00213 int* indices = home.alloc<int>(n);
00214 for (int i = 0 ; i < n ; i++) {
00215 VariableMap::const_iterator index = variableMap.find(varref->xs[i]);
00216 if (index == variableMap.end())
00217 throw LDSBUnbranchedVariable("VariableSymmetryObject::createBool");
00218 indices[i] = index->second;
00219 }
00220 return new (home) VariableSymmetryImp<BoolView>(home, indices, n);
00221 }
00222 if (valref) {
00223 int n = valref->values.size();
00224 int *vs = home.alloc<int>(n);
00225 int i = 0;
00226 for (IntSetValues v(valref->values) ; v() ; ++v) {
00227 vs[i] = v.val();
00228 i++;
00229 }
00230 return new (home) ValueSymmetryImp<BoolView>(home, vs, n);
00231 }
00232 if (varseqref) {
00233 int n = varseqref->nxs;
00234 int* indices = home.alloc<int>(n);
00235 for (int i = 0 ; i < n ; i++) {
00236 VariableMap::const_iterator index =
00237 variableMap.find(varseqref->xs[i]);
00238 if (index == variableMap.end())
00239 throw LDSBUnbranchedVariable("VariableSequenceSymmetryObject::createBool");
00240 indices[i] = index->second;
00241 }
00242 return new (home) VariableSequenceSymmetryImp<BoolView>(home, indices,
00243 n, varseqref->seq_size);
00244 }
00245 if (valseqref) {
00246 unsigned int n = valseqref->values.size();
00247 int *vs = home.alloc<int>(n);
00248 for (unsigned int i = 0 ; i < n ; i++)
00249 vs[i] = valseqref->values[i];
00250 return new (home) ValueSequenceSymmetryImp<BoolView>(home, vs, n,
00251 valseqref->seq_size);
00252 }
00253 GECODE_NEVER;
00254 return NULL;
00255 }
00256 }}}
00257
00258 namespace Gecode {
00259
00260 using namespace Int::LDSB;
00261
00262 void
00263 branch(Home home, const IntVarArgs& x,
00264 IntVarBranch vars, IntValBranch vals,
00265 const Symmetries& syms,
00266 IntBranchFilter bf,
00267 IntVarValPrint vvp) {
00268 using namespace Int;
00269 if (home.failed()) return;
00270 vars.expand(home,x);
00271 ViewArray<IntView> xv(home,x);
00272 ViewSel<IntView>* vs[1] = {
00273 Branch::viewsel(home,vars)
00274 };
00275 switch (vals.select()) {
00276 case IntValBranch::SEL_SPLIT_MIN:
00277 case IntValBranch::SEL_SPLIT_MAX:
00278 case IntValBranch::SEL_RANGE_MIN:
00279 case IntValBranch::SEL_RANGE_MAX:
00280 case IntValBranch::SEL_VALUES_MIN:
00281 case IntValBranch::SEL_VALUES_MAX:
00282 throw LDSBBadValueSelection("Int::LDSB::branch");
00283 break;
00284 case IntValBranch::SEL_VAL_COMMIT:
00285 if (vals.commit())
00286 throw LDSBBadValueSelection("Int::LDSB::branch");
00287
00288
00289 default:
00290
00291
00292 VariableMap variableMap;
00293 for (int i = 0 ; i < x.size() ; i++)
00294 variableMap[x[i].varimp()] = i;
00295
00296
00297
00298 int n = syms.size();
00299 SymmetryImp<IntView>** array =
00300 static_cast<Space&>(home).alloc<SymmetryImp<IntView>* >(n);
00301 for (int i = 0 ; i < n ; i++) {
00302 array[i] = createIntSym(home, syms[i], variableMap);
00303 }
00304
00305 postldsbbrancher<IntView,1,int,2>
00306 (home,xv,vs,Branch::valselcommit(home,vals),
00307 array,n,bf,vvp);
00308 }
00309 }
00310
00311 void
00312 branch(Home home, const IntVarArgs& x,
00313 TieBreak<IntVarBranch> vars, IntValBranch vals,
00314 const Symmetries& syms,
00315 IntBranchFilter bf,
00316 IntVarValPrint vvp) {
00317 using namespace Int;
00318 if (home.failed()) return;
00319 vars.a.expand(home,x);
00320 if ((vars.a.select() == IntVarBranch::SEL_NONE) ||
00321 (vars.a.select() == IntVarBranch::SEL_RND))
00322 vars.b = INT_VAR_NONE();
00323 vars.b.expand(home,x);
00324 if ((vars.b.select() == IntVarBranch::SEL_NONE) ||
00325 (vars.b.select() == IntVarBranch::SEL_RND))
00326 vars.c = INT_VAR_NONE();
00327 vars.c.expand(home,x);
00328 if ((vars.c.select() == IntVarBranch::SEL_NONE) ||
00329 (vars.c.select() == IntVarBranch::SEL_RND))
00330 vars.d = INT_VAR_NONE();
00331 vars.d.expand(home,x);
00332 if (vars.b.select() == IntVarBranch::SEL_NONE) {
00333 branch(home,x,vars.a,vals,syms,bf,vvp);
00334 } else {
00335
00336
00337 VariableMap variableMap;
00338 for (int i = 0 ; i < x.size() ; i++)
00339 variableMap[x[i].varimp()] = i;
00340
00341
00342
00343 int n = syms.size();
00344 SymmetryImp<IntView>** array =
00345 static_cast<Space&>(home).alloc<SymmetryImp<IntView>* >(n);
00346 for (int i = 0 ; i < n ; i++) {
00347 array[i] = createIntSym(home, syms[i], variableMap);
00348 }
00349
00350 ViewArray<IntView> xv(home,x);
00351 if (vars.c.select() == IntVarBranch::SEL_NONE) {
00352 ViewSel<IntView>* vs[2] = {
00353 Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b)
00354 };
00355 switch (vals.select()) {
00356 case IntValBranch::SEL_SPLIT_MIN:
00357 case IntValBranch::SEL_SPLIT_MAX:
00358 case IntValBranch::SEL_RANGE_MIN:
00359 case IntValBranch::SEL_RANGE_MAX:
00360 case IntValBranch::SEL_VALUES_MIN:
00361 case IntValBranch::SEL_VALUES_MAX:
00362 throw LDSBBadValueSelection("Int::LDSB::branch");
00363 break;
00364 case IntValBranch::SEL_VAL_COMMIT:
00365 if (vals.commit())
00366 throw LDSBBadValueSelection("Int::LDSB::branch");
00367
00368
00369 default:
00370 postldsbbrancher<IntView,2,int,2>
00371 (home,xv,vs,Branch::valselcommit(home,vals),
00372 array,n,bf,vvp);
00373 }
00374 } else if (vars.d.select() == IntVarBranch::SEL_NONE) {
00375 ViewSel<IntView>* vs[3] = {
00376 Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b),
00377 Branch::viewsel(home,vars.c)
00378 };
00379 switch (vals.select()) {
00380 case IntValBranch::SEL_SPLIT_MIN:
00381 case IntValBranch::SEL_SPLIT_MAX:
00382 case IntValBranch::SEL_RANGE_MIN:
00383 case IntValBranch::SEL_RANGE_MAX:
00384 case IntValBranch::SEL_VALUES_MIN:
00385 case IntValBranch::SEL_VALUES_MAX:
00386 throw LDSBBadValueSelection("Int::LDSB::branch");
00387 break;
00388 case IntValBranch::SEL_VAL_COMMIT:
00389 if (vals.commit())
00390 throw LDSBBadValueSelection("Int::LDSB::branch");
00391
00392
00393 default:
00394 postldsbbrancher<IntView,3,int,2>
00395 (home,xv,vs,Branch::valselcommit(home,vals),
00396 array,n,bf,vvp);
00397 }
00398 } else {
00399 ViewSel<IntView>* vs[4] = {
00400 Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b),
00401 Branch::viewsel(home,vars.c),Branch::viewsel(home,vars.d)
00402 };
00403 switch (vals.select()) {
00404 case IntValBranch::SEL_SPLIT_MIN:
00405 case IntValBranch::SEL_SPLIT_MAX:
00406 case IntValBranch::SEL_RANGE_MIN:
00407 case IntValBranch::SEL_RANGE_MAX:
00408 case IntValBranch::SEL_VALUES_MIN:
00409 case IntValBranch::SEL_VALUES_MAX:
00410 throw LDSBBadValueSelection("Int::LDSB::branch");
00411 break;
00412 case IntValBranch::SEL_VAL_COMMIT:
00413 if (vals.commit())
00414 throw LDSBBadValueSelection("Int::LDSB::branch");
00415
00416
00417 default:
00418 postldsbbrancher<IntView,4,int,2>
00419 (home,xv,vs,Branch::valselcommit(home,vals),
00420 array,n,bf,vvp);
00421 }
00422 }
00423 }
00424 }
00425
00426 void
00427 branch(Home home, const BoolVarArgs& x,
00428 BoolVarBranch vars, BoolValBranch vals,
00429 const Symmetries& syms,
00430 BoolBranchFilter bf,
00431 BoolVarValPrint vvp) {
00432 using namespace Int;
00433 if (home.failed()) return;
00434 vars.expand(home,x);
00435 ViewArray<BoolView> xv(home,x);
00436 ViewSel<BoolView>* vs[1] = {
00437 Branch::viewsel(home,vars)
00438 };
00439
00440
00441
00442 VariableMap variableMap;
00443 for (int i = 0 ; i < x.size() ; i++)
00444 variableMap[x[i].varimp()] = i;
00445
00446
00447
00448 int n = syms.size();
00449 SymmetryImp<BoolView>** array =
00450 static_cast<Space&>(home).alloc<SymmetryImp<BoolView>* >(n);
00451 for (int i = 0 ; i < n ; i++) {
00452 array[i] = createBoolSym(home, syms[i], variableMap);
00453 }
00454
00455
00456
00457
00458
00459 switch (vals.select()) {
00460 case BoolValBranch::SEL_VAL_COMMIT:
00461 if (vals.commit())
00462 throw LDSBBadValueSelection("Int::LDSB::branch");
00463
00464
00465 default:
00466 postldsbbrancher<BoolView,1,int,2>
00467 (home,xv,vs,Branch::valselcommit(home,vals),array,n,bf,vvp);
00468 }
00469 }
00470
00471
00472 void
00473 branch(Home home, const BoolVarArgs& x,
00474 TieBreak<BoolVarBranch> vars, BoolValBranch vals,
00475 const Symmetries& syms,
00476 BoolBranchFilter bf,
00477 BoolVarValPrint vvp) {
00478 using namespace Int;
00479 if (home.failed()) return;
00480 vars.a.expand(home,x);
00481 if ((vars.a.select() == BoolVarBranch::SEL_NONE) ||
00482 (vars.a.select() == BoolVarBranch::SEL_RND))
00483 vars.b = BOOL_VAR_NONE();
00484 vars.b.expand(home,x);
00485 if ((vars.b.select() == BoolVarBranch::SEL_NONE) ||
00486 (vars.b.select() == BoolVarBranch::SEL_RND))
00487 vars.c = BOOL_VAR_NONE();
00488 vars.c.expand(home,x);
00489 if ((vars.c.select() == BoolVarBranch::SEL_NONE) ||
00490 (vars.c.select() == BoolVarBranch::SEL_RND))
00491 vars.d = BOOL_VAR_NONE();
00492 vars.d.expand(home,x);
00493 if (vars.b.select() == BoolVarBranch::SEL_NONE) {
00494 branch(home,x,vars.a,vals,syms,bf,vvp);
00495 } else {
00496
00497
00498 VariableMap variableMap;
00499 for (int i = 0 ; i < x.size() ; i++)
00500 variableMap[x[i].varimp()] = i;
00501
00502
00503
00504 int n = syms.size();
00505 SymmetryImp<BoolView>** array =
00506 static_cast<Space&>(home).alloc<SymmetryImp<BoolView>* >(n);
00507 for (int i = 0 ; i < n ; i++) {
00508 array[i] = createBoolSym(home, syms[i], variableMap);
00509 }
00510
00511
00512
00513
00514
00515 switch (vals.select()) {
00516 case BoolValBranch::SEL_VAL_COMMIT:
00517 if (vals.commit())
00518 throw LDSBBadValueSelection("Int::LDSB::branch");
00519
00520
00521 default:
00522 ;
00523
00524 }
00525
00526 ViewArray<BoolView> xv(home,x);
00527 ValSelCommitBase<BoolView,int>*
00528 vsc = Branch::valselcommit(home,vals);
00529 if (vars.c.select() == BoolVarBranch::SEL_NONE) {
00530 ViewSel<BoolView>* vs[2] = {
00531 Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b)
00532 };
00533 postldsbbrancher<BoolView,2,int,2>(home,xv,vs,vsc,array,n,bf,vvp);
00534 } else if (vars.d.select() == BoolVarBranch::SEL_NONE) {
00535 ViewSel<BoolView>* vs[3] = {
00536 Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b),
00537 Branch::viewsel(home,vars.c)
00538 };
00539 postldsbbrancher<BoolView,3,int,2>(home,xv,vs,vsc,array,n,bf,vvp);
00540 } else {
00541 ViewSel<BoolView>* vs[4] = {
00542 Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b),
00543 Branch::viewsel(home,vars.c),Branch::viewsel(home,vars.d)
00544 };
00545 postldsbbrancher<BoolView,4,int,2>(home,xv,vs,vsc,array,n,bf,vvp);
00546 }
00547 }
00548 }
00549
00550 }
00551
00552
00553
00554