Generated on Tue May 22 09:40:02 2018 for Gecode by doxygen 1.6.3

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