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 = 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 Region r;
00198 ProcessStack xa(r,n);
00199 ProcessStack ya(r,n);
00200
00201 DomInfo<View,Offset>* x = xy;
00202 DomInfo<View,Offset>* y = xy+n;
00203
00204 if (View::me(med) == ME_INT_VAL) {
00205
00206 for (int i = n; i--; ) {
00207 if (x[i].doval()) xa.push(i);
00208 if (y[i].doval()) ya.push(i);
00209 }
00210
00211 if (shared) {
00212 do {
00213
00214 GECODE_ES_CHECK((prop_val<View,Offset,DomInfo<View,Offset> >
00215 (home,n,x,ox,y,oy,n_na,xa,ya)));
00216
00217 GECODE_ES_CHECK((prop_val<View,Offset,DomInfo<View,Offset> >
00218 (home,n,y,oy,x,ox,n_na,ya,xa)));
00219 assert(ya.empty());
00220 } while (!xa.empty() || !ya.empty());
00221 return home.ES_NOFIX_PARTIAL(*this,View::med(ME_INT_DOM));
00222 } else {
00223 do {
00224
00225 GECODE_ES_CHECK((prop_val<View,Offset,DomInfo<View,Offset> >
00226 (home,n,x,ox,y,oy,n_na,xa,ya)));
00227
00228 GECODE_ES_CHECK((prop_val<View,Offset,DomInfo<View,Offset> >
00229 (home,n,y,oy,x,ox,n_na,ya,xa)));
00230 assert(ya.empty());
00231 } while (!xa.empty());
00232 return home.ES_FIX_PARTIAL(*this,View::med(ME_INT_DOM));
00233 }
00234 }
00235
00236
00237
00238
00239 GECODE_ES_CHECK(prop_dom(home,n,y,oy,x,ox,xa));
00240
00241
00242 GECODE_ES_CHECK((prop_val<View,Offset,DomInfo<View,Offset> >
00243 (home,n,x,ox,y,oy,n_na,xa,ya)));
00244
00245
00246 if (dc.available()) {
00247 GECODE_ES_CHECK(dc.sync());
00248 } else {
00249 ViewArray<View> xv(r,n);
00250 for (int i=n; i--; )
00251 xv[i] = x[i].view;
00252 GECODE_ES_CHECK(dc.init(home,xv));
00253 }
00254 bool assigned;
00255 GECODE_ES_CHECK(dc.propagate(home,assigned));
00256 if (assigned) {
00257
00258
00259
00260
00261 for (int i=n; i--; )
00262 if (x[i].doval()) {
00263 int j = ox(x[i].view).val();
00264
00265 ModEvent me = oy(y[j].view).eq(home,i);
00266 if (me_failed(me))
00267 return ES_FAILED;
00268 if (me_modified(me)) {
00269
00270 assert(me == ME_INT_VAL);
00271
00272 ya.push(j);
00273 }
00274 x[i].assigned(); n_na--;
00275 }
00276 }
00277
00278
00279
00280
00281 GECODE_ES_CHECK(prop_dom(home,n,x,ox,y,oy,ya));
00282
00283
00284 while (!xa.empty() || !ya.empty()) {
00285
00286 GECODE_ES_CHECK((prop_val<View,Offset,DomInfo<View,Offset> >
00287 (home,n,x,ox,y,oy,n_na,xa,ya)));
00288
00289 GECODE_ES_CHECK((prop_val<View,Offset,DomInfo<View,Offset> >
00290 (home,n,y,oy,x,ox,n_na,ya,xa)));
00291 };
00292
00293 if (shared) {
00294 for (int i=2*n; i--; )
00295 if (!xy[i].view.assigned())
00296 return ES_NOFIX;
00297 return home.ES_SUBSUMED(*this);
00298 } else {
00299 return (n_na == 0) ? home.ES_SUBSUMED(*this) : ES_FIX;
00300 }
00301 }
00302
00303 template<class View, class Offset, bool shared>
00304 ExecStatus
00305 Dom<View,Offset,shared>::post(Home home, int n, DomInfo<View,Offset>* xy,
00306 Offset& ox, Offset& oy) {
00307 assert(n > 0);
00308 if (n == 1) {
00309 GECODE_ME_CHECK(ox(xy[0].view).eq(home,0));
00310 GECODE_ME_CHECK(oy(xy[1].view).eq(home,0));
00311 return ES_OK;
00312 }
00313 for (int i=n; i--; ) {
00314 GECODE_ME_CHECK(ox(xy[i ].view).gq(home,0));
00315 GECODE_ME_CHECK(ox(xy[i ].view).le(home,n));
00316 GECODE_ME_CHECK(oy(xy[i+n].view).gq(home,0));
00317 GECODE_ME_CHECK(oy(xy[i+n].view).le(home,n));
00318 }
00319 (void) new (home) Dom<View,Offset,shared>(home,n,xy,ox,oy);
00320 return ES_OK;
00321 }
00322
00323 }}}
00324
00325
00326