package com.company;

import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;

class BinaryTree {
    Node root = null;

    Node addToTree(Node node, double value) {
        if(node == null) {
            Node root = new Node(value);
            root.path.add(root);
            return root;
        }

        if(value < node.value) {
            if(node.left == null) {
                node.left = new Node(value);
                node.left.path.addAll(node.path);
                node.left.path.add(node.left);
            } else {
                addToTree(node.left, value);
            }
        } else if(value > node.value) {
            if(node.right == null) {
                node.right = new Node(value);
                node.right.path.addAll(node.path);
                node.right.path.add(node.right);
            } else {
                addToTree(node.right, value);
            }
        }

        return node;
    }

    void removeVertex(Node node) {
        int size = node.path.size();
        if(size - 2 > -1) {
            Node parent = node.path.get(size-2);
            if(parent.left == node)
                parent.left = null;
            else if(parent.right == node)
                parent.right = null;
        }
    }

    boolean contains(double value, Node node) {
        if(node == null)
            return false;

        if(value == node.value)
            return true;

        if(value < node.value)
            return contains(value, node.left);
        else if(value > node.value)
            return contains(value, node.right);

        return false;
    }

    String takeVisual() {
        if(root == null)
           return "Невозможно отобразить пустое дерево";

        StringBuilder tree = new StringBuilder();
        tree.append(root.value);
        String pointerLeft;
        if (root.right != null)
            pointerLeft = "+--";
        else
            pointerLeft = "L--";

        takeNodesString(tree, "", pointerLeft, root.left, root.right != null);
        takeNodesString(tree, "", "L--", root.right, false);
        return tree.toString();
    }

    void takeNodesString(StringBuilder tree, String padding, String pointer, Node node, boolean hasRightNode) {
        if (node != null) {
            tree.append("\n").append(padding).append(pointer).append(node.value < 0 ? "(" + node.value + ")" : node.value);
            if (hasRightNode)
                padding += "¦  ";
            else
                padding += "   ";

            if (node.right != null)
                pointer = "+--";
            else
                pointer = "L--";

            takeNodesString(tree, padding, pointer, node.left, node.right != null);
            takeNodesString(tree, padding, "L--", node.right, false);
        }
    }

    ArrayList<Node> maxPathRecursive(Node node, ArrayList<Node> path) {
        if(node == null)
            return path;
        ArrayList<Node> maxPath = new ArrayList<>();
        if(node.path.size() > maxPath.size())
            maxPath = node.path;
        ArrayList<Node> leftPath = maxPathRecursive(node.left, maxPath);
        ArrayList<Node> rightPath = maxPathRecursive(node.right, maxPath);
        if(leftPath.size() > rightPath.size())
            maxPath = leftPath;
        else
            maxPath = rightPath;
        return maxPath;
    }

    ArrayList<Node> maxPath() {
        return maxPathRecursive(root, root.path);
    }

    void add(double value) {
        root = addToTree(root, value);
    }
}

class Node {
    double value;
    Node left = null;
    Node right = null;
    ArrayList<Node> path = new ArrayList<>();
    Node(double value) {
        this.value = value;
    }
}

public class Main {
    static BinaryTree inputTreeFromConsole(Scanner scan) {
        boolean continueCycle = true;
        int i = 1;
        BinaryTree tree = new BinaryTree();
        System.out.println("Введите [стоп], если хотите прекратить ввод");
        while(continueCycle) {
            boolean notCorrect = true;
            while(notCorrect) {
                System.out.println("Введите " + i + "-ю вершину дерева");
                String value = scan.nextLine();
                if(value.equals("стоп")) {
                    continueCycle = false;
                    notCorrect = false;
                } else {
                    try {
                        double elem = Double.parseDouble(value);
                        if(!tree.contains(elem, tree.root)) {
                            tree.add(elem);
                            notCorrect = false;
                        } else {
                            System.out.println("Такая вершина уже существует, повторите ввод");
                        }
                    } catch (Exception err) {
                        System.out.println("Вершина дерева должна быть вещественным числом, повторите ввод");
                    }
                }
            }
            i++;
        }
        return tree;
    }

    static BinaryTree inputTreeFromFile(Scanner scan) {
        String filePath = "";
        boolean notCorrect = true;
        BinaryTree tree = new BinaryTree();
        while(notCorrect) {
            System.out.println("Введите путь к файлу");
            filePath = scan.nextLine();
            try(FileReader fr = new FileReader(filePath)) {
                Scanner frScan = new Scanner(fr);
                String nums = frScan.nextLine().trim();
                String[] arr = nums.split("\\s+");
                for(String el : arr)
                    tree.add(Double.parseDouble(el));
                notCorrect = false;
            } catch (Exception err) {
                System.out.println("Произошла ошибка при открытии файла, убедитесь, что файл существует, либо проверьте правильность введенных данных. В файле должны содержаться вещественные числа, введенные в одну строку и разделенные одиночным пробелом");
            }
        }
        return tree;
    }

    static BinaryTree inputTree(Scanner scan) {
        String choice = "";
        boolean notCorrect = true;
        System.out.println("Введите [c], если хотите ввести данные из консоли, либо [f], если хотите ввести данные из файла");
        while(notCorrect) {
            choice = scan.nextLine();
            if(choice.equals("f") || choice.equals("c"))
                notCorrect = false;
            else
                System.out.println("Введите либо [c], либо [f]");
        }

        if(choice.equals("c"))
            return inputTreeFromConsole(scan);
        return inputTreeFromFile(scan);
    }

    static void showMaxPath(ArrayList<Node> path) {
        for(Node node : path)
            System.out.print(node.value + " ");
        System.out.println("");
    }

    static void deleteCentralVertex(BinaryTree tree) {
        if(tree.root != null) {
            ArrayList<Node> maxPath = tree.maxPath();
            System.out.println("Максимальный путь:");
            showMaxPath(maxPath);
            boolean isCentralVertexExists = maxPath.size() > 1 && maxPath.size() % 2 != 0;
            if(isCentralVertexExists) {
                Node centralVertex = maxPath.get(maxPath.size() / 2);
                double vertexValue = centralVertex.value;
                tree.removeVertex(centralVertex);
                System.out.println("Дерево после удаления центральной вершины " + vertexValue + ":");
                System.out.println(tree.takeVisual());
            } else {
                System.out.println("Максимальный путь данного дерева не содержит центральную вершину");
            }
        }
    }

    static void saveResult(String treeStr, Scanner scan) {
        System.out.println("Хотите сохранить результат в файл? [д/н]");
        boolean notCorrect = true;
        String choice = "";
        while(notCorrect) {
            choice = scan.nextLine();
            if(choice.equals("д") || choice.equals("н"))
                notCorrect = false;
            else
                System.out.println("Введите либо [д], либо [н]");
        }

        if(choice.equals("д")) {
            System.out.println("Введите имя файла");
            String fileName = scan.nextLine() + ".txt";
            try(FileWriter fw = new FileWriter(fileName)) {
                fw.write(treeStr);
                System.out.println("Результат успешно сохранен в файл " + fileName);
            } catch (IOException err) {
                System.out.println("Возникла ошибка при записи результата в файл");
            }
        }
    }

    public static void main(String[] args) {
        System.out.println("Данная программа позволяет создать дерево двоичного поиска, найти максимальный путь между вершинами и удалить центральную вершину этого пути");
        Scanner scan = new Scanner(System.in);
        BinaryTree tree = inputTree(scan);
        System.out.println("Введенное дерево:");
        System.out.println(tree.takeVisual());
        deleteCentralVertex(tree);
        saveResult(tree.takeVisual(), scan);
    }
}