package graphTheory.graphDrawer;

import graphTheory.graph.Arc;
import graphTheory.graph.Graph;
import graphTheory.utils.Couple;
import graphTheory.utils.Math2;

import java.util.HashMap;
import java.util.List;

/**
 * 
 * Draw a graph using an analogy with electomagnetism.
 * 
 * Source : Graph Drawing by Force-directed Placement, THOMAS M. J. FRUCHTERMAN
 * AND EDWARD M. REINGOLD
 * 
 * @author Watel Dimitri
 * 
 */
public class EnergyAnalogyGraphDrawer extends GraphDrawer {

	/**
	 * 
	 */
	private static final long serialVersionUID = 1L;

	public EnergyAnalogyGraphDrawer(Graph g) {
		super(g);
	}

	public EnergyAnalogyGraphDrawer(Graph g,
			@SuppressWarnings("rawtypes") HashMap arcDisplayedParam) {
		super(g, arcDisplayedParam);
	}

	/**
	 * This parameter increases the repulsion force and and reduces the
	 * attraction forces when growing.
	 */
	private double k;

	/**
	 * Number of iterations before stop the process.
	 */
	private static final int iterations = 1000;

	/**
	 * Place nodes at random at first.
	 */
	protected void initVerticesCoordinates() {
		List<Integer> vertices = graph.getVertices();

		for (Integer v : vertices) {
			graph.setNodeAbscisse(v, Math2.randomInt(getWidth()));
			graph.setNodeOrdonnee(v, Math2.randomInt(getHeight()));
		}
	}

	protected void setVerticesCoordinates() {
		int area = this.getWidth() * this.getHeight();
		k = Math.sqrt((double) area / graph.getNumberOfVertices());

		initVerticesCoordinates(); // Place nodes at random.

		List<Integer> vertices = graph.getVertices();
		Couple<Double, Double> c, delta;
		double rep, att;

		// Disp contains the displacement vectors of each nodes at each iteration.
		HashMap<Integer, Couple<Double, Double>> disp = new HashMap<Integer, Couple<Double, Double>>();

		for (int i = 0; i < iterations; i++) {

			// Start with repulsive forces
			for (Integer v : vertices) {
				disp.put(v, new Couple<Double, Double>(0.0, 0.0)); // Displacement initialized with 0
				for (Integer u : vertices) {
					if (u != v) {
						delta = new Couple<Double, Double>(
								(double) (graph.getNodeAbscisse(v) - graph
										.getNodeAbscisse(u)),
								(double) (graph.getNodeOrdonnee(v) - graph
										.getNodeOrdonnee(u)));

						// If nodes are at the same place, repulsion is infinite. The nodes are then moved a little.
						if (delta.first == 0.0 && delta.second == 0.0) {
							graph.setNodeAbscisse(
									v,
									graph.getNodeAbscisse(v)
											+ ((graph.getNodeAbscisse(v) > getWidth() / 2) ? -1
													: 1) * 50);
							delta.first = (double) (graph.getNodeAbscisse(v) - graph
									.getNodeAbscisse(u));
							delta.second = (double) (graph.getNodeOrdonnee(v) - graph
									.getNodeOrdonnee(u));
						}
						// We add the repulsion to the displacement vector.
						else {
							normalize(delta);
							c = disp.get(v);
							rep = repulsion(v, u);
							c.first = c.first + delta.first * rep;
							c.second = c.second + delta.second * rep;
						}
					}
				}
			}

			// Compute the attractions
			Integer u, v;
			for (Arc e : graph.getEdges()) {
				v = e.getInput();
				u = e.getOutput();
				delta = new Couple<Double, Double>(
						(double) (graph.getNodeAbscisse(v) - graph
								.getNodeAbscisse(u)),
						(double) (graph.getNodeOrdonnee(v) - graph
								.getNodeOrdonnee(u)));
				normalize(delta);
				att = attraction(v, u);
				c = disp.get(v);
				c.first = c.first - delta.first * att;
				c.second = c.second - delta.second * att;

				c = disp.get(u);
				c.first = c.first + delta.first * att;
				c.second = c.second + delta.second * att;

			}

			// Move the vertices
			// At each iteration, the movement is maximized by an upper bound which decrease
			// as if temperature would decrease and reach 0. As a consequence, nodes can move
			// a lot at the beginning and very little at the end.
			double norm;
			for (Integer v1 : vertices) {
				c = disp.get(v1);
				norm = norm(c);
				normalize(c);
				graph.setNodeAbscisse(
						v1,
						graph.getNodeAbscisse(v1)
								+ (int) (c.first * Math.min(norm, iterations
										/ (double) (i + 1))));
				if (graph.getNodeAbscisse(v1) > this.getWidth() - 50)
					graph.setNodeAbscisse(v1,
							this.getWidth() - 50 + Math2.randomInt(-25, 25));
				else if (graph.getNodeAbscisse(v1) < 50)
					graph.setNodeAbscisse(v1, 50 + Math2.randomInt(-25, 25));

				graph.setNodeOrdonnee(
						v1,
						graph.getNodeOrdonnee(v1)
								+ (int) (c.second * Math.min(norm, iterations
										/ (double) (i + 1))));
				if (graph.getNodeOrdonnee(v1) > this.getHeight() - 50)
					graph.setNodeOrdonnee(v1,
							this.getHeight() - 50 + Math2.randomInt(-25, 25));
				else if (graph.getNodeOrdonnee(v1) < 50)
					graph.setNodeOrdonnee(v1, 50 + Math2.randomInt(-25, 25));

			}
		}
	}

	/**
	 * Divide a 2D vector by its norm
	 * 
	 * @param c
	 */
	private void normalize(Couple<Double, Double> c) {
		double norm = norm(c);
		c.first = c.first / norm;
		c.second = c.second / norm;
	}

	/**
	 * Compute the norm of a 2D vector
	 * 
	 * @param c
	 * @return
	 */
	private double norm(Couple<Double, Double> c) {
		return Math.sqrt(c.first * c.first + c.second * c.second);
	}

	/**
	 * Compute the distance between two nodes drawed on the frame
	 * 
	 * @param n1
	 * @param n2
	 * @return
	 */
	private double distance(Integer n1, Integer n2) {
		return Math.sqrt(Math.pow(
				graph.getNodeAbscisse(n1) - graph.getNodeAbscisse(n2), 2)
				+ Math.pow(
						graph.getNodeOrdonnee(n1) - graph.getNodeOrdonnee(n2),
						2));
	}

	/**
	 * Compute the attraction bewteen two nodes
	 * 
	 * @param n1
	 * @param n2
	 * @return
	 */
	private double attraction(Integer n1, Integer n2) {
		return Math.pow(distance(n1, n2), 2) / k;
	}

	/**
	 * Compute the repulsion bewteen two nodes.
	 * 
	 * @param n1
	 * @param n2
	 * @return
	 */
	private double repulsion(Integer n1, Integer n2) {
		return k * k / distance(n1, n2);
	}
}
