Generated on Thu Mar 22 10:39:38 2012 for Gecode by doxygen 1.6.3

incremental.hpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Mikael Lagerkvist <lagerkvist@gecode.org>
00005  *
00006  *  Contributing authors:
00007  *     Christian Schulte <schulte@gecode.org>
00008  *
00009  *  Copyright:
00010  *     Mikael Lagerkvist, 2007
00011  *     Christian Schulte, 2008
00012  *
00013  *  Last modified:
00014  *     $Date: 2010-07-14 17:46:18 +0200 (Wed, 14 Jul 2010) $ by $Author: schulte $
00015  *     $Revision: 11192 $
00016  *
00017  *  This file is part of Gecode, the generic constraint
00018  *  development environment:
00019  *     http://www.gecode.org
00020  *
00021  *  Permission is hereby granted, free of charge, to any person obtaining
00022  *  a copy of this software and associated documentation files (the
00023  *  "Software"), to deal in the Software without restriction, including
00024  *  without limitation the rights to use, copy, modify, merge, publish,
00025  *  distribute, sublicense, and/or sell copies of the Software, and to
00026  *  permit persons to whom the Software is furnished to do so, subject to
00027  *  the following conditions:
00028  *
00029  *  The above copyright notice and this permission notice shall be
00030  *  included in all copies or substantial portions of the Software.
00031  *
00032  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00033  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00034  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00035  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00036  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00037  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00038  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00039  *
00040  */
00041 
00042 namespace Gecode { namespace Int { namespace Extensional {
00043 
00044   /*
00045    * Support advisor
00046    *
00047    */
00048 
00049   template<class View>
00050   forceinline
00051   Incremental<View>::SupportAdvisor::
00052   SupportAdvisor(Space& home, Propagator& p, Council<SupportAdvisor>& c,
00053                  int i0)
00054     : Advisor(home,p,c), i(i0) {}
00055 
00056   template<class View>
00057   forceinline
00058   Incremental<View>::SupportAdvisor::
00059   SupportAdvisor(Space& home, bool share, SupportAdvisor& a)
00060     : Advisor(home,share,a), i(a.i) {}
00061 
00062   template<class View>
00063   forceinline void
00064   Incremental<View>::SupportAdvisor::
00065   dispose(Space& home, Council<SupportAdvisor>& c) {
00066     Advisor::dispose(home,c);
00067   }
00068 
00069 
00070   /*
00071    * Support entries
00072    *
00073    */
00074   template<class View>
00075   forceinline
00076   Incremental<View>::SupportEntry::SupportEntry(Tuple t0)
00077     : t(t0) {}
00078 
00079   template<class View>
00080   forceinline
00081   Incremental<View>::SupportEntry::SupportEntry(Tuple t0, SupportEntry* n)
00082     : FreeList(n), t(t0) {}
00083 
00084   template<class View>
00085   forceinline typename Incremental<View>::SupportEntry*
00086   Incremental<View>::SupportEntry::next(void) const {
00087     return static_cast<SupportEntry*>(FreeList::next());
00088   }
00089 
00090   template<class View>
00091   forceinline typename Incremental<View>::SupportEntry**
00092   Incremental<View>::SupportEntry::nextRef(void) {
00093     return reinterpret_cast<SupportEntry**>(FreeList::nextRef());
00094   }
00095 
00096   template<class View>
00097   forceinline void
00098   Incremental<View>::SupportEntry::operator delete(void*) {}
00099 
00100   template<class View>
00101   forceinline void
00102   Incremental<View>::SupportEntry::operator delete(void*, Space&) {
00103     GECODE_NEVER;
00104   }
00105 
00106   template<class View>
00107   forceinline void*
00108   Incremental<View>::SupportEntry::operator new(size_t, Space& home) {
00109     return home.fl_alloc<sizeof(SupportEntry)>();
00110   }
00111 
00112   template<class View>
00113   forceinline void
00114   Incremental<View>::SupportEntry::dispose(Space& home) {
00115     home.fl_dispose<sizeof(SupportEntry)>(this,this);
00116   }
00117 
00118   template<class View>
00119   forceinline void
00120   Incremental<View>::SupportEntry::dispose(Space& home, SupportEntry* l) {
00121     home.fl_dispose<sizeof(SupportEntry)>(this,l);
00122   }
00123 
00124 
00125   /*
00126    * Work entries
00127    *
00128    */
00129   template<class View>
00130   forceinline
00131   Incremental<View>::WorkEntry::WorkEntry(int i0, int n0, WorkEntry* n)
00132     : FreeList(n), i(i0), n(n0) {}
00133 
00134   template<class View>
00135   forceinline typename Incremental<View>::WorkEntry*
00136   Incremental<View>::WorkEntry::next(void) const {
00137     return static_cast<WorkEntry*>(FreeList::next());
00138   }
00139 
00140   template<class View>
00141   forceinline void
00142   Incremental<View>::WorkEntry::next(WorkEntry* n) {
00143     return FreeList::next(n);
00144   }
00145 
00146   template<class View>
00147   forceinline void
00148   Incremental<View>::WorkEntry::operator delete(void*) {}
00149 
00150   template<class View>
00151   forceinline void
00152   Incremental<View>::WorkEntry::operator delete(void*, Space&) {
00153     GECODE_NEVER;
00154   }
00155 
00156   template<class View>
00157   forceinline void*
00158   Incremental<View>::WorkEntry::operator new(size_t, Space& home) {
00159     return home.fl_alloc<sizeof(WorkEntry)>();
00160   }
00161 
00162   template<class View>
00163   forceinline void
00164   Incremental<View>::WorkEntry::dispose(Space& home) {
00165     home.fl_dispose<sizeof(WorkEntry)>(this,this);
00166   }
00167 
00168 
00169   /*
00170    * Work stack
00171    *
00172    */
00173   template<class View>
00174   forceinline
00175   Incremental<View>::Work::Work(void)
00176     : we(NULL) {}
00177   template<class View>
00178   forceinline bool
00179   Incremental<View>::Work::empty(void) const {
00180     return we == NULL;
00181   }
00182   template<class View>
00183   forceinline void
00184   Incremental<View>::Work::push(Space& home, int i, int n) {
00185     we = new (home) WorkEntry(i,n,we);
00186   }
00187   template<class View>
00188   forceinline void
00189   Incremental<View>::Work::pop(Space& home, int& i, int& n) {
00190     WorkEntry* d = we;
00191     we = we->next();
00192     i=d->i; n=d->n;
00193     d->dispose(home);
00194   }
00195 
00196 
00197   /*
00198    * Support management
00199    *
00200    */
00201   template<class View>
00202   forceinline typename Incremental<View>::SupportEntry*
00203   Incremental<View>::support(int i, int n) {
00204     return support_data[(i*(ts()->domsize)) + (n - ts()->min)];
00205   }
00206 
00207   template<class View>
00208   forceinline void
00209   Incremental<View>::init_support(Space& home) {
00210     assert(support_data == NULL);
00211     int literals = static_cast<int>(ts()->domsize*x.size());
00212     support_data = home.alloc<SupportEntry*>(literals);
00213     for (int i = literals; i--; )
00214       support_data[i] = NULL;
00215   }
00216 
00217   template<class View>
00218   forceinline void
00219   Incremental<View>::add_support(Space& home, Tuple l) {
00220     for (int i = x.size(); i--; ) {
00221       int pos = (i*static_cast<int>(ts()->domsize)) + (l[i] - ts()->min);
00222       support_data[pos] = new (home) SupportEntry(l, support_data[pos]);
00223     }
00224   }
00225 
00226   template<class View>
00227   forceinline void
00228   Incremental<View>::find_support(Space& home, Domain dom, int i, int n) {
00229     if (support(i,n) == NULL) {
00230       // Find support for value vv.val() in view i
00231       Tuple l = Base<View,false>::find_support(dom,i,n - ts()->min);
00232       if (l == NULL) {
00233         // No possible supports left
00234         w_remove.push(home,i,n);
00235       } else {
00236         // Mark values in support as supported
00237         add_support(home,l);
00238       }
00239     }
00240   }
00241 
00242   template<class View>
00243   forceinline void
00244   Incremental<View>::remove_support(Space& home, Tuple l, int i, int n) {
00245     (void) n;
00246     for (int j = x.size(); j--; ) {
00247       int v = l[j];
00248       int ov = v - ts()->min;
00249       int pos = (j*(static_cast<int>(ts()->domsize))) + ov;
00250 
00251       assert(support_data[pos] != NULL);
00252 
00253       SupportEntry** a = &(support_data[pos]);
00254       while ((*a)->t != l) {
00255         assert((*a)->next() != NULL);
00256         a = (*a)->nextRef();
00257       }
00258       SupportEntry* old = *a;
00259       *a = (*a)->next();
00260 
00261       old->dispose(home);
00262       if ((i != j) && (support_data[pos] == NULL))
00263         w_support.push(home, j, v);
00264     }
00265   }
00266 
00267 
00268 
00269   /*
00270    * The propagator proper
00271    *
00272    */
00273 
00274   template<class View>
00275   forceinline
00276   Incremental<View>::Incremental(Home home, ViewArray<View>& x,
00277                                  const TupleSet& t)
00278     : Base<View,false>(home,x,t), support_data(NULL),
00279       unassigned(x.size()), ac(home) {
00280     init_support(home);
00281 
00282     // Post advisors
00283     for (int i = x.size(); i--; )
00284       if (x[i].assigned()) {
00285         --unassigned;
00286       } else {
00287         x[i].subscribe(home,*new (home) SupportAdvisor(home,*this,ac,i));
00288       }
00289 
00290     Region r(home);
00291 
00292     // Add initial supports
00293     BitSet* dom = r.alloc<BitSet>(x.size());
00294     init_dom(home, dom);
00295     for (int i = x.size(); i--; )
00296       for (ViewValues<View> vv(x[i]); vv(); ++vv)
00297         find_support(home, dom, i, vv.val());
00298 
00299     // Work to be done or subsumption
00300     if (!w_support.empty() || !w_remove.empty() || (unassigned == 0))
00301       View::schedule(home,*this,
00302                      (unassigned != x.size()) ? ME_INT_VAL : ME_INT_DOM);
00303   }
00304 
00305   template<class View>
00306   forceinline ExecStatus
00307   Incremental<View>::post(Home home, ViewArray<View>& x, const TupleSet& t) {
00308     // All variables in the correct domain
00309     for (int i = x.size(); i--; ) {
00310       GECODE_ME_CHECK(x[i].gq(home, t.min()));
00311       GECODE_ME_CHECK(x[i].lq(home, t.max()));
00312     }
00313     (void) new (home) Incremental<View>(home,x,t);
00314     return ES_OK;
00315   }
00316 
00317   template<class View>
00318   forceinline
00319   Incremental<View>::Incremental(Space& home, bool share, Incremental<View>& p)
00320     : Base<View,false>(home,share,p), support_data(NULL),
00321       unassigned(p.unassigned) {
00322     ac.update(home,share,p.ac);
00323 
00324     init_support(home);
00325     for (int i = static_cast<int>(ts()->domsize*x.size()); i--; ) {
00326       SupportEntry** n = &(support_data[i]);
00327       SupportEntry*  o = p.support_data[i];
00328       while (o != NULL) {
00329         // Allocate new support entry
00330         SupportEntry* s = new (home) SupportEntry(o->t);
00331         // Link in support entry
00332         (*n) = s; n = s->nextRef();
00333         // move to next one
00334         o = o->next();
00335       }
00336       *n = NULL;
00337     }
00338   }
00339 
00340   template<class View>
00341   PropCost
00342   Incremental<View>::cost(const Space&, const ModEventDelta& med) const {
00343     if (View::me(med) == ME_INT_VAL)
00344       return PropCost::quadratic(PropCost::HI,x.size());
00345     else
00346       return PropCost::cubic(PropCost::HI,x.size());
00347   }
00348 
00349   template<class View>
00350   Actor*
00351   Incremental<View>::copy(Space& home, bool share) {
00352     return new (home) Incremental<View>(home,share,*this);
00353   }
00354 
00355   template<class View>
00356   forceinline size_t
00357   Incremental<View>::dispose(Space& home) {
00358     if (!home.failed()) {
00359       int literals = static_cast<int>(ts()->domsize*x.size());
00360       for (int i = literals; i--; )
00361         if (support_data[i]) {
00362           SupportEntry* lastse = support_data[i];
00363           while (lastse->next() != NULL)
00364             lastse = lastse->next();
00365           support_data[i]->dispose(home, lastse);
00366         }
00367       home.rfree(support_data, sizeof(SupportEntry*)*literals);
00368     }
00369     ac.dispose(home);
00370     (void) Base<View,false>::dispose(home);
00371     return sizeof(*this);
00372   }
00373 
00374   template<class View>
00375   ExecStatus
00376   Incremental<View>::propagate(Space& home, const ModEventDelta&) {
00377     assert(!w_support.empty() || !w_remove.empty() || unassigned==0);
00378     // Set up datastructures
00379     // Bit-sets for amortized O(1) access to domains
00380     Region r(home);
00381     // Add initial supports
00382     BitSet* dom = r.alloc<BitSet>(x.size());
00383     init_dom(home, dom);
00384 
00385     // Work loop
00386     while (!w_support.empty() || !w_remove.empty()) {
00387       while (!w_remove.empty()) {
00388         int i, n;
00389         w_remove.pop(home,i,n);
00390         // Work is still relevant
00391         if (dom[i].get(static_cast<unsigned int>(n-ts()->min))) {
00392           GECODE_ME_CHECK(x[i].nq(home,n));
00393           dom[i].clear(static_cast<unsigned int>(n-ts()->min));
00394         }
00395       }
00396       while (!w_support.empty()) {
00397         int i, n;
00398         w_support.pop(home,i,n);
00399         // Work is still relevant
00400         if (dom[i].get(static_cast<unsigned int>(n-ts()->min)))
00401           find_support(home, dom, i, n);
00402       }
00403     }
00404     if (unassigned != 0)
00405       return ES_FIX;
00406 
00407     return home.ES_SUBSUMED(*this);
00408   }
00409 
00410 
00411   template<class View>
00412   ExecStatus
00413   Incremental<View>::advise(Space& home, Advisor& _a, const Delta& d) {
00414     SupportAdvisor& a = static_cast<SupportAdvisor&>(_a);
00415     ModEvent me = View::modevent(d);
00416     bool scheduled = !w_support.empty() || !w_remove.empty();
00417 
00418     if (x[a.i].any(d)) {
00419       ViewValues<View> vv(x[a.i]);
00420       for (int n = ts()->min; n <= ts()->max; n++) {
00421         if (vv() && (n == vv.val())) {
00422           ++vv;
00423           continue;
00424         }
00425         while (SupportEntry* s = support(a.i,n))
00426           remove_support(home, s->t, a.i, n);
00427       }
00428     } else {
00429       for (int n = x[a.i].min(d); n <= x[a.i].max(d); n++)
00430         while (SupportEntry* s = support(a.i,n))
00431           remove_support(home, s->t, a.i, n);
00432     }
00433 
00434     if (me == ME_INT_VAL) {
00435       --unassigned;
00436       // nothing to do or already scheduled
00437       // propagator is not subsumed since unassigned!=0
00438       if (((w_support.empty() && w_remove.empty()) || scheduled) &&
00439           (unassigned != 0))
00440         return home.ES_FIX_DISPOSE(ac,a);
00441       else
00442         return home.ES_NOFIX_DISPOSE(ac,a);
00443     } else if ((w_support.empty() && w_remove.empty()) || scheduled) {
00444       // nothing to do or already scheduled
00445       return ES_FIX;
00446     }
00447     return ES_NOFIX;
00448   }
00449 
00450 
00451 }}}
00452 
00453 // STATISTICS: int-prop
00454