or.icc

00001 /*
00002  *  Main authors:
00003  *     Christian Schulte <schulte@gecode.org>
00004  *
00005  *  Copyright:
00006  *     Christian Schulte, 2004
00007  *
00008  *  Last modified:
00009  *     $Date: 2006-09-11 11:34:58 +0200 (Mon, 11 Sep 2006) $ by $Author: schulte $
00010  *     $Revision: 3646 $
00011  *
00012  *  This file is part of Gecode, the generic constraint
00013  *  development environment:
00014  *     http://www.gecode.org
00015  *
00016  *  See the file "LICENSE" for information on usage and
00017  *  redistribution of this file, and for a
00018  *     DISCLAIMER OF ALL WARRANTIES.
00019  *
00020  */
00021 
00022 namespace Gecode { namespace Int { namespace Bool {
00023 
00024   /*
00025    * Boolean disjunction propagator (true)
00026    *
00027    */
00028 
00029   template <class BVA, class BVB>
00030   forceinline
00031   OrTrue<BVA,BVB>::OrTrue(Space* home, BVA b0, BVB b1)
00032     : BoolBinary<BVA,BVB>(home,b0,b1) {}
00033 
00034   template <class BVA, class BVB>
00035   forceinline
00036   OrTrue<BVA,BVB>::OrTrue(Space* home, bool share, OrTrue<BVA,BVB>& p)
00037     : BoolBinary<BVA,BVB>(home,share,p) {}
00038 
00039   template <class BVA, class BVB>
00040   forceinline
00041   OrTrue<BVA,BVB>::OrTrue(Space* home, bool share, Propagator& p,
00042                               BVA b0, BVB b1)
00043     : BoolBinary<BVA,BVB>(home,share,p,b0,b1) {}
00044 
00045   template <class BVA, class BVB>
00046   inline ExecStatus
00047   OrTrue<BVA,BVB>::post(Space* home, BVA b0, BVB b1) {
00048     switch (bool_test(b0,b1)) {
00049     case BT_SAME:
00050       GECODE_ME_CHECK(b0.t_one(home));
00051       break;
00052     case BT_COMP:
00053       break;
00054     case BT_NONE:
00055       if (b0.zero()) {
00056         GECODE_ES_CHECK(b1.t_one(home));
00057       } else if (b1.zero()) {
00058         GECODE_ES_CHECK(b0.t_one(home));
00059       } else if (!b0.one() && !b1.one()) {
00060         (void) new (home) OrTrue<BVA,BVB>(home,b0,b1);
00061       }
00062       break;
00063     default: GECODE_NEVER;
00064     }
00065     return ES_OK;
00066   }
00067 
00068   template <class BVA, class BVB>
00069   Actor*
00070   OrTrue<BVA,BVB>::copy(Space* home, bool share) {
00071     return new (home) OrTrue<BVA,BVB>(home,share,*this);
00072   }
00073 
00074   template <class BVA, class BVB>
00075   ExecStatus
00076   OrTrue<BVA,BVB>::propagate(Space* home) {
00077     if (x0.zero()) {
00078       GECODE_ME_CHECK(x1.t_one(home));
00079     } else if (x1.zero()) {
00080       GECODE_ME_CHECK(x0.t_one(home));
00081     } else {
00082       assert(x0.one() || x1.one());
00083     }
00084     return ES_SUBSUMED;
00085   }
00086 
00087 
00088   /*
00089    * Boolean disjunction propagator
00090    *
00091    */
00092 
00093   template <class BVA, class BVB, class BVC>
00094   forceinline
00095   Or<BVA,BVB,BVC>::Or(Space* home, BVA b0, BVB b1, BVC b2)
00096     : BoolTernary<BVA,BVB,BVC>(home,b0,b1,b2) {}
00097 
00098   template <class BVA, class BVB, class BVC>
00099   forceinline
00100   Or<BVA,BVB,BVC>::Or(Space* home, bool share, Or<BVA,BVB,BVC>& p)
00101     : BoolTernary<BVA,BVB,BVC>(home,share,p) {}
00102 
00103   template <class BVA, class BVB, class BVC>
00104   forceinline
00105   Or<BVA,BVB,BVC>::Or(Space* home, bool share, Propagator& p,
00106                         BVA b0, BVB b1, BVC b2)
00107     : BoolTernary<BVA,BVB,BVC>(home,share,p,b0,b1,b2) {}
00108 
00109   template <class BVA, class BVB, class BVC>
00110   inline ExecStatus
00111   Or<BVA,BVB,BVC>::post(Space* home, BVA b0, BVB b1, BVC b2) {
00112     if (b2.zero()) {
00113       GECODE_ME_CHECK(b0.t_zero(home));
00114       GECODE_ME_CHECK(b1.t_zero(home));
00115     } else if (b2.one()) {
00116       return OrTrue<BVA,BVB>::post(home,b0,b1);
00117     } else {
00118       switch (bool_test(b0,b1)) {
00119       case BT_SAME:
00120         return Eq<BVA,BVC>::post(home,b0,b2);
00121       case BT_COMP:
00122         GECODE_ME_CHECK(b2.t_one(home));
00123         break;
00124       case BT_NONE:
00125         if (b0.one() || b1.one()) {
00126           GECODE_ME_CHECK(b2.t_one(home));
00127         } else if (b0.zero()) {
00128           return Eq<BVB,BVC>::post(home,b1,b2);
00129         } else if (b1.zero()) {
00130           return Eq<BVA,BVC>::post(home,b0,b2);
00131         } else {
00132           (void) new (home) Or<BVA,BVB,BVC>(home,b0,b1,b2);
00133         }
00134         break;
00135       default: GECODE_NEVER;
00136       }
00137     }
00138     return ES_OK;
00139   }
00140 
00141   template <class BVA, class BVB, class BVC>
00142   Actor*
00143   Or<BVA,BVB,BVC>::copy(Space* home, bool share) {
00144     return new (home) Or<BVA,BVB,BVC>(home,share,*this);
00145   }
00146 
00147   template <class BVA, class BVB, class BVC>
00148   ExecStatus
00149   Or<BVA,BVB,BVC>::propagate(Space* home) {
00150     if (x0.one() || x1.one()) {
00151       GECODE_ES_CHECK(x2.t_one(home));
00152     } else if (x2.zero()) {
00153       GECODE_ES_CHECK(x0.t_zero(home));
00154       GECODE_ES_CHECK(x1.t_zero(home));
00155     } else if (x2.one()) {
00156       if (x0.zero()) {
00157         GECODE_ES_CHECK(x1.t_one(home));
00158       } else if (x1.zero()) {
00159         GECODE_ES_CHECK(x0.t_one(home));
00160       } else {
00161         return ES_FIX;
00162       } 
00163     } else if (x0.zero() && x1.zero()) {
00164       GECODE_ES_CHECK(x2.t_zero(home));
00165     } else {
00166       return ES_FIX;
00167     }
00168     return ES_SUBSUMED;
00169   }
00170 
00171 
00172 
00173   /*
00174    * N-ary Boolean disjunction propagator (true)
00175    *
00176    */
00177 
00178   template<class View>
00179   forceinline
00180   NaryOrTrue<View>::NaryOrTrue(Space* home, ViewArray<View>& b)
00181     : BinaryPropagator<View,PC_INT_VAL>(home,
00182                                         b[b.size()-2],
00183                                         b[b.size()-1]), x(b) {
00184     assert(x.size() > 2);
00185     x.size(x.size()-2);
00186   }
00187 
00188   template<class View>
00189   PropCost
00190   NaryOrTrue<View>::cost(void) const {
00191     return cost_lo(x.size(),PC_LINEAR_LO);
00192   }
00193 
00194   template<class View>
00195   forceinline
00196   NaryOrTrue<View>::NaryOrTrue(Space* home, bool share, NaryOrTrue<View>& p)
00197     : BinaryPropagator<View,PC_INT_VAL>(home,share,p), x(home,p.x.size()) {
00198     // Eliminate all zeros and all but one ones in original and update
00199     int n = p.x.size();
00200     for (int i=n; i--; )
00201       if (p.x[i].zero()) {
00202         n--; p.x[i]=p.x[n]; x[i]=x[n];
00203       } else if (p.x[i].one()) {
00204         x[i].update(home,share,p.x[i]);
00205         // Now eliminate all remaining zeros and ones
00206         while (i--)
00207           if (p.x[i].zero() || p.x[i].one()) {
00208             n--; p.x[i]=p.x[n]; x[i]=x[n];
00209           } else {
00210             x[i].update(home,share,p.x[i]);
00211           }
00212         goto done;
00213       } else {
00214         x[i].update(home,share,p.x[i]);
00215       }
00216     done:
00217     x.size(n); p.x.size(n);
00218   }
00219 
00220   template<class View>
00221   inline ExecStatus
00222   NaryOrTrue<View>::post(Space* home, ViewArray<View>& b) {
00223     for (int i=b.size(); i--; )
00224       if (b[i].one())
00225         return ES_OK;
00226       else if (b[i].zero())
00227         b.move_lst(i);
00228     if (b.size() == 0)
00229       return ES_FAILED;
00230     b.unique();
00231     if (b.size() == 1) {
00232       GECODE_ME_CHECK(b[0].t_one(home));
00233     } else if (b.size() == 2) {
00234       return OrTrue<View,View>::post(home,b[0],b[1]);
00235     } else {
00236       (void) new (home) NaryOrTrue(home,b);
00237     }
00238     return ES_OK;
00239   }
00240 
00241   template<class View>
00242   Actor*
00243   NaryOrTrue<View>::copy(Space* home, bool share) {
00244     return new (home) NaryOrTrue<View>(home,share,*this);
00245   }
00246 
00247   template<class View>
00248   forceinline ExecStatus
00249   NaryOrTrue<View>::resubscribe(Space* home, View& x0, View x1) {
00250     if (x0.zero()) {
00251       int n = x.size();
00252       for (int i=n; i--; )
00253         if (x[i].one()) {
00254           x.size(n);
00255           return ES_SUBSUMED;
00256         } else if (x[i].zero()) {
00257           x[i] = x[--n];
00258         } else {
00259           // New unassigned view found
00260           assert(!x[i].zero() && !x[i].one());
00261           // Rewrite if there is just one view left
00262           if (i == 0) {
00263             View y = x[0];
00264             x.size(0);
00265             GECODE_ES_CHECK((OrTrue<View,View>::post(home,x1,y)));
00266             return ES_SUBSUMED;
00267           }
00268           // Move to x0 and subscribe
00269           x0=x[i]; x[i]=x[--n]; 
00270           x.size(n);
00271           x0.subscribe(home,this,PC_INT_VAL,false);
00272           return ES_FIX;
00273         }
00274       // All views have been assigned!
00275       x.size(0);
00276       GECODE_ME_CHECK(x1.t_one(home));
00277       return ES_SUBSUMED;
00278     }
00279     return ES_FIX;
00280   }
00281 
00282   template<class View>
00283   ExecStatus
00284   NaryOrTrue<View>::propagate(Space* home) {
00285     if (x0.one() || x1.one())
00286       return ES_SUBSUMED;
00287     ExecStatus e = resubscribe(home,x0,x1);
00288     if (e != ES_FIX)
00289       return e;
00290     return resubscribe(home,x1,x0);
00291   }
00292 
00293 
00294   /*
00295    * N-ary Boolean disjunction propagator
00296    *
00297    */
00298 
00299   template<class View>
00300   forceinline
00301   NaryOr<View>::NaryOr(Space* home, ViewArray<View>& b, View c)
00302     : NaryOnePropagator<View,PC_INT_VAL>(home,b,c) {}
00303 
00304   template<class View>
00305   forceinline
00306   NaryOr<View>::NaryOr(Space* home, bool share, NaryOr<View>& p)
00307     : NaryOnePropagator<View,PC_INT_VAL>(home,share,p) {}
00308 
00309   template<class View>
00310   inline ExecStatus
00311   NaryOr<View>::post(Space* home, ViewArray<View>& b, View c) {
00312     if (c.one())
00313       return NaryOrTrue<View>::post(home,b);
00314     if (c.zero()) {
00315       for (int i=b.size(); i--; )
00316         GECODE_ME_CHECK(b[i].t_zero(home));
00317       return ES_OK;
00318     }
00319     for (int i=b.size(); i--; )
00320       if (b[i].one()) {
00321         GECODE_ME_CHECK(c.t_one(home));
00322         return ES_OK;
00323       } else if (b[i].zero()) {
00324         b.move_lst(i);
00325       }
00326     if (b.size() == 0)
00327       return ES_FAILED;
00328     b.unique();
00329     if (b.size() == 1)
00330       return Eq<View,View>::post(home,b[0],c);
00331     if (b.size() == 2)
00332       return Or<View,View,View>::post(home,b[0],b[1],c);
00333     (void) new (home) NaryOr(home,b,c);
00334     return ES_OK;
00335   }
00336 
00337   template<class View>
00338   Actor*
00339   NaryOr<View>::copy(Space* home, bool share) {
00340     if (x.size() == 1)
00341       return new (home) Eq<View,View>(home,share,*this,
00342                                       x[0],y);
00343     if (x.size() == 2)
00344       return new (home) Or<View,View,View>(home,share,*this,
00345                                            x[0],x[1],y);
00346     return new (home) NaryOr<View>(home,share,*this);
00347   }
00348 
00349   template<class View>
00350   ExecStatus
00351   NaryOr<View>::propagate(Space* home) {
00352     if (y.zero()) {
00353       for (int i = x.size(); i--; )
00354         GECODE_ME_CHECK(x[i].t_zero(home));
00355       return ES_SUBSUMED;
00356     }
00357     if (y.one()) {
00358       GECODE_ES_CHECK(NaryOrTrue<View>::post(home,x));
00359       return ES_SUBSUMED;
00360     }
00361     for (int i = x.size(); i--; ) {
00362       if (x[i].one()) {
00363         y.t_one_none(home);
00364         return ES_SUBSUMED;
00365       }
00366       if (x[i].zero())
00367         x.move_lst(i);
00368     }
00369     if (x.size() == 0) {
00370       y.t_zero_none(home);
00371       return ES_SUBSUMED;
00372     }
00373     return ES_FIX;
00374   }
00375 
00376 
00377 }}}
00378 
00379 // STATISTICS: int-prop
00380