using Makie
using GeometryTypes

# Константы
const openBranch = "("
const closeBranch = ")"

const SHIRINA = 1500 # ширина (x)
const VISOTA = 800 # высота (y)
RADIUS = 30

# inputStr = "(((a+b)*(c+(d-(-b))))-(a/(d-(-b))))"
inputStr = "((a+b)+((a+b)*c))"

# Структука "вершина"
# n - номер вершины
# childLeft - номер вершины левого ребенка
# childRight - номер вершины правого ребенка
# textShort - текст "развернутой" вершины
# textFull - текст "свернутой" вершины
# level - уровень
# xLeft - левая граница по X
# xRight - правая граница по X
# x - координата x точки ((xLeft + xRight) / 2)
# y - координата y точки
# needChanged - нужно ли перерасчитывать вершину (для интерактивности), 1 - нужно, 0 - не нужно
mutable struct Vertex
    index
    childLeft
    childRight
    textShort
    textFull
    level
    xLeft
    xRight
    x
    y
    needChanged
end

# Массив с вершинами (изначальный)
verteces = []

# Массив с вершинами (текущий)
vertecesCurrent = []

function printVertecesCurrent()
    println("vertecesCurrent:")
    for i = 1:length(vertecesCurrent)
        println(vertecesCurrent[i])
    end
end

# разбивает строку вида (arg1[+*-/]arg2) на 2 аргумента и знак и возвращает arg1, sign, arg2
# (arg1 может отсутствовать (Например "(-b)"), в таком случае arg1 = "")
function bracketParse(str)
    # Изначально flag = 0
    # При встрече открывающей скобки (всегда первый элемент) переключаем flag = 1
    # Пока flag = 1, добавляем символы в arg1
    # При встрече одного из знаков [+*-/], переключаем flag = 2 и записываем текущий сивмол в sign
    # Пока flag = 2, добавляем символы в arg2
    # При встрече закрывающей скобки (всегда последний элемент) завершаем работу
    flag = 0

    sign = ""
    arg1 = ""
    arg2 = ""

    for i = 1:length(str)
        symbol = SubString(str, i, i)

        if symbol == openBranch
            flag = 1
        elseif occursin(r"[+*-/]", symbol)
            flag = 2
            sign = symbol
        elseif symbol == closeBranch
            break
        elseif flag == 1
            arg1 = arg1 * symbol
        elseif flag == 2
            arg2 = arg2 * symbol
        end

    end

    return arg1, sign, arg2
end

# Проверяет наличие выражения в массиве (сравнение идет по атрибуту textFull)
function checkExpInTextFull(exp)
    for i = 1:length(verteces)
        v = verteces[i]
        if v.textFull == exp
            return true
        end
    end
    return false
end

# Расчитывает массив verteces
function calculateVerteces(str)
    # Не открывающая скобка может быть только после последней замены, когда строка принимает вид vertex_X
    # В таком случае замена не нужна
    if SubString(str, 1, 1) == openBranch
        haveBranch = false
        indexStart = 1

        # Начальное количество элементов в массиве
        # Необходимо для замены новых добавившихся элментов
        startLengthVerteces = length(verteces)

        # Идем по строке, пока не встретим конструкцию "(arg1*sign*arg2)"
        for i = 1:length(str)
            symbol = SubString(str, i, i)

            if symbol == openBranch
                indexStart = i
                haveBranch = true
            elseif symbol == closeBranch && haveBranch
                # Вытаскиываем выражение из строки
                branchExp = SubString(str, indexStart, i)

                # Разбиваем выражение на аргументы и знак (arg1 может быть равен пустой строке). Например (-b)
                arg1, sign, arg2 = bracketParse(branchExp)
                indexLeft = 0
                indexRight = 0

                isArgsEqual = false

                # Если первый и второй аргументы равны, тогда добавляем в массив только второй аргумент
                if arg1 != arg2
                    if arg1 != ""
                        # Если аргумент не иммеет вид "vertex_X"
                        # Аргумент имеет такой вид только в том случае, если он уже был заменен
                        if !occursin(r"^vertex_[0-9]+", arg1)
                            # Если аргумент новый, то мы вычисляем его атрибуты и добавлем в массив
                            indexLeft = length(verteces) + 1
                            childLeft = 0
                            childRight = 0
                            textShort = arg1
                            textFull = arg1

                            level = 0
                            xLeft = 0
                            xRight = 0
                            x = 0
                            y = 0
                            needChanged = 0
                            push!(verteces, Vertex(indexLeft, childLeft, childRight, textShort, textFull, level, xLeft, xRight, x, y, needChanged))
                        else
                            # Если аргумент старый, то мы его не добавляем в массив.
                            # Вычисляем какой это аргумент по номеру и запоминаем этот номер для добавления ссылки на этот аргумент при занесении всего выражения
                            indexLeft = parse(Int64, SubString(arg1, 8, length(arg1)))
                        end
                    end
                else
                    isArgsEqual = true
                end

                # Все аналогично arg1, за исключением проверки на пустую строку, т.к. arg2 всегда присутствует
                if !occursin(r"^vertex_[0-9]+", arg2)
                    indexRight = length(verteces) + 1
                    childLeft = 0
                    childRight = 0
                    textShort = arg2
                    textFull = arg2

                    level = 0
                    xLeft = 0
                    xRight = 0
                    x = 0
                    y = 0
                    needChanged = 0
                    push!(verteces, Vertex(indexRight, childLeft, childRight, textShort, textFull, level, xLeft, xRight, x, y, needChanged))
                else
                    indexRight = parse(Int64, SubString(arg2, 8, length(arg2)))
                end

                # Если аргументы одинаковые, то мы добавляем только второй аргумент
                # В таком случае индекс левого и правого ребенка совпадает
                if isArgsEqual
                    indexLeft = indexRight
                end

                # Высчитываем атрибуты для всего выражения
                index = length(verteces) + 1
                childLeft = indexLeft
                childRight = indexRight
                textShort = sign

                textFull = "("
                # Если arg1 отсутсвует, тогда в полное выражение его не добавляем
                if childLeft != 0
                    textFull = textFull * verteces[childLeft].textFull
                end
                textFull = textFull * sign * verteces[childRight].textFull * ")"

                level = 0
                xLeft = 0
                xRight = 0
                x = 0
                y = 0
                needChanged = 0
                push!(verteces, Vertex(index, childLeft, childRight, textShort, textFull, level, xLeft, xRight, x, y, needChanged))

                # Заменяем добавленные выражения
                # Сначала заменяем последнее, т.к. оно включает предыдущие (если были)
                oldExp = branchExp
                newExp = "vertex_$(verteces[end].index)"
                str = replace(str, oldExp => newExp)

                # Если sign = "+|*", то мы замеянем не только arg1*sign*arg2, но и arg2*sign*arg1
                if occursin(r"[+*]", sign)
                    oldExp = "(" * arg2 * sign * arg1 * ")"
                    newExp = "vertex_$(verteces[end].index)"
                    str = replace(str, oldExp => newExp)
                end

                # После этого заменяем остальные (если были)
                for i = startLengthVerteces + 1:length(verteces) - 1
                    oldExp = verteces[i].textFull
                    newExp = "vertex_$(verteces[i].index)"
                    str = replace(str, oldExp => newExp)
                end

                # println(str)
                # Запускаем рекурсию для обновленной строки
                calculateVerteces(str)

                break
            end

        end


    else
        # Удаляет внешние скобки у выражений, т.к. они лишние
        for i = 1:length(verteces)
            v = verteces[i]
            if SubString(v.textFull, 1, 1) == openBranch
                v.textFull = SubString(v.textFull, 2, length(v.textFull) - 1)
            end
        end
    end
end

# Рассчитывает уровни в массиве verteces
# Рассчитывает границы по X в массиве verteces
function calculateVertecesLevelsAndBordersX(index, level, xLeft, xRight)
    v = verteces[index]

    # Если уровень равен нулю, значит он еще не инициализирован, в таком случае инициализриуем его и границы
    # Если уровень меньше текущего, тогда заменяем его на новый, и заменяекм границы
    if v.level == 0 || v.level < level
        v.level = level
        v.xLeft = xLeft
        v.xRight = xRight
    end

    # Рекурсия для левого
    childLeft = v.childLeft
    if childLeft != 0
        calculateVertecesLevelsAndBordersX(childLeft, level + 1, xLeft, xLeft + (xRight - xLeft) / 2)
    end

    # Рекурсия для правого
    childRight = v.childRight
    if childRight != 0
        if childLeft != 0
            calculateVertecesLevelsAndBordersX(childRight, level + 1, xLeft + (xRight - xLeft) / 2, xRight)
        else
            # Если childLeft == 0, т.е. всего один ребенок, то тогда границы не меняются
            calculateVertecesLevelsAndBordersX(childRight, level + 1, xLeft, xRight)
        end
    end
end

# Рассчитывает уровни в массиве vertecesCurrent
# Рассчитывает границы по X в массиве vertecesCurrent
function calculateVertecesCurrentLevelsAndBordersX(index, level, xLeft, xRight)
    v = vertecesCurrent[index]

    # Если уровень равен нулю, значит он еще не инициализирован, в таком случае инициализриуем его и границы
    # Если уровень меньше текущего, тогда заменяем его на новый, и заменяекм границы
    if v.needChanged == 1
        if v.level == 0 || v.level < level
            v.level = level
            v.xLeft = xLeft
            v.xRight = xRight
        end
    end

    # Рекурсия для левого
    childLeft = v.childLeft
    if childLeft != 0
        calculateVertecesCurrentLevelsAndBordersX(childLeft, level + 1, xLeft, xLeft + (xRight - xLeft) / 2)
    end

    # Рекурсия для правого
    childRight = v.childRight
    if childRight != 0
        if childLeft != 0
            calculateVertecesCurrentLevelsAndBordersX(childRight, level + 1, xLeft + (xRight - xLeft) / 2, xRight)
        else
            # Если childLeft == 0, т.е. всего один ребенок, то тогда границы не меняются
            calculateVertecesCurrentLevelsAndBordersX(childRight, level + 1, xLeft, xRight)
        end
    end
end

# Инициализирует массив vertecesCurrent
function initVertecesCurrent()
    for i = 1:length(verteces)
        v = verteces[i]
        # Создаем копию объекта, чтобы не было ссылок
        push!(
            vertecesCurrent,
            Vertex(v.index, v.childLeft, v.childRight, v.textShort, v.textFull, v.level, v.xLeft, v.xRight, v.x, v.y, v.needChanged)
        )
    end
    recalcDownUpVertecesCurrent()
    # printVertecesCurrent()
    # recalcAndSwapChildrenIfNeed()
end

# Очищает уровни и позиции всех вершин, у которых needChanged = 1 в массиве vertecesCurrent для перерасчета
function clearLevelsAndPosVertecesCurrent()
    for i = 1:length(vertecesCurrent)
        v = vertecesCurrent[i]
        if v.needChanged == 1
            v.level = 0
            v.xLeft = 0
            v.xRight = 0
            v.x = 0
            v.y = 0
        end
    end
end

# Перерасчиывает массив vertecesCurrent снизу вверх
function recalcDownUpVertecesCurrent()
    level = getMaxLevelVerteces() - 1
    while level >= 1
        for i = 1:length(vertecesCurrent)
            v = vertecesCurrent[i]
            if v.level == level
                if v.childLeft != 0 && v.childRight != 0
                    v.x = (vertecesCurrent[v.childLeft].x + vertecesCurrent[v.childRight].x) / 2
                elseif v.childLeft != 0
                    v.x = vertecesCurrent[v.childLeft].x
                elseif v.childRight != 0
                    v.x = vertecesCurrent[v.childRight].x
                end
            end
        end
        level = level - 1
    end
end

# Меняет детей местами, если левый находится справа, а правый слева
function recalcAndSwapChildrenIfNeed()
    maxLevel = getMaxLevelVerteces()
    # Идем по всем уровням сверху вниз
    for level = 1:maxLevel
        # Для каждого уровня идем по массиву
        for i = 1:length(vertecesCurrent)
            v = vertecesCurrent[i]
            # Если встретили элемент нужного нам уровня
            if v.level == level
                # Проверяем, правильно ли у него расположены дети
                if vertecesCurrent[v.childLeft].x > vertecesCurrent[v.childRight].x
                    # Если дети расположены не правильно, то меняем их x, xLeft, xRight местами
                    vLeft = vertecesCurrent[v.childLeft]
                    vRight = vertecesCurrent[v.childRight]

                    vLeft.x, vLeft.xLeft, vLeft.xRight, vRight.x, vRight.xLeft, vRight.xRight = vRight.x, vRight.xLeft, vRight.xRight, vLeft.x, vLeft.xLeft, vLeft.xRight

                    # Перераситываем координаты для их детей
                    # Сначала показываем, что для всех их детей надо пересчитать координаты, устанавливая флаг needChanged = 1, и удаляя их координаты x, y, xLeft, xRight
                    if vLeft.childLeft != 0
                        setNeedChangedOnChildren(vLeft.childLeft)
                    end
                    if vLeft.childRight != 0
                        setNeedChangedOnChildren(vLeft.childRight)
                    end
                    if vRight.childLeft != 0
                        setNeedChangedOnChildren(vRight.childLeft)
                    end
                    if vRight.childRight != 0
                        setNeedChangedOnChildren(vRight.childRight)
                    end

                    clearLevelsAndPosVertecesCurrent()
                    calculateVertecesCurrentLevelsAndBordersX(length(vertecesCurrent), 1, 0, SHIRINA)
                    calculatePosVertecesCurrent()
                    setNeedChangedZero()
                    # recalcDownUpVertecesCurrent()

                    return

                end
            end
        end
    end
end

# Перерасчиывает массив vertecesCurrent
function recalcVertecesCurrent()
    clearLevelsAndPosVertecesCurrent()
    calculateVertecesCurrentLevelsAndBordersX(length(vertecesCurrent), 1, 0, SHIRINA)
    calculatePosVertecesCurrent()
    setNeedChangedZero()
    recalcDownUpVertecesCurrent()

    # recalcAndSwapChildrenIfNeed()
end

# Возвращает максимальный уровень из массива verteces
function getMaxLevelVerteces()
    level = 1
    for i = 1:length(verteces)
        if verteces[i].level > level
            level = verteces[i].level
        end
    end
    return level
end

# Возвращает максимальный уровень из массива vertecesCurrent
function getMaxLevelVertecesCurrent()
    level = 1
    for i = 1:length(vertecesCurrent)
        if vertecesCurrent[i].level > level
            level = vertecesCurrent[i].level
        end
    end
    return level
end

# Расчитывает позицию (x, y) вершины массива verteces
function calculatePosVerteces()
    maxLevel = getMaxLevelVerteces()

    for i = 1:length(verteces)
        v = verteces[i]
        v.x = (v.xLeft + v.xRight) / 2
        v.y = VISOTA / (maxLevel + 1) * (maxLevel - v.level + 1)
    end
end

# Расчитывает позицию (x, y) вершины массива vertecesCurrent
function calculatePosVertecesCurrent()
    # maxLevel = getMaxLevelVertecesCurrent()
    maxLevel = getMaxLevelVerteces()

    for i = 1:length(vertecesCurrent)
        v = vertecesCurrent[i]
        if v.needChanged == 1
            v.x = (v.xLeft + v.xRight) / 2
            v.y = VISOTA / (maxLevel + 1) * (maxLevel - v.level + 1)
        end
    end
end

# Проверяет, лежит ли точка (x, y) внутри круга с центром в точке (xc, yc) и радиусом (радиус задан как глобальная константа)
function checkVertexInCircle(x, y, xc, yc)
    if (x - xc) ^ 2 + (y - yc) ^ 2 <= RADIUS ^ 2
        return true
    else
        return false
    end
end

# Проверяет, лежит ли точка (x, y) внутри какой-либо вершины из массива verteces
function checkPointInVertecesCurrent(x, y)
    for i = 1:length(vertecesCurrent)
        v = vertecesCurrent[i]
        if checkVertexInCircle(x, y, v.x, v.y)
            return i
        end
    end
    return -1
end

# После перерасчета устанавливает needChanged = 0 у всех
function setNeedChangedZero()
    for i = 1:length(vertecesCurrent)
        v = vertecesCurrent[i]
        v.needChanged = 0
    end
end

# Устанавливает у вершины с данным индексом и у всех ее детей needChanged = 1
function setNeedChangedOnChildren(index)
    v = vertecesCurrent[index]
    v.needChanged = 1
    if v.childLeft != 0
        setNeedChangedOnChildren(v.childLeft)
    end
    if v.childRight != 0
        setNeedChangedOnChildren(v.childRight)
    end
end

# Интерактивность
function interactivity(scene, index)
    v = vertecesCurrent[index]

    # Развертка
    if v.childLeft == 0 && v.childRight == 0
        v.childLeft = verteces[index].childLeft
        if v.childLeft != 0
            setNeedChangedOnChildren(v.childLeft)
        end
        v.childRight = verteces[index].childRight
        if v.childRight != 0
            setNeedChangedOnChildren(v.childRight)
        end
        v.textShort = verteces[index].textShort
    else # Свертка
        # Обозначаем needChanged = 1 у всех детей, для того, чтобы пересчитать координаты
        if v.childLeft != 0
            setNeedChangedOnChildren(v.childLeft)
        end
        if v.childRight != 0
            setNeedChangedOnChildren(v.childRight)
        end

        v.childLeft = 0
        v.childRight = 0
        v.textShort = v.textFull
    end

    recalcVertecesCurrent()
    drawGraph(scene)
end

# Очищает сцену
function clearScene(scene)
    arr = Point{2,Float32}[]
    xLeft = 0
    xRight = 500
    yTop = 500
    yBot = 0
    mas = []
    push!(arr, Point2f0(xLeft, yBot))
    push!(arr, Point2f0(xLeft, yTop))
    push!(arr, Point2f0(xRight, yTop))
    push!(arr, Point2f0(xRight, yBot))
    push!(arr, Point2f0(xLeft, yBot))
    poly!(scene, arr, color = :white, strokewidth = 10000, strokecolor = :white)
end

# Рисует круг в точке (x, y) с текстом "text" внутри
function drawCircleWithText(scene, x, y, text)
    radius = convert(Float32, RADIUS)

    points = decompose(Point2f0, Circle(Point2f0(x, y), radius))
    poly!(scene, points, color = :white, strokewidth = 2, strokecolor = :black)

    text!(scene, text, textsize = 20, position = (x, y), align = (:center, :center))
end

# Рисует линию из точки (x1, y1) в точку (x2, y2)
function drawLine(scene, x1, y1, x2, y2)
    linesegments!(scene, [Point(x1,y1)=> Point(x2,y2)] )
end

# Проверяет наличие элемента в массиве
function checkElemInArray(elem, arr)
    for i = 1:length(arr)
        if arr[i] == elem
            return true
        end
    end
    return false
end

# Рисует все вершины
function drawCircles(scene, index, drawnVerteces)
    v = vertecesCurrent[index]
    drawCircleWithText(scene, v.x, v.y, v.textShort)
    # Добавляем в массив отрисованных вершин текущую вершину
    push!(drawnVerteces, index)

    # Если левый ребенок еще не был отрисован
    if !checkElemInArray(v.childLeft, drawnVerteces)
        if v.childLeft != 0
            drawCircles(scene, v.childLeft, drawnVerteces)
        end
    end

    # Если правый ребенок еще не был отрисован
    if !checkElemInArray(v.childRight, drawnVerteces)
        if v.childRight != 0
            drawCircles(scene, v.childRight, drawnVerteces)
        end
    end
end

# Переводит градусы в радианы
function degreeToRad(degree)
    return degree * pi / 180
end

# Рисует "стрелку"
function drawArrow(scene)
end

# Рисует ребра графа от заданной вершины, а так же все ребра "детей" этой вершины
function drawEdges(scene, index)
    # Угол, на который смещаются ребра относительно оси OX
    offsetAngle = 75

    v = vertecesCurrent[index]
    x = v.x
    y = v.y

    if v.childLeft != 0
        vLeft = vertecesCurrent[v.childLeft]

        xLeft1 = x - RADIUS * cos(degreeToRad(offsetAngle))
        yLeft1 = y - RADIUS * sin(degreeToRad(offsetAngle))

        xLeft2 = vLeft.x
        yLeft2 = vLeft.y + RADIUS

        drawLine(scene, xLeft1, yLeft1, xLeft2, yLeft2)
        drawEdges(scene, v.childLeft)
    end

    if v.childRight != 0
        if v.childLeft != 0
            vRight = vertecesCurrent[v.childRight]

            xRight1 = x + RADIUS * cos(degreeToRad(offsetAngle))
            yRight1 = y - RADIUS * sin(degreeToRad(offsetAngle))

            xRight2 = vRight.x
            yRight2 = vRight.y + RADIUS

            drawLine(scene, xRight1, yRight1, xRight2, yRight2)
            drawEdges(scene, v.childRight)
        else
            vRight = vertecesCurrent[v.childRight]

            xRight1 = x
            yRight1 = y - RADIUS

            xRight2 = vRight.x
            yRight2 = vRight.y + RADIUS

            drawLine(scene, xRight1, yRight1, xRight2, yRight2)
            drawEdges(scene, v.childRight)
        end


    end
end

# Рисует граф
function drawGraph(scene)
    clearScene(scene)

    # Массив в котором содержатся все отрисованные вершины
    drawnVerteces = []
    drawCircles(scene, length(vertecesCurrent), drawnVerteces)

    drawEdges(scene, length(vertecesCurrent))
end

# Добавляем события на кнопки мыши
function addMouseEvents(scene)
    on(scene.events.mousebuttons) do buttons
       if ispressed(scene, Mouse.left)
           pos = to_world(scene, Point2f0(scene.events.mouseposition[]))

           numberVertex = checkPointInVertecesCurrent(pos[1], pos[2])
           if numberVertex != -1
               interactivity(scene, numberVertex)
           end
       end
       return
    end
end

# Рисует формулу
function drawFormula(formula)
    calculateVerteces(formula)
    calculateVertecesLevelsAndBordersX(length(verteces), 1, 0, SHIRINA)
    calculatePosVerteces()

    initVertecesCurrent()

    scene = Scene(resolution = (SHIRINA, VISOTA))
    addMouseEvents(scene)
    # Рисуем граф
    drawGraph(scene)

    # Без этого не рисуется ????????????????????????
    clicks = Node(Point2f0[(0,0)])
    scatter!(scene, clicks, color = :red, marker = '+', markersize = 0)
end