algorithm3

package Algorithms;

import Graph.*;

import java.util.ArrayList;

import static Graph.Vertex.isIntersect;

class Algorithm3 {
    private static final double R = 100;
    private static final double PHI = Math.PI;
    private static final double R_OFFSET = Graph.R_OFFSET;

    private static Vertex findNearestSibling(Vertex v) {
        Vertex parent = v.getParent();
        double minAngle = Math.PI * 2;
        double delta;
        Vertex sibling = null;

        for (Vertex u: parent.getChild()) {
            if (u != v) {
                delta = makeInFirstQuarter(v.getAngle() - u.getAngle());

                if (delta < minAngle) {
                    minAngle = delta;
                    sibling = u;
                }
            }
        }

        if (sibling == null)
            throw new RuntimeException("Sibling is null");

        return sibling;
    }

    private static double makeInFirstQuarter(double angle) {
        if (angle <= 0) {
            while (angle <= 0)
                angle += Math.PI;
        }
        else {
            if (angle > Math.PI) {
                while (angle > Math.PI)
                    angle -= Math.PI;
            }
        }

        return angle;
    }

    private static double cosinesLaw(double angle, double side) {
        return Math.sqrt(2 * side * side - 2 * side * side * Math.cos(angle));
    }

    private static void radialPositions(Graph tree, Vertex root) {
        int currentDepth = root.getDepth();

        if (currentDepth != 0)
            throw new RuntimeException("Depth of the root is not null");

        for (Vertex v: tree.getVertices()) {
            if (v.isRoot()) {
                root.setX(0);
                root.setY(0);
                root.setR(R);
            }
            else {
                if (v.getParent() == root) {
                    v.setAngle(2 * Math.PI * root.getChild().indexOf(v) / root.getChild().size());
                    v.setR(R);
                    //System.out.println("v = " + v.getIndex() + " polar coords = (" + v.getAngle() + ", " + v.getR() + ")");
                }
                else {
                    v.setAngle(Math.PI - PHI / 2 + PHI * v.getParent().getChild().indexOf(v) / v.getParent().getChild().size() + PHI / (2 * v.getParent().getChild().size()));

                    if (v.getParent().getParent().getChild().size() == 1) {
                        v.setR(v.getParent().getR()); //здесь было R / 2
                        //System.out.println("v = " + v.getIndex() + " polar coords = (" + v.getAngle() + ", " + v.getR() + ")");
                    }
                    else {
                        Vertex sibling = findNearestSibling(v.getParent());

                        //System.out.println("v = " + v.getIndex() + " v.parent = " + v.getParent().getIndex() + " v.parent's sibling = " + sibling.getIndex());
                        //System.out.println("deltaOld = " + (v.getParent().getAngle() - sibling.getAngle()));

                        double delta = makeInFirstQuarter(v.getParent().getAngle() - sibling.getAngle()) / 2;

                        //System.out.println("r = " + cosinesLaw(delta, v.getParent().getR()) + " delta = " + delta);

                        v.setR(cosinesLaw(delta, v.getParent().getR()));

                        //System.out.println("v = " + v.getIndex() + " polar coords = (" + v.getAngle() + ", " + v.getR() + ")");
                    }
                }
            }

            System.out.println("VERTEX v = " + v.getIndex() + " r = " + v.getR());
            tree.getRadials().add(v.getR());
        }
    }

//    private static void castToPolarCoordinates(Graph tree, Vertex root) {
//        for (Vertex v: tree.getVertices()) {
//
//            if (v.getParent() == root) {
//                v.setX(v.getR() * Math.cos(v.getAngle()));
//                v.setY(v.getR() * Math.sin(v.getAngle()));
//            }
//
//            else {
//
//                if (v != root) {
//                    double r = cosinesLaw(v.getR(), v.getParent().getR(), v.getAngle());
//                    double phi = v.getParent().getAngle() - Math.asin(v.getR() * Math.sin(v.getAngle()) / cosinesLaw(v.getR(), v.getParent().getR(), v.getAngle()));
//
//                    v.setX(r * Math.cos(phi));
//                    v.setY(r * Math.sin(phi));
//                    //v.setVertexByPolar(r, phi);
//                }
//            }
//        }
//
////        for (Vertex v: tree.getVertices()) {
////            tree.getVertices().get(v.getIndex()).setX(v.getX());
////            tree.getVertices().get(v.getIndex()).setY(v.getY());
////        }
//    }

    private static void deleteIntersections(Graph tree) {
        //TODO сделать проверку пересечений на одной глубине; Проблема - пересечения не братьев, находящихся на одной глубине
//        for (int i = 1; i <= maxDepth; i++) {
//            ArrayList<Vertex> currentDepth = verticesByDepth.get(i);
//
//            for (Vertex v: currentDepth) {
//                double offset = makeRadialOffsetWithoutIntersections(v, verticesByDepth.get(i - 1));
//
//                if (offset != 0.0) {
//
//                    for (Vertex u: currentDepth) {
//
//                        if (u != v) {
//                            u.setVertexByPolar(u.getR() + offset, u.getAngle());
//                        }
//                    }
//                }
//            }
//
//            for (Vertex v: currentDepth) {
//                double offset = makeRadialOffsetWithoutIntersections(v, verticesByDepth.get(i));
//
//                if (offset != 0.0) {
//
//                    for (Vertex u: currentDepth) {
//
//                        if (u != v) {
//                            u.setVertexByPolar(u.getR() + offset, u.getAngle());
//                        }
//                    }
//                }
//            }
//        }

        for (Vertex v: tree.getVertices()) {
            makeRadialOffsetWithoutIntersections(v, v.getChild());

            for (Vertex u: v.getChild()) {
                ArrayList<Vertex> siblingsOfU = new ArrayList<>();
                siblingsOfU.addAll(v.getChild());
                siblingsOfU.remove(u);
                makeRadialOffsetWithoutIntersections(u, siblingsOfU);
//                double offset = makeRadialOffsetWithoutIntersections(u, siblingsOfU);
//                if (offset != 0.0) {
//                    double r = u.getR();
//                    u.setVertexByPolar(u.getR() + offset, u.getAngle());
//                    System.out.println("vertex = " + u.getIndex() + " r = " + u.getR() + " fact offset = " + (u.getR() - r));
//                }
            }
        }


        for (Vertex v: tree.getVertices()){
            for (Vertex u: tree.getVertices()) {
                if (v != u && isIntersect(v, u)) {
                    makeRadialOffsetWithoutIntersections(v, u);
                }
            }
        }
    }

    private static void makeRadialOffsetWithoutIntersections(Vertex v, Vertex u) {
        System.out.println("v = " + v.getIndex() + " u = " + u.getIndex());
        Vertex tempV = v;
        Vertex tempU = u;

        if (tempV.getDepth() > tempU.getDepth())
            while (tempV.getDepth() != tempU.getDepth())
                tempV = tempV.getParent();
        else
            while (tempV.getDepth() != tempU.getDepth())
                tempU = tempU.getParent();

        Vertex vP = tempV.getParent();
        Vertex uP = tempU.getParent();

        while (vP != uP){
            tempV = vP;
            tempU = uP;
            vP = tempV.getParent();
            uP = tempU.getParent();
        }

        System.out.println("vP = " + vP.getIndex() + " uP = " + uP.getIndex());
        System.out.println("tempV = " + tempV.getIndex() + " tempU = " + tempU.getIndex());
        System.out.println("\n");

        while (isIntersect(v, u)) {
            for (Vertex w: vP.getChild())
                w.moveFromParent(R_OFFSET);
            //tempV.moveFromParent(R_OFFSET);
            //tempU.moveFromParent(R_OFFSET);
        }
    }

    /* Смещаются вершины в vertices, v (брат или родитель) при выполнении этого алгоритма остается на месте */
    private static void makeRadialOffsetWithoutIntersections(Vertex v, ArrayList<Vertex> vertices) {
        double offset = 0.0;

        boolean wasIntersection = false;

        //TODO убрать это в production:
        if (v.getParent() != null)
            System.out.println("offset of v = " + v.getIndex() + " offset = " + v.distTo(v.getParent()));

        for (Vertex u: vertices) {
            System.out.println("v = " + v.getIndex() + " u = " + u.getIndex() + " isIntersect? " + isIntersect(v, u));

            double dist = u.distTo(u.getParent());

            while (isIntersect(v, u)) {
                wasIntersection = true;
                offset += R_OFFSET;
                u.moveFromParent(R_OFFSET);
                //System.out.println(pcLength);
                //System.out.println(u.getX() + " " + u.getY());
            }

            System.out.println("v = " + v.getIndex() + " child of v -- u = " + u.getIndex() + " offset = " + (u.distTo(u.getParent()) - dist) + " dist = " + u.distTo(u.getParent()));

            if (wasIntersection) {
                for (Vertex w : vertices) {
                    if (w != u) {
                        dist = w.distTo(w.getParent());
                        w.moveFromParent(offset);
                        System.out.println("                    w = " + w.getIndex() + " offset = " + (w.distTo(w.getParent()) - dist) + " dist = " + w.distTo(w.getParent()));
                    }
                }

                if (!v.getChild().contains(vertices.get(0))) {
                    dist = v.distTo(v.getParent());
                    v.moveFromParent(offset);
                    System.out.println("        siblings of v = " + v.getIndex() + " offset = " + (v.distTo(v.getParent()) - dist) + " dist = " + v.distTo(v.getParent()));
                }
            }
            wasIntersection = false;
            offset = 0.0;
            System.out.println("\n");
        }
    }

//    private static void fillRadials3(Graph tree) {
//        tree.getRadials().clear();
//
//        for (Vertex v: tree.getVertices()) {
//            if (v.getChild().size() != 0)
//                tree.getRadials().add(v.distTo(v.getChild().get(0)));
//            else
//                tree.getRadials().add(v.distTo(v.getParent()));
//        }
//    }

    static void useAlgorithm(Graph tree) {
        Vertex root = Algorithm5.findRoot(tree);

        tree.calculateMaxDepth(root);

        radialPositions(tree, root);

        for (Vertex v: tree.getVertices())
            v.castToCartesianCoordinates();

        for (Vertex v: tree.getVertices())
            System.out.println("BEFORE INTERSECT v = " + v.getIndex() + " r = " + v.getR() + " angle" + v.getAngle());

        deleteIntersections(tree);

        tree.fillRadials3();
    }
}