projection.cc

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: 2007-09-13 17:50:04 +0200 (Thu, 13 Sep 2007) $ by $Author: tack $
00011  *     $Revision: 5028 $
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 #include "gecode/set/projectors.hh"
00040 #include "gecode/minimodel.hh"
00041 
00042 using namespace Gecode;
00043 
00044 namespace Test { namespace Set {
00045 
00047   namespace Projection {
00048 
00054 
00055     static IntSet ds_22(-2,2);
00056     static IntSet ds_33(-3,3);
00057 
00059     class RelBinNEq : public SetTest {
00060     public:
00062       RelBinNEq(const char* t)
00063         : SetTest(t,2,ds_33) {}
00065       virtual bool solution(const SetAssignment& x) const {
00066         CountableSetRanges xr0(x.lub, x[0]);
00067         CountableSetRanges xr1(x.lub, x[1]);
00068         return !Iter::Ranges::equal(xr0, xr1);
00069       }
00071       virtual void post(Space* home, SetVarArray& x, IntVarArray&) {
00072         Gecode::Projector p(0, Gecode::SetExpr(1), Gecode::SetExpr(1));
00073         Gecode::Projector q(1, Gecode::SetExpr(0), Gecode::SetExpr(0));
00074         Gecode::ProjectorSet ps(2);
00075         ps.add(p); ps.add(q);
00076         Gecode::projector(home, x[0], x[1], ps, true);
00077       }
00078     };
00079     RelBinNEq _relneq("Proj::Rel::BinNEq");
00080 
00082     class RelBinEq : public SetTest {
00083     public:
00085       RelBinEq(const char* t)
00086         : SetTest(t,2,ds_33,true) {}
00088       virtual bool solution(const SetAssignment& x) const {
00089         CountableSetRanges xr0(x.lub, x[0]);
00090         CountableSetRanges xr1(x.lub, x[1]);
00091         return Iter::Ranges::equal(xr0, xr1);
00092       }
00094       virtual void post(Space* home, SetVarArray& x, IntVarArray&) {
00095         Gecode::SetExpr xe(0);
00096         Gecode::SetExpr ye(1);
00097         Gecode::Projector p(0, ye, ye);
00098         Gecode::Projector q(1, xe, xe);
00099         Gecode::ProjectorSet ps(2);
00100         ps.add(p);
00101         ps.add(q);
00102         Gecode::projector(home, x[0], x[1], ps);
00103       }
00105       virtual void post(Space* home, SetVarArray& x, IntVarArray&,
00106                         BoolVar b) {
00107         Gecode::Projector p(0, Gecode::SetExpr(1), Gecode::SetExpr(1));
00108         Gecode::Projector q(1, Gecode::SetExpr(0), Gecode::SetExpr(0));
00109         Gecode::ProjectorSet ps(2);
00110         ps.add(p); ps.add(q);
00111         Gecode::projector(home, x[0], x[1], b, ps);
00112       }
00113     };
00114     RelBinEq _releq("Proj::Rel::BinEq");
00115 
00117     class RelBinSub : public SetTest {
00118     public:
00120       RelBinSub(const char* t)
00121         : SetTest(t,2,ds_33,true) {}
00123       virtual bool solution(const SetAssignment& x) const {
00124         CountableSetRanges xr0(x.lub, x[0]);
00125         CountableSetRanges xr1(x.lub, x[1]);
00126         return Iter::Ranges::subset(xr0, xr1);
00127       }
00129       virtual void post(Space* home, SetVarArray& x, IntVarArray&) {
00130         Gecode::Projector p(0, Gecode::SetExpr(), Gecode::SetExpr(1));
00131         Gecode::Projector q(1, Gecode::SetExpr(0), -Gecode::SetExpr());
00132         Gecode::ProjectorSet ps(2);
00133         ps.add(p); ps.add(q);
00134         Gecode::projector(home, x[0], x[1], ps);
00135       }
00137       virtual void post(Space* home, SetVarArray& x, IntVarArray&,  
00138                         BoolVar b) {
00139         Gecode::Projector p(0, Gecode::SetExpr(), Gecode::SetExpr(1));
00140         Gecode::Projector q(1, Gecode::SetExpr(0), -Gecode::SetExpr());
00141         Gecode::ProjectorSet ps(2);
00142         ps.add(p); ps.add(q);
00143         Gecode::projector(home, x[0], x[1], b, ps);
00144       }
00145     };
00146     RelBinSub _relsub("Proj::Rel::BinSub");
00147 
00149     class RelBinDisj : public SetTest {
00150     public:
00152       RelBinDisj(const char* t)
00153         : SetTest(t,2,ds_33,true) {}
00155       virtual bool solution(const SetAssignment& x) const {
00156         CountableSetRanges xr0(x.lub, x[0]);
00157         CountableSetRanges xr1(x.lub, x[1]);
00158         return Iter::Ranges::disjoint(xr0, xr1);
00159       }
00161       virtual void post(Space* home, SetVarArray& x, IntVarArray&) {
00162         Gecode::Projector p(0, Gecode::SetExpr(), -Gecode::SetExpr(1));
00163         Gecode::Projector q(1, Gecode::SetExpr(), -Gecode::SetExpr(0));
00164         Gecode::ProjectorSet ps(2);
00165         ps.add(p); ps.add(q);
00166         Gecode::projector(home, x[0], x[1], ps);
00167       }
00169       virtual void post(Space* home, SetVarArray& x, IntVarArray&,
00170                         BoolVar b) {
00171         Gecode::Projector p(0, Gecode::SetExpr(), -Gecode::SetExpr(1));
00172         Gecode::Projector q(1, Gecode::SetExpr(), -Gecode::SetExpr(0));
00173         Gecode::ProjectorSet ps(2);
00174         ps.add(p); ps.add(q);
00175         Gecode::projector(home, x[0], x[1], b, ps);
00176       }
00177     };
00178     RelBinDisj _reldisj("Proj::Rel::BinDisj");
00179 
00181     class RelBinCompl : public SetTest {
00182     public:
00184       RelBinCompl(const char* t)
00185       : SetTest(t,2,ds_33,true) {}
00187       virtual bool solution(const SetAssignment& x) const {
00188         CountableSetRanges xr0(x.lub, x[0]);
00189         CountableSetRanges xr1(x.lub, x[1]);
00190         Gecode::Set::RangesCompl<CountableSetRanges> xr1c(xr1);
00191         return Iter::Ranges::equal(xr0, xr1c);
00192       }
00194       virtual void post(Space* home, SetVarArray& x, IntVarArray&) {
00195         Gecode::Projector p(0, -Gecode::SetExpr(1), -Gecode::SetExpr(1));
00196         Gecode::Projector q(1, -Gecode::SetExpr(0), -Gecode::SetExpr(0));
00197         Gecode::ProjectorSet ps(2);
00198         ps.add(p); ps.add(q);
00199         Gecode::projector(home, x[0], x[1], ps);
00200       }
00202       virtual void post(Space* home, SetVarArray& x, IntVarArray&,
00203                         BoolVar b) {
00204         Gecode::Projector p(0, -Gecode::SetExpr(1), -Gecode::SetExpr(1));
00205         Gecode::Projector q(1, -Gecode::SetExpr(0), -Gecode::SetExpr(0));
00206         Gecode::ProjectorSet ps(2);
00207         ps.add(p); ps.add(q);
00208         Gecode::projector(home, x[0], x[1], b, ps);
00209       }
00210     };
00211     RelBinCompl _relcompl("Proj::Rel::BinCompl");
00212 
00214     class RelUnionEq : public SetTest {
00215     public:
00217       RelUnionEq(const char* t)
00218         : SetTest(t,3,ds_22,true) {}
00220       virtual bool solution(const SetAssignment& x) const {
00221         CountableSetRanges xr0(x.lub, x[0]);
00222         CountableSetRanges xr1(x.lub, x[1]);
00223         CountableSetRanges xr2(x.lub, x[2]);
00224         Iter::Ranges::Union<CountableSetRanges, CountableSetRanges> 
00225           u(xr0,xr1);
00226         return Iter::Ranges::equal(xr2, u);
00227       }
00229       virtual void post(Space* home, SetVarArray& x, IntVarArray&) {
00230         Gecode::Projector p0(0,
00231                              Gecode::SetExpr(2) - Gecode::SetExpr(1),
00232                              Gecode::SetExpr(2)
00233                              );
00234         Gecode::Projector p1(1,
00235                              Gecode::SetExpr(2) - Gecode::SetExpr(0),
00236                              Gecode::SetExpr(2)
00237                              );
00238         Gecode::Projector p2(2,
00239                              Gecode::SetExpr(0) || Gecode::SetExpr(1),
00240                              Gecode::SetExpr(0) || Gecode::SetExpr(1)
00241                              );
00242         Gecode::ProjectorSet ps(3);
00243         ps.add(p0); ps.add(p1); ps.add(p2);
00244         Gecode::projector(home, x[0], x[1], x[2], ps);
00245 
00246         IntVar x0c(home, 0, 10);
00247         IntVar x1c(home, 0, 10);
00248         IntVar x2c(home, 0, 10);
00249         Gecode::cardinality(home, x[0], x0c);
00250         Gecode::cardinality(home, x[1], x1c);
00251         Gecode::cardinality(home, x[2], x2c);
00252 
00253         Gecode::Projector p3(2,
00254                              Gecode::SetExpr(0) && Gecode::SetExpr(1),
00255                              Gecode::SetExpr(0) && Gecode::SetExpr(1)
00256                              );
00257         IntVar x0ix1c(home, 0, 20);
00258         Gecode::projector(home, x[0], x[1], x[2], x0ix1c, p3);
00260         Gecode::post(home, x2c == x0c + x1c - x0ix1c);
00261 
00262         Gecode::Projector p4(2,
00263                              Gecode::SetExpr(0) - Gecode::SetExpr(1),
00264                              Gecode::SetExpr(0) - Gecode::SetExpr(1)
00265                              );
00266         IntVar x0mx1c(home, 0, 20);
00267         Gecode::projector(home, x[0], x[1], x[2], x0mx1c, p4);
00269         Gecode::post(home, x1c == x2c - x0mx1c);
00270 
00271         Gecode::Projector p5(2,
00272                              Gecode::SetExpr(1) - Gecode::SetExpr(0),
00273                              Gecode::SetExpr(1) - Gecode::SetExpr(0)
00274                              );
00275         IntVar x1mx0c(home, 0, 20);
00276         Gecode::projector(home, x[0], x[1], x[2], x1mx0c, p5);
00278         Gecode::post(home, x0c == x2c - x1mx0c);
00279       }
00281       virtual void post(Space* home, SetVarArray& x, IntVarArray&,
00282                         BoolVar b) {
00283         Gecode::Projector p0(0,
00284                              Gecode::SetExpr(2) - Gecode::SetExpr(1),
00285                              Gecode::SetExpr(2)
00286                              );
00287         Gecode::Projector p1(1,
00288                              Gecode::SetExpr(2) - Gecode::SetExpr(0),
00289                              Gecode::SetExpr(2)
00290                              );
00291         Gecode::Projector p2(2,
00292                              Gecode::SetExpr(0) || Gecode::SetExpr(1),
00293                              Gecode::SetExpr(0) || Gecode::SetExpr(1)
00294                              );
00295         Gecode::ProjectorSet ps(3);
00296         ps.add(p0); ps.add(p1); ps.add(p2);
00297         Gecode::projector(home, x[0], x[1], x[2], b, ps);
00298       }
00299     };
00300     RelUnionEq _relunioneq("Proj::RelOp::UnionEq");
00301 
00303     class RelUnionEqFormula : public SetTest {
00304     public:
00306       RelUnionEqFormula(const char* t)
00307         : SetTest(t,3,ds_22,false) {}
00309       virtual bool solution(const SetAssignment& x) const {
00310         CountableSetRanges xr0(x.lub, x[0]);
00311         CountableSetRanges xr1(x.lub, x[1]);
00312         CountableSetRanges xr2(x.lub, x[2]);
00313         Iter::Ranges::Union<CountableSetRanges, CountableSetRanges> 
00314           u(xr0,xr1);
00315         return Iter::Ranges::equal(xr2, u);
00316       }
00318       virtual void post(Space* home, SetVarArray& x, IntVarArray&) {
00319         Formula f = (Formula(0) | Formula(1)) == Formula(2);
00320         Gecode::ProjectorSet ps = f.projectors();
00321         Gecode::projector(home, x[0], x[1], x[2], ps);
00322       }
00323     };
00324     RelUnionEqFormula _relunioneqfor("Proj::Formula::RelOp::UnionEq");
00325 
00327     class RelInterEqCard : public SetTest {
00328     public:
00330       RelInterEqCard(const char* t)
00331         : SetTest(t,3,ds_22,false) {}
00333       virtual bool solution(const SetAssignment& x) const {
00334         CountableSetRanges xr0(x.lub, x[0]);
00335         CountableSetRanges xr1(x.lub, x[1]);
00336         CountableSetRanges xr2(x.lub, x[2]);
00337         Iter::Ranges::Inter<CountableSetRanges, CountableSetRanges> 
00338           u(xr0,xr1);
00339         return Iter::Ranges::equal(xr2, u);
00340       }
00342       virtual void post(Space* home, SetVarArray& x, IntVarArray&) {
00343         Gecode::Projector p0(0,
00344                              Gecode::SetExpr(2),
00345                              Gecode::SetExpr(2) || -Gecode::SetExpr(1)
00346                              );
00347         Gecode::Projector p1(1,
00348                              Gecode::SetExpr(2),
00349                              Gecode::SetExpr(2) || -Gecode::SetExpr(0)
00350                              );
00351         Gecode::Projector p2(2,
00352                              Gecode::SetExpr(0) && Gecode::SetExpr(1),
00353                              Gecode::SetExpr(0) && Gecode::SetExpr(1)
00354                              );
00355         Gecode::ProjectorSet ps(3);
00356         ps.add(p0); ps.add(p1); ps.add(p2);
00357         Gecode::projector(home, x[0], x[1], x[2], ps);
00358 
00359         IntVar x0c(home, 0, 10);
00360         IntVar x1c(home, 0, 10);
00361         IntVar x2c(home, 0, 10);
00362         Gecode::cardinality(home, x[0], x0c);
00363         Gecode::cardinality(home, x[1], x1c);
00364         Gecode::cardinality(home, x[2], x2c);
00365 
00366         Gecode::Projector p3(2,
00367                              Gecode::SetExpr(0) || Gecode::SetExpr(1),
00368                              Gecode::SetExpr(0) || Gecode::SetExpr(1)
00369                              );
00370         IntVar x0ux1c(home, 0, 20);
00371         Gecode::projector(home, x[0], x[1], x[2], x0ux1c, p3);
00373         Gecode::post(home, x2c == x0c + x1c - x0ux1c);
00374 
00375         Gecode::Projector p4(2,
00376                              Gecode::SetExpr(0) - Gecode::SetExpr(1),
00377                              Gecode::SetExpr(0) - Gecode::SetExpr(1)
00378                              );
00379         IntVar x0mx1c(home, 0, 20);
00380         Gecode::projector(home, x[0], x[1], x[2], x0mx1c, p4);
00382         Gecode::post(home, x2c == x0c - x0mx1c);
00383 
00384         Gecode::Projector p5(2,
00385                              Gecode::SetExpr(1) - Gecode::SetExpr(0),
00386                              Gecode::SetExpr(1) - Gecode::SetExpr(0)
00387                              );
00388         IntVar x1mx0c(home, 0, 20);
00389         Gecode::projector(home, x[0], x[1], x[2], x1mx0c, p5);
00391         Gecode::post(home, x2c == x1c - x1mx0c);
00392 
00393       }
00394     };
00395     RelInterEqCard _relintereqcard("Proj::RelOp::InterEqCard");
00396 
00398     class NegRelUnionEq : public SetTest {
00399     public:
00401       NegRelUnionEq(const char* t)
00402         : SetTest(t,3,ds_22) {}
00404       virtual bool solution(const SetAssignment& x) const {
00405         CountableSetRanges xr0(x.lub, x[0]);
00406         CountableSetRanges xr1(x.lub, x[1]);
00407         CountableSetRanges xr2(x.lub, x[2]);
00408         Iter::Ranges::Union<CountableSetRanges, CountableSetRanges> 
00409           u(xr0,xr1);
00410         return !Iter::Ranges::equal(xr2, u);
00411       }
00413       virtual void post(Space* home, SetVarArray& x, IntVarArray&) {
00414         Gecode::Projector p0(0,
00415                              Gecode::SetExpr(2) - Gecode::SetExpr(1),
00416                              Gecode::SetExpr(2)
00417                              );
00418         Gecode::Projector p1(1,
00419                              Gecode::SetExpr(2) - Gecode::SetExpr(0),
00420                              Gecode::SetExpr(2)
00421                              );
00422         Gecode::Projector p2(2,
00423                              Gecode::SetExpr(0) || Gecode::SetExpr(1),
00424                              Gecode::SetExpr(0) || Gecode::SetExpr(1)
00425                              );
00426         Gecode::ProjectorSet ps(3);
00427         ps.add(p0); ps.add(p1); ps.add(p2);
00428         Gecode::projector(home, x[0], x[1], x[2], ps, true);
00429       }
00430     };
00431 
00432     NegRelUnionEq _negrelunioneq("Proj::RelOp::NegUnionEq");
00433 
00434 }}}
00435 
00436 // STATISTICS: test-set