76 for (
int i=0; i<arity; i++)
111 delete td;
td=
nullptr;
122 TupleCompare tc(
arity);
127 for (
int a=0; a<
arity; a++)
128 if (tuple[t-1][a] != tuple[t][a])
132 tuple[j++] = tuple[t];
143 for (
int a=0; a<
arity; a++) {
144 new_td[t*
arity+a] = tuple[t][a];
147 tuple[t] = new_td + t*
arity;
162 unsigned int n_vals = 0U;
164 unsigned int n_ranges = 0U;
165 for (
int a=0; a<
arity; a++) {
172 n_vals++; n_ranges++;
174 assert(tuple[i-1][a] <= tuple[i][a]);
175 if (
max+1 == tuple[i][a]) {
178 }
else if (
max+1 < tuple[i][a]) {
179 n_vals++; n_ranges++;
182 assert(
max == tuple[i][a]);
194 for (
unsigned int i=0; i<n_vals *
n_words; i++)
196 for (
int a=0; a<
arity; a++) {
203 min = std::min(
min,tuple[0][a]);
208 vd[a].r[0].max=
vd[a].r[0].min=tuple[0][a];
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];
216 assert(
vd[a].
r[j].
max == tuple[i][a]);
223 for (
unsigned int i=0U; i<
vd[a].n; i++) {
230 while (tuple[i][a] >
vd[a].
r[j].
max)
239 assert(cr ==
range + n_ranges);
249 int n =
static_cast<int>(1+
n_tuples*1.5);
276 (void) SharedHandle::operator =(ts);
312 Layer* layers =
r.alloc<Layer>(a+1);
313 State* states =
r.alloc<State>(max_states*(a+1));
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;
320 for (
int i=0; i<a+1; i++) {
321 layers[i].states = states + i*max_states;
322 layers[i].n_supports = 0;
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);
336 for (
int i=0; i<a; i++) {
341 if (layers[i].states[t.i_state()].i_deg != 0) {
343 edges[n_edges].i_state = t.i_state();
344 edges[n_edges].o_state = t.o_state();
347 layers[i].states[t.i_state()].o_deg++;
348 layers[i+1].states[t.o_state()].i_deg++;
350 layers[i+1].states[t.o_state()].n_tuples
351 += layers[i].states[t.i_state()].n_tuples;
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);
364 if (n_supports > 0) {
367 layers[i].n_supports = n_supports;
376 if (layers[a].states[s].i_deg != 0U)
377 layers[a].states[s].o_deg = 1U;
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;
388 if (layers[i+1].states[o_state].o_deg == 0) {
390 --layers[i+1].states[o_state].i_deg;
391 --layers[i].states[i_state].o_deg;
393 assert(s.n_edges > 0);
394 s.edges[k] = s.edges[--s.n_edges];
399 layers[i].supports[j] = layers[i].supports[--layers[i].n_supports];
401 if (layers[i].n_supports == 0U) {
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;
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;
420 int n = layers[i+1].states[o_state].n_tuples;
422 for (
int t=0; t < layers[i].states[i_state].n_tuples; t++) {
425 &layers[i].states[i_state].
tuples[t*i], i);
427 layers[i+1].states[o_state].tuples[n*(i+1)+t*(i+1)+i] = s.val;
429 layers[i+1].states[o_state].n_tuples
430 += layers[i].states[i_state].n_tuples;
437 for (
int i=0; i<layers[a].states[s].n_tuples; i++) {
438 int* tuple = &layers[a].states[s].tuples[i*a];
452 for (
int i=0; i<
tuples(); i++)
453 for (
int j=0; j<
arity(); j++)
454 if ((*
this)[i][j] != t[i][j])
468 for (
int i=0; i<t.
size(); i++)
int size(void) const
Return size of array (number of elements)
Iterator for DFA symbols.
Iterator for DFA transitions (sorted by symbols)
Deterministic finite automaton (DFA)
unsigned int max_degree(void) const
Return maximal degree (in-degree and out-degree) of any state.
int n_states(void) const
Return the number of states.
int final_lst(void) const
Return the number of the last final state.
unsigned int n_symbols(void) const
Return the number of symbols.
int final_fst(void) const
Return the number of the first final state.
static T * copy(T *d, const T *s, long unsigned int n)
Copy n objects starting at s to d.
Passing integer arguments.
Exception: Tuple set already finalized
Exception: Arguments are of different size
PosCompare(int p)
Initialize with position p.
bool operator()(const Tuple &a, const Tuple &b)
Comparison of tuples a and b.
TupleCompare(int a)
Initialize with arity a.
bool operator()(const Tuple &a, const Tuple &b)
Comparison of tuples a and b.
Exception: Value out of limits
Exception: uninitialized tuple set
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.
int n_free
Number of free tuple entries of arity.
void resize(void)
Resize tuple data.
BitSetData * support
Pointer to all support data.
unsigned int n_words
Number of words for support.
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.
unsigned int tuple2idx(Tuple t) const
Map tuple address to index.
Range * range
Pointer to all ranges.
bool finalized(void) const
Is datastructure finalized.
ValueData * vd
Value data.
Tuple add(void)
Return newly added tuple.
Class represeting a set of tuples.
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.
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.
void init(int a)
Initialize an uninitialized tuple set.
int arity(void) const
Arity of tuple set.
Heap heap
The single global heap.
TupleSet::Tuple Tuple
Tuple type.
const int min
Smallest allowed integer value.
const int max
Largest allowed integer value.
Support algorithms and datastructures
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
void cmb_hash(std::size_t &seed, const T h)
Combine hash value h into seed.
bool same(VarArgArray< Var > x, VarArgArray< Var > y)