# coding: utf-8

from typing import TypeVar, Generic
C = TypeVar('Chainon')
V = TypeVar('Valeur')

class Chainon :
    """ Un chaînon d'une liste chaînée.
    Un chaînon contient 2 attributs :
        - val : la valeur
        - next : le Chainon suivant ou None si c'est le dernier chaînon de la liste
     """

    def __init__(self:C, valeur:V, suivant:C=None) ->None:
        """ Constructeur = crée un objet de classe Chainon """
        self.val = valeur
        self.next = suivant

    def __str__(self:C) ->str:
        """ Affiche le Chainon (résultat de la fonction print) """
        if self.next == None : # Cas terminal
            return f"{self.val} -> None"
        else : # Cas récursif
            return f"{self.val} -> {str(self.next)}"

    def __len__(self:C) ->int:
        """ Renvoie le nombre de Chainon de la chaîne """
        if self.next == None : # Cas terminal
            return 1
        else: # Cas récursif
            return 1 + len(self.next)

    def n_ieme_element(self:C, n:int) ->V:
        """ Renvoie la valeur du n-ième élément de la liste chainée passée en argument """
        if n < 0 :
            raise IndexError("n_ieme_element inexistant")
        if n == 0 : # Cas terminal
            return self.val
        else: # Cas récursif
            return self.next.n_ieme_element(n-1)

    def concatener(self:C, autre:C) ->C:
        """ renvoie une liste chainée obtenue par concaténation du Chainon courant et d'un autre """
        if self.next == None :  # Cas terminal
            return Chainon(self.val, autre)
        else: # Cas récursif
            return Chainon(self.val, self.next.concatener(autre))

    def renverser(self:C) ->C:
        """ Renvoie une nouvelle liste dont le sens est renversé """
        # La récursivité n'est pas toujours la meilleure solution !
        # On va donc passer en itératif, surtout qu'il est facile d'attacher un chainon en tête d'une chaine déjà constituée
        chaine_renversee = None
        chainon = self
        while chainon != None :
            chaine_renversee = Chainon(chainon.val, chaine_renversee)
            chainon = chainon.next
        return chaine_renversee

    def inserer(self:C, valeur:V, indice:int) ->None:
        """ Insère l'élément valeur à la position indice dans la liste. """
        if indice < 0:
            raise IndexOutOfRangeError(f"Impossible d'insérer à l'indice {indice}")
        elif indice == 0:
            self.next = Chainon(self.val, self.next)
            self.val = valeur
        else:
            if self.next is None:
                self.next = Chainon(valeur)
            else:
                self.next.inserer(valeur, indice-1)

    def supprimer(self:C, indice:int) ->None:
        """ Supprime le chainon en position indice de la liste chainée. """
        if len(self) == 1:
            raise ValueError("Impossible de supprimer le seul élément")
        if indice == 0:
            a_supprimer = self.next
            self.val = self.next.val
            self.next = self.next.next
            del a_supprimer
        elif indice == 1:
            a_supprimer = self.next
            self.next = self.next.next
            del a_supprimer
        else:
            self.next.supprimer(indice-1)

    def occurences(self:C, valeur:V) ->int:
        """ Renvoie le nombre d’occurrence de valeur dans la liste chainée. """
        if self.next == None:
            if self.val == valeur:
                return 1
            else:
                return 0
        else:
            if self.val == valeur:
                return 1 + self.next.occurences(valeur)
            else:
                return 0 + self.next.occurences(valeur)


    def premiere_occurence(self:C, valeur:V, indice=0) ->int:
        """ Renvoie l'indice de la première occurrence de valeur dans la liste chainée. """
        if self.val == valeur:
            return indice
        if self.next == None:
            return -1
        else:
            return self.next.premiere_occurence(valeur, indice+1)

    def identique(self:C, autre:C) ->bool:
        """ Renvoie True si les deux chaines contiennent les mêmes valeurs dans le même ordre, et False sinon. """
        if(self.next == None and autre.next == None):
            if self.val == autre.val:
                return True
        else:
            if self.val == autre.val:
                return self.next.identique(autre.next)
        return False