/**
 * @(#)ShortPathFrame.java
 *
 * Calculates shortest path for e.g. paraglider competitions
 *
 * @author K. Rege
 * @version 1.00 2015/12/2
 */

import java.awt.event.*;
import javax.swing.*;
import java.util.*;
import java.awt.Dimension;
import java.awt.FlowLayout;
import java.awt.BorderLayout;
import java.awt.Graphics;
import java.awt.Color;
import java.awt.Color;

class Circle {
	Circle(double cX, double cY, double r, double phi1, double phi2) {
		centerX = cX;
		centerY = cY;
		this.r = r;
		this.phi1 = phi1;
		this.phi2 = phi2;
	}
	double centerX, centerY;
	double r;
	double phi1, phi2;
}


class Point {
	Point(double x, double y) {
		this.x = x;
		this.y = y;
	}
	double x, y;
}

public class ShortPathFrame extends JFrame implements Runnable, ActionListener {
	List<Circle> circles = new ArrayList<Circle>();
	List<Point> path = new ArrayList<Point>(); // path
	JCheckBox cb;
	double pathLength;
	int count;
    
	double temperature;
	double coolingRate;
	double deltaPhi;
    
    // initializes the values and start the thread
	void startSimulAneal() {
		temperature = 1;
		coolingRate = 0.9995;
		deltaPhi = 0.05; 
		init();
		Thread s = new Thread(this);
		s.start();	
	}
	
    // does the simul annealing in a thread
	public void run() {
		try {
			double origDistance = pathLength;
			double deltaDistance = 0;
			int acceptBoltzCount = 0;
			int acceptCount = 0;
			while (true) {
				
				// calculate new arrangement
				List<Circle> nextArrangement = copyCircles();
				for (Circle c : nextArrangement) {
					double dp = deltaPhi / 2 - Math.random() * deltaPhi;
					c.phi1 += dp;
					dp = deltaPhi / 2 - Math.random() * deltaPhi;
					c.phi2 += dp;
				}
				List<Point> nextPath = calcPath(nextArrangement);
				double nextPathLength = pathLength(nextPath);
				
				// skale delta dist so that initial boltz is ~0.5 
				deltaDistance = (nextPathLength - pathLength) / origDistance * 10;
				// if the new order has a smaller distance
				// or if the new order has a larger distance but 
				// satisfies Boltzman condition then accept the arrangement
				double boltz = Math.exp(-deltaDistance / temperature);
				if (deltaDistance < 0
						|| (deltaDistance > 0 && boltz > Math.random())) {
					acceptCount++;
					if (deltaDistance > 0) {
						acceptBoltzCount++;
					} 
					circles = nextArrangement;
					path = nextPath;
					pathLength = nextPathLength;
				}
				count++;
				if (count % 1000 == 0) {
					if (cb.isSelected()) {
						System.out.println(
								"Accept Count:" + acceptCount
								+ "  Boltz Accept Count:" + acceptBoltzCount);
						this.repaint();
						Thread.sleep(100);
					}
					if (acceptCount == 0) {
						this.repaint();
						break;
					}
					acceptBoltzCount = 0;
					acceptCount = 0;
				}
				// cool down the temperature
				temperature *= coolingRate;
			}
		} catch (Exception e) {
			e.printStackTrace();	
		}
	}

	List<Circle> copyCircles() {
		List<Circle> copy = new ArrayList<Circle>(circles.size());
		for (Circle c : circles) {
			copy.add(copy.size(),
					new Circle(c.centerX, c.centerY, c.r, c.phi1, c.phi2));
		}
		return copy;
	}    
    
	double pathLength(List<Point> path) {
		double pathLength = 0;
		for (int i = 0; i < path.size() - 1; i++) {
			double dx = path.get(i).x - path.get(i + 1).x;
			double dy = path.get(i).y - path.get(i + 1).y;
			pathLength += Math.sqrt(dx * dx + dy * dy);
		} 	
		return pathLength;
	}
    
	List<Point> calcPath(List<Circle> circles) {
		List<Point> path = new ArrayList<Point>();
		path.add(new Point(20, 100)); // start;
		for (Circle c : circles) {
			path.add(
					new Point(c.centerX + c.r * Math.cos(c.phi1),
					c.centerY + c.r * Math.sin(c.phi1)));
			path.add(
					new Point(c.centerX + c.r * Math.cos(c.phi2),
					c.centerY + c.r * Math.sin(c.phi2)));
    		
		}
		path.add(new Point(20, 300)); // end;
		return path;
	}
    
	void init() {
		circles.clear();
		count = 0;
		circles.add(new Circle(100, 100, 50, 0, Math.PI / 2));
		circles.add(new Circle(250, 70, 50, 0, Math.PI));
		circles.add(new Circle(380, 160, 30, 0, Math.PI * 3 / 2));
		
				circles.add(new Circle(380, 260, 30, 0, Math.PI * 3 / 2));
				
		circles.add(new Circle(150, 200, 50, 0, Math.PI * 3 / 2));
		path = calcPath(circles);
		pathLength = pathLength(path);
	}

	/**
	 * The constructor
	 */  
	public ShortPathFrame() {
                
		JMenuBar menuBar = new JMenuBar();
		JMenu menuFile = new JMenu();
		JMenuItem menuFileExit = new JMenuItem();
        
		menuFile.setText("File");
		menuFileExit.setText("Exit");
        
		// Add action listener.for the menu button
		menuFileExit.addActionListener(new ActionListener() {
			public void actionPerformed(ActionEvent e) {
				ShortPathFrame.this.windowClosed();
			}
		}); 
		menuFile.add(menuFileExit);
		menuBar.add(menuFile);
        
		setTitle("ShortPath");
		setJMenuBar(menuBar);
		setSize(new Dimension(400, 400));
        
		// Add window listener.
		this.addWindowListener(new WindowAdapter() {
			public void windowClosing(WindowEvent e) {
				ShortPathFrame.this.windowClosed();
			}
		});  
		JPanel jp = new JPanel(new FlowLayout(FlowLayout.LEFT));
		JButton but = new JButton("start");
		but.addActionListener(this);
		jp.add(but);
		cb = new JCheckBox("animate");
		jp.add(cb);
		add(BorderLayout.PAGE_START, jp);
		initCanvas();
		init();
	}
    
	public void actionPerformed(ActionEvent e) {
		startSimulAneal();
	}
    
	/**
	 * Shutdown procedure when run as an application.
	 */
	protected void windowClosed() {
    	
		// TODO: Check if it is safe to close the application
    	
		// Exit application.
		System.exit(0);
	}

	void initCanvas() {
		this.add(
				new JPanel() {
			@Override
			public void paint(Graphics g) {
				// super.paint(g);
				g.setColor(Color.WHITE);
				g.fillRect(0, 0, 2000, 2000);
				g.setColor(Color.BLACK);
				for (Circle c : circles) {
					int r = (int) c.r;
					g.drawOval((int) c.centerX - r, (int) c.centerY - r,
							(int) 2 * r, (int) 2 * r);
				}
				g.setColor(Color.BLUE);
				int[] x = new int[path.size()];
				int[] y = new int[path.size()];
				int i = 0;
				for (Point p : path) {
					x[i] = (int) p.x;
					y[i] = (int) p.y;
					i++;
				}
				g.drawPolyline(x, y, x.length);
				g.setColor(Color.BLACK);
		    	
				g.drawString(
						"Path length=" + Double.toString((int) pathLength) + "   "
						+ count + " steps",
						10,
						25);
			}
		});
	}
    
	public static void main(String[] args) {
		// Create application frame.
		try {
			UIManager.setLookAndFeel(UIManager.getSystemLookAndFeelClassName());
        	
		} catch (Exception e) {}
		ShortPathFrame frame = new ShortPathFrame();
		// Show frame.
		frame.setVisible(true);
	}
}