# v_0.9.5
# https://www.enjoyalgorithms.com/blog/binary-tree-traversals-preorder-inorder-postorder

# BT (Node) Naive implementation

# 1. Naimplementujte třídou (class) Node pro vrcholy
# datové struktury BT (zatim bez operaci, a bez BST)

# Připomenutí BT
# BT: a) Node
#     b) None (Nic, Nill, ...)

# Node:
# ----------------
# |     Dato     |
# ----------------
# | left | right |
# ----------------
# kde left a right jsou zase BT


from xmlrpc.server import list_public_methods


class Node:
    def __init__(self, k, l=None, p=None):
        self.dato = k
        self.l = l
        self.p = p


# 1.1 Rucne vytvorte zadaný BST (BT) t
# (zatim nemame zadne operace typu insert, delete, apod;
# strom tvorime "rucne" vhodným voláním)

# BST t
#         10
#    5          15
# 1     7    12    20


# vytvorim instanci Nodu s hodnotou 10
# a ulozim si ji do promenne t
t = Node(10)

# co mi vypise print(t)?
print(t)


print(t.dato)
print(t.l)
print(t.p)


# o(tazka): jak budeme postupovat nyni?

# pridam (rucne) vrcholy 5 a 15
t.l = Node(5)
t.p = Node(15)


# o: jak vypisu obsah vrcholu 5 a 10?


print(t.dato)
print(t.l)  # nyni uz vypisi adresu vrcholu 5
print(t.l.dato)
print(t.p.dato)

# z(adani): rucne dovytvorte zadany BST t


t.l.l = Node(1)
t.l.p = Node(7)
print(t.l.p.dato)

t.l.p.l = Node(6)
t.l.p.p = Node(8)

t.p.p = Node(30)
t.p.p.l = Node(25)

print(t.p.p.dato)

# zkuste vytvorit strom "na jeden radek" kodu
# ve smyslu rekurzvního vkladání vrcholů

# BST
#         10
#    5         20
# 1     7          30


t = Node(10, Node(5, Node(1), Node(7)), Node(20, None, Node(30)))


# 2. Napiste rekurzivni funkci traverz(t),
# ktera systematicky (DFS) projde binarni strom
# a pro kazdy vrchol (prave jednou) vypise na konzoly hodnotu
# ve vrcholu ulozenou
# t je kořen stromu


# logika průchodu BT,
# kde garantovaně projdu všechny vrcholy
# a "nedělám zbytečnou práci"


# zkusme nejdrive navrhnout meta algoritmus


# idea:
#     a] proved akci/proces na vrholu t
#     b] rekuzivne spracuj potomky


def traverz(t):
    if t != None:
        print(t.dato)
        traverz(t.l)
        traverz(t.p)


# komentovana verze funkce traverz(t)
def traverz(t):
    # Co dostane funkce traverz za vstup?
    # BT ... Co je BT (dle def)?
    # Bud:  a) Node nebo za
    #       b) None

    if t != None:
        # kdyz None nedelam nic, koncim
        # kdyz Node vyresim ho
        print(t.dato)  # na vrcholu provedu akci

        # a vyresim potomky
        traverz(t.l)  # vyresim leveho potomka
        traverz(t.p)  # vyresim praveho potomka


# jeste nez si kod pustime, zkuste urcit jakou posloupnost hodnot
# tento rekurzuvni algorimus vypise; teoreticke cviceni


# a podivejme se na vysledek
traverz(t)

# poznamka: provedli jsme traverz bin stromem DFS preOrder


# 3. Mohu nejak zmenit poradi vypisu vrcholu? (stale rekurzivni dfs)


# note: prohodit volani z LP na PL


def traverzPL(t):
    if t != None:
        print(t.dato)
        traverzPL(t.p)
        traverzPL(t.l)


# jeste nez si kod pustime, zkuste urcit jakou posloupnost hodnot
# tento rekurzuvni algorimus vypise; teoreticke cviceni

traverzPL(t)

# Note: to by slo, ale neni to az tak zajimave,
# snad jen dostali jsme vypis v poradi zasobniku
# a ano volba poradi spracovani podstromu je dulezity optimalizcni prvek,
# v tuto chvíli je beyond


# 4. tak zkusme to jinak? jiny napad? jak zmenit poradi vypisu?


def traverzPostOrder(t):
    if t != None:
        # print(t.dato)
        traverzPostOrder(t.l)
        # print(t.dato)
        traverzPostOrder(t.p)
        print(t.dato)


# a zase zkusme si nejdriv urcit poradi vypisu pred spustenim kodu
traverzPostOrder(t)

# poznamka: provedli jsme traverz DFS postOrder
# idea je provest akci na vrcholu, a hned jit do (nenavstiveneho) potomka, a v potomkovi zase provest akci a jit do nenavstiveneho potomka,
# teprve kdyz uz nemam kam dale (hloubeji) jit vracim se do rodice (tomu se rika backtrack) a zkusim navtivit jineho
# nenavstiveneho potomka a tepreve pokud uz zadny neni provedu backtrack do rodice

# kdy provadime akci?
# kdyz vstupujeme do vrcholu vs kdyz vrchol ukoncujeme/opoustime
# resp.
# akce pred spracovanim potomku vs po jejich spracovani
# akce to tom kdyz uz znam vstupy/hodnoty/vysledky z potomku

# vycisleni aritmetickeho vyrazu ve reprezentaci stromu
# "vycisleni behu programu"


# 1.9 Projdete BST t tak, ze vypiste setridene hodnoty uzlu
# od nejmensiho k nejvetsimu


# pro bin stromy mame jeste INorder


def traverzInOrder(t):
    if t != None:
        # print(t.dato)
        traverzInOrder(t.l)
        print(t.dato)
        traverzInOrder(t.p)
        # print(t.dato)


traverzInOrder(t)

# https://www.enjoyalgorithms.com/blog/binary-tree-traversals-preorder-inorder-postorder


# 4. Upravte funkci traverz(t) tak,
# aby spocitala soucet vsech cisel ve strome a vratila ho

# nejdrive tužka a papír; ideu algoritmu,
# rozmyslete si co funkce bere jako vstup a co vraci jako vystup
# nasledne funkci napiste v pseudokodu


def traverzSum(t):
    if t != None:
        return traverzSum(t.l) + traverzSum(t.p) + t.dato
    else:
        return 0


print(traverzSum(t))

# poznamka: (konecna) rekurze v principu obsahuje dve casti:
# a] rekurzivni volani
# b] zastavovaci podminku


# 4. Upravte funkci traverz tak,
# aby spocitala (maximalni) hloubku stromu a vratila ji;
# - hloubka stromu je definovana jako: delka nejdelsi cesty
# z korene stromu do nejakeho listu (mereno poctem hran cesty)


# co vlastne delame?
# a] prochazime strom a pocitame jeho nejakou globalni charakteristiku
# b] (zasadni) rozmyslime, jak funguje rekuzre resp pruchod stromem - coz potrebujeme k vypoctu charakteristiky
# c] (zasadni) jak predavat data behem rekurzivniho volani (mutable vs imutable)


# note: dva druhy rekurze: a] botom up rekurze, b] top down rekurze
# note: funkce vraci spatny vysledek. v cem je spatne a proc?


# nekorektni verze, proc vraci +1 vetsi hloubku?
# note: botom up rekurze
def traverzDepth(t):
    if t != None:
        return max(traverzDepth(t.l), traverzDepth(t.p)) + 1
    else:
        # musi zde byt 0? co vraci funkce, ktera neobsahuje return?
        return 0


print(traverzDepth(t))


# nekorektni verze, proc vraci +1 vetsi hloubku?
# note: top down rekurze
def traverzDepth(t, h=0):
    if t != None:
        return max(traverzDepth(t.l, h + 1), traverzDepth(t.p, h + 1))
    else:
        return h


print(traverzDepth(t))


def traverzDepth(t):
    if t != None:
        if t.l != None:
            dLeft = traverzDepth(t.l)
        else:
            return 0

        if t.p != None:
            dRight = traverzDepth(t.p)
        else:
            return 0

        return max(dLeft, dRight) + 1
    else:
        # musi zde byt 0? co vraci funkce, ktera neobsahuje return?
        return 0


print(traverzDepth(t))


# 5. Vytvorte funkci traverzReturnValues(t), ktera funguje analogicky jako funkce traverz,
# projde systematicky strom
# avsak hodnoty nevypisuje, ale vsechny je vraci ulozene v listu (binaryTree2List),
# kazdou prave jednou
# "projit strom a v listu vratit vsechny hodnoty"

# a] (prasarna) pres global variable
# b] lokal mutable var


# b]
def traverzReturnValues(t, l=[]):
    if t != None:
        l.append(t.dato)
        traverzReturnValues(t.l, l)
        traverzReturnValues(t.p, l)

    return l


print(traverzReturnValues(t))


# a]
l = []


def traverzReturnValuesGlob(t):
    if t != None:
        l.append(t.dato)
        traverzReturnValuesGlob(t.l)
        traverzReturnValuesGlob(t.p)

    return l


print("Glob variable: ", traverzReturnValuesGlob(t))
# print("Glob variable: ", l)


# 5.1 Rekurzivne projdete BST a spocitejte pocet vrcholu v kazde vrstve
# a] pomoci dict
# b] pomoci listu


def countNodesInTreeLayer(t, h=0, l=[]):
    if t != None:
        if len(l) <= h:
            l.append(0)
            l[h] += 1
        else:
            l[h] += 1

        countNodesInTreeLayer(t.l, h + 1, l)
        countNodesInTreeLayer(t.p, h + 1, l)

    return l


# print(len([]))
# countNodesInTreeLayer(None)
print(countNodesInTreeLayer(t))

# 5.2 Rekurzivne projdete BST a vratte list Listu,
# kde kazdy (vnitrni) list obsahuje vrcholy dane vrstvy z leva doprava
# "ulozit hodnoty nodu po vrstvach"


def getListsNodesInTreeLayer(t, h=0, l=[]):
    if t != None:
        if len(l) <= h:
            l.append([t.dato])
        else:
            l[h].append(t.dato)

        getListsNodesInTreeLayer(t.l, h + 1, l)
        getListsNodesInTreeLayer(t.p, h + 1, l)

    return l


print(getListsNodesInTreeLayer(t))


# 6. Napiste funkci, ktera vytisknete vertikalne BST (kdy nahore je nejvetsi hodnota)
# velikost odsazeni je parametr (n cele kladne cislo) funkce,
# ktery udava pocet mezer za jednu vrstvu hloubky
# stale rekurzivni algoritmus
# (za "prazdne nody" se neprovadi tisk; co vrchol to jeden radek)

# Priklad

# pro zadany strom
#         10
#    5          15
# 1     7    12    20

# vytiskne
#         20
#     15
#         12
# 10
#         7
#     5
#         1


def printBSTVert(t, n=3, h=0):
    if t != None:
        printBSTVert(t.p, n, h + 1)
        # print(t.dato)
        # print(" "*(n*h), t.dato)
        print(f"{t.dato:{n * h}d}")
        printBSTVert(t.l, n, h + 1)


printBSTVert(t, 4)
printBSTVert(t, 7)


# def printBSTVert2(t, n=3, h=0):
#     hPodstromu = traverzDepth(t)-1
#     if hPodstromu < 0:
#         nSpace = 0
#     else:
#         nSpace = 2**hPodstromu

#     # print(f"{t.dato}: {hPodstromu} {2**hPodstromu} {nSpace}")

#     if t != None:
#         if t.p:
#             printBSTVert2(t.p, n, h+1)
#         else:
#             s = "\n"*nSpace
#             print(s, end="")

#         print(f"{t.dato:{n*h}d}")

#         if t.l:
#             printBSTVert2(t.l, n, h+1)
#         else:
#             s = "\n"*nSpace
#             print(s, end="")

# printBSTVert2(t, 7)


# 7. Strom tisk horiz - treba fronta

# DALSI PRIKLADY NA REKURZI

# 9. Napište rekurzuvní funkci isPalindrom(string), která na vstupu dostane řetězec
# a vrátí True v případě, že se jedná o palindrom
# a False pokud se o palindrom nejedná; prázdný řetězec je považován na palindrom


def isPalindrom(str):
    print(str)

    if (len(str) == 0) or (len(str) == 1):
        return True
    else:
        if str[0] == str[-1]:
            # print(str[0]+" "+str[-1])
            return isPalindrom(str[1:-1])

        else:
            return False


print(isPalindrom("rotor"))
print(isPalindrom("r"))
print(isPalindrom("rr"))
print(isPalindrom("ro"))
print(isPalindrom("rrrr"))
print(isPalindrom("rrrro"))
print(isPalindrom(""))


# kviiiiz: co vypise? a proc?
print([].append(5))

print(print(""))

s = []
s = s.append(0)
print(s)

s = []
s.append(0)
print(s)


# 10. Napište rekurzivní funkci reverse(list), která na vstupu dostane list
# a vrátí ho v obráceném (reverzním) pořadí


def reverse(list):
    if len(list) <= 1:
        return list
    else:
        head = list.pop(0)
        tail = list
        print(head)
        print(tail)

        reverse(tail).append(head)
        return tail


print(reverse([1, 2, 3]))
print(reverse([1, 2, 3, 4]))
print(reverse([1, 2, 3, 4, 5]))


# 20. PRIKLADY NA BST

# 20.1 Def: BST, operace: find, insert, delete

# 21. Na nasi "Node" definici BST implementujte funkci: a) find(), b) insert()
# - co funkce dostavaji jako parametry a co vraci?


def find(t, key):
    if t == None:
        return t
    elif t.dato == key:
        return t
    elif key < t.dato:
        return find(t.l, key)
    else:
        return find(t.p, key)


printBSTVert(t)
ref_on_found_node = find(t, 100)
print(f"na adrese: {ref_on_found_node}")

ref_on_found_node = find(t, 10)
print(f"{ref_on_found_node.dato} na adrese: {ref_on_found_node}")

ref_on_found_node = find(t, 20)
print(f"{ref_on_found_node.dato} na adrese: {ref_on_found_node}")

ref_on_found_node = find(t, 1)
print(f"{ref_on_found_node.dato} na adrese: {ref_on_found_node}")


def insert(t, key):
    if t == None:
        t = Node(key)
    else:
        if key < t.dato:
            if t.l == None:
                t.l = Node(key)
            else:
                insert(t.l, key)
        else:
            if t.p == None:
                t.p = Node(key)
            else:
                insert(t.p, key)
    return t


t2 = None
t2 = insert(t2, 5)
t2 = insert(t2, 10)
t2 = insert(t2, 50)
# printBSTVert(t2)
t2 = insert(t2, 3)
t2 = insert(t2, 1)
t2 = insert(t2, 7)
printBSTVert(t2)


# 30. DFS a BFS

# Univerzalni algoritmus pro abstraktni datovou strukturu d
# a] d:= Stack
# b] d:= Frontu

# Jak implemtovat Stack v Pythonu?
# 1. Pomoci listu
# kde
# push() -> .appaned()
# pop() -> .pop()

# 2.
# 3.


def dfs(t):
    if t != None:
        s = []
        s.append(t)

        while len(s) > 0:
            v = s.pop()
            print(v.dato)
            #    print(v) # tiskne odkazy na cele objekty typu Node()

            if v.l != None:
                s.append(v.l)

            if v.p != None:
                s.append(v.p)


print("DFS: Stack ")
dfs(t)

print("DFS: Rekurze")
traverzPL(t)


import collections as coll

# Jak implemtovat Frontu v Pythonu?
# 1. Pomoci listu
# kde
# push()/Q/Insert -> .appaned()
# pop() -> .pop(0)

# 2. Collection: https://docs.python.org/3/library/collections.html
# 3.

def bfs(t):
    if t != None:
        q = coll.deque()

        q.append(t)

        while len(q) > 0:
            v = q.popleft()
            print(v.dato)

            if v.l != None:
                q.append(v.l)

            if v.p != None:
                q.append(v.p)


print("BFS: ")
bfs(t)


# 30.7 Porovnani DFS a BFS
# a] pametovych naroku (v zavislosti na hloubce stromu)
# b] rychlost nalezeni reseni (hloubka stromu; limitDepthDFS)


# 30.13 Priprava na domaci ukol Konem po sachovnici 

class Stack:
    def __init__(self):
        self.s = []

    def push(self, x):
        self.s.append(x)

    def pop(self):
        return self.s.pop()

    def isEmpty(self):
        if len(self.s) > 0:
            return False
        else:
            return True