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