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 x0.cancel(home,*this,PC_INT_DOM);
00140 x1.cancel(home,*this,PC_INT_DOM);
00141 c.~IntSharedArray();
00142 (void) Propagator::dispose(home);
00143 return sizeof(*this);
00144 }
00145
00146 template<class V0, class V1, class Idx, class Val>
00147 ExecStatus
00148 Int<V0,V1,Idx,Val>::post(Home home, IntSharedArray& c, V0 x0, V1 x1) {
00149 if (x0.assigned()) {
00150 GECODE_ME_CHECK(x1.eq(home,c[x0.val()]));
00151 } else {
00152 (void) new (home) Int<V0,V1,Idx,Val>(home,c,x0,x1);
00153 }
00154 return ES_OK;
00155 }
00156
00157 template<class V0, class V1, class Idx, class Val>
00158 forceinline
00159 Int<V0,V1,Idx,Val>::Int(Space& home, bool share, Int& p)
00160 : Propagator(home,share,p), iv(NULL) {
00161 c.update(home,share,p.c);
00162 x0.update(home,share,p.x0);
00163 x1.update(home,share,p.x1);
00164 }
00165
00166 template<class V0, class V1, class Idx, class Val>
00167 Actor*
00168 Int<V0,V1,Idx,Val>::copy(Space& home, bool share) {
00169 return new (home) Int<V0,V1,Idx,Val>(home,share,*this);
00170 }
00171
00172 template<class V0, class V1, class Idx, class Val>
00173 PropCost
00174 Int<V0,V1,Idx,Val>::cost(const Space&, const ModEventDelta&) const {
00175 return PropCost::binary(PropCost::HI);
00176 }
00177
00178 template<class V0, class V1, class Idx, class Val>
00179 ExecStatus
00180 Int<V0,V1,Idx,Val>::propagate(Space& home, const ModEventDelta&) {
00181 bool assigned = x0.assigned() && x1.assigned();
00182 if (iv == NULL) {
00183
00184 iv = home.alloc<IdxVal>(x0.size() + 1);
00185
00186
00187
00188 IdxVal* by_idx = &iv[1];
00189 {
00190 Idx i = 0;
00191 ViewValues<V0> v(x0);
00192 while (v()) {
00193 by_idx[i].idx = static_cast<Idx>(v.val());
00194 by_idx[i].val = static_cast<Val>(c[v.val()]);
00195 ++i; ++v;
00196 }
00197 }
00198 Idx size = static_cast<Idx>(x0.size());
00199
00200 Region r(home);
00201 Idx* by_val = r.alloc<Idx>(size);
00202 for (Idx i = size; i--; )
00203 by_val[i] = i+1;
00204 ByVal less(iv);
00205 Support::quicksort<Idx>(by_val,size,less);
00206
00207 for (Idx i = size-1; i--; ) {
00208 by_idx[i].idx_next = i+2;
00209 iv[by_val[i]].val_next = by_val[i+1];
00210 }
00211 by_idx[size-1].idx_next = 0;
00212 iv[by_val[size-1]].val_next = 0;
00213
00214 iv[0].idx_next = 1;
00215 iv[0].val_next = by_val[0];
00216 } else {
00217
00218 Idx p = 0;
00219 Idx i = iv[p].idx_next;
00220 ViewRanges<V0> v(x0);
00221 while (v() && (i != 0)) {
00222 assert(!iv[i].marked());
00223 if (iv[i].idx < v.min()) {
00224 iv[i].mark(); i=iv[i].idx_next; iv[p].idx_next=i;
00225 } else if (iv[i].idx > v.max()) {
00226 ++v;
00227 } else {
00228 p=i; i=iv[i].idx_next;
00229 }
00230 }
00231 iv[p].idx_next = 0;
00232 while (i != 0) { iv[i].mark(); i=iv[i].idx_next; }
00233 }
00234
00235
00236 {
00237 Idx p = 0;
00238 Idx i = iv[p].val_next;
00239 ViewRanges<V1> v(x1);
00240 while (v() && (i != 0)) {
00241 if (iv[i].marked()) {
00242 i=iv[i].val_next; iv[p].val_next=i;
00243 } else if (iv[i].val < v.min()) {
00244 iv[i].mark(); i=iv[i].val_next; iv[p].val_next=i;
00245 } else if (iv[i].val > v.max()) {
00246 ++v;
00247 } else {
00248 p=i; i=iv[i].val_next;
00249 }
00250 }
00251 iv[p].val_next = 0;
00252 while (i != 0) { iv[i].mark(); i=iv[i].val_next; }
00253 }
00254
00255
00256 {
00257 IterIdx i(iv);
00258 GECODE_ME_CHECK(x0.narrow_v(home,i,false));
00259 IterVal v(iv);
00260 if (shared(x0,x1)) {
00261 GECODE_ME_CHECK(x1.inter_v(home,v,false));
00262 return assigned ? home.ES_SUBSUMED(*this) : ES_NOFIX;
00263 } else {
00264 GECODE_ME_CHECK(x1.narrow_v(home,v,false));
00265 return (x0.assigned() || x1.assigned()) ?
00266 home.ES_SUBSUMED(*this) : ES_FIX;
00267 }
00268 }
00269 }
00270
00271 template<class V0, class V1>
00272 forceinline ExecStatus
00273 post_int(Home home, IntSharedArray& c, V0 x0, V1 x1) {
00274 assert(c.size() > 0);
00275 GECODE_ME_CHECK(x0.gq(home,0));
00276 GECODE_ME_CHECK(x0.le(home,c.size()));
00277 Support::IntType idx_type = Support::s_type(c.size());
00278 int min = c[0];
00279 int max = c[0];
00280 for (int i=1; i<c.size(); i++) {
00281 min = std::min(c[i],min); max = std::max(c[i],max);
00282 }
00283 GECODE_ME_CHECK(x1.gq(home,min));
00284 GECODE_ME_CHECK(x1.lq(home,max));
00285 Support::IntType val_type =
00286 std::max(Support::s_type(min),Support::s_type(max));
00287 switch (idx_type) {
00288 case Support::IT_CHAR:
00289 switch (val_type) {
00290 case Support::IT_CHAR:
00291 return Int<V0,V1,signed char,signed char>::post(home,c,x0,x1);
00292 case Support::IT_SHRT:
00293 return Int<V0,V1,signed char,signed short int>::post(home,c,x0,x1);
00294 case Support::IT_INT:
00295 return Int<V0,V1,signed char,signed int>::post(home,c,x0,x1);
00296 default: GECODE_NEVER;
00297 }
00298 break;
00299 case Support::IT_SHRT:
00300 switch (val_type) {
00301 case Support::IT_CHAR:
00302 return Int<V0,V1,signed short int,signed char>::post(home,c,x0,x1);
00303 case Support::IT_SHRT:
00304 return Int<V0,V1,signed short int,signed short int>::post(home,c,x0,x1);
00305 case Support::IT_INT:
00306 return Int<V0,V1,signed short int,signed int>::post(home,c,x0,x1);
00307 default: GECODE_NEVER;
00308 }
00309 break;
00310 case Support::IT_INT:
00311 switch (val_type) {
00312 case Support::IT_CHAR:
00313 return Int<V0,V1,signed int,signed char>::post(home,c,x0,x1);
00314 case Support::IT_SHRT:
00315 return Int<V0,V1,signed int,signed short int>::post(home,c,x0,x1);
00316 case Support::IT_INT:
00317 return Int<V0,V1,signed int,signed int>::post(home,c,x0,x1);
00318 default: GECODE_NEVER;
00319 }
00320 break;
00321 default: GECODE_NEVER;
00322 }
00323 return ES_OK;
00324 }
00325
00326 }}}
00327
00328
00329