41namespace 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++)
203 min = std::min(
min,tuple[0][
a]);
210 assert(tuple[i-1][
a] <= tuple[i][
a]);
211 if (
vd[
a].
r[j].
max+1 == tuple[i][
a]) {
213 }
else if (
vd[
a].
r[j].
max+1 < 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);
251 n_free =
n - n_tuples;
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++) {
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];
448 assert(
tuples() ==
t.tuples());
449 assert(
arity() ==
t.arity());
450 assert(
min() ==
t.min());
451 assert(
max() ==
t.max());
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++)
struct Gecode::@603::NNF::@65::@66 b
For binary nodes (and, or, eqv)
int p
Number of positive literals for node type.
int n
Number of negative literals for node type.
struct Gecode::@603::NNF::@65::@67 a
For atomic nodes.
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.
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.
static T * copy(T *d, const T *s, long unsigned int n)
Copy n objects starting at s to d.
T * alloc(long unsigned int n)
Allocate block of n objects of type T from heap.
void rfree(void *p)
Free memory block starting at p.
Passing integer arguments.
Exception: Tuple set already finalized
Exception: Arguments are of different size
Tuple comparison by position.
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::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.
BitSetData * s
Begin of supports.
unsigned int width(void) const
Return the width.
unsigned int n
Number of ranges.
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.
void finalize(void)
Finalize tuple set.
bool equal(const TupleSet &t) const
Test whether tuple set is equal to t.
int * Tuple
Type of a tuple.
int min(void) const
Return minimal value in all tuples.
Data & raw(void) const
Get raw data (must be initialized)
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.
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
void range(Home home, const IntVarArgs &x, SetVar y, SetVar z)
Post constraint .
void cmb_hash(std::size_t &seed, const T h)
Combine hash value h into seed.
bool same(VarArgArray< Var > x, VarArgArray< Var > y)