Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
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
38namespace Gecode {
39
40 /*
41 * Ranges
42 *
43 */
44 forceinline unsigned int
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
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 }
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
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
276 return c->min;
277 }
278 forceinline int
280 return c->max;
281 }
282 forceinline unsigned int
284 return c->width();
285 }
286
287}
288
289// STATISTICS: int-prop
290
Passing integer arguments.
Definition int.hh:634
SharedHandle::Object * object(void) const
Access to the shared object.
static const unsigned int bpb
Bits per base.
Data stored for a Table.
Definition int.hh:2244
int max
Largest value.
Definition int.hh:2260
int n_free
Number of free tuple entries of arity.
Definition int.hh:2256
void resize(void)
Resize tuple data.
BitSetData * support
Pointer to all support data.
Definition int.hh:2270
Data(int a)
Initialize as empty tuple set with arity a.
Definition tuple-set.hpp:61
unsigned int n_words
Number of words for support.
Definition int.hh:2252
int min
Smallest value.
Definition int.hh:2258
static void set(BitSetData *d, unsigned int n)
Set bit n in bitset data d.
int n_tuples
Number of Tuples.
Definition int.hh:2254
Tuple get(int i) const
Return tuple with number i.
Definition tuple-set.hpp:87
int * td
Tuple data.
Definition int.hh:2264
unsigned int tuple2idx(Tuple t) const
Map tuple address to index.
Range * range
Pointer to all ranges.
Definition int.hh:2268
const Range * lst(int i) const
Return last range for position i.
bool finalized(void) const
Is datastructure finalized.
Definition tuple-set.hpp:71
ValueData * vd
Value data.
Definition int.hh:2266
const Range * fst(int i) const
Return first range for position i.
static const int n_initial_free
Initial number of free tuples.
Definition int.hh:2247
std::size_t key
Hash key.
Definition int.hh:2262
Tuple add(void)
Return newly added tuple.
Definition tuple-set.hpp:76
Range information.
Definition int.hh:2216
BitSetData * s
Begin of supports.
Definition int.hh:2223
unsigned int width(void) const
Return the width.
Definition tuple-set.hpp:45
int max
Maximum value.
Definition int.hh:2221
int min
Minimum value.
Definition int.hh:2219
const BitSetData * supports(unsigned int n_words, int n) const
Return the supports for value n.
Definition tuple-set.hpp:50
bool operator()(void) const
Test whether iterator is still at a range.
Ranges(const TupleSet &ts, int i)
Initialize for column i.
int max(void) const
Return largest value of range.
const Range * l
Last range.
Definition int.hh:2379
int min(void) const
Return smallest value of range.
void operator++(void)
Move iterator to next range (if possible)
const Range * c
Current range.
Definition int.hh:2377
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
Data about values in the table.
Definition int.hh:2231
unsigned int start(int n) const
Find start range for value n.
Definition tuple-set.hpp:93
unsigned int n
Number of ranges.
Definition int.hh:2234
Class represeting a set of tuples.
Definition int.hh:2206
TupleSet(void)
Construct an unitialized tuple set.
void _add(const IntArgs &t)
Add tuple t to tuple set.
int tuples(void) const
Number of tuples.
int max(void) const
Return maximal value in all tuples.
bool operator!=(const TupleSet &t) const
Test whether tuple set is different from t.
bool finalized(void) const
Is tuple set finalized.
TupleSet & add(const IntArgs &t)
Add tuple t to tuple set.
bool operator==(const TupleSet &t) const
Test whether tuple set is equal to t.
std::basic_ostream< Char, Traits > & operator<<(std::basic_ostream< Char, Traits > &os, const TupleSet &ts)
Tuple operator[](int i) const
Get tuple i.
const Range * lst(int i) const
Return last range for position i.
int * Tuple
Type of a tuple.
Definition int.hh:2212
std::size_t hash(void) const
Return hash key.
void finalize(void)
Finalize tuple set.
bool equal(const TupleSet &t) const
Test whether tuple set is equal to t.
const Range * fst(int i) const
Return first range for position i.
unsigned int words(void) const
Return number of required bit set words.
int min(void) const
Return minimal value in all tuples.
Data & raw(void) const
Get raw data (must be initialized)
Gecode::Support::BitSetData BitSetData
Import bit set data type.
Definition int.hh:2214
Data & data(void) const
Get data (must be initialized and finalized)
int arity(void) const
Arity of tuple set.
Heap heap
The single global heap.
Definition heap.cpp:44
Numerical limits for integer variables.
Definition int.hh:114
Finite domain integers.
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:773
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
#define forceinline
Definition config.hpp:194
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56