main page
modules
namespaces
classes
files
Gecode home
Generated on Sat Nov 9 2013 19:18:29 for Gecode by
doxygen
1.8.4
test
int
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
157
NoVar
novar
;
158
PermVar
permvar
;
160
161
}
162
}}
163
164
// STATISTICS: test-int
165