Generated on Thu Jul 6 07:06:43 2006 for Gecode by doxygen 1.4.7

cumulatives.cc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Mikael Lagerkvist <lagerkvist@gecode.org>
00004  *
00005  *  Copyright:
00006  *     Mikael Lagerkvist, 2005
00007  *
00008  *  Last modified:
00009  *     $Date: 2006-04-11 15:58:37 +0200 (Tue, 11 Apr 2006) $ by $Author: tack $
00010  *     $Revision: 3188 $
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 #include "gecode/int/cumulatives.hh"
00023 
00024 #include "gecode/int/linear.hh"
00025 
00026 namespace Gecode {
00027 
00028   using namespace Int;
00029 
00030   namespace {
00031     ViewArray<IntView>
00032     make_view_array(Space *home, const IntVarArgs& in)
00033     {
00034       return ViewArray<IntView>(home, in);
00035     }
00036     
00037     ViewArray<ConstIntView>
00038     make_view_array(Space *home, const IntArgs& in)
00039     {
00040       ViewArray<ConstIntView> res(home, in.size());
00041       for (int i = in.size(); i--; ) {
00042         if(in[i] < Limits::Int::int_min ||
00043            in[i] > Limits::Int::int_max)
00044           throw new NumericalOverflow("Int::cumulatives");
00045         res[i] = ConstIntView(in[i]);
00046       }
00047       
00048       return res;
00049     }
00050     
00051     template<class In> class ViewType;
00052     
00053     template<>
00054     class ViewType<IntArgs> {
00055     public:
00056       typedef ConstIntView Result;
00057     };
00058     
00059     template<>
00060     class ViewType<IntVarArgs> {
00061     public:
00062       typedef IntView Result;
00063     };
00064 
00065     void
00066     sum(Space *home, const IntVar& s, const IntVar& d, const IntVar& e)
00067     {
00068       GECODE_AUTOARRAY(Linear::Term, t, 3);
00069       t[0].a= 1; t[0].x=s;
00070       t[1].a= 1; t[1].x=d;
00071       t[2].a=-1; t[2].x=e;
00072       Linear::post(home, t, 3, IRT_EQ, 0);
00073     }
00074     
00075     void
00076     sum(Space *home, const IntVar& s, int d, const IntVar& e)
00077     {
00078       GECODE_AUTOARRAY(Linear::Term, t, 2);
00079       t[0].a= 1; t[0].x=s;
00080       t[1].a=-1; t[1].x=e;
00081       Linear::post(home, t, 2, IRT_EQ, -d);
00082     }
00083 
00084     template <class Machine, class Duration, class Height>
00085     void
00086     post_cumulatives(Space* home, const Machine& machine, 
00087                      const IntVarArgs& start, const Duration& duration, 
00088                      const IntVarArgs& end, const Height& height, 
00089                      const IntArgs& limit, bool at_most, 
00090                      IntConLevel cl) {
00091       if (home->failed()) return;
00092       
00093       if(machine.size() != start.size()  || 
00094          start.size() != duration.size() || 
00095          duration.size() != end.size()   || 
00096          end.size() != height.size())
00097         throw new ArgumentSizeMismatch("Int::cumulatives");
00098       
00099       ViewArray<typename ViewType<Machine>::Result> 
00100         vmachine  = make_view_array(home,  machine);
00101       ViewArray<typename ViewType<Duration>::Result> 
00102         vduration = make_view_array(home, duration);
00103       ViewArray<typename ViewType<Height>::Result> 
00104         vheight   = make_view_array(home,   height);
00105       ViewArray<IntView>
00106         vstart    = make_view_array(home,    start),
00107         vend      = make_view_array(home,      end);
00108       
00109       // There is only the value-consistent propagator for this constraint
00110       if(Cumulatives::Val<
00111          typename ViewType<Machine>::Result,
00112          typename ViewType<Duration>::Result,
00113          typename ViewType<Height>::Result,
00114          IntView>::post(home, vmachine,vstart, vduration, vend, vheight,
00115                         limit, at_most) == ::Gecode::ES_FAILED) {
00116         home->fail();
00117         return;
00118       }
00119       
00120       // By definition, s+d=e should hold.
00121       // We enforce this using basic linear constraints, since the
00122       // sweep-algorithm does not check for it.
00123       for (int i = start.size(); i--; ) {
00124         sum(home, start[i], duration[i], end[i]);
00125       }
00126     }
00127   }
00128 
00129 
00130   void
00131   cumulatives(Space* home, const IntVarArgs& machine, 
00132               const IntVarArgs& start, const IntVarArgs& duration, 
00133               const IntVarArgs& end, const IntVarArgs& height, 
00134               const IntArgs& limit, bool at_most, 
00135               IntConLevel cl) {
00136     post_cumulatives(home, machine, start, duration, end, 
00137                      height, limit, at_most, cl);
00138   }
00139 
00140   void
00141   cumulatives(Space* home, const IntArgs& machine, 
00142               const IntVarArgs& start, const IntVarArgs& duration, 
00143               const IntVarArgs& end, const IntVarArgs& height, 
00144               const IntArgs& limit, bool at_most, 
00145               IntConLevel cl) {
00146     post_cumulatives(home, machine, start, duration, end, 
00147                      height, limit, at_most, cl);
00148   }
00149 
00150   void
00151   cumulatives(Space* home, const IntVarArgs& machine, 
00152               const IntVarArgs& start, const IntArgs& duration, 
00153               const IntVarArgs& end, const IntVarArgs& height, 
00154               const IntArgs& limit, bool at_most, 
00155               IntConLevel cl) {
00156     post_cumulatives(home, machine, start, duration, end, 
00157                      height, limit, at_most, cl);
00158   }
00159 
00160   void
00161   cumulatives(Space* home, const IntArgs& machine, 
00162               const IntVarArgs& start, const IntArgs& duration, 
00163               const IntVarArgs& end, const IntVarArgs& height, 
00164               const IntArgs& limit, bool at_most, 
00165               IntConLevel cl) {
00166     post_cumulatives(home, machine, start, duration, end, 
00167                      height, limit, at_most, cl);
00168   }
00169 
00170   void
00171   cumulatives(Space* home, const IntVarArgs& machine, 
00172               const IntVarArgs& start, const IntVarArgs& duration, 
00173               const IntVarArgs& end, const IntArgs& height, 
00174               const IntArgs& limit, bool at_most, 
00175               IntConLevel cl) {
00176     post_cumulatives(home, machine, start, duration, end, 
00177                      height, limit, at_most, cl);
00178   }
00179 
00180   void
00181   cumulatives(Space* home, const IntArgs& machine, 
00182               const IntVarArgs& start, const IntVarArgs& duration, 
00183               const IntVarArgs& end, const IntArgs& height, 
00184               const IntArgs& limit, bool at_most, 
00185               IntConLevel cl) {
00186     post_cumulatives(home, machine, start, duration, end, 
00187                      height, limit, at_most, cl);
00188   }
00189 
00190   void
00191   cumulatives(Space* home, const IntVarArgs& machine, 
00192               const IntVarArgs& start, const IntArgs& duration, 
00193               const IntVarArgs& end, const IntArgs& height, 
00194               const IntArgs& limit, bool at_most, 
00195               IntConLevel cl) {
00196     post_cumulatives(home, machine, start, duration, end, 
00197                      height, limit, at_most, cl);
00198   }
00199 
00200   void
00201   cumulatives(Space* home, const IntArgs& machine, 
00202               const IntVarArgs& start, const IntArgs& duration, 
00203               const IntVarArgs& end, const IntArgs& height, 
00204               const IntArgs& limit, bool at_most, 
00205               IntConLevel cl) {
00206     post_cumulatives(home, machine, start, duration, end, 
00207                      height, limit, at_most, cl);
00208   }
00209 
00210 }
00211 
00212 // STATISTICS: int-post
00213