Generated on Sat Feb 12 2011 17:40:48 for Gecode by doxygen 1.7.3

val.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 ValInfo {
00050   public:
00052     View view;
00054     bool a;
00056     void init(View x, int n);
00058     void update(Space& home, bool share, ValInfo<View>& vi);
00060     bool doval(void) const;
00062     bool dodom(void) const;
00064     void assigned(void);
00066     void removed(int i);
00068     void done(void);
00069   };
00070 
00071   template<class View>
00072   forceinline void
00073   ValInfo<View>::init(View x, int) {
00074     view = x; a = false;
00075   }
00076 
00077   template<class View>
00078   forceinline void
00079   ValInfo<View>::update(Space& home, bool share, ValInfo<View>& vi) {
00080     view.update(home,share,vi.view); a = vi.a;
00081   }
00082 
00083   template<class View>
00084   forceinline bool
00085   ValInfo<View>::doval(void) const {
00086     return !a && view.assigned();
00087   }
00088 
00089   template<class View>
00090   forceinline bool
00091   ValInfo<View>::dodom(void) const {
00092     return false;
00093   }
00094 
00095   template<class View>
00096   forceinline void
00097   ValInfo<View>::assigned(void) {
00098     a = true;
00099   }
00100 
00101   template<class View>
00102   forceinline void
00103   ValInfo<View>::removed(int) {}
00104 
00105   template<class View>
00106   forceinline void
00107   ValInfo<View>::done(void) {}
00108 
00109 
00110   // Propagate assigned views for x
00111   template<class View, class Info>
00112   ExecStatus
00113   doprop_val(Space& home, int n, Info* x, Info* y,
00114              int& n_na, ProcessStack& xa, ProcessStack& ya) {
00115     do {
00116       int i = xa.pop();
00117       int j = x[i].view.val();
00118       // Assign the y variable to i (or test if already assigned!)
00119       {
00120         ModEvent me = y[j].view.eq(home,i);
00121         if (me_failed(me))
00122           return ES_FAILED;
00123         // Record that y[j] has been assigned and must be propagated
00124         if (me_modified(me))
00125           ya.push(j);
00126       }
00127       // Prune the value j from all x variables
00128       for (int k=i; k--; ) {
00129         ModEvent me = x[k].view.nq(home,j);
00130         if (me_failed(me))
00131           return ES_FAILED;
00132         if (me_modified(me)) {
00133           if (me == ME_INT_VAL) {
00134             // Record that x[k] has been assigned and must be propagated
00135             xa.push(k);
00136           } else {
00137             // One value has been removed and this removal does not need
00138             // to be propagated again: after all y[j] = i, so it holds
00139             // that y[j] != k.
00140             x[k].removed(j);
00141           }
00142         }
00143       }
00144       // The same for the other views
00145       for (int k=i+1; k<n; k++) {
00146         ModEvent me = x[k].view.nq(home,j);
00147         if (me_failed(me))
00148           return ES_FAILED;
00149         if (me_modified(me)) {
00150           if (me == ME_INT_VAL) {
00151             // Record that x[k] has been assigned and must be propagated
00152             xa.push(k);
00153           } else {
00154             // One value has been removed and this removal does not need
00155             // to be propagated again: after all y[j] = i, so it holds
00156             // that y[j] != k.
00157             x[k].removed(j);
00158           }
00159         }
00160       }
00161       x[i].assigned(); n_na--;
00162     } while (!xa.empty());
00163     return ES_OK;
00164   }
00165 
00166   // Just do a test whether a call to the routine is necessary
00167   template<class View, class Info>
00168   forceinline ExecStatus
00169   prop_val(Space& home, int n, Info* x, Info* y,
00170            int& n_na, ProcessStack& xa, ProcessStack& ya) {
00171     if (xa.empty())
00172       return ES_OK;
00173     return doprop_val<View,Info>(home,n,x,y,n_na,xa,ya);
00174   }
00175 
00176   /*
00177    * The actual propagator
00178    *
00179    */
00180   template<class View, bool shared>
00181   forceinline
00182   Val<View,shared>::Val(Home home, int n, ValInfo<View>* xy)
00183     : Base<ValInfo<View>,PC_INT_VAL>(home,n,xy) {}
00184 
00185   template<class View, bool shared>
00186   forceinline
00187   Val<View,shared>::Val(Space& home, bool share, Val<View,shared>& p)
00188     : Base<ValInfo<View>,PC_INT_VAL>(home,share,p) {}
00189 
00190   template<class View, bool shared>
00191   Actor*
00192   Val<View,shared>::copy(Space& home, bool share) {
00193     return new (home) Val<View,shared>(home,share,*this);
00194   }
00195 
00196   template<class View, bool shared>
00197   ExecStatus
00198   Val<View,shared>::propagate(Space& home, const ModEventDelta&) {
00199     Region r(home);
00200     ProcessStack xa(r,n);
00201     ProcessStack ya(r,n);
00202 
00203     ValInfo<View>* x = xy;
00204     ValInfo<View>* y = xy+n;
00205 
00206     // Scan x and y for assigned but not yet propagated views
00207     for (int i = n; i--; ) {
00208       if (x[i].doval()) xa.push(i);
00209       if (y[i].doval()) ya.push(i);
00210     }
00211 
00212     do {
00213       // Propagate assigned views for x
00214       GECODE_ES_CHECK((prop_val<View,ValInfo<View> >(home,n,x,y,n_na,xa,ya)));
00215       // Propagate assigned views for y
00216       GECODE_ES_CHECK((prop_val<View,ValInfo<View> >(home,n,y,x,n_na,ya,xa)));
00217       assert(ya.empty());
00218     } while (!xa.empty());
00219 
00220     if (n_na == 0)
00221       return home.ES_SUBSUMED(*this);
00222     return shared ? ES_NOFIX : ES_FIX;
00223   }
00224 
00225   template<class View, bool shared>
00226   ExecStatus
00227   Val<View,shared>::post(Home home, int n, ValInfo<View>* xy) {
00228     assert(n > 0);
00229     if (n == 1) {
00230       GECODE_ME_CHECK(xy[0].view.eq(home,0));
00231       GECODE_ME_CHECK(xy[1].view.eq(home,0));
00232       return ES_OK;
00233     }
00234     for (int i=2*n; i--; ) {
00235       GECODE_ME_CHECK(xy[i].view.gq(home,0));
00236       GECODE_ME_CHECK(xy[i].view.le(home,n));
00237     }
00238     (void) new (home) Val<View,shared>(home,n,xy);
00239     return ES_OK;
00240   }
00241 
00242 }}}
00243 
00244 // STATISTICS: int-prop
00245