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
tiny-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
/*
41
* Tiny bit-set
42
*
43
*/
44
template
<
unsigned
int
sz>
45
forceinline
46
TinyBitSet<sz>::TinyBitSet
(
Space
&,
unsigned
int
n
) {
47
assert(
n
<= sz);
49
for
(
unsigned
int
i
=0U;
i
<
n
;
i
++)
50
_bits[
i
].init(
true
);
52
for
(
unsigned
int
i
=
n
;
i
<sz;
i
++)
53
_bits[
i
].init(
false
);
54
}
55
56
template
<
unsigned
int
sz>
57
template
<
unsigned
int
largersz>
58
forceinline
59
TinyBitSet<sz>::TinyBitSet
(
Space
&,
const
TinyBitSet<largersz>
& sbs) {
60
GECODE_ASSUME
(sz <= largersz);
61
assert(!sbs.
empty
());
62
for
(
unsigned
int
i
=0U;
i
<sz;
i
++)
63
_bits[
i
] = sbs.
_bits
[
i
];
64
assert(!empty());
65
}
66
67
template
<
unsigned
int
sz>
68
template
<
class
IndexType>
69
forceinline
70
TinyBitSet<sz>::TinyBitSet
(
Space
&,
const
BitSet<IndexType>
& sbs) {
71
assert(sz == sbs.
width
());
72
assert(!sbs.
empty
());
73
for
(
unsigned
int
i
=0U;
i
<sz;
i
++)
74
_bits[
i
].init(
false
);
75
for
(
unsigned
int
i
=0U;
i
<sbs.
words
();
i
++)
76
_bits[sbs.
_index
[
i
]] = sbs.
_bits
[
i
];
77
assert(!empty());
78
}
79
80
template
<
unsigned
int
sz>
81
forceinline
void
82
TinyBitSet<sz>::clear_mask
(
BitSetData
* mask) {
83
for
(
unsigned
int
i
=0U;
i
<sz;
i
++) {
84
mask[
i
].
init
(
false
);
85
assert(mask[
i
].none());
86
}
87
}
88
89
template
<
unsigned
int
sz>
90
forceinline
void
91
TinyBitSet<sz>::add_to_mask
(
const
BitSetData
*
b
,
BitSetData
* mask)
const
{
92
for
(
unsigned
int
i
=0U;
i
<sz;
i
++)
93
mask[
i
] =
BitSetData::o
(mask[
i
],
b
[
i
]);
94
}
95
96
template
<
unsigned
int
sz>
97
template
<
bool
sparse>
98
forceinline
void
99
TinyBitSet<sz>::intersect_with_mask
(
const
BitSetData
* mask) {
100
for
(
unsigned
int
i
=0U;
i
<sz;
i
++)
101
_bits[
i
] =
BitSetData::a
(_bits[
i
], mask[
i
]);
102
}
103
104
template
<
unsigned
int
sz>
105
forceinline
void
106
TinyBitSet<sz>::intersect_with_masks
(
const
BitSetData
*
a
,
107
const
BitSetData
*
b
) {
108
for
(
unsigned
int
i
=0U;
i
<sz;
i
++)
109
_bits[
i
] =
BitSetData::a
(_bits[
i
],
BitSetData::o
(
a
[
i
],
b
[
i
]));
110
}
111
112
template
<
unsigned
int
sz>
113
forceinline
void
114
TinyBitSet<sz>::nand_with_mask
(
const
BitSetData
*
b
) {
115
for
(
unsigned
int
i
=0U;
i
<sz;
i
++)
116
_bits[
i
] =
BitSetData::a
(_bits[
i
],~(
b
[
i
]));
117
}
118
119
template
<
unsigned
int
sz>
120
forceinline
void
121
TinyBitSet<sz>::flush
(
void
) {
122
for
(
unsigned
int
i
=0U;
i
<sz;
i
++)
123
_bits[
i
].init(
false
);
124
assert(empty());
125
}
126
127
template
<
unsigned
int
sz>
128
forceinline
bool
129
TinyBitSet<sz>::intersects
(
const
BitSetData
*
b
) {
130
for
(
unsigned
int
i
=0U;
i
<sz;
i
++)
131
if
(!
BitSetData::a
(_bits[
i
],
b
[
i
]).none())
132
return
true
;
133
return
false
;
134
}
135
136
template
<
unsigned
int
sz>
137
forceinline
unsigned
long
long
int
138
TinyBitSet<sz>::ones
(
const
BitSetData
*
b
)
const
{
139
unsigned
long
long
int
o = 0U;
140
for
(
unsigned
int
i
=0U;
i
<sz;
i
++)
141
o += static_cast<unsigned long long int>
142
(
BitSetData::a
(_bits[
i
],
b
[
i
]).ones());
143
return
o;
144
}
145
146
template
<
unsigned
int
sz>
147
forceinline
unsigned
long
long
int
148
TinyBitSet<sz>::ones
(
void
)
const
{
149
unsigned
long
long
int
o = 0U;
150
for
(
unsigned
int
i
=0U;
i
<sz;
i
++)
151
o += static_cast<unsigned long long int>(_bits[
i
].ones());
152
return
o;
153
}
154
155
template
<
unsigned
int
sz>
156
forceinline
unsigned
long
long
int
157
TinyBitSet<sz>::bits
(
void
)
const
{
158
return
(static_cast<unsigned long long int>(sz) *
159
static_cast<unsigned long long int>(
BitSetData::bpb
));
160
}
161
162
template
<
unsigned
int
sz>
163
forceinline
bool
164
TinyBitSet<sz>::empty
(
void
)
const
{
// Linear complexity...
165
for
(
unsigned
int
i
=0U;
i
<sz;
i
++)
166
if
(!_bits[
i
].none())
167
return
false
;
168
return
true
;
169
}
170
171
template
<
unsigned
int
sz>
172
forceinline
unsigned
int
173
TinyBitSet<sz>::width
(
void
)
const
{
174
assert(!empty());
176
for
(
unsigned
int
i
=sz;
i
--; )
177
if
(!_bits[
i
].none())
178
return
i
+1U;
179
GECODE_NEVER
;
180
return
0U;
181
}
182
183
template
<
unsigned
int
sz>
184
forceinline
unsigned
int
185
TinyBitSet<sz>::words
(
void
)
const
{
186
return
width();
187
}
188
189
template
<
unsigned
int
sz>
190
forceinline
unsigned
int
191
TinyBitSet<sz>::size
(
void
)
const
{
192
return
sz;
193
}
194
195
}}}
196
197
// 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::Support::BitSetData::a
void a(BitSetData a)
Perform "and" with a.
Definition:
bitset-base.hpp:346
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::TinyBitSet::add_to_mask
void add_to_mask(const BitSetData *b, BitSetData *mask) const
Add to mask.
Definition:
tiny-bit-set.hpp:91
Gecode::Int::Extensional::TinyBitSet::flush
void flush(void)
Make the set empty.
Definition:
tiny-bit-set.hpp:121
Gecode::Int::Extensional::TinyBitSet::words
unsigned int words(void) const
Return the number of required bit set words.
Definition:
tiny-bit-set.hpp:185
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::TinyBitSet::empty
bool empty(void) const
Check whether the set is empty.
Definition:
tiny-bit-set.hpp:164
Gecode::Int::Extensional::BitSet::_index
IndexType * _index
Indices.
Definition:
extensional.hh:242
Gecode::Int::Extensional::BitSet::_bits
BitSetData * _bits
Words.
Definition:
extensional.hh:244
Gecode::Int::Extensional::TinyBitSet::intersect_with_mask
void intersect_with_mask(const BitSetData *mask)
Intersect with mask, sparse mask if sparse is true.
Definition:
tiny-bit-set.hpp:99
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::Int::Extensional::TinyBitSet::ones
unsigned long long int ones(void) const
Return the number of ones.
Definition:
tiny-bit-set.hpp:148
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::TinyBitSet::size
unsigned int size(void) const
Return the total number of words.
Definition:
tiny-bit-set.hpp:191
Gecode::Int::Extensional::TinyBitSet
Tiny bit-set.
Definition:
extensional.hh:231
Gecode::Int::Extensional::TinyBitSet::TinyBitSet
friend class TinyBitSet
Definition:
extensional.hh:303
Gecode::Int::Extensional::TinyBitSet::_bits
BitSetData _bits[_size]
Words.
Definition:
extensional.hh:306
Gecode::Int::Extensional::TinyBitSet::clear_mask
void clear_mask(BitSetData *mask)
Clear the first limit words in mask.
Definition:
tiny-bit-set.hpp:82
Gecode::Int::Extensional::TinyBitSet::intersects
bool intersects(const BitSetData *b)
Check if has a non-empty intersection with the set.
Definition:
tiny-bit-set.hpp:129
forceinline
#define forceinline
Definition:
config.hpp:185
Gecode::Int::Extensional::TinyBitSet::nand_with_mask
void nand_with_mask(const BitSetData *b)
Perform "nand" with b.
Definition:
tiny-bit-set.hpp:114
Gecode::Int::Extensional::TinyBitSet::intersect_with_masks
void intersect_with_masks(const BitSetData *a, const BitSetData *b)
Intersect with the "or" of and b.
Definition:
tiny-bit-set.hpp:106
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::Int::Extensional::TinyBitSet::bits
unsigned long long int bits(void) const
Return an upper bound on the number of bits.
Definition:
tiny-bit-set.hpp:157
Gecode::Support::BitSetData::init
void init(bool setbits=false)
Initialize with all bits set if setbits.
Definition:
bitset-base.hpp:246
Gecode::Int::Extensional::TinyBitSet::width
unsigned int width(void) const
Return the highest active index.
Definition:
tiny-bit-set.hpp:173
GECODE_ASSUME
#define GECODE_ASSUME(p)
Assert certain property.
Definition:
macros.hpp:114