/*---------------------------------------------------------------------------
File:         			TreeMachine.java
Package:                        JFLAP Version 2.0
Author:				Magda & Octavian Procopiuc V1.0 07/15/96
                                Eric Gramond V2.0 07/22/97 
 
Description of Contents:	Contains class TreeMachine.
				
--------------------------------------------------------------------------*/

/* 
 * Susan H. Rodger, Magda Procopiuc, Octavian Procopiuc, Eric Gramond
 * Computer Science Department
 * Duke University
 * June 1998
 * Supported by National Science Foundation DUE-9596002 and DUE-9555084.
 *
 * Copyright (c) 1998
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms are permitted
 * provided that the above copyright notice and this paragraph are
 * duplicated in all such forms and that any documentation,
 * advertising materials, and other materials related to such
 * distribution and use acknowledge that the software was developed
 * by the author.  The name of the author may not be used to
 * endorse or promote products derived from this software without
 * specific prior written permission.
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
 * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
 */

package flap;

import java.util.*;
import java.awt.*;

/**
  * This Machine is a tree used in the Minimize algorithm. 
  *
  *
  * Any subclass of this class has to override at least
  * the following (non-public) methods:
  *
  * @see		flap.FSA
  * @see		flap.PDA
  * @see		flap.TM1
  * @see		flap.TM2
  * @author	Magda & Octavian Procopiuc
  * @version	1.0 15 July 1996
  */
public class TreeMachine extends Machine {

  FSA minimizeSource;
  Environment parent;
  
  TreeMachine(Desktop d, Environment env) {
    super(d);
    parent = env;
  }

  // trees aren't made to be run
  public  boolean expand(Configuration c) {
      return false;
    }
  public Configuration initialConfig() {
      return null;
    }

  public boolean isDeterministic(Transition t , Vector v ) {
      return false;
    }


  /**
    * set up the beginning of the tree by separating final and nonfinal states
    */
  public int  startTree(Machine source) {
    int trap;

    minimizeSource = new FSA( new Desktop(source.d));
    if ((trap = minimizeSource.fillImplicitTransitions()) != -1) {
      parent.setEnabled(false);
      String error = "State q" + trap + " is the implicit trap state.\n";
      OKDialog dg = new OKDialog(error, new Frame(), "Minimize notice.");
      dg.findResult();
      parent.setEnabled(true);
    }
     
    Vector finalVe = new Vector();
    Vector nonfinalVe = new Vector();
    State aState;
    MinimizeDesktop d2 = (MinimizeDesktop) d;

    for(Enumeration e = minimizeSource.d.theStates.elements(); e.hasMoreElements(); ) {
      aState = (State) e.nextElement();
      if(aState.isFinal)  finalVe.addElement(aState);
      else                nonfinalVe.addElement(aState);
    }
    
    d2.finals = d.addState(50, 50);
    d2.finals.stateList = finalVe;
    d2.finals.stateListToLabel();
    d2.nonFinals= d.addState(100, 50);
    d2.nonFinals.stateList = nonfinalVe;
    d2.nonFinals.stateListToLabel();
    d2.menu = new MinimizeTreePopup(this);
    d2.placeStates();
    d.repaint();

    return trap;

  }

 /** Places all the states for the solved DFA solution */
    public void placeAllStates(Machine model, Machine nfa) {
    }



    /** not implemented  */
    public String checkIfDone(Machine amodel, Machine original) {
	return "function not implemented.";
    }


  /**
    * checks if the given state can be attempted to be split (so it can be toggled on 
    * in the popup menu)
    */
  public boolean canSplitState(State s) {
    MinimizeDesktop d2 = (MinimizeDesktop) d;
    MinimizeTreeState aState = (MinimizeTreeState) s;
    
    d.setAllStateLists(minimizeSource.d);

    if(aState.transitions.size() > 0 )
      return false;

    if(aState.stateList.size() <= 1)
      return false;

    return true;
  }
 
  /**
    * Checks if an extra  child can be added to the state
    */
  public boolean canAddChild(State s) {
    
    Transition aTransition;
    
    if( ((MinimizeDesktop)d).expanding != s)
      return false;

    d.setAllStateLists(minimizeSource.d);

    for(Enumeration e = s.transitions.elements(); e.hasMoreElements(); ) {
      aTransition = (Transition) e.nextElement();
      if(aTransition.to.stateList.size() == 0)
	return false;
    }

    return true;
  }
 
  /**
    * checks if the state can be removed
    */
  public boolean canRemoveState(State s) {
    Transition aTransition;
    MinimizeDesktop d2 = (MinimizeDesktop) d;

   d.setAllStateLists(minimizeSource.d);   
    
    if(d2.expanding == null)
      return false;
    if(d2.expanding.transitions.size() < 3)
      return false;

    for(Enumeration e = d2.expanding.transitions.elements(); e.hasMoreElements(); ) {
      aTransition = (Transition) e.nextElement();
      if (aTransition.to == s)
	return true;
    }
    return false;
  }
 
  /**
    * split the state if there are no errors so far in the tree
    */
  public void splitState(State s) {
    State state1, state2;

    d.repaint();

    if(!isDoneExpanding())
      return;

    if(!needsExpanding((MinimizeTreeState) s)) {
      String error = "This state cannot be split now.";
      parent.setEnabled(false);
      OKDialog dg = new OKDialog(error, new Frame(), "Minimize check.");
      dg.findResult();
      parent.setEnabled(true);
      d.repaint();
      return;
    }
    
    if( ((MinimizeDesktop) d).expanding != null)
      ((MinimizeDesktop) d).expanding.ss = State.NORMAL;

    state1 = d.addState(0,0);
    state2 = d.addState(0,0);
    s.transitions.addElement(d.addTransition(s, state1));
    s.transitions.addElement(d.addTransition(s, state2));
    ((MinimizeDesktop) d).placeStates();
    ((MinimizeDesktop) d).expanding = (MinimizeTreeState) s;
    ((MinimizeDesktop) d).selectedSplitting = s;
    d.selectedState = null;
    d.selectedTransition = null;

    //s.ss = State.HIGHLIGHTED;
  }

  /**
    * add an extra child to the tree
    */
  public void addChild(State s) {
    Transition aTransition;

    d.repaint();
    d.setAllStateLists(minimizeSource.d);

    int weightSum = 0;
    for(Enumeration e = s.transitions.elements(); e.hasMoreElements(); ) {
      aTransition = (Transition) e.nextElement();
      weightSum += aTransition.to.stateList.size();
    }

    if(weightSum >= s.stateList.size()) {
      String error = "All the labels in the expanding state \n are already placed.";
      parent.setEnabled(false);
      OKDialog dg = new OKDialog(error, new Frame(), "Minimize error.");
      dg.findResult(); 
      parent.setEnabled(true);
      return;
    }
    
    State newState = d.addState(0,0);
    s.transitions.addElement(d.addTransition(s, newState));
    ((MinimizeDesktop) d).placeStates();
  }

  /**
    * remove the state from the graph
    */
  public void removeState(State s) {

    Transition aTransition;
    MinimizeDesktop d2 = (MinimizeDesktop) d;

    for(int i=0; i< d2.expanding.transitions.size(); ) {
      aTransition = (Transition) d2.expanding.transitions.elementAt(i);
      if(aTransition.to == s)
	d2.expanding.transitions.removeElement(aTransition);
      else
	i++;
    }
    d.removeState(s);
    d2.placeStates();
    d2.repaint();
  }

  /**
    * checks if the currently expanding state has been expanded correctly
    */
  public void checkDoneExpanding(State s)
  {
    if(!isDoneExpanding())
      return;

    ((MinimizeDesktop) d).expanding.ss = State.NORMAL;
    ((MinimizeDesktop) d).expanding = null;
    d.repaint();
    String error = "The state is correct.";
    parent.setEnabled(false);
    OKDialog dg = new OKDialog(error, new Frame(), "Minimize check.");
    dg.findResult();
    parent.setEnabled(true);
  }

  /**
    * check if the whole tree is finished
    */
  public boolean  checkMinimizeDone()
  {
    MinimizeTreeState aState;

    if(((MinimizeDesktop) d).expanding != null) {

      if(!isDoneExpanding())
	return false;
      ((MinimizeDesktop) d).expanding.ss = State.NORMAL;
      ((MinimizeDesktop) d).expanding = null;
    }

    for(Enumeration e = d.theStates.elements(); e.hasMoreElements(); ) {
      aState = (MinimizeTreeState) e.nextElement();
      if(aState.transitions.size() > 0)
	continue;
      if(needsExpanding(aState))
      {
	aState.ss = State.HIGHLIGHTED;
	String error = "The highlighted state needs to be split.";
	d.repaint();
        parent.setEnabled(false);
	OKDialog dg = new OKDialog(error, new Frame(), "Minimize check.");
	dg.findResult();
        parent.setEnabled(true);
	aState.ss = State.NORMAL;
	d.repaint();
	return false;
      }
    }
    return true;
  }


  /** checks if the current expanding state is complete */
  public boolean isDoneExpanding() {
    
    Transition aTransition;
    int weightTotal = 0;
    int temp;
    String error;
    MinimizeDesktop d2 = (MinimizeDesktop) d;
    Enumeration e2;
    State aState;

    d.setAllStateLists(minimizeSource.d);
    minimizeSource.d.unmarkAllStates();

    if(d2.expanding == null)
      return true;

    for(Enumeration e = d2.expanding.transitions.elements(); e.hasMoreElements(); ) {
      aTransition = (Transition) e.nextElement();
      try
      {
	  temp = aTransition.to.labelToStateList(minimizeSource.d);
      }
      catch(NumberFormatException num)
      {
          parent.setEnabled(false);
	  OKDialog dg = new OKDialog("All state labels must be numbers.", new Frame(), "Minimize check.");
	  dg.findResult();
          parent.setEnabled(true);
	  return false;
      }
      if(temp != -2) {
	if (temp == -1)
	  error = "The highlighted state has an empty label.";
	else
           error = "There is no state labeled q"+temp+" \n in the original DFA.";
	aTransition.to.ss = State.FOCUSED;
	d.repaint();
        parent.setEnabled(false);
        OKDialog dg = new OKDialog(error, new Frame(), "Minimize check.");
	dg.findResult(); 
        parent.setEnabled(true);
	aTransition.to.ss = State.NORMAL;
        d.repaint();
	return false;
      }
      for(e2 = aTransition.to.stateList.elements(); e2.hasMoreElements(); ) {
	aState = (State) e2.nextElement();
	if(aState.checkMark++ != 0) {
	  error = "The state q"+aState.id+ " is already included in one \n of the highlighted state's sibling states.";
	  aTransition.to.ss = State.FOCUSED;
	  d.repaint();
          parent.setEnabled(false);
	  OKDialog dg = new OKDialog(error, new Frame(), "Minimize check.");
	  dg.findResult(); 
          parent.setEnabled(true);
	  aTransition.to.ss = State.NORMAL;
          d.repaint();
	  return false;
	}
	if(!d2.expanding.stateList.contains(aState)) {
	  aTransition.to.ss = State.FOCUSED;
	  error = "The state q"+aState.id+ " should not be \n part of the highlighted state's label.\n It is not part of its parent's label.";
	  OKDialog dg = new OKDialog(error, new Frame(), "Minimize check.");
	  d.repaint();
          parent.setEnabled(false);
	  dg.findResult(); 
          parent.setEnabled(true);
	  aTransition.to.ss = State.NORMAL;
          d.repaint();
	  return false;
	}
      }
    }
    for(Enumeration e = d2.expanding.stateList.elements(); e.hasMoreElements(); ) {
      aState = (State) e.nextElement();
      if(aState.checkMark == 0) {
	error = "The state q" + aState.id + " is not in any of the child states.";
	OKDialog dg = new OKDialog(error, new Frame(), "Minimize check.");
	d.repaint();
        parent.setEnabled(false);
	dg.findResult();
        parent.setEnabled(true);
	return false;
      }
    }

    Vector alphabet = minimizeSource.getAlphabet();
    if(d2.expanding.splittingLetter.equals("")) {
      d2.selectedSplitting = d2.expanding;
      d2.selectedState = null;
      d2.selectedTransition = null;
      d2.repaint();
      error = "The selected label should not be empty.";
      parent.setEnabled(false);
      OKDialog dg = new OKDialog(error, new Frame(), "Minimize check.");
      dg.findResult();
      parent.setEnabled(true);
      return false;
    }
    if(alphabet.indexOf(new Character(d2.expanding.splittingLetter.charAt(0))) == -1) {
      d2.selectedSplitting = d2.expanding;
      d2.selectedState = null;
      d2.selectedTransition = null;
      d2.repaint();
      error = "The letter " + d2.expanding.splittingLetter + " is not in the alphabet.";
      parent.setEnabled(false);
      OKDialog dg = new OKDialog(error, new Frame(), "Minimize check.");
      dg.findResult();
      parent.setEnabled(true);
      return false;
    }
    
    // all badly formed situations have been taken care of above. now check for correctness

    Character letter = new Character(d2.expanding.splittingLetter.charAt(0)); 
    if(findChildren(d2.expanding,  letter).size() == 1) {
      error = "The letter \"" + letter + "\" cannot distingish anything \n in the state being split.";
      d2.repaint();
      parent.setEnabled(false);
      OKDialog dg = new OKDialog(error, new Frame(), "Minimize check.");
      dg.findResult();
      parent.setEnabled(true);
      return false;
    }

    return isDoneExpandingHelper(d2.expanding, 
				 new Character(d2.expanding.splittingLetter.charAt(0)));
  }



  private boolean isDoneExpandingHelper(MinimizeTreeState expState, Character letter) {
    Vector answer = findChildren(expState, letter);
    Vector user = new Vector();
    State aState, aState2;
    Transition aTransition;
    MinimizeDesktop d2 = (MinimizeDesktop) d; 
    String error;

    for(Enumeration e = d2.expanding.transitions.elements(); e.hasMoreElements(); ) {
      aTransition  = (Transition) e.nextElement();
      user.addElement(aTransition.to);
    }

    VectorArray arr = new VectorArray(user);
    Sorting.sort( arr, new MinimizeSortPredicate() );
    user = new Vector();
    for ( Enumeration e = arr.elements(); e.hasMoreElements(); ) 
      user.addElement( (State) e.nextElement());

    if(user.size() != answer.size()) {
      error = "The state being expanded should \n have " + answer.size() + " children.";
      parent.setEnabled(false);
      OKDialog dg = new OKDialog(error, new Frame(), "Minimize check.");
      dg.findResult();
      parent.setEnabled(true);
      return false;
    }


    Enumeration e;
    State tempState;
    for(int i = 0; i < answer.size();i++ ) {

      aState = (State) answer.elementAt(i);
      aState2 = (State) user.elementAt(i);
      for(e = aState.stateList.elements(); e.hasMoreElements(); ) {
	tempState = (State) e.nextElement();
	if(! aState2.stateList.contains(tempState)) {
	  aState2.ss = State.FOCUSED;
	  error = "q"+tempState.id+ " should be in the highlighted state, \n with q"+
	  ((State) aState.stateList.elementAt(0)).id  + ".";
	  d.repaint();
	  parent.setEnabled(false);
          OKDialog dg = new OKDialog(error, new Frame(), "Minimize check.");
	  dg.findResult();
          parent.setEnabled(true);
	  aState2.ss = State.NORMAL;
	  return false;
	}
      }
      for(e = aState2.stateList.elements(); e.hasMoreElements(); ) {
	tempState = (State) e.nextElement();
	if(! aState.stateList.contains(tempState)) {
	  aState2.ss = State.FOCUSED;
	  error = "q"+tempState.id+ " should not be in the same state as q" + 
	  ((State) aState.stateList.elementAt(0)).id  +".";
	  OKDialog dg = new OKDialog(error, new Frame(), "Minimize check.");
	  d.repaint();
	  parent.setEnabled(false);
          dg.findResult();
          parent.setEnabled(false);
	  aState2.ss = State.NORMAL;
	  return false;
	}
      }


    }
    return true;
  }
  

  /**
    * checks if the given state needs expanding.
    */
  private boolean needsExpanding(MinimizeTreeState checkState) {
    
    Character aCharacter;
    Vector alphabet = minimizeSource.getAlphabet();
    Vector answer;

    for(Enumeration e = alphabet.elements(); e.hasMoreElements(); ) {
      aCharacter = (Character) e.nextElement();
      answer = findChildren(checkState, aCharacter);
      if(answer.size() > 1)
	return true;
    } 
    return false;
  }


  private Vector findChildren(MinimizeTreeState expState, Character letter) {

    Vector baseList = new Vector();
    State aState, aState2, aState3;
    Transition aTransition;
    Character aCharacter;
    Enumeration e2;
    int i;
    boolean found;

    MinimizeDesktop d2 = (MinimizeDesktop) d;

    for(Enumeration e = d2.theStates.elements(); e.hasMoreElements(); ) {
      aState = (State) e.nextElement();
      if((aState.transitions.size() == 0) || (aState == expState)) {
	baseList.addElement(aState);
      }
    }
    for(Enumeration e = expState.transitions.elements(); e.hasMoreElements(); ) {
      aTransition = (Transition) e.nextElement();
      baseList.removeElement(aTransition.to);
    }


    Vector answerList = new Vector();
    for(i=0; i<=baseList.size(); i++)
      answerList.addElement(new MinimizeTreeState());
    
    State temp;
    for(Enumeration e = expState.stateList.elements(); e.hasMoreElements(); ) {
	found = false;
	aState = (State) e.nextElement();
	temp = aState;
	aTransition = minimizeSource.findFirstLambda(aState);
	aState2 = (aTransition == null) ? aState : aTransition.to;
	aTransition  = minimizeSource.findTransition(aState2, letter.charValue());
	aState = (aTransition == null) ? null :  aTransition.to;
	if(aState == null) {
	  if (((State) answerList.elementAt(answerList.size()-1)).label.length() == 0)
	    ((State) answerList.elementAt(answerList.size()-1)).label = String.valueOf(temp.id);
	  else 
	    ((State) answerList.elementAt(answerList.size()-1)).label += 
	      "," + String.valueOf(temp.id);
	  found = true;
	} else {
	test: for(i = 0; i < baseList.size(); i++ ) {
	  aState2 = (MinimizeTreeState) baseList.elementAt(i);
	  for(e2 = aState2.stateList.elements(); e2.hasMoreElements(); ) {
	    aState3 = (State) e2.nextElement();
	    if(aState3 == aState) {
	      if(  ((State) answerList.elementAt(i)).label.length() == 0)
		((State) answerList.elementAt(i)).label = String.valueOf(temp.id);
	      else 
		((State) answerList.elementAt(i)).label += "," + String.valueOf(temp.id);
	      found = true;
	      break test;
	    }
	  }
	}
	}
	if(!found) 
	    System.out.println("WARNING: missing state");
    }
    
    for(i = answerList.size()-1; i >= 0; i--) {
      if(((State) answerList.elementAt(i)).label.trim().equals(""))
	answerList.removeElementAt(i);
      else
	((State) answerList.elementAt(i)).labelToStateList(minimizeSource.d);
    }


    VectorArray arr = new VectorArray(answerList);
    Sorting.sort( arr, new MinimizeSortPredicate() );
    answerList = new Vector();
    for ( Enumeration e = arr.elements(); e.hasMoreElements(); ) 
      answerList.addElement( (State) e.nextElement());


    return answerList;
  }

  /**
    * completely solves whichever parts of the tree are not yet finished
    */
  public void showAllMinimize() {
    MinimizeDesktop d2 = (MinimizeDesktop) d;
    MinimizeTreeState aState;
    Enumeration e;
    
    if(d2.expanding != null)
      solveState(d2.expanding);


    boolean done = false;
    while(done != true) {
      done = true;
      for(e = d.theStates.elements(); e.hasMoreElements(); ) {
	aState = (MinimizeTreeState) e.nextElement();
	if(aState.transitions.size() > 0)
	  continue;
	if(needsExpanding(aState)) {
	  splitState(aState);
	  solveState(aState);
	  done = false;
	  break;
	}
      }
    }

  }

  /**
    * solves the given state if it is the one being expanded
    */
  public void solveState(State s) {
    Character letter = null;
    Vector answer = null;
    Vector alphabet = minimizeSource.getAlphabet();
    MinimizeDesktop d2 = (MinimizeDesktop) d;
    State aState ,aState2;
    int i =0;

    d2.expanding.ss = State.NORMAL;

    if(d2.expanding.splittingLetter != null && d2.expanding.splittingLetter.length() > 0){
      letter = new Character(d2.expanding.splittingLetter.charAt(0));
      answer = findChildren(d2.expanding, letter);
      if(answer.size() < 2)
	letter = null;
    }
    for(Enumeration e = alphabet.elements(); e.hasMoreElements(); ) {
      if (letter != null)
	break;
      
      letter = (Character) e.nextElement();
      answer = findChildren(d2.expanding, letter);
      if(answer.size() < 2)
	letter = null;
    }
    
    d2.expanding.splittingLetter = String.valueOf(letter.charValue());

    i = d2.expanding.transitions.size();
    Enumeration e2 = d2.expanding.transitions.elements();
    for(Enumeration e = answer.elements(); e.hasMoreElements(); ) {
      if(e2.hasMoreElements() && i-- > 0)
	aState = ((Transition) e2.nextElement()).to;
      else {
	aState = d.addState(0,0);
	d2.expanding.transitions.addElement(d.addTransition(d2.expanding, aState));
      }
      aState2 = (State) e.nextElement();
      aState.label = new String(aState2.label);
      aState.stateList = aState2.stateList;
    }
    d2.expanding = null;
    d2.placeStates();
    d.repaint();
  }

  
 /* 
  * starts a functionThread with the given function inside
  */
  public void  startThread(String functionName, State state) {
	FunctionThread ft;
	Class source;
        
	try {
            Object arg[] = new Object[1];
            arg[0] = state;
            Class types[] = new Class[1];
            types[0] = Class.forName("flap.State");
	    source = this.getClass();
	    ft = new FunctionThread(source.getMethod(functionName, types), this, arg);
	    ft.start();
	}
	catch(NoSuchMethodException h)
        {
	    System.out.println("no " + functionName + " method found.");
	}
        catch(ClassNotFoundException e)
        {
            System.out.println(e);
        }
  }
}
