Generated on Tue Jan 26 2021 00:00:00 for Gecode by doxygen 1.9.1
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 
38 namespace 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
148  TinyBitSet<sz>::ones(void) const {
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
157  TinyBitSet<sz>::bits(void) const {
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
173  TinyBitSet<sz>::width(void) const {
174  assert(!empty());
176  for (unsigned int i=sz; i--; )
177  if (!_bits[i].none())
178  return i+1U;
179  GECODE_NEVER;
180  return 0U;
181  }
182 
183  template<unsigned int sz>
184  forceinline unsigned int
185  TinyBitSet<sz>::words(void) const {
186  return width();
187  }
188 
189  template<unsigned int sz>
190  forceinline unsigned int
191  TinyBitSet<sz>::size(void) const {
192  return sz;
193  }
194 
195 }}}
196 
197 // STATISTICS: int-prop
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
struct Gecode::@602::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.
BitSetData _bits[_size]
Words.
Definition: extensional.hh:306
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.
Definition: bitset-base.hpp:65
static const unsigned int bpb
Bits per base.
Definition: bitset-base.hpp:79
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::IntArgs i({1, 2, 3, 4})
#define forceinline
Definition: config.hpp:185
#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