Generated on Thu Apr 5 2018 19:44:19 for Gecode by doxygen 1.8.13
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  * Last modified:
14  * $Date$ by $Author$
15  * $Revision$
16  *
17  * This file is part of Gecode, the generic constraint
18  * development environment:
19  * http://www.gecode.org
20  *
21  * Permission is hereby granted, free of charge, to any person obtaining
22  * a copy of this software and associated documentation files (the
23  * "Software"), to deal in the Software without restriction, including
24  * without limitation the rights to use, copy, modify, merge, publish,
25  * distribute, sublicense, and/or sell copies of the Software, and to
26  * permit persons to whom the Software is furnished to do so, subject to
27  * the following conditions:
28  *
29  * The above copyright notice and this permission notice shall be
30  * included in all copies or substantial portions of the Software.
31  *
32  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
33  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
34  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
35  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
36  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
37  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
38  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
39  *
40  */
41 
42 #include <gecode/int.hh>
43 #include <algorithm>
44 
45 namespace Gecode { namespace Int { namespace Extensional {
46 
49 
51  class TupleCompare {
52  private:
54  int arity;
55  public:
57  TupleCompare(int a);
59  bool operator ()(const Tuple& a, const Tuple& b);
60  };
61 
63  class PosCompare {
64  private:
66  int p;
67  public:
69  PosCompare(int p);
71  bool operator ()(const Tuple& a, const Tuple& b);
72  };
73 
74 
76  TupleCompare::TupleCompare(int a) : arity(a) {}
77 
78  forceinline bool
79  TupleCompare::operator ()(const Tuple& a, const Tuple& b) {
80  for (int i = 0; i < arity; i++)
81  if (a[i] < b[i])
82  return true;
83  else if (a[i] > b[i])
84  return false;
85  return false;
86  }
87 
88 
90  PosCompare::PosCompare(int p0) : p(p0) {}
91 
92  forceinline bool
93  PosCompare::operator ()(const Tuple& a, const Tuple& b) {
94  return a[p] < b[p];
95  }
96 
97 
98 }}}
99 
100 namespace Gecode {
101 
102  /*
103  * Tuple set data
104  *
105  */
106  void
108  using namespace Int::Extensional;
109  assert(!finalized());
110  // Mark as finalized
111  n_free = -1;
112 
113  // Initialization
114  if (n_tuples == 0) {
115  delete td; td=nullptr;
116  return;
117  }
118 
119  // Compact and copy data
120  Region r;
121  // Set up tuple pointers
122  Tuple* tuple = r.alloc<Tuple>(n_tuples);
123  {
124  for (int t=n_tuples; t--; )
125  tuple[t] = td + t*arity;
126  TupleCompare tc(arity);
127  Support::quicksort(tuple, n_tuples, tc);
128  // Remove duplicates
129  int j=1;
130  for (int t=1; t<n_tuples; t++) {
131  for (int a=arity; a--; )
132  if (tuple[t-1][a] != tuple[t][a])
133  goto notsame;
134  goto same;
135  notsame: ;
136  tuple[j++] = tuple[t];
137  same: ;
138  }
139  assert(j <= n_tuples);
140  n_tuples=j;
141  // Initialize hash key
142  key = static_cast<std::size_t>(n_tuples);
143  cmb_hash(key, arity);
144  // Copy into now possibly smaller area
145  int* new_td = heap.alloc<int>(n_tuples*arity);
146  for (int t=n_tuples; t--; ) {
147  for (int a=arity; a--; ) {
148  new_td[t*arity+a] = tuple[t][a];
149  cmb_hash(key,tuple[t][a]);
150  }
151  tuple[t] = new_td + t*arity;
152  }
153  heap.rfree(td);
154  td = new_td;
155  }
156 
157  // Only now compute how many tuples are needed!
158  n_words = BitSetData::data(n_tuples);
159 
160  // Compute range information
161  {
162  /*
163  * Pass one: compute how many values and ranges are needed
164  */
165  // How many values
166  unsigned int n_vals = 0U;
167  // How many ranges
168  unsigned int n_ranges = 0U;
169  for (int a=arity; a--; ) {
170  // Sort tuple according to position
171  PosCompare pc(a);
172  Support::quicksort(tuple, n_tuples, pc);
173  // Scan values
174  {
175  int max=tuple[0][a];
176  n_vals++; n_ranges++;
177  for (int i=1; i<n_tuples; i++) {
178  assert(tuple[i-1][a] <= tuple[i][a]);
179  if (max+1 == tuple[i][a]) {
180  n_vals++;
181  max=tuple[i][a];
182  } else if (max+1 < tuple[i][a]) {
183  n_vals++; n_ranges++;
184  max=tuple[i][a];
185  } else {
186  assert(max == tuple[i][a]);
187  }
188  }
189  }
190  }
191  /*
192  * Pass 2: allocate memory and fill data structures
193  */
194  // Allocate memory for ranges
195  Range* cr = range = heap.alloc<Range>(n_ranges);
196  // Allocate and initialize memory for supports
197  BitSetData* cs = support = heap.alloc<BitSetData>(n_words * n_vals);
198  for (unsigned int i=n_vals * n_words; i--; )
199  cs[i].init();
200  for (int a=arity; a--; ) {
201  // Set range pointer
202  vd[a].r = cr;
203  // Sort tuple according to position
204  PosCompare pc(a);
205  Support::quicksort(tuple, n_tuples, pc);
206  // Update min and max
207  min = std::min(min,tuple[0][a]);
208  max = std::max(max,tuple[n_tuples-1][a]);
209  // Compress into non-overlapping ranges
210  {
211  unsigned int j=0U;
212  vd[a].r[0].max=vd[a].r[0].min=tuple[0][a];
213  for (int i=1; i<n_tuples; i++) {
214  assert(tuple[i-1][a] <= tuple[i][a]);
215  if (vd[a].r[j].max+1 == tuple[i][a]) {
216  vd[a].r[j].max=tuple[i][a];
217  } else if (vd[a].r[j].max+1 < tuple[i][a]) {
218  j++; vd[a].r[j].min=vd[a].r[j].max=tuple[i][a];
219  } else {
220  assert(vd[a].r[j].max == tuple[i][a]);
221  }
222  }
223  vd[a].n = j+1U;
224  cr += j+1U;
225  }
226  // Set support pointer and set bits
227  for (unsigned int i=0U; i<vd[a].n; i++) {
228  vd[a].r[i].s = cs;
229  cs += n_words * vd[a].r[i].width();
230  }
231  {
232  int j=0;
233  for (int i=0; i<n_tuples; i++) {
234  while (tuple[i][a] > vd[a].r[j].max)
235  j++;
236  set(const_cast<BitSetData*>
237  (vd[a].r[j].supports(n_words,tuple[i][a])),
238  tuple2idx(tuple[i]));
239  }
240  }
241  }
242  assert(cs == support + n_words * n_vals);
243  assert(cr == range + n_ranges);
244  }
245  if ((min < Int::Limits::min) || (max > Int::Limits::max))
246  throw Int::OutOfLimits("TupleSet::finalize()");
247  assert(finalized());
248  }
249 
250  void
252  assert(n_free == 0);
253  int n = static_cast<int>(1+n_tuples*1.5);
254  td = heap.realloc<int>(td, n_tuples * arity, n * arity);
255  n_free = n - n_tuples;
256  }
257 
259  heap.rfree(td);
260  heap.rfree(vd);
261  heap.rfree(range);
262  heap.rfree(support);
263  }
264 
265 
266  /*
267  * Tuple set
268  *
269  */
271  : SharedHandle(new Data(a)) {}
272  void
274  object(new Data(a));
275  }
277  : SharedHandle(ts) {}
278  TupleSet&
280  (void) SharedHandle::operator =(ts);
281  return *this;
282  }
283 
284  TupleSet::TupleSet(int a, const Gecode::DFA& dfa) {
286  struct Edge {
287  unsigned int i_state;
288  unsigned int o_state;
289  };
291  struct State {
292  unsigned int i_deg;
293  unsigned int o_deg;
294  unsigned int n_tuples;
295  int* tuples;
296  };
298  struct Support {
299  int val;
300  unsigned int n_edges;
301  Edge* edges;
302  };
304  struct Layer {
305  State* states;
306  Support* supports;
307  unsigned int n_supports;
308  };
309  // Initialize
310  object(new Data(a));
311 
312  Region r;
313  // Number of states
314  int max_states = dfa.n_states();
315  // Allocate memory for all layers and states
316  Layer* layers = r.alloc<Layer>(a+1);
317  State* states = r.alloc<State>(max_states*(a+1));
318 
319  for (int i=max_states*(a+1); i--; ) {
320  states[i].i_deg = 0U; states[i].o_deg = 0U;
321  states[i].n_tuples = 0U;
322  states[i].tuples = nullptr;
323  }
324  for (int i=a+1; i--; ) {
325  layers[i].states = states + i*max_states;
326  layers[i].n_supports = 0U;
327  }
328 
329  // Mark initial state as being reachable
330  layers[0].states[0].i_deg = 1U;
331  layers[0].states[0].n_tuples = 1U;
332  layers[0].states[0].tuples = r.alloc<int>(1U);
333  assert(layers[0].states[0].tuples != nullptr);
334 
335  // Allocate temporary memory for edges and supports
336  Edge* edges = r.alloc<Edge>(dfa.max_degree());
337  Support* supports = r.alloc<Support>(dfa.n_symbols());
338 
339  // Forward pass: accumulate
340  for (int i=0; i<a; i++) {
341  unsigned int n_supports=0;
342  for (DFA::Symbols s(dfa); s(); ++s) {
343  unsigned int n_edges=0;
344  for (DFA::Transitions t(dfa,s.val()); t(); ++t) {
345  if (layers[i].states[t.i_state()].i_deg != 0) {
346  // Create edge
347  edges[n_edges].i_state = t.i_state();
348  edges[n_edges].o_state = t.o_state();
349  n_edges++;
350  // Adjust degrees
351  layers[i].states[t.i_state()].o_deg++;
352  layers[i+1].states[t.o_state()].i_deg++;
353  // Adjust number of tuples
354  layers[i+1].states[t.o_state()].n_tuples
355  += layers[i].states[t.i_state()].n_tuples;
356  }
357  assert(n_edges <= dfa.max_degree());
358  }
359  // Found a support for the value
360  if (n_edges > 0U) {
361  Support& support = supports[n_supports++];
362  support.val = s.val();
363  support.n_edges = n_edges;
364  support.edges = Heap::copy(r.alloc<Edge>(n_edges),edges,n_edges);
365  }
366  }
367  // Create supports
368  if (n_supports > 0U) {
369  layers[i].supports =
370  Heap::copy(r.alloc<Support>(n_supports),supports,n_supports);
371  layers[i].n_supports = n_supports;
372  } else {
373  finalize();
374  return;
375  }
376  }
377 
378  // Mark final states as being reachable
379  for (int s = dfa.final_fst(); s < dfa.final_lst(); s++) {
380  if (layers[a].states[s].i_deg != 0U)
381  layers[a].states[s].o_deg = 1U;
382  }
383 
384  // Backward pass: validate
385  for (int i=a; i--; ) {
386  for (unsigned int j = layers[i].n_supports; j--; ) {
387  Support& s = layers[i].supports[j];
388  for (unsigned int k = s.n_edges; k--; ) {
389  unsigned int i_state = s.edges[k].i_state;
390  unsigned int o_state = s.edges[k].o_state;
391  // State is unreachable
392  if (layers[i+1].states[o_state].o_deg == 0U) {
393  // Adjust degree
394  --layers[i+1].states[o_state].i_deg;
395  --layers[i].states[i_state].o_deg;
396  // Remove edge
397  assert(s.n_edges > 0U);
398  s.edges[k] = s.edges[--s.n_edges];
399  }
400  }
401  // Lost support
402  if (s.n_edges == 0U)
403  layers[i].supports[j] = layers[i].supports[--layers[i].n_supports];
404  }
405  if (layers[i].n_supports == 0U) {
406  finalize();
407  return;
408  }
409  }
410 
411  // Generate tuples
412  for (int i=0; i<a; i++) {
413  for (unsigned int j = layers[i].n_supports; j--; ) {
414  Support& s = layers[i].supports[j];
415  for (unsigned int k = s.n_edges; k--; ) {
416  unsigned int i_state = s.edges[k].i_state;
417  unsigned int o_state = s.edges[k].o_state;
418  // Allocate memory for tuples if not done
419  if (layers[i+1].states[o_state].tuples == nullptr) {
420  unsigned int n_tuples = layers[i+1].states[o_state].n_tuples;
421  layers[i+1].states[o_state].tuples = r.alloc<int>((i+1)*n_tuples);
422  layers[i+1].states[o_state].n_tuples = 0;
423  }
424  unsigned int n = layers[i+1].states[o_state].n_tuples;
425  // Write tuples
426  for (unsigned int t=0; t < layers[i].states[i_state].n_tuples; t++) {
427  // Copy the first i number of digits from the previous layer
428  Heap::copy(&layers[i+1].states[o_state].tuples[n*(i+1)+t*(i+1)],
429  &layers[i].states[i_state].tuples[t*i], i);
430  // Write the last digit
431  layers[i+1].states[o_state].tuples[n*(i+1)+t*(i+1)+i] = s.val;
432  }
433  layers[i+1].states[o_state].n_tuples
434  += layers[i].states[i_state].n_tuples;
435  }
436  }
437  }
438 
439  // Add tuples to tuple set
440  for (int s = dfa.final_fst(); s < dfa.final_lst(); s++) {
441  for (unsigned int i=0; i<layers[a].states[s].n_tuples; i++) {
442  int* tuple = &layers[a].states[s].tuples[i*a];
443  add(IntArgs(a,tuple));
444  }
445  }
446 
447  finalize();
448  }
449 
450  bool
451  TupleSet::equal(const TupleSet& t) const {
452  assert(tuples() == t.tuples());
453  assert(arity() == t.arity());
454  assert(min() == t.min());
455  assert(max() == t.max());
456  for (int i=tuples(); i--; )
457  for (int j=arity(); j--; )
458  if ((*this)[i][j] != t[i][j])
459  return false;
460  return true;
461  }
462 
463  void
465  if (!*this)
466  throw Int::UninitializedTupleSet("TupleSet::add()");
467  if (raw().finalized())
468  throw Int::AlreadyFinalized("TupleSet::add()");
469  if (t.size() != raw().arity)
470  throw Int::ArgumentSizeMismatch("TupleSet::add()");
471  Tuple a = raw().add();
472  for (int i=t.size(); i--; )
473  a[i]=t[i];
474  }
475 
476  TupleSet&
477  TupleSet::add(int n, ...) {
478  if (!*this)
479  throw Int::UninitializedTupleSet("TupleSet::add()");
480  if (raw().finalized())
481  throw Int::AlreadyFinalized("TupleSet::add()");
482  Tuple t = raw().add();
483  va_list args;
484  va_start(args, n);
485  t[0]=n;
486  for (int i=1; i<raw().arity; i++)
487  t[i] = va_arg(args,int);
488  va_end(args);
489  return *this;
490  }
491 
492 }
493 
494 // STATISTICS: int-prop
495 
PosCompare(int p)
Initialize with position p.
Definition: tuple-set.cpp:90
static T * copy(T *d, const T *s, long unsigned int n)
Copy n objects starting at s to d.
Definition: heap.hpp:587
NodeType t
Type of node.
Definition: bool-expr.cpp:234
int arity
Arity.
Definition: int.hh:2188
int final_fst(void) const
Return the number of the first final state.
Definition: dfa.hpp:167
The shared handle.
void finalize(void)
Finalize tuple set.
Definition: tuple-set.hpp:159
void cmb_hash(std::size_t &seed, int h)
Combine hash value h into seed.
Definition: hash.hpp:56
Exception: Value out of limits
Definition: exception.hpp:48
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1657
Iterator for DFA symbols.
Definition: int.hh:2070
void resize(void)
Resize tuple data.
Definition: tuple-set.cpp:251
const FloatNum max
Largest allowed float value.
Definition: float.hh:848
void rfree(void *p)
Free memory block starting at p.
Definition: heap.hpp:375
int arity(void) const
Arity of tuple set.
Definition: tuple-set.hpp:185
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition: region.hpp:384
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:53
TupleCompare(int a)
Initialize with arity a.
Definition: tuple-set.cpp:76
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
Handle to region.
Definition: region.hpp:57
bool operator()(const Tuple &a, const Tuple &b)
Comparison of tuples a and b.
Definition: tuple-set.cpp:93
#define forceinline
Definition: config.hpp:182
void _add(const IntArgs &t)
Add tuple t to tuple set.
Definition: tuple-set.cpp:464
const int max
Largest allowed integer value.
Definition: int.hh:116
void init(int a)
Initialize an uninitialized tuple set.
Definition: tuple-set.cpp:273
const int min
Smallest allowed integer value.
Definition: int.hh:118
bool same(const CachedView< View > &x, const CachedView< View > &y)
Definition: cached.hpp:394
int tuples(void) const
Number of tuples.
Definition: tuple-set.hpp:189
Tuple add(void)
Return newly added tuple.
Definition: tuple-set.hpp:80
Exception: Tuple set already finalized
Definition: exception.hpp:147
Deterministic finite automaton (DFA)
Definition: int.hh:2027
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
T * alloc(long unsigned int n)
Allocate block of n objects of type T from heap.
Definition: heap.hpp:435
const FloatNum min
Smallest allowed float value.
Definition: float.hh:850
Gecode::IntArgs i(4, 1, 2, 3, 4)
::Gecode::TupleSet::Tuple Tuple
Import tuple type.
Definition: tuple-set.cpp:48
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition: sort.hpp:134
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
bool operator()(const Tuple &a, const Tuple &b)
Comparison of tuples a and b.
Definition: tuple-set.cpp:79
SharedHandle::Object * object(void) const
Access to the shared object.
void range(Home home, const IntVarArgs &x, SetVar y, SetVar z)
Post constraint .
Definition: minimodel.hh:2030
static unsigned int data(unsigned int s)
Get number of data elements for s bits.
BitSetData * s
Begin of supports.
Definition: int.hh:2161
Passing integer arguments.
Definition: int.hh:608
Data & raw(void) const
Get raw data (must be initialized)
Definition: tuple-set.hpp:176
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:769
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:71
Class represeting a set of tuples.
Definition: int.hh:2144
TupleSet(void)
Construct an unitialized tuple set.
Definition: tuple-set.hpp:151
struct Gecode::@585::NNF::@62::@63 b
For binary nodes (and, or, eqv)
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.
unsigned int max_degree(void) const
Return maximal degree (in-degree and out-degree) of any state.
Definition: dfa.hpp:161
Heap heap
The single global heap.
Definition: heap.cpp:48
Date item for bitsets.
Definition: bitset-base.hpp:69
Iterator for DFA transitions (sorted by symbols)
Definition: int.hh:2047
Tuple comparison by position.
Definition: tuple-set.cpp:63
virtual ~Data(void)
Delete implementation.
Definition: tuple-set.cpp:258
int n
Number of elements.
Definition: array.hpp:515
int n_states(void) const
Return the number of states.
Definition: dfa.hpp:143
TupleSet & add(const IntArgs &t)
Add tuple t to tuple set.
Definition: tuple-set.hpp:146
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:486
Gecode toplevel namespace
int final_lst(void) const
Return the number of the last final state.
Definition: dfa.hpp:173
Exception: uninitialized tuple set
Definition: exception.hpp:133
TupleSet & operator=(const TupleSet &t)
Assignment operator.
Definition: tuple-set.cpp:279
Exception: Arguments are of different size
Definition: exception.hpp:77
unsigned int n_symbols(void) const
Return the number of symbols.
Definition: dfa.hpp:149
Data stored for a Table.
Definition: int.hh:2182
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