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

#Exercice 1.1

def longueur_r(l):
    if l is None:
        return 0
    else:
        return 1 + longueur_r(l.suivante)

def longueur_i(l):
    res = 0
    c = l
    while l is not None:
        res = res + 1
        c = c.suivante
    return res

#Exercice 1.2

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 nieme_element_i(l, n):
    if n < 0:
        raise IndexError ("Indice invalide")
    i = 0
    c = l
    while i < n and c is not None:
        i = i + 1
        c = c.suivante
    if c is None:
        raise IndexError ("Indice invalide")
    return c.valeur

#Exercice 1.3

def chaine (l):
    r = "["
    c = l
    while c is not None:
        r = r + str (c.valeur)
        if c.suivante is not None:
            r = r + ", "
        c = c.suivante
    r = r + "]"
    return r

#Exercice 2.1

def concatener (l1, l2):
    if l1 is None:
        return l2
    else:
        return Cellule(l1.valeur, concatener(l1.suivante, l2))

#Exercice 2.2
def concatener_mod (l1, l2):
    if l1 is None:
        return l2
    c = l1
    while c.suivante is not None:
        c = c.suivante
    c.suivante = l2
    return l1

l1 = Cellule(1,Cellule(2, Cellule(3, None)))
l2 = Cellule(4,Cellule(5, Cellule(6, None)))

l3 = concatener(l1, l2)
print (chaine(l1), chaine(l2), chaine (l3))

# Danger, on crée une liste cyclique 1,2,3,1,2,3,1,2,3,...
# la fonction chaine va boucler jusqu'a saturer la mémoire.
# l4 = concatener_mod(l1, l1)
# print (chaine(l1), chaine(l2), chaine (l4))

#Exercice 2.3
# La fonction concatener (l1, l2) est linéaire en la
# taille de l1 (elle parcourt chaque cellule de l1 une fois)



#Exercice 3.1

def renverser (l):
    res = None
    c = l
    while c is not None:
        res = Cellule(c.valeur, res)
        c = c.suivante
    return res


#Exercice 3.2
# La fonction renv_r renvoie une copie de la liste l
# renversée. Sa complexité est quadratique (proportionnelle
# au carré de la taille de l). En effet, la fonction renv_r
# applique essentiellement l'algorithme naif suivant :
# Si l n'est pas vide, elle est de la forme
# Cellule(v, l')
# (1) renverser l' (appel récursif)
# (2) ajouter v à la fin
# pour ajouter v à la fin, on le mets dans un petite liste
# de 1 élément, et on utilise la concaténation.
# Si on appelle n le nombre d'éléments dans l, alors on fait:
# - n appels récursifs
# - à chaque appel une concaténation
# les concaténations se font sur des listes de taille:
# n-1, puis n-2, puis... puis 1, puis 0
# le coût total est donc 0+1+2+... + (n-1) ~ n^2


#Exercice 3.3

def est_trie(l):
    if l is None or l.suivante is None:
        return True
    else:
        v1 = l.valeur
        v2 = l.suivante.valeur
        return v1 <= v2 and est_trie(l.suivante)

#Exercice 4

class Liste:

    def __init__(self):
        self.tete = None

#Exercice 4.1

    def longueur(self):
        return longueur_i(self.tete)

    def est_vide(self):
        return self.tete is None

    def nieme_element(self, n):
        return nieme_element_i(self.tete, n)

#Exercice 4.2

    def ajoute(self, x):
        self.tete = Cellule(x, self.tete)

    def retire(self):
        """Retire l'élément en tête. Suppose que la liste est non vide"""
        assert(not self.est_vide())
        v = self.tete.valeur
        self.tete = self.tete.suivante
        return v

#Exercice 4.3
    def concat(self, l2):
        self.tete = concatener(self.tete, l2)


#Exercice 4.4
    def __str__(self):
        return chaine(self.tete)

#Exercice 4.5
    def __add__(self, l2):
        return self.concat(l2)

    def __len__(self):
        return self.longueur()

    def __getitem__(self, n):
        return self.nieme_element(n)


#Exercice avancé 5.4, voir la définition ci-dessous.
    def __iter__(self):
        return ListeIter(self.tete)



##Exercices avancés

#Exercice 5.1

def fusion(l1, l2, f):
    if l1 is None:
        return l2
    elif l2 is None:
        return l1
    else:
        v1 = l1.valeur
        v2 = l2.valeur
        if f(v1, v2):
            return Cellule(v1, fusion(l1.suivante, l2))
        else:
            return Cellule(v2, fusion(l1, l2.suivante))


#Exercice 5.2, version iterative pour changer
def partage (l):
    l1 = None
    l2 = None
    c = l
    while c is not None:
        l1 = Cellule(c.valeur, l1)
        c = c.suivante
        l1, l2 = l2, l1 
    return (l1, l2)


def tri_fusion (l):
    #Une liste de taille 0 ou 1 est triée
    if l is None or l.suivante is None:
        return l
    else:
        l1, l2 = partage (l)
        t1 = tri_fusion (l1)
        t2 = tri_fusion (l2)
        return fusion (l1, l2)        


# Un itérateur sur les listes
class ListeIter:
    def __init__(self, cell):
        self.tete = cell

    def __next__(self):
        if self.tete is None:
            raise StopIteration
        else:
            v = self.tete.valeur
            self.tete = self.tete.suivante
            return v

l = Liste()
l.ajoute(1)
l.ajoute(2)
l.ajoute(3)

for i in l:
    print(i)




#Exercice 5.4
def concatener_i (l1, l2):
    #Cellule permettant de stocker le résultat
    #de la concaténation dans None
    #cela évite de gérer cela comme un cas particulier
    #La première cellule de res ne doit pas être renvoyée.
    res = Cellule("A NE PAS RENVOYER", None)
    c = l1
    cr = res
    while c is not None:
        cell = Cellule(c.valeur, None)
        cr.suivante = cell
        cr = cell
        c = c.suivante
    cr.suivante = l2
    return res.suivante

l1 = Cellule(1,Cellule(2, Cellule(3, None)))
l2 = Cellule(4,Cellule(5, Cellule(6, None)))

l3 = concatener(l1, l1)
print (chaine(l1), chaine(l1), chaine (l3))