'''MODULE d'implémentation d'une Pile sous forme d'une liste Chaînée MUABLE
  en utilisant des Cellules-Objets pour former une liste chaînée
  où la Tete de la liste correspond au Sommet de la Pile.
  
  On peut manipuler directement l'objet Pile via les méthodes.
  On peut utiliser les fonctions sans se rendre compte qu'on manipule un objet.
  
Méthodes primitives de la classe Pile
-------------------------------------
CST : Pile() -> 'Pile'
CST : Pile.est_pile_vide(p:'Pile') -> bool
CST : Pile.empiler(p:'Pile', elt:'Element') -> None
CST : Pile.depiler(p:'Pile NON VIDE') -> 'Element'
CST : Pile.lire_sommet(p:'Pile NON VIDE') -> 'Element'

Fonctions primitives de la Pile
-------------------------------
CST : Pile() -> 'Pile'
CST : Pile.est_pile_vide(p:'Pile') -> bool
CST : Pile.empiler(p:'Pile', elt:'Element') -> None
CST : Pile.depiler(p:'Pile NON VIDE') -> 'Element'
CST : Pile.lire_sommet(p:'Pile NON VIDE') -> 'Element'


'''
# Déclaration des classes Cellule et Pile

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

class Pile:
    def __init__(self):
        self.sommet = None
     
    def est_pile_vide(self:'Pile') -> bool:
        return self.sommet is None
       
    def empiler(self:'Pile', elt:'Element') -> None:
        '''Rajoute une nouvelle cellule contenant elt au sommet de la Pile'''
        nouvelle = Cellule(elt, None)  # Etape 1 : création de la cellule
        nouvelle.s = self.sommet       # Etape 2 : on relie la nouvelle cellule à l'"ancien" sommet
        self.sommet = nouvelle         # Etape 3 : modification de la liste
        
    def depiler(self:'Pile NON VIDE') -> 'Element':
        '''Supprime la cellule de tête et renvoie l'élément qui y était stocké'''
        ancienne_valeur = self.sommet.v  # Etape 1 : on mémorise la valeur au sommet
        self.sommet = self.sommet.s      # Etape 2 : le sommet devient le successeur du sommet supprimé
        return ancienne_valeur           # Etape 3 : on renvoie la valeur stockée

    def lire_sommet(self:'Pile NON VIDE') -> 'Element':
        '''Renvoie la valeur au sommet de la Pile'''
        return self.sommet.v

# Déclaration des fonctions primitives si on veut "cacher" l'objet

def nouvelle_pile() -> 'Pile':
    '''Renvoie une nouvelle Pile vide'''
    return Pile()
 
def est_pile_vide(p:'Pile') -> bool:
    '''Prédicat qui renvoie True si p est une Pile vide'''
    return p.est_pile_vide()

def empiler(p:'Pile', elt:'Element' ) -> None:
    '''Rajoutant elt au sommet de la pile p'''
    p.empiler(elt)
    
def depiler(p:'Pile NON VIDE') -> 'Element':
    '''Dépile et renvoie le sommet de la pile p'''
    return p.depiler()
 
def lire_sommet(p:'Pile NON VIDE') -> 'Element':
    '''Renvoie la valeur actuellement au sommet de la Pile p NON VIDE'''
    return p.lire_sommet()


# Programme-test

if __name__ == '__main__':
    p = nouvelle_pile()
    empiler(p, 0)
    empiler(p, 5)
    empiler(p, 10)
    assert lire_sommet(p) == 10
    depiler(p)
    assert lire_sommet(p) == 5