Go to the documentation of this file.
41 namespace Gecode {
namespace Int {
namespace Extensional {
76 for (
int i=0;
i<arity;
i++)
104 using namespace Int::Extensional;
111 delete td;
td=
nullptr;
122 TupleCompare tc(
arity);
128 if (tuple[
t-1][
a] != tuple[
t][
a])
132 tuple[j++] = tuple[
t];
162 unsigned int n_vals = 0U;
164 unsigned int n_ranges = 0U;
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++)
210 assert(tuple[
i-1][
a] <= tuple[
i][
a]);
213 }
else if (
vd[
a].
r[j].
max+1 < tuple[
i][
a]) {
223 for (
unsigned int i=0U;
i<
vd[
a].
n;
i++) {
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);
333 Support* supports =
r.alloc<Support>(dfa.
n_symbols());
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) {
366 Heap::copy(
r.alloc<Support>(n_supports),supports,n_supports);
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++) {
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];
448 assert(
tuples() ==
t.tuples());
449 assert(
arity() ==
t.arity());
450 assert(
min() ==
t.min());
451 assert(
max() ==
t.max());
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++)
Data & raw(void) const
Get raw data (must be initialized)
static unsigned int data(unsigned int s)
Get number of data elements for s bits.
static T * copy(T *d, const T *s, long unsigned int n)
Copy n objects starting at s to d.
Exception: Arguments are of different size
TupleSet & add(const IntArgs &t)
Add tuple t to tuple set.
BitSetData * s
Begin of supports.
bool operator()(const Tuple &a, const Tuple &b)
Comparison of tuples a and b.
int min(void) const
Return minimal value in all tuples.
SharedHandle::Object * object(void) const
Access to the shared object.
int max(void) const
Return maximal value in all tuples.
const FloatNum min
Smallest allowed float value.
TupleSet & operator=(const TupleSet &t)
Assignment operator.
int final_fst(void) const
Return the number of the first final state.
T * alloc(long unsigned int n)
Allocate block of n objects of type T from heap.
Exception: Tuple set already finalized
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Gecode toplevel namespace
TupleSet(void)
Construct an unitialized tuple set.
unsigned int n_symbols(void) const
Return the number of symbols.
void finalize(void)
Finalize tuple set.
unsigned int n_words
Number of words for support.
Exception: uninitialized tuple set
Tuple add(void)
Return newly added tuple.
Tuple comparison by position.
static void set(BitSetData *d, unsigned int n)
Set bit n in bitset data d.
Range * range
Pointer to all ranges.
Post propagator for SetVar SetOpType SetVar SetRelType r
int * Tuple
Type of a tuple.
PosCompare(int p)
Initialize with position p.
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
const int max
Largest allowed integer value.
Iterator for DFA transitions (sorted by symbols)
void _add(const IntArgs &t)
Add tuple t to tuple set.
::Gecode::TupleSet::Tuple Tuple
Import tuple type.
bool finalized(void) const
Is tuple set finalized.
unsigned int max_degree(void) const
Return maximal degree (in-degree and out-degree) of any state.
Class represeting a set of tuples.
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
void finalize(void)
Finalize datastructure (disallows additions of more Tuples)
Heap heap
The single global heap.
void cmb_hash(std::size_t &seed, const T h)
Combine hash value h into seed.
unsigned int tuple2idx(Tuple t) const
Map tuple address to index.
int n_states(void) const
Return the number of states.
Deterministic finite automaton (DFA)
TupleCompare(int a)
Initialize with arity a.
virtual ~Data(void)
Delete implementation.
bool equal(const TupleSet &t) const
Test whether tuple set is equal to t.
int final_lst(void) const
Return the number of the last final state.
ValueData * vd
Value data.
void init(int a)
Initialize an uninitialized tuple set.
int tuples(void) const
Number of tuples.
void resize(void)
Resize tuple data.
const int min
Smallest allowed integer value.
int arity(void) const
Arity of tuple set.
unsigned int width(void) const
Return the width.
bool operator()(const Tuple &a, const Tuple &b)
Comparison of tuples a and b.
bool same(VarArgArray< Var > x, VarArgArray< Var > y)
Exception: Value out of limits
int n_tuples
Number of Tuples.
bool finalized(void) const
Is datastructure finalized.
int n
Number of negative literals for node type.
void rfree(void *p)
Free memory block starting at p.
Passing integer arguments.
Gecode::IntArgs i({1, 2, 3, 4})
unsigned int n
Number of ranges.
int n_free
Number of free tuple entries of arity.
int p
Number of positive literals for node type.
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.
BitSetData * support
Pointer to all support data.
const FloatNum max
Largest allowed float value.
Iterator for DFA symbols.