import java.util.List;
import java.util.LinkedList;
import java.util.ArrayList;

class Table<T> {
    // Invariant : les paquets sont définis
    // Invariant : les paquets ne contiennent pas [null]
    // Invariant : les paquets ne contiennent pas de doublons
    private Tableau table;
    // Invariant : nbPaquets == table.length()
    private int nbPaquets;
    // Invariant : nbElements == nombre d'éléments dans l'ensemble
    private int nbElements;
    private final float seuilCharge;
    
    public Table(int n, float s) {
        this.nbPaquets = n;
        this.nbElements = 0;
        this.seuilCharge = s;
        this.table = new Tableau(n);
    }

    private class Paquet {
        LinkedList<T> l;
        Paquet() { this.l = new LinkedList<>(); }
        // Précondition : néant
        // Résultat : [true] si [elt] présent
        boolean contient(T elt) { return l.contains(elt); }
        // Précondition : néant
        // Postcondition : élément ajouté (une occurrence de plus si présent)
        void ajoute(T elt) { l.add(elt); }
        // Précondition : néant
        // Postcondition : retire une occurrence de l'élément
        void retire(T elt) { l.remove(elt); }
    }

    private class Tableau {
        List<Paquet> t;
        Tableau(int n) {
            this.t = new ArrayList<>(n);
            for (Paquet paquet : this.t) {
                paquet = new Paquet();
            }
        }
        // Précondition : [i] entre [0] et [nbPaquets]
        // Résultat : le paquet d'indice [i]
        Paquet paquet(int i) { return t.get(i); }
    }
    
    // Précondition : [elt] est défini
    // Postcondition : résultat entre [0] et [nbPaquets]
    private int indicePaquet(T elt) {
        return elt.hashCode() % this.nbPaquets;
    }

    // Précondition : valeur [nbElements] correcte
    // Résultat : le cardinal de l'ensemble
    public int cardinal() {
        return this.nbElements;
    }
    
    // Précondition : paquets définis
    // Postcondition : répond [true] si l'élément est présent
    public boolean contient(T elt) {
        if (elt == null) { return false; }
        int indicePaquet = indicePaquet(elt);
        return table.paquet(indicePaquet).contient(elt);
    }
    
    // Précondition : paquets définis, [elt] != [null]
    // Postcondition : élément ajouté dans son paquet s'il n'y était pas déjà
    //                 si la charge dépasse le seuil, doublement de capacité
    public void ajoute(T elt) {
        if (elt == null) throw new NullPointerException();
        int ip = indicePaquet(elt);
        Paquet paquet = table.paquet(ip);
        if (!paquet.contient(elt)) {
            paquet.ajoute(elt);
            this.nbElements++;
            if (nbElements / (float)nbPaquets >= seuilCharge) {
                doublePaquets();
            }
        }
    }

    // Précondition : néant (posera problème si tableau trop grand)
    // Postcondition : [nbPaquets] doublé, éléments préservés
    private void doublePaquets() {
        Tableau ancien = this.table;
        this.nbPaquets *= 2;
        this.table = new Tableau(this.nbPaquets);
        for (Paquet p: ancien.t) {
            for (T elt: p.l) {
                this.ajoute(elt);
            }
        }
    }

    // Précondition : paquets définis, pas de doublons
    // Postcondition : élément retiré ; aucun effet si [elt] == [null]
    public void retire(T elt) {
        if (elt != null) {
            int ip = indiceePaquet(elt);
            Paquet paquet = table.paquet(ip);
            if (paquet.contient(elt)) {
                paquet.retire(elt);
                this.nbElements--;
            }
        }
    }
}