# Complexités : on note n (éventuellement n1 ou n2) le nombre d'enregistrements et k (éventuellement k1 ou k2) le nombre d'attributs d'une table.

# Exercice 1

def selection_constante(table, indice, valeur):
    """Simule une requête de sélection avec test d'égalité à une constante.
    """
    res = [] # O(1)
    for enregistrement in table: # O(n)
        if enregistrement[indice] == valeur: # O(1)
            res.append(enregistrement) # O(1)
    return res # O(n) au total

# Exercice 2

def selection_egalite(table, indice1, indice2):
    """Simule une requête de sélection avec test d'égalité entre deux attributs.
    """
    res = []
    for enregistrement in table: # O(n)
        if enregistrement[indice1] == enregistrement[indice2]: # O(1)
            res.append(enregistrement) # O(1)
    return res # O(n) au total

# Exercice 3

def projection_enregistrement(enregistrement, indices):
    """Restreint un enregistrement à la liste des indices à garder.
    """
    rep = [] # O(1)
    for i in indices: # O(k)
        rep.append(enregistrement[i]) # O(1)
    return rep # O(k) au total

def projection(table, indices):
    """Simule une requête de projection sur une table entière.
    """
    rep = [] # O(1)
    for enregistrement in table: # O(nk)
        rep.append(projection_enregistrement(enregistrement, indices)) # O(k)
    return rep # O(nk) au total

# Exercice 4

def produit_cartesien(table1, table2):
    """Simule un produit cartésien entre deux tables.
    """
    rep = [] # O(1)
    for enregistrement1 in table1: # O(n1 n2 (k1 + k2))
        for enregistrement2 in table2: # O(n1 (k1 + k2))
            rep.append(enregistrement1 + enregistrement2) # O(k1 + k2)
    return rep # O(n1 n2 (k1 + k2)) au total

# Exercice 5

def jointure(table1, table2, indice1, indice2):
    """Simule une jointure symétrique suivant une égalité d'attributs
    entre deux tables. L'attribut de la deuxième table ne sera pas maintenu.
    """
    rep = [] # O(1)
    for enregistrement1 in table1: # O(n1 n2 (k1 + k2))
        for enregistrement2 in table2: # O(n1 (k1 + k2))
            if enregistrement1[indice1] == enregistrement2[indice2]: # O(1) (sans compter l'intérieur)
                e2 = enregistrement2[:indice2] + enregistrement2[indice2+1:] # O(k2)
                rep.append(enregistrement1 + e2) # O(k1 + k2)
    return rep # O(n1 n2 (k1 + k2)) au total

# Exercice 6

def supprimer_doublons(table):
    """Renvoie la table sans ses doublons. Aucun effet de bord ne s'applique.
    """
    rep = [] # O(1)
    for enregistrement in table: # O(n²k)
        if enregistrement not in rep: # O(nk) # Pour information, le sujet de Polytechnique interdisait ce raccourci.
            rep.append(enregistrement) # O(1)
    return rep # O(n²k) au total

# Exercice 7 fait au fur et à mesure

# Exercice 8

# SQL : SELECT Note FROM Notes WHERE Etudiant = 42 AND Examen = 5

def exercice8():
    """Trouver la note de l'étudiant d'identifiant 42 à l'examen d'identifiant 5.
    """
    sel1 = selection_constante(NOTES, 0, 42) # Normalement il reste 5 éléments.
    sel2 = selection_constante(sel1, 1, 5) # Normalement il n'en reste qu'un…
    proj = projection(sel2, [2]) # … qui est une liste de taille 1. Attention à ne pas oublier les crochets !
    return proj[0][0]

# Exercice 9

# SQL : SELECT Nom, Prenom FROM Etudiants JOIN Notes ON Id = Etudiant WHERE Examen = 1 AND Note = 20

def exercice9():
    """Trouver le nom et le prénom de tous les étudiants qui ont eu 20 à l'examen numéro 1.
    """
    joint = jointure(ETUDIANTS, NOTES, 0, 0) # Normalement il y a 400 éléments.
    sel1 = selection_constante(joint, 4, 1) # Normalement il en reste 80, attention à l'indice !
    sel2 = selection_constante(sel1, 5, 20) # On garde ceux qui ont 20.
    proj = projection(sel2, [1, 2]) # Et ici les noms et prénoms, donc ce qu'on cherche.
    return proj

# Exercice 10

# SQL : SELECT COUNT(DISTINCT Id) FROM Etudiants JOIN Notes ON Id = Etudiant WHERE Note = 0

def exercice10():
    """Trouver le nombre d'étudiants ayant eu au moins une fois 0.
    """
    joint = jointure(ETUDIANTS, NOTES, 0, 0) # La même !
    sel = selection_constante(joint, 5, 0) # Toujours ce danger.
    proj = projection(sel, [0]) # Ceci est fait pour n'avoir que les identifiants et préparer un retrait des doublons.
    dist = supprimer_doublons(proj) # Et voici la liste de ceux qui ont eu au moins un zéro…
    return len(dist)

# Exercice 11

# SQL : SELECT DISTINCT Classe FROM Etudiants JOIN Notes On Etudiants.Id = Etudiant JOIN Examens ON Examen = Examens.Id WHERE Note = 19 AND Date = "19/12/2015"

def exercice11():
    """Trouver l'ensemble des classes où au moins un étudiant a eu 19 à l'examen du 19 décembre 2015.
    """
    joint1 = jointure(ETUDIANTS, NOTES, 0, 0) # On connaît la musique !
    joint2 = jointure(joint1, EXAMENS, 4, 0) # Le danger est déjà là !
    sel1 = selection_constante(joint2, 5, 19) # Maintenant on a l'habitude…
    sel2 = selection_constante(sel1, 6, "19/12/2015") # Attention aux guillemets !
    proj = projection(sel2, [3]) # L'attribut dont on veut retirer les doublons…
    dist = supprimer_doublons(proj) # … voilà qui est fait !
    return dist
    
# À quoi ont servi les exercices 2 et 4, me demanderez-vous ? Hé bien on peut se servir des exercices 2, 3 et 4 pour faire directement l'exercice 5.

def exercice_5_avec_2_3_et_4(table1, table2, indice1, indice2):
    if len(table1) == 0 or len(table2) == 0: # danger par la suite, on veut récupérer le nombre d'attributs
        return []
    k1 = len(table1[0]) # (ici)
    k2 = len(table2[0]) # (et là)
    pc = produit_cartesien(table1, table2)
    sel = selection_egalite(pc, indice1, k1 + indice2)
    les_attributs = []
    for i in range(k1 + k2):
        if i != k1 + indice2:
            les_attributs.append(i)
    proj = projection(sel, les_attributs)
    return proj # Et la complexité est asymptotiquement la même !