Generated on Mon May 10 06:46:31 2010 for Gecode by doxygen 1.6.3

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  *  Contributing authors:
00007  *     Mikael Lagerkvist <lagerkvist@gecode.org>
00008  *
00009  *  Copyright:
00010  *     Christian Schulte, 2006
00011  *     Mikael Lagerkvist, 2006
00012  *
00013  *  Last modified:
00014  *     $Date: 2010-03-03 17:32:21 +0100 (Wed, 03 Mar 2010) $ by $Author: schulte $
00015  *     $Revision: 10364 $
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 Channel {
00043 
00048   template<class View>
00049   class DomInfo {
00050   public:
00052     View view;
00054     unsigned int size;
00056     int min;
00058     int max;
00060     void init(View x, int n);
00062     void update(Space& home, bool share, DomInfo<View>& vcb);
00064     bool doval(void) const;
00066     bool dodom(void) const;
00068     void assigned(void);
00070     void removed(int i);
00072     void done(void);
00073   };
00074 
00075   template<class View>
00076   forceinline void
00077   DomInfo<View>::init(View x, int n) {
00078     view = x;
00079     size = static_cast<unsigned int>(n);
00080     min  = 0;
00081     max  = n-1;
00082   }
00083 
00084   template<class View>
00085   forceinline void
00086   DomInfo<View>::update(Space& home, bool share, DomInfo<View>& di) {
00087     view.update(home,share,di.view);
00088     size = di.size;
00089     min  = di.min;
00090     max  = di.max;
00091   }
00092 
00093   template<class View>
00094   forceinline bool
00095   DomInfo<View>::doval(void) const {
00096     return (size != 1) && view.assigned();
00097   }
00098 
00099   template<class View>
00100   forceinline bool
00101   DomInfo<View>::dodom(void) const {
00102     return size != view.size();
00103   }
00104 
00105   template<class View>
00106   forceinline void
00107   DomInfo<View>::assigned(void) {
00108     size = 1;
00109   }
00110 
00111   template<class View>
00112   forceinline void
00113   DomInfo<View>::removed(int i) {
00114     size--;
00115     if (i == min)
00116       min++;
00117     else if (i == max)
00118       max--;
00119   }
00120 
00121   template<class View>
00122   forceinline void
00123   DomInfo<View>::done(void) {
00124     size = view.size();
00125     min  = view.min();
00126     max  = view.max();
00127   }
00128 
00129   // Propagate domain information from x to y
00130   template<class View>
00131   ExecStatus
00132   prop_dom(Space& home, int n, DomInfo<View>* x, DomInfo<View>* y,
00133            ProcessStack& ya) {
00134     for (int i = n; i--; )
00135       // Only views with not yet propagated missing values
00136       if (x[i].dodom()) {
00137         // Iterate the values in the complement of x[i]
00138         ViewRanges<View>
00139           xir(x[i].view);
00140         Iter::Ranges::ComplVal<ViewRanges<View> >
00141           xirc(x[i].min,x[i].max,xir);
00142         Iter::Ranges::ToValues<Iter::Ranges::ComplVal<ViewRanges<View> > >
00143           jv(xirc);
00144         while (jv()) {
00145           // j is not in the domain of x[i], so prune i from y[j]
00146           int j = jv.val();
00147           ModEvent me = y[j].view.nq(home,i);
00148           if (me_failed(me))
00149             return ES_FAILED;
00150           if (me_modified(me)) {
00151             if (me == ME_INT_VAL) {
00152               // Record that y[j] has been assigned and must be propagated
00153               ya.push(j);
00154             } else {
00155               // Obvious as x[i] is different from j
00156               y[j].removed(i);
00157             }
00158           }
00159           ++jv;
00160         }
00161         // Update which values have been propagated and what are the new bounds
00162         x[i].done();
00163       }
00164     return ES_OK;
00165   }
00166 
00167   /*
00168    * The actual propagator
00169    *
00170    */
00171   template<class View, bool shared>
00172   forceinline
00173   Dom<View,shared>::Dom(Home home, int n, DomInfo<View>* xy)
00174     : Base<DomInfo<View>,PC_INT_DOM>(home,n,xy) {}
00175 
00176   template<class View, bool shared>
00177   forceinline
00178   Dom<View,shared>::Dom(Space& home, bool share, Dom<View,shared>& p)
00179     : Base<DomInfo<View>,PC_INT_DOM>(home,share,p) {}
00180 
00181   template<class View, bool shared>
00182   Actor*
00183   Dom<View,shared>::copy(Space& home, bool share) {
00184     return new (home) Dom<View,shared>(home,share,*this);
00185   }
00186 
00187   template<class View, bool shared>
00188   PropCost
00189   Dom<View,shared>::cost(const Space&, const ModEventDelta& med) const {
00190     if (View::me(med) == ME_INT_VAL)
00191       return PropCost::quadratic(PropCost::LO, 2*n);
00192     else
00193       return PropCost::quadratic(PropCost::HI, 2*n);
00194   }
00195 
00196   template<class View, bool shared>
00197   ExecStatus
00198   Dom<View,shared>::propagate(Space& home, const ModEventDelta& med) {
00199     Region r(home);
00200     ProcessStack xa(r,n);
00201     ProcessStack ya(r,n);
00202 
00203     DomInfo<View>* x = xy;
00204     DomInfo<View>* y = xy+n;
00205 
00206     if (View::me(med) == ME_INT_VAL) {
00207       // Scan x and y for assigned but not yet propagated views
00208       for (int i = n; i--; ) {
00209         if (x[i].doval()) xa.push(i);
00210         if (y[i].doval()) ya.push(i);
00211       }
00212 
00213       if (shared) {
00214         do {
00215           // Propagate assigned views for x
00216           GECODE_ES_CHECK((prop_val<View,DomInfo<View> >
00217                            (home,n,x,y,n_na,xa,ya)));
00218           // Propagate assigned views for y
00219           GECODE_ES_CHECK((prop_val<View,DomInfo<View> >
00220                            (home,n,y,x,n_na,ya,xa)));
00221           assert(ya.empty());
00222         } while (!xa.empty() || !ya.empty());
00223         return home.ES_NOFIX_PARTIAL(*this,View::med(ME_INT_DOM));
00224       } else {
00225         do {
00226           // Propagate assigned views for x
00227           GECODE_ES_CHECK((prop_val<View,DomInfo<View> >
00228                            (home,n,x,y,n_na,xa,ya)));
00229           // Propagate assigned views for y
00230           GECODE_ES_CHECK((prop_val<View,DomInfo<View> >
00231                            (home,n,y,x,n_na,ya,xa)));
00232           assert(ya.empty());
00233         } while (!xa.empty());
00234         return home.ES_FIX_PARTIAL(*this,View::med(ME_INT_DOM));
00235       }
00236     }
00237 
00238     // Process changed views for y
00239     // This propagates from y to x and possibly records xs that
00240     // got assigned
00241     GECODE_ES_CHECK(prop_dom(home,n,y,x,xa));
00242 
00243     // Process assigned views for x
00244     GECODE_ES_CHECK((prop_val<View,DomInfo<View> >(home,n,x,y,n_na,xa,ya)));
00245 
00246     // Perform domain consistent propagation for distinct on the x views
00247     if (dc.available()) {
00248       GECODE_ES_CHECK(dc.sync(home));
00249     } else {
00250       View* xv = r.alloc<View>(n);
00251       for (int i=n; i--; )
00252         xv[i] = x[i].view;
00253       GECODE_ES_CHECK(dc.init(home,n,&xv[0]));
00254     }
00255     bool assigned;
00256     GECODE_ES_CHECK(dc.propagate(home,assigned));
00257     if (assigned) {
00258       // This has assigned some more views in x which goes unnoticed
00259       // (that is, not recorded in xa). This must be checked and propagated
00260       // to the y views, however the distinctness on x is already
00261       // propagated.
00262       for (int i=n; i--; )
00263         if (x[i].doval()) {
00264           int j = x[i].view.val();
00265           // Assign the y variable to i (or test if already assigned!)
00266           ModEvent me = y[j].view.eq(home,i);
00267           if (me_failed(me))
00268             return ES_FAILED;
00269           if (me_modified(me)) {
00270             // Record that y[j] has been assigned and must be propagated
00271             assert(me == ME_INT_VAL);
00272             // Otherwise the modification event would not be ME_INT_VAL
00273             ya.push(j);
00274           }
00275           x[i].assigned(); n_na--;
00276         }
00277     }
00278 
00279     // Process changed views for x
00280     // This propagates from x to y and possibly records ys that
00281     // got assigned
00282     GECODE_ES_CHECK(prop_dom(home,n,x,y,ya));
00283 
00284     // Process assigned view again (some might have been found above)
00285     while (!xa.empty() || !ya.empty()) {
00286       // Process assigned views for x
00287       GECODE_ES_CHECK((prop_val<View,DomInfo<View> >(home,n,x,y,n_na,xa,ya)));
00288       // Process assigned views for y
00289       GECODE_ES_CHECK((prop_val<View,DomInfo<View> >(home,n,y,x,n_na,ya,xa)));
00290     };
00291 
00292     if (shared) {
00293       for (int i=2*n; i--; )
00294         if (!xy[i].view.assigned())
00295           return ES_NOFIX;
00296       return home.ES_SUBSUMED(*this);
00297     } else {
00298       return (n_na == 0) ? home.ES_SUBSUMED(*this) : ES_FIX;
00299     }
00300   }
00301 
00302   template<class View, bool shared>
00303   ExecStatus
00304   Dom<View,shared>::post(Home home, int n, DomInfo<View>* xy) {
00305     assert(n > 0);
00306     if (n == 1) {
00307       GECODE_ME_CHECK(xy[0].view.eq(home,0));
00308       GECODE_ME_CHECK(xy[1].view.eq(home,0));
00309       return ES_OK;
00310     }
00311     for (int i=2*n; i--; ) {
00312       GECODE_ME_CHECK(xy[i].view.gq(home,0));
00313       GECODE_ME_CHECK(xy[i].view.le(home,n));
00314     }
00315     (void) new (home) Dom<View,shared>(home,n,xy);
00316     return ES_OK;
00317   }
00318 
00319 }}}
00320 
00321 // STATISTICS: int-prop
00322