Generated on Thu Apr 5 2018 19:44:19 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  * 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  /*
45  * Tiny bit-set
46  *
47  */
48  template<unsigned int sz>
51  assert(n <= sz);
53  for (unsigned int i=0U; i < n; i++)
54  bits[i].init(true);
56  for (unsigned int i=n; i < sz; i++)
57  bits[i].init(false);
58  }
59 
60  template<unsigned int sz>
61  template<unsigned int largersz>
64  assert(sz <= largersz);
65  assert(!sbs.empty());
66  for (unsigned int i = sz; i--; )
67  bits[i] = sbs.bits[i];
68  assert(!empty());
69  }
70 
71  template<unsigned int sz>
72  template<class IndexType>
75  assert(sz == sbs.width());
76  assert(!sbs.empty());
77  for (unsigned int i = sz; i--; )
78  bits[i].init(false);
79  for (unsigned int i = sbs.words(); i--; ) {
80  bits[sbs.index[i]] = sbs.bits[i];
81  }
82  assert(!empty());
83  }
84 
85  template<unsigned int sz>
86  forceinline void
88  for (unsigned int i=sz; i--; ) {
89  mask[i].init(false);
90  assert(mask[i].none());
91  }
92  }
93 
94  template<unsigned int sz>
95  forceinline void
97  for (unsigned int i=sz; i--; )
98  mask[i] = BitSetData::o(mask[i],b[i]);
99  }
100 
101  template<unsigned int sz>
102  template<bool sparse>
103  forceinline void
105  for (unsigned int i=sz; i--; )
106  bits[i] = BitSetData::a(bits[i], mask[i]);
107  }
108 
109  template<unsigned int sz>
110  forceinline void
112  for (unsigned int i=sz; i--; )
113  bits[i] = BitSetData::a(bits[i], BitSetData::o(a[i],b[i]));
114  }
115 
116  template<unsigned int sz>
117  forceinline void
119  for (unsigned int i=sz; i--; )
120  bits[i] = BitSetData::a(bits[i],~(b[i]));
121  }
122 
123  template<unsigned int sz>
124  forceinline bool
126  for (unsigned int i=sz; i--; )
127  if (!BitSetData::a(bits[i],b[i]).none())
128  return true;
129  return false;
130  }
131 
132  template<unsigned int sz>
133  forceinline bool
134  TinyBitSet<sz>::empty(void) const { // Linear complexity...
135  for (unsigned int i=sz; i--; )
136  if (!bits[i].none())
137  return false;
138  return true;
139  }
140 
141  template<unsigned int sz>
142  forceinline unsigned int
143  TinyBitSet<sz>::width(void) const {
144  assert(!empty());
146  for (unsigned int i=sz; i--; )
147  if (!bits[i].none())
148  return i+1U;
149  GECODE_NEVER;
150  return 0U;
151  }
152 
153  template<unsigned int sz>
154  forceinline unsigned int
155  TinyBitSet<sz>::words(void) const {
156  return width();
157  }
158 
159  template<unsigned int sz>
160  forceinline unsigned int
161  TinyBitSet<sz>::size(void) const {
162  return sz;
163  }
164 
165 }}}
166 
167 // STATISTICS: int-prop
void intersect_with_masks(const BitSetData *a, const BitSetData *b)
Intersect with the "or" of and b.
bool empty(void) const
Check whether the set is empty.
Definition: bit-set.hpp:197
#define forceinline
Definition: config.hpp:182
Computation spaces.
Definition: core.hpp:1668
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:303
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
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: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)
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:69
Gecode toplevel namespace
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:60