# ---
# jupyter:
#   jupytext:
#     formats: ipynb,py:percent
#     text_representation:
#       extension: .py
#       format_name: percent
#       format_version: '1.3'
#       jupytext_version: 1.15.2
#   kernelspec:
#     display_name: Python 3 (ipykernel)
#     language: python
#     name: python3
# ---

# %% [markdown] slideshow={"slide_type": "slide"}
# # Fondamenti di Programmazione <a class="tocSkip"> <img align=right width=20% src=sap.png />
#
#
# **Andrea Sterbini**
#
# lezione 17 - 20 novembre 2023

# %% RECAP [markdown] slideshow={"slide_type": "slide"}
# # RECAP:
# - Analisi OOP
# - Ereditarietà
# - Esempio di gerarchia di figure disegnate con Turtle
# - Ricorsione e sue proprietà
# - Esempi: albero frattale, fattoriale, conigli di Fibonacci
#
# # OGGI: altri esempi di ricorsione

# %% Ricorsione init_cell=true slideshow={"slide_type": "notes"}
# carico il decoratore che stampa le chiamate ed uscite di una funzione ricorsiva
from rtrace import trace

# %%% Una chiamata ricorsiva può simulare un ciclo, anzi due slideshow={"slide_type": "slide"}
# mi costruisco una lista di valori casuali
import random 
lista = random.choices(range(-10000,10001), k=10)

# %% [markdown] slideshow={"slide_type": "slide"}
# # Somma ricorsiva di una lista (svolta in uscita)
# - **caso base**: se la lista è vuota la somma è 0
# - **se la lista non è vuota**: sommiamo il primo elemento alla <u>somma del resto della lista</u>

# %% slideshow={"slide_type": "slide"}
@trace(True)
def somma_ricorsiva(L):
    if L:           # se caso ricorsivo
        primo, *resto = L
        return primo + somma_ricorsiva(resto)
    else:
        return 0    # altrimenti caso base

somma = somma_ricorsiva.trace(lista)
somma2 = sum(lista)
somma, somma2


# %% slideshow={"slide_type": "slide"}
@trace()
def somma_ricorsiva_distruttiva(L):
    if L:           # se caso ricorsivo
        ultimo = L.pop()
        return ultimo + somma_ricorsiva_distruttiva(L)
    else:
        return 0    # altrimenti caso base

somma3 = somma_ricorsiva_distruttiva.trace(lista.copy())
# controlliamo che venga il risultato giusto
somma2, somma3 


# %% [markdown] slideshow={"slide_type": "slide"}
# ## Somma iterativa di una lista
# - accumuliamo la somma con un ciclo

# %% slideshow={"slide_type": "fragment"}
def somma_iter(L : list[int]) -> int:
    somma = 0
    N = len(L)
    for i in range(N):
        somma += L[i]
    return somma

somma_iter(lista), sum(lista)


# %% [markdown] slideshow={"slide_type": "slide"}
# ## Somma ricorsiva in avanti (simulando il ciclo)
# - le variabili di stato, **somma**, **i** ed **N** 
#   - diventano argomenti della funzione
#   - ad ogni step le aggiorniamo nella chiamata ricorsiva

# %% slideshow={"slide_type": "fragment"}
@trace()
def _somma_ric_avanti(L : list[int], i : int, 
                      N : int, somma : int) -> int :
    if i==N:
        return somma
    else:
        return _somma_ric_avanti(L, i+1, N, somma + L[i]) # AGGIORNAMENTO

def somma_ric_avanti(L):
    return _somma_ric_avanti(L, 0, len(L), 0)

somma_ric_avanti(lista)
_somma_ric_avanti.trace(lista, 0, len(lista), 0)


# %% [markdown] slideshow={"slide_type": "slide"}
# ## Stampa di una lista 
# - **in avanti** (<u>prima</u> del passo ricorsivo)
# - **indietro**  (<u>dopo</u> il passo ricorsivo)
# - **avanti poi indietro** (prima e dopo)
#
# Analisi:
# - la lista vuota non stampa nulla (caso base)
# - una volta stampato il primo elemento va stampato il resto (passo ricorsivo)

# %% slideshow={"slide_type": "slide"}
# per scandire e stampare una lista in avanti
def stampa_in_avanti(L):
    if L:
        primo, *resto = L
        print(primo, end=' ') 
        stampa_in_avanti(resto) 
    # else caso base non stampo nulla

stampa_in_avanti(lista)
print()
print(lista)


# %% slideshow={"slide_type": "slide"}
# per scandire e stampare una lista a rovescio
def stampa_dalla_fine(L):
    if L:
        primo, *resto = L
        stampa_dalla_fine(resto) 
        print(primo, end=' ')

stampa_dalla_fine(lista)
print()
print(lista)
# TODO per scandire una lista sia in avanti che a rovescio 
#      basta stampare sia prima della ricorsione che dopo

# %%% esempio: GCD con l'algoritmo di Euclide [markdown] slideshow={"slide_type": "slide"}
# ## Altro esempio: Massimo Comun Divisore di x, y interi positivi
# Ovvero dobbiamo trovare quel'intero **$M$** tale che:
# - **$x = M*k$** 
# - **$y = M*j$**
# - con **$k,j>=1$** (e senza fattori comuni)


# %%% esempio: GCD con l'algoritmo di Euclide [markdown] slideshow={"slide_type": "slide"}
# ### Quali sono le proprietà di **$x$** ed **$y$**?
# - se **x == y** allora esistono **k == j == 1** e **M == x**     (ecco un buon **caso base**!)
# - altrimenti proviamo a <u>sottrarre il minore dal maggiore</u> (assumiamo sia y)
#   - **$z = x-y = Mk - Mj = M(k-j)$**   quindi **z** e **y** hanno lo stesso **MCD**, <br>
#     e inoltre <u>z è più piccolo di x</u>  (ecco la nostra **riduzione**!)
#     - se prendiamo come _dimensione del problema_ la somma $x+y$
#         - ad ogni passo si riduce la somma $x+y = M(k+j)$ di almeno $y=Mj$ (il più piccolo dei due)
#         - quindi anche $k+j$ diminuisce mano a mano fino a diventare 1
#         - perchè sottraendo un numero più piccolo diminuiamo la somma ma non si può andare nei negativi nè sullo 0
#   - quindi a forza di sottrarre arriveremo per forza a $j=k=1$ ovvero al caso base      (ed ecco la **convergenza**)
#   - una volta trovato **M** abbiamo già la soluzione di ciascun caso __più grande__ (**ricomposizione**)
#
# Ottimizzazione: invece di sottrarre y da x calcoliamone il resto -> algoritmo di **Euclide**


# %%% esempio: GCD con l'algoritmo di Euclide slideshow={"slide_type": "slide"}
# Sfruttiamo la definizione ricorsiva del problema
# per dare una implementazione ricorsiva
@trace()
def GCD(x : int, y : int) -> int :
    # FIXME: controllare che siano  interi E positivi
    if x == y:
        return x
    else:
        if x>y:
            return GCD(x-y, y) # sottraggo il minore dal maggiore e tengo l'altro
        else:
            return GCD(y-x, x) # sottraggo il minore dal maggiore e tengo l'altro

GCD.trace(32, 18)


# %%% esempio: GCD con l'algoritmo di Euclide slideshow={"slide_type": "slide"}
## Non è difficile farne una versione iterativa

def GCD_iter(x : int, y : int) -> int :
    while x != y:
        print(x,y)
        if x > y:
            x -= y
        else:
            y -= x
    return x

print(GCD_iter(75,45))


# %%% esempio: palindromaP [markdown] slideshow={"slide_type": "slide"}
# ## Esempio: Check se una stringa/lista è palindroma <br> (si legge uguale in senso inverso)
#
# ### soluzioni iterative
# 1. rovescio e confronto
# 1. scandisco gli indici degli elementi partendo dagli estremi e li confronto
#     - se trovo una differenza torno False
#     - se arrivo a metà senza differenze torno True


# %% run_control={"marked": false}
from typing import Sequence
## Rovescio e confronto
def palindromaP_iter1(sequenza : Sequence):
    rovesciata = sequenza[::-1]
    return rovesciata == sequenza

# leggermente inefficiente, costruisco una nuova sequenza e confronto N coppie di elementi
# (potrei confrontarne solo N//2)
palindromaP_iter1('amoRoma')


# %% slideshow={"slide_type": "slide"}
## Versione iterativa

def palindromaP_iter2(sequenza : Sequence ) -> bool :
    for i in range(len(sequenza)//2):  # scandisco la prima metà degli indici
        print('comparing', sequenza[i], sequenza[-i-1], sequenza[i] == sequenza[-i-1])
        if sequenza[i] != sequenza[-i-1]:  # e confronto il primo con l'ultimo .... eccetera ... usando indici negativi
            return False
    return True

def palindromaP_iter3(sequenza : Sequence ) -> bool :
    "con una list comprehension e 'all'"
    return all(sequenza[i] == sequenza[-i-1] for i in range(len(sequenza)//2))


#palindromaP_iter2('amoRoma')
palindromaP_iter2([1, 2, 3, 4, 5, 4, 3, 2, 1])


# %%
def palindroma_iter2(sequenza):
    "lo stesso usando sue indici e spostandoli mano a mano verso il centro"
    inizio = 0
    fine   = len(sequenza)-1
    while inizio < fine:
        print('comparing', sequenza[inizio], sequenza[fine], sequenza[inizio] == sequenza[fine])
        if sequenza[inizio] != sequenza[fine]:
            return False
        inizio += 1      # l'inizio avanza di un passo
        fine   -= 1      # la fine arretra di un passo
    return True

palindroma_iter2([1, 2, 3, 4, 5, 4, 3, 2, 1])

# %%% esempio: palindromaP [markdown] slideshow={"slide_type": "slide"}
# ### soluzione ricorsiva
# - **casi base**: ogni sequenza di lunghezza 0 o 1 è già palindroma
# - se è lunga 2 o più elementi il primo e l'ultimo devono essere uguali
# - se non lo sono NON è palindroma (altro **caso base**)
# - se lo sono deve essere palindromo anche il resto, tolto primo ed ultimo carattere
#   - (togliere i 2 caratteri = **riduzione**)
#   - a forza di togliere 2 caratteri si arrivarà sempre ad averne 1 o 0 (**convergenza**)
#   - la stringa è palindroma se sono uguali primo e ultimo AND la sottostringa è palindroma <br>
#    (**costruzione della soluzione dalla sottosoluzione** + calcolo locale)


# %% slideshow={"slide_type": "slide"}
@trace()
def palindromaP(sequenza : Sequence ) -> bool :
    "predicato che verifica se una sequenza è palindroma"
    if len(sequenza) < 2: 
        return True
    if sequenza[0] != sequenza[-1]:
        return False
    else:
        return palindromaP(sequenza[1:-1])

palindromaP.trace('amoRoma')

# NOTA: è un po' inefficiente perchè crea tante sottosequenze


# %% slideshow={"slide_type": "slide"}
# versione che non crea sottostringhe usando gli indici inizio e fine per sapere quali caratteri confrontare
@trace()
def _palindromaP2(sequenza : Sequence, inizio : int, fine : int ) -> bool :
    if inizio >= fine:                           # se si sono raggiunti non ho trovato differenze (caso base)
        return True                              # la stringa è palindroma
    if sequenza[inizio] != sequenza[fine]:       # se sono diversi (caso base)
        return False                             # # la stringa NON è palindroma
    return _palindromaP2(sequenza, inizio+1, fine-1)   # altrimenti gli estremi sono OK, tutto dipende dal resto, sposto gli indici
    
def palindromaP2(sequenza):
    return palindromaP2(sequenza, 0, len(sequenza)-1)   # inizio da 0 e da N-1


_palindromaP2.trace('amoRoma', 0, 6)

# %% [markdown] slideshow={"slide_type": "slide"}
# ## Esploriamo un albero di directory: <br>cerchiamo tutti i file .txt e la loro dimensione
# Torniamo un dizionario **path del file -> dimensioni**
# - una directory contiene files (caso base) e sottodirectory (caso ricorsivo)
# - ogni volta che esaminiamo una sottodirectory abbiamo un problema simile a quello iniziale, e più piccolo (riduzione)
# - a forza di scendere arriveremo in una sottodirectory che contiene solo file (convergenza)
# - i file trovati nelle sottodirectory vanno raccolti assieme a quelli della dir iniziale (composizione)
#
# Per esaminare directory e files si usa la libreria **`os`** (os.listdir, os.path.isdir, os.path.getsize)

# %% slideshow={"slide_type": "subslide"}
import os

@trace()
def cerca_file_sizes(directory : str) -> dict[str, int] :
    "cerco tutti i file '.txt' e ne ritorno le dimensioni"
    risultato = {}
    for nome in os.listdir(directory):                 # esamino tutti i nomi nella directory
        if nome[0] in '_.': continue                   # ignoro file e dir che iniziano per '.' oppure '_'
        fullname = directory + '/' + nome              # costruisco il path completo del file/dir
        if os.path.isdir(fullname):                    # se è una directory devo cercarci dentro
            trovati = cerca_file_sizes(fullname)       # trovo tutti i file della sottodirectory
            risultato.update(trovati)                  # aggiorno il dizionario con ciò che ho trovato nella sottodirectory
        elif nome.endswith('.txt'):                    # altrimenti è un file e se finisce con '.txt'
            size = os.path.getsize(fullname)           # ne trovo le dimensioni
            risultato[fullname] = size                 # e aggiorno il dizionario    path -> dimensioni 
    return risultato                                   # e alla fine torno il risultato

cerca_file_sizes.trace('../lezione11')


# %%
## soluzione ricorsiva che raccoglie i file
## in un dizionario fornito come argomento
## e aggiornato mano a mano che si esplora

def cerca_file_sizes2(directory : str, dizionario : dict[str, int]) -> None:
    "cerco tutti i file '.txt' e ne ritorno le dimensioni, ma aggiornando un dizionario fornito dall'esterno"
    for nome in os.listdir(directory):
        
        if nome[0] in '_.': continue                       # ignoro file e dir che iniziano per '.' oppure '_'
        fullname = directory + '/' + nome                  # costruisco il path completo
        
        if os.path.isdir(fullname):                        # se sono nel caso ricorsivo
            cerca_file_sizes2(fullname, dizionario)        # continuo a cercare e passo il dizionario da aggiornare
        
        elif nome.endswith('.txt'):                        # altrimenti è un file e se finisce con '.txt'
            size = os.path.getsize(fullname)               # ne trovo le dimensioni
            dizionario[fullname] = size                    # ed aggiorno il dizionario


# %%
# per usare cerca_file_sizes2 devo PRIMA creare il dizionario
D : dict[str,int] = {}
cerca_file_sizes2('../lezione11', D)     # e passarlo
D


# %% [markdown]
# ## come sbagliare usando gli argomenti con default
#
# Potrebbe venire in mente di definire l'argomento del dizionario con un valore di default
# ```python
# def  cerca_file_sizes2( directory : str, dizionario : dict = {}):   # <-- notare questo valore di default
#     ...
# ```
# Ma questo crea effetti collaterali ed **errori difficili da riconoscere**
# - il valore di default **viene istanziato al momento della definizione** della funzione
# - viene quindi **condiviso tra tutte le chiamate**
# - questo non è un problema se il valore è immutabile
# - **diventa un casino se il valore di default è mutevole**

# %%
# esempio sbagliato
def cerca_file_sizes_sbagliato(directory, dizionario = {} ):
    "cerco tutti i file '.txt' e ne ritorno le dimensioni, ma aggiornando un dizionario CON DEFAULT!!!"
    for nome in os.listdir(directory):
        if nome[0] in '_.': continue                          # ignoro file e dir che iniziano per '.' oppure '_'
        fullname = directory + '/' + nome                     # costruisco il path completo
        if os.path.isdir(fullname):                           # se sono nel caso ricorsivo
            cerca_file_sizes_sbagliato(fullname, dizionario)  # continuo a cercare e passo il dizionario da aggiornare
        elif nome.endswith('.txt'):                           # altrimenti è un file e se finisce con '.txt'
            size = os.path.getsize(fullname)                  # ne trovo le dimensioni
            dizionario[fullname] = size                       # ed aggiorno il dizionario
    return dizionario


# %%
cerca_file_sizes_sbagliato('.')              # prima esecuzione, raccolgo i file in questa dir

# %%
cerca_file_sizes_sbagliato('../lezione11')   # seconda esecuzione, ritrovo anche quelli di prima

# %%
cerca_file_sizes_sbagliato('../lezione10')   # terza esecuzione, ritrovo anche quelli di prima!!!!


# %%
## conclusione: NON usate parametri di default mutevoli
def cerca_file_sizes_corretto(directory, dizionario = None ):
    "cerco tutti i file '.txt' e ne ritorno le dimensioni, ma aggiornando un dizionario CON DEFAULT!!!"
    if dizionario is None: dizionario = {}                 # ne creo uno nuovo ad ogni chiamata
    for nome in os.listdir(directory):
        if nome[0] in '_.': continue                       # ignoro file e dir che iniziano per '.' oppure '_'
        fullname = directory + '/' + nome                  # costruisco il path completo
        if os.path.isdir(fullname):                        # se sono nel caso ricorsivo
            cerca_file_sizes_corretto(fullname, dizionario)        # continuo a cercare e passo il dizionario da aggiornare
        elif nome.endswith('.txt'):                        # altrimenti è un file e se finisce con '.txt'
            size = os.path.getsize(fullname)               # ne trovo le dimensioni
            dizionario[fullname] = size                    # ed aggiorno il dizionario
    return dizionario


# %%
cerca_file_sizes_corretto('.')

# %%
cerca_file_sizes_corretto('../lezione11')    # ORA VA BENE

# %% [markdown] slideshow={"slide_type": "slide"}
# # Alberi binari
#
# - si parte da un nodo "radice" che non ha "padri"
# - ogni nodo piò avere fino a 2 "figli"
# - i nodi senza figli sono le "foglie"
# - ogni nodo ha un solo "padre"

# %% slideshow={"slide_type": "notes"} jupyter={"source_hidden": true}
from pygraphviz import AGraph
G = AGraph(directed=True)
G.add_path(['radice', "nodo\n0", "nodo\n00", "foglia\n000"])
G.add_path(['radice', "nodo\n1", "nodo\n10", "foglia\n100"])
G.add_path([          "nodo\n0", "nodo\n01", "foglia\n010"])
G.add_path([          "nodo\n1", "nodo\n11", "foglia\n110"])
G.add_edge("nodo\n00", "foglia\n001")
G.add_edge("nodo\n10", "foglia\n101")
G.add_edge("nodo\n01", "foglia\n011")
G.add_edge("nodo\n11", "foglia\n111")
G.layout('dot')
G


# %% slideshow={"slide_type": "slide"}
# usiamo gli oggetti per rappresentare i nodi dell'albero
class NodoBinario:
    def __init__(self,   V : int, left  : 'NodoBinario' = None, right : 'NodoBinario' = None):
        self._value = V
        self._sx = left
        self._dx = right
    def __repr__(self):
        return f'NodoBinario({self._value})'

n11 = NodoBinario(11)
n10 = NodoBinario(10)
n1 = NodoBinario(1, right=n11)
n0 = NodoBinario(0, left= n10)
r = NodoBinario('radice', n0, n1)
r


# %% [markdown] slideshow={"slide_type": "slide"}
# ## Stampa di un albero
# ### con visita in <u>PREordine</u> (la radice prima dei sottoalberi)

# %% slideshow={"slide_type": "fragment"}
# radice è un nodo oppure None
# per stampare indentato passo un argomento 'livello'
# e lo incremento ogni volta che scendo in un sottoalbero
def stampa_PRE(radice : NodoBinario, livello : int = 0) -> None :
    print('|--'*livello, radice)             # PRIMA stampo la radice (lo faccio in ogni caso, per mostrare i figli mancanti)
    if radice:
        stampa_PRE(radice._sx, livello+1)    # poi SE questo è un nodo stampo SX
        stampa_PRE(radice._dx, livello+1)    # e DX

stampa_PRE(r)


# %% [markdown] slideshow={"slide_type": "slide"}
# ### con visita in <u>POSTordine</u> (la radice DOPO i sottoalberi)

# %% slideshow={"slide_type": "fragment"}
def stampa_POST(radice, livello=0):
    if radice:                               # se il nodo esiste
        stampa_POST(radice._sx, livello+1)   # scendo nei sottoalberi SX
        stampa_POST(radice._dx, livello+1)   # e DX
    print('|--'*livello, radice)             # e POI stampo il nodo (lo faccio in ogni caso, per mostrare i figli mancanti)
    # altrimenti non ho nulla da fare
stampa_POST(r)


# %% [markdown] slideshow={"slide_type": "slide"}
# ### con visita <u>INordine</u> (la radice TRA i sottoalberi)

# %% slideshow={"slide_type": "fragment"}
def stampa_IN(radice, livello=0):
    if radice:                             # se questo è un nodo 
        stampa_IN(radice._sx, livello+1)   # stampo il sottoalbero SX
    print('|--'*livello, radice)           # poi la radice (lo faccio in ogni caso, per mostrare i figli mancanti)
    if radice:                             
        stampa_IN(radice._dx, livello+1)   # poi il DX

stampa_IN(r)


# %% [markdown] slideshow={"slide_type": "slide"}
# ## Calcolo della profondità/altezza di un albero (in uscita)
# - Una foglia ha altezza 1 (**caso base**)
# - un nodo ha altezza 1 + la massima altezza dei sottoalberi (**passo ricorsivo + composizione**)
# - **convergenza**: ogni volta che scendo in un sottoalbero i nodi da esaminare diminuiscono almeno di 1 (la radice)
#
# Oppure possiamo considerare come **caso base**:
# - **None** ha altezza 0

# %% [markdown]
# ![](altezza.png)

# %% slideshow={"slide_type": "slide"}
@trace()
def altezza(radice):
    if radice is None:            # caso base, None ha altezza 0
        return 0
    # altrimenti sono nel caso ricorsivo
    H_sx = altezza(radice._sx)    # calcolo l'altezza a sinistra
    H_dx = altezza(radice._dx)    # calcolo l'altezza a destra
    return 1 + max(H_sx, H_dx)    # e sommo 1 al massimo delle due

altezza.trace(r)
#stampa_PRE(r)

# %% [markdown] slideshow={"slide_type": "slide"}
# ## Calcolo della profondità in "andata"
#
# - si fornisce  come argomento la profondità massima incontrata finora
# - la si aggiorna visitando tutto l'albero 
#   - (ogni volta che si scende in un sottoalbero si somma 1 alla profondità)
# - se il nodo è **None** si torna la profondità corrente
# - altrimenti il nodo esiste e la profondità è il massimo delle profondità dei due sottoalberi

# %% slideshow={"slide_type": "slide"}
@trace()
def altezza2(radice, profondità=0):
    if radice is None:
        return profondità
    P_sx = altezza2(radice._sx, profondità+1)
    P_dx = altezza2(radice._dx, profondità+1)
    return max(P_sx, P_dx)

altezza2.trace(r) 

# %% [markdown] slideshow={"slide_type": "slide"}
# # Alberi N-ari (con numero indefinito di figli)
# - **value**: valore del nodo
# - **sons**: elenco di figli

# %% slideshow={"slide_type": "notes"} jupyter={"source_hidden": true}
G3 = AGraph(directed=True)
G3.add_node(2,style='filled',fillcolor='lightgreen')
G3.add_node(19,style='filled',fillcolor='magenta')
G3.add_edges_from([
    [14, 11],
    [14, 12],
    [14, 2],
    [11, 19],
    [11, 13],
    [11, 3],
    [11, 4],    
])
G3.layout('dot')
G3

# %% slideshow={"slide_type": "fragment"}
# utility che mi permette di aggiungere con %%add_to dei metodi definiti in celle separate alla classe
import jdc

class NodoNario :
    def __init__(self,   V : int, 
                         sons : list['NodoNario'] = None): 
        # ATTENTI AL DEFAULT!!!
        self._value = V
        if sons is None:
            self._sons = []
        else:
            self._sons = sons

    def __repr__(self):
        return f"NodoNario({self._value}, {len(self._sons)} sons)"    


# %% [markdown] slideshow={"slide_type": "slide"}
# ### stavolta scriviamo le funzioni come metodi della classe NodoNario

# %% [markdown] slideshow={"slide_type": "fragment"}
# ### altezza del nodo nell'albero (quanti livelli ha sotto)
# - esploro l'albero ricorsivamente
# - l'altezza di un nodo è 1 + max altezza dei sottoalberi figli
# - l'altezza di una foglia è 0

# %% slideshow={"slide_type": "fragment"}
# %%add_to NodoNario

## metodo per calcolare l'altezza del nodo
def altezza(self):
    # se non ci sono figli si torna 1
    return max( [son.altezza()+1 for son in self._sons], default=1 )


# %% slideshow={"slide_type": "fragment"}
n19 = NodoNario(19)
n2 = NodoNario(2)
n3 = NodoNario(3)
n4 = NodoNario(4)
n13 = NodoNario(13)
n12 = NodoNario(12)
n11 = NodoNario(11, [n3, n4, n13, n19])
n14 = NodoNario(1, [n2, n11, n12])

# %% slideshow={"slide_type": "fragment"}
n14.altezza()


# %% [markdown] slideshow={"slide_type": "slide"}
# ### stampa (in preordine) di un nodo e dei figli
# - aggiungo un argomento livello che incremento ogni volta che scendo per dare l'indentazione giusta
# - prima stampo il nodo indentato del livello corrente
# - poi stampo ricorsivamente i sottoalberi con livello+1

# %% slideshow={"slide_type": "fragment"}
# %%add_to NodoNario
# metodo per stampare l'albero
def stampa(self, livello=0):
    indent = '|--'*livello        # indentazione corretta per il mio livello   
    print(indent, self)           # PRE ordine
    for son in self._sons:        # per ciascun sottoalbero (se ci sono)
        son.stampa(livello+1)     # lo stampo con indentazione aumentata


# %% slideshow={"slide_type": "fragment"}
n14.stampa()


# %% [markdown] slideshow={"slide_type": "slide"}
# ## cerchiamo il massimo valore nell'albero
#
# - esploriamo ricorsivamente
# - il valore massimo di un sottoalbero è il massimo tra il valore della radice ed i massimi dei sottoalberi

# %% slideshow={"slide_type": "fragment"}
# %%add_to NodoNario

# versione in stile non-funzionale
def massimo(self):
    M = self._value
    for s in self._sons:
        m = s.massimo()
        if M < m:
            M = m
    return M 

# versione in stile funzionale
def massimo2(self):
    return max([s.massimo2() for s in self._sons] + [self._value])


# %% slideshow={"slide_type": "fragment"}
n14.massimo2()


# %% slideshow={"slide_type": "slide"}
# %%add_to NodoNario
# versione che porta il massimo come argomento 
# da aggiornare mano a mano che si esplora l'albero
def massimo3(self, max_corrente=None):
    if max_corrente is None:           # se è il primo nodo che esploro
        max_corrente = self._value     # il massimo è il mio valore
    else:
        max_corrente = max(max_corrente, self._value)   # altrimenti aggiorno il massimo
    for son in self._sons:             # lo passo a ciascun sottoalbero, che mi torna il massimo trovato e che passo al successivo
        max_corrente = son.massimo3(max_corrente)
    return max_corrente   # ATTENZIONE: DOVETE TORNARE IL NUOVO VALORE!!!
                          # perchè max_corrente è una VARIABILE LOCALE!!!
                          # e tornandola comunicate all'esterno il risultato 
                          # (e quindi anche agli altri sottoalberi)


# %%
n14.massimo3()

# %% slideshow={"slide_type": "fragment"}
n14.massimo(), n14.massimo2(), n14.massimo3()


# %% [markdown] slideshow={"slide_type": "slide"}
# ## cerchiamo il <u>nodo</u> col massimo valore
# - esploriamo ricorsivamente 
# - il nodo massimo di un sottoalbero è nodo che contiene il massimo tra il valore della radice ed i massimi dei sottoalberi

# %% slideshow={"slide_type": "fragment"}
# %%add_to NodoNario

def max_node(self):
    M = [self] + [s.max_node() for s in self._sons] # prendo me stesso ed i massimi nodi dei figli
    #print(M)
    return max(M, key=lambda x: x._value)           # a tra tutti cerco il nodo che ha massimo valore

def min_node(self):
    M = [self] + [s.min_node() for s in self._sons] # prendo me stesso ed i massimi nodi dei figli
    #print(M)
    return min(M, key=lambda x: x._value)           # a tra tutti cerco il nodo che ha minimo valore


# %% slideshow={"slide_type": "fragment"}
n14.max_node(), n14.min_node()


# %% [markdown] slideshow={"slide_type": "slide"}
# ## cerchiamo la differenza in altezza tra nodo con valore massimo e nodo con valore minimo

# %% slideshow={"slide_type": "fragment"}
# %%add_to NodoNario
def depth_of_max(self,livello=0):
    # prendo coppie (valore, profondità) di me stesso e di tutti i sottoalberi
    M = [(self._value, livello)] + [ son.depth_of_max(livello+1) for son in self._sons]
    return max(M, key=lambda x: x[0])    # ne torno il (massimo VALORE e sua profondità)

def depth_of_max2(self,livello=0):
    M = self._value
    P = livello
    for son in self._sons:
        m,p = son.depth_of_max2(livello+1)
        if m > M:
            M = m
            P = p
    return M, P

def depth_of_min(self,livello=0):
    M = [(self._value, livello)] + [ son.depth_of_min(livello+1) for son in self._sons]
    return min(M, key=lambda x: x[0])



# %% slideshow={"slide_type": "fragment"}
n14.depth_of_max(), n14.depth_of_min()


# %%% esempio: mergesort  (ordinamento per fusione) [markdown] slideshow={"slide_type": "slide"}
# # MergeSort (ordinamento per fusione)
#
# ## osservazione: se due liste sono <u>già ordinate</u> è facile e veloce fonderle in una nuova lista ordinata
#
# - per fondere due liste ordinate (**merge**)
#   - il primo elemento della soluzione è uno dei due primi delle due liste (**composizione** della soluzione)
#   - il resto della soluzione è la fusione del resto delle due liste (**caso ricorsivo**)
# - **convergenza**: almeno un elemento va a posto per ogni chiamata ricorsiva
# - **caso base**: una delle due liste è vuota

# %% slideshow={"slide_type": "slide"}
@trace(True)
def merge(L1 : list, L2 : list ) -> list:
    if not L1:             # caso base: L1 vuota
        return L2
    if not L2:             # caso base: L2 vuota
        return L1
    if L1[0] <= L2[0]:     # caso ricorsivo con L1[0] minore
        return [L1[0]] + merge( L1[1:], L2 )
    else:                  # caso ricorsivo con L2[0] minore
        return [L2[0]] + merge( L1,     L2[1:] )

L1 = [1, 3, 5, 7, 9]
L2 = [2, 4, 6, 8]
merge.trace(L1, L2)

# NOTA: per essere più efficienti possiamo preallocare la lista risultato e lavorare solo su indici
# NOTA: oppure/inoltre lavorare in modo iterativo 

# %%% esempio: mergesort  (ordinamento per fusione) [markdown] slideshow={"slide_type": "slide"}
# ## MA se ho una lista <u>disordinata</u> e la voglio ordinare? (MergeSort)
# - la posso spezzare in due liste <u>disordinate</u> (**riduzione**)
# - le posso ordinare separatamente (chiamata ricorsiva sui **sottoproblemi**)
# - le posso fondere rapidamente (**costruzione della soluzione**) con **merge**
# - **convergenza**: a forza di spezzare le liste in 2 si arriverà a liste di 0,1 elementi
# - **caso base**:  liste di 1 o 0 elementi, <u>sono già ordinate</u>

# %% slideshow={"slide_type": "slide"}
## per spezzare in 2 posso usare una slice
L = [1, 5, 2, 9, 4, 6, 1, 90 ]

mid = len(L)//2
L1 = L[:mid]
L2 = L[mid:]

L1, L2


# %%% esempio: alberi binari e stampa in/pre/post ordine slideshow={"slide_type": "slide"}
## oppure una funzione ricorsiva che torna due liste di elementi alternati
@trace()
def splitta(L):
    if not L:
        return [], []
    else:
        primo, *resto = L     # prendo il primo elemento ed il resto
        L1, L2 = splitta(resto)
        L2.append(primo)
        return L2, L1    # aggiungo il valore su una lista e le scambio
splitta.trace(L)


# %%% esempio: alberi n-inari e directory slideshow={"slide_type": "slide"}
## Finalmente realizziamo mergeSort
@trace()
def merge_sort(L : list) -> list:
    if len(L) < 2:                       # [x] e [] sono già ordinate
        return L
    else:
        L1, L2 = splitta(L)              # 2 sottoliste disordinate
        sorted1 = merge_sort(L1)         # ordino la prima
        sorted2 = merge_sort(L2)         # ordino la seconda
        return merge(sorted1, sorted2)   # le fondo


# %%% esempio: alberi n-inari e directory slideshow={"slide_type": "slide"}
# TODO: per essere un po' più efficienti si può lavorare con indici in liste che non vengono modificate

merge_sort.trace(L)

# %% [markdown] slideshow={"slide_type": "slide"}
# ![](mergesort.png)