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