main page
modules
namespaces
classes
files
Gecode home
Generated on Tue Oct 22 2013 00:49:03 for Gecode by
doxygen
1.8.4
test
int
distinct.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
* Mikael Lagerkvist <lagerkvist@gecode.org>
6
*
7
* Copyright:
8
* Christian Schulte, 2005
9
* Mikael Lagerkvist, 2006
10
*
11
* Last modified:
12
* $Date: 2013-03-14 21:16:41 +0100 (Thu, 14 Mar 2013) $ by $Author: schulte $
13
* $Revision: 13539 $
14
*
15
* This file is part of Gecode, the generic constraint
16
* development environment:
17
* http://www.gecode.org
18
*
19
* Permission is hereby granted, free of charge, to any person obtaining
20
* a copy of this software and associated documentation files (the
21
* "Software"), to deal in the Software without restriction, including
22
* without limitation the rights to use, copy, modify, merge, publish,
23
* distribute, sublicense, and/or sell copies of the Software, and to
24
* permit persons to whom the Software is furnished to do so, subject to
25
* the following conditions:
26
*
27
* The above copyright notice and this permission notice shall be
28
* included in all copies or substantial portions of the Software.
29
*
30
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37
*
38
*/
39
40
#include "
test/int.hh
"
41
42
namespace
Test {
namespace
Int {
43
45
namespace
Distinct
{
46
52
template
<
bool
useCount>
54
class
Distinct
:
public
Test
{
55
public
:
57
Distinct
(
const
Gecode::IntSet
& d0,
Gecode::IntConLevel
icl
)
58
:
Test
(std::string(useCount ?
"Count::Distinct::"
:
"Distinct::"
)+
59
str
(icl)+
"::Sparse"
,6,d0,false,icl) {}
61
Distinct
(
int
min
,
int
max
,
Gecode::IntConLevel
icl
)
62
:
Test
(std::string(useCount ?
"Count::Distinct::"
:
"Distinct::"
)+
63
str
(icl)+
"::Dense"
,6,min,max,false,icl) {}
65
virtual
bool
solution
(
const
Assignment
&
x
)
const
{
66
for
(
int
i
=0;
i
<x.
size
();
i
++)
67
for
(
int
j=
i
+1; j<x.
size
(); j++)
68
if
(x[
i
]==x[j])
69
return
false
;
70
return
true
;
71
}
73
virtual
void
post
(
Gecode::Space
& home,
Gecode::IntVarArray
&
x
) {
74
if
(!useCount) {
75
Gecode::distinct
(home, x,
icl
);
76
}
else
{
77
Gecode::IntSetRanges
dr(
dom
);
78
int
i
= 0;
79
Gecode::IntArgs
ia(
Gecode::Iter::Ranges::size
(dr));
80
for
(
Gecode::IntSetValues
dr2(
dom
); dr2(); ++dr2)
81
ia[i++] = dr2.val();
82
Gecode::count
(home, x,
Gecode::IntSet
(0,1), ia,
icl
);
83
}
84
}
85
};
86
88
class
Offset
:
public
Test
{
89
public
:
91
Offset
(
const
Gecode::IntSet
&
d
,
Gecode::IntConLevel
icl
)
92
:
Test
(
"Distinct::Offset::Sparse::"
+
str
(icl),6,d,false,icl) {}
94
Offset
(
int
min
,
int
max
,
Gecode::IntConLevel
icl
)
95
:
Test
(
"Distinct::Offset::Dense::"
+
str
(icl),6,min,max,false,icl) {}
97
virtual
bool
solution
(
const
Assignment
&
x
)
const
{
98
for
(
int
i
=0;
i
<x.
size
();
i
++)
99
for
(
int
j=
i
+1; j<x.
size
(); j++)
100
if
(x[
i
]+
i
==x[j]+j)
101
return
false
;
102
return
true
;
103
}
105
virtual
void
post
(
Gecode::Space
& home,
Gecode::IntVarArray
&
x
) {
106
Gecode::IntArgs
c
(x.
size
());
107
for
(
int
i
=0;
i
<x.
size
();
i
++)
108
c
[
i
]=
i
;
109
Gecode::distinct
(home,
c
, x,
icl
);
110
}
111
};
112
114
class
Random
:
public
Test
{
115
public
:
117
Random
(
int
n
,
int
min
,
int
max
,
Gecode::IntConLevel
icl
)
118
:
Test
(
"Distinct::Random::"
+
str
(icl),n,min,max,false,icl) {
119
testsearch
=
false
;
120
}
122
virtual
Assignment
*
assignment
(
void
)
const
{
123
return
new
RandomAssignment
(
arity
,
dom
,100);
124
}
126
virtual
bool
solution
(
const
Assignment
&
x
)
const
{
127
for
(
int
i
=0;
i
<x.
size
();
i
++)
128
for
(
int
j=
i
+1; j<x.
size
(); j++)
129
if
(x[
i
]==x[j])
130
return
false
;
131
return
true
;
132
}
134
virtual
void
post
(
Gecode::Space
& home,
Gecode::IntVarArray
&
x
) {
135
Gecode::distinct
(home, x,
icl
);
136
}
137
};
138
140
class
Pathological
:
public
Base
{
141
protected
:
143
int
n
;
145
Gecode::IntConLevel
icl
;
147
class
TestSpace
:
public
Gecode::Space
{
148
public
:
150
TestSpace
(
void
) {}
152
TestSpace
(
bool
share,
TestSpace
& s)
153
: Gecode::
Space
(share,s) {}
155
virtual
Gecode::Space
*
copy
(
bool
share) {
156
return
new
TestSpace
(share,*
this
);
157
}
158
};
159
public
:
161
Pathological
(
int
n0,
Gecode::IntConLevel
icl0)
162
:
Base
(
"Int::Distinct::Pathological::"
+
163
Test
::str(n0)+
"::"
+
Test
::str(icl0)),
n
(n0),
icl
(icl0) {}
165
virtual
bool
run
(
void
) {
166
using namespace
Gecode;
167
{
168
TestSpace
* s =
new
TestSpace
;
169
IntVarArgs
x
(
n
);
170
for
(
int
i
=0;
i
<
n
;
i
++)
171
x[
i
] =
IntVar
(*s,0,
i
);
172
distinct
(*s,x,
icl
);
173
if
(s->
status
() ==
SS_FAILED
) {
174
delete
s;
return
false
;
175
}
176
for
(
int
i
=0;
i
<
n
;
i
++)
177
if
(!x[
i
].
assigned
() || (x[
i
].val() !=
i
)) {
178
delete
s;
return
false
;
179
}
180
delete
s;
181
}
182
{
183
TestSpace
* s =
new
TestSpace
;
184
IntVarArgs
x
(2*
n
);
185
for
(
int
i
=0;
i
<
n
;
i
++) {
186
int
v
[] = {0,
i
};
187
IntSet
d
(v,2);
188
x[
i
] =
IntVar
(*s,d);
189
}
190
for
(
int
i
=n;
i
<2*
n
;
i
++)
191
x[
i
] =
IntVar
(*s,n-1,
i
);
192
distinct
(*s,x,
icl
);
193
if
(s->
status
() ==
SS_FAILED
) {
194
delete
s;
return
false
;
195
}
196
for
(
int
i
=0;
i
<
n
;
i
++)
197
if
(!x[
i
].
assigned
() || (x[
i
].val() !=
i
)) {
198
delete
s;
return
false
;
199
}
200
delete
s;
201
}
202
return
true
;
203
}
204
};
205
206
const
int
v
[7] = {-1001,-1000,-10,0,10,1000,1001};
207
Gecode::IntSet
d
(
v
,7);
208
209
Distinct<false>
dom_d
(-3,3,
Gecode::ICL_DOM
);
210
Distinct<false>
bnd_d
(-3,3,
Gecode::ICL_BND
);
211
Distinct<false>
val_d
(-3,3,
Gecode::ICL_VAL
);
212
Distinct<false>
dom_s
(
d
,
Gecode::ICL_DOM
);
213
Distinct<false>
bnd_s
(
d
,
Gecode::ICL_BND
);
214
Distinct<false>
val_s
(
d
,
Gecode::ICL_VAL
);
215
216
Distinct<true>
count_dom_d
(-3,3,
Gecode::ICL_DOM
);
217
Distinct<true>
count_bnd_d
(-3,3,
Gecode::ICL_BND
);
218
Distinct<true>
count_val_d
(-3,3,
Gecode::ICL_VAL
);
219
Distinct<true>
count_dom_s
(
d
,
Gecode::ICL_DOM
);
220
Distinct<true>
count_bnd_s
(
d
,
Gecode::ICL_BND
);
221
Distinct<true>
count_val_s
(
d
,
Gecode::ICL_VAL
);
222
223
Offset
dom_od
(-3,3,
Gecode::ICL_DOM
);
224
Offset
bnd_od
(-3,3,
Gecode::ICL_BND
);
225
Offset
val_od
(-3,3,
Gecode::ICL_VAL
);
226
Offset
dom_os
(
d
,
Gecode::ICL_DOM
);
227
Offset
bnd_os
(
d
,
Gecode::ICL_BND
);
228
Offset
val_os
(
d
,
Gecode::ICL_VAL
);
229
230
Random
dom_r
(20,-50,50,
Gecode::ICL_DOM
);
231
Random
bnd_r
(50,-500,500,
Gecode::ICL_BND
);
232
Random
val_r
(50,-500,500,
Gecode::ICL_VAL
);
233
234
Pathological
p_16_v
(16,
Gecode::ICL_VAL
);
235
Pathological
p_16_b
(16,
Gecode::ICL_BND
);
236
Pathological
p_16_d
(16,
Gecode::ICL_DOM
);
237
238
Pathological
p_32_v
(32,
Gecode::ICL_VAL
);
239
Pathological
p_32_b
(32,
Gecode::ICL_BND
);
240
Pathological
p_32_d
(32,
Gecode::ICL_DOM
);
242
243
}
244
}}
245
246
// STATISTICS: test-int