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
00039
00040 namespace Gecode { namespace Set { namespace Element {
00041
00042 template<class SView, class RView>
00043 forceinline
00044 ElementDisjoint<SView,RView>::ElementDisjoint(Home home,
00045 IdxViewArray& iv0,
00046 RView y1)
00047 : Propagator(home), iv(iv0), x1(y1) {
00048
00049 x1.subscribe(home,*this, PC_SET_ANY);
00050 iv.subscribe(home,*this, PC_SET_ANY);
00051 }
00052
00053 template<class SView, class RView>
00054 forceinline
00055 ElementDisjoint<SView,RView>::ElementDisjoint(Space& home, bool share,
00056 ElementDisjoint& p)
00057 : Propagator(home,share,p) {
00058 x1.update(home,share,p.x1);
00059 iv.update(home,share,p.iv);
00060 }
00061
00062 template<class SView, class RView>
00063 forceinline ExecStatus
00064 ElementDisjoint<SView,RView>::post(Home home, IdxViewArray& xs,
00065 RView x1) {
00066 int n = xs.size();
00067
00068
00069 Iter::Ranges::Singleton s(0, n-1);
00070 GECODE_ME_CHECK(x1.intersectI(home,s));
00071 (void) new (home)
00072 ElementDisjoint(home,xs,x1);
00073 return ES_OK;
00074 }
00075
00076 template<class SView, class RView>
00077 PropCost
00078 ElementDisjoint<SView,RView>::cost(const Space&, const ModEventDelta&) const {
00079 return PropCost::quadratic(PropCost::LO, iv.size()+2);
00080 }
00081
00082 template<class SView, class RView>
00083 size_t
00084 ElementDisjoint<SView,RView>::dispose(Space& home) {
00085 assert(!home.failed());
00086 x1.cancel(home,*this, PC_SET_ANY);
00087 iv.cancel(home,*this,PC_SET_ANY);
00088 (void) Propagator::dispose(home);
00089 return sizeof(*this);
00090 }
00091
00092 template<class SView, class RView>
00093 Actor*
00094 ElementDisjoint<SView,RView>::copy(Space& home, bool share) {
00095 return new (home) ElementDisjoint(home,share,*this);
00096 }
00097
00098 template<class SView, class RView>
00099 ExecStatus
00100 ElementDisjoint<SView,RView>::propagate(Space& home, const ModEventDelta&) {
00101 int n = iv.size();
00102
00103 bool fix_flag = false;
00104 do {
00105 fix_flag = false;
00106
00107 GlbRanges<RView> x1lb(x1);
00108 Iter::Ranges::ToValues<GlbRanges<RView> > vx1lb(x1lb);
00109 GLBndSet unionOfSelected(home);
00110 for(int i=0; vx1lb(); ++vx1lb) {
00111 while (iv[i].idx < vx1lb.val()) i++;
00112 GlbRanges<SView> clb(iv[i].view);
00113 unionOfSelected.includeI(home,clb);
00114 }
00115
00116 {
00117 LubRanges<RView> x1ub(x1);
00118 Iter::Ranges::ToValues<LubRanges<RView> > vx1ub(x1ub);
00119 int i=0;
00120 int j=0;
00121
00122 while (vx1ub()) {
00123 if (iv[i].idx < vx1ub.val()) {
00124 iv[i].view.cancel(home,*this, PC_SET_ANY);
00125 i++;
00126 continue;
00127 }
00128 iv[j] = iv[i];
00129 ++vx1ub;
00130 ++i; ++j;
00131 }
00132
00133
00134
00135 for (int k=i; k<n; k++) {
00136 iv[k].view.cancel(home,*this, PC_SET_ANY);
00137 }
00138 n = j;
00139 iv.size(n);
00140 }
00141
00142 {
00143 UnknownRanges<RView> x1u(x1);
00144 Iter::Ranges::Cache<UnknownRanges<RView> > x1uc(x1u);
00145 Iter::Ranges::ToValues<Iter::Ranges::Cache<UnknownRanges<RView> > >
00146 vx1u(x1uc);
00147 int i=0;
00148 int j=0;
00149 while (vx1u()) {
00150 while (iv[i].idx < vx1u.val()) {
00151 iv[j] = iv[i];
00152 i++; j++;
00153 }
00154 assert(iv[i].idx == vx1u.val());
00155
00156 SView candidate = iv[i].view;
00157 int candidateInd = iv[i].idx;
00158
00159 GlbRanges<SView> clb(candidate);
00160 BndSetRanges uos(unionOfSelected);
00161 Iter::Ranges::Inter<GlbRanges<SView>, BndSetRanges>
00162 inter(clb, uos);
00163 if (inter()) {
00164 ModEvent me = x1.exclude(home,candidateInd);
00165 fix_flag |= me_modified(me);
00166 GECODE_ME_CHECK(me);
00167
00168 candidate.cancel(home,*this, PC_SET_ANY);
00169 ++i;
00170 ++vx1u;
00171 continue;
00172 }
00173 iv[j] = iv[i];
00174 ++vx1u;
00175 ++i; ++j;
00176 }
00177
00178 unionOfSelected.dispose(home);
00179
00180
00181 for (int k=i; k<n; k++) {
00182 iv[j] = iv[k];
00183 j++;
00184 }
00185 n = j;
00186 iv.size(n);
00187 }
00188
00189 if (x1.cardMax()==0) {
00190
00191 return ES_SUBSUMED(*this,home);
00192 }
00193
00194 {
00195
00196
00197 GlbRanges<RView> x1lb(x1);
00198 Iter::Ranges::ToValues<GlbRanges<RView> > vx1lb(x1lb);
00199 int i=0;
00200 for (; vx1lb(); ++vx1lb) {
00201 while (iv[i].idx < vx1lb.val()) i++;
00202 assert(iv[i].idx==vx1lb.val());
00203 GlbRanges<RView> x1lb2(x1);
00204 Iter::Ranges::ToValues<GlbRanges<RView> > vx1lb2(x1lb2);
00205 for (int j=0; vx1lb2(); ++vx1lb2) {
00206 while (iv[j].idx < vx1lb2.val()) j++;
00207 assert(iv[j].idx==vx1lb2.val());
00208 if (iv[i].idx!=iv[j].idx) {
00209 GlbRanges<SView> xilb(iv[i].view);
00210 ModEvent me = iv[j].view.excludeI(home,xilb);
00211 fix_flag |= me_modified(me);
00212 GECODE_ME_CHECK(me);
00213 }
00214 }
00215 }
00216 }
00217
00218
00219
00220
00221 if (x1.cardMin()-x1.glbSize() > 1) {
00222 UnknownRanges<RView> x1u(x1);
00223 Iter::Ranges::Cache<UnknownRanges<RView> > x1uc(x1u);
00224 Iter::Ranges::ToValues<Iter::Ranges::Cache<UnknownRanges<RView> > >
00225 vx1u(x1uc);
00226
00227 for (; vx1u() && x1.cardMin()-x1.glbSize() > 1; ++vx1u) {
00228 int i = 0;
00229 while (iv[i].idx < vx1u.val()) i++;
00230 assert(iv[i].idx == vx1u.val());
00231 bool flag=true;
00232
00233 UnknownRanges<RView> x1u2(x1);
00234 Iter::Ranges::ToValues<UnknownRanges<RView> > vx1u2(x1u2);
00235 for (; vx1u2(); ++vx1u2) {
00236 int j = 0;
00237 while (iv[j].idx < vx1u2.val()) j++;
00238 assert(iv[j].idx == vx1u2.val());
00239 if (iv[i].idx!=iv[j].idx) {
00240 GlbRanges<SView> xjlb(iv[j].view);
00241 GlbRanges<SView> xilb(iv[i].view);
00242 Iter::Ranges::Inter<GlbRanges<SView>, GlbRanges<SView> >
00243 inter(xjlb, xilb);
00244 if (!inter()) {
00245 flag = false;
00246 goto here;
00247 }
00248 }
00249 }
00250 here:
00251 if (flag) {
00252 ModEvent me = x1.exclude(home,iv[i].idx);
00253 fix_flag |= me_modified(me);
00254 GECODE_ME_CHECK(me);
00255 }
00256 }
00257 }
00258
00259
00260
00261
00262 UnknownRanges<RView> x1u(x1);
00263 Iter::Ranges::Cache<UnknownRanges<RView> > x1uc(x1u);
00264 Iter::Ranges::ToValues<Iter::Ranges::Cache<UnknownRanges<RView> > >
00265 vx1u(x1uc);
00266
00267 for (; x1.cardMin()-x1.glbSize() == 2 && vx1u(); ++vx1u) {
00268 int i = 0;
00269 while (iv[i].idx < vx1u.val()) i++;
00270 assert (iv[i].idx == vx1u.val());
00271 bool flag=true;
00272
00273 UnknownRanges<RView> x1u2(x1);
00274 Iter::Ranges::ToValues<UnknownRanges<RView> > vx1u2(x1u2);
00275 for (; vx1u2(); ++vx1u2) {
00276 int j = 0;
00277 while (iv[j].idx < vx1u2.val()) j++;
00278 assert (iv[j].idx == vx1u2.val());
00279 if (iv[i].idx!=iv[j].idx) {
00280 UnknownRanges<RView> x1u3(x1);
00281 Iter::Ranges::ToValues<UnknownRanges<RView> > vx1u3(x1u3);
00282 for (; vx1u3(); ++vx1u3) {
00283 int k = 0;
00284 while (iv[k].idx < vx1u3.val()) k++;
00285 assert (iv[k].idx == vx1u3.val());
00286 if (iv[j].idx!=iv[k].idx && iv[i].idx!=iv[k].idx) {
00287 GlbRanges<SView> xjlb(iv[j].view);
00288 GlbRanges<SView> xilb(iv[k].view);
00289 Iter::Ranges::Inter<GlbRanges<SView>, GlbRanges<SView> >
00290 inter(xjlb, xilb);
00291 if (!inter()) {
00292 flag = false;
00293 goto here2;
00294 }
00295 }
00296 }
00297 }
00298 }
00299 here2:
00300 if (flag) {
00301 ModEvent me = x1.include(home,iv[i].idx);
00302 fix_flag |= me_modified(me);
00303 GECODE_ME_CHECK(me);
00304 }
00305 }
00306 } while (fix_flag);
00307
00308 bool allAssigned = true;
00309 for (int i=iv.size(); i--;)
00310 if (!iv[i].view.assigned()) {
00311 allAssigned = false;
00312 break;
00313 }
00314 if (!x1.assigned())
00315 allAssigned = false;
00316
00317 return allAssigned ? ES_SUBSUMED(*this,home) : ES_FIX;
00318 }
00319
00320
00321 }}}
00322
00323