main page
modules
namespaces
classes
files
Gecode home
Generated on Fri Jan 10 2020 11:38:25 for Gecode by
doxygen
1.8.16
gecode
int
extensional
bit-set.hpp
Go to the documentation of this file.
1
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2
/*
3
* Main authors:
4
* Linnea Ingmar <linnea.ingmar@hotmail.com>
5
*
6
* Contributing authors:
7
* Christian Schulte <schulte@gecode.org>
8
*
9
* Copyright:
10
* Linnea Ingmar, 2017
11
* Christian Schulte, 2017
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
namespace
Gecode
{
namespace
Int {
namespace
Extensional {
39
40
template
<
class
IndexType>
41
forceinline
unsigned
int
42
BitSet<IndexType>::limit
(
void
)
const
{
43
return
static_cast<unsigned int>(_limit);
44
}
45
46
template
<
class
IndexType>
47
forceinline
bool
48
BitSet<IndexType>::empty
(
void
)
const
{
49
return
_limit == 0U;
50
}
51
52
template
<
class
IndexType>
53
forceinline
unsigned
int
54
BitSet<IndexType>::words
(
void
)
const
{
55
return
static_cast<unsigned int>(_limit);
56
}
57
58
template
<
class
IndexType>
59
forceinline
unsigned
int
60
BitSet<IndexType>::size
(
void
)
const
{
61
return
words();
62
}
63
64
template
<
class
IndexType>
65
forceinline
unsigned
int
66
BitSet<IndexType>::width
(
void
)
const
{
67
assert(!empty());
68
IndexType width = _index[0];
69
for
(IndexType
i
=1;
i
<_limit;
i
++)
70
width =
std::max
(width,_index[
i
]);
71
assert(static_cast<unsigned int>(width+1U) >= words());
72
return
static_cast<unsigned int>(width+1U);
73
}
74
75
template
<
class
IndexType>
76
forceinline
77
BitSet<IndexType>::BitSet
(
Space
& home,
unsigned
int
n
)
78
: _limit(static_cast<IndexType>(
n
)),
79
_index(home.alloc<IndexType>(
n
)),
80
_bits(home.alloc<
BitSetData
>(
n
)) {
81
// Set all bits in all words (including the last)
82
for
(IndexType
i
=0;
i
<
_limit
;
i
++) {
83
_bits
[
i
].
init
(
true
);
84
_index
[
i
] =
i
;
85
}
86
}
87
88
template
<
class
IndexType>
89
template
<
class
OldIndexType>
90
forceinline
91
BitSet<IndexType>::BitSet
(
Space
& home,
92
const
BitSet<OldIndexType>
& bs)
93
: _limit(static_cast<IndexType>(bs._limit)),
94
_index(home.alloc<IndexType>(_limit)),
95
_bits(home.alloc<
BitSetData
>(_limit)) {
96
assert(
_limit
> 0U);
97
for
(IndexType
i
=0;
i
<
_limit
;
i
++) {
98
_bits
[
i
] = bs.
_bits
[
i
];
99
_index
[
i
] = static_cast<IndexType>(bs.
_index
[
i
]);
100
}
101
}
102
103
template
<
class
IndexType>
104
forceinline
void
105
BitSet<IndexType>::flush
(
void
) {
106
_limit = 0U;
107
assert(empty());
108
}
109
110
template
<
class
IndexType>
111
forceinline
112
BitSet<IndexType>::BitSet
(
Space
&,
const
TinyBitSet<1U>
&) {
113
GECODE_NEVER
;
114
}
115
template
<
class
IndexType>
116
forceinline
117
BitSet<IndexType>::BitSet
(
Space
&,
const
TinyBitSet<2U>
&) {
118
GECODE_NEVER
;
119
}
120
template
<
class
IndexType>
121
forceinline
122
BitSet<IndexType>::BitSet
(
Space
&,
const
TinyBitSet<3U>
&) {
123
GECODE_NEVER
;
124
}
125
template
<
class
IndexType>
126
forceinline
127
BitSet<IndexType>::BitSet
(
Space
&,
const
TinyBitSet<4U>
&) {
128
GECODE_NEVER
;
129
}
130
131
template
<
class
IndexType>
132
forceinline
void
133
BitSet<IndexType>::replace_and_decrease
(IndexType
i
,
BitSetData
w) {
134
assert(_limit > 0U);
135
BitSetData
w_i = _bits[
i
];
136
if
(w != w_i) {
137
_bits[
i
] = w;
138
if
(w.
none
()) {
139
assert(_bits[
i
].none());
140
_limit--;
141
_bits[
i
] = _bits[_limit];
142
_index[
i
] = _index[_limit];
143
}
144
}
145
}
146
147
template
<
class
IndexType>
148
forceinline
void
149
BitSet<IndexType>::clear_mask
(
BitSetData
* mask)
const
{
150
assert(_limit > 0U);
151
for
(IndexType
i
=0;
i
<_limit;
i
++) {
152
mask[
i
].
init
(
false
);
153
assert(mask[
i
].none());
154
}
155
}
156
157
template
<
class
IndexType>
158
forceinline
void
159
BitSet<IndexType>::add_to_mask
(
const
BitSetData
*
b
,
BitSetData
* mask)
const
{
160
assert(_limit > 0U);
161
for
(IndexType
i
=0;
i
<_limit;
i
++)
162
mask[
i
] =
BitSetData::o
(mask[
i
],
b
[_index[
i
]]);
163
}
164
165
template
<
class
IndexType>
166
template
<
bool
sparse>
167
forceinline
void
168
BitSet<IndexType>::intersect_with_mask
(
const
BitSetData
* mask) {
169
assert(_limit > 0U);
170
if
(sparse) {
171
for
(IndexType
i
= _limit;
i
--; ) {
172
assert(!_bits[
i
].none());
173
BitSetData
w_i = _bits[
i
];
174
BitSetData
w_a =
BitSetData::a
(w_i, mask[_index[
i
]]);
175
replace_and_decrease(
i
,w_a);
176
assert(
i
== _limit || !_bits[
i
].none());
177
}
178
}
else
{
// The same except different _indexing in mask
179
for
(IndexType
i
= _limit;
i
--; ) {
180
assert(!_bits[
i
].none());
181
BitSetData
w_i = _bits[
i
];
182
BitSetData
w_a =
BitSetData::a
(w_i, mask[
i
]);
183
replace_and_decrease(
i
,w_a);
184
assert(
i
== _limit || !_bits[
i
].none());
185
}
186
}
187
}
188
189
template
<
class
IndexType>
190
forceinline
void
191
BitSet<IndexType>::intersect_with_masks
(
const
BitSetData
*
a
,
192
const
BitSetData
*
b
) {
193
assert(_limit > 0U);
194
for
(IndexType
i
= _limit;
i
--; ) {
195
assert(!_bits[
i
].none());
196
BitSetData
w_i = _bits[
i
];
197
IndexType offset = _index[
i
];
198
BitSetData
w_o =
BitSetData::o
(
a
[offset],
b
[offset]);
199
BitSetData
w_a =
BitSetData::a
(w_i,w_o);
200
replace_and_decrease(
i
,w_a);
201
assert(
i
== _limit || !_bits[
i
].none());
202
}
203
}
204
205
template
<
class
IndexType>
206
forceinline
void
207
BitSet<IndexType>::nand_with_mask
(
const
BitSetData
*
b
) {
208
assert(_limit > 0U);
209
for
(IndexType
i
= _limit;
i
--; ) {
210
assert(!_bits[
i
].none());
211
BitSetData
w =
BitSetData::a
(_bits[
i
],~(
b
[_index[
i
]]));
212
replace_and_decrease(
i
,w);
213
assert(
i
== _limit || !_bits[
i
].none());
214
}
215
}
216
217
template
<
class
IndexType>
218
forceinline
bool
219
BitSet<IndexType>::intersects
(
const
BitSetData
*
b
)
const
{
220
for
(IndexType
i
=0;
i
<_limit;
i
++)
221
if
(!
BitSetData::a
(_bits[
i
],
b
[_index[
i
]]).none())
222
return
true
;
223
return
false
;
224
}
225
226
template
<
class
IndexType>
227
forceinline
unsigned
long
long
int
228
BitSet<IndexType>::ones
(
const
BitSetData
*
b
)
const
{
229
unsigned
long
long
int
o = 0U;
230
for
(IndexType
i
=0;
i
<_limit;
i
++)
231
o += static_cast<unsigned long long int>
232
(
BitSetData::a
(_bits[
i
],
b
[_index[
i
]]).ones());
233
return
o;
234
}
235
236
template
<
class
IndexType>
237
forceinline
unsigned
long
long
int
238
BitSet<IndexType>::ones
(
void
)
const
{
239
unsigned
long
long
int
o = 0U;
240
for
(IndexType
i
=0;
i
<_limit;
i
++)
241
o += static_cast<unsigned long long int>(_bits[
i
].ones());
242
return
o;
243
}
244
245
template
<
class
IndexType>
246
forceinline
unsigned
long
long
int
247
BitSet<IndexType>::bits
(
void
)
const
{
248
return
(static_cast<unsigned long long int>(_limit) *
249
static_cast<unsigned long long int>(
BitSetData::bpb
));
250
}
251
252
}}}
253
254
// STATISTICS: int-prop
b
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
Gecode::Int::Extensional::BitSet::width
unsigned int width(void) const
Return the highest active index.
Definition:
bit-set.hpp:66
Gecode::Int::Extensional::BitSet::flush
void flush(void)
Make the set empty.
Definition:
bit-set.hpp:105
Gecode::Int::Extensional::BitSet::clear_mask
void clear_mask(BitSetData *mask) const
Clear the first limit words in mask.
Definition:
bit-set.hpp:149
Gecode::Int::Extensional::BitSet::intersect_with_masks
void intersect_with_masks(const BitSetData *a, const BitSetData *b)
Intersect with the "or" of and b.
Definition:
bit-set.hpp:191
Gecode::Support::BitSetData::a
void a(BitSetData a)
Perform "and" with a.
Definition:
bitset-base.hpp:346
Gecode::Int::Extensional::BitSet::_limit
IndexType _limit
Limit.
Definition:
extensional.hh:240
Gecode::Int::Extensional::BitSet::words
unsigned int words(void) const
Return the number of required bit set words.
Definition:
bit-set.hpp:54
Gecode::Int::Extensional::BitSet::intersects
bool intersects(const BitSetData *b) const
Check if has a non-empty intersection with the set.
Definition:
bit-set.hpp:219
Gecode::Int::Extensional::BitSet::bits
unsigned long long int bits(void) const
Return an upper bound on the number of bits.
Definition:
bit-set.hpp:247
Gecode::Support::BitSetData::o
void o(BitSetData a)
Perform "or" with a.
Definition:
bitset-base.hpp:362
Gecode::Space
Computation spaces.
Definition:
core.hpp:1742
Gecode::Int::Extensional::BitSet::_index
IndexType * _index
Indices.
Definition:
extensional.hh:242
Gecode::Int::Extensional::BitSet::add_to_mask
void add_to_mask(const BitSetData *b, BitSetData *mask) const
Add to mask.
Definition:
bit-set.hpp:159
Gecode::Int::Extensional::BitSet::_bits
BitSetData * _bits
Words.
Definition:
extensional.hh:244
Gecode
Gecode toplevel namespace
Gecode::Support::BitSetData::bpb
static const unsigned int bpb
Bits per base.
Definition:
bitset-base.hpp:79
a
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
Gecode::Support::BitSetData::none
bool none(void) const
Whether no bits are set.
Definition:
bitset-base.hpp:303
Gecode::Int::Extensional::BitSet::size
unsigned int size(void) const
Return the number of required bit set words.
Definition:
bit-set.hpp:60
Gecode::Int::Extensional::BitSet::nand_with_mask
void nand_with_mask(const BitSetData *b)
Perform "nand" with b.
Definition:
bit-set.hpp:207
Gecode::Int::Extensional::BitSet::BitSet
friend class BitSet
Definition:
extensional.hh:236
Gecode::Int::Extensional::BitSet::empty
bool empty(void) const
Check whether the set is empty.
Definition:
bit-set.hpp:48
GECODE_NEVER
#define GECODE_NEVER
Assert that this command is never executed.
Definition:
macros.hpp:56
Gecode::Int::Extensional::BitSet::limit
unsigned int limit(void) const
Get the limit.
Definition:
bit-set.hpp:42
Gecode::Int::Extensional::BitSet::ones
unsigned long long int ones(void) const
Return the number of ones.
Definition:
bit-set.hpp:238
Gecode::Int::Extensional::TinyBitSet
Tiny bit-set.
Definition:
extensional.hh:231
Gecode::Int::Extensional::BitSet::replace_and_decrease
void replace_and_decrease(IndexType i, BitSetData w)
Replace the i th word with w, decrease limit if w is zero.
Definition:
bit-set.hpp:133
forceinline
#define forceinline
Definition:
config.hpp:185
Gecode::Support::BitSetData
Date item for bitsets.
Definition:
bitset-base.hpp:65
Gecode::Int::Extensional::BitSet
Bit-set.
Definition:
extensional.hh:235
n
int n
Number of negative literals for node type.
Definition:
bool-expr.cpp:234
Test::Int::Basic::i
Gecode::IntArgs i({1, 2, 3, 4})
Gecode::Support::BitSetData::init
void init(bool setbits=false)
Initialize with all bits set if setbits.
Definition:
bitset-base.hpp:246
Gecode::Int::Extensional::BitSet::intersect_with_mask
void intersect_with_mask(const BitSetData *mask)
Intersect with mask, sparse mask if sparse is true.
Definition:
bit-set.hpp:168
Gecode::Float::Limits::max
const FloatNum max
Largest allowed float value.
Definition:
float.hh:844