select.cc
Go to the documentation of this file.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 Select {
00046
00052 template <class View>
00053 forceinline void
00054 selectNonEmptySub_post(Space* home, ViewArray<View> x) {
00055 if (home->failed()) return;
00056 int n = x.size() - 2;
00057 int s = n;
00058 int t = n + 1;
00059
00060
00061 unsigned int xrange = x[0].tableWidth();
00062
00063
00064 for (int i = n; i--; ) {
00065 if (x[i].tableWidth() > xrange) {
00066 xrange = x[i].tableWidth();
00067 }
00068 }
00069
00070 if (x[t].tableWidth() > xrange) {
00071 int a = x[t].initialLubMin() + xrange;
00072 int b = x[t].initialLubMin() + x[t].tableWidth();
00073 GECODE_ME_FAIL(home, x[t].exclude(home, a, b));
00074 }
00075
00076 bdd d0 = bdd_true();
00077
00078
00079
00080 int shift = 0;
00081 if (x[s].initialLubMin() < 0) {
00082 shift = 0 - x[s].initialLubMin();
00083 }
00084
00085 Iter::Ranges::Singleton idx(0, n - 1);
00086 GECODE_ME_FAIL(home, x[s].intersectI(home, idx));
00087
00088 for (int j = 0; j < n; j++) {
00089 bdd subset = bdd_true();
00090 bdd inter = bdd_false();
00091 for (unsigned int k = 0; k < xrange; k++) {
00092 subset &= (x[j].element(k) >>= x[t].element(k));
00093 inter |= (x[j].element(k) & x[t].element(k));
00094 }
00095 d0 &= (x[s].element(j + shift) % (subset & inter));
00096 }
00097
00098 GECODE_ES_FAIL(home, NaryCpltSetPropagator<View>::post(home, x, d0));
00099 }
00100
00101 forceinline void
00102 selectNonEmptySub_con(Space* home, const CpltSetVarArgs& x,
00103 const CpltSetVar& s, const CpltSetVar& t) {
00104 int n = x.size();
00105 int m = n + 2;
00106 ViewArray<CpltSetView> bv(home, m);
00107 for (int i = 0; i < n; i++) {
00108 bv[i] = x[i];
00109 }
00110 bv[n] = s;
00111 bv[n + 1] = t;
00112 selectNonEmptySub_post(home, bv);
00113 }
00114
00115 }}
00116
00117 using namespace CpltSet::Select;
00118
00119 void selectNonEmptySub(Space* home, const CpltSetVarArgs& x, CpltSetVar s,
00120 CpltSetVar t) {
00121 selectNonEmptySub_con(home, x, s, t);
00122 }
00123
00124 }
00125
00126