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