Generated on Fri Mar 20 15:56:20 2015 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: 2012-09-07 17:31:22 +0200 (Fri, 07 Sep 2012) $ by $Author: schulte $
00011  *     $Revision: 13068 $
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=0, b=0, c=0;
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 u(r, isrs, realN);
00257               IntSetRanges isr(is);
00258               Iter::Ranges::Union<IntSetRanges,
00259                 Iter::Ranges::NaryUnion> uu(isr, u);
00260               eq = Iter::Ranges::equal(uu, xnr);
00261             } else {
00262               Region r(*fs);
00263               Iter::Ranges::NaryUnion 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               FakeSpace* fs = new FakeSpace;
00274               bool eq;
00275               {
00276                 Region r(*fs);
00277                 Iter::Ranges::NaryInter u(r, isrs, realN);
00278                 IntSetRanges isr(is);
00279                 Iter::Ranges::Inter<IntSetRanges,
00280                   Iter::Ranges::NaryInter> uu(isr, u);
00281                 eq = (realN == 0 ? Iter::Ranges::equal(isr, xnr) :
00282                            Iter::Ranges::equal(uu, xnr));
00283                 delete [] isrs;
00284               }
00285               delete fs;
00286               return eq;
00287             } else {
00288               if (realN == 0) {
00289                 bool ret =
00290                   Iter::Ranges::size(xnr) ==  Gecode::Set::Limits::card;
00291                 delete [] isrs;
00292                 return ret;
00293               } else {
00294                 FakeSpace* fs = new FakeSpace;
00295                 bool eq;
00296                 {
00297                   Region r(*fs);
00298                   Iter::Ranges::NaryInter u(r,isrs, realN);
00299                   eq = Iter::Ranges::equal(u, xnr);
00300                 }
00301                 delete [] isrs;
00302                 delete fs;
00303                 return eq;
00304               }
00305             }
00306           }
00307         default:
00308           GECODE_NEVER;
00309         }
00310         GECODE_NEVER;
00311         return false;
00312       }
00314       void post(Space& home, SetVarArray& x, IntVarArray&) {
00315         int size = shared == 0 ? x.size()-1 : 3;
00316         SetVarArgs xs(size);
00317         SetVar xn;
00318         switch (shared) {
00319         case 0:
00320           for (int i=x.size()-1; i--;)
00321             xs[i]=x[i];
00322           xn = x[x.size()-1];
00323           break;
00324         case 1:
00325           xs[0] = x[0]; xs[1] = x[0]; xs[2] = x[1]; xn = x[2];
00326           break;
00327         case 2:
00328           xs[0] = x[0]; xs[1] = x[1]; xs[2] = x[2]; xn = x[2];
00329           break;
00330         case 3:
00331           xs[0] = x[0]; xs[1] = x[1]; xs[2] = x[0]; xn = x[0];
00332           break;
00333         default:
00334           GECODE_NEVER;
00335           break;
00336         }
00337         if (!withConst)
00338           Gecode::rel(home, sot, xs, xn);
00339         else
00340           Gecode::rel(home, sot, xs, is, xn);
00341       }
00342     };
00343 
00345     class CreateN {
00346     public:
00348       CreateN(void) {
00349         for (int wc=0; wc<=1; wc++) {
00350           for (int i=0; i<=3; i++) {
00351             (void) new RelN(Gecode::SOT_UNION, i, 0, wc);
00352             (void) new RelN(Gecode::SOT_DUNION, i, 0, wc);
00353             (void) new RelN(Gecode::SOT_INTER, i, 0, wc);
00354 
00355             if (i>0) {
00356               (void) new RelN(Gecode::SOT_UNION, 0, i, wc);
00357               (void) new RelN(Gecode::SOT_DUNION, 0, i, wc);
00358               (void) new RelN(Gecode::SOT_INTER, 0, i, wc);
00359             }
00360           }
00361         }
00362       }
00363     };
00364 
00365     CreateN cn;
00366 
00368     class RelIntN : public SetTest {
00369     private:
00370       Gecode::SetOpType sot;
00371       int n;
00372       bool withConst;
00373       IntSet is;
00374     public:
00376       RelIntN(Gecode::SetOpType sot0, int n0, bool withConst0)
00377         : SetTest("RelOp::IntN::"+str(sot0)+"::"+str(n0)+
00378                   "::C"+str(withConst0 ? 1 : 0),
00379                   1,ds_12,false,n0)
00380         , sot(sot0), n(n0), withConst(withConst0)
00381         , is(0,1) {}
00383       bool solution(const SetAssignment& x) const {
00384         int* isrs = new int[n];
00385         for (int i=0; i<n; i++)
00386           isrs[i] = x.ints()[i];
00387 
00388         IntSet iss(isrs,n);
00389         CountableSetRanges xnr(x.lub, x[0]);
00390 
00391         switch (sot) {
00392         case SOT_DUNION:
00393           {
00394             IntSetRanges issr(iss);
00395             unsigned int cardSum = Iter::Ranges::size(issr);
00396             if (cardSum != static_cast<unsigned int>(n)) {
00397               delete[] isrs;
00398               return false;
00399             }
00400             if (withConst) {
00401               IntSetRanges isr(is);
00402               cardSum += Iter::Ranges::size(isr);
00403             }
00404             CountableSetRanges xnr2(x.lub, x[0]);
00405             if (cardSum != Iter::Ranges::size(xnr2)) {
00406               delete[] isrs;
00407               return false;
00408             }
00409           }
00410           // fall through to union case
00411         case SOT_UNION:
00412           {
00413             if (withConst) {
00414               IntSetRanges issr(iss);
00415               IntSetRanges isr(is);
00416               Iter::Ranges::Union<IntSetRanges,IntSetRanges > uu(isr, issr);
00417               delete[] isrs;
00418               return Iter::Ranges::equal(uu, xnr);
00419             } else {
00420               IntSetRanges issr(iss);
00421               delete[] isrs;
00422               return Iter::Ranges::equal(issr, xnr);
00423             }
00424           }
00425         case SOT_INTER:
00426           {
00427             bool allEqual = true;
00428             for (int i=1; i<n; i++) {
00429               if (isrs[i] != isrs[0]) {
00430                 allEqual = false;
00431                 break;
00432               }
00433             }
00434             if (withConst) {
00435               if (allEqual) {
00436                 if (n == 0) {
00437                   IntSetRanges isr(is);
00438                   delete[] isrs;
00439                   return Iter::Ranges::equal(isr, xnr);
00440                 } else {
00441                   Iter::Ranges::Singleton s(isrs[0],isrs[0]);
00442                   IntSetRanges isr(is);
00443                   Iter::Ranges::Inter<IntSetRanges,Iter::Ranges::Singleton>
00444                     uu(isr, s);
00445                   delete[] isrs;
00446                   return Iter::Ranges::equal(uu, xnr);
00447                 }
00448               } else {
00449                 delete[] isrs;
00450                 return Iter::Ranges::size(xnr) == 0;
00451               }
00452             } else {
00453               if (allEqual) {
00454                 if (n == 0) {
00455                   delete[] isrs;
00456                   return Iter::Ranges::size(xnr) == Gecode::Set::Limits::card;
00457                 } else {
00458                   Iter::Ranges::Singleton s(isrs[0],isrs[0]);
00459                   delete[] isrs;
00460                   return Iter::Ranges::equal(s, xnr);
00461                 }
00462               } else {
00463                 delete[] isrs;
00464                 return Iter::Ranges::size(xnr) == 0;
00465               }
00466             }
00467           }
00468         default:
00469           GECODE_NEVER;
00470         }
00471         GECODE_NEVER;
00472         return false;
00473       }
00475       void post(Space& home, SetVarArray& x, IntVarArray& y) {
00476         if (!withConst)
00477           Gecode::rel(home, sot, y, x[0]);
00478         else
00479           Gecode::rel(home, sot, y, is, x[0]);
00480       }
00481     };
00482 
00484     class CreateIntN {
00485     public:
00487       CreateIntN(void) {
00488         for (int wc=0; wc<=1; wc++) {
00489           for (int i=0; i<=3; i++) {
00490             (void) new RelIntN(Gecode::SOT_UNION, i, wc);
00491             (void) new RelIntN(Gecode::SOT_DUNION, i, wc);
00492             (void) new RelIntN(Gecode::SOT_INTER, i, wc);
00493           }
00494         }
00495       }
00496     };
00497 
00498     CreateIntN intcn;
00499 
00501 
00502 }}}
00503 
00504 // STATISTICS: test-set