45 namespace Gecode {
namespace Int {
namespace Extensional {
80 for (
int i = 0;
i < arity;
i++)
108 using namespace Int::Extensional;
109 assert(!finalized());
115 delete td; td=
nullptr;
124 for (
int t=n_tuples;
t--; )
125 tuple[
t] = td +
t*arity;
126 TupleCompare tc(arity);
130 for (
int t=1;
t<n_tuples;
t++) {
131 for (
int a=arity;
a--; )
132 if (tuple[
t-1][
a] != tuple[
t][
a])
136 tuple[j++] = tuple[
t];
139 assert(j <= n_tuples);
142 key =
static_cast<std::size_t
>(n_tuples);
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];
151 tuple[
t] = new_td +
t*arity;
166 unsigned int n_vals = 0U;
168 unsigned int n_ranges = 0U;
169 for (
int a=arity;
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]) {
182 }
else if (max+1 < tuple[
i][a]) {
183 n_vals++; n_ranges++;
186 assert(max == tuple[
i][a]);
198 for (
unsigned int i=n_vals * n_words;
i--; )
200 for (
int a=arity;
a--; ) {
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];
220 assert(vd[a].r[j].
max == tuple[
i][a]);
227 for (
unsigned int i=0U;
i<vd[
a].
n;
i++) {
229 cs += n_words * vd[
a].r[
i].width();
233 for (
int i=0;
i<n_tuples;
i++) {
234 while (tuple[
i][a] > vd[a].r[j].
max)
237 (vd[
a].r[j].supports(n_words,tuple[
i][a])),
238 tuple2idx(tuple[
i]));
242 assert(cs == support + n_words * n_vals);
243 assert(cr ==
range + n_ranges);
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;
280 (void) SharedHandle::operator =(ts);
287 unsigned int i_state;
288 unsigned int o_state;
294 unsigned int n_tuples;
300 unsigned int n_edges;
307 unsigned int n_supports;
316 Layer* layers = r.
alloc<Layer>(a+1);
317 State* states = r.
alloc<State>(max_states*(a+1));
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;
324 for (
int i=a+1;
i--; ) {
325 layers[
i].states = states +
i*max_states;
326 layers[
i].n_supports = 0U;
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);
340 for (
int i=0;
i<
a;
i++) {
341 unsigned int n_supports=0;
343 unsigned int n_edges=0;
345 if (layers[
i].states[
t.i_state()].i_deg != 0) {
347 edges[n_edges].i_state =
t.i_state();
348 edges[n_edges].o_state =
t.o_state();
351 layers[
i].states[
t.i_state()].o_deg++;
352 layers[
i+1].states[
t.o_state()].i_deg++;
354 layers[
i+1].states[
t.o_state()].n_tuples
355 += layers[
i].states[
t.i_state()].n_tuples;
361 Support& support = supports[n_supports++];
362 support.val = s.val();
363 support.n_edges = n_edges;
368 if (n_supports > 0U) {
371 layers[
i].n_supports = n_supports;
380 if (layers[a].states[s].i_deg != 0U)
381 layers[
a].states[s].o_deg = 1U;
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;
392 if (layers[
i+1].states[o_state].o_deg == 0U) {
394 --layers[
i+1].states[o_state].i_deg;
395 --layers[
i].states[i_state].o_deg;
397 assert(s.n_edges > 0U);
398 s.edges[k] = s.edges[--s.n_edges];
403 layers[
i].supports[j] = layers[
i].supports[--layers[
i].n_supports];
405 if (layers[
i].n_supports == 0U) {
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;
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;
424 unsigned int n = layers[
i+1].states[o_state].n_tuples;
426 for (
unsigned int t=0;
t < layers[
i].states[i_state].n_tuples;
t++) {
429 &layers[
i].states[i_state].
tuples[
t*
i], i);
431 layers[i+1].states[o_state].tuples[n*(i+1)+
t*(i+1)+
i] = s.val;
433 layers[
i+1].states[o_state].n_tuples
434 += layers[
i].states[i_state].n_tuples;
441 for (
unsigned int i=0;
i<layers[
a].states[s].n_tuples;
i++) {
442 int* tuple = &layers[
a].states[s].tuples[
i*
a];
457 for (
int j=
arity(); j--; )
458 if ((*
this)[
i][j] != t[
i][j])
472 for (
int i=t.
size();
i--; )
487 t[
i] = va_arg(args,
int);
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.
void cmb_hash(std::size_t &seed, int h)
Combine hash value h into seed.
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.
bool same(const CachedView< View > &x, const CachedView< View > &y)
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::IntArgs i(4, 1, 2, 3, 4)
::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.
bool operator()(const Tuple &a, const Tuple &b)
Comparison of tuples a and b.
SharedHandle::Object * object(void) const
Access to the shared object.
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.
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.
struct Gecode::@585::NNF::@62::@63 b
For binary nodes (and, or, eqv)
int min(void) const
Return minimal value in all tuples.
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.
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 finalize(void)
Finalize datastructure (disallows additions of more Tuples)
bool equal(const TupleSet &t) const
Test whether tuple set is equal to t.