uoc.ei.tads
Class TablaDispersion<C,E>

java.lang.Object
  extended by uoc.ei.tads.TablaDispersion<C,E>
All Implemented Interfaces:
java.io.Serializable, Contenedor<E>, Diccionario<C,E>

public class TablaDispersion<C,E>
extends java.lang.Object
implements Diccionario<C,E>

Clase que implementa las operaciones de un diccionario mediante una tabla de dispersión indirecta, conocida con el número de tabla encadenada abierta (separate chaining). Seguramente es la manera más sencilla de resolver las colisiones. Por la función de dispersión se accede a el índice del vector y los sinónimos se encadenan a partir de esta posición. Los diccionarios son estructuras que almacenan elementos con una clave asociada. La clave debe disponer de una operación de igualdad y el elemento asociado a la clave puede ser cualquier objeto. En esta implementación se utilizan elementos de la clase ClaveValor que sobrescribe, por delegación en la clave, la función hashCode().

See Also:
ClaveValor, Serialized Form

Nested Class Summary
protected static class TablaDispersion.RecorridoNodos<C,E>
          Clase que proporciona un recorrido de las posiciones.
 
Field Summary
protected  int n
          Número de elementos que hay actualmente al contenedor.
protected  ListaEncadenada<ClaveValor<C,E>>[] tabla
          Vector de nodos encadenados.
static int TAMANO_TABLA_POR_DEFECTO
          Medida por defecto de la tabla de dispersión.
 
Constructor Summary
TablaDispersion()
          Constructor sin parámetros (tamaño de la tabla por defecto).
TablaDispersion(int tamano)
          Constructor con un parámetro.
 
Method Summary
 E borrar(C clave)
          Borra la primera clave coincidente y el elemento asociado, si se puede.
protected  void borrarListaDeSinonimos(int indice)
           
protected  Posicion<ClaveValor<C,E>> buscarClaveEnSinonimos(ListaEncadenada<ClaveValor<C,E>> sinonimos, C clave)
           
protected  int calcularIndiceTabla(C clave)
           
 Iterador<C> claves()
          Accesor de lectura de los elementos que hay en el contenedor.
 E consultar(C clave)
          Accesor de lectura del elemento asociado con una clave.
protected  ListaEncadenada<ClaveValor<C,E>> creaListaDeSinonimos(int indice, ClaveValor<C,E> kv)
           
 Iterador<E> elementos()
          Accesor de lectura de los elementos que hay en el contenedor.
 boolean esta(C clave)
          Comprueba si hay un elemento con una determinada clave.
 boolean estaVacio()
          Método para comprobar si el contenedor está vacío.
 void insertar(C clave, E elem)
          Añade un elemento con una clave asociada, si se puede.
 int numElems()
          Accesor de lectura del número de elementos que hay en el contenedor.
 java.lang.String toString()
          Método que sobrescribe Object.toString().
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

TAMANO_TABLA_POR_DEFECTO

public static final int TAMANO_TABLA_POR_DEFECTO
Medida por defecto de la tabla de dispersión.

See Also:
Constant Field Values

n

protected int n
Número de elementos que hay actualmente al contenedor.


tabla

protected ListaEncadenada<ClaveValor<C,E>>[] tabla
Vector de nodos encadenados.

Constructor Detail

TablaDispersion

public TablaDispersion()
Constructor sin parámetros (tamaño de la tabla por defecto).


TablaDispersion

public TablaDispersion(int tamano)
                throws ExcepcionParametroIncorrecto
Constructor con un parámetro. Crea un vector con la tamaño dada.

Parameters:
tamano - tamaño de la tabla de dispersión
Throws:
ExcepcionParametroIncorrecto - si la tamaño es negativa
Method Detail

numElems

public int numElems()
Accesor de lectura del número de elementos que hay en el contenedor.

Specified by:
numElems in interface Contenedor<E>
Returns:
número de elementos que contiene actualmente

estaVacio

public boolean estaVacio()
Método para comprobar si el contenedor está vacío.

Specified by:
estaVacio in interface Contenedor<E>
Returns:
cierto o falso, según si está vacío o no lo está

insertar

public void insertar(C clave,
                     E elem)
Añade un elemento con una clave asociada, si se puede. Si encuentra un elemento con la misma clave lo sobrescribe.

Specified by:
insertar in interface Diccionario<C,E>
Parameters:
clave - clave asociada al elemento que se quiere añadir
elem - elemento que se quiere añadir al diccionario
Throws:
ExcepcionTADs - si la clave es null
See Also:
ClaveValor

esta

public boolean esta(C clave)
Comprueba si hay un elemento con una determinada clave.

Specified by:
esta in interface Diccionario<C,E>
Parameters:
clave - clave asociada a un elemento
Returns:
cierto o falso, según si encuentra o no encuentra la clave

consultar

public E consultar(C clave)
Accesor de lectura del elemento asociado con una clave.

Specified by:
consultar in interface Diccionario<C,E>
Parameters:
clave - clave de referencia
Returns:
elemento ClaveValor asociado con la clave; o null, si no era
Throws:
ExcepcionElementosNoComparables - si el elemento es no comparable
See Also:
ClaveValor

borrar

public E borrar(C clave)
Borra la primera clave coincidente y el elemento asociado, si se puede.

Specified by:
borrar in interface Diccionario<C,E>
Parameters:
clave - clave de referencia
Returns:
elemento borrado asociado con la clave; o null, si no era
Throws:
ExcepcionContenedorVacio - si la tabla está vacía
ExcepcionElementosNoComparables - si el elemento es no comparable
See Also:
ClaveValor

calcularIndiceTabla

protected int calcularIndiceTabla(C clave)

creaListaDeSinonimos

protected ListaEncadenada<ClaveValor<C,E>> creaListaDeSinonimos(int indice,
                                                                ClaveValor<C,E> kv)

borrarListaDeSinonimos

protected void borrarListaDeSinonimos(int indice)

buscarClaveEnSinonimos

protected Posicion<ClaveValor<C,E>> buscarClaveEnSinonimos(ListaEncadenada<ClaveValor<C,E>> sinonimos,
                                                           C clave)

claves

public Iterador<C> claves()
Accesor de lectura de los elementos que hay en el contenedor. Retorna una enumeración. Enumerar es simplemente enunciar la una detrás la otra (las cosas de una serie, las partes de un todo). Pero si el contenedor tiene definido algún tipo de ordenación o de recorrido, la enumeración debe ser consecuente y ofrecer los elementos por orden (FIFO, LIFO, inordre, etc.), sin alterar el estado actual del contenedor.

Specified by:
claves in interface Diccionario<C,E>
Returns:
enumeración de las claves del contenedor sin ordenar
See Also:
Iterador.haySiguiente(), Iterador.siguiente()

elementos

public Iterador<E> elementos()
Accesor de lectura de los elementos que hay en el contenedor. Retorna una enumeración. Enumerar es simplemente enunciar la una detrás la otra (las cosas de una serie, las partes de un todo). Pero si el contenedor tiene definido algún tipo de ordenación o de recorrido, la enumeración debe ser consecuente y ofrecer los elementos por orden (FIFO, LIFO, inordre, etc.), sin alterar el estado actual del contenedor.

Specified by:
elementos in interface Contenedor<E>
Returns:
enumeración de los elementos asociados con las claves
See Also:
Iterador.haySiguiente(), Iterador.siguiente()

toString

public java.lang.String toString()
Método que sobrescribe Object.toString(). Muestra pares de elementos. Separa una par de la siguiente con el salto de línea de la plataforma.

Overrides:
toString in class java.lang.Object