Generated on Thu Apr 5 2018 19:44:19 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  * Last modified:
14  * $Date$ by $Author$
15  * $Revision$
16  *
17  * This file is part of Gecode, the generic constraint
18  * development environment:
19  * http://www.gecode.org
20  *
21  * Permission is hereby granted, free of charge, to any person obtaining
22  * a copy of this software and associated documentation files (the
23  * "Software"), to deal in the Software without restriction, including
24  * without limitation the rights to use, copy, modify, merge, publish,
25  * distribute, sublicense, and/or sell copies of the Software, and to
26  * permit persons to whom the Software is furnished to do so, subject to
27  * the following conditions:
28  *
29  * The above copyright notice and this permission notice shall be
30  * included in all copies or substantial portions of the Software.
31  *
32  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
33  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
34  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
35  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
36  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
37  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
38  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
39  *
40  */
41 
42 namespace Gecode { namespace Int { namespace Extensional {
43 
44  template<class IndexType>
46  BitSet<IndexType>::BitSet(Space& home, unsigned int n)
47  : _limit(static_cast<IndexType>(n)),
48  index(home.alloc<IndexType>(n)),
49  bits(home.alloc<BitSetData>(n)) {
50  // Set all bits in all words (including the last)
51  for (IndexType i=_limit; i--; ) {
52  bits[i].init(true);
53  index[i] = i;
54  }
55  }
56 
57  template<class IndexType>
58  template<class OldIndexType>
61  const BitSet<OldIndexType>& bs)
62  : _limit(bs._limit),
63  index(home.alloc<IndexType>(_limit)),
64  bits(home.alloc<BitSetData>(_limit)) {
65  assert(_limit > 0U);
66  for (IndexType i = _limit; i--; ) {
67  bits[i] = bs.bits[i];
68  index[i] = bs.index[i];
69  }
70  }
71 
72  template<class IndexType>
76  }
77  template<class IndexType>
81  }
82  template<class IndexType>
86  }
87  template<class IndexType>
91  }
92 
93  template<class IndexType>
94  forceinline void
96  assert(_limit > 0U);
97  BitSetData w_i = bits[i];
98  if (w != w_i) {
99  bits[i] = w;
100  if (w.none()) {
101  assert(bits[i].none());
102  bits[i] = bits[_limit-1];
103  index[i] = index[_limit-1];
104  _limit--;
105  }
106  }
107  }
108 
109  template<class IndexType>
110  forceinline void
112  assert(_limit > 0U);
113  for (IndexType i = _limit; i--; ) {
114  mask[i].init(false);
115  assert(mask[i].none());
116  }
117  }
118 
119  template<class IndexType>
120  forceinline void
122  assert(_limit > 0U);
123  for (IndexType i = _limit; i--; )
124  mask[i] = BitSetData::o(mask[i],b[index[i]]);
125  }
126 
127  template<class IndexType>
128  template<bool sparse>
129  forceinline void
131  assert(_limit > 0U);
132  if (sparse) {
133  for (IndexType i = _limit; i--; ) {
134  assert(!bits[i].none());
135  BitSetData w_i = bits[i];
136  BitSetData w_a = BitSetData::a(w_i, mask[index[i]]);
137  replace_and_decrease(i,w_a);
138  assert(i == _limit || !bits[i].none());
139  }
140  } else { // The same except different indexing in mask
141  for (IndexType i = _limit; i--; ) {
142  assert(!bits[i].none());
143  BitSetData w_i = bits[i];
144  BitSetData w_a = BitSetData::a(w_i, mask[i]);
145  replace_and_decrease(i,w_a);
146  assert(i == _limit || !bits[i].none());
147  }
148  }
149  }
150 
151  template<class IndexType>
152  forceinline void
154  const BitSetData* b) {
155  assert(_limit > 0U);
156  for (IndexType i = _limit; i--; ) {
157  assert(!bits[i].none());
158  BitSetData w_i = bits[i];
159  IndexType offset = index[i];
160  BitSetData w_o = BitSetData::o(a[offset], b[offset]);
161  BitSetData w_a = BitSetData::a(w_i,w_o);
162  replace_and_decrease(i,w_a);
163  assert(i == _limit || !bits[i].none());
164  }
165  }
166 
167  template<class IndexType>
168  forceinline void
170  assert(_limit > 0U);
171  for (IndexType i = _limit; i--; ) {
172  assert(!bits[i].none());
173  BitSetData w = BitSetData::a(bits[i],~(b[index[i]]));
175  assert(i == _limit || !bits[i].none());
176  }
177  }
178 
179  template<class IndexType>
180  forceinline bool
182  for (IndexType i = _limit; i--; )
183  if (!BitSetData::a(bits[i],b[index[i]]).none())
184  return true;
185  return false;
186  }
187 
188 
189  template<class IndexType>
190  forceinline unsigned int
192  return static_cast<unsigned int>(_limit);
193  }
194 
195  template<class IndexType>
196  forceinline bool
198  return _limit == 0U;
199  }
200 
201  template<class IndexType>
202  forceinline unsigned int
204  return static_cast<unsigned int>(_limit);
205  }
206 
207  template<class IndexType>
208  forceinline unsigned int
210  return words();
211  }
212 
213  template<class IndexType>
214  forceinline unsigned int
216  assert(!empty());
217  IndexType width = index[0];
218  for (IndexType i = _limit; i--; ) {
219  width = std::max(width,index[i]);
220  }
221  assert(static_cast<unsigned int>(width+1U) >= words());
222  return static_cast<unsigned int>(width+1U);
223  }
224 
225 }}}
226 
227 // STATISTICS: int-prop
const FloatNum max
Largest allowed float value.
Definition: float.hh:848
bool empty(void) const
Check whether the set is empty.
Definition: bit-set.hpp:197
void nand_with_mask(const BitSetData *b)
Perform "nand" with b.
Definition: bit-set.hpp:169
void intersect_with_masks(const BitSetData *a, const BitSetData *b)
Intersect with the "or" of and b.
Definition: bit-set.hpp:153
#define forceinline
Definition: config.hpp:182
Computation spaces.
Definition: core.hpp:1668
unsigned int width(void) const
Return the highest active index.
Definition: bit-set.hpp:215
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
void add_to_mask(const BitSetData *b, BitSetData *mask) const
Add to mask.
Definition: bit-set.hpp:121
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:203
void init(bool setbits=false)
Initialize with all bits set if setbits.
IndexType * index
Indices.
Definition: extensional.hh:247
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:181
struct Gecode::@585::NNF::@62::@64 a
For atomic nodes.
unsigned int limit(void) const
Get the limit.
Definition: bit-set.hpp:191
void a(BitSetData a)
Perform "and" with a.
Date item for bitsets.
Definition: bitset-base.hpp:69
void intersect_with_mask(const BitSetData *mask)
Intersect with mask, sparse mask if sparse is true.
Definition: bit-set.hpp:130
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:95
Gecode toplevel namespace
void clear_mask(BitSetData *mask) const
Clear the first limit words in mask.
Definition: bit-set.hpp:111
unsigned int size(void) const
Return the number of required bit set words.
Definition: bit-set.hpp:209
bool none(void) const
Whether no bits are set.
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:60