Generated on Wed Mar 19 07:29:56 2008 for Gecode by doxygen 1.5.5

max.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  *  Copyright:
00007  *     Christian Schulte, 2004
00008  *
00009  *  Last modified:
00010  *     $Date: 2008-01-31 18:29:16 +0100 (Thu, 31 Jan 2008) $ by $Author: tack $
00011  *     $Revision: 6017 $
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 #include "gecode/int/rel.hh"
00039 
00040 namespace Gecode { namespace Int { namespace Arithmetic {
00041 
00042   /*
00043    * Ternary bounds-consistent maximum
00044    *
00045    */
00046 
00047   template <class View>
00048   forceinline
00049   Max<View>::Max(Space* home, View x0, View x1, View x2)
00050     : TernaryPropagator<View,PC_INT_BND>(home,x0,x1,x2) {}
00051 
00052   template <class View>
00053   ExecStatus
00054   Max<View>::post(Space* home, View x0, View x1, View x2) {
00055     if (same(x0,x1))
00056       return Rel::EqBnd<View,View>::post(home,x0,x2);
00057     if (same(x0,x2))
00058       return Rel::Lq<View>::post(home,x1,x2);
00059     if (same(x1,x2))
00060       return Rel::Lq<View>::post(home,x0,x2);
00061     (void) new (home) Max<View>(home,x0,x1,x2);
00062     return ES_OK;
00063   }
00064 
00065   template <class View>
00066   forceinline void
00067   Max<View>::post(Space* home, Reflection::VarMap& vars,
00068                   const Reflection::ActorSpec& spec) {
00069      spec.checkArity(3);
00070      View x0(home, vars, spec[0]);
00071      View x1(home, vars, spec[1]);
00072      View x2(home, vars, spec[2]);
00073      (void) new (home) Max<View>(home,x0,x1,x2);
00074   }
00075 
00076   template <class View>
00077   forceinline
00078   Max<View>::Max(Space* home, bool share, Max<View>& p)
00079     : TernaryPropagator<View,PC_INT_BND>(home,share,p) {}
00080 
00081   template <class View>
00082   forceinline
00083   Max<View>::Max(Space* home, bool share, Propagator& p,
00084                  View x0, View x1, View x2)
00085     : TernaryPropagator<View,PC_INT_BND>(home,share,p,x0,x1,x2) {}
00086 
00087   template <class View>
00088   Actor*
00089   Max<View>::copy(Space* home, bool share) {
00090     return new (home) Max<View>(home,share,*this);
00091   }
00092 
00093   template <class View>
00094   ExecStatus
00095   Max<View>::propagate(Space* home, ModEventDelta) {
00096     bool mod = false;
00097     do {
00098       mod = false;
00099       {
00100         ModEvent me = x2.lq(home,std::max(x0.max(),x1.max()));
00101         if (me_failed(me)) return ES_FAILED;
00102         mod |= me_modified(me);
00103       }
00104       {
00105         ModEvent me = x2.gq(home,std::max(x0.min(),x1.min()));
00106         if (me_failed(me)) return ES_FAILED;
00107         mod |= me_modified(me);
00108       }
00109       {
00110         ModEvent me = x0.lq(home,x2.max());
00111         if (me_failed(me)) return ES_FAILED;
00112         mod |= me_modified(me);
00113       }
00114       {
00115         ModEvent me = x1.lq(home,x2.max());
00116         if (me_failed(me)) return ES_FAILED;
00117         mod |= me_modified(me);
00118       }
00119     } while (mod);
00120     if (x0.max() <= x1.min())
00121       GECODE_REWRITE(this,(Rel::EqBnd<View,View>::post(home,x1,x2)));
00122     if (x1.max() <= x0.min())
00123       GECODE_REWRITE(this,(Rel::EqBnd<View,View>::post(home,x0,x2)));
00124     return x0.assigned() && x1.assigned() && x2.assigned() ?
00125       ES_SUBSUMED(this,sizeof(*this)) : ES_FIX;
00126   }
00127 
00128   template <class View>
00129   Support::Symbol
00130   Max<View>::ati(void) {
00131     return Reflection::mangle<View>("Gecode::Int::Arithmetic::Max");
00132   }
00133 
00134   template <class View>
00135   Reflection::ActorSpec
00136   Max<View>::spec(const Space* home, Reflection::VarMap& m) const {
00137     return TernaryPropagator<View,PC_INT_BND>::spec(home, m, ati());
00138   }
00139 
00140   /*
00141    * Nary bounds-consistent maximum
00142    *
00143    */
00144 
00145   template <class View>
00146   forceinline
00147   NaryMax<View>::NaryMax(Space* home, ViewArray<View>& x, View y)
00148     : NaryOnePropagator<View,PC_INT_BND>(home,x,y) {}
00149 
00150   template <class View>
00151   ExecStatus
00152   NaryMax<View>::post(Space* home, ViewArray<View>& x, View y) {
00153     assert(x.size() > 0);
00154     x.unique();
00155     if (x.size() == 1)
00156       return Rel::EqBnd<View,View>::post(home,x[0],y);
00157     if (x.size() == 2)
00158       return Max<View>::post(home,x[0],x[1],y);
00159     if (x.same(y)) {
00160       // Check whether y occurs in x
00161       for (int i=x.size(); i--; )
00162         GECODE_ES_CHECK(Rel::Lq<View>::post(home,x[i],y));
00163     } else {
00164       (void) new (home) NaryMax<View>(home,x,y);
00165     }
00166     return ES_OK;
00167   }
00168 
00169   template <class View>
00170   forceinline void
00171   NaryMax<View>::post(Space* home, Reflection::VarMap& vars,
00172                       const Reflection::ActorSpec& spec) {
00173     spec.checkArity(2);
00174     ViewArray<View> x(home, vars, spec[0]);
00175     View y(home, vars, spec[1]);
00176     (void) new (home) NaryMax<View>(home,x,y);
00177   }
00178 
00179   template <class View>
00180   forceinline
00181   NaryMax<View>::NaryMax(Space* home, bool share, NaryMax<View>& p)
00182     : NaryOnePropagator<View,PC_INT_BND>(home,share,p) {}
00183 
00184   template <class View>
00185   Actor*
00186   NaryMax<View>::copy(Space* home, bool share) {
00187     if (x.size() == 1)
00188       return new (home) Rel::EqBnd<View,View>(home,share,*this,x[0],y);
00189     if (x.size() == 2)
00190       return new (home) Max<View>(home,share,*this,x[0],x[1],y);
00191     return new (home) NaryMax<View>(home,share,*this);
00192   }
00193 
00195   enum MaxPropStatus {
00196     MPS_ASSIGNED  = 1<<0, 
00197     MPS_REMOVED   = 1<<1, 
00198     MPS_NEW_BOUND = 1<<2  
00199   };
00200 
00201   template <class View>
00202   ExecStatus
00203   NaryMax<View>::propagate(Space* home, ModEventDelta) {
00204   rerun:
00205     assert(x.size() > 0);
00206     int maxmax = x[x.size()-1].max();
00207     int maxmin = x[x.size()-1].min();
00208     for (int i = x.size()-1; i--; ) {
00209       maxmax = std::max(x[i].max(),maxmax);
00210       maxmin = std::max(x[i].min(),maxmin);
00211     }
00212     GECODE_ME_CHECK(y.lq(home,maxmax));
00213     GECODE_ME_CHECK(y.gq(home,maxmin));
00214     maxmin = y.min();
00215     maxmax = y.max();
00216     int status = MPS_ASSIGNED;
00217     for (int i = x.size(); i--; ) {
00218       ModEvent me = x[i].lq(home,maxmax);
00219       if (me == ME_INT_FAILED)
00220         return ES_FAILED;
00221       if (me_modified(me) && (x[i].max() != maxmax))
00222         status |= MPS_NEW_BOUND;
00223       if (x[i].max() < maxmin) {
00224         x.move_lst(i,home,this,PC_INT_BND);
00225         status |= MPS_REMOVED;
00226       } else if (!x[i].assigned())
00227         status &= ~MPS_ASSIGNED;
00228     }
00229     if (x.size() == 0)
00230       return ES_FAILED;
00231     if ((status & MPS_REMOVED) != 0)
00232       goto rerun;
00233     if (((status & MPS_ASSIGNED) != 0) && y.assigned())
00234       return ES_SUBSUMED(this,sizeof(*this));
00235     return ((status & MPS_NEW_BOUND) != 0) ? ES_NOFIX : ES_FIX;
00236   }
00237 
00238   template <class View>
00239   Support::Symbol
00240   NaryMax<View>::ati(void) {
00241     return Reflection::mangle<View>("Gecode::Int::Arithmetic::NaryMax");
00242   }
00243 
00244   template <class View>
00245   Reflection::ActorSpec
00246   NaryMax<View>::spec(const Space* home, Reflection::VarMap& m) const {
00247     return NaryOnePropagator<View,PC_INT_BND>::spec(home, m, ati());
00248   }
00249 
00250 }}}
00251 
00252 // STATISTICS: int-prop
00253