Generated on Sat Jun 2 2018 07:17:44 for Gecode by doxygen 1.8.13
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>
42  BitSet<IndexType>::BitSet(Space& home, unsigned int n)
43  : _limit(static_cast<IndexType>(n)),
44  index(home.alloc<IndexType>(n)),
45  bits(home.alloc<BitSetData>(n)) {
46  // Set all bits in all words (including the last)
47  for (IndexType i=_limit; i--; ) {
48  bits[i].init(true);
49  index[i] = i;
50  }
51  }
52 
53  template<class IndexType>
54  template<class OldIndexType>
57  const BitSet<OldIndexType>& bs)
58  : _limit(bs._limit),
59  index(home.alloc<IndexType>(_limit)),
60  bits(home.alloc<BitSetData>(_limit)) {
61  assert(_limit > 0U);
62  for (IndexType i = _limit; i--; ) {
63  bits[i] = bs.bits[i];
64  index[i] = bs.index[i];
65  }
66  }
67 
68  template<class IndexType>
72  }
73  template<class IndexType>
77  }
78  template<class IndexType>
82  }
83  template<class IndexType>
87  }
88 
89  template<class IndexType>
90  forceinline void
92  assert(_limit > 0U);
93  BitSetData w_i = bits[i];
94  if (w != w_i) {
95  bits[i] = w;
96  if (w.none()) {
97  assert(bits[i].none());
98  bits[i] = bits[_limit-1];
99  index[i] = index[_limit-1];
100  _limit--;
101  }
102  }
103  }
104 
105  template<class IndexType>
106  forceinline void
108  assert(_limit > 0U);
109  for (IndexType i = _limit; i--; ) {
110  mask[i].init(false);
111  assert(mask[i].none());
112  }
113  }
114 
115  template<class IndexType>
116  forceinline void
118  assert(_limit > 0U);
119  for (IndexType i = _limit; i--; )
120  mask[i] = BitSetData::o(mask[i],b[index[i]]);
121  }
122 
123  template<class IndexType>
124  template<bool sparse>
125  forceinline void
127  assert(_limit > 0U);
128  if (sparse) {
129  for (IndexType i = _limit; i--; ) {
130  assert(!bits[i].none());
131  BitSetData w_i = bits[i];
132  BitSetData w_a = BitSetData::a(w_i, mask[index[i]]);
133  replace_and_decrease(i,w_a);
134  assert(i == _limit || !bits[i].none());
135  }
136  } else { // The same except different indexing in mask
137  for (IndexType i = _limit; i--; ) {
138  assert(!bits[i].none());
139  BitSetData w_i = bits[i];
140  BitSetData w_a = BitSetData::a(w_i, mask[i]);
141  replace_and_decrease(i,w_a);
142  assert(i == _limit || !bits[i].none());
143  }
144  }
145  }
146 
147  template<class IndexType>
148  forceinline void
150  const BitSetData* b) {
151  assert(_limit > 0U);
152  for (IndexType i = _limit; i--; ) {
153  assert(!bits[i].none());
154  BitSetData w_i = bits[i];
155  IndexType offset = index[i];
156  BitSetData w_o = BitSetData::o(a[offset], b[offset]);
157  BitSetData w_a = BitSetData::a(w_i,w_o);
158  replace_and_decrease(i,w_a);
159  assert(i == _limit || !bits[i].none());
160  }
161  }
162 
163  template<class IndexType>
164  forceinline void
166  assert(_limit > 0U);
167  for (IndexType i = _limit; i--; ) {
168  assert(!bits[i].none());
169  BitSetData w = BitSetData::a(bits[i],~(b[index[i]]));
171  assert(i == _limit || !bits[i].none());
172  }
173  }
174 
175  template<class IndexType>
176  forceinline bool
178  for (IndexType i = _limit; i--; )
179  if (!BitSetData::a(bits[i],b[index[i]]).none())
180  return true;
181  return false;
182  }
183 
184 
185  template<class IndexType>
186  forceinline unsigned int
188  return static_cast<unsigned int>(_limit);
189  }
190 
191  template<class IndexType>
192  forceinline bool
194  return _limit == 0U;
195  }
196 
197  template<class IndexType>
198  forceinline unsigned int
200  return static_cast<unsigned int>(_limit);
201  }
202 
203  template<class IndexType>
204  forceinline unsigned int
206  return words();
207  }
208 
209  template<class IndexType>
210  forceinline unsigned int
212  assert(!empty());
213  IndexType width = index[0];
214  for (IndexType i = _limit; i--; ) {
215  width = std::max(width,index[i]);
216  }
217  assert(static_cast<unsigned int>(width+1U) >= words());
218  return static_cast<unsigned int>(width+1U);
219  }
220 
221 }}}
222 
223 // STATISTICS: int-prop
const FloatNum max
Largest allowed float value.
Definition: float.hh:844
bool empty(void) const
Check whether the set is empty.
Definition: bit-set.hpp:193
void nand_with_mask(const BitSetData *b)
Perform "nand" with b.
Definition: bit-set.hpp:165
void intersect_with_masks(const BitSetData *a, const BitSetData *b)
Intersect with the "or" of and b.
Definition: bit-set.hpp:149
#define forceinline
Definition: config.hpp:185
Computation spaces.
Definition: core.hpp:1701
unsigned int width(void) const
Return the highest active index.
Definition: bit-set.hpp:211
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
void add_to_mask(const BitSetData *b, BitSetData *mask) const
Add to mask.
Definition: bit-set.hpp:117
void o(BitSetData a)
Perform "or" with a.
unsigned int words(void) const
Return the number of required bit set words.
Definition: bit-set.hpp:199
void init(bool setbits=false)
Initialize with all bits set if setbits.
IndexType * index
Indices.
Definition: extensional.hh:243
struct Gecode::@585::NNF::@62::@63 b
For binary nodes (and, or, eqv)
bool intersects(const BitSetData *b) const
Check if has a non-empty intersection with the set.
Definition: bit-set.hpp:177
struct Gecode::@585::NNF::@62::@64 a
For atomic nodes.
unsigned int limit(void) const
Get the limit.
Definition: bit-set.hpp:187
void a(BitSetData a)
Perform "and" with a.
Date item for bitsets.
Definition: bitset-base.hpp:65
void intersect_with_mask(const BitSetData *mask)
Intersect with mask, sparse mask if sparse is true.
Definition: bit-set.hpp:126
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:91
Gecode toplevel namespace
void clear_mask(BitSetData *mask) const
Clear the first limit words in mask.
Definition: bit-set.hpp:107
unsigned int size(void) const
Return the number of required bit set words.
Definition: bit-set.hpp:205
bool none(void) const
Whether no bits are set.
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:56