Generated on Thu Feb 21 2013 23:11:43 for Gecode by doxygen 1.8.3.1
element.cpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  *
6  * Copyright:
7  * Christian Schulte, 2005
8  *
9  * Last modified:
10  * $Date: 2010-04-08 20:35:31 +1000 (Thu, 08 Apr 2010) $ by $Author: schulte $
11  * $Revision: 10684 $
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 #include <gecode/minimodel.hh>
41 #include <climits>
42 
43 namespace Test { namespace Int {
44 
46  namespace Element {
47 
53 
54  class IntIntVar : public Test {
55  protected:
58  public:
60  IntIntVar(const std::string& s, const Gecode::IntArgs& c0,
61  int min, int max)
62  : Test("Element::Int::Int::Var::"+s,2,min,max),
63  c(c0) {}
65  virtual bool solution(const Assignment& x) const {
66  return (x[0]>= 0) && (x[0]<c.size()) && c[x[0]]==x[1];
67  }
69  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
70  Gecode::element(home, c, x[0], x[1]);
71  }
72  };
73 
75  class IntIntInt : public Test {
76  protected:
80  int r;
81  public:
83  IntIntInt(const std::string& s, const Gecode::IntArgs& c0, int r0)
84  : Test("Element::Int::Int::Int::"+s+"::"+str(r0),1,-4,8),
85  c(c0), r(r0) {}
87  virtual bool solution(const Assignment& x) const {
88  return (x[0]>= 0) && (x[0]<c.size()) && c[x[0]]==r;
89  }
91  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
92  Gecode::element(home, c, x[0], r);
93  }
94  };
95 
97  class IntIntShared : public Test {
98  protected:
101  public:
103  IntIntShared(const std::string& s, const Gecode::IntArgs& c0,
104  int minDomain=-4)
105  : Test("Element::Int::Int::Shared::"+s,1,minDomain,8), c(c0) {}
107  virtual bool solution(const Assignment& x) const {
108  return (x[0]>= 0) && (x[0]<c.size()) && c[x[0]]==x[0];
109  }
111  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
112  Gecode::element(home, c, x[0], x[0]);
113  }
114  };
115 
117  class IntBoolVar : public Test {
118  protected:
121  public:
123  IntBoolVar(const std::string& s, const Gecode::IntArgs& c0)
124  : Test("Element::Int::Bool::Var::"+s,2,-4,8), c(c0) {}
126  virtual bool solution(const Assignment& x) const {
127  return (x[0]>= 0) && (x[0]<c.size()) && c[x[0]]==x[1];
128  }
130  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
131  Gecode::element(home, c, x[0], Gecode::channel(home,x[1]));
132  }
133  };
134 
136  class IntBoolInt : public Test {
137  protected:
141  int r;
142  public:
144  IntBoolInt(const std::string& s, const Gecode::IntArgs& c0, int r0)
145  : Test("Element::Int::Bool::Int::"+s+"::"+str(r0),1,-4,8),
146  c(c0), r(r0) {}
148  virtual bool solution(const Assignment& x) const {
149  return (x[0]>= 0) && (x[0]<c.size()) && c[x[0]]==r;
150  }
152  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
153  Gecode::element(home, c, x[0], r);
154  }
155  };
156 
158  class VarIntVar : public Test {
159  public:
162  : Test("Element::Var::Int::Var::"+str(icl),6,-1,3,false,icl) {}
164  virtual bool solution(const Assignment& x) const {
165  return (x[0]>= 0) && (x[0]<x.size()-2) && x[2+x[0]]==x[1];
166  }
168  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
169  Gecode::IntVarArgs c(x.size()-2);
170  for (int i=0; i<x.size()-2; i++)
171  c[i]=x[2+i];
172  Gecode::element(home, c, x[0], x[1], icl);
173  }
174  };
175 
177  class VarIntInt : public Test {
178  protected:
180  int r;
181  public:
184  : Test("Element::Var::Int::Int::"+str(icl)+"::"+str(r0),
185  5,-1,3,false,icl), r(r0) {
186  contest = CTL_NONE;
187  }
189  virtual bool solution(const Assignment& x) const {
190  return (x[0]>= 0) && (x[0]<x.size()-1) && x[1+x[0]]==r;
191  }
193  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
194  Gecode::IntVarArgs c(x.size()-1);
195  for (int i=0; i<x.size()-1; i++)
196  c[i]=x[1+i];
197  Gecode::element(home, c, x[0], r, icl);
198  }
199  };
200 
202  class VarIntShared : public Test {
203  public:
206  : Test("Element::Var::Int::Shared::"+str(icl),5,-1,3,false,icl) {
207  contest = CTL_NONE;
208  }
210  virtual bool solution(const Assignment& x) const {
211  return (x[0]>= 0) && (x[0]<x.size()-1) && x[1+x[0]]==x[0];
212  }
214  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
215  Gecode::IntVarArgs c(x.size()-1);
216  for (int i=0; i<x.size()-1; i++)
217  c[i]=x[1+i];
218  Gecode::element(home, c, x[0], x[0], icl);
219  }
220  };
221 
223  class VarBoolVar : public Test {
224  public:
226  VarBoolVar(void) : Test("Element::Var::Bool::Var",6,-1,3,false) {}
228  virtual bool solution(const Assignment& x) const {
229  for (int i=0; i<x.size()-2; i++)
230  if ((x[2+i] < 0) || (x[2+i]>1))
231  return false;
232  return ((x[0]>= 0) && (x[0]<x.size()-2) && x[2+x[0]]==x[1]
233  && (x[1]>=0) && (x[1]<=1));
234  }
236  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
237  using namespace Gecode;
238  BoolVarArgs c(x.size()-2);
239  for (int i=0; i<x.size()-2; i++)
240  c[i]=channel(home,x[2+i]);
241  element(home, c, x[0], channel(home,x[1]));
242  }
243  };
244 
246  class VarBoolInt : public Test {
247  protected:
249  int r;
250  public:
252  VarBoolInt(int r0)
253  : Test("Element::Var::Bool::Int::"+str(r0),5,-1,3,false), r(r0) {}
255  virtual bool solution(const Assignment& x) const {
256  for (int i=0; i<x.size()-1; i++)
257  if ((x[1+i] < 0) || (x[1+i]>1))
258  return false;
259  return ((x[0]>= 0) && (x[0]<x.size()-1) && x[1+x[0]]==r);
260  }
262  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
263  using namespace Gecode;
264  BoolVarArgs c(x.size()-1);
265  for (int i=0; i<x.size()-1; i++)
266  c[i]=channel(home,x[1+i]);
267  element(home, c, x[0], r);
268  }
269  };
270 
271 
273  class MatrixIntIntVarXY : public Test {
274  protected:
277  public:
280  : Test("Element::Matrix::Int::IntVar::XY",3,0,5,false),
281  tm(6, 0,1,2,3,4,5) {}
283  virtual bool solution(const Assignment& x) const {
284  // x-coordinate: x[0], y-coordinate: x[1], result: x[2]
285  using namespace Gecode;
286  if ((x[0] > 2) || (x[1] > 1))
287  return false;
288  Matrix<IntArgs> m(tm,3,2);
289  return m(x[0],x[1]) == x[2];
290  }
292  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
293  // x-coordinate: x[0], y-coordinate: x[1], result: x[2]
294  using namespace Gecode;
295  Matrix<IntArgs> m(tm,3,2);
296  element(home, m, x[0], x[1], x[2]);
297  }
298  };
299 
301  class MatrixIntIntVarXX : public Test {
302  protected:
305  public:
308  : Test("Element::Matrix::Int::IntVar::XX",2,0,3,false),
309  tm(4, 0,1,2,3) {}
311  virtual bool solution(const Assignment& x) const {
312  // x-coordinate: x[0], y-coordinate: x[0], result: x[1]
313  using namespace Gecode;
314  if (x[0] > 1)
315  return false;
316  Matrix<IntArgs> m(tm,2,2);
317  return m(x[0],x[0]) == x[1];
318  }
320  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
321  // x-coordinate: x[0], y-coordinate: x[0], result: x[1]
322  using namespace Gecode;
323  Matrix<IntArgs> m(tm,2,2);
324  element(home, m, x[0], x[0], x[1]);
325  }
326  };
327 
329  class MatrixIntBoolVarXY : public Test {
330  protected:
333  public:
336  : Test("Element::Matrix::Int::BoolVar::XY",3,0,3,false),
337  tm(4, 0,1,1,0) {}
339  virtual bool solution(const Assignment& x) const {
340  // x-coordinate: x[0], y-coordinate: x[1], result: x[2]
341  using namespace Gecode;
342  if ((x[0] > 1) || (x[1] > 1))
343  return false;
344  Matrix<IntArgs> m(tm,2,2);
345  return m(x[0],x[1]) == x[2];
346  }
348  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
349  // x-coordinate: x[0], y-coordinate: x[1], result: x[2]
350  using namespace Gecode;
351  Matrix<IntArgs> m(tm,2,2);
352  element(home, m, x[0], x[1], channel(home,x[2]));
353  }
354  };
355 
357  class MatrixIntBoolVarXX : public Test {
358  protected:
361  public:
364  : Test("Element::Matrix::Int::BoolVar::XX",2,0,3,false),
365  tm(4, 0,1,1,0) {}
367  virtual bool solution(const Assignment& x) const {
368  // x-coordinate: x[0], y-coordinate: x[0], result: x[1]
369  using namespace Gecode;
370  if (x[0] > 1)
371  return false;
372  Matrix<IntArgs> m(tm,2,2);
373  return m(x[0],x[0]) == x[1];
374  }
376  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
377  // x-coordinate: x[0], y-coordinate: x[0], result: x[1]
378  using namespace Gecode;
379  Matrix<IntArgs> m(tm,2,2);
380  element(home, m, x[0], x[0], channel(home,x[1]));
381  }
382  };
383 
385  class MatrixIntVarIntVarXY : public Test {
386  public:
389  : Test("Element::Matrix::IntVar::IntVar::XY",3+4,0,3,false) {}
391  virtual bool solution(const Assignment& x) const {
392  // x-coordinate: x[0], y-coordinate: x[1], result: x[2]
393  // remaining: matrix
394  using namespace Gecode;
395  if ((x[0] > 1) || (x[1] > 1))
396  return false;
397  IntArgs tm(4);
398  tm[0]=x[3]; tm[1]=x[4]; tm[2]=x[5]; tm[3]=x[6];
399  Matrix<IntArgs> m(tm,2,2);
400  return m(x[0],x[1]) == x[2];
401  }
403  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
404  // x-coordinate: x[0], y-coordinate: x[1], result: x[2]
405  using namespace Gecode;
406  IntVarArgs tm(4);
407  tm[0]=x[3]; tm[1]=x[4]; tm[2]=x[5]; tm[3]=x[6];
408  Matrix<IntVarArgs> m(tm,2,2);
409  element(home, m, x[0], x[1], x[2]);
410  }
411  };
412 
414  class MatrixIntVarIntVarXX : public Test {
415  public:
418  : Test("Element::Matrix::IntVar::IntVar::XX",2+4,0,3,false) {}
420  virtual bool solution(const Assignment& x) const {
421  // x-coordinate: x[0], y-coordinate: x[0], result: x[1]
422  // remaining: matrix
423  using namespace Gecode;
424  if (x[0] > 1)
425  return false;
426  IntArgs tm(4);
427  tm[0]=x[2]; tm[1]=x[3]; tm[2]=x[4]; tm[3]=x[5];
428  Matrix<IntArgs> m(tm,2,2);
429  return m(x[0],x[0]) == x[1];
430  }
432  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
433  // x-coordinate: x[0], y-coordinate: x[1], result: x[1]
434  using namespace Gecode;
435  IntVarArgs tm(4);
436  tm[0]=x[2]; tm[1]=x[3]; tm[2]=x[4]; tm[3]=x[5];
437  Matrix<IntVarArgs> m(tm,2,2);
438  element(home, m, x[0], x[0], x[1]);
439  }
440  };
441 
443  class MatrixBoolVarBoolVarXY : public Test {
444  public:
447  : Test("Element::Matrix::BoolVar::BoolVar::XY",3+4,0,1,false) {}
449  virtual bool solution(const Assignment& x) const {
450  // x-coordinate: x[0], y-coordinate: x[1], result: x[2]
451  // remaining: matrix
452  using namespace Gecode;
453  IntArgs tm(4);
454  tm[0]=x[3]; tm[1]=x[4]; tm[2]=x[5]; tm[3]=x[6];
455  Matrix<IntArgs> m(tm,2,2);
456  return m(x[0],x[1]) == x[2];
457  }
459  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
460  // x-coordinate: x[0], y-coordinate: x[1], result: x[2]
461  using namespace Gecode;
462  BoolVarArgs tm(4);
463  tm[0]=channel(home,x[3]); tm[1]=channel(home,x[4]);
464  tm[2]=channel(home,x[5]); tm[3]=channel(home,x[6]);
465  Matrix<BoolVarArgs> m(tm,2,2);
466  element(home, m, x[0], x[1], channel(home,x[2]));
467  }
468  };
469 
471  class MatrixBoolVarBoolVarXX : public Test {
472  public:
475  : Test("Element::Matrix::BoolVar::BoolVar::XX",2+4,0,1,false) {}
477  virtual bool solution(const Assignment& x) const {
478  // x-coordinate: x[0], y-coordinate: x[0], result: x[1]
479  // remaining: matrix
480  using namespace Gecode;
481  IntArgs tm(4);
482  tm[0]=x[2]; tm[1]=x[3]; tm[2]=x[4]; tm[3]=x[5];
483  Matrix<IntArgs> m(tm,2,2);
484  return m(x[0],x[0]) == x[1];
485  }
487  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
488  // x-coordinate: x[0], y-coordinate: x[1], result: x[1]
489  using namespace Gecode;
490  BoolVarArgs tm(4);
491  tm[0]=channel(home,x[2]); tm[1]=channel(home,x[3]);
492  tm[2]=channel(home,x[4]); tm[3]=channel(home,x[5]);
493  Matrix<BoolVarArgs> m(tm,2,2);
494  element(home, m, x[0], x[0], channel(home,x[1]));
495  }
496  };
497 
498 
499 
500 
502  class Create {
503  public:
505  void optimized(int idx, int val) {
506  Gecode::IntArgs c(idx);
507  for (int i=0; i<idx; i++)
508  c[i]=std::max(val-i,0);
509  (void) new IntIntVar(Test::str(idx)+"::"+Test::str(val)+"::val",c,
510  val-8,val-1);
511  if (idx != val)
512  (void) new IntIntVar(Test::str(idx)+"::"+Test::str(val)+"::idx",c,
513  idx-8,idx-1);
514  }
516  Create(void) {
517  using namespace Gecode;
518  IntArgs ic1(5, -1,1,-3,3,-4);
519  IntArgs ic2(8, -1,1,-1,1,-1,1,0,0);
520  IntArgs ic3(1, -1);
521  IntArgs ic4(7, 0,-1,2,-2,4,-3,6);
522  IntArgs ic5(6, 0,0,1,2,3,4);
523 
524  IntArgs bc1(5, 0,1,1,0,1);
525  IntArgs bc2(8, 1,1,0,1,0,1,0,0);
526  IntArgs bc3(1, 1);
527 
528  (void) new IntIntVar("A",ic1,-8,8);
529  (void) new IntIntVar("B",ic2,-8,8);
530  (void) new IntIntVar("C",ic3,-8,8);
531  (void) new IntIntVar("D",ic4,-8,8);
532 
533  // Test optimizations
534  {
535  int ov[] = {
536  SCHAR_MAX-1,SCHAR_MAX,
537  SHRT_MAX-1,SHRT_MAX,
538  0
539  };
540  for (int i=0; ov[i] != 0; i++)
541  for (int j=0; ov[j] != 0; j++)
542  optimized(ov[i],ov[j]);
543  }
544 
545  for (int i=-4; i<=4; i++) {
546  (void) new IntIntInt("A",ic1,i);
547  (void) new IntIntInt("B",ic2,i);
548  (void) new IntIntInt("C",ic3,i);
549  (void) new IntIntInt("D",ic4,i);
550  }
551 
552  (void) new IntIntShared("A",ic1);
553  (void) new IntIntShared("B",ic2);
554  (void) new IntIntShared("C",ic3);
555  (void) new IntIntShared("D",ic4);
556  (void) new IntIntShared("E",ic5,1);
557 
558  (void) new IntBoolVar("A",bc1);
559  (void) new IntBoolVar("B",bc2);
560  (void) new IntBoolVar("C",bc3);
561 
562  for (int i=0; i<=1; i++) {
563  (void) new IntBoolInt("A",bc1,i);
564  (void) new IntBoolInt("B",bc2,i);
565  (void) new IntBoolInt("C",bc3,i);
566  }
567 
568  (void) new VarIntVar(ICL_BND);
569  (void) new VarIntVar(ICL_DOM);
570 
571  for (int i=-4; i<=4; i++) {
572  (void) new VarIntInt(ICL_BND,i);
573  (void) new VarIntInt(ICL_DOM,i);
574  }
575 
576  (void) new VarIntShared(ICL_BND);
577  (void) new VarIntShared(ICL_DOM);
578 
579  (void) new VarBoolVar();
580  (void) new VarBoolInt(0);
581  (void) new VarBoolInt(1);
582 
583  // Matrix tests
584  (void) new MatrixIntIntVarXY();
585  (void) new MatrixIntIntVarXX();
586  (void) new MatrixIntBoolVarXY();
587  (void) new MatrixIntBoolVarXX();
588 
589  (void) new MatrixIntVarIntVarXY();
590  (void) new MatrixIntVarIntVarXX();
591  (void) new MatrixBoolVarBoolVarXY();
592  (void) new MatrixBoolVarBoolVarXX();
593  }
594  };
595 
598 
599  }
600 }}
601 
602 // STATISTICS: test-int