/*
 *  A small test applet for the QAP.
 *
 *  Author: Jeff Linderoth
 *  
 */

import java.awt.*;
import java.awt.event.*;
import java.applet.*;
import java.applet.AudioClip;

/*
 *  Things to do:
 *
 */

public class QAPSolver extends java.applet.Applet
{

    AudioClip audio;

  String alphabet[] = {"A", "B", "C", "D", "E", "F", "G", "H", "I" };

  final int scaleFactor = 100;

  public class BadPermException extends Exception
  {
    public BadPermException() {}
  };

  /** This class holds information about the QAP.
   
    It holds the potential facility locations, and the required 
    flows between all facilities.
    */    

	
  public class QAP
  {

    int nFac;

    Point locations[];
    Point graphicsLocations[];

    int flows[][];
    
    /// This holds the current permutation
    int solution[];

    /// This will hold the "reverse" permutation
    int revsolution[];

      /// This will hold the optimal solution.
      int optimalsolution[];

      /// This holds the best solution value (for size 6 and 7 instances)
      int optimalSolutionVal;

      String bestNames [];
    public QAP( int instancesize )
    {
      if( instancesize == 4 )
	{
	  // The optimal solution for this problem is 395
	  // Permutation is 3-4-1-2

	    // Don't put it in for these!
	    optimalSolutionVal = 395;
	  nFac = 4;
	  locations = new Point [nFac];

	  locations[0] = new Point( 55, 20 );
	  locations[1] = new Point( 75, 30 );
	  locations[2] = new Point( 75, 70 );
	  locations[3] = new Point( 20, 60 );
	  
	  flows = new int [nFac][nFac];
	  flows[0][1] = 3;
	  flows[0][3] = 2;
	  flows[1][3] = 1;
	  flows[2][3] = 4;

	  optimalsolution = new int [nFac];
	  optimalsolution[0] = 2;
	  optimalsolution[1] = 3;
	  optimalsolution[2] = 0;
	  optimalsolution[3] = 1;

	}
      else if( instancesize == 5 )
	{
	  // The optimal solution for this problem is 314
	  //  Permutation is 3-4-5-2-1

	    optimalSolutionVal = 314;
	  nFac = 5;
	  locations = new Point [nFac];

	  // These types are only arrays of references -- you need to
	  //  explicitly initialize the member of the array
	  locations[0] = new Point( 20, 10 );
	  locations[1] = new Point( 30, 60 );
	  locations[2] = new Point( 50, 50 );
	  locations[3] = new Point( 70, 90 );      
	  locations[4] = new Point( 60, 40 );

	  flows = new int [nFac][nFac];
	  
	  flows[0][2] = 2;
	  flows[0][4] = 3;
	  flows[3][4] = 1;
	  flows[1][3] = 3;

	  optimalsolution = new int[nFac];
	  optimalsolution[0] = 1;
	  optimalsolution[1] = 3;
	  optimalsolution[2] = 4;
	  optimalsolution[3] = 2;
	  optimalsolution[4] = 0;

	}
      else if( instancesize == 6 )
	{
	    /* Solution is 5-2-6-1-4-3.  Value: 313 */
	    optimalSolutionVal = 313;
	    nFac = 6;
	    locations = new Point [nFac];

	    locations[0] = new Point( 20, 20 );
	    locations[1] = new Point( 60, 20 );
	    locations[2] = new Point( 70, 60 );
	    locations[3] = new Point( 50, 40 );
	    locations[4] = new Point( 30, 40 );
	    locations[5] = new Point( 20, 80 );

	    flows = new int [nFac][nFac];

	    flows[0][1] = 1;
	    flows[0][2] = 1;
	    flows[0][3] = 2;
	    flows[1][5] = 2;
	    flows[2][5] = 1;
	    flows[3][4] = 3;
	}
      else if( instancesize== 7 )
	  {
	/* 5-4-7-1-2-3-6 */
	      optimalSolutionVal = 470;
	      nFac = 7;
	      locations = new Point [nFac];
	      locations[0] = new Point( 15, 15 );
	      locations[1] = new Point( 50, 15 );
	      locations[2] = new Point( 80, 45 );
	      locations[3] = new Point( 80, 90 );
	      locations[4] = new Point( 45, 80 );
	      locations[5] = new Point( 15, 90 );
	      locations[6] = new Point( 25, 55 );

	      flows = new int [nFac][nFac];
	      flows[0][1] = 2;
	      flows[1][5] = 1;
	      flows[2][5] = 1;
	      flows[3][4] = 3;
	      flows[3][6] = 1;	      
	      flows[1][2] = 3;
	      flows[0][6] = 2;
	  }
      else if( instancesize== 8 )
	  {
	      optimalSolutionVal = 904;
	      nFac = 8;
	      locations = new Point [nFac];
	      locations[0] = new Point( 18, 15 );
	      locations[1] = new Point( 50, 15 );
	      locations[2] = new Point( 80, 45 );
	      locations[3] = new Point( 80, 90 );
	      locations[4] = new Point( 78, 60 );
	      locations[5] = new Point( 45, 80 );
	      locations[6] = new Point( 15, 90 );
	      locations[7] = new Point( 25, 55 );

	      flows = new int [nFac][nFac];
	      flows[0][1] = 2;
	      flows[1][5] = 1;
	      flows[2][5] = 1;
	      flows[3][4] = 3;
	      flows[1][3] = 1;
	      flows[3][6] = 1;	      
	      flows[1][2] = 3;
	      flows[0][6] = 2;
	      flows[3][7] = 1;
	      flows[6][7] = 4;
	      flows[0][2] = 4;
	      flows[3][7] = 5;
	  }
      else if( instancesize== 9 )
	  {
	      optimalSolutionVal = 1160;
	      nFac = 9;
	      locations = new Point [nFac];
	      locations[0] = new Point( 18, 15 );
	      locations[1] = new Point( 50, 15 );
	      locations[2] = new Point( 80, 45 );
	      locations[3] = new Point( 80, 90 );
	      locations[4] = new Point( 78, 60 );
	      locations[5] = new Point( 45, 80 );
	      locations[6] = new Point( 15, 90 );
	      locations[7] = new Point( 25, 55 );
	locations[8] = new Point( 30, 36 );

	      flows = new int [nFac][nFac];
	      flows[0][1] = 2;
	      flows[1][5] = 6;
	      flows[2][5] = 3;
	      flows[3][4] = 1;
	      flows[1][3] = 1;
	      flows[3][6] = 1;	      
	      flows[1][2] = 3;
	      flows[0][6] = 2;
	      flows[3][7] = 5;
	      flows[6][7] = 4;
	      flows[0][2] = 4;
	      flows[3][7] = 2;
	flows[1][8] = 2;
	flows[5][8] = 2;
	flows[6][8] = 3;
	  }
      else
	  {
	      System.out.println( "Bad Parameter to Applet" );	      
	  }

      graphicsLocations = new Point [nFac];
      for( int i = 0; i < nFac; i++ )
	{
	  // These are initialized by drawCircles() routine
	  graphicsLocations[i] = new Point( 0, 0 );
	}

      solution = new int [nFac];
      revsolution = new int [nFac];
      for( int i = 0; i < nFac; i++ )
	{
	  solution[i] = i;
	  revsolution[i] = i;
	}
    }

    public int computeVal() throws BadPermException
    {
      // Check for validity of the permutation
      for( int i = 0; i < nFac; i++ )
	{
	  if( solution[i] < 0 || solution[i] >= nFac )
	    {
	      BadPermException e = new BadPermException();
	      throw e;
	    }
	}
      
      for( int i = 0; i < nFac; i++ )
	{
	  revsolution[i] = -1;
	}

      // Setup the "reverse" solution.
      for( int i = 0; i < nFac; i++ )
	{
	  revsolution[solution[i]] = i;
	}
	  
      for( int i = 0; i < nFac; i++ )
	{
	  if( revsolution[i] == -1 )
	    {
	      BadPermException e = new BadPermException();
	      throw e;	      
	    }
	}
      int retval = 0;
      for( int i = 0; i < nFac; i++ )
	{
	  for( int j = i; j < nFac; j++ )
	    {
	      if( flows[i][j] > 0 )
		{
		    Point p1 = locations[revsolution[i]];
		    Point p2 = locations[revsolution[j]];
		  
		  int dist = (int) Math.sqrt( (p1.x - p2.x) * (p1.x - p2.x) + 
					      (p1.y - p2.y) * (p1.y - p2.y) );

		  //System.out.println( "i: " + String.valueOf( i ) + " j: " + String.valueOf( j ) + " dist: " + String.valueOf( dist ) );

		  retval += flows[i][j] * dist;
		}
	    }	    	    
	}
      if( retval <= optimalSolutionVal )
	  {
	      System.out.println( "OPTIMAL!" );
	      audio.play();

	  }
      return retval;
    }

    public void writeQAP()
    {
      System.out.println( String.valueOf( nFac ) );
      System.out.println();

      for( int i = 0; i < nFac; i++ )
	{
	  for( int j = 0; j < nFac; j++ )
	    {
	      int temp;
	      if( i > j )
		{
		  temp = flows[j][i];
		}
	      else
		{
		  temp = flows[i][j];
		}
	      System.out.print( String.valueOf( temp ) + " " );
	    }
	  System.out.println();      
	}
      System.out.println();      

      for( int i = 0; i < nFac; i++ )
	{
	  for( int j = 0; j < nFac; j++ )
	    {
		  Point p1 = locations[i];
		  Point p2 = locations[j];
		  
		  int dist = (int) Math.sqrt( (p1.x - p2.x) * (p1.x - p2.x) + 
					      (p1.y - p2.y) * (p1.y - p2.y) );

		  System.out.print( String.valueOf( dist ) + " " );
	    }
	  System.out.println();
	}

      System.out.println();

    }

  }


  /// This is the class that draws the middle
  public class QAPCanvas extends Canvas
  {
        
    public void paint( Graphics g )
    {

      Font font = new Font( "TimesRoman", Font.PLAIN, 18 ); 
      g.setFont( font );

      drawCircles( g, qap );
      drawSolution( g, qap );
    }

    public void drawCircles( Graphics g, QAP qap )
    {
      Dimension currentSize = getSize();

      int xUnitSize = currentSize.width / scaleFactor;
      int yUnitSize = currentSize.height / scaleFactor;

      for( int i = 0; i < qap.nFac; i++ )
	{	
	  int x = xUnitSize * qap.locations[i].x;
	  int y = yUnitSize * qap.locations[i].y;

	  qap.graphicsLocations[i].x = x;
	  qap.graphicsLocations[i].y = y;
	  
	  g.fillOval( x-10, y-10, 20, 20 );
	  g.drawString( alphabet[i], x+2, y+25 );
	}
    }

    public void drawSolution( Graphics g, QAP qap )
    {

      for( int i = 0; i < qap.nFac; i++ )
	{
	  for( int j = i; j < qap.nFac; j++ )
	    {

	      if( qap.flows[i][j] > 0 )
		{

		  int II = qap.revsolution[i];
		  int JJ = qap.revsolution[j];

		  int xcoors[] = new int [4];
		  int ycoors[] = new int [4];

		  // Figure angle between locations of II and JJ
		  int x1 = qap.graphicsLocations[II].x;
		  int x2 = qap.graphicsLocations[JJ].x;
		  int y1 = qap.graphicsLocations[II].y;
		  int y2 = qap.graphicsLocations[JJ].y;

		  double costheta = (x2-x1) / Math.sqrt( (x2-x1)*(x2-x1) + (y2-y1)*(y2-y1) );
		  double sintheta = (y2-y1) / Math.sqrt( (x2-x1)*(x2-x1) + (y2-y1)*(y2-y1) );

		  //System.out.println( "Angle between " + alphabet[II] + " and " + alphabet[JJ] + " is " + String.valueOf( 180 * Math.acos( costheta ) / Math.PI ) );

		  int dx = (int) Math.round( 1.0 * qap.flows[i][j] * sintheta );
		  int dy = (int) Math.round( 1.0 * qap.flows[i][j] * costheta );

		  //System.out.println( "dx = " + dx );
		  //System.out.println( "dy = " + dy );

		  xcoors[0] = x1-dx;
		  xcoors[1] = x2-dx;
		  xcoors[2] = x2+dx;
		  xcoors[3] = x1+dx;

		  ycoors[0] = y1+dy;
		  ycoors[1] = y2+dy;
		  ycoors[2] = y2-dy;
		  ycoors[3] = y1-dy;

		  /*
		  for( int k = 0; k < 4; k++ )
		    {
		      System.out.println( " Point " + String.valueOf( k ) + ": ( " +
					  String.valueOf( xcoors[k] ) + ", " +
					  String.valueOf( ycoors[k] ) + " )" );
					  
					}
		    */
		  Polygon linePolygon = new Polygon( xcoors, ycoors, 4 );
		  g.fillPolygon( linePolygon );
		}
	    }
	}

      Dimension currentSize = getSize();

      for( int i = 0; i < qap.nFac; i++ )
	{	
	  int II = qap.solution[i];
	  
	  g.setColor( Color.red );
	  g.drawString( String.valueOf( II + 1 ), qap.graphicsLocations[i].x - 22, 
			qap.graphicsLocations[i].y -10 );
	}

      
    }

    public Dimension getMinimumSize()
    {
      return new Dimension( 250, 250 );
    }

    public Dimension getPreferredSize()
    {
      return new Dimension( 400, 400 );
    }

  }

  
  /// This is for the bottom panel.
  public class QAPSolInfo extends Canvas
  {
    
    public void paint( Graphics g )
    {
      Dimension currentSize = getSize();
      
      Font font = new Font( "TimesRoman", Font.PLAIN, 18 ); 
      g.setFont( font ); 
      g.drawString( "Current solution value: ", 15, 10 ); 
      g.drawString( answerStr, 35, 30 ); 

    }

   public Dimension getMinimumSize()
    {
      return new Dimension( 100, 45 );
    }

    public Dimension getPreferredSize()
    {
      return new Dimension( 500, 45 );
    }

  }


    public class EastPanel extends Panel
    {
	public Dimension getPreferredSize()
	{
	    return new Dimension( 100, 400 );
	}
	
	public Dimension getMinimumSize()
	{
	    return new Dimension( 100, 200 );
	}
    }


  /// This variable holds the "answer" to the current permutation.
  String answerStr;

  /// Text fields for the different facilities
  TextField [] fac;

  QAPSolInfo solinfo;
  QAPCanvas display;
  QAP qap;
    
  // This is called at the very beginning by an Applet.
  public void init()
  {

    int instancesize = Integer.parseInt( getParameter( "Size" ) );

    // A am going to use a BorderLayout.
    setLayout( new BorderLayout() );

    //audio = getAudioClip( getDocumentBase(), "brain.au" );
    //audio = getAudioClip( getDocumentBase(), "not_worthy.au" );
    //audio = getAudioClip( getDocumentBase(), "yousaidit.au" );
    audio = getAudioClip( getDocumentBase(), "excellent.au" );
    
    qap = new QAP( instancesize );
    qap.writeQAP();
    int ia = -1;
    try
      {
	ia = qap.computeVal();
      }
    catch ( BadPermException e ) {}
    answerStr = String.valueOf( ia );
    
    ///  Create the top panel.
    Panel topPanel = new Panel();

    fac = new TextField[qap.nFac];
    for( int i = 0; i < qap.nFac; i++ )
      {
	topPanel.add( new Label( alphabet[i], Label.RIGHT ) );
	fac[i] = new TextField( String.valueOf( i+1 ), 2 );
	topPanel.add( fac[i] );
      }

    Button compute = new Button( "Compute" );
    topPanel.add( compute );

    Button reset = new Button( "Reset" );
    topPanel.add( reset );

    add( topPanel, BorderLayout.NORTH );

    // Create a solution info class for the bottom 
    solinfo = new QAPSolInfo();   
    add( solinfo, BorderLayout.SOUTH );

    // Put the picture in the middle...
    display = new QAPCanvas();
    add( "Center", display );

    // Add a listener for the button
    ActionListener computeListener = new ActionListener() {
      public void actionPerformed( ActionEvent evt )
	{

	  boolean validPerm = true;

	  try 
	    {
	      for( int i = 0; i < qap.nFac; i++ )
		{
		  qap.solution[i] = Integer.parseInt( fac[i].getText() ) - 1;
		}
	    }
	  catch ( NumberFormatException e )
	    {
	      System.out.println( "Invalid Permutation!" );
	      answerStr = "Invalid Permutation!";
	      validPerm = false;
	    }

	  if( validPerm )
	    {
	  
	      try
		{
		  int answer = qap.computeVal();
		  answerStr = String.valueOf( answer );
		  if( answer <= qap.optimalSolutionVal )
			{
			answerStr = answerStr + " -- Optimal!!!";
			}
		}
	      catch( BadPermException e )
		{
		  System.out.println( "Invalid Permutation!" );
		  answerStr = "Invalid Permutation!";
		  validPerm = false;
		}
	  
	      if( validPerm )
		{		  
		  display.repaint();	  
		}
	    }
	  solinfo.repaint();	  
	}
    };

    // Register the listener with your button
    compute.addActionListener( computeListener );

    ActionListener resetListener = new ActionListener() {
	public void actionPerformed( ActionEvent evt )
	{	    
	    for( int i = 0; i < qap.nFac; i++ )
	    {
		fac[i].setText( String.valueOf( i + 1 ) );
		qap.solution[i] = i;
	    }
	    int ria = -1;
	    try
	    {
		ria = qap.computeVal();
	    }
	    catch ( BadPermException e ) {}
	    answerStr = String.valueOf( ria );

	    display.repaint();
	    solinfo.repaint();
	}
    };

    reset.addActionListener( resetListener );


    // Create some stuff for the East.
    
    EastPanel eastPanel = new EastPanel();

    eastPanel.add( new Label("Flows") );
    
    for( int i = 0; i< qap.nFac; i++ )
	{
	    for( int j = 0;j < qap.nFac; j++ )
		{
		    if( qap.flows[i][j] > 0 )
			{
			    String s = "Flow(" + String.valueOf( i + 1 )
				+ ", " + String.valueOf( j + 1 )
				+ ") = " + String.valueOf( qap.flows[i][j] );
								
			    eastPanel.add( new Label( s ) );
			}
		}
	}

    if( qap.nFac == 4 || qap.nFac == 5 )
      {
	  Button optimal = new Button("Show Optimal");
	eastPanel.add( optimal );

	add( eastPanel, BorderLayout.EAST );

	// Add an action listener for the optimal button

	ActionListener optimalListener = new ActionListener() {
	    public void actionPerformed( ActionEvent evt )
	    {	    
		for( int i = 0; i < qap.nFac; i++ )
		{
		    fac[i].setText( String.valueOf( qap.optimalsolution[i] + 1 ) );
		    qap.solution[i] = qap.optimalsolution[i];
		}
		int ria = -1;
		try
		{
		    ria = qap.computeVal();
		}
		catch ( BadPermException e ) {}
		answerStr = String.valueOf( ria );

		display.repaint();
		solinfo.repaint();
	    }
	};

	optimal.addActionListener( optimalListener );
      }
    else if( qap.nFac == 6 || qap.nFac == 7 || qap.nFac == 8 || qap.nFac == 9 )
      {
	  /*
	  Button showbest = new Button( "Show Low Scores" );
	eastPanel.add( showbest );
	  */

	add( eastPanel, BorderLayout.EAST );

	// Add action listener and show low score abilitty
      }
    
    //XXX Do you need this?
    repaint();

  }
  

}