Generated on Mon Feb 8 2021 00:00:00 for Gecode by doxygen 1.8.20
tuple-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  * Mikael Lagerkvist <lagerkvist@gecode.org>
5  * Christian Schulte <schulte@gecode.org>
6  *
7  * Copyright:
8  * Mikael Lagerkvist, 2007
9  * Christian Schulte, 2017
10  *
11  * This file is part of Gecode, the generic constraint
12  * development environment:
13  * http://www.gecode.org
14  *
15  * Permission is hereby granted, free of charge, to any person obtaining
16  * a copy of this software and associated documentation files (the
17  * "Software"), to deal in the Software without restriction, including
18  * without limitation the rights to use, copy, modify, merge, publish,
19  * distribute, sublicense, and/or sell copies of the Software, and to
20  * permit persons to whom the Software is furnished to do so, subject to
21  * the following conditions:
22  *
23  * The above copyright notice and this permission notice shall be
24  * included in all copies or substantial portions of the Software.
25  *
26  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
27  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
28  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
29  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
30  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
31  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
32  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
33  *
34  */
35 
36 #include <sstream>
37 
38 namespace Gecode {
39 
40  /*
41  * Ranges
42  *
43  */
44  forceinline unsigned int
45  TupleSet::Range::width(void) const {
46  return static_cast<unsigned int>(max - min + 1);
47  }
48 
50  TupleSet::Range::supports(unsigned int n_words, int n) const {
51  assert((min <= n) && (n <= max));
52  return s + n_words * static_cast<unsigned int>(n - min);
53  }
54 
55 
56  /*
57  * Tuple set data
58  *
59  */
62  : arity(a), n_words(0U), // To be initialized in finalize
63  n_tuples(0), n_free(n_initial_free),
64  min(Int::Limits::max), max(Int::Limits::min), key(0),
65  td(heap.alloc<int>(n_initial_free * a)),
66  vd(heap.alloc<ValueData>(a)),
67  range(nullptr), support(nullptr) {
68  }
69 
70  forceinline bool
72  return n_free < 0;
73  }
74 
77  if (n_free == 0)
78  resize();
79  assert(n_free > 0);
80  n_free--;
81  Tuple t = td + n_tuples*arity;
82  n_tuples++;
83  return t;
84  }
85 
87  TupleSet::Data::get(int i) const {
88  assert((i >= 0) && (i < n_tuples));
89  return td + i*arity;
90  }
91 
92  forceinline unsigned int
94  if (n > 1U) {
95  unsigned int l=0U, h=n-1U;
96  while (true) {
97  assert(l<=h);
98  unsigned int m = l + ((h-l) >> 1);
99  if (k < r[m].min)
100  h=m-1U;
101  else if (k > r[m].max)
102  l=m+1U;
103  else
104  return m;
105  }
106  GECODE_NEVER;
107  } else {
108  return 0U;
109  }
110  }
111 
112  forceinline void
113  TupleSet::Data::set(BitSetData* d, unsigned int i) {
114  d[i / BitSetData::bpb].set(i % BitSetData::bpb);
115  }
116 
117  forceinline bool
118  TupleSet::Data::get(const BitSetData* d, unsigned int i) {
119  return d[i / BitSetData::bpb].get(i % BitSetData::bpb);
120  }
121 
122  forceinline unsigned int
124  return static_cast<unsigned int>((t - td) / static_cast<unsigned int>(arity));
125  }
126 
128  TupleSet::Data::fst(int i) const {
129  return &vd[i].r[0];
130  }
132  TupleSet::Data::lst(int i) const {
133  return &vd[i].r[vd[i].n-1U];
134  }
135 
136 
137  /*
138  * Tuple set
139  *
140  */
143  _add(t); return *this;
144  }
145 
148 
150  TupleSet::operator bool(void) const {
151  return object() != nullptr;
152  }
153 
154  forceinline void
156  Data* d = static_cast<Data*>(object());
157  if (!d->finalized())
158  d->finalize();
159  }
160 
161  forceinline bool
162  TupleSet::finalized(void) const {
163  return static_cast<Data*>(object())->finalized();
164  }
165 
167  TupleSet::data(void) const {
168  assert(finalized());
169  return *static_cast<Data*>(object());
170  }
172  TupleSet::raw(void) const {
173  return *static_cast<Data*>(object());
174  }
175 
176  forceinline bool
178  return !(*this == t);
179  }
180  forceinline int
181  TupleSet::arity(void) const {
182  return raw().arity;
183  }
184  forceinline int
185  TupleSet::tuples(void) const {
186  return raw().n_tuples;
187  }
188  forceinline unsigned int
189  TupleSet::words(void) const {
190  return data().n_words;
191  }
192  forceinline int
193  TupleSet::min(void) const {
194  return data().min;
195  }
196  forceinline int
197  TupleSet::max(void) const {
198  return data().max;
199  }
202  return data().get(i);
203  }
205  TupleSet::fst(int i) const {
206  return data().fst(i);
207  }
209  TupleSet::lst(int i) const {
210  return data().lst(i);
211  }
212 
213  forceinline bool
215  if (tuples() != t.tuples())
216  return false;
217  if (arity() != t.arity())
218  return false;
219  if (min() != t.min())
220  return false;
221  if (max() != t.max())
222  return false;
223  return equal(t);
224  }
225 
226  forceinline std::size_t
227  TupleSet::hash(void) const {
228  return data().key;
229  }
230 
231 
232  template<class Char, class Traits>
233  std::basic_ostream<Char,Traits>&
234  operator <<(std::basic_ostream<Char,Traits>& os, const TupleSet& ts) {
235  std::basic_ostringstream<Char,Traits> s;
236  s.copyfmt(os); s.width(0);
237  s << "Number of tuples: " << ts.tuples()
238  << " (number of words: " << ts.words() << " with "
239  << Support::BitSetData::bpb << " bits)" << std::endl;
240  for (int a=0; a < ts.arity(); a++) {
241  unsigned int size = 0U;
242  for (const TupleSet::Range* c=ts.fst(a); c<=ts.lst(a); c++)
243  size += c->width();
244  s << "\t[" << a << "] size: " << size
245  << ", width: "
246  << static_cast<unsigned int>(ts.lst(a)->max - ts.fst(a)->min + 1)
247  << ", ranges: "
248  << (ts.lst(a) - ts.fst(a) + 1U)
249  << std::endl;
250  }
251  return os << s.str();
252  }
253 
254 
255  /*
256  * Range iterator
257  *
258  */
261  c = &(ts.data().vd[i].r[0]);
262  l = c + ts.data().vd[i].n;
263  }
264 
265  forceinline bool
267  return c<l;
268  }
269  forceinline void
271  c++;
272  }
273 
274  forceinline int
275  TupleSet::Ranges::min(void) const {
276  return c->min;
277  }
278  forceinline int
279  TupleSet::Ranges::max(void) const {
280  return c->max;
281  }
282  forceinline unsigned int
284  return c->width();
285  }
286 
287 }
288 
289 // STATISTICS: int-prop
290 
Data & raw(void) const
Get raw data (must be initialized)
Definition: tuple-set.hpp:172
const Range * lst(int i) const
Return last range for position i.
Definition: tuple-set.hpp:209
Data about values in the table.
Definition: int.hh:2216
TupleSet & add(const IntArgs &t)
Add tuple t to tuple set.
Definition: tuple-set.hpp:142
friend FloatVal max(const FloatVal &x, const FloatVal &y)
Definition: val.hpp:386
Tuple get(int i) const
Return tuple with number i.
Definition: tuple-set.hpp:87
const Range * fst(int i) const
Return first range for position i.
Definition: tuple-set.hpp:205
unsigned int words(void) const
Return number of required bit set words.
Definition: tuple-set.hpp:189
int max
Maximum value.
Definition: int.hh:2206
int min(void) const
Return smallest value of range.
Definition: tuple-set.hpp:275
const Range * lst(int i) const
Return last range for position i.
Definition: tuple-set.hpp:132
bool operator()(void) const
Test whether iterator is still at a range.
Definition: tuple-set.hpp:266
friend FloatVal min(const FloatVal &x, const FloatVal &y)
Definition: val.hpp:398
unsigned int size(I &i)
Size of all ranges of range iterator i.
int min
Minimum value.
Definition: int.hh:2204
int min(void) const
Return minimal value in all tuples.
Definition: tuple-set.hpp:193
int min
Smallest value.
Definition: int.hh:2243
SharedHandle::Object * object(void) const
Access to the shared object.
NodeType t
Type of node.
Definition: bool-expr.cpp:230
int max(void) const
Return maximal value in all tuples.
Definition: tuple-set.hpp:197
void range(Home home, const IntVarArgs &x, SetVar y, SetVar z)
Post constraint .
Definition: aliases.hpp:158
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
Definition: tuple-set.hpp:283
Gecode toplevel namespace
Data stored for a Table.
Definition: int.hh:2229
std::basic_ostream< Char, Traits > & operator<<(std::basic_ostream< Char, Traits > &os, const TupleSet &ts)
Definition: tuple-set.hpp:234
TupleSet(void)
Construct an unitialized tuple set.
Definition: tuple-set.hpp:147
static const unsigned int bpb
Bits per base.
Definition: bitset-base.hpp:79
void finalize(void)
Finalize tuple set.
Definition: tuple-set.hpp:155
unsigned int n_words
Number of words for support.
Definition: int.hh:2237
Tuple add(void)
Return newly added tuple.
Definition: tuple-set.hpp:76
static void set(BitSetData *d, unsigned int n)
Set bit n in bitset data d.
Definition: tuple-set.hpp:113
Range * r
Ranges.
Definition: int.hh:2221
const BitSetData * supports(unsigned int n_words, int n) const
Return the supports for value n.
Definition: tuple-set.hpp:50
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
int * Tuple
Type of a tuple.
Definition: int.hh:2197
void _add(const IntArgs &t)
Add tuple t to tuple set.
Definition: tuple-set.cpp:460
bool finalized(void) const
Is tuple set finalized.
Definition: tuple-set.hpp:162
std::size_t key
Hash key.
Definition: int.hh:2247
Class represeting a set of tuples.
Definition: int.hh:2191
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:56
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
Heap heap
The single global heap.
Definition: heap.cpp:44
unsigned int tuple2idx(Tuple t) const
Map tuple address to index.
Definition: tuple-set.hpp:123
int max
Largest value.
Definition: int.hh:2245
Tuple operator[](int i) const
Get tuple i.
Definition: tuple-set.hpp:201
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
bool equal(const TupleSet &t) const
Test whether tuple set is equal to t.
Definition: tuple-set.cpp:447
bool operator!=(const TupleSet &t) const
Test whether tuple set is different from t.
Definition: tuple-set.hpp:177
Gecode::IntSet d(v, 7)
ValueData * vd
Value data.
Definition: int.hh:2251
std::size_t hash(void) const
Return hash key.
Definition: tuple-set.hpp:227
const Range * fst(int i) const
Return first range for position i.
Definition: tuple-set.hpp:128
int tuples(void) const
Number of tuples.
Definition: tuple-set.hpp:185
Ranges(const TupleSet &ts, int i)
Initialize for column i.
Definition: tuple-set.hpp:260
bool operator==(const TupleSet &t) const
Test whether tuple set is equal to t.
Definition: tuple-set.hpp:214
#define forceinline
Definition: config.hpp:192
int arity(void) const
Arity of tuple set.
Definition: tuple-set.hpp:181
unsigned int width(void) const
Return the width.
Definition: tuple-set.hpp:45
void operator++(void)
Move iterator to next range (if possible)
Definition: tuple-set.hpp:270
Data & data(void) const
Get data (must be initialized and finalized)
Definition: tuple-set.hpp:167
Gecode::FloatVal c(-8, 8)
Date item for bitsets.
Definition: bitset-base.hpp:65
int n_tuples
Number of Tuples.
Definition: int.hh:2239
bool finalized(void) const
Is datastructure finalized.
Definition: tuple-set.hpp:71
Range information.
Definition: int.hh:2201
Data(int a)
Initialize as empty tuple set with arity a.
Definition: tuple-set.hpp:61
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Passing integer arguments.
Definition: int.hh:628
Gecode::IntArgs i({1, 2, 3, 4})
int max(void) const
Return largest value of range.
Definition: tuple-set.hpp:279
unsigned int n
Number of ranges.
Definition: int.hh:2219
unsigned int start(int n) const
Find start range for value n.
Definition: tuple-set.hpp:93
int arity
Arity.
Definition: int.hh:2235