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