Generated on Wed Mar 19 07:29:54 2008 for Gecode by doxygen 1.5.5

rel.cc

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  *  Last modified:
00010  *     $Date: 2008-02-06 20:23:59 +0100 (Wed, 06 Feb 2008) $ by $Author: schulte $
00011  *     $Revision: 6103 $
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 
00040 #include <algorithm>
00041 
00042 namespace Gecode {
00043 
00044   using namespace Int;
00045 
00046   void
00047   rel(Space* home, IntVar x0, IntRelType r, int n, 
00048       IntConLevel, PropKind) {
00049     Limits::check(n,"Int::rel");
00050     if (home->failed()) return;
00051     IntView x(x0);
00052     switch (r) {
00053     case IRT_EQ: GECODE_ME_FAIL(home,x.eq(home,n)); break;
00054     case IRT_NQ: GECODE_ME_FAIL(home,x.nq(home,n)); break;
00055     case IRT_LQ: GECODE_ME_FAIL(home,x.lq(home,n)); break;
00056     case IRT_LE: GECODE_ME_FAIL(home,x.le(home,n)); break;
00057     case IRT_GQ: GECODE_ME_FAIL(home,x.gq(home,n)); break;
00058     case IRT_GR: GECODE_ME_FAIL(home,x.gr(home,n)); break;
00059     default: throw UnknownRelation("Int::rel");
00060     }
00061   }
00062 
00063   void
00064   rel(Space* home, const IntVarArgs& x, IntRelType r, int n, 
00065       IntConLevel, PropKind) {
00066     Limits::check(n,"Int::rel");
00067     if (home->failed()) return;
00068     switch (r) {
00069     case IRT_EQ: 
00070       for (int i=x.size(); i--; ) {
00071         IntView xi(x[i]); GECODE_ME_FAIL(home,xi.eq(home,n));
00072       }
00073       break;
00074     case IRT_NQ:
00075       for (int i=x.size(); i--; ) {
00076         IntView xi(x[i]); GECODE_ME_FAIL(home,xi.nq(home,n));
00077       }
00078       break;
00079     case IRT_LQ:
00080       for (int i=x.size(); i--; ) {
00081         IntView xi(x[i]); GECODE_ME_FAIL(home,xi.lq(home,n));
00082       }
00083       break;
00084     case IRT_LE:
00085       for (int i=x.size(); i--; ) {
00086         IntView xi(x[i]); GECODE_ME_FAIL(home,xi.le(home,n));
00087       }
00088       break;
00089     case IRT_GQ:
00090       for (int i=x.size(); i--; ) {
00091         IntView xi(x[i]); GECODE_ME_FAIL(home,xi.gq(home,n));
00092       }
00093       break;
00094     case IRT_GR:
00095       for (int i=x.size(); i--; ) {
00096         IntView xi(x[i]); GECODE_ME_FAIL(home,xi.gr(home,n));
00097       }
00098       break;
00099     default:
00100       throw UnknownRelation("Int::rel");
00101     }
00102   }
00103 
00104   void
00105   rel(Space* home, IntVar x0, IntRelType r, IntVar x1, 
00106       IntConLevel icl, PropKind) {
00107     if (home->failed()) return;
00108     switch (r) {
00109     case IRT_EQ:
00110       if ((icl == ICL_DOM) || (icl == ICL_DEF)) {
00111         GECODE_ES_FAIL(home,(Rel::EqDom<IntView,IntView>::post(home,x0,x1)));
00112       } else {
00113         GECODE_ES_FAIL(home,(Rel::EqBnd<IntView,IntView>::post(home,x0,x1)));
00114       }
00115       break;
00116     case IRT_NQ:
00117       GECODE_ES_FAIL(home,Rel::Nq<IntView>::post(home,x0,x1)); break;
00118     case IRT_GQ:
00119       std::swap(x0,x1); // Fall through
00120     case IRT_LQ:
00121       GECODE_ES_FAIL(home,Rel::Lq<IntView>::post(home,x0,x1)); break;
00122     case IRT_GR:
00123       std::swap(x0,x1); // Fall through
00124     case IRT_LE:
00125       GECODE_ES_FAIL(home,Rel::Le<IntView>::post(home,x0,x1)); break;
00126     default:
00127       throw UnknownRelation("Int::rel");
00128     }
00129   }
00130 
00131   void
00132   rel(Space* home, const IntVarArgs& x, IntRelType r, IntVar y, 
00133       IntConLevel icl, PropKind) {
00134     if (home->failed()) return;
00135     switch (r) {
00136     case IRT_EQ:
00137       {
00138         ViewArray<IntView> xv(home,x.size()+1);
00139         xv[x.size()]=y;
00140         for (int i=x.size(); i--; )
00141           xv[i]=x[i];
00142         if ((icl == ICL_DOM) || (icl == ICL_DEF)) {
00143           GECODE_ES_FAIL(home,Rel::NaryEqDom<IntView>::post(home,xv));
00144         } else {
00145           GECODE_ES_FAIL(home,Rel::NaryEqBnd<IntView>::post(home,xv));
00146         }
00147       }
00148       break;
00149     case IRT_NQ:
00150       for (int i=x.size(); i--; ) {
00151         GECODE_ES_FAIL(home,Rel::Nq<IntView>::post(home,x[i],y)); 
00152       }
00153       break;
00154     case IRT_GQ:
00155       for (int i=x.size(); i--; ) {
00156         GECODE_ES_FAIL(home,Rel::Lq<IntView>::post(home,y,x[i])); 
00157       }
00158       break;
00159     case IRT_LQ:
00160       for (int i=x.size(); i--; ) {
00161         GECODE_ES_FAIL(home,Rel::Lq<IntView>::post(home,x[i],y)); 
00162       }
00163       break;
00164     case IRT_GR:
00165       for (int i=x.size(); i--; ) {
00166         GECODE_ES_FAIL(home,Rel::Le<IntView>::post(home,y,x[i])); 
00167       }
00168       break;
00169     case IRT_LE:
00170       for (int i=x.size(); i--; ) {
00171         GECODE_ES_FAIL(home,Rel::Le<IntView>::post(home,x[i],y)); 
00172       }
00173       break;
00174     default:
00175       throw UnknownRelation("Int::rel");
00176     }
00177   }
00178 
00179 
00180   void
00181   rel(Space* home, IntVar x0, IntRelType r, IntVar x1, BoolVar b,
00182       IntConLevel icl, PropKind) {
00183     if (home->failed()) return;
00184     switch (r) {
00185     case IRT_EQ:
00186       if ((icl == ICL_DOM) || (icl == ICL_DEF)) {
00187         GECODE_ES_FAIL(home,(Rel::ReEqDom<IntView,BoolView>
00188                              ::post(home,x0,x1,b)));
00189       } else {
00190         GECODE_ES_FAIL(home,(Rel::ReEqBnd<IntView,BoolView>
00191                              ::post(home,x0,x1,b)));
00192       }
00193       break;
00194     case IRT_NQ:
00195       {
00196         NegBoolView n(b);
00197         if (icl == ICL_BND) {
00198           GECODE_ES_FAIL(home,(Rel::ReEqBnd<IntView,NegBoolView>
00199                                ::post(home,x0,x1,n)));
00200         } else {
00201           GECODE_ES_FAIL(home,(Rel::ReEqDom<IntView,NegBoolView>
00202                                ::post(home,x0,x1,n)));
00203         }
00204       }
00205       break;
00206     case IRT_GQ:
00207       std::swap(x0,x1); // Fall through
00208     case IRT_LQ:
00209       GECODE_ES_FAIL(home,(Rel::ReLq<IntView,BoolView>::post(home,x0,x1,b)));
00210       break;
00211     case IRT_LE:
00212       std::swap(x0,x1); // Fall through
00213     case IRT_GR:
00214       {
00215         NegBoolView n(b);
00216         GECODE_ES_FAIL(home,(Rel::ReLq<IntView,NegBoolView>::post(home,x0,x1,n)));
00217       }
00218       break;
00219     default:
00220       throw UnknownRelation("Int::rel");
00221     }
00222   }
00223 
00224   void
00225   rel(Space* home, IntVar x, IntRelType r, int n, BoolVar b,
00226       IntConLevel icl, PropKind) {
00227     Limits::check(n,"Int::rel");
00228     if (home->failed()) return;
00229     switch (r) {
00230     case IRT_EQ:
00231       if ((icl == ICL_DOM) || (icl == ICL_DEF)) {
00232         GECODE_ES_FAIL(home,(Rel::ReEqDomInt<IntView,BoolView>
00233                              ::post(home,x,n,b)));
00234       } else {
00235         GECODE_ES_FAIL(home,(Rel::ReEqBndInt<IntView,BoolView>
00236                              ::post(home,x,n,b)));
00237       }
00238       break;
00239     case IRT_NQ:
00240       {
00241         NegBoolView nb(b);
00242         if (icl == ICL_BND) {
00243           GECODE_ES_FAIL(home,(Rel::ReEqBndInt<IntView,NegBoolView>
00244                                ::post(home,x,n,nb)));
00245         } else {
00246           GECODE_ES_FAIL(home,(Rel::ReEqDomInt<IntView,NegBoolView>
00247                                ::post(home,x,n,nb)));
00248         }
00249       }
00250       break;
00251     case IRT_LE:
00252       n--; // Fall through
00253     case IRT_LQ:
00254       GECODE_ES_FAIL(home,(Rel::ReLqInt<IntView,BoolView>
00255                            ::post(home,x,n,b)));
00256       break;
00257     case IRT_GQ:
00258       n--; // Fall through
00259     case IRT_GR:
00260       {
00261         NegBoolView nb(b);
00262         GECODE_ES_FAIL(home,(Rel::ReLqInt<IntView,NegBoolView>
00263                              ::post(home,x,n,nb)));
00264       }
00265       break;
00266     default:
00267       throw UnknownRelation("Int::rel");
00268     }
00269   }
00270 
00271   void
00272   rel(Space* home, const IntVarArgs& x, IntRelType r, 
00273       IntConLevel icl, PropKind) {
00274     if (home->failed() || (x.size() < 2)) return;
00275     switch (r) {
00276     case IRT_EQ:
00277       {
00278         ViewArray<IntView> xv(home,x);
00279         if ((icl == ICL_DOM) || (icl == ICL_DEF)) {
00280           GECODE_ES_FAIL(home,Rel::NaryEqDom<IntView>::post(home,xv));
00281         } else {
00282           GECODE_ES_FAIL(home,Rel::NaryEqBnd<IntView>::post(home,xv));
00283         }
00284       }
00285       break;
00286     case IRT_NQ:
00287       distinct(home,x,icl);
00288       break;
00289     case IRT_LE:
00290       for (int i=x.size()-1; i--; )
00291         GECODE_ES_FAIL(home,Rel::Le<IntView>::post(home,x[i],x[i+1]));
00292       break;
00293     case IRT_LQ:
00294       for (int i=x.size()-1; i--; )
00295         GECODE_ES_FAIL(home,Rel::Lq<IntView>::post(home,x[i],x[i+1]));
00296       break;
00297     case IRT_GR:
00298       for (int i=x.size()-1; i--; )
00299         GECODE_ES_FAIL(home,Rel::Le<IntView>::post(home,x[i+1],x[i]));
00300       break;
00301     case IRT_GQ:
00302       for (int i=x.size()-1; i--; )
00303         GECODE_ES_FAIL(home,Rel::Lq<IntView>::post(home,x[i+1],x[i]));
00304       break;
00305     default:
00306       throw UnknownRelation("Int::rel");
00307     }
00308   }
00309 
00310   void
00311   rel(Space* home, const IntVarArgs& x, IntRelType r, const IntVarArgs& y,
00312       IntConLevel icl, PropKind) {
00313     if (x.size() != y.size())
00314       throw ArgumentSizeMismatch("Int::rel");
00315     if (home->failed()) return;
00316 
00317     switch (r) {
00318     case IRT_GR: 
00319       {
00320         ViewArray<ViewTuple<IntView,2> > xy(home,x.size());
00321         for (int i = x.size(); i--; ) {
00322           xy[i][0]=y[i]; xy[i][1]=x[i];
00323         }
00324         GECODE_ES_FAIL(home,Rel::Lex<IntView>::post(home,xy,true));
00325       }
00326       break;
00327     case IRT_LE: 
00328       {
00329         ViewArray<ViewTuple<IntView,2> > xy(home,x.size());
00330         for (int i = x.size(); i--; ) {
00331           xy[i][0]=x[i]; xy[i][1]=y[i];
00332         }
00333         GECODE_ES_FAIL(home,Rel::Lex<IntView>::post(home,xy,true));
00334       }
00335       break;
00336     case IRT_GQ: 
00337       {
00338         ViewArray<ViewTuple<IntView,2> > xy(home,x.size());
00339         for (int i = x.size(); i--; ) {
00340           xy[i][0]=y[i]; xy[i][1]=x[i];
00341         }
00342         GECODE_ES_FAIL(home,Rel::Lex<IntView>::post(home,xy,false));
00343       }
00344       break;
00345     case IRT_LQ: 
00346       {
00347         ViewArray<ViewTuple<IntView,2> > xy(home,x.size());
00348         for (int i = x.size(); i--; ) {
00349           xy[i][0]=x[i]; xy[i][1]=y[i];
00350         }
00351         GECODE_ES_FAIL(home,Rel::Lex<IntView>::post(home,xy,false));
00352       }
00353       break;
00354     case IRT_EQ:
00355       if ((icl == ICL_DOM) || (icl == ICL_DEF))
00356         for (int i=x.size(); i--; ) {
00357           GECODE_ES_FAIL(home,(Rel::EqDom<IntView,IntView>
00358                                ::post(home,x[i],y[i])));
00359         }
00360       else
00361         for (int i=x.size(); i--; ) {
00362           GECODE_ES_FAIL(home,(Rel::EqBnd<IntView,IntView>
00363                                ::post(home,x[i],y[i])));
00364         }
00365       break;
00366     case IRT_NQ: 
00367       {
00368         ViewArray<ViewTuple<IntView,2> > xy(home,x.size());
00369         for (int i = x.size(); i--; ) {
00370           xy[i][0]=x[i]; xy[i][1]=y[i];
00371         }
00372         GECODE_ES_FAIL(home,Rel::NaryNq<IntView>::post(home,xy));
00373       }
00374       break;
00375     default:
00376       throw UnknownRelation("Int::rel");
00377     }
00378   }
00379 
00380   namespace {
00381     using namespace Int;
00382     GECODE_REGISTER2(Rel::EqBnd<IntView,IntView>);
00383     GECODE_REGISTER2(Rel::EqBnd<IntView,ConstIntView>);
00384     GECODE_REGISTER2(Rel::EqBnd<BoolView,ConstIntView>);
00385     GECODE_REGISTER2(Rel::EqBnd<BoolView,BoolView>);
00386     GECODE_REGISTER2(Rel::EqBnd<MinusView,IntView>);
00387     GECODE_REGISTER2(Rel::EqBnd<MinusView,MinusView>);
00388 
00389     GECODE_REGISTER2(Rel::EqDom<IntView,IntView>);
00390     GECODE_REGISTER2(Rel::EqDom<IntView,ConstIntView>);
00391     GECODE_REGISTER2(Rel::EqDom<MinusView,IntView>);
00392 
00393     GECODE_REGISTER1(Rel::NaryEqBnd<IntView>);
00394     GECODE_REGISTER1(Rel::NaryEqDom<IntView>);
00395 
00396     GECODE_REGISTER2(Rel::ReEqDomInt<IntView,NegBoolView>);
00397     GECODE_REGISTER2(Rel::ReEqDomInt<IntView,BoolView>);
00398     GECODE_REGISTER2(Rel::ReEqDom<IntView,NegBoolView>);
00399     GECODE_REGISTER2(Rel::ReEqDom<IntView,BoolView>);
00400 
00401     GECODE_REGISTER2(Rel::ReEqBndInt<IntView,NegBoolView>);
00402     GECODE_REGISTER2(Rel::ReEqBndInt<IntView,BoolView>);
00403     GECODE_REGISTER2(Rel::ReEqBnd<IntView,NegBoolView>);
00404     GECODE_REGISTER2(Rel::ReEqBnd<IntView,BoolView>);
00405 
00406     GECODE_REGISTER1(Rel::NaryNq<BoolView>);
00407     GECODE_REGISTER1(Rel::NaryNq<IntView>);
00408 
00409     GECODE_REGISTER1(Rel::Nq<BoolView>);
00410     GECODE_REGISTER1(Rel::Nq<IntView>);
00411     GECODE_REGISTER1(Rel::Nq<OffsetView>);
00412 
00413     GECODE_REGISTER1(Rel::Lq<BoolView>);
00414     GECODE_REGISTER1(Rel::Lq<IntView>);
00415     GECODE_REGISTER1(Rel::Lq<MinusView>);
00416     GECODE_REGISTER1(Rel::Le<BoolView>);
00417     GECODE_REGISTER1(Rel::Le<IntView>);
00418     GECODE_REGISTER2(Rel::ReLq<IntView, NegBoolView>);
00419     GECODE_REGISTER2(Rel::ReLq<IntView, BoolView>);
00420     GECODE_REGISTER2(Rel::ReLqInt<IntView, NegBoolView>);
00421     GECODE_REGISTER2(Rel::ReLqInt<IntView, BoolView>);
00422 
00423     GECODE_REGISTER1(Rel::Lex<BoolView>);
00424     GECODE_REGISTER1(Rel::Lex<IntView>);
00425 
00426   }
00427 
00428 }
00429 
00430 // STATISTICS: int-post
00431