distinct.cpp

00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *     Mikael Lagerkvist <lagerkvist@gecode.org>
00006  *
00007  *  Copyright:
00008  *     Christian Schulte, 2005
00009  *     Mikael Lagerkvist, 2006
00010  *
00011  *  This file is part of Gecode, the generic constraint
00012  *  development environment:
00013  *     http://www.gecode.org
00014  *
00015  *  Permission is hereby granted, free of charge, to any person obtaining
00016  *  a copy of this software and associated documentation files (the
00017  *  "Software"), to deal in the Software without restriction, including
00018  *  without limitation the rights to use, copy, modify, merge, publish,
00019  *  distribute, sublicense, and/or sell copies of the Software, and to
00020  *  permit persons to whom the Software is furnished to do so, subject to
00021  *  the following conditions:
00022  *
00023  *  The above copyright notice and this permission notice shall be
00024  *  included in all copies or substantial portions of the Software.
00025  *
00026  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00027  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00028  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00029  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00030  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00031  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00032  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00033  *
00034  */
00035 
00036 #include "test/int.hh"
00037 #include <gecode/minimodel.hh>
00038 
00039 namespace Test { namespace Int {
00040 
00042    namespace Distinct {
00043 
00049 
00050      template<bool useCount>
00051      class Distinct : public Test {
00052      public:
00054        Distinct(const Gecode::IntSet& d0, Gecode::IntPropLevel ipl,
00055                 int n=6)
00056          : Test(std::string(useCount ? "Count::Distinct::" : "Distinct::")+
00057                 str(ipl)+"::Sparse::"+str(n),n,d0,false,ipl) {}
00059        Distinct(int min, int max, Gecode::IntPropLevel ipl)
00060          : Test(std::string(useCount ? "Count::Distinct::" : "Distinct::")+
00061                 str(ipl)+"::Dense",6,min,max,false,ipl) {}
00063        virtual bool solution(const Assignment& x) const {
00064          for (int i=0; i<x.size(); i++)
00065            for (int j=i+1; j<x.size(); j++)
00066              if (x[i]==x[j])
00067                return false;
00068          return true;
00069        }
00071        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00072          if (!useCount) {
00073            Gecode::distinct(home, x, ipl);
00074          } else {
00075            Gecode::IntSetRanges dr(dom);
00076            int i = 0;
00077            Gecode::IntArgs ia(Gecode::Iter::Ranges::size(dr));
00078            for (Gecode::IntSetValues dr2(dom); dr2(); ++dr2)
00079              ia[i++] = dr2.val();
00080            Gecode::count(home, x, Gecode::IntSet(0,1), ia, ipl);
00081          }
00082        }
00083      };
00084 
00086      class Offset : public Test {
00087      public:
00089        Offset(const Gecode::IntSet& d, Gecode::IntPropLevel ipl)
00090          : Test("Distinct::Offset::Sparse::"+str(ipl),6,d,false,ipl) {}
00092        Offset(int min, int max, Gecode::IntPropLevel ipl)
00093          : Test("Distinct::Offset::Dense::"+str(ipl),6,min,max,false,ipl) {}
00095        virtual bool solution(const Assignment& x) const {
00096          for (int i=0; i<x.size(); i++)
00097            for (int j=i+1; j<x.size(); j++)
00098              if (x[i]+i==x[j]+j)
00099                return false;
00100          return true;
00101        }
00103        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00104          Gecode::IntArgs c(x.size());
00105          for (int i=0; i<x.size(); i++)
00106            c[i]=i;
00107          Gecode::distinct(home, c, x, ipl);
00108        }
00109      };
00110 
00112      class Optional : public Test {
00113      public:
00115        Optional(const Gecode::IntArgs& d, Gecode::IntPropLevel ipl)
00116          : Test("Distinct::Optional::"+str(ipl)+"::"+str(d),
00117                 6,Gecode::IntSet(d),false,ipl) {}
00119        virtual bool solution(const Assignment& x) const {
00120          int n = x.size() / 2;
00121          for (int i=0; i<n; i++)
00122            if ((x[i] < 0) || (x[i] > 1))
00123              return false;
00124          for (int i=0; i<n; i++)
00125            for (int j=i+1; j<n; j++)
00126              if ((x[i] == 1) && (x[j] == 1) && (x[n+i] == x[n+j]))
00127                return false;
00128          return true;
00129        }
00131        virtual void post(Gecode::Space& home, Gecode::IntVarArray& bx) {
00132          int n = bx.size() / 2;
00133          Gecode::BoolVarArgs b(n);
00134          Gecode::IntVarArgs x(n);
00135          for (int i=0; i<n; i++) {
00136            b[i] = Gecode::channel(home, bx[i]);
00137            x[i] = bx[n+i];
00138          }
00139          Gecode::distinct(home, b, x, ipl);
00140        }
00141      };
00142 
00144      class Except : public Test {
00145      public:
00147        Except(const Gecode::IntArgs& d, Gecode::IntPropLevel ipl)
00148          : Test("Distinct::Except::"+str(ipl)+"::"+str(d),
00149                 3,Gecode::IntSet(d),false,ipl) {
00150          contest = CTL_NONE;
00151        }
00153        virtual bool solution(const Assignment& x) const {
00154          for (int i=0; i<x.size(); i++)
00155            for (int j=i+1; j<x.size(); j++)
00156              if ((x[i] != 0) && (x[j] != 0) && (x[i] == x[j]))
00157                return false;
00158          return true;
00159        }
00161        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00162          Gecode::distinct(home, x, 0, ipl);
00163        }
00164      };
00165 
00167      class Random : public Test {
00168      public:
00170        Random(int n, int min, int max, Gecode::IntPropLevel ipl)
00171          : Test("Distinct::Random::"+str(ipl),n,min,max,false,ipl) {
00172          testsearch = false;
00173        }
00175        virtual Assignment* assignment(void) const {
00176          return new RandomAssignment(arity,dom,100);
00177        }
00179        virtual bool solution(const Assignment& x) const {
00180          for (int i=0; i<x.size(); i++)
00181            for (int j=i+1; j<x.size(); j++)
00182              if (x[i]==x[j])
00183                return false;
00184          return true;
00185        }
00187        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00188          Gecode::distinct(home, x, ipl);
00189        }
00190      };
00191 
00193      class Pathological : public Base {
00194      protected:
00196        int n;
00198        Gecode::IntPropLevel ipl;
00200        class TestSpace : public Gecode::Space {
00201        public:
00203          TestSpace(void) {}
00205          TestSpace(TestSpace& s)
00206            : Gecode::Space(s) {}
00208          virtual Gecode::Space* copy(void) {
00209            return new TestSpace(*this);
00210          }
00211        };
00212      public:
00214        Pathological(int n0, Gecode::IntPropLevel ipl0)
00215          : Base("Int::Distinct::Pathological::"+
00216                 Test::str(n0)+"::"+Test::str(ipl0)), n(n0), ipl(ipl0) {}
00218        virtual bool run(void) {
00219          using namespace Gecode;
00220          {
00221            TestSpace* s = new TestSpace;
00222            IntVarArgs x(n);
00223            for (int i=0; i<n; i++)
00224              x[i] = IntVar(*s,0,i);
00225            distinct(*s,x,ipl);
00226            if (s->status() == SS_FAILED) {
00227              delete s; return false;
00228            }
00229            for (int i=0; i<n; i++)
00230              if (!x[i].assigned() || (x[i].val() != i)) {
00231                delete s; return false;
00232              }
00233            delete s;
00234          }
00235          {
00236            TestSpace* s = new TestSpace;
00237            IntVarArgs x(2*n);
00238            for (int i=0; i<n; i++) {
00239              int v[] = {0,i};
00240              IntSet d(v,2);
00241              x[i] = IntVar(*s,d);
00242            }
00243            for (int i=n; i<2*n; i++)
00244              x[i] = IntVar(*s,n-1,i);
00245            distinct(*s,x,ipl);
00246            if (s->status() == SS_FAILED) {
00247              delete s; return false;
00248            }
00249            for (int i=0; i<n; i++)
00250              if (!x[i].assigned() || (x[i].val() != i)) {
00251                delete s; return false;
00252              }
00253            delete s;
00254          }
00255          return true;
00256        }
00257      };
00258 
00259      const int v[7] = {-1001,-1000,-10,0,10,1000,1001};
00260      Gecode::IntSet d(v,7);
00261      const int vl[6] = {Gecode::Int::Limits::min+0,
00262                         Gecode::Int::Limits::min+1,
00263                         Gecode::Int::Limits::min+2,
00264                         Gecode::Int::Limits::max-2,
00265                         Gecode::Int::Limits::max-1,
00266                         Gecode::Int::Limits::max-0};
00267      Gecode::IntSet dl(vl,6);
00268 
00269      Distinct<false> dom_d(-3,3,Gecode::IPL_DOM);
00270      Distinct<false> bnd_d(-3,3,Gecode::IPL_BND);
00271      Distinct<false> val_d(-3,3,Gecode::IPL_VAL);
00272      Distinct<false> dom_s(d,Gecode::IPL_DOM);
00273      Distinct<false> bnd_s(d,Gecode::IPL_BND);
00274      Distinct<false> val_s(d,Gecode::IPL_VAL);
00275 
00276      Distinct<false> dom_l(dl,Gecode::IPL_DOM,5);
00277      Distinct<false> bnd_l(dl,Gecode::IPL_BND,5);
00278      Distinct<false> val_l(dl,Gecode::IPL_VAL,5);
00279 
00280      Distinct<true> count_dom_d(-3,3,Gecode::IPL_DOM);
00281      Distinct<true> count_bnd_d(-3,3,Gecode::IPL_BND);
00282      Distinct<true> count_val_d(-3,3,Gecode::IPL_VAL);
00283      Distinct<true> count_dom_s(d,Gecode::IPL_DOM);
00284      Distinct<true> count_bnd_s(d,Gecode::IPL_BND);
00285      Distinct<true> count_val_s(d,Gecode::IPL_VAL);
00286 
00287      Offset dom_od(-3,3,Gecode::IPL_DOM);
00288      Offset bnd_od(-3,3,Gecode::IPL_BND);
00289      Offset val_od(-3,3,Gecode::IPL_VAL);
00290      Offset dom_os(d,Gecode::IPL_DOM);
00291      Offset bnd_os(d,Gecode::IPL_BND);
00292      Offset val_os(d,Gecode::IPL_VAL);
00293 
00294      Gecode::IntArgs v1({Gecode::Int::Limits::min+4,
00295                          0,1,
00296                          Gecode::Int::Limits::max});
00297      Gecode::IntArgs v2({Gecode::Int::Limits::min,
00298                          0,1,
00299                          Gecode::Int::Limits::max-4});
00300      Gecode::IntArgs v3({0,1,2,3});
00301      Gecode::IntArgs v4({0,1,2});
00302      Gecode::IntArgs v5({0,1});
00303 
00304      Optional od1(v1,Gecode::IPL_DOM);
00305      Optional ob1(v1,Gecode::IPL_BND);
00306      Optional ov1(v1,Gecode::IPL_VAL);
00307      Optional od2(v2,Gecode::IPL_DOM);
00308      Optional ob2(v2,Gecode::IPL_BND);
00309      Optional ov2(v2,Gecode::IPL_VAL);
00310      Optional od3(v3,Gecode::IPL_DOM);
00311      Optional ob3(v3,Gecode::IPL_BND);
00312      Optional ov3(v3,Gecode::IPL_VAL);
00313      Optional od4(v4,Gecode::IPL_DOM);
00314      Optional ob4(v4,Gecode::IPL_BND);
00315      Optional ov4(v4,Gecode::IPL_VAL);
00316      Optional od5(v5,Gecode::IPL_DOM);
00317      Optional ob5(v5,Gecode::IPL_BND);
00318      Optional ov5(v5,Gecode::IPL_VAL);
00319 
00320      Except ed1(v1,Gecode::IPL_DOM);
00321      Except eb1(v1,Gecode::IPL_BND);
00322      Except ev1(v1,Gecode::IPL_VAL);
00323      Except ed2(v2,Gecode::IPL_DOM);
00324      Except eb2(v2,Gecode::IPL_BND);
00325      Except ev2(v2,Gecode::IPL_VAL);
00326      Except ed5(v5,Gecode::IPL_DOM);
00327      Except eb5(v5,Gecode::IPL_BND);
00328      Except ev5(v5,Gecode::IPL_VAL);
00329 
00330      Random dom_r(20,-50,50,Gecode::IPL_DOM);
00331      Random bnd_r(50,-500,500,Gecode::IPL_BND);
00332      Random val_r(50,-500,500,Gecode::IPL_VAL);
00333 
00334      Pathological p_16_v(16,Gecode::IPL_VAL);
00335      Pathological p_16_b(16,Gecode::IPL_BND);
00336      Pathological p_16_d(16,Gecode::IPL_DOM);
00337 
00338      Pathological p_32_v(32,Gecode::IPL_VAL);
00339      Pathological p_32_b(32,Gecode::IPL_BND);
00340      Pathological p_32_d(32,Gecode::IPL_DOM);
00342 
00343    }
00344 }}
00345 
00346 // STATISTICS: test-int