Method init

gecode/int/extensional/dfa.cpp:151–472

namespace Gecode {

  void
  DFA::init(int start, Transition t_spec[], int f_spec[], bool minimize) {
    using namespace Int;
    using namespace Extensional;
    Region region;

    // Compute number of states and transitions
    int n_states = start;
    int n_trans  = 0;
    for (Transition* t = &t_spec[0]; t->i_state >= 0; t++) {
      n_states = std::max(n_states,t->i_state);
      n_states = std::max(n_states,t->o_state);
      n_trans++;
    }
    for (int* f = &f_spec[0]; *f >= 0; f++)
      n_states = std::max(n_states,*f);
    n_states++;

    // Temporary structure for transitions
    Transition* trans = region.alloc<Transition>(n_trans);
    for (int i=0; i<n_trans; i++)
      trans[i] = t_spec[i];
    // Temporary structures for finals
    int* final = region.alloc<int>(n_states+1);
    bool* is_final = region.alloc<bool>(n_states+1);
    int n_finals = 0;
    for (int i=0; i<n_states+1; i++)
      is_final[i] = false;
    for (int* f = &f_spec[0]; *f != -1; f++) {
      is_final[*f]      = true;
      final[n_finals++] = *f;
    }

    if (minimize) {
      // Sort transitions by symbol and i_state
      TransBySymbolI_State::sort(trans, n_trans);
      Transition** idx = region.alloc<Transition*>(n_trans+1);
      //  idx[i]...idx[i+1]-1 gives where transitions for symbol i start
      int n_symbols = 0;
      {
        int j = 0;
        while (j < n_trans) {
          idx[n_symbols++] = &trans[j];
          int s = trans[j].symbol;
          while ((j < n_trans) && (s == trans[j].symbol))
            j++;
        }
        idx[n_symbols] = &trans[j];
        assert(j == n_trans);
      }
      // Map states to groups
      int* s2g = region.alloc<int>(n_states+1);
      StateGroup* part = region.alloc<StateGroup>(n_states+1);
      GroupStates* g2s = region.alloc<GroupStates>(n_states+1);
      // Initialize: final states is group one, all other group zero
      for (int i=0; i<n_states+1; i++) {
        part[i].state = i;
        part[i].group = is_final[i] ? 1 : 0;