cumulative.cpp

00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *     Guido Tack <tack@gecode.org>
00006  *
00007  *  Copyright:
00008  *     Christian Schulte, 2009
00009  *     Guido Tack, 2010
00010  *
00011  *  This file is part of Gecode, the generic constraint
00012  *  development environment:
00013  *     http://www.gecode.org
00014  *
00015  *  Permission is hereby granted, free of charge, to any person obtaining
00016  *  a copy of this software and associated documentation files (the
00017  *  "Software"), to deal in the Software without restriction, including
00018  *  without limitation the rights to use, copy, modify, merge, publish,
00019  *  distribute, sublicense, and/or sell copies of the Software, and to
00020  *  permit persons to whom the Software is furnished to do so, subject to
00021  *  the following conditions:
00022  *
00023  *  The above copyright notice and this permission notice shall be
00024  *  included in all copies or substantial portions of the Software.
00025  *
00026  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00027  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00028  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00029  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00030  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00031  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00032  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00033  *
00034  */
00035 
00036 #include <gecode/int/cumulative.hh>
00037 
00038 #include <algorithm>
00039 
00040 namespace Gecode { namespace Int { namespace Cumulative {
00041 
00042   template<class Cap>
00043   void
00044   cumulative(Home home, Cap c, const TaskTypeArgs& t,
00045              const IntVarArgs& s, const IntArgs& p, const IntArgs& u,
00046              IntPropLevel ipl) {
00047     if ((s.size() != p.size()) || (s.size() != u.size()) ||
00048         (s.size() != t.size()))
00049       throw ArgumentSizeMismatch("Int::cumulative");
00050     long long int w = 0;
00051     for (int i=p.size(); i--; ) {
00052       Limits::nonnegative(p[i],"Int::cumulative");
00053       Limits::nonnegative(u[i],"Int::cumulative");
00054       Limits::check(static_cast<long long int>(s[i].max()) + p[i],
00055                     "Int::cumulative");
00056       mul_check(p[i],u[i]);
00057       w += s[i].width();
00058     }
00059     mul_check(c.max(),w,s.size());
00060     GECODE_POST;
00061 
00062     int minU = INT_MAX; int minU2 = INT_MAX; int maxU = INT_MIN;
00063     for (int i=u.size(); i--;) {
00064       if (u[i] < minU) {
00065         minU2 = minU;
00066         minU = u[i];
00067       } else if (u[i] < minU2)
00068         minU2 = u[i];
00069       if (u[i] > maxU)
00070         maxU = u[i];
00071     }
00072     bool disjunctive =
00073       (minU > c.max()/2) || (minU2 > c.max()/2 && minU+minU2>c.max());
00074     if (disjunctive) {
00075       GECODE_ME_FAIL(c.gq(home,maxU));
00076       unary(home,t,s,p,ipl);
00077     } else {
00078       bool fixp = true;
00079       for (int i=t.size(); i--;)
00080         if (t[i] != TT_FIXP) {
00081           fixp = false; break;
00082         }
00083       int nonOptionals = 0;
00084       for (int i=u.size(); i--;)
00085         if (u[i]>0) nonOptionals++;
00086       if (fixp) {
00087         TaskArray<ManFixPTask> tasks(home,nonOptionals);
00088         int cur = 0;
00089         for (int i=0; i<s.size(); i++)
00090           if (u[i] > 0)
00091             tasks[cur++].init(s[i],p[i],u[i]);
00092         GECODE_ES_FAIL(manpost(home,c,tasks,ipl));
00093       } else {
00094         TaskArray<ManFixPSETask> tasks(home,nonOptionals);
00095         int cur = 0;
00096         for (int i=s.size(); i--;)
00097           if (u[i] > 0)
00098             tasks[cur++].init(t[i],s[i],p[i],u[i]);
00099         GECODE_ES_FAIL(manpost(home,c,tasks,ipl));
00100       }
00101     }
00102   }
00103 
00104   template<class Cap>
00105   void
00106   cumulative(Home home, Cap c, const TaskTypeArgs& t,
00107              const IntVarArgs& s, const IntArgs& p, const IntArgs& u,
00108              const BoolVarArgs& m, IntPropLevel ipl) {
00109     using namespace Gecode::Int;
00110     using namespace Gecode::Int::Cumulative;
00111     if ((s.size() != p.size()) || (s.size() != u.size()) ||
00112         (s.size() != t.size()) || (s.size() != m.size()))
00113       throw Int::ArgumentSizeMismatch("Int::cumulative");
00114     long long int w = 0;
00115     for (int i=p.size(); i--; ) {
00116       Limits::nonnegative(p[i],"Int::cumulative");
00117       Limits::nonnegative(u[i],"Int::cumulative");
00118       Limits::check(static_cast<long long int>(s[i].max()) + p[i],
00119                     "Int::cumulative");
00120       mul_check(p[i],u[i]);
00121       w += s[i].width();
00122     }
00123     mul_check(c.max(),w,s.size());
00124     GECODE_POST;
00125 
00126     bool allMandatory = true;
00127     for (int i=m.size(); i--;) {
00128       if (!m[i].one()) {
00129         allMandatory = false;
00130         break;
00131       }
00132     }
00133     if (allMandatory) {
00134       cumulative(home,c,t,s,p,u,ipl);
00135     } else {
00136       bool fixp = true;
00137       for (int i=t.size(); i--;)
00138         if (t[i] != TT_FIXP) {
00139           fixp = false; break;
00140         }
00141       int nonOptionals = 0;
00142       for (int i=u.size(); i--;)
00143         if (u[i]>0) nonOptionals++;
00144       if (fixp) {
00145         TaskArray<OptFixPTask> tasks(home,nonOptionals);
00146         int cur = 0;
00147         for (int i=0; i<s.size(); i++)
00148           if (u[i]>0)
00149             tasks[cur++].init(s[i],p[i],u[i],m[i]);
00150         GECODE_ES_FAIL(optpost(home,c,tasks,ipl));
00151       } else {
00152         TaskArray<OptFixPSETask> tasks(home,nonOptionals);
00153         int cur = 0;
00154         for (int i=s.size(); i--;)
00155           if (u[i]>0)
00156             tasks[cur++].init(t[i],s[i],p[i],u[i],m[i]);
00157         GECODE_ES_FAIL(optpost(home,c,tasks,ipl));
00158       }
00159     }
00160   }
00161 
00162   template<class Cap>
00163   void
00164   cumulative(Home home, Cap c, const IntVarArgs& s,
00165              const IntArgs& p, const IntArgs& u, IntPropLevel ipl) {
00166     using namespace Gecode::Int;
00167     using namespace Gecode::Int::Cumulative;
00168     if ((s.size() != p.size()) || (s.size() != u.size()))
00169       throw Int::ArgumentSizeMismatch("Int::cumulative");
00170     long long int w = 0;
00171     for (int i=p.size(); i--; ) {
00172       Limits::nonnegative(p[i],"Int::cumulative");
00173       Limits::nonnegative(u[i],"Int::cumulative");
00174       Limits::check(static_cast<long long int>(s[i].max()) + p[i],
00175                     "Int::cumulative");
00176       mul_check(p[i],u[i]);
00177       w += s[i].width();
00178     }
00179     mul_check(c.max(),w,s.size());
00180     GECODE_POST;
00181 
00182     int minU = INT_MAX; int minU2 = INT_MAX; int maxU = INT_MIN;
00183     for (int i=u.size(); i--;) {
00184       if (u[i] < minU) {
00185         minU2 = minU;
00186         minU = u[i];
00187       } else if (u[i] < minU2)
00188         minU2 = u[i];
00189       if (u[i] > maxU)
00190         maxU = u[i];
00191     }
00192     bool disjunctive =
00193       (minU > c.max()/2) || (minU2 > c.max()/2 && minU+minU2>c.max());
00194     if (disjunctive) {
00195       GECODE_ME_FAIL(c.gq(home,maxU));
00196       unary(home,s,p,ipl);
00197     } else {
00198       int nonOptionals = 0;
00199       for (int i=u.size(); i--;)
00200         if (u[i]>0) nonOptionals++;
00201       TaskArray<ManFixPTask> t(home,nonOptionals);
00202       int cur = 0;
00203       for (int i=0; i<s.size(); i++)
00204         if (u[i]>0)
00205           t[cur++].init(s[i],p[i],u[i]);
00206       GECODE_ES_FAIL(manpost(home,c,t,ipl));
00207     }
00208   }
00209 
00210   template<class Cap>
00211   void
00212   cumulative(Home home, Cap c, const IntVarArgs& s, const IntArgs& p,
00213              const IntArgs& u, const BoolVarArgs& m, IntPropLevel ipl) {
00214     using namespace Gecode::Int;
00215     using namespace Gecode::Int::Cumulative;
00216     if ((s.size() != p.size()) || (s.size() != u.size()) ||
00217         (s.size() != m.size()))
00218       throw Int::ArgumentSizeMismatch("Int::cumulative");
00219     long long int w = 0;
00220     for (int i=p.size(); i--; ) {
00221       Limits::nonnegative(p[i],"Int::cumulative");
00222       Limits::nonnegative(u[i],"Int::cumulative");
00223       Limits::check(static_cast<long long int>(s[i].max()) + p[i],
00224                     "Int::cumulative");
00225       mul_check(p[i],u[i]);
00226       w += s[i].width();
00227     }
00228     mul_check(c.max(),w,s.size());
00229     GECODE_POST;
00230 
00231     bool allMandatory = true;
00232     for (int i=m.size(); i--;) {
00233       if (!m[i].one()) {
00234         allMandatory = false;
00235         break;
00236       }
00237     }
00238     if (allMandatory) {
00239       cumulative(home,c,s,p,u,ipl);
00240     } else {
00241       int nonOptionals = 0;
00242       for (int i=u.size(); i--;)
00243         if (u[i]>0) nonOptionals++;
00244       TaskArray<OptFixPTask> t(home,nonOptionals);
00245       int cur = 0;
00246       for (int i=0; i<s.size(); i++)
00247         if (u[i]>0)
00248           t[cur++].init(s[i],p[i],u[i],m[i]);
00249       GECODE_ES_FAIL(optpost(home,c,t,ipl));
00250     }
00251   }
00252 
00253   template<class Cap>
00254   void
00255   cumulative(Home home, Cap c, const IntVarArgs& s,
00256              const IntVarArgs& p, const IntVarArgs& e,
00257              const IntArgs& u, IntPropLevel ipl) {
00258     using namespace Gecode::Int;
00259     using namespace Gecode::Int::Cumulative;
00260     if ((s.size() != p.size()) || (s.size() != e.size()) ||
00261         (s.size() != u.size()))
00262       throw Int::ArgumentSizeMismatch("Int::cumulative");
00263     long long int w = 0;
00264     for (int i=p.size(); i--; ) {
00265       rel(home, p[i], IRT_GQ, 0);
00266     }
00267     for (int i=p.size(); i--; ) {
00268       Limits::nonnegative(u[i],"Int::cumulative");
00269       Limits::check(static_cast<long long int>(s[i].max()) + p[i].max(),
00270                     "Int::cumulative");
00271       mul_check(p[i].max(),u[i]);
00272       w += s[i].width();
00273     }
00274     mul_check(c.max(),w,s.size());
00275     GECODE_POST;
00276 
00277     bool fixP = true;
00278     for (int i=p.size(); i--;) {
00279       if (!p[i].assigned()) {
00280         fixP = false;
00281         break;
00282       }
00283     }
00284     if (fixP) {
00285       IntArgs pp(p.size());
00286       for (int i=p.size(); i--;)
00287         pp[i] = p[i].val();
00288       cumulative(home,c,s,pp,u,ipl);
00289     } else {
00290       int nonOptionals = 0;
00291       for (int i=u.size(); i--;)
00292         if (u[i]>0) nonOptionals++;
00293       TaskArray<ManFlexTask> t(home,nonOptionals);
00294       int cur = 0;
00295       for (int i=0; i<s.size(); i++)
00296         if (u[i]>0)
00297           t[cur++].init(s[i],p[i],e[i],u[i]);
00298       GECODE_ES_FAIL(manpost(home,c,t,ipl));
00299     }
00300   }
00301 
00302   template<class Cap>
00303   void
00304   cumulative(Home home, Cap c, const IntVarArgs& s, const IntVarArgs& p,
00305              const IntVarArgs& e, const IntArgs& u, const BoolVarArgs& m,
00306              IntPropLevel ipl) {
00307     using namespace Gecode::Int;
00308     using namespace Gecode::Int::Cumulative;
00309     if ((s.size() != p.size()) || (s.size() != u.size()) ||
00310         (s.size() != e.size()) || (s.size() != m.size()))
00311       throw Int::ArgumentSizeMismatch("Int::cumulative");
00312     for (int i=p.size(); i--; ) {
00313       rel(home, p[i], IRT_GQ, 0);
00314     }
00315     long long int w = 0;
00316     for (int i=p.size(); i--; ) {
00317       Limits::nonnegative(u[i],"Int::cumulative");
00318       Limits::check(static_cast<long long int>(s[i].max()) + p[i].max(),
00319                     "Int::cumulative");
00320       mul_check(p[i].max(),u[i]);
00321       w += s[i].width();
00322     }
00323     mul_check(c.max(),w,s.size());
00324     GECODE_POST;
00325 
00326     bool allMandatory = true;
00327     for (int i=m.size(); i--;) {
00328       if (!m[i].one()) {
00329         allMandatory = false;
00330         break;
00331       }
00332     }
00333     if (allMandatory) {
00334       cumulative(home,c,s,p,e,u,ipl);
00335     } else {
00336       int nonOptionals = 0;
00337       for (int i=u.size(); i--;)
00338         if (u[i]>0) nonOptionals++;
00339       TaskArray<OptFlexTask> t(home,nonOptionals);
00340       int cur = 0;
00341       for (int i=s.size(); i--; )
00342         if (u[i]>0)
00343           t[cur++].init(s[i],p[i],e[i],u[i],m[i]);
00344       GECODE_ES_FAIL(optpost(home,c,t,ipl));
00345     }
00346   }
00347 
00348 }}}
00349 
00350 namespace Gecode {
00351 
00352   void
00353   cumulative(Home home, int c, const TaskTypeArgs& t,
00354              const IntVarArgs& s, const IntArgs& p, const IntArgs& u,
00355              IntPropLevel ipl) {
00356     Int::Limits::nonnegative(c,"Int::cumulative");
00357     Int::Cumulative::cumulative(home,Int::ConstIntView(c),t,s,p,u,ipl);
00358   }
00359 
00360   void
00361   cumulative(Home home, IntVar c, const TaskTypeArgs& t,
00362              const IntVarArgs& s, const IntArgs& p, const IntArgs& u,
00363              IntPropLevel ipl) {
00364     if (c.assigned())
00365       cumulative(home,c.val(),t,s,p,u,ipl);
00366     else
00367       Int::Cumulative::cumulative(home,Int::IntView(c),t,s,p,u,ipl);
00368   }
00369 
00370 
00371   void
00372   cumulative(Home home, int c, const TaskTypeArgs& t,
00373              const IntVarArgs& s, const IntArgs& p, const IntArgs& u,
00374              const BoolVarArgs& m, IntPropLevel ipl) {
00375     Int::Limits::nonnegative(c,"Int::cumulative");
00376     Int::Cumulative::cumulative(home,Int::ConstIntView(c),t,s,p,u,m,ipl);
00377   }
00378 
00379   void
00380   cumulative(Home home, IntVar c, const TaskTypeArgs& t,
00381              const IntVarArgs& s, const IntArgs& p, const IntArgs& u,
00382              const BoolVarArgs& m, IntPropLevel ipl) {
00383     if (c.assigned())
00384       cumulative(home,c.val(),t,s,p,u,m,ipl);
00385     else
00386       Int::Cumulative::cumulative(home,Int::IntView(c),t,s,p,u,m,ipl);
00387   }
00388 
00389 
00390   void
00391   cumulative(Home home, int c, const IntVarArgs& s,
00392              const IntArgs& p, const IntArgs& u, IntPropLevel ipl) {
00393     Int::Limits::nonnegative(c,"Int::cumulative");
00394     Int::Cumulative::cumulative(home,Int::ConstIntView(c),s,p,u,ipl);
00395   }
00396 
00397   void
00398   cumulative(Home home, IntVar c, const IntVarArgs& s,
00399              const IntArgs& p, const IntArgs& u, IntPropLevel ipl) {
00400     if (c.assigned())
00401       cumulative(home,c.val(),s,p,u,ipl);
00402     else
00403       Int::Cumulative::cumulative(home,Int::IntView(c),s,p,u,ipl);
00404   }
00405 
00406 
00407   void
00408   cumulative(Home home, int c, const IntVarArgs& s, const IntArgs& p,
00409              const IntArgs& u, const BoolVarArgs& m, IntPropLevel ipl) {
00410     Int::Limits::nonnegative(c,"Int::cumulative");
00411     Int::Cumulative::cumulative(home,Int::ConstIntView(c),s,p,u,m,ipl);
00412   }
00413 
00414   void
00415   cumulative(Home home, IntVar c, const IntVarArgs& s, const IntArgs& p,
00416              const IntArgs& u, const BoolVarArgs& m, IntPropLevel ipl) {
00417     if (c.assigned())
00418       cumulative(home,c.val(),s,p,u,m,ipl);
00419     else
00420       Int::Cumulative::cumulative(home,Int::IntView(c),s,p,u,m,ipl);
00421   }
00422 
00423 
00424   void
00425   cumulative(Home home, int c, const IntVarArgs& s,
00426              const IntVarArgs& p, const IntVarArgs& e,
00427              const IntArgs& u, IntPropLevel ipl) {
00428     Int::Limits::nonnegative(c,"Int::cumulative");
00429     Int::Cumulative::cumulative(home,Int::ConstIntView(c),s,p,e,u,ipl);
00430   }
00431 
00432   void
00433   cumulative(Home home, IntVar c, const IntVarArgs& s,
00434              const IntVarArgs& p, const IntVarArgs& e,
00435              const IntArgs& u, IntPropLevel ipl) {
00436     if (c.assigned())
00437       cumulative(home,c.val(),s,p,e,u,ipl);
00438     else
00439       Int::Cumulative::cumulative(home,Int::IntView(c),s,p,e,u,ipl);
00440   }
00441 
00442 
00443   void
00444   cumulative(Home home, int c, const IntVarArgs& s, const IntVarArgs& p,
00445              const IntVarArgs& e, const IntArgs& u, const BoolVarArgs& m,
00446              IntPropLevel ipl) {
00447     Int::Limits::nonnegative(c,"Int::cumulative");
00448     Int::Cumulative::cumulative(home,Int::ConstIntView(c),s,p,e,u,m,ipl);
00449   }
00450 
00451   void
00452   cumulative(Home home, IntVar c, const IntVarArgs& s, const IntVarArgs& p,
00453              const IntVarArgs& e, const IntArgs& u, const BoolVarArgs& m,
00454              IntPropLevel ipl) {
00455     if (c.assigned())
00456       cumulative(home,c.val(),s,p,e,u,m,ipl);
00457     else
00458       Int::Cumulative::cumulative(home,Int::IntView(c),s,p,e,u,m,ipl);
00459   }
00460 
00461 }
00462 
00463 // STATISTICS: int-post