#I.1

def SelectionConstante(table,indice,constante):
    sortie = []
    for enregistrement in table:
        if(enregistrement[indice]==constante):
            sortie.append(enregistrement)
    return sortie

#I.2
# Ce programme est de complexité O(n) avec n la taille de la table. En effet, toutes les instructions sont en temps constant et la boucle parcours chacun des n éléments de la table une et une seule fois.

#I.3

def SelectionEgalité(table,indice1,indice2):
    sortie = []
    for enregistrement in table:
        if(enregistrement[indice1]==enregistrement[indice2]):
            sortie.append(enregistrement)
    return sortie

#I.4
def ProjectionEnregistrement(enregistrement,listeIndices):
    newregistrement = []
    for i in listindices:
        newregistrement.append(enregistrement[i])
    return newregistrement
#I.5
def Projection(table, listeIndices):
    sortie = []
    for enregistrement in table:
        sortie.append(ProjectionEnregistrement(enregistrement))
    return sortie

#I.6

def ProduitCartesien(table1,table2):
    sortie = []
    for enreg1 in table1:
        for enreg2 in table2:
            sortie.append(enreg1+enreg2)
    return sortie
    
#I.7

def jointEnregistrementsSaufIndice(enreg1,enreg2,indice2):
    sortie = [] + enreg1
    for i in range(0,indice2):
        sortie.append(enreg2[i])
    for i in range(indice2+1,len(enreg2)):
        sortie.append(enreg2[i])
    return sortie
def Jointure(table1,table2,indice1,indice2):
    sortie = []
    for enreg1 in table1:
        for enreg2 in table2:
            if(enreg1[indice1]==enreg2[indice2]):
                sortie.append(jointEnregistrementsSaufIndice(enreg1,enreg2,indice2))
    return sortie

#I.8
# La complexité est en O(n1*n2*(k2-1))
# En effet, la fonction jointEnregistrementSaufIndice effectue une copie de l'enregistrement (copie = somme avec la liste vide) en temps constant, puis deux boucles qui s'executent respectivement (indice1) et (k2-indice1-1), donc une complexité pour cette fonction en O(k2-1)
# Enfin, la fonction Jointure est constituée d'une instruction en temps constant, de deux boucles imbriquées s'executant respectivement n1 et n2 fois. Le contenu de la boucle est en complexité O(1 ou k2-1) donc dans le pire des cas, O(k2-1) d'où la complexité donnée.

#I.9
def egal(liste1,liste2):
    if(len(liste1) != len(liste2)):
        return False
    for i in range(len(liste1)):
        if(liste1(i)==liste2(i)):
            return False
    return True
    
def SupprimerDoublons(table):
    sortie = []
    for ei in range(len(table)):
        oups = False
        for eii in range(ei):
            if(egal(table[ei],table[eii])):
                oups = True
        if(not oups):
            sortie.append(table[ei])
    return sortie
        

#I.10
# La fonction égal est de complexité (dans le pire des cas) O(n*n) avec n la longeur commune des deux liste (on peut considérer n'importe laquelle des deux, puisque si l'une est plus longue que l'autre, le coût sera constant).
# La fonctions SupprimerDoublons effectue deux boucles s'executant n (longeur de la table) fois pour la première et ei pour la deuxième. Le tout s'execute donc 1+2+3+…+n fois , c'est à dire environ n*n/2.
# La fonction egal étant appelé à chaque fois sur des liste de taille k, l'arité de la table, la complexité totale est donc en O(n*n/2*k)