168 int max_state = start;
170 max_state = std::max(max_state,t->i_state);
171 max_state = std::max(max_state,t->o_state);
174 std::size_t n_final_spec = 0;
175 for (
int* f = &f_spec[0]; *f >= 0; f++) {
176 max_state = std::max(max_state,*f);
181 const bool compact =
static_cast<std::size_t
>(max_state) >=
182 static_cast<std::size_t
>(n_trans)+n_final_spec+1;
183 std::vector<int> states;
186 states.reserve(2*
static_cast<std::size_t
>(n_trans)+n_final_spec+1);
187 states.push_back(start);
189 states.push_back(t->i_state);
190 states.push_back(t->o_state);
192 for (
int* f = &f_spec[0]; *f >= 0; f++)
193 states.push_back(*f);
194 std::sort(states.begin(),states.end());
195 states.erase(std::unique(states.begin(),states.end()),states.end());
196 n_states =
static_cast<int>(states.size());
197 start = state_index(states,start);
205 for (
int i=0; i<n_trans; i++) {
206 trans[i] = t_spec[i];
207 trans[i].
i_state = state_index(states,trans[i].i_state);
208 trans[i].
o_state = state_index(states,trans[i].o_state);
211 for (
int i=0; i<n_trans; i++)
212 trans[i] = t_spec[i];
220 for (
int* f = &f_spec[0]; *f != -1; f++) {
221 const int state = compact ? state_index(states,*f) : *f;
222 if (!is_final[state]) {
223 is_final[state] =
true;
224 final[n_finals++] = state;
230 TransBySymbolI_State::sort(trans, n_trans);
236 while (j < n_trans) {
239 while ((j < n_trans) && (s == trans[j].symbol))
243 assert(j == n_trans);
252 part[i].group = is_final[i] ? 1 : 0;
253 s2g[i] = part[i].group;
260 StateGroupByGroup::sort(part,
n_states+1);
262 if (part[0].group == part[
n_states].group) {
264 g2s[0].fst = &part[0]; g2s[0].lst = &part[
n_states+1];
268 assert(part[0].group == 0);
269 do i++;
while (part[i].group == 0);
270 g2s[0].fst = &part[0]; g2s[0].lst = &part[i];
271 g2s[1].fst = &part[i]; g2s[1].lst = &part[
n_states+1];
283 for (
int g = n_groups; g--; ) {
285 if (g2s[g].lst-g2s[g].fst > 1) {
291 for (StateGroup* sg = g2s[g].fst; sg<g2s[g].lst; sg++) {
292 while ((t < t_lst) && (t->
i_state < sg->state))
295 if ((t < t_lst) && (t->
i_state == sg->state))
301 StateGroupByGroup::sort(g2s[g].fst,
302 static_cast<int>(g2s[g].lst-g2s[g].fst));
304 if (g2s[g].fst->group != (g2s[g].lst-1)->group) {
306 StateGroup* sg = g2s[g].fst+1;
307 while ((sg-1)->group == sg->group)
310 StateGroup* lst = g2s[g].lst;
313 s2g[sg->state] = n_groups;
314 g2s[n_groups].fst = sg++;
315 while ((sg < lst) && ((sg-1)->group == sg->group)) {
316 s2g[sg->state] = n_groups; sg++;
318 g2s[n_groups++].lst = sg;
324 }
while (n_groups != m_groups);
329 for (
int g = n_groups; g--; )
330 for (StateGroup* sg = g2s[g].fst; sg < g2s[g].lst; sg++)
331 if (is_final[sg->state]) {
332 final[n_finals++] = g;
339 for (
int g=0; g<n_groups; g++)
340 s2r[g2s[g].fst->state] = g;
343 for (
int i = 0; i<n_trans; i++)
344 if (s2r[trans[i].i_state] != -1) {
346 trans[j].symbol = trans[i].symbol;
347 trans[j].o_state = s2g[trans[i].o_state];
365 TransByI_State::sort(trans, n_trans);
370 while ((j < n_trans) && (i == trans[j].i_state))
374 assert(j == n_trans);
377 state[start] = SI_FROM_START;
379 while (!visit.
empty()) {
381 for (
Transition* t = idx[s]; t < idx[s+1]; t++)
382 if (!(state[t->o_state] & SI_FROM_START)) {
383 state[t->o_state] |= SI_FROM_START;
384 visit.
push(t->o_state);
393 TransByO_State::sort(trans, n_trans);
398 while ((j < n_trans) && (i == trans[j].o_state))
402 assert(j == n_trans);
405 for (
int i=0; i<n_finals; i++) {
406 state[
final[i]] |= (SI_TO_FINAL | SI_FINAL);
407 visit.
push(
final[i]);
409 while (!visit.
empty()) {
411 for (
Transition* t = idx[s]; t < idx[s+1]; t++)
412 if (!(state[t->i_state] & SI_TO_FINAL)) {
413 state[t->i_state] |= SI_TO_FINAL;
414 visit.
push(t->i_state);
427 re[start] = m_states++;
431 if ((state[i] == (SI_FINAL | SI_FROM_START | SI_TO_FINAL)) && (re[i] < 0))
434 int final_fst = (state[start] & SI_FINAL) ? 0 : 1;
440 if ((state[i] == (SI_FROM_START | SI_TO_FINAL)) && (re[i] < 0))
445 for (
int i=n_trans; i--; )
446 if ((re[trans[i].i_state] >= 0) && (re[trans[i].o_state] >= 0))
451 d->n_states = m_states;
452 d->n_trans = m_trans;
458 for (
int i = 0; i<n_trans; i++)
459 if ((re[trans[i].i_state] >= 0) && (re[trans[i].o_state] >= 0)) {
460 r[j].symbol = trans[i].
symbol;
461 r[j].i_state = re[trans[i].
i_state];
462 r[j].o_state = re[trans[i].o_state];
465 TransBySymbol::sort(r,m_trans);
470 for (
int i = 0; i<m_trans; ) {
471 int s = d->trans[i++].symbol;
473 while ((i<m_trans) && (d->trans[i].symbol == s))
481 unsigned int* deg = region.
alloc<
unsigned int>(m_states);
484 for (
int i=0; i<m_states; i++)
486 for (
int i=0; i<m_trans; i++)
487 deg[d->trans[i].o_state]++;
488 for (
int i=0; i<m_states; i++)
492 for (
int i=0; i<m_states; i++)
494 for (
int i=0; i<m_trans; i++)
495 deg[d->trans[i].i_state]++;
496 for (
int i=0; i<m_states; i++)
502 while (i < m_trans) {
504 while ((i < m_trans) &&
505 (d->trans[j].symbol == d->trans[i].symbol))