41 namespace Gecode {
namespace Int {
namespace Extensional {
76 for (
int i=0;
i<arity;
i++)
104 using namespace Int::Extensional;
105 assert(!finalized());
111 delete td; td=
nullptr;
120 for (
int t=0;
t<n_tuples;
t++)
121 tuple[
t] = td +
t*arity;
122 TupleCompare tc(arity);
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])
132 tuple[j++] = tuple[
t];
135 assert(j <= n_tuples);
138 key =
static_cast<std::size_t
>(n_tuples);
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];
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++;
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]) {
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++) {
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];
216 assert(vd[a].r[j].
max == tuple[
i][a]);
223 for (
unsigned int i=0U;
i<vd[
a].
n;
i++) {
225 cs += n_words * vd[
a].r[
i].width();
229 for (
int i=0;
i<n_tuples;
i++) {
230 while (tuple[
i][a] > vd[a].r[j].
max)
233 (vd[
a].r[j].supports(n_words,tuple[
i][a])),
234 tuple2idx(tuple[
i]));
238 assert(cs == support + n_words * n_vals);
239 assert(cr ==
range + n_ranges);
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;
276 (void) SharedHandle::operator =(ts);
283 unsigned int i_state;
284 unsigned int o_state;
290 unsigned int n_tuples;
296 unsigned int n_edges;
303 unsigned int n_supports;
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 = 0U; states[
i].o_deg = 0U;
317 states[
i].n_tuples = 0U;
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 = 0U;
326 layers[0].states[0].i_deg = 1U;
327 layers[0].states[0].n_tuples = 1U;
328 layers[0].states[0].tuples = r.
alloc<
int>(1U);
329 assert(layers[0].states[0].
tuples !=
nullptr);
336 for (
int i=0;
i<
a;
i++) {
337 unsigned int n_supports=0;
339 unsigned int n_edges=0;
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;
364 if (n_supports > 0U) {
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 (
unsigned int j = layers[
i].n_supports; j--; ) {
383 Support& s = layers[
i].supports[j];
384 for (
unsigned int k = s.n_edges; k--; ) {
385 unsigned int i_state = s.edges[k].i_state;
386 unsigned int o_state = s.edges[k].o_state;
388 if (layers[
i+1].states[o_state].o_deg == 0U) {
390 --layers[
i+1].states[o_state].i_deg;
391 --layers[
i].states[i_state].o_deg;
393 assert(s.n_edges > 0U);
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 (
unsigned int j = layers[
i].n_supports; j--; ) {
410 Support& s = layers[
i].supports[j];
411 for (
unsigned int k = s.n_edges; k--; ) {
412 unsigned int i_state = s.edges[k].i_state;
413 unsigned int o_state = s.edges[k].o_state;
415 if (layers[
i+1].states[o_state].
tuples ==
nullptr) {
416 unsigned 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 unsigned int n = layers[
i+1].states[o_state].n_tuples;
422 for (
unsigned 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 (
unsigned int i=0;
i<layers[
a].states[s].n_tuples;
i++) {
438 int* tuple = &layers[
a].states[s].tuples[
i*
a];
453 for (
int j=0; j<
arity(); j++)
454 if ((*
this)[
i][j] != t[
i][j])
PosCompare(int p)
Initialize with position p.
static T * copy(T *d, const T *s, long unsigned int n)
Copy n objects starting at s to d.
int final_fst(void) const
Return the number of the first final state.
void finalize(void)
Finalize tuple set.
Exception: Value out of limits
int size(void) const
Return size of array (number of elements)
Iterator for DFA symbols.
void resize(void)
Resize tuple data.
const FloatNum max
Largest allowed float value.
void rfree(void *p)
Free memory block starting at p.
int arity(void) const
Arity of tuple set.
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
TupleCompare(int a)
Initialize with arity a.
int * Tuple
Type of a tuple.
int max(void) const
Return maximal value in all tuples.
bool finalized(void) const
Is tuple set finalized.
bool operator()(const Tuple &a, const Tuple &b)
Comparison of tuples a and b.
void _add(const IntArgs &t)
Add tuple t to tuple set.
const int max
Largest allowed integer value.
void init(int a)
Initialize an uninitialized tuple set.
const int min
Smallest allowed integer value.
int tuples(void) const
Number of tuples.
Tuple add(void)
Return newly added tuple.
Exception: Tuple set already finalized
Deterministic finite automaton (DFA)
int p
Number of positive literals for node type.
T * alloc(long unsigned int n)
Allocate block of n objects of type T from heap.
const FloatNum min
Smallest allowed float value.
::Gecode::TupleSet::Tuple Tuple
Import tuple type.
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
int n
Number of negative literals for node type.
Gecode::IntArgs i({1, 2, 3, 4})
bool operator()(const Tuple &a, const Tuple &b)
Comparison of tuples a and b.
SharedHandle::Object * object(void) const
Access to the shared object.
struct Gecode::@593::NNF::@62::@63 b
For binary nodes (and, or, eqv)
void range(Home home, const IntVarArgs &x, SetVar y, SetVar z)
Post constraint .
static unsigned int data(unsigned int s)
Get number of data elements for s bits.
BitSetData * s
Begin of supports.
Passing integer arguments.
bool same(VarArgArray< Var > x, VarArgArray< Var > y)
Data & raw(void) const
Get raw data (must be initialized)
Post propagator for SetVar SetOpType SetVar SetRelType r
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Class represeting a set of tuples.
TupleSet(void)
Construct an unitialized tuple set.
int min(void) const
Return minimal value in all tuples.
unsigned int max_degree(void) const
Return maximal degree (in-degree and out-degree) of any state.
Heap heap
The single global heap.
Iterator for DFA transitions (sorted by symbols)
Tuple comparison by position.
virtual ~Data(void)
Delete implementation.
int n_states(void) const
Return the number of states.
TupleSet & add(const IntArgs &t)
Add tuple t to tuple set.
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.
Gecode toplevel namespace
int final_lst(void) const
Return the number of the last final state.
Exception: uninitialized tuple set
TupleSet & operator=(const TupleSet &t)
Assignment operator.
Exception: Arguments are of different size
unsigned int n_symbols(void) const
Return the number of symbols.
void cmb_hash(std::size_t &seed, const T h)
Combine hash value h into seed.
void finalize(void)
Finalize datastructure (disallows additions of more Tuples)
bool equal(const TupleSet &t) const
Test whether tuple set is equal to t.
struct Gecode::@593::NNF::@62::@64 a
For atomic nodes.