Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
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
38namespace Gecode { namespace Int { namespace Extensional {
39
40 template<class IndexType>
41 forceinline unsigned int
43 return static_cast<unsigned int>(_limit);
44 }
45
46 template<class IndexType>
47 forceinline bool
49 return _limit == 0U;
50 }
51
52 template<class IndexType>
53 forceinline unsigned int
55 return static_cast<unsigned int>(_limit);
56 }
57
58 template<class IndexType>
59 forceinline unsigned int
61 return words();
62 }
63
64 template<class IndexType>
65 forceinline unsigned int
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>
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>
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
106 _limit = 0U;
107 assert(empty());
108 }
109
110 template<class IndexType>
115 template<class IndexType>
120 template<class IndexType>
125 template<class IndexType>
130
131 template<class IndexType>
132 forceinline void
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
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
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
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
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];
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
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
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
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
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
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
struct Gecode::@603::NNF::@65::@66 b
For binary nodes (and, or, eqv)
int n
Number of negative literals for node type.
struct Gecode::@603::NNF::@65::@67 a
For atomic nodes.
unsigned long long int bits(void) const
Return an upper bound on the number of bits.
Definition bit-set.hpp:247
void intersect_with_mask(const BitSetData *mask)
Intersect with mask, sparse mask if sparse is true.
Definition bit-set.hpp:168
unsigned int width(void) const
Return the highest active index.
Definition bit-set.hpp:66
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
unsigned long long int ones(void) const
Return the number of ones.
Definition bit-set.hpp:238
bool intersects(const BitSetData *b) const
Check if has a non-empty intersection with the set.
Definition bit-set.hpp:219
void intersect_with_masks(const BitSetData *a, const BitSetData *b)
Intersect with the "or" of and b.
Definition bit-set.hpp:191
void add_to_mask(const BitSetData *b, BitSetData *mask) const
Add to mask.
Definition bit-set.hpp:159
unsigned int size(void) const
Return the number of required bit set words.
Definition bit-set.hpp:60
unsigned int limit(void) const
Get the limit.
Definition bit-set.hpp:42
void clear_mask(BitSetData *mask) const
Clear the first limit words in mask.
Definition bit-set.hpp:149
bool empty(void) const
Check whether the set is empty.
Definition bit-set.hpp:48
unsigned int words(void) const
Return the number of required bit set words.
Definition bit-set.hpp:54
void flush(void)
Make the set empty.
Definition bit-set.hpp:105
void nand_with_mask(const BitSetData *b)
Perform "nand" with b.
Definition bit-set.hpp:207
Computation spaces.
Definition core.hpp:1742
Date item for bitsets.
static const unsigned int bpb
Bits per base.
void init(bool setbits=false)
Initialize with all bits set if setbits.
void a(BitSetData a)
Perform "and" with a.
bool none(void) const
Whether no bits are set.
void o(BitSetData a)
Perform "or" with a.
int offset(void) const
Integer-precision integer scale view.
Definition view.hpp:642
Gecode toplevel namespace
#define forceinline
Definition config.hpp:187
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56