Generated on Wed Jan 4 17:49:09 2006 for Gecode by doxygen 1.4.6

int.icc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Christian Schulte <schulte@gecode.org>
00004  *
00005  *  Copyright:
00006  *     Christian Schulte, 2004
00007  *
00008  *  Last modified:
00009  *     $Date: 2005-08-09 17:26:38 +0200 (Tue, 09 Aug 2005) $ by $Author: schulte $
00010  *     $Revision: 2190 $
00011  *
00012  *  This file is part of Gecode, the generic constraint
00013  *  development environment:
00014  *     http://www.gecode.org
00015  *
00016  *  See the file "LICENSE" for information on usage and
00017  *  redistribution of this file, and for a
00018  *     DISCLAIMER OF ALL WARRANTIES.
00019  *
00020  */
00021 
00022 #include "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     // Unlink from both index and value links
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     // Enter information sorted by idx
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     // Create val links sorted by val
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     // Create idx links
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     // Link to sentinel element: iv[0]
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    * Element propagator proper
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   Int<ViewA,ViewB>::~Int(void) {
00314     x0.cancel(this,PC_INT_DOM);
00315     x1.cancel(this,PC_INT_DOM);
00316     delete ivm;
00317   }
00318 
00319   template <class ViewA, class ViewB>
00320   void
00321   Int<ViewA,ViewB>::flush(void) {
00322     delete ivm; ivm = NULL;
00323   }
00324 
00325   template <class ViewA, class ViewB>
00326   size_t
00327   Int<ViewA,ViewB>::size(void) const {
00328     return (ivm != NULL) ? ivm->size() : 0;
00329   }
00330 
00331   template <class ViewA, class ViewB>
00332   forceinline
00333   Int<ViewA,ViewB>::Int(Space* home, bool share, Int& p)
00334     : Propagator(home,share,p), ivm(NULL) {
00335     c.update(share,p.c);
00336     x0.update(home,share,p.x0);
00337     x1.update(home,share,p.x1);
00338   }
00339 
00340   template <class ViewA, class ViewB>
00341   Actor*
00342   Int<ViewA,ViewB>::copy(Space* home, bool share) {
00343     return new (home) Int<ViewA,ViewB>(home,share,*this);
00344   }
00345 
00346 
00347   template <class ViewA, class ViewB>
00348   PropCost
00349   Int<ViewA,ViewB>::cost(void) const {
00350     return PC_BINARY_HI;
00351   }
00352 
00353   template <class ViewA, class ViewB>
00354   ExecStatus
00355   Int<ViewA,ViewB>::propagate(Space* home) {
00356     if (ivm == NULL) {
00357       ivm = IdxValMap::allocate(x0.size());
00358       ivm->init(&c[0],x0);
00359     } else {
00360       ivm->prune_idx(x0);
00361     }
00362     ivm->prune_val(x1);
00363 
00364     if (ivm->failed())
00365       return ES_FAILED;
00366 
00367     ExecStatus es = ivm->tell(home,x0,x1);
00368 
00369     return (x0.assigned() || x1.assigned()) ? ES_SUBSUMED : es;
00370   }
00371 
00372 }}}
00373 
00374 
00375 // STATISTICS: int-prop
00376