Generated on Fri Jan 10 2020 11:38:25 for Gecode by doxygen 1.8.16
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
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>
113  GECODE_NEVER;
114  }
115  template<class IndexType>
118  GECODE_NEVER;
119  }
120  template<class IndexType>
123  GECODE_NEVER;
124  }
125  template<class IndexType>
128  GECODE_NEVER;
129  }
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];
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
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::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
unsigned int width(void) const
Return the highest active index.
Definition: bit-set.hpp:66
void flush(void)
Make the set empty.
Definition: bit-set.hpp:105
void clear_mask(BitSetData *mask) const
Clear the first limit words in mask.
Definition: bit-set.hpp:149
void intersect_with_masks(const BitSetData *a, const BitSetData *b)
Intersect with the "or" of and b.
Definition: bit-set.hpp:191
void a(BitSetData a)
Perform "and" with a.
IndexType _limit
Limit.
Definition: extensional.hh:240
unsigned int words(void) const
Return the number of required bit set words.
Definition: bit-set.hpp:54
bool intersects(const BitSetData *b) const
Check if has a non-empty intersection with the set.
Definition: bit-set.hpp:219
unsigned long long int bits(void) const
Return an upper bound on the number of bits.
Definition: bit-set.hpp:247
void o(BitSetData a)
Perform "or" with a.
Computation spaces.
Definition: core.hpp:1742
IndexType * _index
Indices.
Definition: extensional.hh:242
void add_to_mask(const BitSetData *b, BitSetData *mask) const
Add to mask.
Definition: bit-set.hpp:159
BitSetData * _bits
Words.
Definition: extensional.hh:244
Gecode toplevel namespace
static const unsigned int bpb
Bits per base.
Definition: bitset-base.hpp:79
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
bool none(void) const
Whether no bits are set.
unsigned int size(void) const
Return the number of required bit set words.
Definition: bit-set.hpp:60
void nand_with_mask(const BitSetData *b)
Perform "nand" with b.
Definition: bit-set.hpp:207
friend class BitSet
Definition: extensional.hh:236
bool empty(void) const
Check whether the set is empty.
Definition: bit-set.hpp:48
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:56
unsigned int limit(void) const
Get the limit.
Definition: bit-set.hpp:42
unsigned long long int ones(void) const
Return the number of ones.
Definition: bit-set.hpp:238
Tiny bit-set.
Definition: extensional.hh:231
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
#define forceinline
Definition: config.hpp:185
Date item for bitsets.
Definition: bitset-base.hpp:65
Bit-set.
Definition: extensional.hh:235
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Gecode::IntArgs i({1, 2, 3, 4})
void init(bool setbits=false)
Initialize with all bits set if setbits.
void intersect_with_mask(const BitSetData *mask)
Intersect with mask, sparse mask if sparse is true.
Definition: bit-set.hpp:168
const FloatNum max
Largest allowed float value.
Definition: float.hh:844