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=0; 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=0; 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=0; i<t.size(); i++)
00080         if (t[i] != TT_FIXP) {
00081           fixp = false; break;
00082         }
00083       int nonOptionals = 0;
00084       for (int i=0; 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=0; 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=0; 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=0; 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=0; i<t.size(); i++)
00138         if (t[i] != TT_FIXP) {
00139           fixp = false; break;
00140         }
00141       int nonOptionals = 0;
00142       for (int i=0; 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=0; 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=0; 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=0; 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=0; 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=0; 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=0; 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=0; 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=0; i<p.size(); i++) {
00265       Limits::nonnegative(u[i],"Int::cumulative");
00266       Limits::check(static_cast<long long int>(s[i].max()) + p[i].max(),
00267                     "Int::cumulative");
00268       mul_check(p[i].max(),u[i]);
00269       w += s[i].width();
00270     }
00271     mul_check(c.max(),w,s.size());
00272 
00273     GECODE_POST;
00274     for (int i=0; i<p.size(); i++)
00275       GECODE_ME_FAIL(IntView(p[i]).gq(home,0));
00276 
00277     bool fixP = true;
00278     for (int i=0; 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=0; 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=0; 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 
00313     long long int w = 0;
00314     for (int i=0; i<p.size(); i++) {
00315       Limits::nonnegative(u[i],"Int::cumulative");
00316       Limits::check(static_cast<long long int>(s[i].max()) + p[i].max(),
00317                     "Int::cumulative");
00318       mul_check(p[i].max(),u[i]);
00319       w += s[i].width();
00320     }
00321     mul_check(c.max(),w,s.size());
00322 
00323     GECODE_POST;
00324     for (int i=0; i<p.size(); i++)
00325       GECODE_ME_FAIL(IntView(p[i]).gq(home,0));
00326 
00327     bool allMandatory = true;
00328     for (int i=0; i<m.size(); i++) {
00329       if (!m[i].one()) {
00330         allMandatory = false;
00331         break;
00332       }
00333     }
00334     if (allMandatory) {
00335       cumulative(home,c,s,p,e,u,ipl);
00336     } else {
00337       int nonOptionals = 0;
00338       for (int i=0; i<u.size(); i++)
00339         if (u[i]>0) nonOptionals++;
00340       TaskArray<OptFlexTask> t(home,nonOptionals);
00341       int cur = 0;
00342       for (int i=0; i<s.size(); i++)
00343         if (u[i]>0)
00344           t[cur++].init(s[i],p[i],e[i],u[i],m[i]);
00345       GECODE_ES_FAIL(optpost(home,c,t,ipl));
00346     }
00347   }
00348 
00349 }}}
00350 
00351 namespace Gecode {
00352 
00353   void
00354   cumulative(Home home, int c, const TaskTypeArgs& t,
00355              const IntVarArgs& s, const IntArgs& p, const IntArgs& u,
00356              IntPropLevel ipl) {
00357     Int::Limits::nonnegative(c,"Int::cumulative");
00358     Int::Cumulative::cumulative(home,Int::ConstIntView(c),t,s,p,u,ipl);
00359   }
00360 
00361   void
00362   cumulative(Home home, IntVar c, const TaskTypeArgs& t,
00363              const IntVarArgs& s, const IntArgs& p, const IntArgs& u,
00364              IntPropLevel ipl) {
00365     if (c.assigned())
00366       cumulative(home,c.val(),t,s,p,u,ipl);
00367     else
00368       Int::Cumulative::cumulative(home,Int::IntView(c),t,s,p,u,ipl);
00369   }
00370 
00371 
00372   void
00373   cumulative(Home home, int c, const TaskTypeArgs& t,
00374              const IntVarArgs& s, const IntArgs& p, const IntArgs& u,
00375              const BoolVarArgs& m, IntPropLevel ipl) {
00376     Int::Limits::nonnegative(c,"Int::cumulative");
00377     Int::Cumulative::cumulative(home,Int::ConstIntView(c),t,s,p,u,m,ipl);
00378   }
00379 
00380   void
00381   cumulative(Home home, IntVar c, const TaskTypeArgs& t,
00382              const IntVarArgs& s, const IntArgs& p, const IntArgs& u,
00383              const BoolVarArgs& m, IntPropLevel ipl) {
00384     if (c.assigned())
00385       cumulative(home,c.val(),t,s,p,u,m,ipl);
00386     else
00387       Int::Cumulative::cumulative(home,Int::IntView(c),t,s,p,u,m,ipl);
00388   }
00389 
00390 
00391   void
00392   cumulative(Home home, int c, const IntVarArgs& s,
00393              const IntArgs& p, const IntArgs& u, IntPropLevel ipl) {
00394     Int::Limits::nonnegative(c,"Int::cumulative");
00395     Int::Cumulative::cumulative(home,Int::ConstIntView(c),s,p,u,ipl);
00396   }
00397 
00398   void
00399   cumulative(Home home, IntVar c, const IntVarArgs& s,
00400              const IntArgs& p, const IntArgs& u, IntPropLevel ipl) {
00401     if (c.assigned())
00402       cumulative(home,c.val(),s,p,u,ipl);
00403     else
00404       Int::Cumulative::cumulative(home,Int::IntView(c),s,p,u,ipl);
00405   }
00406 
00407 
00408   void
00409   cumulative(Home home, int c, const IntVarArgs& s, const IntArgs& p,
00410              const IntArgs& u, const BoolVarArgs& m, IntPropLevel ipl) {
00411     Int::Limits::nonnegative(c,"Int::cumulative");
00412     Int::Cumulative::cumulative(home,Int::ConstIntView(c),s,p,u,m,ipl);
00413   }
00414 
00415   void
00416   cumulative(Home home, IntVar c, const IntVarArgs& s, const IntArgs& p,
00417              const IntArgs& u, const BoolVarArgs& m, IntPropLevel ipl) {
00418     if (c.assigned())
00419       cumulative(home,c.val(),s,p,u,m,ipl);
00420     else
00421       Int::Cumulative::cumulative(home,Int::IntView(c),s,p,u,m,ipl);
00422   }
00423 
00424 
00425   void
00426   cumulative(Home home, int c, const IntVarArgs& s,
00427              const IntVarArgs& p, const IntVarArgs& e,
00428              const IntArgs& u, IntPropLevel ipl) {
00429     Int::Limits::nonnegative(c,"Int::cumulative");
00430     Int::Cumulative::cumulative(home,Int::ConstIntView(c),s,p,e,u,ipl);
00431   }
00432 
00433   void
00434   cumulative(Home home, IntVar c, const IntVarArgs& s,
00435              const IntVarArgs& p, const IntVarArgs& e,
00436              const IntArgs& u, IntPropLevel ipl) {
00437     if (c.assigned())
00438       cumulative(home,c.val(),s,p,e,u,ipl);
00439     else
00440       Int::Cumulative::cumulative(home,Int::IntView(c),s,p,e,u,ipl);
00441   }
00442 
00443 
00444   void
00445   cumulative(Home home, int c, const IntVarArgs& s, const IntVarArgs& p,
00446              const IntVarArgs& e, const IntArgs& u, const BoolVarArgs& m,
00447              IntPropLevel ipl) {
00448     Int::Limits::nonnegative(c,"Int::cumulative");
00449     Int::Cumulative::cumulative(home,Int::ConstIntView(c),s,p,e,u,m,ipl);
00450   }
00451 
00452   void
00453   cumulative(Home home, IntVar c, const IntVarArgs& s, const IntVarArgs& p,
00454              const IntVarArgs& e, const IntArgs& u, const BoolVarArgs& m,
00455              IntPropLevel ipl) {
00456     if (c.assigned())
00457       cumulative(home,c.val(),s,p,e,u,m,ipl);
00458     else
00459       Int::Cumulative::cumulative(home,Int::IntView(c),s,p,e,u,m,ipl);
00460   }
00461 
00462 }
00463 
00464 // STATISTICS: int-post