main page
modules
namespaces
classes
files
Gecode home
Generated on Sat Aug 25 2012 03:32:53 for Gecode by
doxygen
1.8.1.2
test
set.hh
Go to the documentation of this file.
1
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2
/*
3
* Main authors:
4
* Guido Tack <tack@gecode.org>
5
* Christian Schulte <schulte@gecode.org>
6
*
7
* Copyright:
8
* Guido Tack, 2005
9
* Christian Schulte, 2005
10
*
11
* Last modified:
12
* $Date: 2011-07-12 20:49:06 +1000 (Tue, 12 Jul 2011) $ by $Author: tack $
13
* $Revision: 12172 $
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
#ifndef __GECODE_TEST_SET_HH__
41
#define __GECODE_TEST_SET_HH__
42
43
#include <
gecode/set.hh
>
44
#include "
test/test.hh
"
45
#include "
test/int.hh
"
46
47
namespace
Test {
48
50
namespace
Set {
51
57
58
class
FakeSpace
:
public
Gecode::Space
{
59
public
:
61
FakeSpace
(
void
) {}
63
virtual
Gecode::Space
*
copy
(
bool
share) {
64
(void) share;
65
return
NULL;
66
}
67
};
68
74
76
class
CountableSetValues
{
77
private
:
78
Gecode::IntSetValues
dv;
79
int
cur;
80
int
i;
81
public
:
83
CountableSetValues
(
void
) {}
85
CountableSetValues
(
const
Gecode::IntSet
& d0,
int
cur0)
86
: dv(d0), cur(cur0), i(1) {
87
if
(! (i & cur))
88
operator++
();
89
}
91
void
init
(
const
Gecode::IntSet
& d0,
int
cur0) {
92
dv = d0;
93
cur = cur0;
94
i = 1;
95
if
(! (i & cur))
96
operator++
();
97
}
99
bool
operator()
(
void
)
const
{
100
return
i<=cur;
101
}
103
void
operator++
(
void
) {
104
do
{
105
++dv;
106
i = i<<1;
107
}
while
(! (i & cur) && i<cur);
108
}
110
int
val
(
void
)
const
{
return
dv.
val
(); }
111
};
112
114
class
CountableSetRanges
115
:
public
Gecode::Iter::Values::ToRanges
<CountableSetValues> {
116
private
:
118
CountableSetValues
v;
119
public
:
121
CountableSetRanges
(
void
) {}
123
CountableSetRanges
(
const
Gecode::IntSet
&
d
,
int
cur) : v(d, cur) {
124
Gecode::Iter::Values::ToRanges<CountableSetValues>::init
(v);
125
}
127
void
init
(
const
Gecode::IntSet
&
d
,
int
cur) {
128
v.
init
(d, cur);
129
Gecode::Iter::Values::ToRanges<CountableSetValues>::init
(v);
130
}
131
};
132
134
class
CountableSet
{
135
private
:
137
Gecode::IntSet
d;
139
unsigned
int
cur;
141
unsigned
int
lubmax;
142
public
:
144
CountableSet
(
const
Gecode::IntSet
& s);
146
CountableSet
(
void
) {}
148
void
init
(
const
Gecode::IntSet
& s);
150
bool
operator()
(
void
)
const
{
return
cur<lubmax; }
152
void
operator++
(
void
);
154
int
val
(
void
)
const
;
155
};
156
158
class
SetAssignment
{
159
private
:
161
int
n;
163
CountableSet
* dsv;
165
Test::Int::CpltAssignment
ir;
167
bool
done;
168
public
:
170
Gecode::IntSet
lub
;
172
int
withInt
;
174
SetAssignment
(
int
n,
const
Gecode::IntSet
&
d
,
int
i
= 0);
176
bool
operator()
(
void
)
const
{
return
!done; }
178
void
operator++
(
void
);
180
int
operator[]
(
int
i
)
const
{
181
assert((i>=0) && (i<n));
182
return
dsv[
i
].
val
();
183
}
185
int
intval
(
void
)
const
{
return
ir[0]; }
187
const
Test::Int::Assignment
&
ints
(
void
)
const
{
return
ir; }
189
int
size
(
void
)
const
{
return
n; }
191
~SetAssignment
(
void
) {
delete
[] dsv; }
192
};
193
194
195
class
SetTest;
196
198
class
SetTestSpace
:
public
Gecode::Space
{
199
public
:
201
Gecode::IntSet
d
;
203
Gecode::SetVarArray
x
;
205
Gecode::IntVarArray
y
;
207
int
withInt
;
209
Gecode::BoolVar
b
;
211
bool
reified
;
213
SetTest
*
test
;
214
224
SetTestSpace
(
int
n,
Gecode::IntSet
& d0,
int
i
,
bool
r
,
SetTest
* t,
225
bool
log=
true
);
227
SetTestSpace
(
bool
share,
SetTestSpace
& s);
229
virtual
Gecode::Space
*
copy
(
bool
share);
231
void
post
(
void
);
233
bool
failed
(
void
);
235
void
rel
(
int
i
,
Gecode::SetRelType
srt,
const
Gecode::IntSet
& is);
237
void
cardinality
(
int
i
,
int
cmin,
int
cmax);
239
void
rel
(
int
i
,
Gecode::IntRelType
irt,
int
n);
241
void
rel
(
bool
sol);
243
void
assign
(
const
SetAssignment
&
a
);
245
bool
assigned
(
void
)
const
;
247
void
removeFromLub
(
int
v
,
int
i
,
const
SetAssignment
&
a
);
249
void
addToGlb
(
int
v
,
int
i
,
const
SetAssignment
&
a
);
251
bool
fixprob
(
void
);
253
bool
prune
(
const
SetAssignment
&
a
);
254
};
255
260
class
SetTest
:
public
Base
{
261
private
:
263
int
arity;
265
Gecode::IntSet
lub;
267
bool
reified;
269
int
withInt;
270
272
void
removeFromLub(
int
v
,
Gecode::SetVar
& x,
int
i
,
273
const
Gecode::IntSet
&
a
);
275
void
addToGlb(
int
v,
Gecode::SetVar
& x,
int
i,
const
Gecode::IntSet
& a);
276
SetAssignment
* make_assignment(
void
);
277
public
:
285
SetTest
(
const
std::string& s,
286
int
a,
const
Gecode::IntSet
&
d
,
bool
r
=
false
,
int
w=0)
287
:
Base
(
"Set::"
+s), arity(a), lub(d), reified(
r
), withInt(w) {}
289
virtual
bool
solution
(
const
SetAssignment
&)
const
= 0;
291
virtual
void
post
(
Gecode::Space
& home,
Gecode::SetVarArray
& x,
292
Gecode::IntVarArray
& y) = 0;
294
virtual
void
post
(
Gecode::Space
&,
Gecode::SetVarArray
&,
295
Gecode::IntVarArray
&,
Gecode::BoolVar
) {}
297
virtual
bool
run
(
void
);
298
300
301
302
static
std::string
str
(
Gecode::SetRelType
srt);
304
static
std::string
str
(
Gecode::SetOpType
srt);
306
static
std::string
str
(
int
i);
308
static
std::string
str
(
const
Gecode::IntArgs
& i);
310
};
312
314
class
SetRelTypes
{
315
private
:
317
static
const
Gecode::SetRelType
srts[6];
319
int
i;
320
public
:
322
SetRelTypes
(
void
);
324
bool
operator()
(
void
)
const
;
326
void
operator++
(
void
);
328
Gecode::SetRelType
srt
(
void
)
const
;
329
};
330
332
class
SetOpTypes
{
333
private
:
335
static
const
Gecode::SetOpType
sots[4];
337
int
i;
338
public
:
340
SetOpTypes
(
void
);
342
bool
operator()
(
void
)
const
;
344
void
operator++
(
void
);
346
Gecode::SetOpType
sot
(
void
)
const
;
347
};
348
349
}}
350
355
std::ostream&
356
operator<<
(std::ostream&,
const
Test::Set::SetAssignment
&
a
);
357
358
#include "
test/set.hpp
"
359
360
#endif
361
362
// STATISTICS: test-set