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>
00045 class ValInfo {
00046 public:
00048 View view;
00050 bool a;
00052 void init(View x, int n);
00054 void update(Space& home, ValInfo<View>& vi);
00056 bool doval(void) const;
00058 bool dodom(void) const;
00060 void assigned(void);
00062 void removed(int i);
00064 void done(void);
00065 };
00066
00067 template<class View>
00068 forceinline void
00069 ValInfo<View>::init(View x, int) {
00070 view = x; a = false;
00071 }
00072
00073 template<class View>
00074 forceinline void
00075 ValInfo<View>::update(Space& home, ValInfo<View>& vi) {
00076 view.update(home,vi.view); a = vi.a;
00077 }
00078
00079 template<class View>
00080 forceinline bool
00081 ValInfo<View>::doval(void) const {
00082 return !a && view.assigned();
00083 }
00084
00085 template<class View>
00086 forceinline bool
00087 ValInfo<View>::dodom(void) const {
00088 return false;
00089 }
00090
00091 template<class View>
00092 forceinline void
00093 ValInfo<View>::assigned(void) {
00094 a = true;
00095 }
00096
00097 template<class View>
00098 forceinline void
00099 ValInfo<View>::removed(int) {}
00100
00101 template<class View>
00102 forceinline void
00103 ValInfo<View>::done(void) {}
00104
00105
00106
00107 template<class View, class Offset, class Info>
00108 ExecStatus
00109 doprop_val(Space& home, int n, Info* x, Offset& ox,
00110 Info* y, Offset& oy,
00111 int& n_na, ProcessStack& xa, ProcessStack& ya) {
00112 do {
00113 int i = xa.pop();
00114 int j = ox(x[i].view).val();
00115
00116 {
00117 ModEvent me = oy(y[j].view).eq(home,i);
00118 if (me_failed(me)) {
00119 return ES_FAILED;
00120 }
00121
00122 if (me_modified(me))
00123 ya.push(j);
00124 }
00125
00126 for (int k=i; k--; ) {
00127 ModEvent me = ox(x[k].view).nq(home,j);
00128 if (me_failed(me)) {
00129 return ES_FAILED;
00130 }
00131 if (me_modified(me)) {
00132 if (me == ME_INT_VAL) {
00133
00134 xa.push(k);
00135 } else {
00136
00137
00138
00139 x[k].removed(j);
00140 }
00141 }
00142 }
00143
00144 for (int k=i+1; k<n; k++) {
00145 ModEvent me = ox(x[k].view).nq(home,j);
00146 if (me_failed(me)) {
00147 return ES_FAILED;
00148 }
00149 if (me_modified(me)) {
00150 if (me == ME_INT_VAL) {
00151
00152 xa.push(k);
00153 } else {
00154
00155
00156
00157 x[k].removed(j);
00158 }
00159 }
00160 }
00161 x[i].assigned(); n_na--;
00162 } while (!xa.empty());
00163 return ES_OK;
00164 }
00165
00166
00167 template<class View, class Offset, class Info>
00168 forceinline ExecStatus
00169 prop_val(Space& home, int n, Info* x, Offset& ox, Info* y, Offset& oy,
00170 int& n_na, ProcessStack& xa, ProcessStack& ya) {
00171 if (xa.empty())
00172 return ES_OK;
00173 return doprop_val<View,Offset,Info>(home,n,x,ox,y,oy,n_na,xa,ya);
00174 }
00175
00176
00177
00178
00179
00180 template<class View, class Offset, bool shared>
00181 forceinline
00182 Val<View,Offset,shared>::Val(Home home, int n, ValInfo<View>* xy,
00183 Offset& ox, Offset& oy)
00184 : Base<ValInfo<View>,Offset,PC_INT_VAL>(home,n,xy,ox,oy) {}
00185
00186 template<class View, class Offset, bool shared>
00187 forceinline
00188 Val<View,Offset,shared>::Val(Space& home, Val<View,Offset,shared>& p)
00189 : Base<ValInfo<View>,Offset,PC_INT_VAL>(home,p) {}
00190
00191 template<class View, class Offset, bool shared>
00192 Actor*
00193 Val<View,Offset,shared>::copy(Space& home) {
00194 return new (home) Val<View,Offset,shared>(home,*this);
00195 }
00196
00197 template<class View, class Offset, bool shared>
00198 ExecStatus
00199 Val<View,Offset,shared>::propagate(Space& home, const ModEventDelta&) {
00200 Region r;
00201 ProcessStack xa(r,n);
00202 ProcessStack ya(r,n);
00203
00204 ValInfo<View>* x = xy;
00205 ValInfo<View>* y = xy+n;
00206
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 do {
00214
00215 GECODE_ES_CHECK((prop_val<View,Offset,ValInfo<View> >
00216 (home,n,x,ox,y,oy,n_na,xa,ya)));
00217
00218 GECODE_ES_CHECK((prop_val<View,Offset,ValInfo<View> >
00219 (home,n,y,oy,x,ox,n_na,ya,xa)));
00220 assert(ya.empty());
00221 } while (!xa.empty());
00222
00223 if (n_na == 0)
00224 return home.ES_SUBSUMED(*this);
00225 return shared ? ES_NOFIX : ES_FIX;
00226 }
00227
00228 template<class View, class Offset, bool shared>
00229 ExecStatus
00230 Val<View,Offset,shared>::post(Home home, int n, ValInfo<View>* xy,
00231 Offset& ox, Offset& oy) {
00232 assert(n > 0);
00233 if (n == 1) {
00234 GECODE_ME_CHECK(ox(xy[0].view).eq(home,0));
00235 GECODE_ME_CHECK(oy(xy[1].view).eq(home,0));
00236 return ES_OK;
00237 }
00238 for (int i=n; i--; ) {
00239 GECODE_ME_CHECK(ox(xy[i ].view).gq(home,0));
00240 GECODE_ME_CHECK(ox(xy[i ].view).le(home,n));
00241 GECODE_ME_CHECK(oy(xy[i+n].view).gq(home,0));
00242 GECODE_ME_CHECK(oy(xy[i+n].view).le(home,n));
00243 }
00244 (void) new (home) Val<View,Offset,shared>(home,n,xy,ox,oy);
00245 return ES_OK;
00246 }
00247
00248 }}}
00249
00250
00251