from typing import Optional
from typing import cast

# Liste:
# - di numeri interi
# - identificate dal loro primo elemento
# - singolarmente concatenate
# - ordinate (in modo non decrescente rispetto al valore)

class List :
    def __init__(self) :
        self.value:int = 0
        self.next:Optional[List] = None

# metodo che inserisce un intero in una lista
# ATTENZIONE: poiché la lista è identificata 
#             dal suo primo elemento, è necessario
#             che il metodo restituisca il riferimento
#             alla nuova lista dopo l'inserimento

def insert (l:Optional[List], value:int) -> Optional[List] :
    # creo il nuovo elemento da inserire
    nuovo = List()
    nuovo.value = value    
    # trovo il punto in cui inserire il nuovo elemento
    precedente = None
    i = l 
    while i is not None and i.value<value :
        precedente = i
        cast (List, i)
        i = i.next
    if precedente is None :
        # devo inserire in prima posizione
        nuovo.next = l
        return nuovo
    else :
        # devo inserire dopo precedente
        precedente.next = nuovo
        nuovo.next = i
        return l
    

# funzione che converte una lista in stringa nella forma, ad esempio, [1, -4, 3]
def printList (l:Optional[List]) -> str :
    ris = "["
    i = l
    while i is not None :
        ris += str(i.value)
        if i.next is not None :
            ris += ", "
        i = i.next
    return ris + "]"

l = None
l = insert (l, 10)
l = insert (l, 5)
l = insert (l, 20)
l = insert (l, 15)
l = insert (l, 1)
print (printList(l))

# scrivere una funzione iterativa che data una lista e un valore restituisce
# True se il valore è presente, False altrimenti
def search (l:Optional[List], value:int) -> bool :
    i = l
    while i is not None and i.value <= value:
        if (i.value==value) :
            return True
        i = i.next
    return False

# scrivere una funzione ricorsiva che data una lista e un valore restituisce
# True se il valore è presente, False altrimenti
def searchRic (l:Optional[List], value:int) -> bool :
    # casi base
    if l is None :
        return False
    if l.value==value :
        return True
    if l.value>value :
        return False
    # caso ricorsivo
    return searchRic (l.next, value)

# esercizio 1: metodo che restituisce la lunghezza della lista (iterativo e ricorsivo)
# esercizio 2: metodo che conta quanti numeri pari ci sono nella lista (iterativo e ricorsivo)
# esercizio 3: metodo che elimina la prima occorrenza di un valore dalla lista (iterativo)

# es 1 iterativo
def length (l:Optional[List]) -> int :
    ris:int = 0
    i:Optional[List] = l 
    while i is not None :
        ris += 1
        i = i.next
    return ris
print ("Lunghezza = ", length(l))

# es 1 ricorsivo
def length_ric (l:Optional[List]) -> int :
    # caso base
    if l is None :
        return 0
    # caso ricorsivo

    return 1 + length_ric (l.next)
print ("Lunghezza = ", length_ric(l))

#es 2 iterativo
def even_count (l:Optional[List]) -> int :
    ris:int = 0
    i:Optional[List] = l 
    while i is not None :
        if i.value % 2 == 0 :
            ris += 1
        i = i.next
    return ris
print ("conto pari = ", even_count(l))

# es 2 ricorsivo
def even_count_ric (l:Optional[List]) -> int :
    # caso base
    if l is None :
        return 0
    # caso ricorsivo
    if l.value % 2 == 0 :
        return 1 + even_count_ric (l.next)
    else :
        return even_count_ric (l.next)
print ("conto pari = ", even_count_ric(l))


# es 3
def delete (l:Optional[List], v:int) -> tuple[Optional[List], bool]:
    precedente:Optional[List] = None
    i:Optional[List] = l
    while i is not None and i.value <= v:
        if i.value == v :
            if precedente is None : #elimino il primo elemento
                return i.next, True
            else : # elimino un elemento che non è il primo
                precedente.next = i.next 
                return l, True
        precedente = i
        i = i.next
    return l, False
l, flag = delete (l, 15)
print (printList(l))
l, flag = delete (l, 1)
print (printList(l))


#esercizio. Sfruttando delete, fare un metodo delete_all che cancella tutte le occorrenze 
#           di un dato intero dalla lista
def delete_all (l:Optional[List], v:int) -> Optional[List] :
    continuazione = True
    while continuazione :
        l, continuazione = delete (l, v)
    return l
print (printList(l))
l = insert (l, 16)
l = insert (l, 16)
l = insert (l, 16)
l = insert (l, 16)
print (printList(l))
l = delete_all (l, 16)
print (printList(l))