private IntPair complement()

in jflex/src/main/java/jflex/core/NFA.java [579:689]
69 lines of code
15 McCabe index (conditional complexity)

  private IntPair complement(IntPair nfa) {

    if (Build.DEBUG) {
      Out.debug("complement for " + nfa);
      Out.debug("NFA is :" + Out.NL + this);
    }

    int dfaStart = nfa.end() + 1;

    epsilonFill();

    Map<StateSet, Integer> dfaStates = new HashMap<>(numStates);
    List<StateSet> dfaList = new ArrayList<>(numStates);

    int numDFAStates = 0;
    int currentDFAState = 0;

    StateSet currentState, newState;

    newState = epsilon[nfa.start()];
    dfaStates.put(newState, numDFAStates);
    dfaList.add(newState);

    if (Build.DEBUG) {
      Out.debug(
          "pos DFA start state is :"
              + Out.NL
              + dfaStates
              + Out.NL
              + Out.NL
              + "ordered :"
              + Out.NL
              + dfaList);
    }

    while (currentDFAState <= numDFAStates) {

      currentState = dfaList.get(currentDFAState);

      for (int input = 0; input < numInput; input++) {
        newState = DFAEdge(currentState, input);

        if (newState.containsElements()) {

          // Out.debug("DFAEdge for input "+(int)input+" and state set "+currentState+" is
          // "+newState);

          // Out.debug("Looking for state set "+newState);
          Integer nextDFAState = dfaStates.get(newState);

          if (nextDFAState != null) {
            // Out.debug("FOUND!");
            addTransition(dfaStart + currentDFAState, input, dfaStart + nextDFAState);
          } else {
            if (Options.dump) {
              Out.print("+");
              // Out.debug("NOT FOUND!");
              // Out.debug("Table was "+dfaStates);
            }
            numDFAStates++;

            dfaStates.put(newState, numDFAStates);
            dfaList.add(newState);

            addTransition(dfaStart + currentDFAState, input, dfaStart + numDFAStates);
          }
        }
      }

      currentDFAState++;
    }

    // We have a dfa accepting the positive regexp.

    // Now the complement:
    if (Build.DEBUG) {
      Out.debug("dfa finished, nfa is now :" + Out.NL + this);
    }

    int start = dfaStart + numDFAStates + 1;
    int error = dfaStart + numDFAStates + 2;
    int end = dfaStart + numDFAStates + 3;

    addEpsilonTransition(start, dfaStart);

    for (int i = 0; i < numInput; i++) addTransition(error, i, error);

    addEpsilonTransition(error, end);

    for (int s = 0; s <= numDFAStates; s++) {
      currentState = dfaList.get(s);

      currentDFAState = dfaStart + s;

      // if it was not a final state, it is now in the complement
      if (!currentState.hasElement(nfa.end())) addEpsilonTransition(currentDFAState, end);

      // all inputs not present (formerly leading to an implicit error)
      // now lead to an explicit (final) state accepting everything.
      for (int i = 0; i < numInput; i++)
        if (table[currentDFAState][i] == null) addTransition(currentDFAState, i, error);
    }

    // eliminate transitions that cannot reach final states
    removeDead(dfaStart, end);

    if (Build.DEBUG) {
      Out.debug("complement finished, nfa (" + start + "," + end + ") is now :" + this);
    }
    return IntPair.create(start, end);
  }