Generated on Mon Nov 30 23:53:33 2009 for Gecode by doxygen 1.6.1

cumulatives.cpp

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