'''INTERFACE d'une structure de données IMMUABLE Liste Contiguë
 
Description des types non natifs utilisés dans les fonctions
+ Element : le type des éléments disponibles dans votre Liste si elle est homogène.
+ Case    : la référence d'une case : un tuple (Liste, indice)
+ Liste   : la référence d'un tableau
 
Opérations primitives de la Liste contiguë
------------------------------------------
 
+ nouvelleListe() -> Liste
+ estListeVide(lst:'Liste') -> bool
+ longueur(lst:'Liste') -> int
+ ieme(lst:'Liste Non Vide', i:int) -> 'Elément'
+ inserer(lst:'Liste', elt:'Element', i:int) -> 'Liste'
+ supprimer(lst:'Liste Non Vide', i:int) -> 'Liste'
 
+ acces(lst:'Liste Non Vide') -> 'Case'
+ contenu(c:'Case') -> 'Element'
+ successeur(c:'Case Non Fin') -> 'Case'
+ precedent(c:'Case Non Tête') -> 'Case'
 
Fonctions d'interface supplémentaires
-------------------------------------
 
+ insererTete(lst:'Liste', elt:'Element') -> 'Liste'
+ supprimerTete(lst:'Liste Non Vide') -> 'Liste'
+ accesTete(lst:'Liste Non Vide') -> 'Case'
 
+ insererFin(lst:'Liste', elt:'Element') -> 'Liste'
+ supprimerFin(lst:'Liste Non Vide') -> 'Liste'
+ accesFin(lst:'Liste Non Vide') -> 'Case'
 
+ premier(lst:'Liste Non Vide') -> 'Element'
+ dernier(lst:'Liste Non Vide') -> 'Element'
 
+ insererFin(lst:'Liste', elt:'Element') -> 'Liste'
+ supprimerFin(lst:'Liste Non Vide') -> 'Liste'
+ accesFin(lst:'Liste Non Vide') -> 'Case'
 
+ concatener(gauche:'Liste', droite:'Liste') -> 'Liste'
+ rechercher(lst1:'Liste', elt:'Element') -> int
 
+ representerListe(lst:'Liste') -> str
+ liste(x:'list|tuple|int|float|str') -> 'Liste'
+ copier(lst:'Liste') -> 'Liste'
 
'''
 
# Importation : aucune
# Déclaration des CONSTANTES : aucune
 
# Déclaration des opérations primitives
 
def nouvelleListe() -> 'Liste':
    '''Renvoie une liste vide'''
    return []
 
def estListeVide(lst:'Liste') -> bool:
    '''Prédicat qui renvoie True si la liste est vide'''
    return lst == []
 
def longueur(lst:'Liste') -> int:
    '''Renvoie le nombre d'éléments stockés dans lst'''
    return len(lst)
 
def ieme(lst:'Liste Non Vide', i:int) -> 'Element':
    '''Renvoie le contenu de la Case de position i VALIDE dans la liste NON VIDE lst'''
    return lst[i]
 
def inserer(lst:'Liste', elt:'Elément', i:int) -> 'Liste':
    '''Renvoie une Liste basée sur lst où elt est en position VALIDE i'''
 
    nb = len(lst) + 1
    nouveau = [None for _ in range(nb)]  # 1 - nouveau tableau avec une case en plus 
    for k in range(0, i):                # 2 - copie les éléments des indices 0 à i-1 sans décalage               
        nouveau[k] = lst[k]
    for k in range(i, len(lst)):         # 3 - décalage à droite des éléments d'indice i et plus
        nouveau[k+1] = lst[k]
    nouveau[i] = elt                     # 4 - elt à la position i
 
    return nouveau
 
def supprimer(lst:'Liste Non Vide', i:int) -> 'Liste':
    '''Renvoie une Liste basée sur lst NON VIDE en supprimant la case i VALIDE'''
 
    nb = len(lst) - 1
    nouveau = [None for _ in range(nb)]  # 1 - nouveau tableau avec une case en moins 
    for k in range(0, i):                # 2 - copie les éléments des indices 0 à i-1 sans décalage               
        nouveau[k] = lst[k]
    for k in range(i+1, len(lst)):        # 3 - décalage à gauche des éléments d'indice i+1 et plus
        nouveau[k-1] = lst[k]
 
    return nouveau
 
def acces(lst:'Liste Non Vide', i:int) -> 'Case':
    '''Renvoie la référence de la case d'indice i VALIDE dans la liste lst NON VIDE'''
    return (lst, i)  # on crée un tuple-case (quelle liste ?, quel indice ?)
 
def contenu(c:'Case') -> 'Elément':
    '''Renvoie le contenu de la case valide fournie'''
 
    lst = c[0]         # on récupère la liste contenant notre case
    i =   c[1]         # on récupère l'indice de notre case
    return lst[i]      # on renvoie l'élément stocké à cet endroit
 
def successeur(c:'Case Non Finale') -> 'Case':
    '''Renvoie le case qui succède à la case fournie (qui ne doit pas être la dernière)'''
    lst = c[0]         # on récupère la liste contenant notre case
    i =   c[1]         # on récupère l'indice de notre case    
    return (lst, i+1)  # on crée un tuple-case correspond à la case suivante
 
def precedent(c:'Case Non Tête') -> 'Case':
    '''Renvoie le case qui précéde la case fournie (qui ne doit pas être la première)'''
    lst = c[0]         # on récupère la liste contenant notre case
    i =   c[1]         # on récupère l'indice de notre case    
    return (lst, i-1)  # on crée un tuple-case correspond à la case précédente
 
 
# Déclaration des fonctions d'interface supplémentaires
 
def insererTete(lst:'Liste', elt:'Elément') -> 'Liste':
    '''Renvoie une Liste basée sur lst où elt est en Tête'''
    return inserer(lst, elt, 0)
 
def supprimerTete(lst:'Liste Non Vide') -> 'Liste':
    '''Renvoie une Liste basée sur lst NON VIDE en supprimant la Tête'''
    return supprimer(lst, 0)
 
def accesTete(lst:'Liste Non Vide') -> 'Case':
    '''Renvoie la référence de la case de tête dans lst NON VIDE'''
    return acces(lst, 0)
 
 
def insererFin(lst:'Liste', elt:'Elément') -> 'Liste':
    '''Renvoie une Liste basée sur lst où elt est en Fin'''
    return inserer(lst, elt, longueur(lst))
 
def supprimerFin(lst:'Liste Non Vide') -> 'Liste':
    '''Renvoie une Liste basée sur lst NON VIDE en supprimant la fin'''
    return supprimer(lst, longueur(lst) - 1)
 
def accesFin(lst:'Liste Non Vide') -> 'Case':
    '''Renvoie la référence de la case de fin dans lst NON VIDE'''
    return acces(lst, longueur(lst) - 1)
 
 
def premier(lst:'Liste Non Vide') -> 'Element':
    '''Renvoie la valeur de tête de lst NON VIDE'''
    return ieme(lst, 0)
 
def dernier(lst:'Liste Non Vide') -> 'Element':
    '''Renvoie la valeur de fin de lst NON VIDE'''
    return ieme(lst, longueur(lst) - 1)
 

 
def representerListe(lst:'Liste') -> str:
    '''Renvoie une représentation de la Liste sous forme d'une séquence commençant par la tête'''
    return str(lst).replace(',',' -> ').replace('[','').replace(']','')
 
def concatener(gauche:'Liste', droite:'Liste') -> 'Liste':
    '''Renvoie une nouvelle liste commençant par la tête de gauche vers la fin de droite'''
    nouveau = nouvelleListe()            # 1 - nouvelle liste pour la concaténation
    ng = longueur(gauche)
    for i in range(ng):                  # 2 - on copie les éléments de gauche 
        nouveau = inserer(nouveau, ieme(gauche, i), i)
    nd = longueur(droite)
    for i in range(nd):                  # 3 - on copie les éléments de droite
        nouveau = inserer(nouveau, ieme(droite, i), ng + i)
    return nouveau
 
def concatener_version_primitive(gauche:'Liste', droite:'Liste') -> 'Liste':
    '''Renvoie une nouvelle liste commençant par la tête de gauche vers la fin de droite'''
    nb = len(gauche) + len(droite)
    nouveau = [None for _ in range(nb)]  # 1 - nouveau tableau avec autant de cases que les deux autres 
    for i in range(0, len(gauche)):      # 2 - on copie les éléments de gauche 
        nouveau[i] = gauche[i]
    ng = len(gauche)                      # on récupère le nb d'élémnets à gauche
    for i in range(0, len(droite)):  # 3 - on copie les éléments de droite
        nouveau[ng+i] = droite[i]
    return nouveau
 
def rechercher(lst:'Liste', elt:'Element') -> int:
    '''Renvoie la position éventuelle de elt dans lst, -1 si non trouvé'''
    for i in range(longueur(lst)):   # Pour chaque indice valide de la liste lst
        if ieme(lst, i) == elt:      # si la case i contient l'élément cherché
            return i                 # répondre en renvoyant l'indice de la case
    return -1                        # si on arrive ici, c'est qu'on a pas trouvé
 
def liste(x) -> 'Liste':
    '''Renvoie une liste générée à partir de x'''
 
    nouvelle = nouvelleListe()
 
    if type(x) == list or type(x) == tuple:
        for i in range(len(x)-1, -1, -1):
            nouvelle = [v for v in x]
 
    elif type(x) == dict:
        for couple in dict.items():
            nouvelle = insererTete(nouvelle, couple)
 
    elif type(x) == int or type(x) == float or type(x) == str or type(x) == bool:
        nouvelle = insererTete(nouvelle, x)
 
    return nouvelle
 
def copie(lst:'Liste') -> 'Liste':
    '''Renvoie une copie peu profonde de la liste lst envoyée'''
    return [v for v in lst]
 
 
# Instructions du programme principal
 
if __name__ == '__main__':
 
    # Ces fonctions ne seront en mémoire qu'en lancement direct
 
    def tester_insererTete():
        a = nouvelleListe()
        a = insererTete(a, 5)
        assert a == [5]
        a = insererTete(a, 2)
        assert a == [2, 5]
        b = insererTete(a, 20)
        assert a == [2, 5]
        assert b == [20, 2, 5]
        print('Test OK pour insererTete()')
 
    def tester_supprimerTete():
        a = nouvelleListe()
        a = insererTete(a, 5)
        a = insererTete(a, 2)
        b = supprimerTete(a)
        assert a == [2, 5]
        assert b == [5]
        c = supprimerTete(b)
        assert estListeVide(c)
        print('Test OK pour supprimerTete()')
 
    def tester_accesTete():
        a = nouvelleListe()
        a = insererTete(a, 5)
        a = insererTete(a, 2)
        assert accesTete(a) == ([2, 5], 0)
        print('Test OK pour accesTete()')
 
    def tester_contenu():
        a = nouvelleListe()
        a = insererTete(a, 5)
        b = insererTete(a, 2)
        assert contenu(accesTete(a)) == 5
        assert contenu(accesTete(b)) == 2
        print('Test OK pour contenu()')
 
    def tester_successeur():
        a = nouvelleListe()
        b = insererTete(a, 5)
        c = insererTete(b, 2)
        d = insererTete(c, 20)
        assert successeur(accesTete(d)) == ([20, 2, 5], 1)
        assert successeur(accesTete(c)) == ([2, 5], 1)
        print('Test OK pour successeur()')
 
    def tester_longueur():
        a = nouvelleListe()
        b = insererTete(a, 5)
        c = insererTete(b, 2)
        assert longueur(a) == 0
        assert longueur(b) == 1
        assert longueur(c) == 2
        print('Test OK pour longueur()')
 
    def tester_acces():
        a = nouvelleListe()
        b = insererTete(a, 5)
        c = insererTete(b, 2)
        assert acces(b, 0) == ([5], 0)
        assert acces(c, 0) == ([2, 5], 0)
        assert acces(c, 1) == ([2, 5], 1)
        print('Test OK pour acces()')
 
    def tester_ieme():
        a = nouvelleListe()
        b = insererTete(a, 5)
        c = insererTete(b, 2)
        assert ieme(b, 0) == 5
        assert ieme(c, 0) == 2
        assert ieme(c, 1) == 5
        print('Test OK pour lire()')
 
    def tester_inserer():
        a = nouvelleListe()
        b = insererTete(a, 5)
        c = insererTete(b, 2)
        d = inserer(c, 20, 1)
        assert d == [2, 20, 5]
        print('Test OK pour inserer()')
 
    def tester_supprimer():
        a = nouvelleListe()
        b = insererTete(a, 5)
        c = insererTete(b, 2)
        d = inserer(c, 20, 1)
        e = supprimer(d, 2)
        assert d == [2, 20, 5]
        assert e == [2, 20]
        print('Test OK pour supprimer()')
 
    def tester_concatener():
        a = nouvelleListe()
        b1 = insererTete(a, 5)
        b2 = insererTete(b1, 2)
        b3 = insererTete(b2, 50)
        c1 = insererTete(a, 20)
        c2 = insererTete(c1, 200)
        d = concatener(b3, c2)
        assert d == [50, 2, 5, 200, 20]
        print('Test OK pour concatener()')
 
    def tester_rechercher():
        a = nouvelleListe()
        b = insererTete(a, 5)
        c = insererTete(b, 2)
        d = inserer(c, 20, 1)
        assert rechercher(d, 30) == -1
        assert rechercher(d, 20) == 1
        assert rechercher(d, 2) == 0
        assert rechercher(d, 5) == 2
        print('Test OK pour rechercher()')
 
    def tester():  # Tous les tests
        tester_insererTete()
        tester_supprimerTete()
        tester_accesTete()
        tester_contenu()
        tester_successeur()
        tester_longueur()
        tester_acces()
        tester_ieme()
        tester_inserer()
        tester_supprimer()
        tester_concatener()
        tester_rechercher()
 
    print("Module lancé directement, il ne s'agit pas d'une importation")
    tester()