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