Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
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
38namespace Gecode { namespace Int { namespace Extensional {
39
40 /*
41 * Tiny bit-set
42 *
43 */
44 template<unsigned int sz>
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>
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>
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
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
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
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
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
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
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
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
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
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
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
174 assert(!empty());
176 for (unsigned int i=sz; i--; )
177 if (!_bits[i].none())
178 return i+1U;
180 return 0U;
181 }
182
183 template<unsigned int sz>
184 forceinline unsigned int
186 return width();
187 }
188
189 template<unsigned int sz>
190 forceinline unsigned int
192 return sz;
193 }
194
195}}}
196
197// 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 int width(void) const
Return the highest active index.
Definition bit-set.hpp:66
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 intersect_with_mask(const BitSetData *mask)
Intersect with mask, sparse mask if sparse is true.
unsigned int words(void) const
Return the number of required bit set words.
unsigned int width(void) const
Return the highest active index.
bool intersects(const BitSetData *b)
Check if has a non-empty intersection with the set.
void add_to_mask(const BitSetData *b, BitSetData *mask) const
Add to mask.
unsigned long long int bits(void) const
Return an upper bound on the number of bits.
unsigned long long int ones(void) const
Return the number of ones.
unsigned int size(void) const
Return the total number of words.
bool empty(void) const
Check whether the set is empty.
void intersect_with_masks(const BitSetData *a, const BitSetData *b)
Intersect with the "or" of and b.
void flush(void)
Make the set empty.
void nand_with_mask(const BitSetData *b)
Perform "nand" with b.
void clear_mask(BitSetData *mask)
Clear the first limit words in mask.
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.
void o(BitSetData a)
Perform "or" with a.
Gecode toplevel namespace
#define forceinline
Definition config.hpp:187
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56
#define GECODE_ASSUME(p)
Assert certain property.
Definition macros.hpp:114