1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  *  Main authors:
4  *     Patrick Pekczynski <pekczynski@ps.uni-sb.de>
5  *
6  *  Contributing authors:
7  *     Christian Schulte <schulte@gecode.org>
8  *
9  *  Copyright:
10  *     Patrick Pekczynski, 2005
11  *     Christian Schulte, 2007
12  *
13  *  This file is part of Gecode, the generic constraint
14  *  development environment:
15  *     http://www.gecode.org
16  *
17  *  Permission is hereby granted, free of charge, to any person obtaining
18  *  a copy of this software and associated documentation files (the
19  *  "Software"), to deal in the Software without restriction, including
20  *  without limitation the rights to use, copy, modify, merge, publish,
21  *  distribute, sublicense, and/or sell copies of the Software, and to
22  *  permit persons to whom the Software is furnished to do so, subject to
23  *  the following conditions:
24  *
25  *  The above copyright notice and this permission notice shall be
26  *  included in all copies or substantial portions of the Software.
27  *
28  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 #include "test/int.hh"
39 
40 namespace Test { namespace Int {
41 
42    /// %Tests for counting constraints (global cardinality)
43    namespace GCC {
44 
45      /**
46       * \defgroup TaskTestIntGCC Counting constraints (global cardinality)
47       * \ingroup TaskTestInt
48       */
49      //@{
50      /// %Test for integer cardinality with min and max for all variables
51      class IntAllMinMax : public Test {
52      public:
53        /// Create and register test
IntAllMinMax(Gecode::IntPropLevel ipl)54        IntAllMinMax(Gecode::IntPropLevel ipl)
55          : Test("GCC::Int::All::MinMax::"+str(ipl),4,-1,3,false,ipl) {}
56        /// %Test whether \a x is solution
solution(const Assignment & x) const57        virtual bool solution(const Assignment& x) const {
58          int n[5];
59          for (int i=5; i--; )
60            n[i]=0;
61          for (int i=x.size(); i--; )
62            n[x[i]+1]++;
63          if (n[2] > 0)
64           return false;
65          for (int i=5; i--;)
66            if (n[i]>2)
67              return false;
68          return true;
69        }
70        /// Post constraint on \a x
post(Gecode::Space & home,Gecode::IntVarArray & x)71        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
72          using namespace Gecode;
73          IntArgs values(5);
74          IntSet fixed(0,2);
75          IntSetArgs cards(5);
76          for (int i=0; i<5; i++) {
77            values[i] = i-1; cards[i] = fixed;
78          }
79          cards[2] = IntSet(0,0);
80          count(home, x, cards, values, ipl);
81        }
82      };
83 
84      /// %Test for integer cardinality with min and max for all variables
85      class IntAllMinMaxDef : public Test {
86      public:
87        /// Create and register test
IntAllMinMaxDef(Gecode::IntPropLevel ipl)88        IntAllMinMaxDef(Gecode::IntPropLevel ipl)
89          : Test("GCC::Int::All::MinMaxDef::"+str(ipl),4,0,3,false,ipl) {}
90        /// %Test whether \a x is solution
solution(const Assignment & x) const91        virtual bool solution(const Assignment& x) const {
92          int n[4];
93          for (int i=4; i--; )
94            n[i]=0;
95          for (int i=x.size(); i--; )
96            n[x[i]]++;
97          if (n[2] > 0)
98            return false;
99          for (int i=4; i--;)
100            if (n[i]>2)
101              return false;
102          return true;
103        }
104        /// Post constraint on \a x
post(Gecode::Space & home,Gecode::IntVarArray & x)105        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
106          using namespace Gecode;
107          IntSet fixed(0,2);
108          IntSetArgs cards(4);
109          for (int i=0; i<4; i++) {
110            cards[i] = fixed;
111          }
112          cards[2] = IntSet(0,0);
113          count(home, x, cards, ipl);
114        }
115      };
116 
117      /// %Test for integer cardinality with max cardinality for all variables
118      class IntAllMax : public Test {
119      public:
120        /// Create and register test
IntAllMax(Gecode::IntPropLevel ipl)121        IntAllMax(Gecode::IntPropLevel ipl)
122          : Test("GCC::Int::All::Max::"+str(ipl), 4, 1,2, false, ipl) {}
123        /// %Test whether \a x is solution
solution(const Assignment & x) const124        virtual bool solution(const Assignment& x) const {
125          int n[2];
126          for (int i=2; i--; )
127            n[i] = 0;
128          for (int i=x.size(); i--; )
129            n[x[i] - 1]++;
130          if (n[0] != 2 || n[1] != 2)
131            return false;
132          return true;
133        }
134        /// Post constraint on \a x
post(Gecode::Space & home,Gecode::IntVarArray & x)135        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
136          Gecode::IntArgs values({1,2});
137          Gecode::count(home, x, Gecode::IntSet(2,2), values, ipl);
138        }
139      };
140 
141 
142      /// %Test for integer cardinality for some variables
143      template<bool hole>
144      class IntSome : public Test {
145      public:
146        /// Create and register test
IntSome(Gecode::IntPropLevel ipl)147        IntSome(Gecode::IntPropLevel ipl)
148          : Test(std::string("GCC::Int::Some::")+
149                 (hole ? "::Hole" : "::Full")+str(ipl),4,1,4,false,ipl) {}
150        /// %Test whether \a x is solution
solution(const Assignment & x) const151        virtual bool solution(const Assignment& x) const {
152          int n[4];
153          for (int i=4; i--; )
154            n[i]=0;
155          for (int i=x.size(); i--; )
156            n[x[i]-1]++;
157          if ((n[0] < 2) || (n[1] < 2) || (n[2] > 0) || (n[3] > 0))
158            return false;
159          return true;
160        }
161        /// Post constraint on \a x
post(Gecode::Space & home,Gecode::IntVarArray & x)162        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
163          using namespace Gecode;
164          IntArgs values({1,2});
165          Gecode::IntSet fixed;
166          if (!hole) {
167            fixed = IntSet(0,2);
168          } else {
169            int ish[] = {0,2};
170            fixed = IntSet(ish,2);
171          }
172          Gecode::IntSetArgs cards(2);
173          cards[0]=fixed; cards[1]=fixed;
174          count(home, x, cards, values, ipl);
175        }
176      };
177 
178      /// %Test for variable cardinality for all cardinality values
179      class VarAll : public Test {
180      protected:
181        /// Number of non-cardinality variables
182        static const int n = 4;
183      public:
184        /// Create and register test
VarAll(Gecode::IntPropLevel ipl)185        VarAll(Gecode::IntPropLevel ipl)
186          : Test("GCC::Var::All::"+str(ipl),7,0,2,false,ipl) {}
187        /// %Test whether \a x is solution
solution(const Assignment & x) const188        virtual bool solution(const Assignment& x) const {
189          // Number of cardinality variables
190          int m = x.size()-n;
191          for (int i=0; i<n; i++)
192            if ((x[i] < 0) || (x[i] > 2))
193              return false;
194          int* card = new int[m];
195          for (int i=0; i<m; i++) {
196            card[i] = 0;
197            if ((x[n+i] < 0) || (x[n+i] > 2)) {
198              delete [] card;
199              return false;
200            }
201          }
202          for (int i=0; i<n; i++)
203            card[x[i]]++;
204          for (int i=0; i<m; i++)
205            if (card[i] != x[n+i]) {
206              delete [] card;
207              return false;
208            }
209          delete [] card;
210          return true;
211        }
212        /// Post constraint on \a xy
post(Gecode::Space & home,Gecode::IntVarArray & xy)213        virtual void post(Gecode::Space& home, Gecode::IntVarArray& xy) {
214          using namespace Gecode;
215          // Number of cardinality variables
216          int m = xy.size()-n;
217 
218          IntVarArgs x(n), y(m);
219          for (int i=0; i<n; i++)
220            x[i]=xy[i];
221          for (int i=0; i<m; i++)
222            y[i]=xy[n+i];
223          count(home, x, y, ipl);
224        }
225      };
226 
227      /// %Test for variable cardinality for some cardinality values
228      class VarSome : public Test {
229      protected:
230        /// Number of non-cardinality variables
231        int n;
232        /// Arity beyond which to use randomized tests
233        static const int randomArity = 7;
234      public:
235        /// Create and register test
VarSome(std::string s,int n0,int min,int max,Gecode::IntPropLevel ipl)236        VarSome(std::string s, int n0, int min, int max,
237                Gecode::IntPropLevel ipl)
238          : Test("GCC::Var::Some::"+s+"::"+str(ipl),
239                 n0+(max-min)+1,min,max,false,ipl)
240          , n(n0)
241         {
242           contest = CTL_NONE;
243           if (arity>randomArity)
244             testsearch = false;
245         }
246        /// %Test whether \a x is solution
solution(const Assignment & x) const247        virtual bool solution(const Assignment& x) const {
248          // Number of cardinality variables
249          int m = x.size()-n;
250          int* card = new int[m];
251          for (int i=0; i<m; i++) {
252            card[i] = 0;
253            if ((x[n+i] < 0) || (x[n+i] > n)) {
254              delete [] card;
255              return false;
256            }
257          }
258          for (int i=0; i<n; i++)
259            card[x[i]-dom.min()]++;
260          for (int i=0; i<m; i++)
261            if (card[i] != x[n+i]) {
262              delete [] card;
263              return false;
264            }
265          delete [] card;
266          return true;
267        }
268        /// Create and register initial assignment
assignment(void) const269        virtual Assignment* assignment(void) const {
270          if (arity > randomArity)
271            return new RandomAssignment(arity, dom, 4000, _rand);
272          else
273            return new CpltAssignment(arity,dom);
274        }
275        /// Post constraint on \a xy
post(Gecode::Space & home,Gecode::IntVarArray & xy)276        virtual void post(Gecode::Space& home, Gecode::IntVarArray& xy) {
277          using namespace Gecode;
278          // Number of cardinality variables
279          int m = xy.size()-n;
280          IntVarArgs x(n), y(m);
281          for (int i=0; i<n; i++)
282            x[i]=xy[i];
283          for (int i=0; i<m; i++)
284            y[i]=xy[n+i];
285          IntArgs values(m);
286          for (int i=m; i--;)
287            values[i] = i+dom.min();
288          count(home,x,y,values,ipl);
289        }
290      };
291 
292      /// Help class to create and register tests
293      class Create {
294      public:
295        /// Perform creation and registration
Create(void)296        Create(void) {
297          for (IntPropLevels ipls; ipls(); ++ipls) {
298            (void) new IntAllMinMax(ipls.ipl());
299            (void) new IntAllMinMaxDef(ipls.ipl());
300            (void) new IntAllMax(ipls.ipl());
301            (void) new IntSome<false>(ipls.ipl());
302            (void) new IntSome<true>(ipls.ipl());
303            (void) new VarAll(ipls.ipl());
304            (void) new VarSome("Small",2,-1,3,ipls.ipl());
305            (void) new VarSome("Large",3,-1,4,ipls.ipl());
306          }
307        }
308      };
309 
310      Create c;
311      //@}
312 
313    }
314 }}
315 
316 // STATISTICS: test-int
317