/**
 * Clase para crear tablas de dispersión usando el método lineal para resolver
 * las colisiones
 * @author Amparo López Gaona
 * @version 1a. ed.
 */
public class TablaDeDispersionA implements Dispersable {
  private Object[] elementos ;
  int nElementos;

  /**
   * Crea una tabla de dispersión del tamaño especificado
   * @param tam -- cantidad inicial de elementos permitida
   */
  public TablaDeDispersionA (int tam) {
    elementos = new Object[sgtePrimo(tam)];
    nElementos = 0;
  }

  /**
   * Crea una tabla de dispersión para 100 elementos
   * @param tam -- cantidad inicial de elementos permitida
   */
  public TablaDeDispersionA () {
    this(100);
  }

  /**
   * Verifica 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;
  }

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

  /**
   * Elimina todos los elementos de la tabla.
   */
  public void vaciar () {
    for (int i = 0; i < elementos.length; i++)
      elementos[i] = null;
    nElementos = 0;
  }

  /**
   * Agrega un elemento a la tabla
   * @param val objeto que se insertará en la tabla
   */
  public void agregar (Object val) {
    if (nElementos + 1 >= elementos.length) 
      throw new RuntimeException("Arreglo lleno"); 
    int indice = Math.abs(val.hashCode()) % elementos.length;

    while (elementos[indice] != null)  //Resolución de colisiones
      if (++indice >= elementos.length) indice = 0;
    elementos[indice] = val;
    nElementos++;
  }

  /**
   * Determina si una tabla contiene un valor particular
   * @param val -- elemento que se busca
   * @return true -- si la tabla contiene un valor particular y false en
   * otro caso.
   */
  public boolean contiene (Object val) {
    int indiceIni = Math.abs(val.hashCode()) % elementos.length;
    int indice = indiceIni;

    while (elementos[indice] != null) {
      if (val.equals(elementos[indice]))
        return true;
      if (++indice >= elementos.length) indice = 0;
      if (indiceIni == indice) break;
    }
    return false;
  }

  /**
   * Metodo para obtener el valor asociado a una llave
   * @param val -- llave del elemento que se busca
   * @return Object -- objeto asociado a la llave o null si no lo encuentra
   */
  public Object obtener (Object val) {
    int indiceIni = Math.abs(val.hashCode()) % elementos.length;
    int indice = indiceIni;

    while (elementos[indice] != null) {
      if (val.equals(elementos[indice]))
	  return elementos[indice];
      if (++indice >= elementos.length) indice = 0;
      if (indiceIni == indice) break;
    }
    return null;
  }

  /**
   * Iterador de la tabla
   * @return Iterator -- que mantiene los elementos de la tabla
   * @see java.util.Iterator
   */

  public java.util.Iterator iterador () 
    { return new MiIterador(); }


  /*
   * Clase privada que implementa el iterador. 
   */
  private class MiIterador implements java.util.Iterator {
    private int indice = -1;

    public boolean hasNext () {
      while (++indice < elementos.length) {
        if (elementos[indice] != null)
          return true;
      }
      return false;
    }

    public Object next () { return elementos[indice]; }

    public void remove() {
      throw new IllegalStateException();
    }
  }
    /*
     * 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;
    }

}