this repo has no description
dekker.one
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
43 /// Import tuple type
44 typedef ::Gecode::TupleSet::Tuple Tuple;
45
46 /// Tuple comparison
47 class TupleCompare {
48 private:
49 /// The arity of the tuples to compare
50 int arity;
51 public:
52 /// Initialize with arity \a a
53 TupleCompare(int a);
54 /// Comparison of tuples \a a and \a b
55 bool operator ()(const Tuple& a, const Tuple& b);
56 };
57
58 /// Tuple comparison by position
59 class PosCompare {
60 private:
61 /// The position of the tuples to compare
62 int p;
63 public:
64 /// Initialize with position \a p
65 PosCompare(int p);
66 /// Comparison of tuples \a a and \a b
67 bool operator ()(const Tuple& a, const Tuple& b);
68 };
69
70
71 forceinline
72 TupleCompare::TupleCompare(int a) : arity(a) {}
73
74 forceinline bool
75 TupleCompare::operator ()(const Tuple& a, const Tuple& b) {
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
85 forceinline
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
103 TupleSet::Data::finalize(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 heap.rfree(td);
112 td=nullptr;
113 return;
114 }
115
116 // Compact and copy data
117 Region r;
118 // Set up tuple pointers
119 Tuple* tuple = r.alloc<Tuple>(n_tuples);
120 {
121 for (int t=0; t<n_tuples; t++)
122 tuple[t] = td + t*arity;
123 TupleCompare tc(arity);
124 Support::quicksort(tuple, n_tuples, tc);
125 // Remove duplicates
126 int j=1;
127 for (int t=1; t<n_tuples; t++) {
128 for (int a=0; a<arity; a++)
129 if (tuple[t-1][a] != tuple[t][a])
130 goto notsame;
131 goto same;
132 notsame: ;
133 tuple[j++] = tuple[t];
134 same: ;
135 }
136 assert(j <= n_tuples);
137 n_tuples=j;
138 // Initialize hash key
139 key = static_cast<std::size_t>(n_tuples);
140 cmb_hash(key, arity);
141 // Copy into now possibly smaller area
142 int* new_td = heap.alloc<int>(n_tuples*arity);
143 for (int t=0; t<n_tuples; t++) {
144 for (int a=0; a<arity; a++) {
145 new_td[t*arity+a] = tuple[t][a];
146 cmb_hash(key,tuple[t][a]);
147 }
148 tuple[t] = new_td + t*arity;
149 }
150 heap.rfree(td);
151 td = new_td;
152 }
153
154 // Only now compute how many tuples are needed!
155 n_words = BitSetData::data(static_cast<unsigned int>(n_tuples));
156
157 // Compute range information
158 {
159 /*
160 * Pass one: compute how many values and ranges are needed
161 */
162 // How many values
163 unsigned int n_vals = 0U;
164 // How many ranges
165 unsigned int n_ranges = 0U;
166 for (int a=0; a<arity; a++) {
167 // Sort tuple according to position
168 PosCompare pc(a);
169 Support::quicksort(tuple, n_tuples, pc);
170 // Scan values
171 {
172 int max=tuple[0][a];
173 n_vals++; n_ranges++;
174 for (int i=1; i<n_tuples; i++) {
175 assert(tuple[i-1][a] <= tuple[i][a]);
176 if (max+1 == tuple[i][a]) {
177 n_vals++;
178 max=tuple[i][a];
179 } else if (max+1 < tuple[i][a]) {
180 n_vals++; n_ranges++;
181 max=tuple[i][a];
182 } else {
183 assert(max == tuple[i][a]);
184 }
185 }
186 }
187 }
188 /*
189 * Pass 2: allocate memory and fill data structures
190 */
191 // Allocate memory for ranges
192 Range* cr = range = heap.alloc<Range>(n_ranges);
193 // Allocate and initialize memory for supports
194 BitSetData* cs = support = heap.alloc<BitSetData>(n_words * n_vals);
195 for (unsigned int i=0; i<n_vals * n_words; i++)
196 cs[i].init();
197 for (int a=0; a<arity; a++) {
198 // Set range pointer
199 vd[a].r = cr;
200 // Sort tuple according to position
201 PosCompare pc(a);
202 Support::quicksort(tuple, n_tuples, pc);
203 // Update min and max
204 min = std::min(min,tuple[0][a]);
205 max = std::max(max,tuple[n_tuples-1][a]);
206 // Compress into non-overlapping ranges
207 {
208 unsigned int j=0U;
209 vd[a].r[0].max=vd[a].r[0].min=tuple[0][a];
210 for (int i=1; i<n_tuples; i++) {
211 assert(tuple[i-1][a] <= tuple[i][a]);
212 if (vd[a].r[j].max+1 == tuple[i][a]) {
213 vd[a].r[j].max=tuple[i][a];
214 } else if (vd[a].r[j].max+1 < tuple[i][a]) {
215 j++; vd[a].r[j].min=vd[a].r[j].max=tuple[i][a];
216 } else {
217 assert(vd[a].r[j].max == tuple[i][a]);
218 }
219 }
220 vd[a].n = j+1U;
221 cr += j+1U;
222 }
223 // Set support pointer and set bits
224 for (unsigned int i=0U; i<vd[a].n; i++) {
225 vd[a].r[i].s = cs;
226 cs += n_words * vd[a].r[i].width();
227 }
228 {
229 int j=0;
230 for (int i=0; i<n_tuples; i++) {
231 while (tuple[i][a] > vd[a].r[j].max)
232 j++;
233 set(const_cast<BitSetData*>
234 (vd[a].r[j].supports(n_words,tuple[i][a])),
235 tuple2idx(tuple[i]));
236 }
237 }
238 }
239 assert(cs == support + n_words * n_vals);
240 assert(cr == range + n_ranges);
241 }
242 if ((min < Int::Limits::min) || (max > Int::Limits::max))
243 throw Int::OutOfLimits("TupleSet::finalize()");
244 assert(finalized());
245 }
246
247 void
248 TupleSet::Data::resize(void) {
249 assert(n_free == 0);
250 int n = static_cast<int>(1+n_tuples*1.5);
251 td = heap.realloc<int>(td, n_tuples * arity, n * arity);
252 n_free = n - n_tuples;
253 }
254
255 TupleSet::Data::~Data(void) {
256 heap.rfree(td);
257 heap.rfree(vd);
258 heap.rfree(range);
259 heap.rfree(support);
260 }
261
262
263 /*
264 * Tuple set
265 *
266 */
267 TupleSet::TupleSet(int a)
268 : SharedHandle(new Data(a)) {}
269 void
270 TupleSet::init(int a) {
271 object(new Data(a));
272 }
273 TupleSet::TupleSet(const TupleSet& ts)
274 : SharedHandle(ts) {}
275 TupleSet&
276 TupleSet::operator =(const TupleSet& ts) {
277 (void) SharedHandle::operator =(ts);
278 return *this;
279 }
280
281 TupleSet::TupleSet(int a, const Gecode::DFA& dfa) {
282 /// Edges in layered graph
283 struct Edge {
284 int i_state; ///< Number of in-state
285 int o_state; ///< Number of out-state
286 };
287 /// State in layered graph
288 struct State {
289 int i_deg; ///< In-degree (number of incoming arcs)
290 int o_deg; ///< Out-degree (number of outgoing arcs)
291 int n_tuples; ///< Number of tuples
292 int* tuples; ///< The tuples
293 };
294 /// Support for a value
295 struct Support {
296 int val; ///< Supported value
297 int n_edges; ///< Number of supporting edges
298 Edge* edges; ///< Supporting edges
299 };
300 /// Layer in layered graph
301 struct Layer {
302 State* states; ///< States
303 Support* supports; ///< Supported values
304 int n_supports; ///< Number of supported values
305 };
306 // Initialize
307 object(new Data(a));
308
309 Region r;
310 // Number of states
311 int max_states = dfa.n_states();
312 // Allocate memory for all layers and states
313 Layer* layers = r.alloc<Layer>(a+1);
314 State* states = r.alloc<State>(max_states*(a+1));
315
316 for (int i=0; i<max_states*(a+1); i++) {
317 states[i].i_deg = 0; states[i].o_deg = 0;
318 states[i].n_tuples = 0;
319 states[i].tuples = nullptr;
320 }
321 for (int i=0; i<a+1; i++) {
322 layers[i].states = states + i*max_states;
323 layers[i].n_supports = 0;
324 }
325
326 // Mark initial state as being reachable
327 layers[0].states[0].i_deg = 1;
328 layers[0].states[0].n_tuples = 1;
329 layers[0].states[0].tuples = r.alloc<int>(1);
330 assert(layers[0].states[0].tuples != nullptr);
331
332 // Allocate temporary memory for edges and supports
333 Edge* edges = r.alloc<Edge>(dfa.max_degree());
334 Support* supports = r.alloc<Support>(dfa.n_symbols());
335
336 // Forward pass: accumulate
337 for (int i=0; i<a; i++) {
338 int n_supports=0;
339 for (DFA::Symbols s(dfa); s(); ++s) {
340 int n_edges=0;
341 for (DFA::Transitions t(dfa,s.val()); t(); ++t) {
342 if (layers[i].states[t.i_state()].i_deg != 0) {
343 // Create edge
344 edges[n_edges].i_state = t.i_state();
345 edges[n_edges].o_state = t.o_state();
346 n_edges++;
347 // Adjust degrees
348 layers[i].states[t.i_state()].o_deg++;
349 layers[i+1].states[t.o_state()].i_deg++;
350 // Adjust number of tuples
351 layers[i+1].states[t.o_state()].n_tuples
352 += layers[i].states[t.i_state()].n_tuples;
353 }
354 assert(static_cast<unsigned int>(n_edges) <= dfa.max_degree());
355 }
356 // Found a support for the value
357 if (n_edges > 0) {
358 Support& support = supports[n_supports++];
359 support.val = s.val();
360 support.n_edges = n_edges;
361 support.edges = Heap::copy(r.alloc<Edge>(n_edges),edges,n_edges);
362 }
363 }
364 // Create supports
365 if (n_supports > 0) {
366 layers[i].supports =
367 Heap::copy(r.alloc<Support>(n_supports),supports,n_supports);
368 layers[i].n_supports = n_supports;
369 } else {
370 finalize();
371 return;
372 }
373 }
374
375 // Mark final states as being reachable
376 for (int s=dfa.final_fst(); s<dfa.final_lst(); s++) {
377 if (layers[a].states[s].i_deg != 0U)
378 layers[a].states[s].o_deg = 1U;
379 }
380
381 // Backward pass: validate
382 for (int i=a; i--; ) {
383 for (int j = layers[i].n_supports; j--; ) {
384 Support& s = layers[i].supports[j];
385 for (int k = s.n_edges; k--; ) {
386 int i_state = s.edges[k].i_state;
387 int o_state = s.edges[k].o_state;
388 // State is unreachable
389 if (layers[i+1].states[o_state].o_deg == 0) {
390 // Adjust degree
391 --layers[i+1].states[o_state].i_deg;
392 --layers[i].states[i_state].o_deg;
393 // Remove edge
394 assert(s.n_edges > 0);
395 s.edges[k] = s.edges[--s.n_edges];
396 }
397 }
398 // Lost support
399 if (s.n_edges == 0)
400 layers[i].supports[j] = layers[i].supports[--layers[i].n_supports];
401 }
402 if (layers[i].n_supports == 0U) {
403 finalize();
404 return;
405 }
406 }
407
408 // Generate tuples
409 for (int i=0; i<a; i++) {
410 for (int j = layers[i].n_supports; j--; ) {
411 Support& s = layers[i].supports[j];
412 for (int k = s.n_edges; k--; ) {
413 int i_state = s.edges[k].i_state;
414 int o_state = s.edges[k].o_state;
415 // Allocate memory for tuples if not done
416 if (layers[i+1].states[o_state].tuples == nullptr) {
417 int n_tuples = layers[i+1].states[o_state].n_tuples;
418 layers[i+1].states[o_state].tuples = r.alloc<int>((i+1)*n_tuples);
419 layers[i+1].states[o_state].n_tuples = 0;
420 }
421 int n = layers[i+1].states[o_state].n_tuples;
422 // Write tuples
423 for (int t=0; t < layers[i].states[i_state].n_tuples; t++) {
424 // Copy the first i number of digits from the previous layer
425 Heap::copy(&layers[i+1].states[o_state].tuples[n*(i+1)+t*(i+1)],
426 &layers[i].states[i_state].tuples[t*i], i);
427 // Write the last digit
428 layers[i+1].states[o_state].tuples[n*(i+1)+t*(i+1)+i] = s.val;
429 }
430 layers[i+1].states[o_state].n_tuples
431 += layers[i].states[i_state].n_tuples;
432 }
433 }
434 }
435
436 // Add tuples to tuple set
437 for (int s = dfa.final_fst(); s < dfa.final_lst(); s++) {
438 for (int i=0; i<layers[a].states[s].n_tuples; i++) {
439 int* tuple = &layers[a].states[s].tuples[i*a];
440 add(IntArgs(a,tuple));
441 }
442 }
443
444 finalize();
445 }
446
447 bool
448 TupleSet::equal(const TupleSet& t) const {
449 assert(tuples() == t.tuples());
450 assert(arity() == t.arity());
451 assert(min() == t.min());
452 assert(max() == t.max());
453 for (int i=0; i<tuples(); i++)
454 for (int j=0; j<arity(); j++)
455 if ((*this)[i][j] != t[i][j])
456 return false;
457 return true;
458 }
459
460 void
461 TupleSet::_add(const IntArgs& t) {
462 if (!*this)
463 throw Int::UninitializedTupleSet("TupleSet::add()");
464 if (raw().finalized())
465 throw Int::AlreadyFinalized("TupleSet::add()");
466 if (t.size() != raw().arity)
467 throw Int::ArgumentSizeMismatch("TupleSet::add()");
468 Tuple a = raw().add();
469 for (int i=0; i<t.size(); i++)
470 a[i]=t[i];
471 }
472
473}
474
475// STATISTICS: int-prop
476