/*---------------------------------------------------------------------------
File:         			Desktop.java
Package:                        JFLAP Version 3.1
Author:				Magda & Octavian Procopiuc V1.0 07/15/96
                                Eric Gramond V3.0 08/14/98
				Ted Hung V3.1 07/25/99
Description of Contents:	Contains class Desktop.
				
--------------------------------------------------------------------------*/

/* 
 * Susan H. Rodger, Magda Procopiuc, Octavian Procopiuc, Eric Gramond, Ted Hung
 * Computer Science Department
 * Duke University
 * August 1999
 * Supported by National Science Foundation DUE-9596002, DUE-9555084,
 *  and DUE-9752583
 *
 * Copyright (c) 1999
 * 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.awt.*;
import  java.awt.event.*;
import	java.util.*;


/**
 * This is the canvas where the machines are built and displayed.
 * It is the main class involved in the interface part of 
 * the different
 * machines. The lists of transitions and states are kept here, 
 * and the actual painting of the transitions and states is performed
 * here also.
 *
 * @see		flap.State
 * @see		flap.Transition
 * @author	Magda & Octavian Procopiuc
 * @version	1.0, 15 July 1996
 */ 
public class Desktop extends Canvas implements MouseMotionListener, MouseListener {
    
  /**
   * The start state of the machine.
   */
  public State		initialState = null;
  /**
    * The currently selected transition.
    */
  public Transition	selectedTransition; 
  /**
    * The currently selected dfa State (for label)
    */
  public State          selectedState;
  /**
    * The list of states currently on the desktop.
    * The machine will use them from here, too.
    */
  public Vector		theStates;
  /**
   * The list of transitions currently on the desktop.
   * The machine will use them from here, too.
   */
  public Vector		theTransitions;
  /**
   * Becomes true when the current machine is modified in any way.
   */
  public boolean	modified = false;
  /**
   * The type of the machine currently on the desktop.
   * This enables us to draw any type of machine using this class.
   */
  public int		type;

  /**
   * When the user sets the auto relabel option,
   * this flag becomes true, and the states are
   * automatically relabeled each time one of them is removed.
   */
  boolean	autoRelabel = false;
  /**
   * The state label counter.
   */ 
  int		currentId = 0;
  /**
   * The x distance between the mouse pointer
   * and the center of the state circle, when
   * dragging a state.
   */
  protected int		x_offset = 0;
  /**
   * The x distance between the mouse pointer
   * and the center of the state circle, when
   * dragging a state.
   */
  protected int		y_offset = 0;
  protected Color	backcolor = Params._d_backcolor;
  protected PopupMenu	menu;
  protected boolean	menuOn = false;
  /**
   * used to retain the beginning state when dragging.
   */
  protected State	firstState = null;
  /**
   * used when dragging.
   */
  protected Transition	firstTransition = null;
  protected Point	drag = null;
  protected int		draggingWhat;
  /**
   * The number of sublabels in a label.
   */
  protected int		fieldCounter = 1;
  /**
   * The separators between the sublabels in a label.
   */
  protected String[]	separator = new String[6];

  /**
   * What are we currently dragging.
   */
    final static int DG_NOTHING	= 0;
    final static int DG_STATE	= 1;
    final static int DG_TRANS	= 2;
    final static int DG_LABEL	= 3;
    final static int DG_LOOP    = 4;

  /**
   * Used for writing the current machine in the tabular form.
   * @see	toTabular()
   */
  final static String EMPTY_STR = "-----";

  /**
   * the offscreen image.
   */
  private Image		offscr = null;
  /**
   * the graphics context of the offscreen image.
   */
  private Graphics	offg = null;

  private int	off1 = 11;
  private int	off2 = 6;
  private int 	count = 0; 

  /**
   * distance factor between transitions
   */
  private double df = 1.5;

  /**
    * value used in compareTo to initialise unique checkmarks
    */
  public int currentCheckMark = 0;


    /*
     * backup desktop for undoing andcopy of the environment's menuitem
     */
    public Desktop undoDesktop;
    private Desktop backupDesktop;
    public MenuItem undoItem;    

  /**
   * Tells whether to show state labels or not.
   * Modified by showDfaLabels and showStringLabel
   */
   public boolean showStateLabels = false;

  /**
   * Whether to handle the label as a DFA label or not
   */
  public boolean showDfaLabels = false;

  /**
   * Whether to handle the label as a regular grammar to FSA label or not
   */ 
  public boolean showStringLabel = false;
    

  /**
   * used to notify the last state that the mouse has moved
   * outside of it
   */
  private State lastMouseState = null;

  /**
   * Builds a new Desktop with the specified type.
   * @param type	the type of the machine represented on the desktop.
   */
  public Desktop(int type) {
    this.type = type;

  /**
   * Overrides processKeyEvent so that tabs can be
   * consumed by Desktop
   */
    this.enableEvents(AWTEvent.KEY_EVENT_MASK);
    
    this.addMouseMotionListener(this);
    this.addMouseListener(this);
    //this.addKeyListener(this);
    
    theStates = new Vector(10, 1);
    theTransitions = new Vector(30, 1);
    menu = new Popup(this);
    setupSeparators();
  }

  /** 
    * copy constructor. makes a deep copy.
    * Precondition: all State ids are unique.
    */
  public Desktop(Desktop aDesktop) {
    this(aDesktop.type);

    Enumeration e;
    this.currentId = aDesktop.currentId;
    this.autoRelabel = aDesktop.autoRelabel;
    this.showDfaLabels = aDesktop.showDfaLabels;
    undoDesktop = aDesktop.undoDesktop;
    this.showStringLabel = aDesktop.showStringLabel;
    this.showStateLabels = aDesktop.showStateLabels;

    int idFrom, idTo;
    State stateFrom, stateTo;
    Transition aTransition;

    for( e = aDesktop.theStates.elements(); e.hasMoreElements(); ) 
      theStates.addElement(new State( (State) e.nextElement()));
    
    for( e = aDesktop.theTransitions.elements(); e.hasMoreElements(); ) {
      aTransition = (Transition) e.nextElement();
      idFrom = aTransition.from.id;
      idTo = aTransition.to.id;
      stateFrom = getStateWithId(idFrom);
      stateTo = getStateWithId(idTo);
      this.addTransition(stateFrom, stateTo).label = new String(aTransition.label);
      ((Transition) theTransitions.lastElement()).distance = aTransition.distance; 
    }
    
    if(aDesktop.initialState != null)
      this.initialState = getStateWithId(aDesktop.initialState.id);

  }


  /**
    * sets up the separators for transition labels for different types of automatons
    */
  void setupSeparators() {
 switch (type) {
      case Machine.FSA:
        fieldCounter = 1;
        break;
      case Machine.PDA:
        separator[0] = ",";
        separator[1] = ";";
        fieldCounter = 3;
        break;
      case Machine.TM1:
        separator[0] = ";";
        separator[1] = ",";
        fieldCounter = 3;
        break;
      case Machine.TM2:
        separator[0] = ";";
        separator[1] = ",";
        separator[2] = "|";
        separator[3] = ";";
        separator[4] = ",";
        fieldCounter = 6;
        break;
    }
    separator[fieldCounter - 1] = "";
  }

  /**
    *  Overrides Component.processKeyEvent so that tabs are 
    *  consumed here in the canvas instead of letting the
    *  canvas go out of focus and highlighting another component
    */
  protected void processKeyEvent(KeyEvent e) 
  {
      if (e.getID() == KeyEvent.KEY_PRESSED)
      {
          if(e.getKeyCode() == KeyEvent.VK_TAB)
          {
	    e.consume();
          }
          else if(e.isActionKey())
	  {
	    keyTyped(e);
	  }
	  // must consume so that a tab will not take the Desktop out of focus
      }
      else if(e.getID() == KeyEvent.KEY_TYPED)
      {
	  keyTyped(e);
      }
  }
    
  public void keyTyped(KeyEvent e) 
  {
    backup();
    int key;
    boolean modif = false;
    if (!e.isActionKey()) // if is a character key
        key = e.getKeyChar();
    else
        key = e.getKeyCode();

    requestFocus();
    if(showStateLabels && selectedState != null)
    {
        if(showDfaLabels)
            modif= selectedState.processDfaKey(key, e);
        else if(showStringLabel)
            modif = selectedState.processStringKey(key,e);
        else
            modif = selectedState.processKey(key,e);
    }
    else if(selectedTransition != null)
    {
        modif = selectedTransition.processKey(key, e);
    }

    if(modif)
        modify();
	  
    repaint();
    e.consume();
    requestFocus();
  }

  public void mouseClicked(MouseEvent e) 
  {}
  public void mouseEntered(MouseEvent e) 
  {}
  public void mouseExited(MouseEvent e) 
  {}
  public void mousePressed(MouseEvent e){

    State	s;
    Transition	t;
    
    int x = e.getX();
    int y = e.getY();

    requestFocus();

    //ignore clicks while dragging
    if(draggingWhat != Desktop.DG_NOTHING)
	return;
    
    backup();

    int mods = e.getModifiers();
    
    if((mods & Event.ALT_MASK) != 0 ||
       (mods & Event.SHIFT_MASK) != 0 ||
       (mods & InputEvent.BUTTON2_MASK) != 0)
    {
       //middle mouse button
       if ((s = isInState(x,y)) != null) {
          draggingWhat = Desktop.DG_STATE;
          firstState = s;
          x_offset = x - s.p.x;
          y_offset = y - s.p.y;
          modified = true;
        }
        else if (isGoodLocation(x, y)) {
          s = addState(x, y);
          if (theStates.size() == 1)
            initialState = s;
          draggingWhat = Desktop.DG_STATE;
          firstState = s;
          x_offset = 0;
          y_offset = 0;
          modified = true;
        }
        else {
          draggingWhat = Desktop.DG_NOTHING;
        }
    }
    else if((mods & Event.META_MASK) != 0 ||
            (mods & Event.CTRL_MASK) != 0 ||
	    (mods & InputEvent.BUTTON3_MASK) != 0)
    {
        //right mouse button
        menuOn = true;
        menu.move(x, y);
        menu.invalidateAll();
        if ((s = isInState(x, y)) != null) 
          menu.setState(s);
        else if ((t = isInTransition(x, y)) != null)
          menu.setTransition(t);
    }
    else 
    {
        //left mouse button and anything else
        if ((t = isInTransition(x,y)) != null) {
          draggingWhat = Desktop.DG_LABEL;
          firstTransition = t;
          selectedTransition = t;
          Point pp = locateLabel(t);   
          x_offset = x - pp.x;
          y_offset = y - pp.y;
          selectedState = null;
          t.tokenizeLabel();
	} else if (((showStateLabels) && 
                    ( s = isInStateDfaLabel(x,y)) != null)) {
          draggingWhat = Desktop.DG_NOTHING;
          firstState = s;
	  selectedTransition = null;
	  selectedState = s;   
        } else if ((s = isInState(x,y)) != null) {
	    draggingWhat = Desktop.DG_TRANS;
	    firstState = s;
	    drag = new Point(x, y);
	} else if((s = isInLoopTop(x,y)) != null) {
	    draggingWhat = Desktop.DG_LOOP;
	    firstState = s;
	    x_offset = x - s.p.x;
	    y_offset = y - (s.p.y - s.loopSize);
        } else {
	    selectedTransition = null;
	    selectedState = null;
	    draggingWhat = Desktop.DG_NOTHING;
        }
    }
    repaint();
  }	// end of method MouseDown.
  
  public void mouseMoved(MouseEvent e)
  {
    State s;
    int x = e.getX();
    int y = e.getY();

    if ((s = isInState(x,y)) != null) {
      s.setMouseOver(true);
    }

    if(s != lastMouseState)
    {
      if(lastMouseState != null)
	 lastMouseState.setMouseOver(false);
      repaint();
    }
    else if(s != null)
    {
      repaint();
    }

    lastMouseState = s;
  }
  
  public void mouseDragged(MouseEvent e) 
  {

    int x = e.getX();
    int y = e.getY();

    int mods = e.getModifiers();
    if((mods & Event.ALT_MASK) != 0 ||
       (mods & Event.SHIFT_MASK) != 0 ||
       (mods & InputEvent.BUTTON2_MASK) != 0)
    {
        //middle button
        if (draggingWhat == Desktop.DG_STATE)
	{
	  firstState.move(x - x_offset, y - y_offset, getSize());
	}
    }
    else if((mods & Event.META_MASK) != 0 ||
            (mods & Event.CTRL_MASK) != 0 ||
	    (mods & InputEvent.BUTTON3_MASK) != 0)
    {
        //right button
	if (x >= menu.p.x && x <= menu.p.x + menu.width)
	{
          int idx = (int) Math.floor((y - menu.p.y) / menu.height);
          if (y >= menu.p.y && idx < menu.itemsCounter)
            menu.hasFocus = idx;
          else
            menu.hasFocus = -1;
        } else
          menu.hasFocus = -1;
    }
    else
    {
        //left button and anything else
	if (draggingWhat == Desktop.DG_TRANS) {
          drag.move(x, y);
        }
        else if (draggingWhat == Desktop.DG_LABEL) {
	    slideLabel(firstTransition, x, y);
        }
	else if(draggingWhat == Desktop.DG_LOOP) {
	    slideLoop(firstState, x, y);
	}
    }

    repaint();
  }	// end of method MouseDrag.

  public void mouseReleased(MouseEvent e){
    State	s;
    Transition	t;

    int x = e.getX();
    int y = e.getY();

    int mods = e.getModifiers();
    if((mods & Event.ALT_MASK) != 0 ||
       (mods & Event.SHIFT_MASK) != 0 ||
       (mods & InputEvent.BUTTON2_MASK) != 0)
    {
        if (draggingWhat == Desktop.DG_STATE) {
          draggingWhat = Desktop.DG_NOTHING;
          // what if there's another state here???
          firstState.move(x - x_offset, y - y_offset, getSize());
          x_offset = 0;
          y_offset = 0;
          firstState = null;
	  modify();
        }
        else {}
    }
    else if(!((mods & Event.META_MASK) != 0 ||
              (mods & Event.CTRL_MASK) != 0 ||
	      (mods & InputEvent.BUTTON2_MASK) != 0))
    {
   	if (draggingWhat == Desktop.DG_LABEL) {
          draggingWhat = Desktop.DG_NOTHING;
	  slideLabel(firstTransition, x, y);
          x_offset = 0;
          y_offset = 0;
          firstTransition = null;
        } else if (draggingWhat == Desktop.DG_TRANS) {
          if ((s = isInState(x,y)) != null) {
            t = addTransition(firstState, s);
	    selectedTransition = t;
	    selectedState = null;
            if (firstState == s) {	// for loop transitions
		if(s.loopSize == 0)
		    s.loopSize += Params._t_distance;
		s.loopSize += Params._t_distance;
		//make sure it doesn't go off the top
		s.loopSize = Math.min(s.p.y, s.loopSize);
            }
	    modify();
          }
	  else {}
          drag = null;
          firstState = null;
          draggingWhat = Desktop.DG_NOTHING;
        }
	else if(draggingWhat == Desktop.DG_LOOP) {
	    draggingWhat = Desktop.DG_NOTHING;
	    slideLoop(firstState, x, y);
	    x_offset = y_offset = 0;
	    modify();
	  }
    }    // end of switch 
    if (menuOn) {	// it's not under switch due to differences in events on
	// different platforms. bugs...
      menuOn = false;
      if (menu.takeAction()) 
	  modify();

    }
    repaint();
  }

    /** 
     * Slides the loop size of the same state transitions to this state
     */
    private void slideLoop(State s, int x, int y) {
	Dimension d = getSize();
	y = y - y_offset;
	y = Math.min(y, s.p.y -Params._s_loop_radius - Params._t_distance );
	y = Math.max(y, 0);
	s.loopSize = s.p.y - y;
    }

    /** 
     * Slides the label of a transition being dragged
     */
    private void slideLabel(Transition t, int x, int y) {
	FontMetrics	fm = getFontMetrics(Params._t_font);
	Dimension d = getSize();
	int x1 = t.from.p.x;
	int y1 = t.from.p.y;
	int x2 = t.to.p.x;
	int y2 = t.to.p.y;
	int xFinal, yFinal;

	if(t.from == t.to) {
	    y2 = y1 - t.from.loopSize;
	    if(y2 == y1)
		return;
	    yFinal = y - y_offset;
	    yFinal = Math.min(yFinal, y1 - Params._t_distance);
	    yFinal = Math.max(yFinal, y2 + Params._t_distance/3); 

	    t.distance = (double) (y1 - yFinal) / (double) (y1 - y2); 
	}
	else {
	    if (y1 > y2 || (y1 == y2 && x1 < x2)){
		x +=  fm.stringWidth(t.label)+Transition.off+Transition.offr;
		if(selectedTransition == t)
		    x += fm.stringWidth("_");
	    }     
	    if(x1 < x2 || (x1 == x2 && y1 < y2))  
		y += Params._t_height;
	    
	    if(Math.abs(y2 - y1) > Math.abs(x2 - x1)) {
		if(y2 == y1)
		    return;
		yFinal = y - y_offset;
		if( Math.abs(yFinal - y1) > Math.abs(y2 - y1))
		    yFinal = y2;
		yFinal = Math.max(yFinal, 0);
		yFinal = Math.min(yFinal, d.height);
		if( (y1-y2) * (y1 - yFinal) < 0)
		    yFinal = y1;
		t.distance = Math.abs(    (double) (y1 - yFinal) / (double) (y1 - y2)); 
	    }
	    else {
		if(x2 == x1)
		    return;
		xFinal = x - x_offset;
		if( Math.abs(x1 - x2) < Math.abs(xFinal - x1))
		    xFinal = x2;
		xFinal = Math.max(xFinal, 0);
		xFinal = Math.min(xFinal, d.width);
		if( (x1-x2) * (x1 - xFinal) < 0)
		    xFinal = x1;
		t.distance = Math.abs((double) (x1 - xFinal) / (double) (x1 - x2)); 
	    }
	}
    }


    /**
     * makes a temp backup in case of modification(for undo)
     */
    private void backup() {
	backupDesktop = new Desktop(this);
    }


    /** 
     * handles modifications by backing up the desktop for undo
     */
    private void modify() {
	modified = true;
	undoDesktop = backupDesktop;
	if(undoItem != null)
	    undoItem.setLabel("Undo");
    }


  /**
   * Returns a vector of transitions in the list of transitions
   * which have the same from and to states with the given transition t,
   * but is different from it.
   */
  public Vector sameStatesTransition(Transition t)
  {
    Vector vect = new Vector();
    Transition tt;
    for(Enumeration e = theTransitions.elements(); e.hasMoreElements(); )
    {
       tt = (Transition) e.nextElement();
       if((tt.from == t.from) && (tt.to == t.to) && (tt != t))
          vect.addElement(tt);
    }
    return vect;
  }	// end of method sameStatesTransition


    /** 
     * Creates a list of all same sate transitions
     * @return a Vector containing all the transitions
     */
  public Vector makeLoopList() {
    
    Vector answer = new Vector();
    Transition t;

    for(Enumeration e = theTransitions.elements(); e.hasMoreElements(); ) {
      t = (Transition) e.nextElement();
      if(t.from == t.to)
        answer.addElement(t);
     }
    return answer;
  }
  

  /**
   * Sets the transition field of a given State to be the list
   * of transitions having that state as the from state.
   * @param s	the state.
   * @param tokenize	whether or not to tokenize a FSA label.
   */
  public void setTransitions(State s, boolean tokenize) {
    Transition t;
    StringTokenizer stk;
    String label;

    s.transitions.removeAllElements();
    for (Enumeration et = theTransitions.elements(); et.hasMoreElements(); ) {
      t = (Transition) et.nextElement();     
      if (t.from == s) {
        if (type == Machine.FSA && tokenize) {
          stk = new StringTokenizer(t.label, ",", false);
          while (stk.hasMoreTokens()) {
            label = stk.nextToken().trim();
            s.transitions.addElement(new Transition(s, t.to, label, fieldCounter, separator));
	  }
        } else
          s.transitions.addElement(t);
      }
    }
  }

  public void  paint(Graphics g) {
    
    Transition aTransition;

    Dimension	d = getSize();
    g.setColor(backcolor);
    g.fillRect(0, 0, d.width, d.height);

    g.setColor(Params._d_forecolor);
    g.draw3DRect(0, 0, d.width-1, d.height-1, true);

    for (Enumeration e = theTransitions.elements(); e.hasMoreElements();) {
      ((Transition) e.nextElement()).paintLine(g, selectedTransition);
    }
 
    // although it's very time-consuming to draw everything when dragging,
    // it seems the only reliable solution. For whatever reason,
    // setXORMode is not working properly.
    if (drag != null) {
      g.setColor(Params._t_selectedcolor);
      g.drawLine(firstState.p.x, firstState.p.y, drag.x, drag.y);
    }

    for (Enumeration e = theStates.elements(); e.hasMoreElements();)
    {
      ((State) e.nextElement()).paint(g, showDfaLabels || showStringLabel);
    }

    if (initialState != null) {
      setTransitions(initialState, false);
      for(Enumeration e = theTransitions.elements(); e.hasMoreElements();) {
	aTransition = (Transition) e.nextElement();
	if(aTransition.to == initialState) {
	  initialState.transitions.addElement(
	     new Transition(aTransition.to, aTransition.from, 1, new String[2]));
	}
      }
      initialState.paintInitial(g, this);
      setTransitions(initialState, true);
    }

    g.setFont(Params._t_font);
    for (Enumeration e = theTransitions.elements(); e.hasMoreElements();) {
      aTransition = (Transition) e.nextElement();
      aTransition.paintLabel(g, selectedTransition, locateLabel(aTransition));
    }

    //if labels are to be shown
    if(showStateLabels)
    {
      if(showDfaLabels)
      {
	 //show the DFA Labels
	 for (Enumeration e = theStates.elements(); e.hasMoreElements();)
	 {
	    ((State) e.nextElement()).paintDfaLabel(g, selectedState);
	 }
      }
      else if(showStringLabel)
      {
	 //show the regular grammar to FSA Labels
	 for (Enumeration e = theStates.elements(); e.hasMoreElements();)
	 {
	    ((State) e.nextElement()).paintStringLabel(g, selectedState);
	 }
      }
      else
      {
	 //show normal string labels
	 for (Enumeration e = theStates.elements(); e.hasMoreElements();)
	 {
	    ((State) e.nextElement()).paintNormalLabel(g, selectedState);
	 }
      }
    }

    if (selectedTransition != null)
      if (theTransitions.indexOf(selectedTransition) != -1)
        selectedTransition.paintLabel(g, selectedTransition, locateLabel(selectedTransition));

    if (menuOn)
      menu.paint(g);

  }	// end of method paint.


  public void update(Graphics g) {

    Dimension	d = getSize();

    if (offscr == null) {
      offscr = createImage(d.width, d.height);
      offg = offscr.getGraphics();
    }
    if (offscr.getWidth(this) != d.width || offscr.getHeight(this) != d.height) {
      offscr = createImage(d.width, d.height);
      offg = offscr.getGraphics();
    }

    if (offg == null) 
      paint(g);
    else {
      paint(offg);
      g.drawImage(offscr, 0, 0, null);
    }
  }	// end of method update.

  /**
   * Creates a new state and adds it to the list of states.
   */
  public State addState(int x, int y) {
    State s = new State(currentId++, false, x, y);
    theStates.addElement(s);
    return s;
  }

  /**
    * returns the State with the given id if there is one
    * else returns null.
    */
  public State getStateWithId(int idNum) {
    State aState;
    for(Enumeration e = theStates.elements(); e.hasMoreElements(); ) {
      aState = (State) e.nextElement();
      if(aState.id == idNum)
	return aState;
    }
    return null;
  }

  /**
   * Checks to see if the given position is in a state.
   * To speed it up, we check if the position is in the
   * rectangle surrounding the state's circle.
   * @return	the state found, or null, if none was found.
   */
  public State isInState(int x, int y) {
    State	s = null;
    boolean	found = false;
    Enumeration	e = theStates.elements();

    while ((e.hasMoreElements()) && (!found)) {
      s = (State) e.nextElement();
      if ((Math.abs(s.p.x - x) < Params._s_radius) && (Math.abs(s.p.y - y) < Params._s_radius))
        found = true;
    }
    if (found)
      return s;
    else
      return null;
  }	// end of method isInState.


    /** 
     * Checks to see if the given position is on a state arc thingy
     * @return the corresponding state found
     */
    
    public State isInLoopTop(int x, int y) {
	Enumeration e = theStates.elements();
	State s = null;
	int distance;

	while(e.hasMoreElements()) {
	    s = (State) e.nextElement();
	    distance =(int) Math.sqrt(Math.pow(x -s.p.x, 2) + Math.pow(y - (s.p.y -s.loopSize), 2));
	    if(distance <= 4) 
		return s;
	}
	return null;
    }

  /**
   * Creates a new transition and adds it to the list of transitions.
   */
  public Transition addTransition(State from, State to) {
    String label = "";
    Transition t = new Transition(from, to, label, fieldCounter, separator);

    //find the best spot
    Enumeration e;
    Transition tempTrans;
    Vector ratioList = new Vector();
    for(e = theTransitions.elements(); e.hasMoreElements(); ) {
	tempTrans = (Transition) e.nextElement();
	if(tempTrans.from == t.from && tempTrans.to == t.to)
	    ratioList.addElement(new Double(tempTrans.distance));
    }   
    VectorArray arr = new VectorArray(ratioList);
    Sorting.sort( arr, new DoubleSorter());

    ratioList = new Vector();
    ratioList.addElement(new Double(0));
    for (e = arr.elements(); e.hasMoreElements(); ) 
      ratioList.addElement( (Double) e.nextElement());
    ratioList.addElement(new Double(1));

    double bestSpot = (((Double) ratioList.elementAt(0)).doubleValue() + 
		       ((Double) ratioList.elementAt(1)).doubleValue()) / 2;
    double bestSize = ((Double) ratioList.elementAt(1)).doubleValue() - 
	((Double) ratioList.elementAt(0)).doubleValue();

    double prevVal;
    double val = 0;
    for(e = ratioList.elements(); e.hasMoreElements(); )
    {
        prevVal = val;
	val = ((Double) e.nextElement()).doubleValue();
	if(val - prevVal > bestSize)
        {
	    bestSize = val - prevVal;
	    bestSpot = (val+ prevVal) /2;
	}
    }
    t.distance = bestSpot;
    theTransitions.addElement(t);
    return t;
  }

    /**
     * Removes the given transition from the list of transitions.
   */
    public void removeTransition(Transition t) {
	Enumeration e;
	Transition tt;
	if (selectedTransition == t)
	    selectedTransition = null;
	theTransitions.removeElement(t);
	
	//check to fix the loopSize if this was the last same state transition
	if(t.from == t.to) {
	    for(e = theTransitions.elements(); e.hasMoreElements(); ) {
		tt = (Transition) e.nextElement();
		if(tt.from == tt.to && tt.from == t.from) {
		    return;
		}
	    }
	    t.from.loopSize = 0;
	}
    }
	
  /** 
    * Removes the given State from the Desktop
    */
  public void removeState(State s) {
    Transition tt;
    int i = 0;
    while (i < theTransitions.size()) {
      tt = (Transition) theTransitions.elementAt(i);
      if (tt.from == s || tt.to == s) 
	removeTransition(tt);
      else
	i++;
    }
    if (s == initialState)
      initialState = null;
    if(s == selectedState)
      selectedState = null;
    
    theStates.removeElement(s);
    
    if (autoRelabel)
      relabel();
  }
  
  /**
   * Returns the position of the label of the given transition.
   * The position is different if the state is selected or not. Always call this
   * function again if the state selection may have changed.
   */
  public Point locateLabel(Transition t) {
    FontMetrics	fm = getFontMetrics(Params._t_font);
    int x1 = t.from.p.x;
    int y1 = t.from.p.y;
    int x2 = t.to.p.x;
    int y2 = t.to.p.y;
    int x, y;

    if (t.from == t.to) {
	y2 = y1 - t.from.loopSize;
	y = (int) (y1 - t.distance*(t.from.loopSize) );
	y = Math.min(y, y1 - Params._t_distance);
	x = x1;
    } else {
	double len = Math.sqrt((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1));
	double d = t.distance;
	x = (int) (x1 - ((x1 - x2)*d));
	y = (int) (y1 - ((y1 - y2)*d));
	
	if (y1 > y2 || (y1 == y2 && x1 < x2)){
	    x -=  fm.stringWidth(t.label)+Transition.off+Transition.offr;
	    if(selectedTransition == t)
	    	x -= fm.stringWidth("_");
	}     
	if(x1 < x2 || (x1 == x2 && y1 < y2)) { 
	    y -= Params._t_height;
	}
    }
    
    return(new Point(x, y));
  }	// end of method locateLabel.

  /**
   * Checks to see if the given position is in a label.
   * @return	the transition found, or null if none was found.
   */
  public Transition isInTransition(int x, int y) {
    Transition	t = null;
    boolean	found = false;
    int		tx, ty;
    Point 	pl;
    FontMetrics	fm = getFontMetrics(Params._t_font);
    Vector	rt = new Vector(theTransitions.size());	// will keep trans. in reversed order.
    for (Enumeration e = theTransitions.elements(); e.hasMoreElements(); ) 
	rt.insertElementAt(e.nextElement(), 0);  
    Enumeration	e = rt.elements();
    while ((e.hasMoreElements()) && (!found)) {
      t = (Transition) e.nextElement();
      pl = locateLabel(t);
      tx = pl.x;
      ty = pl.y;
      if(selectedTransition != t) {
	  if (((x - tx) <= fm.stringWidth(t.label)+Transition.off+Transition.offr) && ((x - tx) >= 0) && ((y - ty) <= Params._t_height) && ((y - ty) >= 0))
	      found = true;
      }
      else
	  if (((x - tx) <= fm.stringWidth(t.label+"_")+Transition.off+Transition.offr) && ((x - tx) >= 0) && ((y - ty) <= Params._t_height) && ((y - ty) >= 0))
	      found = true;  
    }
    
    if (found)
      return t;
    else
      return null;
  }	// end of method isInTransition.

  /**
    * Checks if the given position is in a Dfa State label.
    * @return the corresponding State found, or null if none is found
    */
  public State isInStateDfaLabel(int x , int y) {
    State s = null;
   
    for(Enumeration e = theStates.elements(); e.hasMoreElements(); ) {
      s = (State) e.nextElement();
      if((x >= s.labelStart.x) && (x <= s.labelEnd.x) && 
	 (y >= s.labelStart.y) && (y <= s.labelEnd.y))
	return s;
    }
    return null;
  }

  /**
   * Checks to see if the given position is a good
   * location for a new state. Not implemented.
   */
   boolean isGoodLocation(int x, int y) {
    return true;
  }	// end of method isGoodLocation.

  /**
   * Changes the aspect of the desktop.
   * It becomes faded when fade is true, and unfaded when fade is false.
   */
  public void changeAspect(boolean fade) {
    State s;
    Transition t;

    if (fade) {			// upper window on; faded desktop
      selectedTransition = null;
      backcolor = Params._d_fadedbackcolor;
    } else {			// upper window closed; sharp desktop
      backcolor = Params._d_backcolor;
      for (Enumeration e = theStates.elements(); e.hasMoreElements(); ) {
        s = (State) e.nextElement();
        s.ss = State.NORMAL;
      }
      for (Enumeration e = theTransitions.elements(); e.hasMoreElements(); ) {
        t = (Transition) e.nextElement();
        t.st = Transition.NORMAL;
      }
    } 
    repaint();
  }  // end of method changeAspect
  
  /**
   * Relabels the states to have consecutive labels.
   */
  public void relabel() {
    int newid = 0;
    State s = null;
    for (Enumeration e = theStates.elements(); e.hasMoreElements(); ) {
      s = (State) e.nextElement();
      s.id = newid++;
    }
    currentId = newid;
  }	// end of method relabel.
   
  /**
   * Removes the highlights from all the states.
   */
  public void unfocusAll() {
    State	s = null;
    Transition  t = null;

    for (Enumeration e = theStates.elements(); e.hasMoreElements(); ) {
      s = (State) e.nextElement();
      s.ss = State.NORMAL;
    }

    for (Enumeration e = theTransitions.elements(); e.hasMoreElements(); ) 
    {
        t = (Transition) e.nextElement();
        t.st = Transition.NORMAL;
    }
  }


  public void setAllStateLists(Desktop d) {
    for (Enumeration e = theStates.elements(); e.hasMoreElements(); ) 
      ((State) e.nextElement()).labelToStateList(d);
  }


  /**
    * Unselects all transitions on the Desktop
    */
 public void unselectTransitions() {
    Transition aTransition;
    selectedTransition = null;
    for(Enumeration e = theTransitions.elements(); e.hasMoreElements(); ) {
      aTransition = (Transition) e.nextElement();
      aTransition.st = Transition.NORMAL;
    }
  }

  /**
   * Returns a string representing the tabular form of the current machine.
   * It is the only method we could find to print the machine on all platforms.
   */
  public String toTabular() {
  
    int		cols = theStates.size() + 1;
    int		rows = theTransitions.size() + theStates.size();
    String[][]	table = new String[rows][cols];
    String[]	header = new String[cols];
    int[]	colWidth = new int[cols];
    int		currentCol = 0;
    int		currentRow = 0;
    int		rowSpan = 0;
    State	s;
    Transition	t;
    String	answer = "";
    String	finalstates = "Final States: ";
    String	initialstate = "Start state: " 
    			+ ((initialState != null) ? "q" + initialState.id : "");
    if (theStates.size() == 0)
      return " ";
    
    for (int i = 0; i < cols; i++) {
      for (int j = 0; j < rows; j++)
        table[j][i] = EMPTY_STR;
      colWidth[i] = 0;
    }
    
    for (Enumeration e1 = theStates.elements(); e1.hasMoreElements(); ) {
      s = (State) e1.nextElement();
      if (s.isFinal)
        finalstates += " q" + s.id;
      table[currentRow][0] = "q" + s.id + "\t|";
      rowSpan = 1;
      setTransitions(s, false);
      for (Enumeration e2 = s.transitions.elements(); e2.hasMoreElements(); ) {
        t = (Transition) e2.nextElement();
        currentCol = theStates.indexOf(t.to) + 1;
        if (t.label.length() > colWidth[currentCol])
          colWidth[currentCol] = t.label.length();
        int i = 0;
        while (!table[currentRow + i][currentCol].equals(EMPTY_STR)) {
          i++;
          table[currentRow + i][0] = "\t|";
        }
        table[currentRow + i][currentCol] = t.label.trim();
        if (i + 1 > rowSpan)
          rowSpan = i + 1;
      }
      currentRow += rowSpan;
    }
    rows = currentRow;
    
    String str;
    int totalWidth = 0;
    answer = "";
    answer += initialstate + "\n";
    answer += finalstates + "\n";
    answer += "Transition function: " + "\n";
    answer += "\n\t ";
    for (Enumeration e1 = theStates.elements(); e1.hasMoreElements(); ) {
      s = (State) e1.nextElement();
      str = "q" + s.id;
      currentCol = theStates.indexOf(s) + 1;
      header[currentCol] = " " + toLength(str, colWidth[currentCol])+ " ";
      answer += header[currentCol];
      totalWidth += Math.max(colWidth[currentCol], 3) + 2;
    }
    answer += "\n";
    answer += "\t-";
    for (int i = 0; i < totalWidth; i++) 
      answer += "-";
    answer += "\n";
    for (int i = 0; i < rows; i++) {
      if (!table[i][0].equals("\t|") && (i > 0)) {
        answer += "\t|";
        for (int ii = 0; ii < totalWidth; ii++) 
          answer += "-";
        answer += "\n";
      }
      answer += " " + table[i][0];
      for (int j = 1; j < cols; j++) {
        table[i][j] = " " + toLength(table[i][j], colWidth[j]) + "|";
        answer += table[i][j];
      }
      answer += "\n";
    }
    answer += "\t-";
    for (int i = 0; i < totalWidth; i++) 
      answer += "-";
    answer += "\n";
    return answer;
  }	// end of method toTabular.
  
  /**
   * Makes the String str have length length by adding white spaces.
   * Used in method toTabular.
   */
  protected String toLength(String str, int length) {
    String	answer = new String(str);
    int		actuall = Math.max(3, length);
    
    if (answer.equals(EMPTY_STR))
      answer = "-";
    int l = answer.length();
    for (int i = l; i < actuall; i++) 
      answer += " ";
    return answer;
  }

  /** sets the checkMarks on all the States on this Desktop to false  */
  public void unmarkAllStates() {
    State aState;

    for( Enumeration e = theStates.elements(); e.hasMoreElements(); ) {
      aState = (State) e.nextElement();
      aState.checkMark = 0;
    }
  }

//*************** functions for placing the nodes when solving the DFA ************************

  /** calculates how many Transitions intersect transitions or states on the Desktop */  
  private int findIntersections(State aState, Vector placedStates) {
    int total = 0;
    Enumeration e, e2, e3;
    Transition aTransition, aTransition2;
    Point [] points = new Point[5];
    State aState2;
    int i;
    Point p1, p2;

    placedStates.addElement(aState);
    
    for(e = theTransitions.elements(); e.hasMoreElements(); ) {
      aTransition = (Transition) e.nextElement();
      if(aTransition.from == aTransition.to) {
	p1 = new Point(aTransition.from.p);
	p1.y -= aTransition.distance*aTransition.from.loopSize; 
      }
      else p1 = new Point(aTransition.to.p);
      
      if(placedStates.contains(aTransition.to) && placedStates.contains(aTransition.from)) {
	for(e2 = theTransitions.elements(); e2.hasMoreElements(); ) {
	  aTransition2 = (Transition) e2.nextElement();
	  if(placedStates.contains(aTransition2.to) && placedStates.contains(aTransition.from)) {
	    
	    if(aTransition2.from == aTransition2.to) {
	      p2 = new Point(aTransition2.from.p);
	      p2.y -= aTransition2.distance; 
	    }
	    else p2 = new Point(aTransition2.to.p);
	    
	    // same state transitions going off the top of the screen are bad
	    if(p1.y < 0 || p2.y <0)
	      total++;

	    if(intersect(aTransition.from.p, p1, aTransition2.from.p, p2))
	       total++;
	  }
	}
	for( e3 = placedStates.elements(); e3.hasMoreElements(); ) {
	  aState2 = (State) e3.nextElement();
	  points[0] = new Point(aState2.p);
	  points[0].x -= Params._s_radius;
	  points[0].y -=  Params._s_radius;
	  points[1] = new Point(points[0]);
	  points[1].x += 2* Params._s_radius;
	  points[2] = new Point(points[0]);
	  points[2].y += 2* Params._s_radius;
	  points[3] = new Point(points[2]);
	  points[3].x += 2*  Params._s_radius;
	  points[4] = new Point(points[0]);
	  for(i=0; i<4; i++) {
	    if(intersect(aTransition.from.p, p1, points[i], points[i+1])) {
	      total+=2;
	      break;
	    }
	  }
	}
      }
    }
    placedStates.removeElement(aState);
    return total;
  }


  /** cool function from Sedgewicks book to figure things about a line's orientation. 
    * Useful for Intersect.*/
  private int ccw(Point p0, Point p1, Point p2) {
    int dx1, dx2, dy1, dy2;
    int ccw = 0;
    dx1 = p1.x - p0.x;
    dy1 = p1.y - p0.y;
    dx2 = p2.x - p0.x;
    dy2 = p2.y - p0.y;

    if(dx1*dy2 > dy1 * dx2) 
      ccw = 1;
    if(dx1*dy2 < dy1 * dx2)
      ccw = -1;
    if(dx1*dy2 == dy1*dx2) {
      if((dx1*dx2 < 0) || (dy1*dy2<0))
	ccw = -1;
      else if ((dx1*dx1+dy1+dy1) >= (dx2*dx2+dy2*dy2))
	ccw = 0;
      else
	ccw = 1;
    }
    return ccw;
  }

  /** checks if two line segments intersect */
  private boolean intersect(Point p1, Point p2, Point q1, Point q2) {
    return ((ccw(p1, p2, q1) * ccw(p1, p2, q2)) <= 0) && 
      ((ccw(q1, q2, p1)*ccw(q1, q2, p2)) <=0);
  }

  /** tries to find a good position for the parameter State by trying a few random positions
    * and keeping the best one.     */
  public void placeState(State aState, Vector placedStates) {
    Point bestPoint = new Point(-1, -1);
    int bestTotal = 1000;
    int total= 0;
    int counter = 0;
    Enumeration e;
    Transition aTransition;
    State neighbour;
    int distancex, distancey;
    boolean found = false;
    Dimension	dim = getSize();
    

    //give it ten tries and keep the best
    for (int i=0; i<10; i++) {
      for(e = theTransitions.elements(); e.hasMoreElements(); ) {
	aTransition = (Transition) e.nextElement();
	if(aTransition.from == aState && placedStates.contains(aTransition.to))
	  neighbour = aTransition.to;
	else if(aTransition.to == aState && placedStates.contains(aTransition.from))
	  neighbour = aTransition.from;
	else 
	  continue;
	if(counter != i) {
	  counter++;
	  continue; 
	}
	distancex = (int) ((Math.random() - .5) * 200.0);	
	distancey = (int) ((Math.random() - .5) * 160.0);
	
	if(distancex <= 0) 
	  distancex -= 2* Params._s_radius;
	else distancex += 2* Params._s_radius;
	if(distancey <= 0) 
	  distancey -= 2* Params._s_radius;
	else distancey += 2* Params._s_radius;	

	if(Math.random() > .50) {
	  distancex = 0;
	  distancey *= 2;
	} else if(Math.random() < .25) {
	  distancey = 0;
	  distancex *= 2;
	}
	aState.p.x = neighbour.p.x + distancex;
	aState.p.y = neighbour.p.y + distancey;
	findProperPosition(aState, placedStates);
	total = findIntersections(aState, placedStates);

	if(total < bestTotal) {
	  bestPoint = new Point(aState.p);
	  bestTotal = total;
	}
	found = true;
	break;
      }
      if(found == false) {
	// if all else fails go random
	aState.p.x = (int) (Math.random() * dim.width);	
	aState.p.y = (int) (Math.random()* dim.height);
	findProperPosition(aState, placedStates);
	total = findIntersections(aState, placedStates);

	if(total < bestTotal) {
	  bestPoint = new Point(aState.p);
	  bestTotal = total;
	}
      }
      found = false;
      counter = 0;
    }
    aState.p = new Point(bestPoint);
    for(e = theTransitions.elements(); e.hasMoreElements(); ) {
	aTransition = (Transition) e.nextElement();
	if(aTransition.from == aTransition.to && aTransition.from == aState)
		    aState.loopSize += Params._t_distance;	    
    }
    



  }

  /** makes sure the State isn't overlapping another state or is placed off the screen */
  private void findProperPosition(State aState, Vector placedStates) {
    Point pos = aState.p;
    Dimension dim = getSize();
    State tempState;
    boolean okay = false;
    int count = 0;

    while (okay == false) {
      
      if(pos.x <= Params._s_radius)
	pos.x = 3 *  Params._s_radius;
      else if(pos.y <= Params._s_radius)
	pos.y = 3 *  Params._s_radius ;
      else if(pos.x >= dim.width - Params._s_radius)
	pos.x = dim.width - (2* Params._s_radius);
      else if(pos.y >= dim.height - Params._s_radius)
	pos.y = dim.height - (2* Params._s_radius);  
      else okay = true;
      
      if(count++ == 50)
	return;
  
      for(Enumeration e = placedStates.elements(); e.hasMoreElements(); ) {
	tempState = (State) e.nextElement();
	if(( Math.abs(tempState.p.y - aState.p.y) <= (Params._s_radius*2)) && 
	   ( Math.abs(tempState.p.x - aState.p.x) <= (Params._s_radius*2))) {
	  aState.p.x += 5* Params._s_radius;
	  aState.p.y += 5* Params._s_radius;
	  okay = false;
	}
      }
    }
  }



}

    
 


