from __future__ import annotations
from dataclasses import dataclass
import random

@dataclass
class Node :
    key:int
    #value: str
    left:Node|None = None
    right:Node|None = None
    parent:Node|None = None #riferimento al padre

@dataclass
class Tree :
    root:Node|None = None

def insert (t:Tree, key:int) -> None:
    nuovo = Node (key)
    i:Node|None = t.root
    precedente:Node|None = None
    while i is not None :
        precedente = i
        if key > i.key:  
            i = i.right
        elif key < i.key:  
            i = i.left
        else: #non posso inserire chiavi duplicate
            return
    if precedente is None:
        # inserisco il primo node dell'albero
        t.root = nuovo
    else:
        nuovo.parent = precedente
        if key > precedente.key:
            precedente.right = nuovo
        else:
            precedente.left = nuovo

# metodo che cerca una chiave e restiutisce 
# true se e solo se è presente
def search (t:Tree, key:int) -> bool :
    i:Node|None = t.root
    while i is not None :
        if key > i.key:  
            i = i.right
        elif key < i.key:  
            i = i.left
        else: 
            return True
    return False

# metodo che cerca una chiave e restituisce 
# il nodo che la contiene (None se non è presente)
def search_node (t:Tree, key:int) -> Node|None :
    i:Node|None = t.root
    while i is not None :
        if key > i.key:  
            i = i.right
        elif key < i.key:  
            i = i.left
        else: 
            return i
    return None


def in_order_visit (t:Tree):
    in_order_visit_node (t.root)
    
def in_order_visit_node (u:Node|None):
    # caso base
    if u is None:
        return
    # caso ricorsivo
    in_order_visit_node (u.left)
    print (u.key, end = " ")
    in_order_visit_node (u.right)
          
t1 = Tree()
insert (t1, 10)
insert (t1, 6)
insert (t1, 20)
insert (t1, 15)
insert (t1, 1)
in_order_visit (t1)
print()

def crea_random_tree (n:int, key_max:int) -> Tree :
    t = Tree()
    for _ in range (n):
        insert (t, random.randint(0, key_max))    
    return t

print ("t2:")
t2 = crea_random_tree (20, 10000)
in_order_visit (t2)


def search_ric (t:Tree, key:int) -> bool:
    return search_ric_node (t.root, key)

def search_ric_node (u:Node|None, key:int) -> bool:
    #caso base negativo
    if u is None :
        return False
    #caso base positivo
    if u.key == key :
               return True
    #caso ricorsivo
    if key > u.key:
        return search_ric_node (u.right, key)
    else:
        return search_ric_node (u.left, key)
    
# esercizio: calcolare in modo ricorsivo 
# l'altezza di un Tree, definita
# come 0 se l'albero è vuoto, 1 se c'è solo la radice
# e così via (ogni livello si incrementa di 1)

def height (t:Tree) -> int:
    return height_ric_node (t.root)

def height_ric_node (u:Node|None):
    if u is None :
        return 0
    return 1 + max(height_ric_node(u.left), height_ric_node(u.right))

# implementiamo in modo iterativo la ricerca della chiave minima
def min (t:Tree) -> int|None:
    if t.root is None :
        return None
    i:Node = t.root
    while i.left is not None:
        i = i.left
    return i.key

# implementiamo in modo iterativo la ricerca il node contenente la chiave minima
def min_node (t:Tree) -> Node|None:
    if t.root is None :
        return None
    i:Node = t.root
    while i.left is not None:
        i = i.left
    return i
    
# implementiamo in modo ricorsivo la ricerca il node contenente la chiave massima
def max (t:Tree) -> Node|None:
    if t.root is None:
        return None
    return max_node_ric (t.root)

def max_node_ric (u:Node) -> Node :
    if u.right is None:
        return u
    return max_node_ric (u.right)

# metodo che restituisce il nodo contenente la chiave 
# immediatamente più grande di quella del nodo passato
def successor (u:Node) -> Node|None:
    if u.right is not None :
        subtree_rx = Tree(u.right)
        return min_node (subtree_rx)
    else:
        i:Node|None=u.parent
        while i is not None and i.key<u.key:
            i=i.parent
        return i

# metodo che sostituisce il nodo new (o None) al figlio old
def change_child (old:Node, new:Node|None) -> None :
    if new is not None:
        new.parent = old.parent
    if old.parent is None:
        return
    if old.parent.left is old : #old era il figlio sinistro
        old.parent.left = new
    else:
        old.parent.right = new

# metodo che cancella la chiave key dall'albero t
# restituisce true se la chiave è presente e viene cancellata,
# false altrimenti

#def remove (t:Tree, key:int) -> bool :
#    u = search_node(t, key)
# continuiamo domani....