Listes avec partage de suffixe

On se propose de manipuler des listes relativement complexes, histoire de nous tester un peu.

figure 4.3: quatre listes partageant des cellules : ’SE’, ’PASSE’, ’DEVISSE’, ’DEPASSE’

On utilise ici des listes partageant des cellules (par exemple pour stocker des mots finissant de la même manière). Comme toute cellule n’a qu’un seul champ suivant, on ne peut partager que la fin des listes.

Il est nécessaire pour pouvoir implémenter les différentes opérations de savoir quelles sont les cellules faisant parties de plusieurs listes. On se propose donc de rajouter dans la classe Cellule un champ utilisation comptant le nombre de pointeurs la référençant.

On peut voir ci-dessus que la cellule contenant le ’S’ de ’SE’ est référencée par deux autres cellules (en plus de la liste ’SE’) ce qui lui vaut une utilisation de 3.

class Cellule:
    """
    une cellule d’une liste. contient une valeur, un pointeur
    vers la cellule suivante, un compteur comptabilisant
    combien de listes ou de cellules pointent dessus.
    """
    # pylint: disable=too-few-public-methods
    def __init__(self, valeur, suivant=None):
        self.valeur = valeur
        self.suivant = suivant
        self.utilisation = 1

On vous demande de compléter la classe Liste du fichier suffixes.py. Prenez bien le temps de comprendre ce qui est attendu de vous. Le code de suffixe est complexe. Que doit-il se passer si on ajoute dans notre exemple ’NT’ à ’DEPASSE’ ?

class Liste:
    """
    liste de cellules.
    des listes differentes peuvent partager des cellules communes.
    """
    def __init__(self, mot):
        """
        transforme un mot en liste non-partagee.
        """
        premiere_cellule = None
        self.taille = 0
        for lettre in reversed(mot):
            premiere_cellule = Cellule(lettre, premiere_cellule)
            self.taille += 1
        self.tete = premiere_cellule

    def cellules(self):
        """
        iterateur sur toute les cellules de la liste.
        """
        cellule_courante = self.tete
        while cellule_courante is not None:
            yield cellule_courante
            cellule_courante = cellule_courante.suivant

    def suffixe(self, autre):
        """
        ajoute la liste autre a la fin de la liste self
        (en partageant les cellules communes).
        si la fin de self etait deja partagee avec quelqu’un, alors
        on dedouble toute la partie partagee avant l’ajout.
        """
        # TODO
        pass

    def __del__(self):
        """
        destructeur.
        """
        # TODO
        pass

4.3 Listes avec partage de suffixe