Generated on Sat Jun 2 2018 07:17:44 for Gecode by doxygen 1.8.13
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 = 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 = sz; i--; )
74  bits[i].init(false);
75  for (unsigned int i = sbs.words(); i--; ) {
76  bits[sbs.index[i]] = sbs.bits[i];
77  }
78  assert(!empty());
79  }
80 
81  template<unsigned int sz>
82  forceinline void
84  for (unsigned int i=sz; i--; ) {
85  mask[i].init(false);
86  assert(mask[i].none());
87  }
88  }
89 
90  template<unsigned int sz>
91  forceinline void
93  for (unsigned int i=sz; i--; )
94  mask[i] = BitSetData::o(mask[i],b[i]);
95  }
96 
97  template<unsigned int sz>
98  template<bool sparse>
99  forceinline void
101  for (unsigned int i=sz; i--; )
102  bits[i] = BitSetData::a(bits[i], mask[i]);
103  }
104 
105  template<unsigned int sz>
106  forceinline void
108  for (unsigned int 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=sz; i--; )
116  bits[i] = BitSetData::a(bits[i],~(b[i]));
117  }
118 
119  template<unsigned int sz>
120  forceinline bool
122  for (unsigned int i=sz; i--; )
123  if (!BitSetData::a(bits[i],b[i]).none())
124  return true;
125  return false;
126  }
127 
128  template<unsigned int sz>
129  forceinline bool
130  TinyBitSet<sz>::empty(void) const { // Linear complexity...
131  for (unsigned int i=sz; i--; )
132  if (!bits[i].none())
133  return false;
134  return true;
135  }
136 
137  template<unsigned int sz>
138  forceinline unsigned int
139  TinyBitSet<sz>::width(void) const {
140  assert(!empty());
142  for (unsigned int i=sz; i--; )
143  if (!bits[i].none())
144  return i+1U;
145  GECODE_NEVER;
146  return 0U;
147  }
148 
149  template<unsigned int sz>
150  forceinline unsigned int
151  TinyBitSet<sz>::words(void) const {
152  return width();
153  }
154 
155  template<unsigned int sz>
156  forceinline unsigned int
157  TinyBitSet<sz>::size(void) const {
158  return sz;
159  }
160 
161 }}}
162 
163 // STATISTICS: int-prop
void intersect_with_masks(const BitSetData *a, const BitSetData *b)
Intersect with the "or" of and b.
#define GECODE_ASSUME(p)
Assert certain property.
Definition: macros.hpp:114
bool empty(void) const
Check whether the set is empty.
Definition: bit-set.hpp:193
#define forceinline
Definition: config.hpp:185
Computation spaces.
Definition: core.hpp:1701
void intersect_with_mask(const BitSetData *mask)
Intersect with mask, sparse mask if sparse is true.
void add_to_mask(const BitSetData *b, BitSetData *mask) const
Add to mask.
BitSetData bits[_size]
Words.
Definition: extensional.hh:299
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
bool empty(void) const
Check whether the set is empty.
void o(BitSetData a)
Perform "or" with a.
unsigned int size(void) const
Return the total number of words.
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)
void clear_mask(BitSetData *mask)
Clear the first limit words in mask.
void nand_with_mask(const BitSetData *b)
Perform "nand" with b.
unsigned int width(void) const
Return the highest active index.
unsigned int words(void) const
Return the number of required bit set words.
struct Gecode::@585::NNF::@62::@64 a
For atomic nodes.
void a(BitSetData a)
Perform "and" with a.
bool intersects(const BitSetData *b)
Check if has a non-empty intersection with the set.
Date item for bitsets.
Definition: bitset-base.hpp:65
Gecode toplevel namespace
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:56