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