'''MODULE d'implémentation d'une Liste Chaînée MUABLE
  en utilisant des Cellules-Objets pour former la liste chaînée


'''

class Cellule:
    def __init__(self, valeur:'Element', successeur:'Cellule|None'):
        self.v = valeur      # Valeur ne peut pas être None si liste homogène
        self.s = successeur  # successeur vaut None si Cellule de Fin
     
    def contenu(self:'Cellule') -> 'Element':
        '''Renvoie le contenu de la Cellule'''
        return self.v
     
    def successeur(self:'Cellule NON FIN') -> 'Cellule':
        '''Renvoie la Cellule suivante de self NON FIN'''
        return self.s
     
    def a_successeur(self:'Cellule') -> bool:
        '''Prédicat qui renvoie True si le successeur de notre Cellule est bien une Cellule'''
        return not self.s is None    # ou même return self.s is not None
     
    def est_fin(self:'Cellule') -> bool:
        '''Prédicat qui renvoie True si la Cellule n'a pas de successeur'''
        return self.s is None   # ou même return not self.a_successeur()

    def nb_cellules(self:'Cellule') -> int:
        '''Renvoie le nombre de cellules dans la chaîne à partir de cette cellule'''
        if self.s is None:                # si il n'y a pas de successeur
            return 1                      # il y a au moins la fin
        else:
            return 1 + self.s.nb_cellules()  # on demande au successeur...
        
class Liste:
    def __init__(self):
        self.tete = None
     
    def est_liste_vide(self:'Liste') -> bool:
        return self.tete is None

    def acces_tete(self:'Liste NON VIDE') -> Cellule:
        '''Renvoie l'adresse de la cellule de Tête dans la liste NON VIDE'''
        return self.tete
     
    def acces(self:'Liste NON VIDE', i:'int VALIDE') -> Cellule:
        '''Renvoie l'adresse de la cellule i dans la liste NON VIDE'''
        c = self.acces_tete()  # récupère la cellule de tête
        for _ in range(i):     # Faire i fois
            c = c.s            # passe au successeur
        return c
    
    def longueur(self:'Liste') -> int:
        '''Renvoie la longueur de la liste'''
        if self.est_liste_vide():
            return 0
        else:
            return self.tete.nb_cellules()
        
    def inserer_tete(self:'Liste', elt:'Element') -> None:
        '''Rajoute une nouvelle cellule contenant elt en tête de liste'''
        nouvelle = Cellule(elt, None)  # Etape 1 : création de la cellule
        nouvelle.s = self.tete         # Etape 2 : on relie la nouvelle cellule à l'"ancienne" tête
        self.tete = nouvelle           # Etape 3 : modification de la liste
        
    def inserer(self:'Liste', elt:'Element', i:'int VALIDE') -> None:
        '''Rajoute une nouvelle cellule contenant elt en position i VALIDE de la liste NON VIDE'''
        if i == 0:
            self.inserer_tete(elt)
        else:
            pred = self.acces(i-1)         # Etape 1 : recherche de la cellule i-1
            nouvelle = Cellule(elt, None)  # Etape 2 : création de la cellule
            nouvelle.s = pred.s            # Etape 3 : liaison nouvelle i vers ancienne i
            pred.s = nouvelle              # Etape 4 : liaison i-1 vers nouvelle i

    def inserer_fin(self:'Liste', elt:'Element') -> None:
        '''Rajoute une nouvelle cellule de Fin contenant elt dans la liste'''
        if self.est_liste_vide():
            self.inserer_tete(elt)
        else:
            pred = self.tete               # Etape 1 : recherche de la cellule de Fin
            while pred.s is not None:      #   TANT QUE pred n'est pas la fin actuelle
                pred = pred.s              #     on passe à la cellule suivante
            nouvelle = Cellule(elt, None)  # Etape 2 : création de la cellule
            pred.s = nouvelle              # Etape 3 : on relie l'ancienne Fin à la nouvelle

    def supprimer_tete(self:'Liste NON VIDE') -> 'Elt':
        '''Supprime la cellule de tête et renvoie l'élément qui y était stocké'''
        ancienne_valeur = self.tete.v  # Etape 1 : on mémorise la valeur en tête
        self.tete = self.tete.s        # Etape 2 : la tête devient le successeur de la tête
        return ancienne_valeur         # Etape 3 : on renvoie la valeur stockée

    def supprimer(self:'Liste', i:'int VALIDE') -> 'Element':
        '''Supprime la cellule en position i VALIDE et renvoie l'élément qui y était stocké'''
        if i == 0:                  # En réalité, on veut supprimer la Tête
            return self.supprimer_tete()
        else:
            pred = self.acces(i-1)      # Etape 1 : recherche de la cellule i-1
            ancienne_valeur = pred.s.v  # Etape 2 : on mémorise la valeur en position i actuellement
            pred.s = pred.s.s           # Etape 3 : on fait pointer le prédécesseur sur le successeur de son successeur
            return ancienne_valeur      # Etape 4 : on renvoie la valeur mémorisée

    def supprimer_fin(self:'Liste NON VIDE') -> 'Element':
        '''Supprime la cellule de Fin d'une liste NON VIDE et renvoie l'élément qui y était stocké'''
         
        if self.tete.s is None:
            return self.supprimer_tete()
        else:
            # Etape 1 : on cherche le prédécesseur de la Fin
            pred = lst.tete    # on part de la tête
            while pred.s.s is not None:   # tant que c n'est pas le prédécesseur de la Fin
                pred = pred.s                # on passe à la cellule suivante
             
            ancienne_valeur = pred.s.v  # Etape 2 : on mémorise la valeur en position i actuellement
            pred.s = None               # Etape 3 : on fait pointer le prédécesseur sur None
            return ancienne_valeur      # Etape 4 : on renvoie la valeur mémorisée

    def premier(self:'Liste NON VIDE') -> 'Element':
        '''Renvoie la valeur en tête de liste'''
        return self.tete.v