package org.simantics.debug.graphical.layout;

import java.util.ArrayList;
import java.util.Iterator;

public class BarnesHut2 {
    
    static final double OPTIMAL_DISTANCE = 150.0;   
    static final double C = 0.1;
    static final double K = C / OPTIMAL_DISTANCE;
    static final double G = K;
    static final double Q = C * OPTIMAL_DISTANCE * OPTIMAL_DISTANCE;

    public static final int OCTREE_LEAF_SIZE = 25;
    
    public static void applyDirectedForce(Particle a, Particle b) {
        double dx = a.x - b.x;
        double dy = a.y - b.y;
        double l2 = dx*dx + dy*dy;
        double s = Q / l2;
        a.fx += s * dx;
        a.fy += s * dy;
    }
    
    public static void applyDirectedForce(Particle a, OctreeNode b) {
        double dx = a.x - b.massCenterX;
        double dy = a.y - b.massCenterY;
        double l2 = dx*dx + dy*dy;
        double s = Q * b.mass / l2;
        a.fx += s * dx;
        a.fy += s * dy;
    }
    
    private static abstract class OctreeNode {
        double mass;
        double massCenterX;
        double massCenterY;
    }
    
    private static class OctreeInnerNode extends OctreeNode {
        final OctreeNode n00;
        final OctreeNode n10;
        final OctreeNode n01;
        final OctreeNode n11;
        
        public OctreeInnerNode(OctreeNode n00, OctreeNode n10, OctreeNode n01, OctreeNode n11) {
            this.n00 = n00;
            this.n10 = n10;
            this.n01 = n01;
            this.n11 = n11;
            
            double mass00 = n00.mass;
            double mass10 = n10.mass;
            double mass01 = n01.mass;
            double mass11 = n11.mass;
            double totalMass = mass00 + mass10 + mass01 + mass11;
            
            this.mass = totalMass;
            this.massCenterX = 
                    (n00.massCenterX*mass00 + n10.massCenterX*mass10 + 
                            n01.massCenterX*mass01 + n11.massCenterX*mass11)
                    / totalMass;
            this.massCenterY = 
                    (n00.massCenterY*mass00 + n10.massCenterY*mass10 + 
                            n01.massCenterY*mass01 + n11.massCenterY*mass11)
                    / totalMass;
        }
    }
    
    private static class OctreeLeaf extends OctreeNode {
        final Particle[] ps;

        public OctreeLeaf(Particle[] ps) {
            this.ps = ps;
            
            double massCenterX = 0.0;
            double massCenterY = 0.0;
            for(Particle p : ps) {
                massCenterX += p.x;
                massCenterY += p.y;
            }            
            
            this.mass = ps.length;
            this.massCenterX = massCenterX / ps.length;
            this.massCenterY = massCenterY / ps.length;
        }
    }
    
    private static OctreeNode constructOctree(double minX, double minY, double maxX, double maxY,
            ArrayList<Particle> ps) {
        if(ps.size() < OCTREE_LEAF_SIZE)
            return new OctreeLeaf(ps.toArray(new Particle[ps.size()]));
        
        double midX = 0.5 * (minX + maxX);
        double midY = 0.5 * (minY + maxY);
        
        ArrayList<Particle> ps00 = new ArrayList<Particle>();
        ArrayList<Particle> ps10 = new ArrayList<Particle>();
        ArrayList<Particle> ps01 = new ArrayList<Particle>();
        ArrayList<Particle> ps11 = new ArrayList<Particle>();
        
        for(Particle p : ps) {
            double x = p.x;
            double y = p.y;
            if(x < midX) {
                if(y < midY)
                    ps00.add(p);
                else
                    ps01.add(p);
            }
            else {
                if(y < midY)
                    ps10.add(p);
                else
                    ps11.add(p);
            }
        }
        
        return new OctreeInnerNode(
                constructOctree(minX, minY, midX, midY, ps00),
                constructOctree(midX, minY, maxX, midY, ps10),
                constructOctree(minX, midY, midX, maxY, ps01),
                constructOctree(midX, midY, maxX, maxY, ps11)
                );                
    }
    
    static class Bounds {
        final double minX;
        final double minY;
        final double maxX;
        final double maxY;
        
        public Bounds(double minX, double minY, double maxX, double maxY) {
            this.minX = minX;
            this.minY = minY;
            this.maxX = maxX;
            this.maxY = maxY;
        }
    }
    
    private static Bounds computeOctreeBounds(ArrayList<Particle> ps) {
        Iterator<Particle> it = ps.iterator();
        
        Particle pFirst = it.next(); 
        
        double minX = pFirst.x;
        double minY = pFirst.y;
        double maxX = pFirst.x;
        double maxY = pFirst.y;
        
        while(it.hasNext()) {
            Particle p = it.next();
            double x = p.x;
            double y = p.y;
            if(x < minX)
                minX = x;
            else if(x > maxX)
                maxX = x;
            if(y < minY)
                minY = y;
            else if(y > maxY)
                maxY = y;
        }
        
        double diff = (maxX - minX) - (maxY - minY);
        diff *= 0.5;
        if(diff > 0.0) {
            minY -= diff;
            maxY += diff;
        }
        else {
            minX += diff;
            maxX -= diff;   
        }
        return new Bounds(minX, minY, maxX, maxY);
    }

    private static void computeForce(OctreeNode octree,
            ArrayList<OctreeNode> nearNodes, ArrayList<OctreeNode> farNodes) {
        // TODO Auto-generated method stub
        
    }
    
    public static void computeRepulsiveForces(ArrayList<Particle> ps) {
        Bounds bounds = computeOctreeBounds(ps);        
        OctreeNode octree = constructOctree(bounds.minX, bounds.minY, bounds.maxX, bounds.maxY, ps);        
        computeForce(octree, new ArrayList<OctreeNode>(), new ArrayList<OctreeNode>());
    }
}