disjoint.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 #include "set/select.hh"
00027 #include "set/rel.hh"
00028 #include "set/rel-op.hh"
00029 #include "set.hh"
00030
00031 #include "iter.hh"
00032
00033 namespace Gecode { namespace Set { namespace Select {
00034
00035 PropCost
00036 SelectDisjoint::cost(void) const {
00037 return PC_QUADRATIC_LO;
00038 }
00039
00040 SelectDisjoint::~SelectDisjoint(void) {
00041 x1.cancel(this, PC_SET_ANY);
00042 iv.cancel(this,PC_SET_ANY);
00043 }
00044
00045 Actor*
00046 SelectDisjoint::copy(Space* home, bool share) {
00047 return new (home) SelectDisjoint(home,share,*this);
00048 }
00049
00050 ExecStatus
00051 SelectDisjoint::propagate(Space* home) {
00052 int n = iv.size();
00053
00054 bool fix_flag;
00055 do {
00056 fix_flag=false;
00057
00058
00059 GlbRanges<SetView> x1lb(x1);
00060 Iter::Ranges::ToValues<GlbRanges<SetView> > vx1lb(x1lb);
00061 GLBndSet unionOfSelected(home);
00062 for(int i=0; vx1lb(); ++vx1lb) {
00063 while (iv[i].idx < vx1lb.val()) i++;
00064 GlbRanges<SetView> clb(iv[i].var);
00065 unionOfSelected.includeI(home,clb);
00066 }
00067
00068 {
00069 LubRanges<SetView> x1ub(x1);
00070 Iter::Ranges::ToValues<LubRanges<SetView> > vx1ub(x1ub);
00071 int i=0;
00072 int j=0;
00073
00074 while (vx1ub()) {
00075 if (iv[i].idx < vx1ub.val()) {
00076 iv[i].var.cancel(this, PC_SET_ANY);
00077 i++;
00078 continue;
00079 }
00080 iv[j] = iv[i];
00081 ++vx1ub;
00082 ++i; ++j;
00083 }
00084
00085
00086
00087 for (int k=i; k<n; k++) {
00088 iv[k].var.cancel(this, PC_SET_ANY);
00089 }
00090 n = j;
00091 iv.size(n);
00092 }
00093
00094 {
00095 UnknownRanges<SetView> x1u(x1);
00096 Iter::Ranges::Cache<UnknownRanges<SetView> > x1uc(x1u);
00097 Iter::Ranges::ToValues<Iter::Ranges::Cache<UnknownRanges<SetView> > >
00098 vx1u(x1uc);
00099 int i=0;
00100 int j=0;
00101 while (vx1u()) {
00102 while (iv[i].idx < vx1u.val()) {
00103 iv[j] = iv[i];
00104 i++; j++;
00105 }
00106 assert(iv[i].idx == vx1u.val());
00107
00108 SetView candidate = iv[i].var;
00109 int candidateInd = iv[i].idx;
00110
00111 GlbRanges<SetView> clb(candidate);
00112 BndSetRanges uos(unionOfSelected);
00113 Iter::Ranges::Inter<GlbRanges<SetView>, BndSetRanges>
00114 inter(clb, uos);
00115 if (inter()) {
00116 ModEvent me = x1.exclude(home,candidateInd);
00117 fix_flag |= me_modified(me);
00118 GECODE_ME_CHECK(me);
00119
00120 candidate.cancel(this, PC_SET_ANY);
00121 ++i;
00122 ++vx1u;
00123 continue;
00124 }
00125 iv[j] = iv[i];
00126 ++vx1u;
00127 ++i; ++j;
00128 }
00129
00130 unionOfSelected.dispose(home);
00131
00132
00133 for (int k=i; k<n; k++) {
00134 iv[j] = iv[k];
00135 j++;
00136 }
00137 n = j;
00138 iv.size(n);
00139 }
00140
00141 if (x1.cardMax()==0) {
00142
00143 return ES_SUBSUMED;
00144 }
00145
00146 {
00147
00148
00149 GlbRanges<SetView> x1lb(x1);
00150 Iter::Ranges::ToValues<GlbRanges<SetView> > vx1lb(x1lb);
00151 int i=0;
00152 for (; vx1lb(); ++vx1lb) {
00153 while (iv[i].idx < vx1lb.val()) i++;
00154 assert(iv[i].idx==vx1lb.val());
00155 GlbRanges<SetView> x1lb2(x1);
00156 Iter::Ranges::ToValues<GlbRanges<SetView> > vx1lb2(x1lb2);
00157 for (int j=0; vx1lb2(); ++vx1lb2) {
00158 while (iv[j].idx < vx1lb2.val()) j++;
00159 assert(iv[j].idx==vx1lb2.val());
00160 if (iv[i].idx!=iv[j].idx) {
00161 GlbRanges<SetView> xilb(iv[i].var);
00162 ModEvent me = iv[j].var.excludeI(home,xilb);
00163 GECODE_ME_CHECK(me);
00164 }
00165 }
00166 }
00167 }
00168
00169
00170
00171
00172 if (x1.cardMin()-x1.glbSize() > 1) {
00173 UnknownRanges<SetView> x1u(x1);
00174 Iter::Ranges::Cache<UnknownRanges<SetView> > x1uc(x1u);
00175 Iter::Ranges::ToValues<Iter::Ranges::Cache<UnknownRanges<SetView> > >
00176 vx1u(x1uc);
00177
00178 for (; vx1u() && x1.cardMin()-x1.glbSize() > 1; ++vx1u) {
00179 int i = 0;
00180 while (iv[i].idx < vx1u.val()) i++;
00181 assert(iv[i].idx == vx1u.val());
00182 bool flag=true;
00183
00184 UnknownRanges<SetView> x1u2(x1);
00185 Iter::Ranges::ToValues<UnknownRanges<SetView> > vx1u2(x1u2);
00186 for (; vx1u2(); ++vx1u2) {
00187 int j = 0;
00188 while (iv[j].idx < vx1u2.val()) j++;
00189 assert(iv[j].idx == vx1u2.val());
00190 if (iv[i].idx!=iv[j].idx) {
00191 GlbRanges<SetView> xjlb(iv[j].var);
00192 GlbRanges<SetView> xilb(iv[i].var);
00193 Iter::Ranges::Inter<GlbRanges<SetView>, GlbRanges<SetView> >
00194 inter(xjlb, xilb);
00195 if (!inter()) {
00196 flag = false;
00197 goto here;
00198 }
00199 }
00200 }
00201 here:
00202 if (flag) {
00203 ModEvent me = x1.exclude(home,iv[i].idx);
00204 GECODE_ME_CHECK(me);
00205 }
00206 }
00207 }
00208
00209
00210
00211
00212 UnknownRanges<SetView> x1u(x1);
00213 Iter::Ranges::Cache<UnknownRanges<SetView> > x1uc(x1u);
00214 Iter::Ranges::ToValues<Iter::Ranges::Cache<UnknownRanges<SetView> > >
00215 vx1u(x1uc);
00216
00217 for (; x1.cardMin()-x1.glbSize() == 2 && vx1u(); ++vx1u) {
00218 int i = 0;
00219 while (iv[i].idx < vx1u.val()) i++;
00220 assert (iv[i].idx == vx1u.val());
00221 bool flag=true;
00222
00223 UnknownRanges<SetView> x1u2(x1);
00224 Iter::Ranges::ToValues<UnknownRanges<SetView> > vx1u2(x1u2);
00225 for (; vx1u2(); ++vx1u2) {
00226 int j = 0;
00227 while (iv[j].idx < vx1u2.val()) j++;
00228 assert (iv[j].idx == vx1u2.val());
00229 if (iv[i].idx!=iv[j].idx) {
00230 UnknownRanges<SetView> x1u3(x1);
00231 Iter::Ranges::ToValues<UnknownRanges<SetView> > vx1u3(x1u3);
00232 for (; vx1u3(); ++vx1u3) {
00233 int k = 0;
00234 while (iv[k].idx < vx1u3.val()) k++;
00235 assert (iv[k].idx == vx1u3.val());
00236 if (iv[j].idx!=iv[k].idx && iv[i].idx!=iv[k].idx) {
00237 GlbRanges<SetView> xjlb(iv[j].var);
00238 GlbRanges<SetView> xilb(iv[k].var);
00239 Iter::Ranges::Inter<GlbRanges<SetView>, GlbRanges<SetView> >
00240 inter(xjlb, xilb);
00241 if (!inter()) {
00242 flag = false;
00243 goto here2;
00244 }
00245 }
00246 }
00247 }
00248 }
00249 here2:
00250 if (flag) {
00251 ModEvent me = x1.include(home,iv[i].idx);
00252 GECODE_ME_CHECK(me);
00253 fix_flag=true;
00254 }
00255 }
00256 } while(fix_flag);
00257
00258 return ES_FIX;
00259 }
00260
00261 }}}
00262
00263