GoupillWiki

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.
====== Module Pile ======

{{ :nsi:modules:pile.py |}}

<Code python linenums>
'''
module: pile
synopsys: définition d'une pile au format liste chaînée
'''

class Noeud:
    '''
    noeud élémentaire de la pile
    '''
    def __init__(self, value):
      '''
      value: valeur du noeud à créer
      '''
      self.__value = value
      self.__next = None
      self.__orphan = True # n'a pas de prédecesseur

    def __str__(self):
        '''
        transtypage -> str
        '''
        return str(self.__value)

    def __repr__(self):
        '''
        représentation console
        '''
        return "<Noeud:{}>".format(str(self.__value))

    def get_next(self):
        '''
        accesseur: renvoie le noeud suivant
        '''
        return self.__next

    def get_value(self):
        '''
        accesseur: renvoie la valeur contenu dans le noeud
        '''
        return self.__value

    def cut_next(self):
        '''
        détache la suite de la chaîne
        '''
        if self.__next != None:
            self.__next.__orphan = True
        self.__next = None

    def insert_prev(self, value):
        '''
        value: valeur insèrée à gauche
        result: le noeud créé
        précondition : self est orphelin
        '''
        assert self.__orphan, "Impossible d'insérer à gauche, le nœud n'est pas orphelin."
        node = Noeud(value)
        node.__next = self
        self.__orphan = False
        return node

class NodeIterator:
    '''
    Utilisé pour doter permettre d'utiliser for in avec la pile
    '''
    def __init__(self, node):
        self.__node = node

    def __next__(self):
        if self.__node == None:
            raise StopIteration
        value = self.__node.get_value()
        self.__node = self.__node.get_next()
        return value

class Pile:
    '''
    Pile sous forme d'une liste chaînée
    '''

    def __init__(self, size = 0):
        '''
        size: taille maximale, 0 si pas de limite
        '''
        self.__head = None
        self.__count = 0
        self.__size = size

    def length(self):
        """
        :returns: le nombre d'éléments de la pile
        """
        return self.__count

    def is_empty(self):
        return self.__head == None

    def push(self, value):
        '''
        insère une valeur en première postion
        précondition : pas déjà plein
        '''
        assert self.__size == 0 or self.__size > self.__count, "Pile pleine"
        self.__count += 1
        if self.__head != None:
            self.__head = self.__head.insert_prev(value)
            return
        node = Noeud(value)
        self.__head = node

    def pop(self):
        '''
        supprime la valeur en première position
        result: valeur supprimée
        précondition: pile non vide
        '''
        assert not self.is_empty(), "Pop sur une pile est vide"
        self.__count -= 1
        delNode = self.__head
        self.__head = delNode.get_next()
        delNode.cut_next()
        return delNode.get_value()

    # Fonctions supplémentaires

    def __str__(self):
        '''
        transtypage -> str
        '''
        if self.is_empty():
            return ">>[ ]"
        return ">>[" + ":".join([str(it) for it in self]) + "]"

    def __repr__(self):
        '''
        affichage console
        '''
        return "<Pile {}>".format(str(self))

    def __iter__(self):
        return NodeIterator(self.__head)

    @classmethod
    def make(cls, *items):
        '''
        crée une pile contenant les items passés en argument
        '''
        p = cls()
        for it in items[::-1]:
            p.push(it)
        return p
</Code>