Generated on Mon May 10 06:46:45 2010 for Gecode by doxygen 1.6.3

rel-op.cpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Guido Tack <tack@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Guido Tack, 2005
00008  *
00009  *  Last modified:
00010  *     $Date: 2010-04-08 12:35:31 +0200 (Thu, 08 Apr 2010) $ by $Author: schulte $
00011  *     $Revision: 10684 $
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 "test/set.hh"
00039 
00040 using namespace Gecode;
00041 
00042 namespace Test { namespace Set {
00043 
00045   namespace RelOp {
00046 
00052 
00053     static IntSet ds_22(-2,2);
00054     static IntSet ds_12(-1,2);
00055 
00057     class Rel : public SetTest {
00058     private:
00059       Gecode::SetOpType  sot;
00060       Gecode::SetRelType srt;
00061       int share;
00062 
00063       template<class I, class J>
00064       bool
00065       sol(I& i, J& j) const {
00066         Iter::Ranges::IsRangeIter<I>();
00067         Iter::Ranges::IsRangeIter<J>();
00068         switch (srt) {
00069         case SRT_EQ: return Iter::Ranges::equal(i,j);
00070         case SRT_NQ: return !Iter::Ranges::equal(i,j);
00071         case SRT_SUB: return Iter::Ranges::subset(i,j);
00072         case SRT_SUP: return Iter::Ranges::subset(j,i);
00073         case SRT_DISJ:
00074           {
00075             Gecode::Iter::Ranges::Inter<I,J> inter(i,j);
00076             return !inter();
00077           }
00078         case SRT_CMPL:
00079           {
00080             Gecode::Set::RangesCompl<J> jc(j);
00081             return Iter::Ranges::equal(i,jc);
00082           }
00083         }
00084         GECODE_NEVER;
00085         return false;
00086       }
00087 
00088     public:
00090       Rel(Gecode::SetOpType sot0, Gecode::SetRelType srt0, int share0=0)
00091         : SetTest("RelOp::"+str(sot0)+"::"+str(srt0)+"::S"+str(share0),
00092                   share0 == 0 ? 3 : 2,ds_22,false)
00093         , sot(sot0), srt(srt0), share(share0) {}
00095       bool solution(const SetAssignment& x) const {
00096         int a,b,c;
00097         switch (share) {
00098           case 0: a=x[0]; b=x[1]; c=x[2]; break;
00099           case 1: a=x[0]; b=x[0]; c=x[0]; break;
00100           case 2: a=x[0]; b=x[0]; c=x[1]; break;
00101           case 3: a=x[0]; b=x[1]; c=x[0]; break;
00102           case 4: a=x[0]; b=x[1]; c=x[1]; break;
00103         }
00104         CountableSetRanges xr0(x.lub, a);
00105         CountableSetRanges xr1(x.lub, b);
00106         CountableSetRanges xr2(x.lub, c);
00107         switch (sot) {
00108         case SOT_UNION:
00109           {
00110             Iter::Ranges::Union<CountableSetRanges, CountableSetRanges>
00111               u(xr0,xr1);
00112             return sol(u,xr2);
00113           }
00114           break;
00115         case SOT_DUNION:
00116           {
00117             Iter::Ranges::Inter<CountableSetRanges, CountableSetRanges>
00118               inter(xr0,xr1);
00119             if (inter())
00120               return false;
00121             Iter::Ranges::Union<CountableSetRanges, CountableSetRanges>
00122               u(xr0,xr1);
00123             return sol(u,xr2);
00124           }
00125           break;
00126         case SOT_INTER:
00127           {
00128             Iter::Ranges::Inter<CountableSetRanges, CountableSetRanges>
00129               u(xr0,xr1);
00130             return sol(u,xr2);
00131           }
00132           break;
00133         case SOT_MINUS:
00134           {
00135             Iter::Ranges::Diff<CountableSetRanges, CountableSetRanges>
00136               u(xr0,xr1);
00137             return sol(u,xr2);
00138           }
00139           break;
00140         }
00141         GECODE_NEVER;
00142         return false;
00143       }
00145       void post(Space& home, SetVarArray& x, IntVarArray&) {
00146         SetVar a,b,c;
00147         switch (share) {
00148           case 0: a=x[0]; b=x[1]; c=x[2]; break;
00149           case 1: a=x[0]; b=x[0]; c=x[0]; break;
00150           case 2: a=x[0]; b=x[0]; c=x[1]; break;
00151           case 3: a=x[0]; b=x[1]; c=x[0]; break;
00152           case 4: a=x[0]; b=x[1]; c=x[1]; break;
00153         }
00154         Gecode::rel(home, a, sot, b, srt, c);
00155       }
00156     };
00157 
00159     class Create {
00160     public:
00162       Create(void) {
00163         using namespace Gecode;
00164         for (SetRelTypes srts; srts(); ++srts) {
00165           for (SetOpTypes sots; sots(); ++sots) {
00166             for (int i=0; i<=4; i++) {
00167               (void) new Rel(sots.sot(),srts.srt(),i);
00168             }
00169           }
00170         }
00171       }
00172     };
00173 
00174     Create c;
00175 
00177     class RelN : public SetTest {
00178     private:
00179       Gecode::SetOpType sot;
00180       int n;
00181       int shared;
00182       bool withConst;
00183       IntSet is;
00184     public:
00186       RelN(Gecode::SetOpType sot0, int n0, int shared0, bool withConst0)
00187         : SetTest("RelOp::N::"+str(sot0)+"::"+str(n0)+"::S"+str(shared0)+
00188                   "::C"+str(withConst0 ? 1 : 0),
00189                   shared0 == 0 ? n0+1 : (shared0 <= 2 ? 3 : 2),ds_12,false)
00190         , sot(sot0), n(n0), shared(shared0), withConst(withConst0)
00191         , is(0,1) {}
00193       bool solution(const SetAssignment& x) const {
00194         int realN = shared == 0 ? n : 3;
00195 
00196         CountableSetRanges* isrs = new CountableSetRanges[realN];
00197 
00198         switch (shared) {
00199         case 0:
00200           for (int i=realN; i--; )
00201             isrs[i].init(x.lub, x[i]);
00202           break;
00203         case 1:
00204           isrs[0].init(x.lub, x[0]);
00205           isrs[1].init(x.lub, x[0]);
00206           isrs[2].init(x.lub, x[1]);
00207           break;
00208         case 2:
00209           isrs[0].init(x.lub, x[0]);
00210           isrs[1].init(x.lub, x[1]);
00211           isrs[2].init(x.lub, x[2]);
00212           break;
00213         case 3:
00214           isrs[0].init(x.lub, x[0]);
00215           isrs[1].init(x.lub, x[1]);
00216           isrs[2].init(x.lub, x[0]);
00217           break;
00218         default:
00219           GECODE_NEVER;
00220         }
00221 
00222         int result = shared == 0 ? x.size() - 1 : (shared <= 2 ? 2 : 0);
00223         CountableSetRanges xnr(x.lub, x[result]);
00224 
00225         switch (sot) {
00226         case SOT_DUNION:
00227           {
00228             if (shared == 1 && (isrs[0]() || isrs[1]())) {
00229               delete[] isrs; return false;
00230             }
00231             if (shared == 3 && (isrs[0]() || isrs[2]())) {
00232               delete[] isrs; return false;
00233             }
00234             unsigned int cardSum = 0;
00235             if (shared == 1 || shared == 3) {
00236               CountableSetRanges x1r(x.lub, x[1]);
00237               cardSum = Iter::Ranges::size(x1r);
00238             } else {
00239               for (int i=0; i<realN; i++) {
00240                 CountableSetRanges xir(x.lub, x[i]);
00241                 cardSum += Iter::Ranges::size(xir);
00242               }
00243             }
00244             if (withConst)
00245               cardSum += 2;
00246             CountableSetRanges xnr2(x.lub, x[result]);
00247             if (cardSum != Iter::Ranges::size(xnr2)) {
00248               delete[] isrs; return false;
00249             }
00250           }
00251           // fall through to union case
00252         case SOT_UNION:
00253           {
00254             if (withConst) {
00255               Iter::Ranges::NaryUnion<CountableSetRanges> u(isrs, realN);
00256               IntSetRanges isr(is);
00257               Iter::Ranges::Union<IntSetRanges,
00258                 Iter::Ranges::NaryUnion<CountableSetRanges> > uu(isr, u);
00259               bool eq = Iter::Ranges::equal(uu, xnr);
00260               delete[] isrs;
00261               return eq;
00262             } else {
00263               Iter::Ranges::NaryUnion<CountableSetRanges> u(isrs, realN);
00264               bool eq = Iter::Ranges::equal(u, xnr);
00265               delete[] isrs;
00266               return eq;
00267             }
00268           }
00269         case SOT_INTER:
00270           {
00271             if (withConst) {
00272               Iter::Ranges::NaryInter<CountableSetRanges> u(isrs, realN);
00273               IntSetRanges isr(is);
00274               Iter::Ranges::Inter<IntSetRanges,
00275                 Iter::Ranges::NaryInter<CountableSetRanges> > uu(isr, u);
00276               bool eq = (realN == 0 ? Iter::Ranges::equal(isr, xnr) :
00277                                       Iter::Ranges::equal(uu, xnr));
00278               delete[] isrs;
00279               return eq;
00280             } else {
00281               if (realN == 0) {
00282                 bool ret =
00283                   Iter::Ranges::size(xnr) ==  Gecode::Set::Limits::card;
00284                 delete[] isrs;
00285                 return ret;
00286               } else {
00287                 Iter::Ranges::NaryInter<CountableSetRanges> u(isrs, realN);
00288                 bool eq = Iter::Ranges::equal(u, xnr);
00289                 delete[] isrs;
00290                 return eq;
00291               }
00292             }
00293           }
00294         default:
00295           GECODE_NEVER;
00296         }
00297         GECODE_NEVER;
00298         return false;
00299       }
00301       void post(Space& home, SetVarArray& x, IntVarArray&) {
00302         int size = shared == 0 ? x.size()-1 : 3;
00303         SetVarArgs xs(size);
00304         SetVar xn;
00305         switch (shared) {
00306         case 0:
00307           for (int i=x.size()-1; i--;)
00308             xs[i]=x[i];
00309           xn = x[x.size()-1];
00310           break;
00311         case 1:
00312           xs[0] = x[0]; xs[1] = x[0]; xs[2] = x[1]; xn = x[2];
00313           break;
00314         case 2:
00315           xs[0] = x[0]; xs[1] = x[1]; xs[2] = x[2]; xn = x[2];
00316           break;
00317         case 3:
00318           xs[0] = x[0]; xs[1] = x[1]; xs[2] = x[0]; xn = x[0];
00319           break;
00320         default:
00321           GECODE_NEVER;
00322           break;
00323         }
00324         if (!withConst)
00325           Gecode::rel(home, sot, xs, xn);
00326         else
00327           Gecode::rel(home, sot, xs, is, xn);
00328       }
00329     };
00330 
00332     class CreateN {
00333     public:
00335       CreateN(void) {
00336         for (int wc=0; wc<=1; wc++) {
00337           for (int i=0; i<=3; i++) {
00338             (void) new RelN(Gecode::SOT_UNION, i, 0, wc);
00339             (void) new RelN(Gecode::SOT_DUNION, i, 0, wc);
00340             (void) new RelN(Gecode::SOT_INTER, i, 0, wc);
00341 
00342             if (i>0) {
00343               (void) new RelN(Gecode::SOT_UNION, 0, i, wc);
00344               (void) new RelN(Gecode::SOT_DUNION, 0, i, wc);
00345               (void) new RelN(Gecode::SOT_INTER, 0, i, wc);
00346             }
00347           }
00348         }
00349       }
00350     };
00351 
00352     CreateN cn;
00353 
00355     class RelIntN : public SetTest {
00356     private:
00357       Gecode::SetOpType sot;
00358       int n;
00359       bool withConst;
00360       IntSet is;
00361     public:
00363       RelIntN(Gecode::SetOpType sot0, int n0, bool withConst0)
00364         : SetTest("RelOp::IntN::"+str(sot0)+"::"+str(n0)+
00365                   "::C"+str(withConst0 ? 1 : 0),
00366                   1,ds_12,false,n0)
00367         , sot(sot0), n(n0), withConst(withConst0)
00368         , is(0,1) {}
00370       bool solution(const SetAssignment& x) const {
00371         int* isrs = new int[n];
00372         for (int i=0; i<n; i++)
00373           isrs[i] = x.ints()[i];
00374 
00375         IntSet iss(isrs,n);
00376         CountableSetRanges xnr(x.lub, x[0]);
00377 
00378         switch (sot) {
00379         case SOT_DUNION:
00380           {
00381             IntSetRanges issr(iss);
00382             unsigned int cardSum = Iter::Ranges::size(issr);
00383             if (cardSum != static_cast<unsigned int>(n)) {
00384               delete[] isrs;
00385               return false;
00386             }
00387             if (withConst) {
00388               IntSetRanges isr(is);
00389               cardSum += Iter::Ranges::size(isr);
00390             }
00391             CountableSetRanges xnr2(x.lub, x[0]);
00392             if (cardSum != Iter::Ranges::size(xnr2)) {
00393               delete[] isrs;
00394               return false;
00395             }
00396           }
00397           // fall through to union case
00398         case SOT_UNION:
00399           {
00400             if (withConst) {
00401               IntSetRanges issr(iss);
00402               IntSetRanges isr(is);
00403               Iter::Ranges::Union<IntSetRanges,IntSetRanges > uu(isr, issr);
00404               delete[] isrs;
00405               return Iter::Ranges::equal(uu, xnr);
00406             } else {
00407               IntSetRanges issr(iss);
00408               delete[] isrs;
00409               return Iter::Ranges::equal(issr, xnr);
00410             }
00411           }
00412         case SOT_INTER:
00413           {
00414             bool allEqual = true;
00415             for (int i=1; i<n; i++) {
00416               if (isrs[i] != isrs[0]) {
00417                 allEqual = false;
00418                 break;
00419               }
00420             }
00421             if (withConst) {
00422               if (allEqual) {
00423                 if (n == 0) {
00424                   IntSetRanges isr(is);
00425                   delete[] isrs;
00426                   return Iter::Ranges::equal(isr, xnr);
00427                 } else {
00428                   Iter::Ranges::Singleton s(isrs[0],isrs[0]);
00429                   IntSetRanges isr(is);
00430                   Iter::Ranges::Inter<IntSetRanges,Iter::Ranges::Singleton>
00431                     uu(isr, s);
00432                   delete[] isrs;
00433                   return Iter::Ranges::equal(uu, xnr);
00434                 }
00435               } else {
00436                 delete[] isrs;
00437                 return Iter::Ranges::size(xnr) == 0;
00438               }
00439             } else {
00440               if (allEqual) {
00441                 if (n == 0) {
00442                   delete[] isrs;
00443                   return Iter::Ranges::size(xnr) == Gecode::Set::Limits::card;
00444                 } else {
00445                   Iter::Ranges::Singleton s(isrs[0],isrs[0]);
00446                   delete[] isrs;
00447                   return Iter::Ranges::equal(s, xnr);
00448                 }
00449               } else {
00450                 delete[] isrs;
00451                 return Iter::Ranges::size(xnr) == 0;
00452               }
00453             }
00454           }
00455         default:
00456           GECODE_NEVER;
00457         }
00458         GECODE_NEVER;
00459         return false;
00460       }
00462       void post(Space& home, SetVarArray& x, IntVarArray& y) {
00463         if (!withConst)
00464           Gecode::rel(home, sot, y, x[0]);
00465         else
00466           Gecode::rel(home, sot, y, is, x[0]);
00467       }
00468     };
00469 
00471     class CreateIntN {
00472     public:
00474       CreateIntN(void) {
00475         for (int wc=0; wc<=1; wc++) {
00476           for (int i=0; i<=3; i++) {
00477             (void) new RelIntN(Gecode::SOT_UNION, i, wc);
00478             (void) new RelIntN(Gecode::SOT_DUNION, i, wc);
00479             (void) new RelIntN(Gecode::SOT_INTER, i, wc);
00480           }
00481         }
00482       }
00483     };
00484 
00485     CreateIntN intcn;
00486 
00488 
00489 }}}
00490 
00491 // STATISTICS: test-set