Generated on Mon May 5 05:53:53 2008 for Gecode by doxygen 1.5.5

dom.icc

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