Generated on Sat Feb 7 2015 02:01:25 for Gecode by doxygen 1.8.9.1
sorted.cpp
Go to the documentation of this file.
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  * Last modified:
14  * $Date: 2010-04-08 12:35:31 +0200 (Thu, 08 Apr 2010) $ by $Author: schulte $
15  * $Revision: 10684 $
16  *
17  * This file is part of Gecode, the generic constraint
18  * development environment:
19  * http://www.gecode.org
20  *
21  * Permission is hereby granted, free of charge, to any person obtaining
22  * a copy of this software and associated documentation files (the
23  * "Software"), to deal in the Software without restriction, including
24  * without limitation the rights to use, copy, modify, merge, publish,
25  * distribute, sublicense, and/or sell copies of the Software, and to
26  * permit persons to whom the Software is furnished to do so, subject to
27  * the following conditions:
28  *
29  * The above copyright notice and this permission notice shall be
30  * included in all copies or substantial portions of the Software.
31  *
32  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
33  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
34  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
35  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
36  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
37  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
38  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
39  *
40  */
41 
42 #include "test/int.hh"
43 
44 namespace Test { namespace Int {
45 
47  namespace Sorted {
48 
54 
56  class SortIntMin {
57  public:
59  bool operator()(const int x, const int y) {
60  return x<y;
61  }
62  };
63 
65  class NoVar : public Test {
66  protected:
68  static const int n = 3;
69  public:
71  NoVar(void) : Test("Sorted::NoVar",2*n,0,3) {}
73  virtual bool solution(const Assignment& xy) const {
74  int x[n], y[n];
75  for (int i=0;i<3; i++) {
76  x[i]=xy[i]; y[i]=xy[n+i];
77  }
78 
79  for (int i=0; i<n-1; i++)
80  if (y[i]>y[i+1])
81  return false;
82 
83  SortIntMin sim;
84  Gecode::Support::quicksort<int,SortIntMin>(x,n,sim);
85 
86  for (int i=0; i<n; i++)
87  if (x[i] != y[i])
88  return false;
89  return true;
90  }
92  virtual void post(Gecode::Space& home, Gecode::IntVarArray& xy) {
93  Gecode::IntVarArgs x(n), y(n);
94  for (int i=0; i<n; i++) {
95  x[i]=xy[i]; y[i]=xy[n+i];
96  }
97  Gecode::sorted(home,x,y);
98  }
99  };
100 
101 
103  class PermVar : public Test {
104  protected:
106  static const int n = 3;
107  public:
109  PermVar(void) : Test("Sorted::PermVar",3*n,0,2) {}
111  virtual bool solution(const Assignment& xyz) const {
112  int x[n], y[n], z[n];
113  for (int i=0; i<n; i++) {
114  x[i]=xyz[i]; y[i]=xyz[n+i]; z[i]=xyz[2*n+i];
115  }
116  // check for permutation
117  for (int i=0; i<n; i++)
118  for (int j=i+1; j<n; j++)
119  if (z[i]==z[j])
120  return false;
121 
122  // y must to be sorted
123  for (int i=0; i<n-1; i++)
124  if (y[i]>y[i+1])
125  return false;
126 
127  // check whether permutation is in range
128  for (int i=0; i<n; i++)
129  if ((z[i] < 0) || (z[i] >= n))
130  return false;
131 
132  // check whether permutation info is correct
133  for (int i=0; i<n; i++)
134  if (x[i] != y[z[i]])
135  return false;
136 
137  // check for sorting
138  SortIntMin sim;
139  Gecode::Support::quicksort<int,SortIntMin>(x,n,sim);
140  for (int i=0; i<n; i++)
141  if (x[i] != y[i])
142  return false;
143 
144  return true;
145  }
147  virtual void post(Gecode::Space& home, Gecode::IntVarArray& xyz) {
148  Gecode::IntVarArgs x(n), y(n), z(n);
149  for (int i=0; i<n; i++) {
150  x[i]=xyz[i]; y[i]=xyz[n+i]; z[i]=xyz[2*n+i];
151  }
152  Gecode::sorted(home,x,y,z);
153  }
154  };
155 
156 
160 
161  }
162 }}
163 
164 // STATISTICS: test-int
165 
Test sorted with permutation variables
Definition: sorted.cpp:103
Relation for sorting integers in increasing order.
Definition: sorted.cpp:56
Integer variable array.
Definition: int.hh:741
virtual bool solution(const Assignment &xyz) const
Test whether xyz is solution
Definition: sorted.cpp:111
NoVar(void)
Create and register test.
Definition: sorted.cpp:71
Computation spaces.
Definition: core.hpp:1362
Gecode::IntArgs i(4, 1, 2, 3, 4)
PermVar(void)
Create and register test.
Definition: sorted.cpp:109
virtual bool solution(const Assignment &xy) const
Test whether xy is solution
Definition: sorted.cpp:73
bool operator()(const int x, const int y)
Test whether x is less than y
Definition: sorted.cpp:59
Passing integer variables.
Definition: int.hh:636
void sorted(Home home, const IntVarArgs &x, const IntVarArgs &y, const IntVarArgs &z, IntConLevel)
Post propagator that y is x sorted in increasing order.
Definition: sorted.cpp:43
General test support.
Definition: afc.cpp:43
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
Base class for assignments
Definition: int.hh:63
static const int n
Number of variables to be sorted.
Definition: sorted.cpp:68
virtual void post(Gecode::Space &home, Gecode::IntVarArray &xyz)
Post constraint on xyz.
Definition: sorted.cpp:147
virtual void post(Gecode::Space &home, Gecode::IntVarArray &xy)
Post constraint on xy.
Definition: sorted.cpp:92
static const int n
Number of variables to be sorted.
Definition: sorted.cpp:106
Test sorted without permutation variables
Definition: sorted.cpp:65
PermVar permvar
Definition: sorted.cpp:158