/**
 * Implementación del tipo Tabla de Dispersion para trabajar con funciones de
 * dispersión y cubetas para las colisiones
 * @author  Amparo López Gaona 
 * @version 1a. ed.
 */
public class TablaDeDispersion implements Dispersable {
    private Lista [] cubetas;
    private int nElementos;

    /**
     * Constructor para una tabla de dispersión del tamaño indicado
     * @param n -- cantidad de cubetas en la tabla
     */
    public TablaDeDispersion (int n) { 
	cubetas = new Lista[sgtePrimo(n)];
	for (int i = 0; i < cubetas.length; i++) 
	    cubetas[i] = new Lista();
	nElementos = 0;
    }

    /**
     * Crea una nueva tabla de dispersión con 101 cubetas
     */
    public TablaDeDispersion () { 
	this (100);
    }

    /**
     * Determina si la tabla está vacía.
     * @return true si la tabla está vacía y false en otro caso.
     */
    public boolean estaVacia () { 
	return  nElementos == 0 ; 
    }

    /**
     * Metodo para eliminar todos los elementos de la tabla.
     */
    public void vaciar () { 
	for (int i=0; i < cubetas.length; i++) 
	    cubetas[i] = new Lista();
	nElementos = 0;
    }

    /**
     * Determina la cantidad de elementos en la tabla.
     * @return int - cantidad de elementos en la tabla.
     */
    public int tamanio () {
	return nElementos;
    }

    /**
     * Agrega un nuevo elemento a la tabla.
     * @param val - elemento que se insertará.
     */
    public void agregar (Object val) {
	cubeta(val).agregar(val); 
	nElementos++;
    }

    /**
     * Determina si un elemento esta en la tabla, o no.
     * @param val -- elemento a buscar.
     * @return true -- si el elemento está en la tabla y false en otro caso.
     */
    public boolean contiene (Object val) {
	return cubeta(val).contiene(val); 
    }

    /**
     * Devuelve los elementos que tienen la misma llave
     * @param val -- llave del elemento que se busca
     * @return Lista -- lista con los elementos que tienen la misma llave.
     */
    public Lista obtener (Object val) {
	return cubeta(val); 
    }

    /**
     * Elimina un valor de la tabla.
     * @param val - elemento que será eliminado de la tabla.
     * @exception java.util.NoSuchElementException  (este está en Lista)
     */
    public void eliminar (Object val) {
	cubeta(val).eliminar(val); 
	nElementos--;
    }
    
    /*
     * Método interno para determinar en qué cubeta se realizará una
     * operación. 
     */ 
    private Lista cubeta (Object val)  {
	return cubetas[Math.abs(val.hashCode()) % cubetas.length];
    }

    /**
     * Iterador para la tabla.
     * @return Iterator -- que tienen los elementos de la tabla.
     * @see java.util.Iterator
     */
    public java.util.Iterator iterador () { 
           return new miIteradorHash(); 
    }

    /*
     * Clase privada que implementa el iterador
     */
    private class miIteradorHash implements java.util.Iterator {
	java.util.Iterator itActual;
	int ind;

	public miIteradorHash () {
	    ind = 0;
	    itActual = cubetas[0].iterador();
	}

	public boolean hasNext() {
	    if (itActual.hasNext()) return true;
	    while (++ind < cubetas.length) {
		itActual = cubetas[ind].iterador();
		if (itActual.hasNext())
		    return true;
	    }
	    return false;
	}

	public Object next() {
	    return itActual.next(); 
	}

	public void remove() {
	    throw new IllegalStateException();
	}
    }

    /**
     * Metodo para mostrar todos los elementos de la tabla
     */
    public void imprimir(){
	for(int i=0; i < cubetas.length; i++) {
	    System.out.print(i+" ");
	    if (cubetas[i] != null) {
		java.util.Iterator it = cubetas[i].iterador();
		while (it.hasNext())
		    System.out.print(it.next()+" ");
		System.out.println();
	    }
	}
    }

    /*
     * Método para determinar el número primo mayor al entero dado.
     * @param n - número positivo inicial
     * @return int - el número primo mayor o igual a n.
     */
    private static int sgtePrimo(int n) {
	if(n % 2 == 0)
	    n++;

	for(; !esPrimo(n); n += 2)
	    ;

	return n;
    }

    /*
     * Método (ineficiente) para determinar si un número es primo.
     * @param n - el número a probar
     * @return boolean - true su el número es primo y false en otro caso.
     */
    private static boolean esPrimo(int n)  {
	if(n == 2 || n == 3)
	    return true;

	if(n == 1 || n % 2 == 0)
	    return false;

	for(int i = 3; i * i <= n; i += 2)
	    if(n % i == 0)
		return false;

	return true;
    }

}