Generated on Tue May 22 09:39:48 2018 for Gecode by doxygen 1.6.3

rel.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  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00031  *
00032  */
00033 
00034 #include <gecode/minimodel.hh>
00035 
00036 #include "test/set.hh"
00037 
00038 using namespace Gecode;
00039 
00040 namespace Test { namespace Set {
00041 
00043   namespace Rel {
00044 
00050 
00051     static IntSet ds_33(-3,3);
00052     static IntSet ds_03(0,3);
00053 
00055     class RelBin : public SetTest {
00056     private:
00057       Gecode::SetRelType srt;
00058       bool shared;
00059     public:
00061       RelBin(Gecode::SetRelType srt0, bool shared0)
00062         : SetTest("Rel::Bin::"+str(srt0)+"::S"+(shared0 ? "1":"0"),
00063                   shared0 ? 1 : 2,ds_33,true)
00064         , srt(srt0), shared(shared0){}
00065       int minSymDiff(const SetAssignment& x) const {
00066         int x1 = shared ? x[0] : x[1];
00067         typedef Iter::Ranges::Diff<CountableSetRanges,CountableSetRanges> Diff;
00068         CountableSetRanges xr00(x.lub, x[0]);
00069         CountableSetRanges xr10(x.lub, x1);
00070         Diff a(xr00,xr10);
00071         CountableSetRanges xr01(x.lub, x[0]);
00072         CountableSetRanges xr11(x.lub, x1);
00073         Diff b(xr11,xr01);
00074         Iter::Ranges::Union<Diff,Diff> u(a,b);
00075         return u() ? u.min() : Gecode::Set::Limits::max+1;
00076       }
00077       bool in(int i, CountableSetRanges& c, bool eq=false) const {
00078         if (eq && i==Gecode::Set::Limits::max+1)
00079           return true;
00080         Iter::Ranges::Singleton s(i,i);
00081         return Iter::Ranges::subset(s,c);
00082       }
00084       bool solution(const SetAssignment& x) const {
00085         int x1 = shared ? x[0] : x[1];
00086         CountableSetRanges xr0(x.lub, x[0]);
00087         CountableSetRanges xr1(x.lub, x1);
00088         switch (srt) {
00089         case SRT_EQ: return Iter::Ranges::equal(xr0, xr1);
00090         case SRT_NQ: return !Iter::Ranges::equal(xr0, xr1);
00091 
00092         case SRT_LQ: return (!xr0()) || in(minSymDiff(x),xr1,true);
00093         case SRT_LE: return xr0() ? in(minSymDiff(x),xr1) : xr1();
00094         case SRT_GQ: return (!xr1()) || in(minSymDiff(x),xr0,true);
00095         case SRT_GR: return xr1() ? in(minSymDiff(x),xr0) : xr0();
00096 
00097         case SRT_SUB: return Iter::Ranges::subset(xr0, xr1);
00098         case SRT_SUP: return Iter::Ranges::subset(xr1, xr0);
00099         case SRT_DISJ:
00100           {
00101             Iter::Ranges::Inter<CountableSetRanges,CountableSetRanges>
00102               inter(xr0,xr1);
00103             return !inter();
00104           }
00105         case SRT_CMPL:
00106           {
00107             Gecode::Set::RangesCompl<CountableSetRanges> rc(xr0);
00108             return Iter::Ranges::equal(rc,xr1);
00109           }
00110         default:
00111           GECODE_NEVER;
00112         }
00113         GECODE_NEVER;
00114         return false;
00115       }
00117       void post(Space& home, SetVarArray& x, IntVarArray&) {
00118         if (!shared)
00119           Gecode::rel(home, x[0], srt, x[1]);
00120         else
00121           Gecode::rel(home, x[0], srt, x[0]);
00122       }
00124       void post(Space& home, SetVarArray& x, IntVarArray&, Reify r) {
00125         if (!shared)
00126           Gecode::rel(home, x[0], srt, x[1], r);
00127         else
00128           Gecode::rel(home, x[0], srt, x[0], r);
00129       }
00130     };
00131 
00133     class ITE : public SetTest {
00134     public:
00136       ITE(void)
00137         : SetTest("ITE",3,ds_03,false,1) {}
00139       virtual bool solution(const SetAssignment& x) const {
00140         if ((x.intval() < 0) || (x.intval() > 1))
00141           return false;
00142         if (x.intval() == 1) {
00143           CountableSetRanges xr0(x.lub, x[0]);
00144           CountableSetRanges xr2(x.lub, x[2]);
00145           return Iter::Ranges::equal(xr0,xr2);
00146         } else {
00147           CountableSetRanges xr1(x.lub, x[1]);
00148           CountableSetRanges xr2(x.lub, x[2]);
00149           return Iter::Ranges::equal(xr1,xr2);
00150         }
00151       }
00153       void post(Space& home, SetVarArray& x, IntVarArray& y) {
00154         Gecode::ite(home, Gecode::channel(home,y[0]), x[0], x[1], x[2]);
00155       }
00156     };
00157 
00158     RelBin _relbin_eq(Gecode::SRT_EQ,false);
00159     RelBin _relbin_lq(Gecode::SRT_LQ,false);
00160     RelBin _relbin_le(Gecode::SRT_LE,false);
00161     RelBin _relbin_gq(Gecode::SRT_GQ,false);
00162     RelBin _relbin_gr(Gecode::SRT_GR,false);
00163     RelBin _relbin_nq(Gecode::SRT_NQ,false);
00164     RelBin _relbin_sub(Gecode::SRT_SUB,false);
00165     RelBin _relbin_sup(Gecode::SRT_SUP,false);
00166     RelBin _relbin_disj(Gecode::SRT_DISJ,false);
00167     RelBin _relbin_cmpl(Gecode::SRT_CMPL,false);
00168     RelBin _relbin_shared_eq(Gecode::SRT_EQ,true);
00169     RelBin _relbin_shared_lq(Gecode::SRT_LQ,true);
00170     RelBin _relbin_shared_le(Gecode::SRT_LE,true);
00171     RelBin _relbin_shared_gq(Gecode::SRT_GQ,true);
00172     RelBin _relbin_shared_gr(Gecode::SRT_GR,true);
00173     RelBin _relbin_shared_nq(Gecode::SRT_NQ,true);
00174     RelBin _relbin_shared_sub(Gecode::SRT_SUB,true);
00175     RelBin _relbin_shared_sup(Gecode::SRT_SUP,true);
00176     RelBin _relbin_shared_disj(Gecode::SRT_DISJ,true);
00177     RelBin _relbin_shared_cmpl(Gecode::SRT_CMPL,true);
00178 
00179     ITE _ite;
00181 
00182 }}}
00183 
00184 // STATISTICS: test-set