Listes triees circulaires

On s’intéresse dans cet exercice aux listes circulaires, triées, avec sentinelle.

La tête de liste est une sentinelle (contenant une valeur fictive). Elle nous permet de garantir que toute cellule a toujours une cellule suivante et une cellule précédente (ce qui permet de simplifier le code de suppression par exemple).

La cellule suivant la dernière est la sentinelle (aucun attribut suivant des cellules ne vaut donc None.)

Les valeurs des cellules sont triées par ordre croissant. La valeur de la sentinelle peut être librement choisie pour vous arranger.

Une des opérations demandées est d’implémenter une fonction decoupe construisant deux nouvelles listes en alternant les éléments d’une liste de départ.

#!/usr/bin/env python3
"""
listes triees, circulaires avec sentinelle.
"""

class Cellule:
    """
    valeur + suivant
    """
    #pylint: disable=too-few-public-methods
    def __init__(self, valeur, suivant=None):
        self.valeur = valeur
        self.suivant = suivant

class Liste:
    """
    liste circulaire triee, simplement chainee avec sentinelle.
    """
    def __init__(self, sentinelle, iterable=None):
        """
        remplit la liste avec les elements de l’iterable donne.
        ’sentinelle’ precise la valeur de la cellule sentinelle.
        pre-condition: l’iterable donne est trie.
        """
        # TODO
        pass

    def cellules(self, inclure_sentinelle=False):
        """
        renvoie un iterateur sur toutes les cellules de la liste.
        ’inclure_sentinelle’ est un booleen permettant de preciser
        si la sentinelle est incluse ou non dans les cellules iterees.
        """
        # TODO
        pass

    def decoupe(self):
        """
        coupe la liste en 2 (une cellule sur 2).
        par exemple (1,4,2,3,5) produit (1,2,5) et (4,3).
        renvoie les deux nouvelles listes.
        aucune nouvelle cellule n’est creee (hormis les sentinelles
        des deux nouvelles listes),
        en sortie la liste est vide.
        """
        # TODO
        pass

    def ajouter(self, valeur):
        """
        ajoute la valeur donnee a la bonne place dans la liste.
        pre-condition : valeur n’est pas la valeur de la sentinelle.
        """
        # TODO
        pass

    def supprimer(self, valeur):
        """
        supprime la premiere cellule contenant la valeur donnee.
        pre-condition : valeur n’est pas la valeur de la sentinelle.
        """
        # TODO
        pass

    def __str__(self):
        # TODO
        return ""

def test():
    """
    tests simples des differentes methodes (a completer).
    """
    entiers = Liste(float("inf"), range(8))
    pairs, impairs = entiers.decoupe()
    print(pairs, impairs)
    print(entiers)
    pairs.supprimer(4)
    pairs.supprimer(0)
    pairs.supprimer(2)
    pairs.supprimer(6)
    impairs.ajouter(6)
    impairs.ajouter(0)

if __name__ == "__main__":
    test()

4.2 Listes triées circulaires