this repo has no description
dekker.one
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
40namespace Test { namespace Int {
41
42 /// %Tests for sorted constraints
43 namespace Sorted {
44
45 /**
46 * \defgroup TaskTestIntSorted Sorted constraints
47 * \ingroup TaskTestInt
48 */
49 //@{
50
51 /// Relation for sorting integers in increasing order
52 class SortIntMin {
53 public:
54 /// %Test whether \a x is less than \a y
55 bool operator()(const int x, const int y) {
56 return x<y;
57 }
58 };
59
60 /// %Test sorted without permutation variables
61 class NoVar : public Test {
62 protected:
63 /// Number of variables to be sorted
64 static const int n = 3;
65 public:
66 /// Create and register test
67 NoVar(void) : Test("Sorted::NoVar",2*n,0,3) {}
68 /// %Test whether \a xy is solution
69 virtual bool solution(const Assignment& xy) const {
70 int x[n], y[n];
71 for (int i=0;i<3; i++) {
72 x[i]=xy[i]; y[i]=xy[n+i];
73 }
74
75 for (int i=0; i<n-1; i++)
76 if (y[i]>y[i+1])
77 return false;
78
79 SortIntMin sim;
80 Gecode::Support::quicksort<int,SortIntMin>(x,n,sim);
81
82 for (int i=0; i<n; i++)
83 if (x[i] != y[i])
84 return false;
85 return true;
86 }
87 /// Post constraint on \a xy
88 virtual void post(Gecode::Space& home, Gecode::IntVarArray& xy) {
89 Gecode::IntVarArgs x(n), y(n);
90 for (int i=0; i<n; i++) {
91 x[i]=xy[i]; y[i]=xy[n+i];
92 }
93 Gecode::sorted(home,x,y);
94 }
95 };
96
97
98 /// %Test sorted with permutation variables
99 class PermVar : public Test {
100 protected:
101 /// Number of variables to be sorted
102 static const int n = 3;
103 public:
104 /// Create and register test
105 PermVar(void) : Test("Sorted::PermVar",3*n,0,2) {}
106 /// %Test whether \a xyz is solution
107 virtual bool solution(const Assignment& xyz) const {
108 int x[n], y[n], z[n];
109 for (int i=0; i<n; i++) {
110 x[i]=xyz[i]; y[i]=xyz[n+i]; z[i]=xyz[2*n+i];
111 }
112 // check for permutation
113 for (int i=0; i<n; i++)
114 for (int j=i+1; j<n; j++)
115 if (z[i]==z[j])
116 return false;
117
118 // y must to be sorted
119 for (int i=0; i<n-1; i++)
120 if (y[i]>y[i+1])
121 return false;
122
123 // check whether permutation is in range
124 for (int i=0; i<n; i++)
125 if ((z[i] < 0) || (z[i] >= n))
126 return false;
127
128 // check whether permutation info is correct
129 for (int i=0; i<n; i++)
130 if (x[i] != y[z[i]])
131 return false;
132
133 // check for sorting
134 SortIntMin sim;
135 Gecode::Support::quicksort<int,SortIntMin>(x,n,sim);
136 for (int i=0; i<n; i++)
137 if (x[i] != y[i])
138 return false;
139
140 return true;
141 }
142 /// Post constraint on \a xyz
143 virtual void post(Gecode::Space& home, Gecode::IntVarArray& xyz) {
144 Gecode::IntVarArgs x(n), y(n), z(n);
145 for (int i=0; i<n; i++) {
146 x[i]=xyz[i]; y[i]=xyz[n+i]; z[i]=xyz[2*n+i];
147 }
148 Gecode::sorted(home,x,y,z);
149 }
150 };
151
152
153 NoVar novar;
154 PermVar permvar;
155 //@}
156
157 }
158}}
159
160// STATISTICS: test-int
161