package plp.collection;

import java.util.*;

/**
 * La classe VecteurInfini implémente une structure de type 
 * Vecteur (accès direct) polymorphe (contenant des objets 
 * quelconques) sans limitation de taille.
 * Les indices doivent être positifs ou nuls.
 * Cette structure n'est pas recommandée pour gérer des vecteurs 
 * creux. 
 */

public class VecteurInfini {

    private static int TAILLE_INITIALE = 8;
    private Object [] vecteur = new Object[TAILLE_INITIALE];
    private int nbElements = 0; // mémorise le nombre d'éléments != null stockés
    private int indiceMax = -1; // mémorise le plus grand indice utilisé.
    private int position;       // mémorise l'emplacement d'un élément recherché par la méthode chercherElement(Object).

    public VecteurInfini() {
    }

    /** 
     * Insere un élément juste derrière le dernier indice utilisé.
     */
    public void inserer(Object o) {
	inserer(++indiceMax, o);
    }
 
    private int nouvelleTaille(int minimumRequis) {
	int nouvelleTaille = vecteur.length;
	
	while (nouvelleTaille < minimumRequis) {
	    nouvelleTaille = nouvelleTaille * 2 + 1;
	}
	return nouvelleTaille;
    }

    private void augmenterVecteur(int min) {
	Object [] nouveauVecteur = new Object[nouvelleTaille(min)];
	System.arraycopy(vecteur, 0, nouveauVecteur, 0, vecteur.length);
	vecteur = nouveauVecteur;
    }
    
    /** 
     * Insère un élément à la position indiquée, en remplaçant au besoin 
     * l'élément déja présent.
     */
    public void inserer(int indice, Object o) {
	if (indice >= vecteur.length) {
	    if (o == null) {
		return;
	    } else {
		augmenterVecteur(indice + 1);
	    }
	}
	if (vecteur[indice] != null) {
	    nbElements--;
	}
	vecteur[indice] = o;
	if (o != null) {
	    nbElements++;
	    if (indice > indiceMax) { 
		indiceMax = indice;
	    }
	}
    }

    /** 
     * Nombre d'éléments non nuls 
     */
    public int cardinal() {
	return nbElements;
    }
    
    /** 
     * Dernier indice utilisé 
     */
    public int indiceMax() {
	return indiceMax;
    }
    
    /* La recherche de l'indice d'un élément se fait pour des raisons de 
       factorisation de code, à l'aide d'une méthode privée, 
       qui affecte une variable à l'indice de l'élément s'il existe, à un 
       indice au delà de l'indice maximum sinon.
    */
    private void chercherElement(Object o) {
	position = indiceMax + 1;
	for (int i = 0; i <= indiceMax; ++i) {
	    if (o.equals(vecteur[i])) { // o ne peut etre null
		position = i;
		return;
	    }
	}
    }

    /** 
     * Recherche d'un élément. Cette recherche utilise equals(Object). 
     * Le paramètre ne peut être nul.
     */
    public boolean estPresent(Object o) {
	chercherElement(o);
	return position <= indiceMax;
    }
    
    /** 
     * Retourne la valeur d'un élément en fonction de son indice.
     */
    public Object element(int indice) {
	return (indice > indiceMax)? null : vecteur[indice];
    }

    /**
     * Retourne l'indice d'un élément. L'élément doit être obligatoirement présent.
     */
    /* Problème de cette solution :
       si le client teste la présence d'un objet, ce test est effectué deux fois.
    */
    public int indice(Object o) {
	if (estPresent(o)) {
	    return position;
	}
	throw new Error("Object " + o + " non présent"); 
    }

    /* Problème de cette solution : si l'utilisateur teste lui-même 
     * la présence d'un objet, ce test est effectué deux fois.
     */
    /** 
     * Suppression d'un élément, qui doit être forcément présent et
     * non nul.
     */
    public void retirer(Object o) {
	inserer(indice(o), null);
    }

    /**
     * Tasse le vecteur en supprimant les valeurs nulles. Les indices
     * des objets sont modifiés.
     */
    public void compacter() {
	if (nbElements == indiceMax + 1) {
	    return;
	}

	Object [] nouveauVecteur = new Object[nbElements];

	for (int i = 0, j = 0; i <= indiceMax; ++i) {
	    if (vecteur[i] != null) {
		nouveauVecteur[j++] = vecteur[i];
	    }
	}
	vecteur = nouveauVecteur;
	indiceMax = nouveauVecteur.length - 1;
    }

    public Iterator elementsNonNuls() {
	return new Iterator() {
	    int index = -1;
	    int suivant = -1;

	    public boolean hasNext() {
		if (suivant == indiceMax + 1) {
		    return false;
		}
		if (suivant != index) {
		    return true;
		}
		for (suivant = index + 1; suivant <= indiceMax; suivant ++) {
		    if (vecteur[suivant] != null) {
			return true;
		    }
		}
		return false;
	    }

	    public Object next() {
		if (!hasNext()) {
		    throw new NoSuchElementException();
		}
		index = suivant;
		return vecteur[index];
	    }

	    public void remove() {
		if (index == -1 || vecteur[index] == null) {
		    throw new IllegalStateException();
		}
		vecteur[index] = null;
	    }
	};
    }
}