# 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 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 + "]"

# lista vuota è identificata da None
l = None 
l = insert (l, 10)
print (printList(l))
l = insert (l, 5)
print (printList(l))
l = insert (l, 20)
print (printList(l))
l = insert (l, 16)
print (printList(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)