package org.simantics.debug.graphical.layout;

import gnu.trove.list.array.TIntArrayList;
import gnu.trove.map.hash.TObjectIntHashMap;

import java.util.ArrayList;

import org.simantics.debug.graphical.model.Edge;
import org.simantics.debug.graphical.model.Node;

public class LayoutGraph {

    static final double G = 0.001;
    static final double K = 0.001;
    static final double Q = 10000.0;
    
    private static void computeForces(Node[] nodes, Edge[] edges) {
        for(Node node : nodes) {
            node.forceX = 0.0;
            node.forceY = 0.0;
        }
        
        for(Edge edge : edges) {
            Node a = edge.getA();
            Node b = edge.getB();
            double ax = a.getX();
            double ay = a.getY();
            double bx = b.getX();
            double by = b.getY();
            double fx = K * (bx - ax);
            double fy = K * (by - ay);
            a.forceX += fx;
            a.forceY += fy;
            b.forceX -= fx;
            b.forceY -= fy;
        }
        
        for(int i=0;i<nodes.length;++i) { 
            Node a = nodes[i];
            a.forceX -= a.getX()*G;
            a.forceY -= a.getY()*G;
            for(int j=i+1;j<nodes.length;++j) {
                Node b = nodes[j];
                
                double ax = a.getX();
                double ay = a.getY();
                double bx = b.getX();
                double by = b.getY();
                double dx = bx - ax;
                double dy = by - ay;
                double l2 = dx*dx + dy*dy;
                if(l2 > 0.1) {
                    double l = Math.sqrt(l2);
                    double l3 = l*l2;
                    double fx = Q * dx / l3;
                    double fy = Q * dy / l3;
                    a.forceX -= fx;
                    a.forceY -= fy;
                    b.forceX += fx;
                    b.forceY += fy;
                }
            }
        }
    }
    
    public static void layout(Node[] nodes, Edge[] edges) {        
        /*for(int iter=0;iter<100;++iter) {
            computeForces(nodes, edges);
            for(Node node : nodes) {
                node.setPos(node.getX() + node.forceX*10.0, node.getY() + node.forceY*10.0);
            }
        } */
        
        TObjectIntHashMap<Node> nodeIds = new TObjectIntHashMap<Node>();
        for(int i=0;i<nodes.length;++i)
            nodeIds.put(nodes[i], i);        
        
        int[][] neighbors = new int[nodes.length][];
        {
            TIntArrayList[] neighborLists = new TIntArrayList[nodes.length];        
            for(int i=0;i<neighborLists.length;++i)
                neighborLists[i] = new TIntArrayList();
            for(Edge edge : edges) {
                Node a = edge.getA();
                Node b = edge.getB();
                int aId = nodeIds.get(a);
                int bId = nodeIds.get(b);
                neighborLists[aId].add(bId);
                neighborLists[bId].add(aId);
            }            
            for(int i=0;i<neighborLists.length;++i) {
                TIntArrayList l = neighborLists[i];                
                removeDuplicates(l);
                neighbors[i] = l.toArray();
            }
        }
        
        LayoutAlgorithm algo = new LayoutAlgorithm(neighbors);
        double[] posX = algo.getPosX();
        double[] posY = algo.getPosY();
        for(int i=0;i<nodes.length;++i) {
            posX[i] = nodes[i].getX();
            posY[i] = nodes[i].getY();
        }
        algo.optimize();
        for(int i=0;i<nodes.length;++i) {
            nodes[i].setPos(posX[i], posY[i]);
        }        
    }
    
    private static void removeDuplicates(TIntArrayList l) {
        l.sort();
        int length = l.size();
        int tgt = 0;
        int tgtValue=l.get(tgt);
        for(int src=1;src<length;++src) {
            int srcValue = l.get(src);
            if(srcValue != tgtValue) {
                tgtValue = srcValue;
                l.set(++tgt, tgtValue);
            }
        }
        --length;
        while(length > tgt) {
            l.removeAt(length);
            --length;
        }
    }

    public static void layoutOld(Node[] nodes, Edge[] edges) {
        
        // Neighborhood array        
        TObjectIntHashMap<Node> nodeIds = new TObjectIntHashMap<Node>();
        for(int i=0;i<nodes.length;++i)
            nodeIds.put(nodes[i], i);
        @SuppressWarnings("unchecked")
        ArrayList<Node>[] neighbors = new ArrayList[nodes.length];        
        for(int i=0;i<neighbors.length;++i)
            neighbors[i] = new ArrayList<Node>();
        for(Edge edge : edges) {
            Node a = edge.getA();
            Node b = edge.getB();
            neighbors[nodeIds.get(a)].add(b);
            neighbors[nodeIds.get(b)].add(a);
        }
        
        // Iteration
        for(int iter=0;iter<1;++iter) {
            for(int i=0;i<nodes.length;++i) {
                Node node = nodes[i];
                double x = node.getX();
                double y = node.getY();
                
                // Gravitation
                double forceX = -G * x;
                double forceY = -G * y;
                double idS = -G;
                
                // Attraction
                ArrayList<Node> ns = neighbors[i];
                idS -= K * ns.size();
                for(Node n : ns) {
                    forceX -= K * (x - n.getX());
                    forceY -= K * (y - n.getY());
                }
                
                // Repulsion
                double xx=0.0, xy=0.0, yy=0.0;
                for(int j=0;j<nodes.length;++j)
                    if(i != j) {
                        Node n = nodes[j];
                        double dx = x - n.getX();
                        double dy = y - n.getY();
                        double l2 = dx*dx + dy*dy;
                        if(l2 > 0.01) {
                            double l = Math.sqrt(l2);
                            double l3 = l*l2;
                            idS += Q / l3;
                            double l5 = l3*l2;
                            xx -= Q*dx*dx / l5;
                            xy -= Q*dx*dy / l5;
                            yy -= Q*dy*dy / l5;
                            
                            forceX += Q * dx / l3;
                            forceY += Q * dy / l3;
                        }
                    }
                
                xx += idS;
                yy += idS;
                
                System.out.println("force"+i+" = (" + forceX + ", " + forceY + ")");                
                
                // Solve
                double det = xx * yy - xy * xy;
                System.out.println("mx"+i+" = (" + xx + "," + xy + "," + yy + ") " + det);
                if(Math.abs(det) > 1e-6) {
                    double dx = (yy * forceX - xy * forceY) / det;
                    double dy = (xx * forceY - xy * forceX) / det;
                    node.setPos(x-dx*0.5, y-dy*0.5);
                }
            }
        }                    
    }
    
}