Generated on Wed Jul 21 2021 00:00:00 for Gecode by doxygen 1.9.1
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 
41 namespace Gecode { namespace Int { namespace Extensional {
42 
45 
47  class TupleCompare {
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
90  return a[p] < b[p];
91  }
92 
93 
94 }}}
95 
96 namespace 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);
139  cmb_hash(key, arity);
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  }
241  if ((min < Int::Limits::min) || (max > Int::Limits::max))
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 
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
NodeType t
Type of node.
Definition: bool-expr.cpp:230
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
NNF * r
Right subtree.
Definition: bool-expr.cpp:242
Iterator for DFA symbols.
Definition: int.hh:2092
Iterator for DFA transitions (sorted by symbols)
Definition: int.hh:2069
Deterministic finite automaton (DFA)
Definition: int.hh:2049
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
T * realloc(T *b, long unsigned int n, long unsigned int m)
Reallocate block of n objects starting at b to m objects of type T from heap.
Definition: heap.hpp:482
static T * copy(T *d, const T *s, long unsigned int n)
Copy n objects starting at s to d.
Definition: heap.hpp:583
T * alloc(long unsigned int n)
Allocate block of n objects of type T from heap.
Definition: heap.hpp:431
void rfree(void *p)
Free memory block starting at p.
Definition: heap.hpp:371
Passing integer arguments.
Definition: int.hh:628
Exception: Tuple set already finalized
Definition: exception.hpp:143
Exception: Arguments are of different size
Definition: exception.hpp:73
Tuple comparison by position.
Definition: tuple-set.cpp:59
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
Definition: exception.hpp:129
Handle to region.
Definition: region.hpp:55
The shared handle.
SharedHandle::Object * object(void) const
Access to the shared object.
Date item for bitsets.
Definition: bitset-base.hpp:65
static unsigned int data(unsigned int s)
Get number of data elements for s bits.
Data stored for a Table.
Definition: int.hh:2229
int max
Largest value.
Definition: int.hh:2245
int n_free
Number of free tuple entries of arity.
Definition: int.hh:2241
void resize(void)
Resize tuple data.
Definition: tuple-set.cpp:247
BitSetData * support
Pointer to all support data.
Definition: int.hh:2255
unsigned int n_words
Number of words for support.
Definition: int.hh:2237
int min
Smallest value.
Definition: int.hh:2243
static void set(BitSetData *d, unsigned int n)
Set bit n in bitset data d.
Definition: tuple-set.hpp:113
virtual ~Data(void)
Delete implementation.
Definition: tuple-set.cpp:254
int arity
Arity.
Definition: int.hh:2235
void finalize(void)
Finalize datastructure (disallows additions of more Tuples)
Definition: tuple-set.cpp:103
int n_tuples
Number of Tuples.
Definition: int.hh:2239
int * td
Tuple data.
Definition: int.hh:2249
unsigned int tuple2idx(Tuple t) const
Map tuple address to index.
Definition: tuple-set.hpp:123
Range * range
Pointer to all ranges.
Definition: int.hh:2253
bool finalized(void) const
Is datastructure finalized.
Definition: tuple-set.hpp:71
ValueData * vd
Value data.
Definition: int.hh:2251
std::size_t key
Hash key.
Definition: int.hh:2247
Tuple add(void)
Return newly added tuple.
Definition: tuple-set.hpp:76
Range information.
Definition: int.hh:2201
BitSetData * s
Begin of supports.
Definition: int.hh:2208
unsigned int width(void) const
Return the width.
Definition: tuple-set.hpp:45
int max
Maximum value.
Definition: int.hh:2206
int min
Minimum value.
Definition: int.hh:2204
unsigned int n
Number of ranges.
Definition: int.hh:2219
Range * r
Ranges.
Definition: int.hh:2221
Class represeting a set of tuples.
Definition: int.hh:2191
TupleSet(void)
Construct an unitialized tuple set.
Definition: tuple-set.hpp:147
void _add(const IntArgs &t)
Add tuple t to tuple set.
Definition: tuple-set.cpp:460
int tuples(void) const
Number of tuples.
Definition: tuple-set.hpp:185
int max(void) const
Return maximal value in all tuples.
Definition: tuple-set.hpp:197
bool finalized(void) const
Is tuple set finalized.
Definition: tuple-set.hpp:162
TupleSet & add(const IntArgs &t)
Add tuple t to tuple set.
Definition: tuple-set.hpp:142
TupleSet & operator=(const TupleSet &t)
Assignment operator.
Definition: tuple-set.cpp:275
int * Tuple
Type of a tuple.
Definition: int.hh:2197
void finalize(void)
Finalize tuple set.
Definition: tuple-set.hpp:155
bool equal(const TupleSet &t) const
Test whether tuple set is equal to t.
Definition: tuple-set.cpp:447
int min(void) const
Return minimal value in all tuples.
Definition: tuple-set.hpp:193
Data & raw(void) const
Get raw data (must be initialized)
Definition: tuple-set.hpp:172
void init(int a)
Initialize an uninitialized tuple set.
Definition: tuple-set.cpp:269
int arity(void) const
Arity of tuple set.
Definition: tuple-set.hpp:181
Heap heap
The single global heap.
Definition: heap.cpp:44
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:1937
const FloatNum max
Largest allowed float value.
Definition: float.hh:844
const FloatNum min
Smallest allowed float value.
Definition: float.hh:846
::Gecode::TupleSet::Tuple Tuple
Import tuple type.
Definition: tuple-set.cpp:44
const int min
Smallest allowed integer value.
Definition: int.hh:118
const int max
Largest allowed integer value.
Definition: int.hh:116
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition: sort.hpp:130
Gecode::IntArgs i({1, 2, 3, 4})
#define forceinline
Definition: config.hpp:192