40 namespace Gecode {
namespace Int {
namespace Extensional {
49 return x.i_state <
y.i_state;
54 Support::quicksort<DFA::Transition,TransByI_State>(
t,
n,tbis);
65 return x.symbol <
y.symbol;
70 Support::quicksort<DFA::Transition,TransBySymbol>(
t,
n,tbs);
81 return ((
x.symbol <
y.symbol) ||
82 ((
x.symbol ==
y.symbol) && (
x.i_state <
y.i_state)));
87 Support::quicksort<DFA::Transition,TransBySymbolI_State>(
t,
n,tbsi);
98 return x.o_state <
y.o_state;
103 Support::quicksort<DFA::Transition,TransByO_State>(
t,
n,tbos);
124 return ((
x.group <
y.group) ||
125 ((
x.group ==
y.group) && (
x.state <
y.state)));
130 Support::quicksort<StateGroup,StateGroupByGroup>(sg,
n,o);
157 using namespace Extensional;
166 for (
int*
f = &f_spec[0]; *
f >= 0;
f++)
172 for (
int i = n_trans;
i--; )
173 trans[
i] = t_spec[
i];
180 for (
int*
f = &f_spec[0]; *
f != -1;
f++) {
182 final[n_finals++] = *
f;
193 while (j < n_trans) {
196 while ((j < n_trans) && (s == trans[j].
symbol))
200 assert(j == n_trans);
209 part[
i].group = is_final[
i] ? 1 : 0;
210 s2g[
i] = part[
i].group;
219 if (part[0].group == part[
n_states].group) {
221 g2s[0].fst = &part[0]; g2s[0].lst = &part[
n_states+1];
225 assert(part[0].group == 0);
226 do i++;
while (part[
i].group == 0);
227 g2s[0].fst = &part[0]; g2s[0].lst = &part[
i];
228 g2s[1].fst = &part[
i]; g2s[1].lst = &part[
n_states+1];
240 for (
int g = n_groups; g--; ) {
242 if (g2s[g].lst-g2s[g].fst > 1) {
248 for (StateGroup* sg = g2s[g].fst; sg<g2s[g].lst; sg++) {
249 while ((
t < t_lst) && (
t->i_state < sg->state))
252 if ((
t < t_lst) && (
t->i_state == sg->state))
253 sg->group = s2g[
t->o_state];
259 static_cast<int>(g2s[g].lst-g2s[g].fst));
261 if (g2s[g].fst->group != (g2s[g].lst-1)->group) {
263 StateGroup* sg = g2s[g].fst+1;
264 while ((sg-1)->group == sg->group)
267 StateGroup* lst = g2s[g].lst;
270 s2g[sg->state] = n_groups;
271 g2s[n_groups].fst = sg++;
272 while ((sg < lst) && ((sg-1)->group == sg->group)) {
273 s2g[sg->state] = n_groups; sg++;
275 g2s[n_groups++].lst = sg;
281 }
while (n_groups != m_groups);
286 for (
int g = n_groups; g--; )
287 for (StateGroup* sg = g2s[g].fst; sg < g2s[g].lst; sg++)
288 if (is_final[sg->state]) {
289 final[n_finals++] = g;
296 for (
int g = n_groups; g--; )
297 s2r[g2s[g].fst->state] = g;
300 for (
int i = 0;
i<n_trans;
i++)
301 if (s2r[trans[
i].i_state] != -1) {
303 trans[j].symbol = trans[
i].symbol;
304 trans[j].o_state = s2g[trans[
i].o_state];
332 while ((j < n_trans) && (
i == trans[j].i_state))
336 assert(j == n_trans);
341 while (!visit.
empty()) {
346 visit.
push(
t->o_state);
360 while ((j < n_trans) && (
i == trans[j].o_state))
364 assert(j == n_trans);
367 for (
int i = n_finals;
i--; ) {
369 visit.
push(
final[
i]);
371 while (!visit.
empty()) {
376 visit.
push(
t->i_state);
392 re[start] = m_states++;
410 for (
int i = n_trans;
i--; )
411 if ((re[trans[
i].i_state] >= 0) && (re[trans[
i].
o_state] >= 0))
416 d->n_states = m_states;
417 d->n_trans = m_trans;
423 for (
int i = 0;
i<n_trans;
i++)
424 if ((re[trans[
i].i_state] >= 0) && (re[trans[
i].o_state] >= 0)) {
425 r[j].symbol = trans[
i].symbol;
426 r[j].i_state = re[trans[
i].i_state];
427 r[j].o_state = re[trans[
i].o_state];
435 for (
int i = 0;
i<m_trans; ) {
436 int s =
d->trans[
i++].symbol;
438 while ((
i<m_trans) && (
d->trans[
i].symbol == s))
446 unsigned int* deg =
heap.
alloc<
unsigned int>(m_states);
449 for (
int i = m_states;
i--; )
451 for (
int i = m_trans;
i--; )
452 deg[
d->trans[
i].o_state]++;
453 for (
int i = m_states;
i--; )
457 for (
int i = m_states;
i--; )
459 for (
int i = m_trans;
i--; )
460 deg[
d->trans[
i].i_state]++;
461 for (
int i = m_states;
i--; )
464 heap.
free<
unsigned int>(deg,m_states);
469 while (
i < m_trans) {
471 while ((
i < m_trans) &&
472 (
d->trans[j].symbol ==
d->trans[
i].symbol))
493 d->n_trans = n_trans;
506 while (
n_symbols >= static_cast<unsigned int>(1<<n_log))
511 for (
int i=(1<<n_log);
i--; )
512 table[
i].fst = table[
i].lst = NULL;
513 int mask = (1 << n_log) - 1;
515 for (
int i = 0;
i<n_trans; ) {
519 while ((
i<n_trans) && (trans[
i].symbol == s))
524 while (table[
p].fst != NULL)
void push(const T &x)
Push element x on top of stack.
static void sort(DFA::Transition t[], int n)
Sort transition array by symbol (value)
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.
static void sort(DFA::Transition t[], int n)
const FloatNum max
Largest allowed float value.
static void sort(DFA::Transition t[], int n)
static void sort(StateGroup sg[], int n)
StateInfo
Information about states.
Sort transition array by output state.
bool empty(void) const
Test whether stack is empty.
State is reachable from start state.
Stategroup is used to compute a partition of states.
Specification of transition range.
static void sort(DFA::Transition t[], int n)
void sort(TaskViewArray< TaskView > &t)
Sort task view array t according to sto and inc (increasing or decreasing)
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.
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
SharedHandle::Object * object(void) const
Access to the shared object.
bool operator()(const StateGroup &x, const StateGroup &y)
GroupStates is used to index StateGroup by group
Sort transition array by input state.
Specification of a DFA transition.
bool operator()(const DFA::Transition &x, const DFA::Transition &y)
int o_state
output state Default constructor
virtual SharedHandle::Object * copy(void) const
Create a copy.
Final state is reachable from state.
Post propagator for SetVar SetOpType SetVar SetRelType r
Post propagator for f(x \diamond_{\mathit{op}} y) \sim_r z \f$ void rel(Home home
Post propagator for SetVar SetOpType SetVar y
void free(T *b, long unsigned int n)
Delete n objects starting at b.
DFA(void)
Initialize for DFA accepting the empty word.
unsigned int max_degree(void) const
Return maximal degree (in-degree and out-degree) of any state.
bool operator()(const DFA::Transition &x, const DFA::Transition &y)
Heap heap
The single global heap.
Sort transition array by symbol and then input states.
Stack with fixed number of elements.
void fill(void)
Fill hash table.
T pop(void)
Pop topmost element from stack and return it.
Sort groups stated by group and then state.
bool operator()(const DFA::Transition &x, const DFA::Transition &y)
Post propagator for SetVar x
int n_states(void) const
Return the number of states.
bool operator()(const DFA::Transition &x, const DFA::Transition &y)
Gecode toplevel namespace
int final_lst(void) const
Return the number of the last final state.
unsigned int n_symbols(void) const
Return the number of symbols.