main page
modules
namespaces
classes
files
Gecode home
Generated on Sat May 25 2013 18:00:40 for Gecode by
doxygen
1.8.3.1
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: 2012-10-19 05:58:26 +0200 (Fri, 19 Oct 2012) $ by $Author: tack $
13
* $Revision: 13156 $
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::Reify
r
;
211
bool
reified
;
213
SetTest
*
test
;
214
224
SetTestSpace
(
int
n
,
Gecode::IntSet
& d0,
int
i
,
SetTest
*
t
,
225
bool
log
=
true
);
235
SetTestSpace
(
int
n
,
Gecode::IntSet
& d0,
int
i
,
SetTest
*
t
,
236
Gecode::ReifyMode
rm,
bool
log
=
true
);
238
SetTestSpace
(
bool
share,
SetTestSpace
& s);
240
virtual
Gecode::Space
*
copy
(
bool
share);
242
void
post
(
void
);
244
bool
failed
(
void
);
246
void
rel
(
int
i
,
Gecode::SetRelType
srt,
const
Gecode::IntSet
& is);
248
void
cardinality
(
int
i
,
int
cmin,
int
cmax);
250
void
rel
(
int
i
,
Gecode::IntRelType
irt,
int
n
);
252
void
rel
(
bool
sol);
254
void
assign
(
const
SetAssignment
&
a
);
256
bool
assigned
(
void
)
const
;
258
void
removeFromLub
(
int
v
,
int
i
,
const
SetAssignment
&
a
);
260
void
addToGlb
(
int
v
,
int
i
,
const
SetAssignment
&
a
);
262
bool
fixprob
(
void
);
264
bool
prune
(
const
SetAssignment
&
a
);
265
};
266
271
class
SetTest
:
public
Base
{
272
private
:
274
int
arity;
276
Gecode::IntSet
lub;
278
bool
reified;
280
int
withInt;
281
283
void
removeFromLub(
int
v
,
Gecode::SetVar
&
x
,
int
i
,
284
const
Gecode::IntSet
&
a
);
286
void
addToGlb(
int
v,
Gecode::SetVar
& x,
int
i,
const
Gecode::IntSet
& a);
287
SetAssignment
* make_assignment(
void
);
288
public
:
296
SetTest
(
const
std::string& s,
297
int
a,
const
Gecode::IntSet
&
d
,
bool
r
=
false
,
int
w=0)
298
:
Base
(
"Set::"
+s), arity(a), lub(d), reified(
r
), withInt(w) {}
300
virtual
bool
solution
(
const
SetAssignment
&)
const
= 0;
302
virtual
void
post
(
Gecode::Space
& home,
Gecode::SetVarArray
& x,
303
Gecode::IntVarArray
& y) = 0;
305
virtual
void
post
(
Gecode::Space
&,
Gecode::SetVarArray
&,
306
Gecode::IntVarArray
&,
Gecode::Reify
) {}
308
virtual
bool
run
(
void
);
309
311
312
313
static
std::string
str
(
Gecode::SetRelType
srt);
315
static
std::string
str
(
Gecode::SetOpType
srt);
317
static
std::string
str
(
int
i);
319
static
std::string
str
(
const
Gecode::IntArgs
& i);
321
};
323
325
class
SetRelTypes
{
326
private
:
328
static
const
Gecode::SetRelType
srts[6];
330
int
i;
331
public
:
333
SetRelTypes
(
void
);
335
bool
operator()
(
void
)
const
;
337
void
operator++
(
void
);
339
Gecode::SetRelType
srt
(
void
)
const
;
340
};
341
343
class
SetOpTypes
{
344
private
:
346
static
const
Gecode::SetOpType
sots[4];
348
int
i;
349
public
:
351
SetOpTypes
(
void
);
353
bool
operator()
(
void
)
const
;
355
void
operator++
(
void
);
357
Gecode::SetOpType
sot
(
void
)
const
;
358
};
359
360
}}
361
366
std::ostream&
367
operator<<
(std::ostream&,
const
Test::Set::SetAssignment
&
a
);
368
369
#include "
test/set.hpp
"
370
371
#endif
372
373
// STATISTICS: test-set