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