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