rel.cpp

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  *  Last modified:
00010  *     $Date: 2011-12-12 16:21:39 +0100 (Mon, 12 Dec 2011) $ by $Author: schulte $
00011  *     $Revision: 12489 $
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/int/rel.hh>
00039 #include <gecode/int/bool.hh>
00040 
00041 #include <algorithm>
00042 
00043 namespace Gecode {
00044 
00045   using namespace Int;
00046 
00047   void
00048   rel(Home home, IntVar x0, IntRelType irt, int n, IntConLevel) {
00049     Limits::check(n,"Int::rel");
00050     if (home.failed()) return;
00051     IntView x(x0);
00052     switch (irt) {
00053     case IRT_EQ: GECODE_ME_FAIL(x.eq(home,n)); break;
00054     case IRT_NQ: GECODE_ME_FAIL(x.nq(home,n)); break;
00055     case IRT_LQ: GECODE_ME_FAIL(x.lq(home,n)); break;
00056     case IRT_LE: GECODE_ME_FAIL(x.le(home,n)); break;
00057     case IRT_GQ: GECODE_ME_FAIL(x.gq(home,n)); break;
00058     case IRT_GR: GECODE_ME_FAIL(x.gr(home,n)); break;
00059     default: throw UnknownRelation("Int::rel");
00060     }
00061   }
00062 
00063   void
00064   rel(Home home, const IntVarArgs& x, IntRelType irt, int n, IntConLevel) {
00065     Limits::check(n,"Int::rel");
00066     if (home.failed()) return;
00067     switch (irt) {
00068     case IRT_EQ:
00069       for (int i=x.size(); i--; ) {
00070         IntView xi(x[i]); GECODE_ME_FAIL(xi.eq(home,n));
00071       }
00072       break;
00073     case IRT_NQ:
00074       for (int i=x.size(); i--; ) {
00075         IntView xi(x[i]); GECODE_ME_FAIL(xi.nq(home,n));
00076       }
00077       break;
00078     case IRT_LQ:
00079       for (int i=x.size(); i--; ) {
00080         IntView xi(x[i]); GECODE_ME_FAIL(xi.lq(home,n));
00081       }
00082       break;
00083     case IRT_LE:
00084       for (int i=x.size(); i--; ) {
00085         IntView xi(x[i]); GECODE_ME_FAIL(xi.le(home,n));
00086       }
00087       break;
00088     case IRT_GQ:
00089       for (int i=x.size(); i--; ) {
00090         IntView xi(x[i]); GECODE_ME_FAIL(xi.gq(home,n));
00091       }
00092       break;
00093     case IRT_GR:
00094       for (int i=x.size(); i--; ) {
00095         IntView xi(x[i]); GECODE_ME_FAIL(xi.gr(home,n));
00096       }
00097       break;
00098     default:
00099       throw UnknownRelation("Int::rel");
00100     }
00101   }
00102 
00103   void
00104   rel(Home home, IntVar x0, IntRelType irt, IntVar x1, IntConLevel icl) {
00105     if (home.failed()) return;
00106     switch (irt) {
00107     case IRT_EQ:
00108       if ((icl == ICL_DOM) || (icl == ICL_DEF)) {
00109         GECODE_ES_FAIL((Rel::EqDom<IntView,IntView>::post(home,x0,x1)));
00110       } else {
00111         GECODE_ES_FAIL((Rel::EqBnd<IntView,IntView>::post(home,x0,x1)));
00112       }
00113       break;
00114     case IRT_NQ:
00115       GECODE_ES_FAIL(Rel::Nq<IntView>::post(home,x0,x1)); break;
00116     case IRT_GQ:
00117       std::swap(x0,x1); // Fall through
00118     case IRT_LQ:
00119       GECODE_ES_FAIL(Rel::Lq<IntView>::post(home,x0,x1)); break;
00120     case IRT_GR:
00121       std::swap(x0,x1); // Fall through
00122     case IRT_LE:
00123       GECODE_ES_FAIL(Rel::Le<IntView>::post(home,x0,x1)); break;
00124     default:
00125       throw UnknownRelation("Int::rel");
00126     }
00127   }
00128 
00129   void
00130   rel(Home home, const IntVarArgs& x, IntRelType irt, IntVar y,
00131       IntConLevel icl) {
00132     if (home.failed()) return;
00133     switch (irt) {
00134     case IRT_EQ:
00135       {
00136         ViewArray<IntView> xv(home,x.size()+1);
00137         xv[x.size()]=y;
00138         for (int i=x.size(); i--; )
00139           xv[i]=x[i];
00140         if ((icl == ICL_DOM) || (icl == ICL_DEF)) {
00141           GECODE_ES_FAIL(Rel::NaryEqDom<IntView>::post(home,xv));
00142         } else {
00143           GECODE_ES_FAIL(Rel::NaryEqBnd<IntView>::post(home,xv));
00144         }
00145       }
00146       break;
00147     case IRT_NQ:
00148       for (int i=x.size(); i--; ) {
00149         GECODE_ES_FAIL(Rel::Nq<IntView>::post(home,x[i],y));
00150       }
00151       break;
00152     case IRT_GQ:
00153       for (int i=x.size(); i--; ) {
00154         GECODE_ES_FAIL(Rel::Lq<IntView>::post(home,y,x[i]));
00155       }
00156       break;
00157     case IRT_LQ:
00158       for (int i=x.size(); i--; ) {
00159         GECODE_ES_FAIL(Rel::Lq<IntView>::post(home,x[i],y));
00160       }
00161       break;
00162     case IRT_GR:
00163       for (int i=x.size(); i--; ) {
00164         GECODE_ES_FAIL(Rel::Le<IntView>::post(home,y,x[i]));
00165       }
00166       break;
00167     case IRT_LE:
00168       for (int i=x.size(); i--; ) {
00169         GECODE_ES_FAIL(Rel::Le<IntView>::post(home,x[i],y));
00170       }
00171       break;
00172     default:
00173       throw UnknownRelation("Int::rel");
00174     }
00175   }
00176 
00177 
00178   void
00179   rel(Home home, IntVar x0, IntRelType irt, IntVar x1, Reify r,
00180       IntConLevel icl) {
00181     if (home.failed()) return;
00182     switch (irt) {
00183     case IRT_EQ:
00184       if ((icl == ICL_DOM) || (icl == ICL_DEF)) {
00185         switch (r.mode()) {
00186         case RM_EQV:
00187           GECODE_ES_FAIL((Rel::ReEqDom<IntView,BoolView,RM_EQV>
00188                           ::post(home,x0,x1,r.var())));
00189           break;
00190         case RM_IMP:
00191           GECODE_ES_FAIL((Rel::ReEqDom<IntView,BoolView,RM_IMP>
00192                           ::post(home,x0,x1,r.var())));
00193           break;
00194         case RM_PMI:
00195           GECODE_ES_FAIL((Rel::ReEqDom<IntView,BoolView,RM_PMI>
00196                           ::post(home,x0,x1,r.var())));
00197           break;
00198         default: throw UnknownReifyMode("Int::rel");
00199         }
00200       } else {
00201         switch (r.mode()) {
00202         case RM_EQV:
00203           GECODE_ES_FAIL((Rel::ReEqBnd<IntView,BoolView,RM_EQV>
00204                           ::post(home,x0,x1,r.var())));
00205           break;
00206         case RM_IMP:
00207           GECODE_ES_FAIL((Rel::ReEqBnd<IntView,BoolView,RM_IMP>
00208                           ::post(home,x0,x1,r.var())));
00209           break;
00210         case RM_PMI:
00211           GECODE_ES_FAIL((Rel::ReEqBnd<IntView,BoolView,RM_PMI>
00212                           ::post(home,x0,x1,r.var())));
00213           break;
00214         default: throw UnknownReifyMode("Int::rel");
00215         }
00216       }
00217       break;
00218     case IRT_NQ:
00219       {
00220         NegBoolView n(r.var());
00221         if (icl == ICL_BND) {
00222           switch (r.mode()) {
00223           case RM_EQV:
00224             GECODE_ES_FAIL((Rel::ReEqBnd<IntView,NegBoolView,RM_EQV>
00225                             ::post(home,x0,x1,n)));
00226             break;
00227           case RM_IMP:
00228             GECODE_ES_FAIL((Rel::ReEqBnd<IntView,NegBoolView,RM_PMI>
00229                             ::post(home,x0,x1,n)));
00230             break;
00231           case RM_PMI:
00232             GECODE_ES_FAIL((Rel::ReEqBnd<IntView,NegBoolView,RM_IMP>
00233                             ::post(home,x0,x1,n)));
00234             break;
00235           default: throw UnknownReifyMode("Int::rel");
00236           }
00237         } else {
00238           switch (r.mode()) {
00239           case RM_EQV:
00240             GECODE_ES_FAIL((Rel::ReEqDom<IntView,NegBoolView,RM_EQV>
00241                             ::post(home,x0,x1,n)));
00242             break;
00243           case RM_IMP:
00244             GECODE_ES_FAIL((Rel::ReEqDom<IntView,NegBoolView,RM_PMI>
00245                             ::post(home,x0,x1,n)));
00246             break;
00247           case RM_PMI:
00248             GECODE_ES_FAIL((Rel::ReEqDom<IntView,NegBoolView,RM_IMP>
00249                             ::post(home,x0,x1,n)));
00250             break;
00251           default: throw UnknownReifyMode("Int::rel");
00252           }
00253         }
00254       }
00255       break;
00256     case IRT_GQ:
00257       std::swap(x0,x1); // Fall through
00258     case IRT_LQ:
00259       switch (r.mode()) {
00260       case RM_EQV:
00261         GECODE_ES_FAIL((Rel::ReLq<IntView,BoolView,RM_EQV>
00262                         ::post(home,x0,x1,r.var())));
00263         break;
00264       case RM_IMP:
00265         GECODE_ES_FAIL((Rel::ReLq<IntView,BoolView,RM_IMP>
00266                         ::post(home,x0,x1,r.var())));
00267         break;
00268       case RM_PMI:
00269         GECODE_ES_FAIL((Rel::ReLq<IntView,BoolView,RM_PMI>
00270                         ::post(home,x0,x1,r.var())));
00271         break;
00272       default: throw UnknownReifyMode("Int::rel");
00273       }
00274       break;
00275     case IRT_LE:
00276       std::swap(x0,x1); // Fall through
00277     case IRT_GR:
00278       {
00279         NegBoolView n(r.var());
00280         switch (r.mode()) {
00281         case RM_EQV:
00282           GECODE_ES_FAIL((Rel::ReLq<IntView,NegBoolView,RM_EQV>
00283                           ::post(home,x0,x1,n)));
00284           break;
00285         case RM_IMP:
00286           GECODE_ES_FAIL((Rel::ReLq<IntView,NegBoolView,RM_PMI>
00287                           ::post(home,x0,x1,n)));
00288           break;
00289         case RM_PMI:
00290           GECODE_ES_FAIL((Rel::ReLq<IntView,NegBoolView,RM_IMP>
00291                           ::post(home,x0,x1,n)));
00292           break;
00293         default: throw UnknownReifyMode("Int::rel");
00294         }
00295       }
00296       break;
00297     default:
00298       throw UnknownRelation("Int::rel");
00299     }
00300   }
00301 
00302   void
00303   rel(Home home, IntVar x, IntRelType irt, int n, Reify r,
00304       IntConLevel icl) {
00305     Limits::check(n,"Int::rel");
00306     if (home.failed()) return;
00307     switch (irt) {
00308     case IRT_EQ:
00309       if ((icl == ICL_DOM) || (icl == ICL_DEF)) {
00310         switch (r.mode()) {
00311         case RM_EQV:
00312           GECODE_ES_FAIL((Rel::ReEqDomInt<IntView,BoolView,RM_EQV>
00313                           ::post(home,x,n,r.var())));
00314           break;
00315         case RM_IMP:
00316           GECODE_ES_FAIL((Rel::ReEqDomInt<IntView,BoolView,RM_IMP>
00317                           ::post(home,x,n,r.var())));
00318           break;
00319         case RM_PMI:
00320           GECODE_ES_FAIL((Rel::ReEqDomInt<IntView,BoolView,RM_PMI>
00321                           ::post(home,x,n,r.var())));
00322           break;
00323         default: throw UnknownReifyMode("Int::rel");
00324         }
00325       } else {
00326         switch (r.mode()) {
00327         case RM_EQV:
00328           GECODE_ES_FAIL((Rel::ReEqBndInt<IntView,BoolView,RM_EQV>
00329                           ::post(home,x,n,r.var())));
00330           break;
00331         case RM_IMP:
00332           GECODE_ES_FAIL((Rel::ReEqBndInt<IntView,BoolView,RM_IMP>
00333                           ::post(home,x,n,r.var())));
00334           break;
00335         case RM_PMI:
00336           GECODE_ES_FAIL((Rel::ReEqBndInt<IntView,BoolView,RM_PMI>
00337                           ::post(home,x,n,r.var())));
00338           break;
00339         default: throw UnknownReifyMode("Int::rel");
00340         }
00341       }
00342       break;
00343     case IRT_NQ:
00344       {
00345         NegBoolView nb(r.var());
00346         if (icl == ICL_BND) {
00347           switch (r.mode()) {
00348           case RM_EQV:
00349             GECODE_ES_FAIL((Rel::ReEqBndInt<IntView,NegBoolView,RM_EQV>
00350                             ::post(home,x,n,nb)));
00351             break;
00352           case RM_IMP:
00353             GECODE_ES_FAIL((Rel::ReEqBndInt<IntView,NegBoolView,RM_PMI>
00354                             ::post(home,x,n,nb)));
00355             break;
00356           case RM_PMI:
00357             GECODE_ES_FAIL((Rel::ReEqBndInt<IntView,NegBoolView,RM_IMP>
00358                             ::post(home,x,n,nb)));
00359             break;
00360           default: throw UnknownReifyMode("Int::rel");
00361           }
00362         } else {
00363           switch (r.mode()) {
00364           case RM_EQV:
00365             GECODE_ES_FAIL((Rel::ReEqDomInt<IntView,NegBoolView,RM_EQV>
00366                             ::post(home,x,n,nb)));
00367             break;
00368           case RM_IMP:
00369             GECODE_ES_FAIL((Rel::ReEqDomInt<IntView,NegBoolView,RM_PMI>
00370                             ::post(home,x,n,nb)));
00371             break;
00372           case RM_PMI:
00373             GECODE_ES_FAIL((Rel::ReEqDomInt<IntView,NegBoolView,RM_IMP>
00374                             ::post(home,x,n,nb)));
00375             break;
00376           default: throw UnknownReifyMode("Int::rel");
00377           }
00378         }
00379       }
00380       break;
00381     case IRT_LE:
00382       n--; // Fall through
00383     case IRT_LQ:
00384       switch (r.mode()) {
00385       case RM_EQV:
00386         GECODE_ES_FAIL((Rel::ReLqInt<IntView,BoolView,RM_EQV>
00387                         ::post(home,x,n,r.var())));
00388         break;
00389       case RM_IMP:
00390         GECODE_ES_FAIL((Rel::ReLqInt<IntView,BoolView,RM_IMP>
00391                         ::post(home,x,n,r.var())));
00392         break;
00393       case RM_PMI:
00394         GECODE_ES_FAIL((Rel::ReLqInt<IntView,BoolView,RM_PMI>
00395                         ::post(home,x,n,r.var())));
00396         break;
00397       default: throw UnknownReifyMode("Int::rel");
00398       }
00399       break;
00400     case IRT_GQ:
00401       n--; // Fall through
00402     case IRT_GR:
00403       {
00404         NegBoolView nb(r.var());
00405         switch (r.mode()) {
00406         case RM_EQV:
00407           GECODE_ES_FAIL((Rel::ReLqInt<IntView,NegBoolView,RM_EQV>
00408                           ::post(home,x,n,nb)));
00409           break;
00410         case RM_IMP:
00411           GECODE_ES_FAIL((Rel::ReLqInt<IntView,NegBoolView,RM_PMI>
00412                           ::post(home,x,n,nb)));
00413           break;
00414         case RM_PMI:
00415           GECODE_ES_FAIL((Rel::ReLqInt<IntView,NegBoolView,RM_IMP>
00416                           ::post(home,x,n,nb)));
00417           break;
00418         default: throw UnknownReifyMode("Int::rel");
00419         }
00420       }
00421       break;
00422     default:
00423       throw UnknownRelation("Int::rel");
00424     }
00425   }
00426 
00427   void
00428   rel(Home home, const IntVarArgs& x, IntRelType irt,
00429       IntConLevel icl) {
00430     if (home.failed() || ((irt != IRT_NQ) && (x.size() < 2))) 
00431       return;
00432     switch (irt) {
00433     case IRT_EQ:
00434       {
00435         ViewArray<IntView> xv(home,x);
00436         if ((icl == ICL_DOM) || (icl == ICL_DEF)) {
00437           GECODE_ES_FAIL(Rel::NaryEqDom<IntView>::post(home,xv));
00438         } else {
00439           GECODE_ES_FAIL(Rel::NaryEqBnd<IntView>::post(home,xv));
00440         }
00441       }
00442       break;
00443     case IRT_NQ:
00444       {
00445         ViewArray<IntView> y(home,x);
00446         GECODE_ES_FAIL((Rel::NaryNq<IntView>::post(home,y)));
00447       }
00448       break;
00449     case IRT_LE:
00450       {
00451         ViewArray<IntView> y(home,x);
00452         GECODE_ES_FAIL((Rel::NaryLqLe<IntView,1>::post(home,y)));
00453       }
00454       break;
00455     case IRT_LQ:
00456       {
00457         ViewArray<IntView> y(home,x);
00458         GECODE_ES_FAIL((Rel::NaryLqLe<IntView,0>::post(home,y)));
00459       }
00460       break;
00461     case IRT_GR:
00462       {
00463         ViewArray<IntView> y(home,x.size());
00464         for (int i=x.size(); i--; )
00465           y[i] = x[x.size()-1-i];
00466         GECODE_ES_FAIL((Rel::NaryLqLe<IntView,1>::post(home,y)));
00467       }
00468       for (int i=x.size()-1; i--; )
00469         GECODE_ES_FAIL(Rel::Le<IntView>::post(home,x[i+1],x[i]));
00470       break;
00471     case IRT_GQ:
00472       {
00473         ViewArray<IntView> y(home,x.size());
00474         for (int i=x.size(); i--; )
00475           y[i] = x[x.size()-1-i];
00476         GECODE_ES_FAIL((Rel::NaryLqLe<IntView,0>::post(home,y)));
00477       }
00478       break;
00479     default:
00480       throw UnknownRelation("Int::rel");
00481     }
00482   }
00483 
00484   void
00485   rel(Home home, const IntVarArgs& x, IntRelType irt, const IntVarArgs& y,
00486       IntConLevel icl) {
00487     if (home.failed()) return;
00488 
00489     switch (irt) {
00490     case IRT_GR:
00491       {
00492         ViewArray<IntView> xv(home,x), yv(home,y);
00493         GECODE_ES_FAIL(Rel::LexLqLe<IntView>::post(home,yv,xv,true));
00494       }
00495       break;
00496     case IRT_LE:
00497       {
00498         ViewArray<IntView> xv(home,x), yv(home,y);
00499         GECODE_ES_FAIL(Rel::LexLqLe<IntView>::post(home,xv,yv,true));
00500       }
00501       break;
00502     case IRT_GQ:
00503       {
00504         ViewArray<IntView> xv(home,x), yv(home,y);
00505         GECODE_ES_FAIL(Rel::LexLqLe<IntView>::post(home,yv,xv,false));
00506       }
00507       break;
00508     case IRT_LQ:
00509       {
00510         ViewArray<IntView> xv(home,x), yv(home,y);
00511         GECODE_ES_FAIL(Rel::LexLqLe<IntView>::post(home,xv,yv,false));
00512       }
00513       break;
00514     case IRT_EQ:
00515       if (x.size() != y.size()) {
00516         home.fail();
00517       } else if ((icl == ICL_DOM) || (icl == ICL_DEF))
00518         for (int i=x.size(); i--; ) {
00519           GECODE_ES_FAIL((Rel::EqDom<IntView,IntView>
00520                           ::post(home,x[i],y[i])));
00521         }
00522       else
00523         for (int i=x.size(); i--; ) {
00524           GECODE_ES_FAIL((Rel::EqBnd<IntView,IntView>
00525                           ::post(home,x[i],y[i])));
00526         }
00527       break;
00528     case IRT_NQ:
00529       {
00530         ViewArray<IntView> xv(home,x), yv(home,y);
00531         GECODE_ES_FAIL(Rel::LexNq<IntView>::post(home,xv,yv));
00532       }
00533       break;
00534     default:
00535       throw UnknownRelation("Int::rel");
00536     }
00537   }
00538 
00539 }
00540 
00541 // STATISTICS: int-post