algorithm5

package Algorithms;

import Graph.*;
import Visualization.GraphVisualization;

import java.util.ArrayList;
import java.util.Comparator;

class Algorithm5 {
    private static double R;
    private static final int WIDTH = GraphVisualization.WIDTH;
    private static final int HEIGHT = GraphVisualization.HEIGHT;
    private static final double RADIAL_COEFFICIENT = 0.9;

    //TODO переписать этот алгоритм, где то есть ошибка
    private static void deleteIntersections(Graph tree) {
        //ArrayList<ArrayList<Vertex>> verticesByDepth = tree.getVerticesByDepth();

        for (Vertex v: tree.getVertices()) {
            ArrayList<Vertex> currentDepthWithoutV = new ArrayList<Vertex>();
            currentDepthWithoutV.sort(angleComparator);
            currentDepthWithoutV.addAll(tree.getVerticesByDepth(v.getDepth()));
            currentDepthWithoutV.remove(v);

            //makeAngleOffsetWithoutIntersections(v, tree.getVerticesByDepth(v.getDepth()));
            makeRadialOffsetWithoutIntersections(v, currentDepthWithoutV, tree);

            if (v.getDepth() != tree.getMaxDepth())
                makeRadialOffsetWithoutIntersections(v, tree.getVerticesByDepth(v.getDepth() + 1), tree);
        }
//        for (int i = 1; i <= tree.getMaxDepth(); i++) {
//            ArrayList<Vertex> currentDepth = verticesByDepth.get(i);
//            currentDepth.sort(angleComparator);
//
////            for (Vertex v: currentDepth)
////                System.out.println("v = " + v.getIndex() + " angle = " + v.getAngle());
//
//            for (Vertex v: currentDepth) {
//                double offset = makeRadialOffsetWithoutIntersections(v, verticesByDepth.get(i - 1), tree);
//
//                if (offset != 0.0) {
//
//                    for (Vertex u: currentDepth) {
//
//                        if (u != v) {
//                            u.setVertexByPolar(u.getR() + offset, u.getAngle());
//                        }
//                    }
//                }
//            }
//
//            for (Vertex v: currentDepth) {
//                double angleOffset = makeAngleOffsetWithoutIntersections(v, currentDepth);
//
//                if (angleOffset == -1.0) {
//                    double radialOffset = makeRadialOffsetWithoutIntersections(v, currentDepth, tree);
//
//                    for (Vertex u: currentDepth) {
//
//                        if (u != v) {
//                            u.setVertexByPolar(u.getR() + radialOffset, u.getAngle());
//                        }
//                    }
//                }
//            }
//        }
    }

    private static final double ANGLE_OFFSET = Math.PI / 18; //10 градусов
    private static Comparator<Vertex> angleComparator = Comparator.comparingDouble(o -> o.getAngle());

    private static void makeAngleOffsetWithoutIntersections(Vertex v, ArrayList<Vertex> vertices) {
        for (Vertex u: vertices) {
            boolean wasIntersection = isIntersect(v, u);
            if (wasIntersection) {
                double angle = v.getAngle();
                double delta = v.getAngle() - u.getAngle();

                int index = vertices.indexOf(v);
                Vertex w = vertices.get(delta < 0 ? (index - 1) % vertices.size() : (index + 1) % vertices.size());

                boolean WIntersection = false;

                while (isIntersect(v, u) && !WIntersection) {
                    if (delta > 0) {
                        v.setVertexByPolar(v.getR(), v.getAngle() + ANGLE_OFFSET);
                    }
                    else {
                        v.setVertexByPolar(v.getR(), v.getAngle() - ANGLE_OFFSET);
                    }

                    WIntersection = isIntersect(v, w);
                }

                if (WIntersection)
                    v.setVertexByPolar(v.getR(), angle);

                angle = u.getAngle();
                delta = u.getAngle() - v.getAngle();

                index = vertices.indexOf(u);
                w = vertices.get(delta < 0 ? (index - 1) % vertices.size() : (index + 1) % vertices.size());

                WIntersection = false;

                while (isIntersect(v, u) && !WIntersection) {
                    if (delta > 0)
                        u.setVertexByPolar(u.getR(), u.getAngle() + ANGLE_OFFSET);
                    else
                        u.setVertexByPolar(u.getR(), u.getAngle() - ANGLE_OFFSET);

                    WIntersection = isIntersect(u, w);
                }

                if (WIntersection)
                    u.setVertexByPolar(u.getR(), angle);
            }
        }
    }

//    private static double makeAngleOffsetWithoutIntersections(Vertex v, ArrayList<Vertex> vertices) {
//        double offset = 0.0;
//        for (Vertex u: vertices) {
//            if (u != v) {
//                boolean intersection = isIntersect(v, u);
//                if (intersection) {
//                    double angle = v.getAngle();
//                    double x = v.getX();
//                    double y = v.getY();
//                    double delta = v.getAngle() - u.getAngle();
//
//                    int indexOfV = vertices.indexOf(v);
//                    Vertex w = vertices.get(delta < 0 ? (indexOfV - 1) % vertices.size() : (indexOfV + 1) % vertices.size());
//
//                    if (delta > 0.0) {
//                        boolean VWintersection = false;
//
//                        while (isIntersect(v, u) && !VWintersection) {
//                            v.setAngle(v.getAngle() + ANGLE_OFFSET);
//                            offset += ANGLE_OFFSET;
//                            v.setX(v.getR() * Math.cos(v.getAngle()));
//                            v.setY(v.getR() * Math.sin(v.getAngle()));
//                            VWintersection = isIntersect(v, w);
//                        }
//
//                        if (VWintersection) {
//                            v.setAngle(angle);
//                            v.setX(x);
//                            v.setY(y);
//                            return -1.0;
//
//                        } else
//                            return offset;
//                    } else {
//                        boolean VWintersection = false;
//
//                        while (isIntersect(v, u) && !VWintersection) {
//                            v.setAngle(v.getAngle() - ANGLE_OFFSET);
//                            offset -= ANGLE_OFFSET;
//                            v.setX(v.getR() * Math.cos(v.getAngle()));
//                            v.setY(v.getR() * Math.sin(v.getAngle()));
//                            VWintersection = isIntersect(v, w);
//                        }
//
//                        if (VWintersection) {
//                            v.setAngle(angle);
//                            v.setX(x);
//                            v.setY(y);
//                            return -1.0;
//
//                        } else
//                            return offset;
//                    }
//                }
//            }
//        }
//        return offset;
//    }

    static final double R_OFFSET = 5.0;

    private static void makeRadialOffsetWithoutIntersections(Vertex v, ArrayList<Vertex> vertices, Graph tree) {
        double offset = 0.0;

        boolean wasIntersection = false;

        for (Vertex u: vertices) {
            while (isIntersect(v, u)) {
                wasIntersection = true;
                offset += R_OFFSET;
                u.setVertexByPolar(u.getR() + R_OFFSET, u.getAngle());

                if (u.getDepth() == v.getDepth())
                    v.setVertexByPolar(v.getR() + R_OFFSET, v.getAngle());
            }

            if (wasIntersection) {
                for (Vertex w: vertices) {
                    if (w != u) {
                        w.setVertexByPolar(w.getR() + offset, w.getAngle());
                    }
                }

                for (int i = u.getDepth() + 1; i <= tree.getMaxDepth(); i++)
                    for (Vertex q: tree.getVerticesByDepth(i))
                        q.setVertexByPolar(q.getR() + offset, q.getAngle());
            }

            wasIntersection = false;
            offset = 0.0;
        }
    }

//    private static double makeRadialOffsetWithoutIntersections(Vertex v, ArrayList<Vertex> vertices, Graph tree) {
//        double offset = 0.0;
//
//        for (Vertex u: vertices) {
//
//            //TODO т.к. isIntersect(v, v) == false, то, возможно, следующий if не нужен
//            if (u != v) {
//
//                System.out.println("INTERSECTION? v = " + v.getIndex() + " u = " + u.getIndex() + " " + isIntersect(v, u));
//
////                if (v.getIndex() == 8 && u.getIndex() == 6) {
////
////                    for (Double[] points : v.getPoints())
////                        System.out.print("[" + points[0] + ", " + points[1] + "] ");
////                    System.out.println("\n");
////
////                    for (Double[] points : u.getPoints())
////                        System.out.print("[" + points[0] + ", " + points[1] + "] ");
////                    System.out.println("\n");
////                }
//
//                while (isIntersect(v, u)) {
//                    int i = tree.getRadials().indexOf(v.getR());
//                    double r = tree.getRadials().get(i);
//
//                    r += R_OFFSET;
//                    offset += R_OFFSET;
//                    tree.getRadials().set(i, r);
//
//                    v.setVertexByPolar(v.getR() + R_OFFSET, v.getAngle());
//                }
//
//                System.out.println("INTERSECTION? v = " + v.getIndex() + " u = " + u.getIndex() + " " + isIntersect(v, u));
////                if (v.getIndex() == 8 && u.getIndex() == 6) {
////
////                    for (Double[] points: v.getPoints())
////                        System.out.print("[" + points[0] + ", " + points[1] + "] ");
////                    System.out.println("\n");
////
////                    for (Double[] points: u.getPoints())
////                        System.out.print("[" + points[0] + ", " + points[1] + "] ");
////                    System.out.println("\n");
////                }
//            }
//        }
//
//        return offset;
//    }

    static boolean isIntersect(Vertex v, Vertex u) {
        return v.isIn(u) || u.isIn(v);
    }

    private static void addFirstRadii(Graph tree) {
        R = (WIDTH < HEIGHT? WIDTH : HEIGHT)/ tree.getMaxDepth() / 2 * RADIAL_COEFFICIENT; //раньше радиус был константный
        //R = 50.0;

        tree.getRadials().add(R);
    }

    static Vertex findRoot(Graph tree) {
        Vertex root = null;

        for (Vertex v: tree.getVertices()) {
            if (v.isRoot()) {
                root = v;
                break;
            }
        }

        if (root == null)
            throw new RuntimeException("ERROR root is null");
        else
            return root;
    }

    private static int leavesCount = 0;
    private static int leavesCounter(Vertex root) {
        countLeaves(root);
        return leavesCount;
    }

    private static void countLeaves(Vertex root) {
        if (root.getChild().size() != 0) {
            for (Vertex v: root.getChild())
                countLeaves(v);
        }
        else
            leavesCount++;
    }

    private static void radialPositions(Graph T, Vertex v, double alpha, double beta){
        if (v.isRoot()) {
            v.setX(0);
            v.setY(0);

            v.setR(0);
            v.setAngle(0);
        }

        int D = v.getDepth();

        double theta = alpha;

        double R_D = R + (R * D);

        if (!T.getRadials().contains(R_D))
            T.getRadials().add(R_D);

        int k = leavesCounter(v);
        leavesCount = 0;

        for (Vertex c: v.getChild()) {
            int lambda = leavesCounter(c);
            leavesCount = 0;

            double mu = theta + ((beta - alpha) * lambda / k);

            c.setVertexByPolar(R_D, (theta + mu) / 2);

            if (c.getChild().size() > 0)
                radialPositions(T, c, theta, mu);

            theta = mu;
        }
    }

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

        tree.calculateMaxDepth(root);

        //System.out.println(tree);
        System.out.println(tree.getVerticesByDepth());

        addFirstRadii(tree);

        radialPositions(tree, root, 0, 2 * Math.PI);

        System.out.println(tree.getVerticesByDepth());

        deleteIntersections(tree);

        System.out.println(tree.getVerticesByDepth());

        tree.fillRadials5();
    }
}