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