'''Module implémentant un File MUABLE
   en utilisant un tableau de deux Piles
 
Les Piles sont implémentées sous forme de tuples (sommet, reste de la pile)
Les Files sont implémentées sous forme de tableaux [pileEntree, pileSortie]
 
Fonctions primitives de la File
--------------------------------
... : nouvelle_file() -> 'File'
... : est_file_vide(f:'File') -> bool
... : enfiler(f:'File', elt:'Element') -> None
... : defiler(f:'File NON VIDE') -> 'Element'
... : lire_avant(f:'File NON VIDE') -> 'Element'
 
'''
 
# Fonctions primitives des PILES
 
def nouvelle_pile() -> 'Pile':
    '''Renvoie une Pile vide'''
    return ()
 
def est_pile_vide(p:'Pile') -> bool:
    '''Prédicat qui renvoie True si la pile est vide'''
    return p == ()
 
def empiler(p:'Pile', elt:'Element') -> 'Pile':
    '''Renvoie une nouvelle pile où elt est le sommet et pile la suite de notre nouvelle pile.'''
    return (elt, p)
 
def depiler(p:'Pile NON VIDE') -> 'Pile':
    '''Renvoie une nouvelle pile où on a supprimé l'ancien sommet d'une pile NON VIDE'''
    return p[1]
 
def lire_sommet(p:'Pile NON VIDE') -> 'Element':
    '''Renvoie la valeur stockée au sommet d'une pile NON VIDE'''
    return p[0]
 
# Fonctions primitives et d'interface de la File
 
def nouvelle_file() -> 'File':
    '''Renvoie la référence d'une File sous forme d'un tableau [pileEntree, pileSortie]'''
    pile_entree = nouvelle_pile() # inputStack en anglais
    pile_sortie = nouvelle_pile() # outputStack en anglais
    return [pile_entree, pile_sortie]
 
def est_file_vide(f:'File') -> bool:
    '''Prédicat qui renvoie True si la File est entièrement vide, False sinon'''
    return est_pile_vide(f[0]) and est_pile_vide(f[1])
 
def enfiler(f:'File', elt:'Element') -> None:
    '''Enfile l'élement elt dans la file f'''
    f[0] = empiler(f[0], elt)
 
def defiler(f:'File NON VIDE') -> 'Element':
    '''Défile la file NON VIDE f et renvoie l'élément supprimé'''
    if est_pile_vide(f[1]):
        deverser_entree_vers_sortie(f)
    valeur = lire_sommet(f[1])
    f[1] = depiler(f[1])
    return valeur
 
def lire_avant(f:'File NON VIDE') -> 'Element':
    '''Renvoie l'avant de la file NON VIDE f sans la modifier'''
    if est_pile_vide(f[1]):
        deverser_entree_vers_sortie(f)
    return lire_sommet(f[1])
 
# Fonctions hors interface
 
def deverser_entree_vers_sortie(f:'File') -> None:
    '''Déverse entièrement la pile d'entrée dans la pile de sortie'''
    while not est_pile_vide(f[0]):
        elt = lire_sommet(f[0])
        f[0] = depiler(f[0])
        f[1] = empiler(f[1], elt)
 
 
# Programme de test
     
if __name__ == '__main__':
    a = nouvelle_file()
    enfiler(a, 0)
    enfiler(a, 5)
    enfiler(a, 10)
    enfiler(a, 15)
     
    s = lire_avant(a)
    assert s == 0
     
    defiler(a)
    s = lire_avant(a)
    assert s == 5