00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 #include "gecode/iter.hh"
00023
00024 namespace Gecode { namespace Int { namespace Element {
00025
00035 class IdxValLink {
00036 public:
00037 IdxValLink *idx_prev, *idx_next;
00038 IdxValLink *val_prev, *val_next;
00039 int idx, val;
00040
00041 void unlink(void);
00042 };
00043
00044 forceinline void
00045 IdxValLink::unlink(void) {
00046
00047 IdxValLink* i_p = idx_prev; IdxValLink* i_n = idx_next;
00048 i_p->idx_next = i_n; i_n->idx_prev = i_p;
00049 IdxValLink* v_p = val_prev; IdxValLink* v_n = val_next;
00050 v_p->val_next = v_n; v_n->val_prev = v_p;
00051 }
00052
00053
00054
00059 class IterIdx {
00060 private:
00061 const IdxValLink *cur, *end;
00062 public:
00063 IterIdx(void);
00064 IterIdx(const IdxValLink&);
00065 void init(const IdxValLink&);
00066 bool operator()(void) const;
00067 void operator++(void);
00068 int val(void) const;
00069 };
00070
00071 forceinline
00072 IterIdx::IterIdx(void) {}
00073 forceinline
00074 IterIdx::IterIdx(const IdxValLink& ivl)
00075 : cur(ivl.idx_next), end(&ivl) {}
00076 forceinline void
00077 IterIdx::init(const IdxValLink& ivl) {
00078 cur = ivl.idx_next;
00079 end = &ivl;
00080 }
00081 forceinline bool
00082 IterIdx::operator()(void) const {
00083 return cur != end;
00084 }
00085 forceinline void
00086 IterIdx::operator++(void) {
00087 cur = cur->idx_next;
00088 }
00089 forceinline int
00090 IterIdx::val(void) const {
00091 return cur->idx;
00092 }
00093
00094
00095
00102 class IterVal {
00103 private:
00104 const IdxValLink *cur, *end;
00105 public:
00106 IterVal(void);
00107 IterVal(const IdxValLink&);
00108 void init(const IdxValLink&);
00109 bool operator()(void) const;
00110 void operator++(void);
00111 int val(void) const;
00112 };
00113
00114 forceinline
00115 IterVal::IterVal(void) {}
00116 forceinline
00117 IterVal::IterVal(const IdxValLink& ivl)
00118 : cur(ivl.val_next), end(&ivl) {}
00119 forceinline void
00120 IterVal::init(const IdxValLink& ivl) {
00121 cur = ivl.val_next;
00122 end = &ivl;
00123 }
00124 forceinline bool
00125 IterVal::operator()(void) const {
00126 return cur != end;
00127 }
00128 forceinline void
00129 IterVal::operator++(void) {
00130 cur = cur->val_next;
00131 }
00132 forceinline int
00133 IterVal::val(void) const {
00134 return cur->val;
00135 }
00136
00137
00138
00139
00144 class IdxValMap {
00145 private:
00147 class ByVal {
00148 public:
00149 bool operator()(IdxValLink*&, IdxValLink*&);
00150 };
00151 size_t _size;
00152 IdxValLink iv[1];
00153 public:
00155 static IdxValMap* allocate(int);
00156 template <class ViewA> void init(int*,ViewA);
00157
00159 template <class ViewA> void prune_idx(ViewA);
00160 template <class ViewB> void prune_val(ViewB);
00161
00163 template <class ViewA, class ViewB>
00164 ExecStatus tell(Space*,ViewA,ViewB) const;
00165 bool failed(void) const;
00166
00167 size_t size(void) const;
00168 static void operator delete(void* p,size_t);
00169 private:
00170 static void* operator new(size_t);
00171 };
00172
00173 forceinline bool
00174 IdxValMap::ByVal::operator()(IdxValLink*& x, IdxValLink*& y) {
00175 return x->val < y->val;
00176 }
00177
00178 forceinline IdxValMap*
00179 IdxValMap::allocate(int n) {
00180 size_t s = sizeof(IdxValMap)+n*sizeof(IdxValLink);
00181 IdxValMap* ivm = reinterpret_cast<IdxValMap*>(Memory::malloc(s));
00182 ivm->_size = s;
00183 return ivm;
00184 }
00185
00186 forceinline size_t
00187 IdxValMap::size(void) const {
00188 return _size;
00189 }
00190
00191 template <class ViewA>
00192 inline void
00193 IdxValMap::init(int* a, ViewA ix) {
00194
00195 IdxValLink* by_idx = &iv[1];
00196 {
00197 int i = 0;
00198 ViewValues<ViewA> v(ix);
00199 while (v()) {
00200 by_idx[i].idx = v.val();
00201 by_idx[i].val = a[v.val()];
00202 ++i; ++v;
00203 }
00204 }
00205 int size = ix.size();
00206
00207 GECODE_AUTOARRAY(IdxValLink*,by_val,size);
00208 for (int i = size; i--; )
00209 by_val[i] = &iv[i+1];
00210 ByVal lt;
00211 Support::quicksort<IdxValLink*>(by_val,size,lt);
00212
00213 for (int i = size-1; i--; ) {
00214 by_idx[i+1].idx_prev = by_idx+i;
00215 by_idx[i].idx_next = by_idx+i+1;
00216 by_val[i+1]->val_prev = by_val[i];
00217 by_val[i]->val_next = by_val[i+1];
00218 }
00219
00220 by_idx[0].idx_prev = &iv[0];
00221 by_idx[size-1].idx_next = &iv[0];
00222 by_val[0]->val_prev = &iv[0];
00223 by_val[size-1]->val_next = &iv[0];
00224 iv[0].idx_prev = &by_idx[size-1];
00225 iv[0].idx_next = &by_idx[0];
00226 iv[0].val_prev = by_val[size-1];
00227 iv[0].val_next = by_val[0];
00228 }
00229
00230 template <class ViewA>
00231 forceinline void
00232 IdxValMap::prune_idx(ViewA x0) {
00233 IdxValLink* l = iv[0].idx_next;
00234 ViewRanges<ViewA> i(x0);
00235 while (i() && (l != &iv[0])) {
00236 if (l->idx < i.min()) {
00237 l->unlink(); l = l->idx_next;
00238 } else if (l->idx > i.max()) {
00239 ++i;
00240 } else {
00241 l = l->idx_next;
00242 }
00243 }
00244 while (l != &iv[0]) { l->unlink(); l = l->idx_next; }
00245 }
00246
00247 template <class ViewB>
00248 forceinline void
00249 IdxValMap::prune_val(ViewB x1) {
00250 IdxValLink* l = iv[0].val_next;
00251 ViewRanges<ViewB> v(x1);
00252 while (v() && (l != &iv[0])) {
00253 if (l->val < v.min()) {
00254 l->unlink(); l = l->val_next;
00255 } else if (l->val > v.max()) {
00256 ++v;
00257 } else {
00258 l = l->val_next;
00259 }
00260 }
00261 while (l != &iv[0]) { l->unlink(); l = l->val_next; }
00262 }
00263
00264 forceinline bool
00265 IdxValMap::failed(void) const {
00266 return iv[0].val_next == &iv[0];
00267 }
00268
00269 template <class ViewA, class ViewB>
00270 forceinline ExecStatus
00271 IdxValMap::tell(Space* home, ViewA x0, ViewB x1) const {
00272 IterIdx i(iv[0]); Iter::Values::ToRanges<IterIdx> ri(i);
00273 x0.narrow(home,ri);
00274 IterVal v(iv[0]); Iter::Values::ToRanges<IterVal> rv(v);
00275 ExecStatus es = x1.modified() ? ES_NOFIX : ES_FIX;
00276 x1.narrow(home,rv);
00277 return es;
00278 }
00279
00280 forceinline void
00281 IdxValMap::operator delete(void* p,size_t) {
00282 Memory::free(p);
00283 }
00284
00285
00286
00287
00288
00289
00290
00291
00292
00293
00294 template <class ViewA, class ViewB>
00295 forceinline
00296 Int<ViewA,ViewB>::Int(Space* home, IntSharedArray& c0, ViewA y0, ViewB y1)
00297 : Propagator(home,true), x0(y0), x1(y1), c(c0), ivm(NULL) {
00298 x0.subscribe(home,this,PC_INT_DOM);
00299 x1.subscribe(home,this,PC_INT_DOM);
00300 }
00301
00302 template <class ViewA, class ViewB>
00303 ExecStatus
00304 Int<ViewA,ViewB>::post(Space* home, IntSharedArray& c, ViewA x0, ViewB x1) {
00305 GECODE_ME_CHECK(x0.gq(home,0));
00306 GECODE_ME_CHECK(x0.le(home,c.size()));
00307 (void) new (home) Int<ViewA,ViewB>(home,c,x0,x1);
00308 return ES_OK;
00309 }
00310
00311
00312 template <class ViewA, class ViewB>
00313 size_t
00314 Int<ViewA,ViewB>::dispose(Space* home) {
00315 if (!home->failed()) {
00316 x0.cancel(home,this,PC_INT_DOM);
00317 x1.cancel(home,this,PC_INT_DOM);
00318 }
00319 c.~IntSharedArray();
00320 delete ivm;
00321 (void) Propagator::dispose(home);
00322 return sizeof(*this);
00323 }
00324
00325 template <class ViewA, class ViewB>
00326 void
00327 Int<ViewA,ViewB>::flush(void) {
00328 delete ivm; ivm = NULL;
00329 }
00330
00331 template <class ViewA, class ViewB>
00332 size_t
00333 Int<ViewA,ViewB>::size(void) const {
00334 return (ivm != NULL) ? ivm->size() : 0;
00335 }
00336
00337 template <class ViewA, class ViewB>
00338 forceinline
00339 Int<ViewA,ViewB>::Int(Space* home, bool share, Int& p)
00340 : Propagator(home,share,p), ivm(NULL) {
00341 c.update(share,p.c);
00342 x0.update(home,share,p.x0);
00343 x1.update(home,share,p.x1);
00344 }
00345
00346 template <class ViewA, class ViewB>
00347 Actor*
00348 Int<ViewA,ViewB>::copy(Space* home, bool share) {
00349 return new (home) Int<ViewA,ViewB>(home,share,*this);
00350 }
00351
00352
00353 template <class ViewA, class ViewB>
00354 PropCost
00355 Int<ViewA,ViewB>::cost(void) const {
00356 return PC_BINARY_HI;
00357 }
00358
00359 template <class ViewA, class ViewB>
00360 ExecStatus
00361 Int<ViewA,ViewB>::propagate(Space* home) {
00362 if (ivm == NULL) {
00363 ivm = IdxValMap::allocate(x0.size());
00364 ivm->init(&c[0],x0);
00365 } else {
00366 ivm->prune_idx(x0);
00367 }
00368 ivm->prune_val(x1);
00369
00370 if (ivm->failed())
00371 return ES_FAILED;
00372
00373 ExecStatus es = ivm->tell(home,x0,x1);
00374
00375 return (x0.assigned() || x1.assigned()) ? ES_SUBSUMED : es;
00376 }
00377
00378 }}}
00379
00380
00381
00382