Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
tuple-set.cpp
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 * Mikael Lagerkvist <lagerkvist@gecode.org>
6 * Christian Schulte <schulte@gecode.org>
7 *
8 * Copyright:
9 * Linnea Ingmar, 2017
10 * Mikael Lagerkvist, 2007
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#include <gecode/int.hh>
39#include <algorithm>
40
41namespace Gecode { namespace Int { namespace Extensional {
42
45
48 private:
50 int arity;
51 public:
53 TupleCompare(int a);
55 bool operator ()(const Tuple& a, const Tuple& b);
56 };
57
59 class PosCompare {
60 private:
62 int p;
63 public:
65 PosCompare(int p);
67 bool operator ()(const Tuple& a, const Tuple& b);
68 };
69
70
72 TupleCompare::TupleCompare(int a) : arity(a) {}
73
74 forceinline bool
76 for (int i=0; i<arity; i++)
77 if (a[i] < b[i])
78 return true;
79 else if (a[i] > b[i])
80 return false;
81 return false;
82 }
83
84
86 PosCompare::PosCompare(int p0) : p(p0) {}
87
88 forceinline bool
89 PosCompare::operator ()(const Tuple& a, const Tuple& b) {
90 return a[p] < b[p];
91 }
92
93
94}}}
95
96namespace Gecode {
97
98 /*
99 * Tuple set data
100 *
101 */
102 void
104 using namespace Int::Extensional;
105 assert(!finalized());
106 // Mark as finalized
107 n_free = -1;
108
109 // Initialization
110 if (n_tuples == 0) {
111 delete td; td=nullptr;
112 return;
113 }
114
115 // Compact and copy data
116 Region r;
117 // Set up tuple pointers
118 Tuple* tuple = r.alloc<Tuple>(n_tuples);
119 {
120 for (int t=0; t<n_tuples; t++)
121 tuple[t] = td + t*arity;
122 TupleCompare tc(arity);
123 Support::quicksort(tuple, n_tuples, tc);
124 // Remove duplicates
125 int j=1;
126 for (int t=1; t<n_tuples; t++) {
127 for (int a=0; a<arity; a++)
128 if (tuple[t-1][a] != tuple[t][a])
129 goto notsame;
130 goto same;
131 notsame: ;
132 tuple[j++] = tuple[t];
133 same: ;
134 }
135 assert(j <= n_tuples);
136 n_tuples=j;
137 // Initialize hash key
138 key = static_cast<std::size_t>(n_tuples);
140 // Copy into now possibly smaller area
141 int* new_td = heap.alloc<int>(n_tuples*arity);
142 for (int t=0; t<n_tuples; t++) {
143 for (int a=0; a<arity; a++) {
144 new_td[t*arity+a] = tuple[t][a];
145 cmb_hash(key,tuple[t][a]);
146 }
147 tuple[t] = new_td + t*arity;
148 }
149 heap.rfree(td);
150 td = new_td;
151 }
152
153 // Only now compute how many tuples are needed!
154 n_words = BitSetData::data(static_cast<unsigned int>(n_tuples));
155
156 // Compute range information
157 {
158 /*
159 * Pass one: compute how many values and ranges are needed
160 */
161 // How many values
162 unsigned int n_vals = 0U;
163 // How many ranges
164 unsigned int n_ranges = 0U;
165 for (int a=0; a<arity; a++) {
166 // Sort tuple according to position
167 PosCompare pc(a);
168 Support::quicksort(tuple, n_tuples, pc);
169 // Scan values
170 {
171 int max=tuple[0][a];
172 n_vals++; n_ranges++;
173 for (int i=1; i<n_tuples; i++) {
174 assert(tuple[i-1][a] <= tuple[i][a]);
175 if (max+1 == tuple[i][a]) {
176 n_vals++;
177 max=tuple[i][a];
178 } else if (max+1 < tuple[i][a]) {
179 n_vals++; n_ranges++;
180 max=tuple[i][a];
181 } else {
182 assert(max == tuple[i][a]);
183 }
184 }
185 }
186 }
187 /*
188 * Pass 2: allocate memory and fill data structures
189 */
190 // Allocate memory for ranges
191 Range* cr = range = heap.alloc<Range>(n_ranges);
192 // Allocate and initialize memory for supports
193 BitSetData* cs = support = heap.alloc<BitSetData>(n_words * n_vals);
194 for (unsigned int i=0; i<n_vals * n_words; i++)
195 cs[i].init();
196 for (int a=0; a<arity; a++) {
197 // Set range pointer
198 vd[a].r = cr;
199 // Sort tuple according to position
200 PosCompare pc(a);
201 Support::quicksort(tuple, n_tuples, pc);
202 // Update min and max
203 min = std::min(min,tuple[0][a]);
204 max = std::max(max,tuple[n_tuples-1][a]);
205 // Compress into non-overlapping ranges
206 {
207 unsigned int j=0U;
208 vd[a].r[0].max=vd[a].r[0].min=tuple[0][a];
209 for (int i=1; i<n_tuples; i++) {
210 assert(tuple[i-1][a] <= tuple[i][a]);
211 if (vd[a].r[j].max+1 == tuple[i][a]) {
212 vd[a].r[j].max=tuple[i][a];
213 } else if (vd[a].r[j].max+1 < tuple[i][a]) {
214 j++; vd[a].r[j].min=vd[a].r[j].max=tuple[i][a];
215 } else {
216 assert(vd[a].r[j].max == tuple[i][a]);
217 }
218 }
219 vd[a].n = j+1U;
220 cr += j+1U;
221 }
222 // Set support pointer and set bits
223 for (unsigned int i=0U; i<vd[a].n; i++) {
224 vd[a].r[i].s = cs;
225 cs += n_words * vd[a].r[i].width();
226 }
227 {
228 int j=0;
229 for (int i=0; i<n_tuples; i++) {
230 while (tuple[i][a] > vd[a].r[j].max)
231 j++;
232 set(const_cast<BitSetData*>
233 (vd[a].r[j].supports(n_words,tuple[i][a])),
234 tuple2idx(tuple[i]));
235 }
236 }
237 }
238 assert(cs == support + n_words * n_vals);
239 assert(cr == range + n_ranges);
240 }
242 throw Int::OutOfLimits("TupleSet::finalize()");
243 assert(finalized());
244 }
245
246 void
248 assert(n_free == 0);
249 int n = static_cast<int>(1+n_tuples*1.5);
250 td = heap.realloc<int>(td, n_tuples * arity, n * arity);
251 n_free = n - n_tuples;
252 }
253
255 heap.rfree(td);
256 heap.rfree(vd);
257 heap.rfree(range);
258 heap.rfree(support);
259 }
260
261
262 /*
263 * Tuple set
264 *
265 */
267 : SharedHandle(new Data(a)) {}
268 void
270 object(new Data(a));
271 }
273 : SharedHandle(ts) {}
274 TupleSet&
276 (void) SharedHandle::operator =(ts);
277 return *this;
278 }
279
280 TupleSet::TupleSet(int a, const Gecode::DFA& dfa) {
282 struct Edge {
283 int i_state;
284 int o_state;
285 };
287 struct State {
288 int i_deg;
289 int o_deg;
290 int n_tuples;
291 int* tuples;
292 };
294 struct Support {
295 int val;
296 int n_edges;
297 Edge* edges;
298 };
300 struct Layer {
301 State* states;
302 Support* supports;
303 int n_supports;
304 };
305 // Initialize
306 object(new Data(a));
307
308 Region r;
309 // Number of states
310 int max_states = dfa.n_states();
311 // Allocate memory for all layers and states
312 Layer* layers = r.alloc<Layer>(a+1);
313 State* states = r.alloc<State>(max_states*(a+1));
314
315 for (int i=0; i<max_states*(a+1); i++) {
316 states[i].i_deg = 0; states[i].o_deg = 0;
317 states[i].n_tuples = 0;
318 states[i].tuples = nullptr;
319 }
320 for (int i=0; i<a+1; i++) {
321 layers[i].states = states + i*max_states;
322 layers[i].n_supports = 0;
323 }
324
325 // Mark initial state as being reachable
326 layers[0].states[0].i_deg = 1;
327 layers[0].states[0].n_tuples = 1;
328 layers[0].states[0].tuples = r.alloc<int>(1);
329 assert(layers[0].states[0].tuples != nullptr);
330
331 // Allocate temporary memory for edges and supports
332 Edge* edges = r.alloc<Edge>(dfa.max_degree());
333 Support* supports = r.alloc<Support>(dfa.n_symbols());
334
335 // Forward pass: accumulate
336 for (int i=0; i<a; i++) {
337 int n_supports=0;
338 for (DFA::Symbols s(dfa); s(); ++s) {
339 int n_edges=0;
340 for (DFA::Transitions t(dfa,s.val()); t(); ++t) {
341 if (layers[i].states[t.i_state()].i_deg != 0) {
342 // Create edge
343 edges[n_edges].i_state = t.i_state();
344 edges[n_edges].o_state = t.o_state();
345 n_edges++;
346 // Adjust degrees
347 layers[i].states[t.i_state()].o_deg++;
348 layers[i+1].states[t.o_state()].i_deg++;
349 // Adjust number of tuples
350 layers[i+1].states[t.o_state()].n_tuples
351 += layers[i].states[t.i_state()].n_tuples;
352 }
353 assert(n_edges <= dfa.max_degree());
354 }
355 // Found a support for the value
356 if (n_edges > 0) {
357 Support& support = supports[n_supports++];
358 support.val = s.val();
359 support.n_edges = n_edges;
360 support.edges = Heap::copy(r.alloc<Edge>(n_edges),edges,n_edges);
361 }
362 }
363 // Create supports
364 if (n_supports > 0) {
365 layers[i].supports =
366 Heap::copy(r.alloc<Support>(n_supports),supports,n_supports);
367 layers[i].n_supports = n_supports;
368 } else {
369 finalize();
370 return;
371 }
372 }
373
374 // Mark final states as being reachable
375 for (int s=dfa.final_fst(); s<dfa.final_lst(); s++) {
376 if (layers[a].states[s].i_deg != 0U)
377 layers[a].states[s].o_deg = 1U;
378 }
379
380 // Backward pass: validate
381 for (int i=a; i--; ) {
382 for (int j = layers[i].n_supports; j--; ) {
383 Support& s = layers[i].supports[j];
384 for (int k = s.n_edges; k--; ) {
385 int i_state = s.edges[k].i_state;
386 int o_state = s.edges[k].o_state;
387 // State is unreachable
388 if (layers[i+1].states[o_state].o_deg == 0) {
389 // Adjust degree
390 --layers[i+1].states[o_state].i_deg;
391 --layers[i].states[i_state].o_deg;
392 // Remove edge
393 assert(s.n_edges > 0);
394 s.edges[k] = s.edges[--s.n_edges];
395 }
396 }
397 // Lost support
398 if (s.n_edges == 0)
399 layers[i].supports[j] = layers[i].supports[--layers[i].n_supports];
400 }
401 if (layers[i].n_supports == 0U) {
402 finalize();
403 return;
404 }
405 }
406
407 // Generate tuples
408 for (int i=0; i<a; i++) {
409 for (int j = layers[i].n_supports; j--; ) {
410 Support& s = layers[i].supports[j];
411 for (int k = s.n_edges; k--; ) {
412 int i_state = s.edges[k].i_state;
413 int o_state = s.edges[k].o_state;
414 // Allocate memory for tuples if not done
415 if (layers[i+1].states[o_state].tuples == nullptr) {
416 int n_tuples = layers[i+1].states[o_state].n_tuples;
417 layers[i+1].states[o_state].tuples = r.alloc<int>((i+1)*n_tuples);
418 layers[i+1].states[o_state].n_tuples = 0;
419 }
420 int n = layers[i+1].states[o_state].n_tuples;
421 // Write tuples
422 for (int t=0; t < layers[i].states[i_state].n_tuples; t++) {
423 // Copy the first i number of digits from the previous layer
424 Heap::copy(&layers[i+1].states[o_state].tuples[n*(i+1)+t*(i+1)],
425 &layers[i].states[i_state].tuples[t*i], i);
426 // Write the last digit
427 layers[i+1].states[o_state].tuples[n*(i+1)+t*(i+1)+i] = s.val;
428 }
429 layers[i+1].states[o_state].n_tuples
430 += layers[i].states[i_state].n_tuples;
431 }
432 }
433 }
434
435 // Add tuples to tuple set
436 for (int s = dfa.final_fst(); s < dfa.final_lst(); s++) {
437 for (int i=0; i<layers[a].states[s].n_tuples; i++) {
438 int* tuple = &layers[a].states[s].tuples[i*a];
439 add(IntArgs(a,tuple));
440 }
441 }
442
443 finalize();
444 }
445
446 bool
447 TupleSet::equal(const TupleSet& t) const {
448 assert(tuples() == t.tuples());
449 assert(arity() == t.arity());
450 assert(min() == t.min());
451 assert(max() == t.max());
452 for (int i=0; i<tuples(); i++)
453 for (int j=0; j<arity(); j++)
454 if ((*this)[i][j] != t[i][j])
455 return false;
456 return true;
457 }
458
459 void
461 if (!*this)
462 throw Int::UninitializedTupleSet("TupleSet::add()");
463 if (raw().finalized())
464 throw Int::AlreadyFinalized("TupleSet::add()");
465 if (t.size() != raw().arity)
466 throw Int::ArgumentSizeMismatch("TupleSet::add()");
467 Tuple a = raw().add();
468 for (int i=0; i<t.size(); i++)
469 a[i]=t[i];
470 }
471
472}
473
474// STATISTICS: int-prop
475
int size(void) const
Return size of array (number of elements)
Definition array.hpp:1613
Iterator for DFA symbols.
Definition int.hh:2107
Iterator for DFA transitions (sorted by symbols)
Definition int.hh:2084
Deterministic finite automaton (DFA)
Definition int.hh:2064
unsigned int max_degree(void) const
Return maximal degree (in-degree and out-degree) of any state.
Definition dfa.hpp:157
int n_states(void) const
Return the number of states.
Definition dfa.hpp:139
int final_lst(void) const
Return the number of the last final state.
Definition dfa.hpp:169
unsigned int n_symbols(void) const
Return the number of symbols.
Definition dfa.hpp:145
int final_fst(void) const
Return the number of the first final state.
Definition dfa.hpp:163
static T * copy(T *d, const T *s, long unsigned int n)
Copy n objects starting at s to d.
Definition heap.hpp:583
Passing integer arguments.
Definition int.hh:634
Exception: Tuple set already finalized
Exception: Arguments are of different size
Definition exception.hpp:73
PosCompare(int p)
Initialize with position p.
Definition tuple-set.cpp:86
bool operator()(const Tuple &a, const Tuple &b)
Comparison of tuples a and b.
Definition tuple-set.cpp:89
TupleCompare(int a)
Initialize with arity a.
Definition tuple-set.cpp:72
bool operator()(const Tuple &a, const Tuple &b)
Comparison of tuples a and b.
Definition tuple-set.cpp:75
Exception: Value out of limits
Definition exception.hpp:44
Exception: uninitialized tuple set
Handle to region.
Definition region.hpp:55
SharedHandle(void)
Create shared handle with no object pointing to.
SharedHandle::Object * object(void) const
Access to the shared object.
static unsigned int data(unsigned int s)
Get number of data elements for s bits.
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
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.
virtual ~Data(void)
Delete implementation.
void finalize(void)
Finalize datastructure (disallows additions of more Tuples)
int n_tuples
Number of Tuples.
Definition int.hh:2254
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
bool finalized(void) const
Is datastructure finalized.
Definition tuple-set.hpp:71
ValueData * vd
Value data.
Definition int.hh:2266
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
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 finalized(void) const
Is tuple set finalized.
TupleSet & add(const IntArgs &t)
Add tuple t to tuple set.
TupleSet & operator=(const TupleSet &t)
Assignment operator.
int * Tuple
Type of a tuple.
Definition int.hh:2212
void finalize(void)
Finalize tuple set.
bool equal(const TupleSet &t) const
Test whether tuple set is equal to t.
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
void init(int a)
Initialize an uninitialized tuple set.
int arity(void) const
Arity of tuple set.
Heap heap
The single global heap.
Definition heap.cpp:44
Extensional propagators
TupleSet::Tuple Tuple
Tuple type.
const int min
Smallest allowed integer value.
Definition int.hh:118
const int max
Largest allowed integer value.
Definition int.hh:116
Finite domain integers.
Support algorithms and datastructures
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition sort.hpp:130
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:773
void cmb_hash(std::size_t &seed, const T h)
Combine hash value h into seed.
Definition hash.hpp:44
bool same(VarArgArray< Var > x, VarArgArray< Var > y)
Definition array.hpp:1943
#define forceinline
Definition config.hpp:194