package drawing;

import java.util.Collections;
import java.util.Comparator;
import java.util.Vector;
import drawing.Diagram;
import Jama.Matrix;

/**
 * This class represents a graph drawing algorithm that respects the hierarchy
 * @author MC
 *
 */
public class GraphHierarchyEnergy extends Graph {
	/**
	 * if (i,j) is an edge, weights[i][j] = 1
	 */
	private double[][] weights;
	/**
	 * the minimum y distance between the vertices i and j
	 */
	private double[][] targetHeightDiff;
	private double[][] laplacien;
	private double[][] balance;
	
	/**
	 * @see Graph#Graph(Diagram)
	 * @param dia
	 */
	public GraphHierarchyEnergy(Diagram dia){
		super(dia);
	}
	/**
	 * @see Graph#Graph(Vector, Vector)
	 * @param V
	 * @param E
	 */
	public GraphHierarchyEnergy(Vector<Vertice> V, Vector<Edge> E){
		super(V, E);
	}
	/**
	 * @see Graph#Graph(Vector, Vector)
	 * @param dia
	 * @param V
	 * @param E
	 */
	public GraphHierarchyEnergy(Diagram dia, Vector<UnitClass> V, Vector<Link> E){
		super(dia, V, E);
	}
	/**
	 * computes the vertices coordinates
	 * @return
	 */
	public double[][] ComputeCoordinatesOptXY(){
		double [][] XY = new double[Vertices.size()][2];
		weights = new double[Vertices.size()][Vertices.size()];
		targetHeightDiff = new double[Vertices.size()][Vertices.size()];
		laplacien = new double[Vertices.size()][Vertices.size()];
		balance = new double[Vertices.size()][1];
		initW();
		initTH();
		computeB();
		computeL();
		
		double [][] Y = assignYCoordinates();
		
		//(new Matrix(Y)).print(2,2);
		for(int i = 0; i < Vertices.size(); i++){
			Vertice v = (Vertice) Vertices.get(i);
			v.y = Y[i][0];
		}
		
		ordering();
		
		GraphSpringLayout g = new GraphSpringLayout(Vertices, Edges);
		g.ComputeCoordinates();
		for(int i = 0; i < Vertices.size(); i++){
			Vertice v = (Vertice) Vertices.get(i);
			XY[v.index][0] = v.x;
			XY[v.index][1] = v.y;
		}
		return XY;
	}
	/**
	 * computes the vertices coordinates
	 * @return
	 */
	public double [][] ComputeCoordinatesOptX(){
		double [][] XY = new double[Vertices.size()][2];
		weights = new double[Vertices.size()][Vertices.size()];
		targetHeightDiff = new double[Vertices.size()][Vertices.size()];
		laplacien = new double[Vertices.size()][Vertices.size()];
		balance = new double[Vertices.size()][1];
		initW();
		initTH();
		computeB();
		computeL();
		
		double [][] Y = assignYCoordinates();
		
		//(new Matrix(Y)).print(2,2);
		for(int i = 0; i < Vertices.size(); i++){
			Vertice v = (Vertice) Vertices.get(i);
			v.y = Y[i][0];
		}
		
		Vector<Vector<Vertice>> order = ordering();

		GraphSpringLayout g = new GraphSpringLayout(Vertices, Edges);		
		g.ComputeXCoordinates();
		
//		reduce chevauchement
		for(int r = 0; r < order.size(); r++){
			Vector<Vertice> vect = order.get(r);
			Collections.sort(vect, new Comparator<Vertice>(){

				public int compare(Vertice arg0, Vertice arg1) {
					return ((Vertice)arg0).compareTo((Vertice)arg1);
				}
				
			});
			for(int i = 1; i < vect.size(); i++){
				Vertice v = (Vertice)vect.get(i);
				Vertice v2 = (Vertice)vect.get(i - 1);
				if(v.index != -1 && v2.index != -1){
					double d = - v2.x + v.x - v2.width -dxMin;
					if(d < 0){
						translateX(v.x , -d);
					}
				}
			}
		}
		
		for(int i = 0; i < Vertices.size(); i++){
			Vertice v = (Vertice) Vertices.get(i);
			if(!v.isVirtual){
				XY[v.index][0] = v.x;
				XY[v.index][1] = v.y;
			}
		}
		return XY;
	}
	/**
	 * computes the vertices coordinates
	 */
	public double [][] ComputeCoordinates(){
		return ComputeCoordinatesOptX();
	}
	/**
	 * computes the vertices coordinates
	 * @return
	 */
	public double [][] ComputeCoordinates1(){
		double [][] XY = new double[Vertices.size()][2];
		weights = new double[Vertices.size()][Vertices.size()];
		targetHeightDiff = new double[Vertices.size()][Vertices.size()];
		laplacien = new double[Vertices.size()][Vertices.size()];
		balance = new double[Vertices.size()][1];
		initW();
		initTH();
		computeB();
		computeL();
		
		double [][] Y = assignYCoordinates();
		
		for(int i = 0; i < Vertices.size(); i++){
			Vertice v = (Vertice) Vertices.get(i);
			v.y = Y[i][0];
		}
		
		Vector<Vector<Vertice>> order = ordering();
				
		double [][] X = new double[Vertices.size()][1];
		for(int i = 0; i < X.length; i++)
			X[i][0] = Math.random();
		
		
//		reduce chevauchement
		for(int r = 0; r < order.size(); r++){
			Vector<Vertice> vect = order.get(r);
			Collections.sort(vect, new Comparator<Vertice>(){

				public int compare(Vertice arg0, Vertice arg1) {
					return ((Vertice)arg0).compareTo((Vertice)arg1);
				}
				
			});
			for(int i = 1; i < vect.size(); i++){
				Vertice v = (Vertice)vect.get(i);
				Vertice v2 = (Vertice)vect.get(i - 1);
				if(v.index != -1 && v2.index != -1){
					double d = - v2.x + v.x - v2.width -dxMin;
					if(d < 0){
						translateX(v.x , -d);
					}
				}
			}
		}
		
		for(int i = 0; i < Vertices.size(); i++){
			Vertice v = (Vertice) Vertices.get(i);
			if(!v.isVirtual){
				XY[v.index][0] = v.x;
				XY[v.index][1] = v.y;
			}
		}
		return XY;
	}
	
	/**
	 * computes the vertices y coordinates
	 * @return
	 */
	private double[][] assignYCoordinates() {
		double [][] Y = new double[weights.length][1];
		Matrix A = new Matrix(laplacien);
		Matrix b = new Matrix(balance);
		Y = conjugateGradient(A, b);
		return Y;
	}
	/**
	 * translates the vertices beyond x absciss according to a distance
	 * @param x 
	 * @param distance
	 */
	private void translateX(double x, double distance){
		for(int i = 0; i < Vertices.size(); i++){
			Vertice v = (Vertice) Vertices.get(i);
			if(v.x >= x){
				v.x += distance;
			}
		}
	}
	/**
	 * compule laplacian
	 *
	 */
	private void computeL(){
		double s;
		for(int i = 0; i < weights.length; i++)
			for(int j = 0; j < weights.length; j++){
				if( i != j)
					laplacien[i][j] = -weights[i][j];
				else
				{
					s = 0;
					for(int k = 0; k < weights.length; k++)
						s += weights[i][k];
					laplacien[i][j] = s;
				}
			}
		
	}
	/**
	 * initialize weights matrix
	 *
	 */
	private void initW(){
		int startIndex;
		int endIndex;
		Edge e;
		for(int i = 0; i < weights.length; i++)
			for(int j = 0; j < weights.length; j++)
				weights[i][j] = 0;

		for(int i = 0; i < Edges.size(); i++){
			e = (Edge) Edges.get(i);
			startIndex = Vertices.indexOf(e.start);
			endIndex = Vertices.indexOf(e.end);
			weights[startIndex][endIndex] = 1;
			weights[endIndex][startIndex] = 1;
		}
	}
	/**
	 * initialize targetHeightDiff which displays the minimum y distance between two vertices 
	 *
	 */
	private void initTH(){
		int startIndex;
		int endIndex;
		Edge e;
		for(int i = 0; i < weights.length; i++)
			for(int j = 0; j < weights.length; j++)
				targetHeightDiff[i][j] = 0;

		for(int i = 0; i < Edges.size(); i++){
			e = (Edge) Edges.get(i);
			startIndex = Vertices.indexOf(e.start);
			endIndex = Vertices.indexOf(e.end);
			if(e.isOriented && !e.isVirtual){
				int d = 1;
				targetHeightDiff[startIndex][endIndex] = -d;
				targetHeightDiff[endIndex][startIndex] = d;
			}
		}
	}
	/**
	 * computes the balance vector
	 *
	 */
	private void computeB(){
		double s;
		for(int i = 0; i < weights.length; i++)
		{
			s = 0;
			for(int j = 0; j < weights.length; j++)
				s += weights[i][j] * targetHeightDiff[i][j];
			balance[i][0] = s;
		}
		
	}
	/**
	 * resolves the system Lx = b where L is singular
	 * @param L 
	 * @param b
	 * @return a solution of the system
	 */
	private double[][] conjugateGradient(Matrix L, Matrix b){
		double [][] y = new double[b.getRowDimension()][1];
		double eps = 0.0001;
		
		Matrix Y;
		Matrix d;
		Matrix r, temp;
		
		double alpha, beta, gama;
		
		//init
		double s = 0;
		for(int i = 0; i < b.getRowDimension(); i++){
			y[i][0] = Math.random();
			s += y[i][0]; 
		}
		s = s/b.getRowDimension();
		for(int i = 0; i < b.getRowDimension(); i++)
			y[i][0] -= s;
		
		Y = new Matrix(y);
		r = b.minus(L.times(Y));
		d = b.minus(L.times(Y));
		double norme = r.times(r.transpose()).get(0,0);
		
		// loop until convergence
		while( norme > eps){
			
			gama = r.transpose().times(r).get(0,0);
			temp = L.times(d);
			alpha = gama / (d.transpose().times(temp).get(0,0));
			Y = Y.plus(d.times(alpha));
			r = r.minus(L.times(d).times(alpha));
			beta = r.transpose().times(r).get(0,0) / gama;
			d = r.plus(d.times(beta));
			norme = r.times(r.transpose()).get(0,0);
		}
		return Y.getArray();
	}
	/**
	 * orders following the vertices abscisses 
	 * @return
	 */
	public Vector<Vector<Vertice>> ordering(){
		Vector<Vector<Vertice>> vectRanks = new Vector<Vector<Vertice>>();
		Vector<Edge> deletedEdges = new Vector<Edge>();
		
		// we order vertices by rank
		if(Vertices.size() > 0){		
			int rank = 0;
			
			Collections.sort(Vertices, new Comparator<Vertice>(){

				public int compare(Vertice arg0, Vertice arg1) {
					return ((Vertice)arg0).compareTo((Vertice)arg1);
				}
				
			});
			
			Vertice v = (Vertice) Vertices.get(0);
			double y = Math.round(v.y * 100);
			v.y = 0;
			v.x = 0;
			vectRanks.add(new Vector<Vertice>());
			(vectRanks.get(0)).add(v);
			
			for(int i = 1; i < Vertices.size() ;i++)
			{
				Vertice vi = (Vertice) Vertices.get(i);
				//System.out.println(vi.y);
				if(Math.round(vi.y * 100) == y){
					(vectRanks.get(rank)).add(vi);
					vi.y = rank; 
					vi.x = (vectRanks.get(rank)).size()-1;
				}
				else{
					v = vi;
					rank ++;
					y = Math.round(vi.y * 100);
					vi.y = rank;
					vi.x = 0;
					vectRanks.add(new Vector<Vertice>());
					(vectRanks.get(rank)).add(v);
				}
			}
			
			// we optimize hierarchy
			for(int r = 0; r < vectRanks.size(); r++){
				Vector<Vertice> vect = vectRanks.get(r);
				for(int i = 0; i < vect.size(); i++){
					Vertice vi = (Vertice)vect.get(i);
					if(optimizeHierarchy(vectRanks, vi, r))
						i--;
				}
				if(vect.size() == 0)
					r--;
			}
			
			// add virtual vertices when needed
			for(int i = 0; i < Edges.size(); i++){
				Edge e = (Edge) Edges.get(i);
				Vertice start = e.start;
				Vertice end = e.end;
				double deg = end.y - start.y - 1;
				if(deg > 0){
					for( int j = 0; j < deg; j++){
						Vertice virtual = new Vertice();
						virtual.x = 0;
						virtual.y = start.y + 1;
						Edges.add(new Edge(start, virtual, true));
						start = virtual;
						
					}
					deletedEdges.add(Edges.get(i));
					Edges.remove(i);
					i--;
				}
			}
			
			
		//	Object best = vectRanks.clone();
                        Vector<Vector<Vertice>> best = new Vector<Vector<Vertice>>(vectRanks);
			int crossBest = crossing();
			for(int i = 0; i < 24; i++){
				wmedian(vectRanks, i);
				transpose(vectRanks);
				int cross = crossing();
				if(cross < crossBest){
					crossBest = cross;
				//	best = vectRanks.clone();
                                        best = new Vector<Vector<Vertice>>(vectRanks);
				}
			}
			vectRanks = best;
	
			for(int r = 0; r< vectRanks.size(); r++)
			{
				Vector<Vertice> vect = vectRanks.get(r);
				if(vect.size() > 0){
					v = (Vertice)vect.get(0);
					v.x = 0;
					v.y = (v.height + dyMin)*r;
					if(vect.size() > 1){
						for(int i = 1; i < vect.size(); i++){
							Vertice vi = (Vertice)vect.get(i);
							vi.x = ((Vertice)vect.get(i - 1)).x + ((Vertice)vect.get(i - 1)).width + dxMin;
							vi.y = v.y;
						}
					}
				}
			}
		}
		
		//add removed edges
		for(int i = 0; i < deletedEdges.size(); i++ )
			Edges.add(deletedEdges.get(i));
		
		//remove virtual edges
		int startIndex;
		int endIndex;
		Edge e;
		for(int i = 0; i < Edges.size(); i++){
			e = (Edge) Edges.get(i);
			startIndex = Vertices.indexOf(e.start);
			endIndex = Vertices.indexOf(e.end);
			if(startIndex == -1 || endIndex == -1){
				Edges.remove(i);
				i--;
			}
		}
		
		//remove virtual vertices
		for(int i = 0; i < Vertices.size(); i++){
			Vertice v = (Vertice) Vertices.get(i);
			if(v.index == -1){
				Vertices.remove(v);
				i--;
			}
		}
		return vectRanks;
	}
	/**
	 * used for ordering method
	 * @param order
	 * @param iter
	 */
	private void wmedian(Vector<Vector<Vertice>> order, int iter){
		//if(iter % 2 == 0)
			for(int r = 1; r < order.size(); r++){
				Vector<Vertice> vect = order.get(r);
				for(int i = 0; i < vect.size(); i++){
					Vertice v = (Vertice)vect.get(i);
					v.x = medianValue(v);
				}
				//Collections.sort(vect);
                 	        Collections.sort(vect, new Comparator<Vertice>() {
	                            public int compare(Vertice o1, Vertice o2) {
	                               Vertice v1 = (Vertice)o1;
	                               Vertice v2 = (Vertice)o2;
	                               return v1.compareTo(v2);
	                            }
	                        }); 
			}		
	}
	/**
	 * optimize the y coordinates for having better hierarchy
	 * @param order
	 * @param v
	 * @param rank
	 * @return
	 */
	private boolean optimizeHierarchy(Vector<Vector<Vertice>> order, Vertice v, int rank){
		boolean res = false;
		Vector<Vertice> P = new Vector<Vertice>();
		double deg = 0;

		for( int i = 0; i < Edges.size(); i++){
			Edge e = (Edge)Edges.get(i);
			Vertice start = e.start;
			Vertice end = e.end;
			if(end.equals(v))
				P.add(start);
		}
		
		if(P.size() > 0){
			Vertice vi = (Vertice) P.get(0);
			deg = v.y - vi.y;
		}
		
		for(int i = 0; i < P.size(); i++){
			Vertice vi = (Vertice) P.get(i);
			if(v.y - vi.y < deg)
				deg = v.y - vi.y;
		}
		
		if(deg > 1){
			res = true;
			// we translate the vertice
			v.y = rank - (int )deg + 1;
			Vector<Vertice> vect = order.get(rank - (int)deg + 1);
			vect.add(v);
			vect = order.get(rank);
			vect.remove(v);
			if(vect.size()  == 0){
				
				order.remove(vect);
				for(int r = rank; r < order.size(); r++){
					Vector<Vertice> vectr = order.get(r);
					for(int i = 0; i < vectr.size(); i++){
						Vertice vi = (Vertice)vectr.get(i);
						vi.y = r;
					}
				}
			}
		}
		return res;
	}
	/**
	 * used in wmedian method
	 * @param v
	 * @return
	 */
	private double medianValue(Vertice v){
		Vector<Vertice> P = new Vector<Vertice>();
		for( int i = 0; i < Edges.size(); i++){
			Edge e = (Edge)Edges.get(i);
			Vertice start = e.start;
			Vertice end = e.end;
			if(end.equals(v))
				P.add(start);
		}
		int m = P.size()/2;
		if(m == 0)
			return v.x;
		else if(P.size() % 2 == 1)
			return ((Vertice)P.get(m)).x;
		else if (P.size()== 2)
			return (((Vertice)P.get(1)).x + ((Vertice)P.get(0)).x)/2;
		else {
			double left = ((Vertice)P.get(m - 1)).x - ((Vertice)P.get(0)).x;
			double right = ((Vertice)P.get(P.size() - 1)).x - ((Vertice)P.get(m)).x;
			return (((Vertice)P.get(m - 1)).x * right + ((Vertice)P.get(m)).x * left)/(left + right);
		}
	}
	/**
	 * used in the ordering method
	 * @param order
	 */
	private void transpose(Vector<Vector<Vertice>> order){
		boolean improved = true;
		while(improved){
			improved = false;
			for(int r = 0; r< order.size(); r++)
			{
				Vector<Vertice> vect = order.get(r);
				for(int i = 0; i < vect.size()-1; i++){
					Vertice v = (Vertice)vect.get(i);
					Vertice w = (Vertice)vect.get(i+1);
					if(crossing(v, w) > crossing(w, v)){
						improved = true;
						vect.set(i+1, v);
						vect.set(i, w);
					}
				}
			}
		}
	}
	/**
	 * used in the ordering method
	 * @param v
	 * @param w
	 * @return
	 */
	private int crossing(Vertice v, Vertice w){
		int ret = 0;
		Vector<Vertice> startV = new Vector<Vertice>();
		Vector<Vertice> startW = new Vector<Vertice>();
		Vector<Vertice> endV = new Vector<Vertice>();
		Vector<Vertice> endW = new Vector<Vertice>();
		for( int i = 0; i < Edges.size(); i++){
			Edge e = (Edge)Edges.get(i);
			Vertice start = e.start;
			Vertice end = e.end;
			if(end.equals(v))
				endV.add(start);
			else if(end.equals(w))
				endW.add(start);
			
			if(start.equals(v))
				startV.add(end);
			else if(start.equals(w))
				startW.add(end);
		}
		
		for(int i = 0; i < startV.size(); i++)
		{
			Vertice vi = (Vertice) startV.get(i);
			for(int j = 0; j < startW.size(); j++){
				Vertice vj = (Vertice) startW.get(j);
				if(vi.x > vj.x)
					ret++;
			}
		}
		
		for(int i = 0; i < endV.size(); i++)
		{
			Vertice vi = (Vertice) endV.get(i);
			for(int j = 0; j < endW.size(); j++){
				Vertice vj = (Vertice) endW.get(j);
				if(vi.x > vj.x)
					ret++;
			}
		}
		return ret;
	}
	/**
	 * used for the ordering method
	 * @return
	 */
	private int crossing(){
		int ret = 0;
		for( int i = 0; i < Edges.size(); i++){
			Edge ei = (Edge)Edges.get(i);
			Vertice starti = ei.start;
			Vertice endi = ei.end;
			for( int j = 0; j < Edges.size(); j++){
				Edge ej = (Edge)Edges.get(j);
				Vertice startj = ej.start;
				Vertice endj = ej.end;
				if(i != j && startj.y == starti.y){
					if (starti.x > startj.x && endi.x < endj.x)
						ret ++;
					else if(starti.y < starti.y && endi.y > endj.y)
						ret++;
				}
			}			
		}
		return ret;
	}
}
