Generated on Fri Aug 24 2012 04:52:18 for Gecode by doxygen 1.8.1.1
unary.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, 2009
8  *
9  * Last modified:
10  * $Date: 2011-05-26 00:56:41 +1000 (Thu, 26 May 2011) $ by $Author: schulte $
11  * $Revision: 12022 $
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 
42 namespace Test { namespace Int {
43 
45  namespace Unary {
46 
52 
53  class ManFixPUnary : public Test {
54  protected:
58  static int st(const Gecode::IntArgs& p) {
59  int t = 0;
60  for (int i=p.size(); i--; )
61  t += p[i];
62  return t;
63  }
64  public:
66  ManFixPUnary(const Gecode::IntArgs& p0, int o)
67  : Test("Unary::Man::Fix::"+str(o)+"::"+str(p0),
68  p0.size(),o,o+st(p0)),
69  p(p0) {
70  testsearch = false;
71  contest = CTL_NONE;
72  }
74  virtual Assignment* assignment(void) const {
75  return new RandomAssignment(arity,dom,500);
76  }
78  virtual bool solution(const Assignment& x) const {
79  for (int i=0; i<x.size(); i++)
80  for (int j=i+1; j<x.size(); j++)
81  if ((x[i]+p[i] > x[j]) && (x[j]+p[j] > x[i]))
82  return false;
83  return true;
84  }
86  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
87  Gecode::unary(home, x, p);
88  }
89  };
90 
92  class OptFixPUnary : public Test {
93  protected:
97  int l;
99  static int st(const Gecode::IntArgs& p) {
100  int t = 0;
101  for (int i=p.size(); i--; )
102  t += p[i];
103  return t;
104  }
105  public:
107  OptFixPUnary(const Gecode::IntArgs& p0, int o)
108  : Test("Unary::Opt::Fix::"+str(o)+"::"+str(p0),
109  2*p0.size(),o,o+st(p0)), p(p0), l(o+st(p)/2) {
110  testsearch = false;
111  contest = CTL_NONE;
112  }
114  virtual Assignment* assignment(void) const {
115  return new RandomAssignment(arity,dom,500);
116  }
118  virtual bool solution(const Assignment& x) const {
119  int n = x.size() / 2;
120  for (int i=0; i<n; i++)
121  if (x[n+i] > l)
122  for (int j=i+1; j<n; j++)
123  if(x[n+j] > l)
124  if ((x[i]+p[i] > x[j]) && (x[j]+p[j] > x[i]))
125  return false;
126  return true;
127  }
129  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
130  int n=x.size() / 2;
131  Gecode::IntVarArgs s(n);
133  for (int i=0; i<n; i++) {
134  s[i]=x[i];
135  m[i]=Gecode::expr(home, (x[n+i] > l));
136  }
137  Gecode::unary(home, s, p, m);
138  }
139  };
140 
141 
143  class ManFlexUnary : public Test {
144  protected:
146  int _minP;
148  int _maxP;
150  int off;
151  public:
153  ManFlexUnary(int n, int minP, int maxP, int o)
154  : Test("Unary::Man::Flex::"+str(o)+"::"+str(n)+"::"
155  +str(minP)+"::"+str(maxP),
156  2*n,0,n*maxP), _minP(minP), _maxP(maxP), off(o) {
157  testsearch = false;
158  testfix = false;
159  contest = CTL_NONE;
160  }
162  virtual Assignment* assignment(void) const {
163  return new RandomMixAssignment(arity/2,dom,arity/2,
164  Gecode::IntSet(_minP,_maxP),500);
165  }
167  virtual bool solution(const Assignment& x) const {
168  int n = x.size()/2;
169  for (int i=0; i<n; i++)
170  for (int j=i+1; j<n; j++)
171  if ((x[i]+x[n+i] > x[j]) && (x[j]+x[n+j] > x[i]))
172  return false;
173  return true;
174  }
176  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
177  Gecode::IntVarArgs s(x.size()/2);
178  Gecode::IntVarArgs px(x.slice(x.size()/2));
179  Gecode::IntVarArgs e(home,x.size()/2,
182  for (int i=s.size(); i--;) {
183  s[i] = expr(home, off+x[i]);
184  rel(home, s[i]+px[i] == e[i]);
185  rel(home, _minP <= px[i]);
186  rel(home, _maxP >= px[i]);
187  }
188  Gecode::unary(home, s, px, e);
189  }
190  };
191 
193  class OptFlexUnary : public Test {
194  protected:
196  int _minP;
198  int _maxP;
200  int off;
202  int l;
204  static int st(const Gecode::IntArgs& p) {
205  int t = 0;
206  for (int i=p.size(); i--; )
207  t += p[i];
208  return t;
209  }
210  public:
212  OptFlexUnary(int n, int minP, int maxP, int o)
213  : Test("Unary::Opt::Flex::"+str(o)+"::"+str(n)+"::"
214  +str(minP)+"::"+str(maxP),
215  3*n,0,n*maxP), _minP(minP), _maxP(maxP), off(o),
216  l(n*maxP/2) {
217  testsearch = false;
218  testfix = false;
219  contest = CTL_NONE;
220  }
222  virtual Assignment* assignment(void) const {
223  return new RandomMixAssignment(2*(arity/3),dom,arity/3,
224  Gecode::IntSet(_minP,_maxP),500);
225  }
227  virtual bool solution(const Assignment& x) const {
228  int n = x.size() / 3;
229  for (int i=0; i<n; i++)
230  if (x[n+i] > l)
231  for (int j=i+1; j<n; j++)
232  if(x[n+j] > l)
233  if ((x[i]+x[2*n+i] > x[j]) && (x[j]+x[2*n+j] > x[i]))
234  return false;
235  return true;
236  }
238  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
239  int n=x.size() / 3;
240 
241  Gecode::IntVarArgs s(n);
242  Gecode::IntVarArgs px(n);
243  Gecode::IntVarArgs e(home,n,
246  for (int i=n; i--;) {
247  s[i] = expr(home, off+x[i]);
248  px[i] = x[2*n+i];
249  rel(home, s[i]+px[i] == e[i]);
250  rel(home, _minP <= px[i]);
251  rel(home, _maxP >= px[i]);
252  }
254  for (int i=0; i<n; i++)
255  m[i]=Gecode::expr(home, (x[n+i] > l));
256  Gecode::unary(home, s, px, e, m);
257  }
258  };
259 
260  Gecode::IntArgs p1(4, 2,2,2,2);
261  ManFixPUnary mfu10(p1,0);
262  ManFixPUnary mfu1i(p1,Gecode::Int::Limits::min);
263  OptFixPUnary ofu10(p1,0);
264  OptFixPUnary ofu1i(p1,Gecode::Int::Limits::min);
265  ManFlexUnary mflu10(4,0,2,0);
266  ManFlexUnary mflu1i(4,0,2,Gecode::Int::Limits::min);
267  ManFlexUnary mflu101(4,1,3,0);
268  ManFlexUnary mflu1i1(4,1,3,Gecode::Int::Limits::min);
269  OptFlexUnary oflu10(4,0,2,0);
270  OptFlexUnary oflu1i(4,0,2,Gecode::Int::Limits::min);
271 
272  Gecode::IntArgs p10(5, 2,2,0,2,2);
273  ManFixPUnary mfu010(p10,0);
274  ManFixPUnary mfu01i(p10,Gecode::Int::Limits::min);
275  OptFixPUnary ofu010(p10,0);
276  OptFixPUnary ofu01i(p10,Gecode::Int::Limits::min);
277  ManFlexUnary mflu010(5,0,2,0);
278  ManFlexUnary mflu01i(5,0,2,Gecode::Int::Limits::min);
279  OptFlexUnary oflu010(5,0,2,0);
280  OptFlexUnary oflu01i(5,0,2,Gecode::Int::Limits::min);
281 
282  Gecode::IntArgs p2(4, 4,3,3,5);
283  ManFixPUnary mfu20(p2,0);
284  ManFixPUnary mfu2i(p2,Gecode::Int::Limits::min);
285  OptFixPUnary ofu20(p2,0);
286  OptFixPUnary ofu2i(p2,Gecode::Int::Limits::min);
287  ManFlexUnary mflu20(4,3,5,0);
288  ManFlexUnary mflu2i(4,3,5,Gecode::Int::Limits::min);
289  OptFlexUnary oflu20(4,3,5,0);
290  OptFlexUnary oflu2i(4,3,5,Gecode::Int::Limits::min);
291 
292  Gecode::IntArgs p20(6, 4,0,3,3,0,5);
293  ManFixPUnary mfu020(p20,0);
294  ManFixPUnary mfu02i(p20,Gecode::Int::Limits::min);
295  OptFixPUnary ofu020(p20,0);
296  OptFixPUnary ofu02i(p20,Gecode::Int::Limits::min);
297  ManFlexUnary mflu020(6,0,5,0);
298  ManFlexUnary mflu02i(6,0,5,Gecode::Int::Limits::min);
299  OptFlexUnary oflu020(6,0,5,0);
300  OptFlexUnary oflu02i(6,0,5,Gecode::Int::Limits::min);
301 
302  Gecode::IntArgs p3(6, 4,2,9,3,7,5);
303  ManFixPUnary mfu30(p3,0);
304  ManFixPUnary mfu3i(p3,Gecode::Int::Limits::min);
305  OptFixPUnary ofu30(p3,0);
306  OptFixPUnary ofu3i(p3,Gecode::Int::Limits::min);
307  ManFlexUnary mflu30(6,2,7,0);
308  ManFlexUnary mflu3i(6,2,7,Gecode::Int::Limits::min);
309  OptFlexUnary oflu30(6,2,7,0);
310  OptFlexUnary oflu3i(6,2,7,Gecode::Int::Limits::min);
311 
312  Gecode::IntArgs p30(8, 4,0,2,9,3,7,5,0);
313  ManFixPUnary mfu030(p30,0);
314  ManFixPUnary mfu03i(p30,Gecode::Int::Limits::min);
315  OptFixPUnary ofu030(p30,0);
316  OptFixPUnary ofu03i(p30,Gecode::Int::Limits::min);
317  ManFlexUnary mflu030(8,0,9,0);
318  ManFlexUnary mflu03i(8,0,9,Gecode::Int::Limits::min);
319  OptFlexUnary oflu030(8,0,9,0);
320  OptFlexUnary oflu03i(8,0,9,Gecode::Int::Limits::min);
321 
323 
324  }
325 }}
326 
327 // STATISTICS: test-int