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/cpltset.hh"
00039 #include "gecode/cpltset/propagators.hh"
00040
00041 using namespace Gecode::CpltSet;
00042
00043 namespace Gecode {
00044
00045 namespace CpltSet { namespace RangeRoots {
00046
00052
00053
00054
00055
00056
00058 template <class View0, class View1>
00059 forceinline void
00060 buildRange(Space* home, ViewArray<View0>& seq, View1 selview,
00061 View1 unionview, bdd& d0) {
00062
00063 if (home->failed()) return;
00064 int n = seq.size();
00065
00066 unsigned int xrange = seq[0].tableWidth();
00067 int xmax = seq[0].initialLubMax();
00068 int xmin = seq[0].initialLubMin();
00069
00070 for (int i = n; i--; ) {
00071 if (seq[i].initialLubMax() > xmax) {
00072 xmax = seq[i].initialLubMax();
00073 }
00074 if (seq[i].initialLubMin() < xmin) {
00075 xmin = seq[i].initialLubMin();
00076 }
00077 if (seq[i].tableWidth() > xrange) {
00078 xrange = seq[i].tableWidth();
00079 }
00080 }
00081
00082 GECODE_ME_FAIL(home, unionview.intersect(home, xmin, xmax));
00083
00084 int unionmin = unionview.initialLubMin();
00085
00086
00087 Iter::Ranges::Singleton idx(0, n - 1);
00088
00089 int shift = 0 - selview.initialLubMin();
00090 GECODE_ME_FAIL(home, selview.intersectI(home, idx));
00091
00092
00093
00094 for (int k = 0; k < (int) xrange; k++) {
00095 bdd inter = bdd_false();
00096 for (int j = 0; j < n; j++) {
00097 LubValues<View0> lub(seq[j]);
00098 int seqmin = seq[j].initialLubMin();
00099 int seqmax = seq[j].initialLubMax();
00100 int cur = xmin + k;
00101 if (seqmin <= cur && cur <= seqmax) {
00102 while (lub() && cur != lub.val()) {
00103 ++lub;
00104 }
00105 if (lub() && cur == lub.val()) {
00106 inter |= (selview.element(j + shift) &
00107 seq[j].element(k - (seqmin - xmin)));
00108 ++lub;
00109 }
00110 }
00111 }
00112
00114 d0 &= (unionview.element(k - (unionmin - xmin)) % inter);
00115 }
00116
00117 for (int i = 0; i < n; i++) {
00118 if (seq[i].assigned()) {
00119 d0 &= seq[i].dom();
00120 }
00121 }
00122 if (selview.assigned()) {
00123 d0 &= selview.dom();
00124 }
00125 if (unionview.assigned()) {
00126 d0 &= unionview.dom();
00127 }
00128
00129 }
00130
00131 template <class View0, class View1>
00132 forceinline void
00133 range_post(Space* home, ViewArray<View0>& seq, View1 selview,
00134 View1 unionview) {
00135 if (home->failed()) return;
00136
00137 bdd d0 = bdd_true();
00138 buildRange(home, seq, selview, unionview, d0);
00139 if (home->failed()) return;
00140 GECODE_ES_FAIL(home,
00141 (NaryTwoCpltSetPropagator<View0, View1>::post(home, seq, selview,
00142 unionview, d0)));
00143 }
00144
00145 forceinline void
00146 range_con(Space* home, const CpltSetVarArgs& x, const CpltSetVar& s,
00147 const CpltSetVar& t) {
00148 int n = x.size();
00149 CpltSetView selview(s);
00150 CpltSetView unionview(t);
00151
00152 ViewArray<CpltSetView> sbv(home, n);
00153 for (int i = 0; i < n; i++)
00154 sbv[i] = x[i];
00155
00156 range_post(home, sbv, selview, unionview);
00157 }
00158
00160 template <class View0, class View1>
00161 forceinline void
00162 buildRoots(Space* home, ViewArray<View0>& seq, View1 selview,
00163 View1 unionview, bdd& d0) {
00164 if (home->failed()) return;
00165 int n = seq.size();
00166
00167 unsigned int xrange = seq[0].tableWidth();
00168 int xmax = seq[0].initialLubMax();
00169 int xmin = seq[0].initialLubMin();
00170
00171 for (int i = n; i--; ) {
00172 if (seq[i].tableWidth() > xrange) {
00173 xrange = seq[i].tableWidth();
00174 }
00175 if (seq[i].initialLubMax() > xmax) {
00176 xmax = seq[i].initialLubMax();
00177 }
00178 if (seq[i].initialLubMin() < xmin) {
00179 xmin = seq[i].initialLubMin();
00180 }
00181 }
00182
00183 int unionmin = unionview.initialLubMin();
00184 int unionmax = unionview.initialLubMax();
00185 if (unionview.assigned()) {
00186 xmin = unionview.glbMin();
00187 xmax = unionview.glbMax();
00188 xrange = xmax - xmin + 1;
00189 } else {
00190 if (unionmin < xmin) { xmin = unionmin; }
00191 if (unionmax < xmax) { xmax = unionmax; }
00192 if (unionview.tableWidth() > xrange) {
00193 xrange = unionview.tableWidth();
00194 }
00195 }
00196
00197
00198 Iter::Ranges::Singleton idx(0, n - 1);
00199 GECODE_ME_FAIL(home, selview.intersectI(home, idx));
00200
00201 int shift = 0 - selview.initialLubMin();
00202
00203 for (int j = 0; j < n; j++) {
00204 bdd subset = bdd_true();
00205 LubValues<CpltSetView> lub(seq[j]);
00206 for (unsigned int k = 0; k < xrange; k++) {
00207 int seqmin = seq[j].initialLubMin();
00208 int seqmax = seq[j].initialLubMax();
00209 int cur = xmin + k;
00210 if (seqmin <= cur && cur <= seqmax) {
00211 while (lub() && cur != lub.val()) {
00212 ++lub;
00213 }
00214 if (lub() && cur == lub.val()) {
00215 if (unionmin <= cur && cur <= unionmax) {
00216 subset &= (seq[j].element(k - (seqmin - xmin)) >>=
00217 unionview.element(k - (unionmin - xmin)));
00218 }
00219 ++lub;
00220 }
00221 }
00222 }
00223 if (!manager.ctrue(subset)) {
00224 d0 &= (selview.element(j + shift) % (subset));
00225 }
00226 if (seq[j].assigned()) {
00227 d0 &= seq[j].dom();
00228 }
00229 }
00230
00231 if (unionview.assigned()) {
00232 d0 &= unionview.dom();
00233 }
00234 if (selview.assigned()) {
00235 d0 &= selview.dom();
00236 }
00237 }
00238
00239 template <class View0, class View1>
00240 forceinline void
00241 roots_post(Space* home, ViewArray<View0>& seq, View1 selview,
00242 View1 unionview) {
00243 if (home->failed()) return;
00244
00245 bdd d0 = bdd_true();
00246 buildRoots(home, seq, selview, unionview, d0);
00247 if (home->failed()) return;
00248 GECODE_ES_FAIL(home,
00249 (NaryTwoCpltSetPropagator<View0, View1>::post(home, seq, selview,
00250 unionview, d0)));
00251 }
00252
00253 forceinline void
00254 roots_con(Space* home, const CpltSetVarArgs& x, const CpltSetVar& s,
00255 const CpltSetVar& t, const CpltSetVarArgs& allvars) {
00256 int n = x.size();
00257
00258 CpltSetView selview(s);
00259 CpltSetView unionview(t);
00260
00261 ViewArray<CpltSetView> sbv(home, n);
00262 for (int i = 0; i < n; i++)
00263 sbv[i] = x[i];
00264
00265
00266 ViewArray<CpltSetView> vars(home, allvars.size());
00267 for (int i = allvars.size(); i--; ) {
00268 vars[i] = allvars[i];
00269 }
00270
00271 variableorder(vars, sbv);
00272 roots_post(home, sbv, selview, unionview);
00273 }
00274
00275 template <class View0, class View1>
00276 forceinline void
00277 nvalue_post(Space* home, ViewArray<View0>& seq, View1 selview,
00278 View1 unionview, int usedvalues) {
00279 std::cout << "nvalue_post\n";
00280 if (home->failed()) return;
00282 variableorder(seq);
00283
00284 bdd d0 = bdd_true();
00285 int n = seq.size();
00286 Iter::Ranges::Singleton idx(0, n - 1);
00287
00288 GECODE_ME_FAIL(home, selview.eqI(home, idx));
00289
00290 GECODE_ME_FAIL(home,
00291 unionview.cardinality(home, usedvalues, usedvalues));
00292
00293 buildRange(home, seq, selview, unionview, d0);
00294 if (home->failed()) return;
00295 GECODE_ES_FAIL(home,
00296 (NaryTwoCpltSetPropagator<View0, View1>::post(home, seq, selview,
00297 unionview, d0)));
00298 }
00299
00300
00301 forceinline void
00302 nvalue_con(Space* home, const CpltSetVarArgs& x, const CpltSetVar& s,
00303 const CpltSetVar& t,
00304 int usedvalues, const CpltSetVarArgs& allvars) {
00305 int n = x.size();
00306 CpltSetView selview(s);
00307 CpltSetView unionview(t);
00308
00309 ViewArray<CpltSetView> sbv(home, n);
00310 for (int i = 0; i < n; i++)
00311 sbv[i] = x[i];
00312
00313
00314 ViewArray<CpltSetView> vars(home, allvars.size());
00315 for (int i = allvars.size(); i--; ) {
00316 vars[i] = allvars[i];
00317 }
00318
00319 variableorder(vars, sbv);
00320 nvalue_post(home, sbv, selview, unionview, usedvalues);
00321 }
00322
00323 template <class View0, class View1>
00324 forceinline void
00325 uses_post(Space* home, ViewArray<View0>& seq, View1 selview,
00326 View1 unionview,
00327 ViewArray<View0>& seqprime, View1 selviewprime,
00328 View1 unionviewprime) {
00329 if (home->failed()) return;
00330
00331 bdd d0 = bdd_true();
00332 int n = seq.size();
00333 Iter::Ranges::Singleton idx(0, n - 1);
00334
00335 GECODE_ME_FAIL(home, selview.eqI(home, idx));
00336
00337
00338 buildRange(home, seq, selview, unionview, d0);
00339 if (home->failed()) return;
00340
00341 int m = seqprime.size();
00342 Iter::Ranges::Singleton idx2(0, m - 1);
00343
00344 GECODE_ME_FAIL(home, selviewprime.eqI(home, idx2));
00345
00346
00347
00348 bdd e0 = bdd_true();
00349 buildRange(home, seqprime, selviewprime, unionviewprime, e0);
00350 if (home->failed()) return;
00351
00352
00353 bdd r0 = bdd_true();
00354 int tab = std::max(unionview.tableWidth(),
00355 unionviewprime.tableWidth());
00356 for (int i = 0; i < (int) tab; i++) {
00357 r0 &= (unionviewprime.element(i)) >>= (unionview.element(i));
00358 }
00359
00360 GECODE_ES_FAIL(home,
00361 (NaryTwoCpltSetPropagator<View0, View1>::post(home, seq, selview,
00362 unionview, d0)));
00363 GECODE_ES_FAIL(home,
00364 (NaryTwoCpltSetPropagator<View0, View1>::post(home, seqprime,
00365 selviewprime,
00366 unionviewprime, e0)));
00367 GECODE_ES_FAIL(home,
00368 (BinaryCpltSetPropagator<View1,View1>::post(home, unionview,
00369 unionviewprime, r0)));
00370 }
00371
00372
00373 forceinline void
00374 uses_con(Space* home, const CpltSetVarArgs& x, const CpltSetVar& s,
00375 const CpltSetVar& t,
00376 const CpltSetVarArgs& y, const CpltSetVar& u,
00377 const CpltSetVar& v) {
00378 int n = x.size();
00379 CpltSetView selview(s);
00380 CpltSetView unionview(t);
00381
00382 ViewArray<CpltSetView> sbv(home, n);
00383 for (int i = 0; i < n; i++)
00384 sbv[i] = x[i];
00385
00386 CpltSetView selviewprime(u);
00387 CpltSetView unionviewprime(v);
00388 int m = y.size();
00389 ViewArray<CpltSetView> sbvprime(home, m);
00390 for (int i = 0; i < m; i++)
00391 sbvprime[i] = y[i];
00392
00393 uses_post(home, sbv, selview, unionview,
00394 sbvprime, selviewprime, unionviewprime);
00395 }
00396
00397 template <class View>
00398 forceinline void
00399 selectUnion_post(Space* home, ViewArray<View>& x) {
00400 if (home->failed()) return;
00401
00402 bdd d0 = bdd_true();
00403 int n = x.size() - 2;
00404 ViewArray<View> seq(home, n);
00405 for (int i = 0; i < n; i++) {
00406 seq[i] = x[i];
00407 }
00408 buildRange(home, seq, x[n], x[n + 1], d0);
00409 if (home->failed()) return;
00410 GECODE_ES_FAIL(home, NaryCpltSetPropagator<View>::post(home, x, d0));
00411 }
00412
00413 forceinline void
00414 selectUnion_con(Space* home, const CpltSetVarArgs& x, const CpltSetVar& s,
00415 const CpltSetVar& t) {
00416 int n = x.size();
00417 int m = n + 2;
00418 ViewArray<CpltSetView> bv(home, m);
00419 for (int i = 0; i < n; i++) {
00420 bv[i] = x[i];
00421 }
00422 bv[n] = s;
00423 bv[n + 1] = t;
00424 selectUnion_post(home, bv);
00425 }
00426
00427 }}
00428
00429 using namespace CpltSet::RangeRoots;
00430
00431 void range(Space* home, const CpltSetVarArgs& x, CpltSetVar s,
00432 CpltSetVar t) {
00433 range_con(home, x, s, t);
00434 }
00435
00436 void roots(Space* home, const CpltSetVarArgs& x, CpltSetVar s, CpltSetVar t,
00437 const CpltSetVarArgs& allvars) {
00438 roots_con(home, x, s, t, allvars);
00439 }
00440
00441
00442 void alldifferent(Space* home, const CpltSetVarArgs& x, CpltSetVar s,
00443 CpltSetVar t, const CpltSetVarArgs& allvars) {
00444 nvalue_con(home, x, s, t, x.size(), allvars);
00445 }
00446
00447 void nvalue(Space* home, const CpltSetVarArgs& x, CpltSetVar s,
00448 CpltSetVar t, unsigned int n, const CpltSetVarArgs& allvars) {
00449 Set::Limits::check(n, "CpltSet::nvalue");
00450 nvalue_con(home, x, s, t, n, allvars);
00451 }
00452
00453 void uses(Space* home, const CpltSetVarArgs& x, CpltSetVar s, CpltSetVar t,
00454 const CpltSetVarArgs& y, CpltSetVar u, CpltSetVar v) {
00455 uses_con(home, x, s, t, y, u, v);
00456 }
00457
00458 void selectUnion(Space* home, const CpltSetVarArgs& x, CpltSetVar s,
00459 CpltSetVar t) {
00460 selectUnion_con(home, x, s, t);
00461 }
00462
00463
00464 }
00465
00466