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 Element {
00039
00040
00041
00042 template<class V0, class V1, class Idx, class Val>
00043 forceinline void
00044 Int<V0,V1,Idx,Val>::IdxVal::mark(void) {
00045 idx = -1;
00046 }
00047 template<class V0, class V1, class Idx, class Val>
00048 forceinline bool
00049 Int<V0,V1,Idx,Val>::IdxVal::marked(void) const {
00050 return idx<0;
00051 }
00052
00053
00054 template<class V0, class V1, class Idx, class Val>
00055 forceinline
00056 Int<V0,V1,Idx,Val>::IterIdx::IterIdx(IdxVal* iv0)
00057 : iv(iv0) {
00058 Idx p=0;
00059 i = iv[p].idx_next;
00060 while ((i != 0) && iv[i].marked())
00061 i=iv[i].idx_next;
00062 iv[p].idx_next=i;
00063 }
00064 template<class V0, class V1, class Idx, class Val>
00065 forceinline bool
00066 Int<V0,V1,Idx,Val>::IterIdx::operator ()(void) const {
00067 return i != 0;
00068 }
00069 template<class V0, class V1, class Idx, class Val>
00070 forceinline void
00071 Int<V0,V1,Idx,Val>::IterIdx::operator ++(void) {
00072 int p=i;
00073 i = iv[p].idx_next;
00074 while ((i != 0) && iv[i].marked())
00075 i=iv[i].idx_next;
00076 iv[p].idx_next=i;
00077 }
00078 template<class V0, class V1, class Idx, class Val>
00079 forceinline Idx
00080 Int<V0,V1,Idx,Val>::IterIdx::val(void) const {
00081 assert(!iv[i].marked());
00082 return iv[i].idx;
00083 }
00084
00085
00086
00087 template<class V0, class V1, class Idx, class Val>
00088 forceinline
00089 Int<V0,V1,Idx,Val>::IterVal::IterVal(IdxVal* iv0)
00090 : iv(iv0), i(iv[0].val_next) {}
00091 template<class V0, class V1, class Idx, class Val>
00092 forceinline bool
00093 Int<V0,V1,Idx,Val>::IterVal::operator ()(void) const {
00094 return i != 0;
00095 }
00096 template<class V0, class V1, class Idx, class Val>
00097 forceinline void
00098 Int<V0,V1,Idx,Val>::IterVal::operator ++(void) {
00099 i=iv[i].val_next;
00100 }
00101 template<class V0, class V1, class Idx, class Val>
00102 forceinline Val
00103 Int<V0,V1,Idx,Val>::IterVal::val(void) const {
00104 assert(!iv[i].marked());
00105 return iv[i].val;
00106 }
00107
00108
00109
00110
00111 template<class V0, class V1, class Idx, class Val>
00112 forceinline
00113 Int<V0,V1,Idx,Val>::ByVal::ByVal(const IdxVal* iv0)
00114 : iv(iv0) {}
00115 template<class V0, class V1, class Idx, class Val>
00116 forceinline bool
00117 Int<V0,V1,Idx,Val>::ByVal::operator ()(Idx& i, Idx& j) {
00118 return iv[i].val < iv[j].val;
00119 }
00120
00121
00122
00123
00124
00125
00126 template<class V0, class V1, class Idx, class Val>
00127 forceinline
00128 Int<V0,V1,Idx,Val>::Int(Home home, IntSharedArray& c0, V0 y0, V1 y1)
00129 : Propagator(home), x0(y0), x1(y1), c(c0), iv(NULL) {
00130 home.notice(*this,AP_DISPOSE);
00131 x0.subscribe(home,*this,PC_INT_DOM);
00132 x1.subscribe(home,*this,PC_INT_DOM);
00133 }
00134
00135 template<class V0, class V1, class Idx, class Val>
00136 forceinline size_t
00137 Int<V0,V1,Idx,Val>::dispose(Space& home) {
00138 home.ignore(*this,AP_DISPOSE);
00139 if (!home.failed()) {
00140 x0.cancel(home,*this,PC_INT_DOM);
00141 x1.cancel(home,*this,PC_INT_DOM);
00142 }
00143 c.~IntSharedArray();
00144 (void) Propagator::dispose(home);
00145 return sizeof(*this);
00146 }
00147
00148 template<class V0, class V1, class Idx, class Val>
00149 ExecStatus
00150 Int<V0,V1,Idx,Val>::post(Home home, IntSharedArray& c, V0 x0, V1 x1) {
00151 if (x0.assigned()) {
00152 GECODE_ME_CHECK(x1.eq(home,c[x0.val()]));
00153 } else {
00154 (void) new (home) Int<V0,V1,Idx,Val>(home,c,x0,x1);
00155 }
00156 return ES_OK;
00157 }
00158
00159 template<class V0, class V1, class Idx, class Val>
00160 forceinline
00161 Int<V0,V1,Idx,Val>::Int(Space& home, bool share, Int& p)
00162 : Propagator(home,share,p), iv(NULL) {
00163 c.update(home,share,p.c);
00164 x0.update(home,share,p.x0);
00165 x1.update(home,share,p.x1);
00166 }
00167
00168 template<class V0, class V1, class Idx, class Val>
00169 Actor*
00170 Int<V0,V1,Idx,Val>::copy(Space& home, bool share) {
00171 return new (home) Int<V0,V1,Idx,Val>(home,share,*this);
00172 }
00173
00174 template<class V0, class V1, class Idx, class Val>
00175 PropCost
00176 Int<V0,V1,Idx,Val>::cost(const Space&, const ModEventDelta&) const {
00177 return PropCost::binary(PropCost::HI);
00178 }
00179
00180 template<class V0, class V1, class Idx, class Val>
00181 ExecStatus
00182 Int<V0,V1,Idx,Val>::propagate(Space& home, const ModEventDelta&) {
00183 bool assigned = x0.assigned() && x1.assigned();
00184 if (iv == NULL) {
00185
00186 iv = home.alloc<IdxVal>(x0.size() + 1);
00187
00188
00189
00190 IdxVal* by_idx = &iv[1];
00191 {
00192 Idx i = 0;
00193 ViewValues<V0> v(x0);
00194 while (v()) {
00195 by_idx[i].idx = static_cast<Idx>(v.val());
00196 by_idx[i].val = static_cast<Val>(c[v.val()]);
00197 ++i; ++v;
00198 }
00199 }
00200 Idx size = static_cast<Idx>(x0.size());
00201
00202 Region r(home);
00203 Idx* by_val = r.alloc<Idx>(size);
00204 for (Idx i = size; i--; )
00205 by_val[i] = i+1;
00206 ByVal less(iv);
00207 Support::quicksort<Idx>(by_val,size,less);
00208
00209 for (Idx i = size-1; i--; ) {
00210 by_idx[i].idx_next = i+2;
00211 iv[by_val[i]].val_next = by_val[i+1];
00212 }
00213 by_idx[size-1].idx_next = 0;
00214 iv[by_val[size-1]].val_next = 0;
00215
00216 iv[0].idx_next = 1;
00217 iv[0].val_next = by_val[0];
00218 } else {
00219
00220 Idx p = 0;
00221 Idx i = iv[p].idx_next;
00222 ViewRanges<V0> v(x0);
00223 while (v() && (i != 0)) {
00224 assert(!iv[i].marked());
00225 if (iv[i].idx < v.min()) {
00226 iv[i].mark(); i=iv[i].idx_next; iv[p].idx_next=i;
00227 } else if (iv[i].idx > v.max()) {
00228 ++v;
00229 } else {
00230 p=i; i=iv[i].idx_next;
00231 }
00232 }
00233 iv[p].idx_next = 0;
00234 while (i != 0) { iv[i].mark(); i=iv[i].idx_next; }
00235 }
00236
00237
00238 {
00239 Idx p = 0;
00240 Idx i = iv[p].val_next;
00241 ViewRanges<V1> v(x1);
00242 while (v() && (i != 0)) {
00243 if (iv[i].marked()) {
00244 i=iv[i].val_next; iv[p].val_next=i;
00245 } else if (iv[i].val < v.min()) {
00246 iv[i].mark(); i=iv[i].val_next; iv[p].val_next=i;
00247 } else if (iv[i].val > v.max()) {
00248 ++v;
00249 } else {
00250 p=i; i=iv[i].val_next;
00251 }
00252 }
00253 iv[p].val_next = 0;
00254 while (i != 0) { iv[i].mark(); i=iv[i].val_next; }
00255 }
00256
00257
00258 {
00259 IterIdx i(iv);
00260 GECODE_ME_CHECK(x0.narrow_v(home,i,false));
00261 IterVal v(iv);
00262 if (shared(x0,x1)) {
00263 GECODE_ME_CHECK(x1.inter_v(home,v,false));
00264 return assigned ? ES_SUBSUMED(*this,home) : ES_NOFIX;
00265 } else {
00266 GECODE_ME_CHECK(x1.narrow_v(home,v,false));
00267 return (x0.assigned() || x1.assigned()) ?
00268 ES_SUBSUMED(*this,home) : ES_FIX;
00269 }
00270 }
00271 }
00272
00273 template<class V0, class V1>
00274 forceinline ExecStatus
00275 post_int(Home home, IntSharedArray& c, V0 x0, V1 x1) {
00276 assert(c.size() > 0);
00277 GECODE_ME_CHECK(x0.gq(home,0));
00278 GECODE_ME_CHECK(x0.le(home,c.size()));
00279 Support::IntType idx_type = Support::s_type(c.size());
00280 int min = c[0];
00281 int max = c[0];
00282 for (int i=1; i<c.size(); i++) {
00283 min = std::min(c[i],min); max = std::max(c[i],max);
00284 }
00285 GECODE_ME_CHECK(x1.gq(home,min));
00286 GECODE_ME_CHECK(x1.lq(home,max));
00287 Support::IntType val_type =
00288 std::max(Support::s_type(min),Support::s_type(max));
00289 switch (idx_type) {
00290 case Support::IT_CHAR:
00291 switch (val_type) {
00292 case Support::IT_CHAR:
00293 return Int<V0,V1,signed char,signed char>::post(home,c,x0,x1);
00294 case Support::IT_SHRT:
00295 return Int<V0,V1,signed char,signed short int>::post(home,c,x0,x1);
00296 case Support::IT_INT:
00297 return Int<V0,V1,signed char,signed int>::post(home,c,x0,x1);
00298 default: GECODE_NEVER;
00299 }
00300 break;
00301 case Support::IT_SHRT:
00302 switch (val_type) {
00303 case Support::IT_CHAR:
00304 return Int<V0,V1,signed short int,signed char>::post(home,c,x0,x1);
00305 case Support::IT_SHRT:
00306 return Int<V0,V1,signed short int,signed short int>::post(home,c,x0,x1);
00307 case Support::IT_INT:
00308 return Int<V0,V1,signed short int,signed int>::post(home,c,x0,x1);
00309 default: GECODE_NEVER;
00310 }
00311 break;
00312 case Support::IT_INT:
00313 switch (val_type) {
00314 case Support::IT_CHAR:
00315 return Int<V0,V1,signed int,signed char>::post(home,c,x0,x1);
00316 case Support::IT_SHRT:
00317 return Int<V0,V1,signed int,signed short int>::post(home,c,x0,x1);
00318 case Support::IT_INT:
00319 return Int<V0,V1,signed int,signed int>::post(home,c,x0,x1);
00320 default: GECODE_NEVER;
00321 }
00322 break;
00323 default: GECODE_NEVER;
00324 }
00325 return ES_OK;
00326 }
00327
00328 }}}
00329
00330
00331