"""
Structure de données pour représenter un ensemble, implémenté avec une
liste non-nécessairement triée.
"""

def cree_ensemble():
    """
    renvoie un ensemble vide
    Complexité: O(1)
    """
    return []

def taille_ensemble(ensemble):
    return len(ensemble)
    
def est_present(ensemble, elem):
    """
    renvoie True si elem est dans ensemble
    Complexité pire cas: n/2 itérations en moyenne, donc O(n)
    """
    for e in ensemble:
        if e == elem:
            return True
    return False
    
def ajoute_element(ensemble, elem):
    """
    Ajoute un élément à ensemble, renvoie True si l'élément était présent, False sinon
    Complexité pire cas: O(n) - identique à est_present(ensemble, elem)
    """
    if est_present(ensemble, elem):
        return True
    ensemble.append(elem)
    return False


def supprime_element(ensemble, elem):
    """
    Supprime un élément de l'ensemble, renvoie True si l'élément était présent, False sinon
    Complexité pire cas: O(n) puisqu'on parcourt tous les éléments de l'ensemble:
        k comparaisonts, n-k affectations
    """
    for i in range(len(ensemble)):
        if ensemble[i] == elem:
            # Décaler les éléments suivants puis faire pop() pour enlever le dernier
            # - on aurait pu faire simplement ensemble.pop(i), mais ça aurait caché
            # la complexité de l'opération.
            # On vérifie que ça marche même si i est le dernier élément de ensemble.
            for j in range(i,len(ensemble)-1):
                ensemble[j] = ensemble[j+1]
            ensemble.pop()
            return True
    return False
    
def prend_element(ensemble):
    """renvoie un élément arbitraire et le supprime de l'ensemble -- utile par

    exemple pour afficher le contenu d'un ensemble
    """
    return ensemble.pop()

e = cree_ensemble()
print('e:', e)
print('ajoute_element(e, "bleu") ->', ajoute_element(e, "bleu"))
print('e:', e)
print('ajoute_element(e, "blanc") ->', ajoute_element(e, "blanc"))
print('e:', e)
print('ajoute_element(e, "rouge") ->', ajoute_element(e, "rouge"))
print('e:', e)
print('est_present(e, "blanc") ->', est_present(e, "blanc"))
print('est_present(e, "vert") ->', est_present(e, "vert"))
print('supprime_element(e, "bleu") ->', supprime_element(e, "bleu"))
print('e:', e)
print('supprime_element(e, "rouge") ->', supprime_element(e, "rouge"))
print('e:', e)
print('supprime_element(e, "rouge") ->', supprime_element(e, "rouge"))
print('e:', e)
print('prend_element(e) ->', prend_element(e))
#print('prend_element(e) ->', prend_element(e))