# 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 = None
        self.next: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:List, value:int) -> 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
        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: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: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: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)