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

class List :
    def __init__(self) :
        self.value:int = None
        self.next:List = None

# funzione 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 ottenuta dopo l'inserimento
def insert (l:List, value:int) -> List :
    # creo il nuovo elemento della lista (di tipo List)
    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
        i = i.next
    if precedente is None :
        # devo inserire nuovo in prima posizione
        nuovo.next = l
        return nuovo
    else :
        # devo inserire nuovo dopo precedente
        precedente.next = nuovo
        nuovo.next = i 
        return l
    

# funzione che converte una lista in stringa nel formato [1, 2, 5]
def print_list (l: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 + "]"

# lista vuota è identificata da None
l = None 
l = insert (l, 10)
print (print_list(l))
l = insert (l, 5)
print (print_list(l))
l = insert (l, 20)
print (print_list(l))
l = insert (l, 16)
print (print_list(l))

# scrivere una funzione iterativa che data una lista e un valore resituisce True
# se il valore è presente nella lista, False altrimenti
def search (l: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 resituisce True
# se il valore è presente nella lista, False altrimenti
def searchRic (l: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: funzione che restituisce la lunghezza della lista (iterativo e ricorsivo)
# esercizio 2: funzione che conta quanti numeri pari ci sono nella lista (iterativo e ricorsivo)
# esercizio 3: funzione che elimina la prima occorrenza di un valore dalla lista (iterativo)

# es 1 iterativo
def length (l:List) -> int :
    ris:int=0
    i:List = l 
    while i is not None :
        ris += 1
        i = i.next
    return ris

print (print_list(l))
print ("La lunghezza della lista è ", length(l))

# es 1 ricorsivo
def length_ric (l:List) -> int :
    #caso base
    if l is None :
        return 0
    #caso ricorsivo
    return length_ric(l.next) + 1
    

print (print_list(l))
print ("La lunghezza (metodo ricorsivo) della lista è ", length_ric(l))

#es 2 iterativo
def even_count (l:List) -> int :
    ris:int=0
    i:List = l 
    while i is not None :
        #ris += 1 if i.value % 2 == 0 else 0
        if i.value % 2 == 0 :
            ris+=1
        i = i.next
    return ris

print (print_list(l))
print ("Il numero di elementi pari è ", even_count(l))

#es 2 ricorsivo
def even_count_ric (l: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 (print_list(l))
print ("Il numero di elementi (metodo ricorsivo) pari è ", even_count_ric(l))

#esercizio 3
def delete (l:List, v:int) -> List :
    i:List = l
    if i is None:
        return i
    if i.value==v :
        #i = i.next
        return i.next    
    while i.next is not None and i.next.value <= v:
        if i.next.value == v :
            i.next = i.next.next
            return l
        i = i.next
    return l
l = delete (l, 10)
print (print_list(l))
l = delete (l, 5)
print (print_list(l))
l = delete (l, 20)
print (print_list(l))
l = delete (l, 16)
print (print_list(l))
    
def delete2 (l:List, v:int) -> tuple[List, bool] :
    i:List = l
    precedente:List = None
    while i is not None and i.value <= v:
        if i.value == v :
            if precedente is None:
                return i.next, True
            else: 
                precedente.next = i.next
                return l, True
        precedente = i
        i = i.next
    return l, False
    
#esercizio 
# Scrivere un metodo delete_all che cancella TUTTE le occorrenze di un valore da una lista
def delete_all (l:List, v:int) -> List :
    while search (l, v):
        l = delete (l,v)
    return l

def delete_all2 (l:List, v:int) -> List :
    continuazione = True
    while continuazione:
        l, continuazione = delete2 (l,v)
    return l

#facciamo la stessa cosa in modo più efficiente (scorrendo la lista solo una volta)
def delete_all3 (l:List, v:int) -> List :
    i:List = l
    precedente:List = None
    #ciclo per individuare il primo elemento con valore v
    while i is not None and i.value < v:
        precedente = i
        i = i.next
    if i is None or i.value>v :
        return l
    #ciclo per individuare l'ultimo elemento con valore v
    while i is not None and i.value==v:
        i=i.next
    if precedente is None:
        return i
    else: 
        precedente.next = i
        return l
    
for i in range (0,4) :
    l = insert (l, 17)

l = insert (l, 10)
l = insert (l, 20)

print (print_list(l)  )
l = delete_all3 (l,17)
print (print_list(l)  )