package algs54; // section 5.4
import stdlib.*;
import algs13.Bag;
import algs13.Stack;
import algs42.Digraph;
import algs42.DirectedDFS;
/* ***********************************************************************
 *  Compilation:  javac NFA.java
 *  Execution:    java NFA regexp text
 *  Dependencies: Stack.java Bag.java Digraph.java DirectedDFS.java
 *
 *  % java NFA "(A*B|AC)D" AAAABD
 *  true
 *
 *  % java NFA "(A*B|AC)D" AAAAC
 *  false
 *
 *  % java NFA "(a|(bc)*d)*" abcbcd
 *  true
 *
 *  % java NFA "(a|(bc)*d)*" abcbcbcdaaaabcbcdaaaddd
 *  true
 *
 *  Remarks
 *  -----------
 *    - This version does not currently suport multiway or, wildcard,
 *      or the + operator.
 *
 *************************************************************************/

public class NFA {

  private final Digraph G;         // digraph of epsilon transitions
  private final String regexp;     // regular expression
  private final int M;             // number of characters in regular expression

  // Create the NFA for the given RE
  public NFA(String regexp) {
    this.regexp = regexp;
    M = regexp.length();
    Stack<Integer> ops = new Stack<>();
    G = new Digraph(M+1);
    for (int i = 0; i < M; i++) {
      int lp = i;
      if (regexp.charAt(i) == '(' || regexp.charAt(i) == '|')
        ops.push(i);
      else if (regexp.charAt(i) == ')') {
        int or = ops.pop();
        if (regexp.charAt(or) == '|') {
          lp = ops.pop();
          G.addEdge(lp, or+1);
          G.addEdge(or, i);
        }
        else if (regexp.charAt(or) == '(')
          lp = or;
        else assert false;
      }

      // Lookahead;
      if (i < M-1 && regexp.charAt(i+1) == '*') {
        G.addEdge(lp, i+1);
        G.addEdge(i+1, lp);
      }
      if (regexp.charAt(i) == '(' || regexp.charAt(i) == '*' || regexp.charAt(i) == ')')
        G.addEdge(i, i+1);
    }
  }

  // Does the NFA recognize txt?
  public boolean recognizes(String txt) {
    DirectedDFS dfs = new DirectedDFS(G, 0);
    Bag<Integer> pc = new Bag<>();
    for (int v = 0; v < G.V(); v++)
      if (dfs.marked(v)) pc.add(v);

    // Compute possible NFA states for txt[i+1].
    for (int i = 0; i < txt.length(); i++) {
      Bag<Integer> match = new Bag<>();
      for (int v : pc) {
        if (v == M) continue;
        if ((regexp.charAt(v) == txt.charAt(i)) || regexp.charAt(v) == '.')
          match.add(v+1);
      }
      dfs = new DirectedDFS(G, match);
      pc = new Bag<>();
      for (int v = 0; v < G.V(); v++)
        if (dfs.marked(v)) pc.add(v);

      // optimization if no states reachable
      if (pc.size() == 0) return false;
    }

    // check for accept state
    for (int v : pc)
      if (v == M) return true;
    return false;
  }


  public static void main(String[] args) {
    args = new String[] { "(a|(bc)*d)*", "abcbcbcdaaaabcbcdaaaddd" };

    String regexp = "(" + args[0] + ")";
    String txt = args[1];
    NFA nfa = new NFA(regexp);
    StdOut.println(nfa.recognizes(txt));
  }

}