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