Generated on Thu Apr 11 13:58:55 2019 for Gecode by doxygen 1.6.3

arithmetic.cpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2002
00008  *
00009  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00031  *
00032  */
00033 
00034 #include <gecode/int/arithmetic.hh>
00035 
00036 namespace Gecode {
00037 
00038   void
00039   abs(Home home, IntVar x0, IntVar x1, IntPropLevel ipl) {
00040     using namespace Int;
00041     GECODE_POST;
00042     if (vbd(ipl) == IPL_DOM) {
00043       GECODE_ES_FAIL(Arithmetic::AbsDom<IntView>::post(home,x0,x1));
00044     } else {
00045       GECODE_ES_FAIL(Arithmetic::AbsBnd<IntView>::post(home,x0,x1));
00046     }
00047   }
00048 
00049 
00050   void
00051   max(Home home, IntVar x0, IntVar x1, IntVar x2,
00052       IntPropLevel ipl) {
00053     using namespace Int;
00054     GECODE_POST;
00055     if (vbd(ipl) == IPL_DOM) {
00056       GECODE_ES_FAIL(Arithmetic::MaxDom<IntView>::post(home,x0,x1,x2));
00057     } else {
00058       GECODE_ES_FAIL(Arithmetic::MaxBnd<IntView>::post(home,x0,x1,x2));
00059     }
00060   }
00061 
00062   void
00063   max(Home home, const IntVarArgs& x, IntVar y,
00064       IntPropLevel ipl) {
00065     using namespace Int;
00066     if (x.size() == 0)
00067       throw TooFewArguments("Int::max");
00068     GECODE_POST;
00069     ViewArray<IntView> xv(home,x);
00070     if (vbd(ipl) == IPL_DOM) {
00071       GECODE_ES_FAIL(Arithmetic::NaryMaxDom<IntView>::post(home,xv,y));
00072     } else {
00073       GECODE_ES_FAIL(Arithmetic::NaryMaxBnd<IntView>::post(home,xv,y));
00074     }
00075   }
00076 
00077   void
00078   min(Home home, IntVar x0, IntVar x1, IntVar x2,
00079       IntPropLevel ipl) {
00080     using namespace Int;
00081     GECODE_POST;
00082     MinusView m0(x0); MinusView m1(x1); MinusView m2(x2);
00083     if (vbd(ipl) == IPL_DOM) {
00084       GECODE_ES_FAIL(Arithmetic::MaxDom<MinusView>::post(home,m0,m1,m2));
00085     } else {
00086       GECODE_ES_FAIL(Arithmetic::MaxBnd<MinusView>::post(home,m0,m1,m2));
00087     }
00088   }
00089 
00090   void
00091   min(Home home, const IntVarArgs& x, IntVar y,
00092       IntPropLevel ipl) {
00093     using namespace Int;
00094     if (x.size() == 0)
00095       throw TooFewArguments("Int::min");
00096     GECODE_POST;
00097     ViewArray<MinusView> m(home,x.size());
00098     for (int i=0; i<x.size(); i++)
00099       m[i] = MinusView(x[i]);
00100     MinusView my(y);
00101     if (vbd(ipl) == IPL_DOM) {
00102       GECODE_ES_FAIL(Arithmetic::NaryMaxDom<MinusView>::post(home,m,my));
00103     } else {
00104       GECODE_ES_FAIL(Arithmetic::NaryMaxBnd<MinusView>::post(home,m,my));
00105     }
00106   }
00107 
00108 
00109   void
00110   argmax(Home home, const IntVarArgs& x, IntVar y, bool tiebreak,
00111          IntPropLevel) {
00112     using namespace Int;
00113     if (x.size() == 0)
00114       throw TooFewArguments("Int::argmax");
00115     if (same(x,y))
00116       throw ArgumentSame("Int::argmax");
00117     GECODE_POST;
00118     // Constrain y properly
00119     IntView yv(y);
00120     GECODE_ME_FAIL(yv.gq(home,0));
00121     GECODE_ME_FAIL(yv.le(home,x.size()));
00122     // Construct index view array
00123     IdxViewArray<IntView> ix(home,x.size());
00124     for (int i=0; i<x.size(); i++) {
00125       ix[i].idx=i; ix[i].view=x[i];
00126     }
00127     if (tiebreak)
00128         GECODE_ES_FAIL((Arithmetic::ArgMax<IntView,IntView,true>
00129                         ::post(home,ix,yv)));
00130     else
00131         GECODE_ES_FAIL((Arithmetic::ArgMax<IntView,IntView,false>
00132                         ::post(home,ix,yv)));
00133   }
00134 
00135   void
00136   argmax(Home home, const IntVarArgs& x, int o, IntVar y, bool tiebreak,
00137          IntPropLevel) {
00138     using namespace Int;
00139     Limits::nonnegative(o,"Int::argmax");
00140     if (x.size() == 0)
00141       throw TooFewArguments("Int::argmax");
00142     if (same(x,y))
00143       throw ArgumentSame("Int::argmax");
00144     GECODE_POST;
00145     // Constrain y properly
00146     OffsetView yv(y,-o);
00147     GECODE_ME_FAIL(yv.gq(home,0));
00148     GECODE_ME_FAIL(yv.le(home,x.size()));
00149     // Construct index view array
00150     IdxViewArray<IntView> ix(home,x.size());
00151     for (int i=0; i<x.size(); i++) {
00152       ix[i].idx=i; ix[i].view=x[i];
00153     }
00154     if (tiebreak)
00155         GECODE_ES_FAIL((Arithmetic::ArgMax<IntView,OffsetView,true>
00156                         ::post(home,ix,yv)));
00157     else
00158         GECODE_ES_FAIL((Arithmetic::ArgMax<IntView,OffsetView,false>
00159                         ::post(home,ix,yv)));
00160   }
00161 
00162   void
00163   argmin(Home home, const IntVarArgs& x, IntVar y, bool tiebreak,
00164          IntPropLevel) {
00165     using namespace Int;
00166     if (x.size() == 0)
00167       throw TooFewArguments("Int::argmin");
00168     if (same(x,y))
00169       throw ArgumentSame("Int::argmin");
00170     GECODE_POST;
00171     // Constrain y properly
00172     IntView yv(y);
00173     GECODE_ME_FAIL(yv.gq(home,0));
00174     GECODE_ME_FAIL(yv.le(home,x.size()));
00175     // Construct index view array
00176     IdxViewArray<MinusView> ix(home,x.size());
00177     for (int i=0; i<x.size(); i++) {
00178       ix[i].idx=i; ix[i].view=MinusView(x[i]);
00179     }
00180     if (tiebreak)
00181         GECODE_ES_FAIL((Arithmetic::ArgMax<MinusView,IntView,true>
00182                         ::post(home,ix,yv)));
00183     else
00184         GECODE_ES_FAIL((Arithmetic::ArgMax<MinusView,IntView,false>
00185                         ::post(home,ix,yv)));
00186   }
00187 
00188   void
00189   argmin(Home home, const IntVarArgs& x, int o, IntVar y, bool tiebreak,
00190          IntPropLevel) {
00191     using namespace Int;
00192     Limits::nonnegative(o,"Int::argmin");
00193     if (x.size() == 0)
00194       throw TooFewArguments("Int::argmin");
00195     if (same(x,y))
00196       throw ArgumentSame("Int::argmin");
00197     GECODE_POST;
00198     // Constrain y properly
00199     OffsetView yv(y,-o);
00200     GECODE_ME_FAIL(yv.gq(home,0));
00201     GECODE_ME_FAIL(yv.le(home,x.size()));
00202     // Construct index view array
00203     IdxViewArray<MinusView> ix(home,x.size());
00204     for (int i=0; i<x.size(); i++) {
00205       ix[i].idx=i; ix[i].view=MinusView(x[i]);
00206     }
00207     if (tiebreak)
00208         GECODE_ES_FAIL((Arithmetic::ArgMax<MinusView,OffsetView,true>
00209                         ::post(home,ix,yv)));
00210     else
00211         GECODE_ES_FAIL((Arithmetic::ArgMax<MinusView,OffsetView,false>
00212                         ::post(home,ix,yv)));
00213   }
00214 
00215   void
00216   argmax(Home home, const BoolVarArgs& x, IntVar y, bool tiebreak,
00217          IntPropLevel) {
00218     using namespace Int;
00219     if (x.size() == 0)
00220       throw TooFewArguments("Int::argmax");
00221     GECODE_POST;
00222     // Constrain y properly
00223     IntView yv(y);
00224     GECODE_ME_FAIL(yv.gq(home,0));
00225     GECODE_ME_FAIL(yv.le(home,x.size()));
00226     // Construct index view array
00227     IdxViewArray<BoolView> ix(home,x.size());
00228     for (int i=x.size(); i--; ) {
00229       ix[i].idx=i; ix[i].view=x[i];
00230     }
00231     if (tiebreak)
00232         GECODE_ES_FAIL((Arithmetic::ArgMax<BoolView,IntView,true>
00233                         ::post(home,ix,yv)));
00234     else
00235         GECODE_ES_FAIL((Arithmetic::ArgMax<BoolView,IntView,false>
00236                         ::post(home,ix,yv)));
00237   }
00238 
00239   void
00240   argmax(Home home, const BoolVarArgs& x, int o, IntVar y, bool tiebreak,
00241          IntPropLevel) {
00242     using namespace Int;
00243     Limits::nonnegative(o,"Int::argmax");
00244     if (x.size() == 0)
00245       throw TooFewArguments("Int::argmax");
00246     GECODE_POST;
00247     // Constrain y properly
00248     OffsetView yv(y,-o);
00249     GECODE_ME_FAIL(yv.gq(home,0));
00250     GECODE_ME_FAIL(yv.le(home,x.size()));
00251     // Construct index view array
00252     IdxViewArray<BoolView> ix(home,x.size());
00253     for (int i=x.size(); i--; ) {
00254       ix[i].idx=i; ix[i].view=x[i];
00255     }
00256     if (tiebreak)
00257         GECODE_ES_FAIL((Arithmetic::ArgMax<BoolView,OffsetView,true>
00258                         ::post(home,ix,yv)));
00259     else
00260         GECODE_ES_FAIL((Arithmetic::ArgMax<BoolView,OffsetView,false>
00261                         ::post(home,ix,yv)));
00262   }
00263 
00264   void
00265   argmin(Home home, const BoolVarArgs& x, IntVar y, bool tiebreak,
00266          IntPropLevel) {
00267     using namespace Int;
00268     if (x.size() == 0)
00269       throw TooFewArguments("Int::argmin");
00270     GECODE_POST;
00271     // Constrain y properly
00272     IntView yv(y);
00273     GECODE_ME_FAIL(yv.gq(home,0));
00274     GECODE_ME_FAIL(yv.le(home,x.size()));
00275     // Construct index view array
00276     IdxViewArray<NegBoolView> ix(home,x.size());
00277     for (int i=x.size(); i--; ) {
00278       ix[i].idx=i; ix[i].view=NegBoolView(x[i]);
00279     }
00280     if (tiebreak)
00281         GECODE_ES_FAIL((Arithmetic::ArgMax<NegBoolView,IntView,true>
00282                         ::post(home,ix,yv)));
00283     else
00284         GECODE_ES_FAIL((Arithmetic::ArgMax<NegBoolView,IntView,false>
00285                         ::post(home,ix,yv)));
00286   }
00287 
00288   void
00289   argmin(Home home, const BoolVarArgs& x, int o, IntVar y, bool tiebreak,
00290          IntPropLevel) {
00291     using namespace Int;
00292     Limits::nonnegative(o,"Int::argmin");
00293     if (x.size() == 0)
00294       throw TooFewArguments("Int::argmin");
00295     GECODE_POST;
00296     // Constrain y properly
00297     OffsetView yv(y,-o);
00298     GECODE_ME_FAIL(yv.gq(home,0));
00299     GECODE_ME_FAIL(yv.le(home,x.size()));
00300     // Construct index view array
00301     IdxViewArray<NegBoolView> ix(home,x.size());
00302     for (int i=x.size(); i--; ) {
00303       ix[i].idx=i; ix[i].view=NegBoolView(x[i]);
00304     }
00305     if (tiebreak)
00306         GECODE_ES_FAIL((Arithmetic::ArgMax<NegBoolView,OffsetView,true>
00307                         ::post(home,ix,yv)));
00308     else
00309         GECODE_ES_FAIL((Arithmetic::ArgMax<NegBoolView,OffsetView,false>
00310                         ::post(home,ix,yv)));
00311   }
00312 
00313   void
00314   mult(Home home, IntVar x0, IntVar x1, IntVar x2,
00315        IntPropLevel ipl) {
00316     using namespace Int;
00317     GECODE_POST;
00318     if (vbd(ipl) == IPL_DOM) {
00319       GECODE_ES_FAIL(Arithmetic::MultDom::post(home,x0,x1,x2));
00320     } else {
00321       GECODE_ES_FAIL(Arithmetic::MultBnd::post(home,x0,x1,x2));
00322     }
00323   }
00324 
00325 
00326   void
00327   divmod(Home home, IntVar x0, IntVar x1, IntVar x2, IntVar x3,
00328          IntPropLevel) {
00329     using namespace Int;
00330     GECODE_POST;
00331 
00332     IntVar prod(home, Int::Limits::min, Int::Limits::max);
00333     GECODE_ES_FAIL(Arithmetic::MultBnd::post(home,x1,x2,prod));
00334     Linear::Term<IntView> t[3];
00335     t[0].a = 1; t[0].x = prod;
00336     t[1].a = 1; t[1].x = x3;
00337     int min, max;
00338     Linear::estimate(t,2,0,min,max);
00339     IntView x0v(x0);
00340     GECODE_ME_FAIL(x0v.gq(home,min));
00341     GECODE_ME_FAIL(x0v.lq(home,max));
00342     t[2].a=-1; t[2].x=x0;
00343     Linear::post(home,t,3,IRT_EQ,0,IPL_BND);
00344     if (home.failed()) return;
00345     IntView x1v(x1);
00346     GECODE_ES_FAIL(
00347       Arithmetic::DivMod<IntView>::post(home,x0,x1,x3));
00348   }
00349 
00350   void
00351   div(Home home, IntVar x0, IntVar x1, IntVar x2,
00352       IntPropLevel) {
00353     using namespace Int;
00354     GECODE_POST;
00355     GECODE_ES_FAIL(
00356       (Arithmetic::DivBnd<IntView>::post(home,x0,x1,x2)));
00357   }
00358 
00359   void
00360   mod(Home home, IntVar x0, IntVar x1, IntVar x2,
00361       IntPropLevel ipl) {
00362     using namespace Int;
00363     GECODE_POST;
00364     IntVar _div(home, Int::Limits::min, Int::Limits::max);
00365     divmod(home, x0, x1, _div, x2, ipl);
00366   }
00367 
00368   void
00369   sqr(Home home, IntVar x0, IntVar x1, IntPropLevel ipl) {
00370     using namespace Int;
00371     GECODE_POST;
00372     Arithmetic::SqrOps ops;
00373     if (vbd(ipl) == IPL_DOM) {
00374       GECODE_ES_FAIL(Arithmetic::PowDom<Arithmetic::SqrOps>
00375                      ::post(home,x0,x1,ops));
00376     } else {
00377       GECODE_ES_FAIL(Arithmetic::PowBnd<Arithmetic::SqrOps>
00378                      ::post(home,x0,x1,ops));
00379     }
00380   }
00381 
00382   void
00383   sqrt(Home home, IntVar x0, IntVar x1, IntPropLevel ipl) {
00384     using namespace Int;
00385     GECODE_POST;
00386     Arithmetic::SqrOps ops;
00387     if (vbd(ipl) == IPL_DOM) {
00388       GECODE_ES_FAIL(Arithmetic::NrootDom<Arithmetic::SqrOps>
00389                      ::post(home,x0,x1,ops));
00390     } else {
00391       GECODE_ES_FAIL(Arithmetic::NrootBnd<Arithmetic::SqrOps>
00392                      ::post(home,x0,x1,ops));
00393     }
00394   }
00395 
00396   void
00397   pow(Home home, IntVar x0, int n, IntVar x1, IntPropLevel ipl) {
00398     using namespace Int;
00399     Limits::nonnegative(n,"Int::pow");
00400     GECODE_POST;
00401     if (n == 2) {
00402       sqr(home, x0, x1, ipl);
00403       return;
00404     }
00405     Arithmetic::PowOps ops(n);
00406     if (vbd(ipl) == IPL_DOM) {
00407       GECODE_ES_FAIL(Arithmetic::PowDom<Arithmetic::PowOps>
00408                      ::post(home,x0,x1,ops));
00409     } else {
00410       GECODE_ES_FAIL(Arithmetic::PowBnd<Arithmetic::PowOps>
00411                      ::post(home,x0,x1,ops));
00412     }
00413   }
00414 
00415   void
00416   nroot(Home home, IntVar x0, int n, IntVar x1, IntPropLevel ipl) {
00417     using namespace Int;
00418     Limits::positive(n,"Int::nroot");
00419     GECODE_POST;
00420     if (n == 2) {
00421       sqrt(home, x0, x1, ipl);
00422       return;
00423     }
00424     Arithmetic::PowOps ops(n);
00425     if (vbd(ipl) == IPL_DOM) {
00426       GECODE_ES_FAIL(Arithmetic::NrootDom<Arithmetic::PowOps>
00427                      ::post(home,x0,x1,ops));
00428     } else {
00429       GECODE_ES_FAIL(Arithmetic::NrootBnd<Arithmetic::PowOps>
00430                      ::post(home,x0,x1,ops));
00431     }
00432   }
00433 
00434 }
00435 
00436 // STATISTICS: int-post