##Exercice 1
## On reproduit juste assez du code des listes chaînées pour l'exercice

class Cellule:

    def __init__(self, val, sui):
        self.valeur = val
        self.suivante = sui


def nieme_element(l, n):
    if n < 0 or l is None:
        raise IndexError("Indice invalide")
    elif n == 0:
        return l.valeur
    else:
        return nieme_element(l.suivante, n-1)

def ajout_10000(l):
    """rajoute 10000 entiers en tête de liste"""
    c = l
    for i in range(10000):
        c = Cellule(i, c)
    return c

def f():
    l = None
    v = -1
    while v < 0:
        try:
            v = nieme_element(l, 8000)
        except:
            l = ajout_10000(l)
    print(v)

#décommenter pour lancer le programme.
#f()

#Le programme boucle et alloue de plus en plus de mémoire.  (il faut
#le tuer avec ctrl-c dans le terminal ou regarder sa machine
#s'effondrer)

#Au premier tour de boucle, la fonction lève l'exception IndexError
#(car la liste est vide). On passe dans le bloc except.
#Le code rajoute 10000 éléments à la liste avec une fonction itérative.
#Au deuxième tour de boucle, la fonction nieme_element *level l'excetpion
#RecursionError (car elle fait plus de 1000 appels récursifs)
#On retourne dans le except et on rajoute 10000 nouveaux éléments…

#Exercice 2.1

#Une classe vide, uniquement là pour que le type Pile existe
class Pile:
    pass


#opérations sur les piles
def pile_vide()-> Pile:
    pass

def est_vide(p : Pile) -> bool:
    pass

def empiler(p: Pile, v : object) -> None:
    pass

def depiler(p: Pile) -> object:
    pass


#Exercice 2.2
#On rappelle qu'en Python, + et * sont définis entre les types numériques (int, float, bool)
# + est aussi défini entre deux tableaux, deux chaînes et de tableaux d'octets (bytes)
# * est défini entre un entier ou un booléen et un tableau, une chaîne ou un tableau d'octets.
# On a donc au minimum:

def f(a : int, b : int, c : int) -> int:
    return a * b + c

def f(a : int, b : int, c : float) -> float:
    return a * b + c

def f(a : int, b : int, c : bool) -> int:
    return a * b + c

def f(a : int, b : float, c : int) -> float:
    return a * b + c

def f(a : int, b : float, c : float) -> float:
    return a * b + c

# ... 27 combinaisons au total pour les trois types int/bool/float


def f(a : int, b : str, c : str) -> str:
    return a * b + c

def f(a : int, b : bytes, c : bytes) -> bytes:
    return a * b + c

def f(a : int, b : list, c : list) -> list:
    return a * b + c

def f(a : bool, b : str, c : str) -> str:
    return a * b + c

def f(a : bool, b : bytes, c : bytes) -> bytes:
    return a * b + c

def f(a : bool, b : list, c : list) -> list:
    return a * b + c

### Au total au moins 33 combinaisons différentes !
### Morale de l'histoire, on peut passer toute une combinaison de
### valeurs farfelues à f et obtenir un résultat sans que ça plante.


#Exercice 3.1

def occurrences(t):
    occ = {}
    for i in t:
        if i in occ:
            occ[i] = occ[i] + 1
        else:
            occ[i] = 1
    return occ

#Exercice 3.2

def test(tri, t):
    occ = occurrences(t)
    tri(t)
    for i in range(0, len(t) - 1):
        assert t[i] <= t[i+1]

    assert occ == occurrences(t)