Generated on Mon Nov 30 23:53:28 2009 for Gecode by doxygen 1.6.1

int-dom.hpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2006
00008  *
00009  *  Last modified:
00010  *     $Date: 2009-10-12 17:36:53 +0200 (Mon, 12 Oct 2009) $ by $Author: schulte $
00011  *     $Revision: 9878 $
00012  *
00013  *  This file is part of Gecode, the generic constraint
00014  *  development environment:
00015  *     http://www.gecode.org
00016  *
00017  *  Permission is hereby granted, free of charge, to any person obtaining
00018  *  a copy of this software and associated documentation files (the
00019  *  "Software"), to deal in the Software without restriction, including
00020  *  without limitation the rights to use, copy, modify, merge, publish,
00021  *  distribute, sublicense, and/or sell copies of the Software, and to
00022  *  permit persons to whom the Software is furnished to do so, subject to
00023  *  the following conditions:
00024  *
00025  *  The above copyright notice and this permission notice shall be
00026  *  included in all copies or substantial portions of the Software.
00027  *
00028  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00029  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00030  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00031  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00032  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00033  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00034  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00035  *
00036  */
00037 
00038 namespace Gecode { namespace Int { namespace Linear {
00039 
00047   class SupportSet {
00048   private:
00050     static const unsigned int bpui = sizeof(unsigned int) * 8;
00052     unsigned int n;
00054     unsigned int* bits;
00055   public:
00057     void init(Region& r, unsigned int n);
00059     void support(unsigned int i);
00061     bool supported(unsigned int i) const;
00062 
00063   private:
00065     class ResultIter : public ViewValues<IntView> {
00066     protected:
00068       const SupportSet* s;
00070       unsigned int p;
00071     public:
00073       ResultIter(const SupportSet* s0, const IntView& x);
00075       void operator ++(void);
00076     };
00077 
00078   public:
00080     ModEvent tell(Space& home, IntView& x) const;
00081   };
00082 
00087   template<class Val>
00088   class SupportIter {
00089   protected:
00091     int           a;
00093     IntView       x;
00095     SupportSet    s;
00097     int           c;
00099     unsigned int  p;
00101     Val           l;
00103     Val           u;
00104   public:
00106     void init(Region& r, int a, const IntView& x, Val l, Val u);
00108     void support(void);
00110     ModEvent tell(Space& home);
00111   };
00112 
00113 
00118   template<class Val>
00119   class PosSupportIter : public SupportIter<Val> {
00120   private:
00122     IntVarImpFwd i;
00123     // Using-declarations for dependant names
00124     using SupportIter<Val>::a;
00125     using SupportIter<Val>::x;
00126     using SupportIter<Val>::s;
00127     using SupportIter<Val>::c;
00128     using SupportIter<Val>::p;
00129     using SupportIter<Val>::l;
00130     using SupportIter<Val>::u;
00131   public:
00133     bool reset(Val& d);
00135     bool adjust(Val& d);
00136   };
00137 
00138 
00143   template<class Val>
00144   class NegSupportIter : public SupportIter<Val> {
00145   private:
00147     IntVarImpBwd i;
00148     // Using-declarations for dependant names
00149     using SupportIter<Val>::a;
00150     using SupportIter<Val>::x;
00151     using SupportIter<Val>::s;
00152     using SupportIter<Val>::c;
00153     using SupportIter<Val>::p;
00154     using SupportIter<Val>::l;
00155     using SupportIter<Val>::u;
00156   public:
00158     bool reset(Val& d);
00160     bool adjust(Val& d);
00161   };
00162 
00163 
00164   /*
00165    * Support set
00166    *
00167    */
00168   forceinline void
00169   SupportSet::init(Region& r, unsigned int n0) {
00170     n = n0;
00171     bits = r.alloc<unsigned int>((n / bpui) + 1);
00172     for (unsigned int i = (n / bpui) + 1; i--; )
00173       bits[i] = 0;
00174   }
00175   forceinline void
00176   SupportSet::support(unsigned int i) {
00177     unsigned int p = i / bpui;
00178     bits[p] |= 1 << (i-p*bpui);
00179   }
00180   forceinline bool
00181   SupportSet::supported(unsigned int i) const {
00182     unsigned int p = i / bpui;
00183     return (bits[p] & (1 << (i-p*bpui))) != 0;
00184   }
00185 
00186   forceinline
00187   SupportSet::ResultIter::ResultIter(const SupportSet* s0, const IntView& x)
00188     : ViewValues<IntView>(x), s(s0), p(0) {
00189     while (ViewValues<IntView>::operator ()() && s->supported(p)) {
00190       ViewValues<IntView>::operator ++(); ++p;
00191     }
00192   }
00193   forceinline void
00194   SupportSet::ResultIter::operator ++(void) {
00195     do {
00196       ViewValues<IntView>::operator ++(); ++p;
00197     } while (ViewValues<IntView>::operator ()() && s->supported(p));
00198   }
00199 
00200 
00201   inline ModEvent
00202   SupportSet::tell(Space& home, IntView& x) const {
00203     unsigned int n = x.size() / bpui;
00204     // Check whether all bits are zero: failure
00205     for (unsigned int i=n+1; i--; )
00206       if (bits[i] != 0)
00207         goto all;
00208     return ME_INT_FAILED;
00209   all:
00210     // Check whether all bits are one: nothing changed
00211     for (unsigned int i=n; i--; )
00212       if (bits[i] != ~0U)
00213         goto tell;
00214     // Now check the bits in the last word
00215     for (unsigned int i=n*bpui; i<x.size(); i++)
00216       if (!supported(i))
00217         goto tell;
00218     return ME_INT_NONE;
00219   tell:
00220     {
00221       ResultIter i(this,x);
00222       return x.minus_v(home,i);
00223     }
00224   }
00225 
00226 
00227   /*
00228    * Base-class for support-based iterator
00229    *
00230    */
00231   template<class Val>
00232   forceinline void
00233   SupportIter<Val>::init(Region& r,
00234                          int a0, const IntView& x0, Val l0, Val u0) {
00235     a=a0; x=x0; l=l0; u=u0;
00236     s.init(r,x.size());
00237   }
00238   template<class Val>
00239   forceinline void
00240   SupportIter<Val>::support(void) {
00241     s.support(p);
00242   }
00243   template<class Val>
00244   forceinline ModEvent
00245   SupportIter<Val>::tell(Space& home) {
00246     return s.tell(home,x);
00247   }
00248 
00249 
00250   /*
00251    * Support-based iterator for positive view
00252    *
00253    */
00254   template<class Val>
00255   forceinline bool
00256   PosSupportIter<Val>::reset(Val& d) {
00257     // Way too small, no value can make it big enough
00258     if (d + static_cast<Val>(a)*x.max() < u)
00259       return false;
00260     // Restart iterator and position of values
00261     i.init(x.var()); p = 0;
00262     // Skip all ranges which are too small
00263     while (d + static_cast<Val>(a)*i.max() < u) {
00264       p += i.width(); ++i;
00265     }
00266     // There is at least one range left (check of max)
00267     assert(i());
00268     // Initialize current range and adjust value
00269     c = i.min();
00270     // Skip all values which are too small
00271     while (d + static_cast<Val>(a)*c < u) {
00272       p++; c++;
00273     }
00274     // Adjust to new value
00275     d += static_cast<Val>(a) * c;
00276     return true;
00277   }
00278   template<class Val>
00279   forceinline bool
00280   PosSupportIter<Val>::adjust(Val& d) {
00281     // Current value
00282     Val v = static_cast<Val>(a) * c;
00283     // Subtract current value from d
00284     d -= v;
00285     // Move to next position (number of value)
00286     p++;
00287     // Still in the same range
00288     if (c < i.max()) {
00289       // Decrement current values
00290       c += 1; v += a;
00291     } else {
00292       // Go to next range
00293       ++i;
00294       if (!i())
00295         return false;
00296       c = i.min(); v = static_cast<Val>(a) * c;
00297     }
00298     // Is d with the current value too large?
00299     if (d + v > l)
00300       return false;
00301     // Update d
00302     d += v;
00303     return true;
00304   }
00305 
00306 
00307   /*
00308    * Support-based iterator for negative view
00309    *
00310    */
00311   template<class Val>
00312   forceinline bool
00313   NegSupportIter<Val>::reset(Val& d) {
00314     // Way too small, no value can make it big enough
00315     if (d + static_cast<Val>(a)*x.min() < u)
00316       return false;
00317     // Restart iterator and position of values
00318     i.init(x.var()); p = x.size()-1;
00319     // Skip all ranges which are too small
00320     while (d + static_cast<Val>(a)*i.min() < u) {
00321       p -= i.width(); ++i;
00322     }
00323     // There is at least one range left (check of max)
00324     assert(i());
00325     // Initialize current range
00326     c = i.max();
00327     // Skip all values which are too small
00328     while (d + static_cast<Val>(a)*c < u) {
00329       p--; c--;
00330     }
00331     // Adjust to new value
00332     d += static_cast<Val>(a) * c;
00333     return true;
00334   }
00335   template<class Val>
00336   forceinline bool
00337   NegSupportIter<Val>::adjust(Val& d) {
00338     // Current value
00339     Val v = static_cast<Val>(a) * c;
00340     // Subtract current value from d
00341     d -= v;
00342     // Move to next position (number of value)
00343     p--;
00344     // Still in the same range
00345     if (c > i.min()) {
00346       // Decrement current values
00347       c -= 1; v -= a;
00348     } else {
00349       // Go to next range
00350       ++i;
00351       if (!i())
00352         return false;
00353       c = i.max(); v = static_cast<Val>(a) * c;
00354     }
00355     // Is d with the current value too large?
00356     if (d + v > l)
00357       return false;
00358     // Update d
00359     d += v;
00360     return true;
00361   }
00362 
00363 
00364 
00365   /*
00366    * The domain consisten equality propagator
00367    *
00368    */
00369   template<class Val, class View>
00370   forceinline
00371   DomEq<Val,View>::DomEq(Home home,
00372                          ViewArray<View >& x, ViewArray<View >& y,
00373                          Val c)
00374     : Lin<Val,View,View,PC_INT_DOM>(home,x,y,c) {}
00375 
00376   template<class Val, class View>
00377   ExecStatus
00378   DomEq<Val,View>::post(Home home,
00379                         ViewArray<View>& x, ViewArray<View>& y,
00380                         Val c) {
00381     (void) new (home) DomEq<Val,View>(home,x,y,c);
00382     return ES_OK;
00383   }
00384 
00385   template<class Val, class View>
00386   forceinline
00387   DomEq<Val,View>::DomEq(Space& home, bool share, DomEq<Val,View>& p)
00388     : Lin<Val,View,View,PC_INT_DOM>(home,share,p) {}
00389 
00390   template<class Val, class View>
00391   Actor*
00392   DomEq<Val,View>::copy(Space& home, bool share) {
00393     return new (home) DomEq<Val,View>(home,share,*this);
00394   }
00395 
00396   template<class Val, class View>
00397   PropCost
00398   DomEq<Val,View>::cost(const Space&, const ModEventDelta& med) const {
00399     if (View::me(med) != ME_INT_DOM)
00400       return PropCost::linear(PropCost::LO, x.size()+y.size());
00401     else
00402       return PropCost::crazy(PropCost::HI, x.size()+y.size());
00403   }
00404 
00405   template<class Val, class View>
00406   ExecStatus
00407   DomEq<Val,View>::propagate(Space& home, const ModEventDelta& med) {
00408     if (View::me(med) != ME_INT_DOM) {
00409       ExecStatus es = prop_bnd<Val,View,View>(home,med,*this,x,y,c);
00410       GECODE_ES_CHECK(es);
00411       return ES_FIX_PARTIAL(*this,View::med(ME_INT_DOM));
00412     }
00413 
00414     // Value of equation for partial assignment
00415     Val d = -c;
00416 
00417     int n = x.size();
00418     int m = y.size();
00419 
00420     Region r(home);
00421     // Create support-base iterators
00422     PosSupportIter<Val>* xp = r.alloc<PosSupportIter<Val> >(n);
00423     NegSupportIter<Val>* yp = r.alloc<NegSupportIter<Val> >(m);
00424 
00425     // Initialize views for assignments
00426     {
00427       Val l = 0;
00428       Val u = 0;
00429       for (int j=m; j--; ) {
00430         yp[j].init(r,-y[j].scale(),y[j].base(),l,u);
00431         l += y[j].max(); u += y[j].min();
00432       }
00433       for (int i=n; i--; ) {
00434         xp[i].init(r,x[i].scale(),x[i].base(),l,u);
00435         l -= x[i].min(); u -= x[i].max();
00436       }
00437     }
00438 
00439     // Collect support information by iterating assignments
00440     {
00441       // Force reset of all iterators in first round
00442       int i = 0;
00443       int j = 0;
00444 
00445     next_i:
00446       // Reset all iterators for positive views and update d
00447       while (i<n) {
00448         if (!xp[i].reset(d)) goto prev_i;
00449         i++;
00450       }
00451     next_j:
00452       // Reset all iterators for negative views and update d
00453       while (j<m) {
00454         if (!yp[j].reset(d)) goto prev_j;
00455         j++;
00456       }
00457       // Check whether current assignment is solution
00458       if (d == 0) {
00459         // Record support
00460         for (int is=n; is--; ) xp[is].support();
00461         for (int js=m; js--; ) yp[js].support();
00462       }
00463     prev_j:
00464       // Try iterating to next assignment: negative views
00465       while (j>0) {
00466         if (yp[j-1].adjust(d)) goto next_j;
00467         j--;
00468       }
00469     prev_i:
00470       // Try iterating to next assignment: positive views
00471       while (i>0) {
00472         if (xp[i-1].adjust(d)) goto next_i;
00473         i--;
00474       }
00475     }
00476 
00477     // Tell back new variable domains
00478     bool assigned = true;
00479     for (int i=n; i--; ) {
00480       GECODE_ME_CHECK(xp[i].tell(home));
00481       if (!x[i].assigned())
00482         assigned = false;
00483     }
00484     for (int j=m; j--; ) {
00485       GECODE_ME_CHECK(yp[j].tell(home));
00486       if (!y[j].assigned())
00487         assigned = false;
00488     }
00489     if (assigned)
00490       return ES_SUBSUMED(*this,sizeof(*this));
00491     return ES_FIX;
00492   }
00493 
00494 }}}
00495 
00496 // STATISTICS: int-prop