40 namespace Gecode {
namespace Int {
namespace Extensional {
54 Support::quicksort<DFA::Transition,TransByI_State>(
t,
n,tbis);
70 Support::quicksort<DFA::Transition,TransBySymbol>(
t,
n,tbs);
87 Support::quicksort<DFA::Transition,TransBySymbolI_State>(
t,
n,tbsi);
103 Support::quicksort<DFA::Transition,TransByO_State>(
t,
n,tbos);
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) {
194 idx[n_symbols++] = &trans[j];
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];
238 for (
int sidx = n_symbols; sidx--; ) {
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))
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) {
302 trans[j].i_state = s2g[trans[
i].i_state];
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)) {
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--; )
454 max_degree =
std::max(max_degree,deg[
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--; )
462 max_degree =
std::max(max_degree,deg[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))
474 max_degree =
std::max(max_degree,static_cast<unsigned int>(i-j));
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)