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 namespace Gecode { namespace Int { namespace Channel {
00039
00044 template<class View, class Offset>
00045 class DomInfo {
00046 public:
00048 View view;
00050 unsigned int size;
00052 int min;
00054 int max;
00056 void init(View x, int n);
00058 void update(Space& home, DomInfo<View,Offset>& vcb);
00060 bool doval(void) const;
00062 bool dodom(void) const;
00064 void assigned(void);
00066 void removed(int i);
00068 void done(Offset& o);
00069 };
00070
00071 template<class View, class Offset>
00072 forceinline void
00073 DomInfo<View,Offset>::init(View x, int n) {
00074 view = x;
00075 size = static_cast<unsigned int>(n);
00076 min = 0;
00077 max = n-1;
00078 }
00079
00080 template<class View, class Offset>
00081 forceinline void
00082 DomInfo<View,Offset>::update(Space& home, DomInfo<View,Offset>& di) {
00083 view.update(home,di.view);
00084 size = di.size;
00085 min = di.min;
00086 max = di.max;
00087 }
00088
00089 template<class View, class Offset>
00090 forceinline bool
00091 DomInfo<View,Offset>::doval(void) const {
00092 return (size != 1) && view.assigned();
00093 }
00094
00095 template<class View, class Offset>
00096 forceinline bool
00097 DomInfo<View,Offset>::dodom(void) const {
00098 return size != view.size();
00099 }
00100
00101 template<class View, class Offset>
00102 forceinline void
00103 DomInfo<View,Offset>::assigned(void) {
00104 size = 1;
00105 }
00106
00107 template<class View, class Offset>
00108 forceinline void
00109 DomInfo<View,Offset>::removed(int i) {
00110 size--;
00111 if (i == min)
00112 min++;
00113 else if (i == max)
00114 max--;
00115 }
00116
00117 template<class View, class Offset>
00118 forceinline void
00119 DomInfo<View,Offset>::done(Offset& o) {
00120 size = view.size();
00121 min = o(view).min();
00122 max = o(view).max();
00123 }
00124
00125
00126 template<class View, class Offset>
00127 ExecStatus
00128 prop_dom(Space& home, int n, DomInfo<View,Offset>* x, Offset& ox,
00129 DomInfo<View,Offset>* y, Offset& oy, ProcessStack& ya) {
00130 for (int i=0; i<n; i++)
00131
00132 if (x[i].dodom()) {
00133
00134 ViewRanges<typename Offset::ViewType>
00135 xir(ox(x[i].view));
00136 Iter::Ranges::ComplVal<ViewRanges<typename Offset::ViewType> >
00137 xirc(x[i].min,x[i].max,xir);
00138 Iter::Ranges::ToValues<Iter::Ranges::ComplVal<
00139 ViewRanges<typename Offset::ViewType> > > jv(xirc);
00140 while (jv()) {
00141
00142 int j = jv.val();
00143 ModEvent me = oy(y[j].view).nq(home,i);
00144 if (me_failed(me))
00145 return ES_FAILED;
00146 if (me_modified(me)) {
00147 if (me == ME_INT_VAL) {
00148
00149 ya.push(j);
00150 } else {
00151
00152 y[j].removed(i);
00153 }
00154 }
00155 ++jv;
00156 }
00157
00158 x[i].done(ox);
00159 }
00160 return ES_OK;
00161 }
00162
00163
00164
00165
00166
00167 template<class View, class Offset, bool shared>
00168 forceinline
00169 Dom<View,Offset,shared>::Dom(Home home, int n, DomInfo<View,Offset>* xy,
00170 Offset& ox, Offset& oy)
00171 : Base<DomInfo<View,Offset>,Offset,PC_INT_DOM>(home,n,xy,ox,oy) {}
00172
00173 template<class View, class Offset, bool shared>
00174 forceinline
00175 Dom<View,Offset,shared>::Dom(Space& home, Dom<View,Offset,shared>& p)
00176 : Base<DomInfo<View,Offset>,Offset,PC_INT_DOM>(home,p) {}
00177
00178 template<class View, class Offset, bool shared>
00179 Actor*
00180 Dom<View,Offset,shared>::copy(Space& home) {
00181 return new (home) Dom<View,Offset,shared>(home,*this);
00182 }
00183
00184 template<class View, class Offset, bool shared>
00185 PropCost
00186 Dom<View,Offset,shared>::cost(const Space&,
00187 const ModEventDelta& med) const {
00188 if (View::me(med) == ME_INT_VAL)
00189 return PropCost::quadratic(PropCost::LO, 2*n);
00190 else
00191 return PropCost::quadratic(PropCost::HI, 2*n);
00192 }
00193
00194 template<class View, class Offset, bool shared>
00195 ExecStatus
00196 Dom<View,Offset,shared>::propagate(Space& home, const ModEventDelta& med) {
00197
00198 const int n = this->n;
00199 Region r;
00200 ProcessStack xa(r,n);
00201 ProcessStack ya(r,n);
00202
00203 DomInfo<View,Offset>* x = xy;
00204 DomInfo<View,Offset>* y = xy+n;
00205
00206 if (View::me(med) == ME_INT_VAL) {
00207
00208 for (int i=0; i<n; i++) {
00209 if (x[i].doval()) xa.push(i);
00210 if (y[i].doval()) ya.push(i);
00211 }
00212
00213 if (shared) {
00214 do {
00215
00216 GECODE_ES_CHECK((prop_val<View,Offset,DomInfo<View,Offset> >
00217 (home,n,x,ox,y,oy,n_na,xa,ya)));
00218
00219 GECODE_ES_CHECK((prop_val<View,Offset,DomInfo<View,Offset> >
00220 (home,n,y,oy,x,ox,n_na,ya,xa)));
00221 assert(ya.empty());
00222 } while (!xa.empty() || !ya.empty());
00223 return home.ES_NOFIX_PARTIAL(*this,View::med(ME_INT_DOM));
00224 } else {
00225 do {
00226
00227 GECODE_ES_CHECK((prop_val<View,Offset,DomInfo<View,Offset> >
00228 (home,n,x,ox,y,oy,n_na,xa,ya)));
00229
00230 GECODE_ES_CHECK((prop_val<View,Offset,DomInfo<View,Offset> >
00231 (home,n,y,oy,x,ox,n_na,ya,xa)));
00232 assert(ya.empty());
00233 } while (!xa.empty());
00234 return home.ES_FIX_PARTIAL(*this,View::med(ME_INT_DOM));
00235 }
00236 }
00237
00238
00239
00240
00241 GECODE_ES_CHECK(prop_dom(home,n,y,oy,x,ox,xa));
00242
00243
00244 GECODE_ES_CHECK((prop_val<View,Offset,DomInfo<View,Offset> >
00245 (home,n,x,ox,y,oy,n_na,xa,ya)));
00246
00247
00248 if (dc.available()) {
00249 GECODE_ES_CHECK(dc.sync());
00250 } else {
00251 ViewArray<View> xv(r,n);
00252 for (int i=0; i<n; i++)
00253 xv[i] = x[i].view;
00254 GECODE_ES_CHECK(dc.init(home,xv));
00255 }
00256 bool assigned;
00257 GECODE_ES_CHECK(dc.propagate(home,assigned));
00258 if (assigned) {
00259
00260
00261
00262
00263 for (int i=0; i<n; i++)
00264 if (x[i].doval()) {
00265 int j = ox(x[i].view).val();
00266
00267 ModEvent me = oy(y[j].view).eq(home,i);
00268 if (me_failed(me))
00269 return ES_FAILED;
00270 if (me_modified(me)) {
00271
00272 assert(me == ME_INT_VAL);
00273
00274 ya.push(j);
00275 }
00276 x[i].assigned(); n_na--;
00277 }
00278 }
00279
00280
00281
00282
00283 GECODE_ES_CHECK(prop_dom(home,n,x,ox,y,oy,ya));
00284
00285
00286 while (!xa.empty() || !ya.empty()) {
00287
00288 GECODE_ES_CHECK((prop_val<View,Offset,DomInfo<View,Offset> >
00289 (home,n,x,ox,y,oy,n_na,xa,ya)));
00290
00291 GECODE_ES_CHECK((prop_val<View,Offset,DomInfo<View,Offset> >
00292 (home,n,y,oy,x,ox,n_na,ya,xa)));
00293 };
00294
00295 if (shared) {
00296 for (int i=0; i<2*n; i++)
00297 if (!xy[i].view.assigned())
00298 return ES_NOFIX;
00299 return home.ES_SUBSUMED(*this);
00300 } else {
00301 return (n_na == 0) ? home.ES_SUBSUMED(*this) : ES_FIX;
00302 }
00303 }
00304
00305 template<class View, class Offset, bool shared>
00306 ExecStatus
00307 Dom<View,Offset,shared>::post(Home home, int n, DomInfo<View,Offset>* xy,
00308 Offset& ox, Offset& oy) {
00309 assert(n > 0);
00310 if (n == 1) {
00311 GECODE_ME_CHECK(ox(xy[0].view).eq(home,0));
00312 GECODE_ME_CHECK(oy(xy[1].view).eq(home,0));
00313 return ES_OK;
00314 }
00315 for (int i=0; i<n; i++) {
00316 GECODE_ME_CHECK(ox(xy[i ].view).gq(home,0));
00317 GECODE_ME_CHECK(ox(xy[i ].view).le(home,n));
00318 GECODE_ME_CHECK(oy(xy[i+n].view).gq(home,0));
00319 GECODE_ME_CHECK(oy(xy[i+n].view).le(home,n));
00320 }
00321 (void) new (home) Dom<View,Offset,shared>(home,n,xy,ox,oy);
00322 return ES_OK;
00323 }
00324
00325 }}}
00326
00327
00328