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

java.lang.Object
  extended by uoc.ei.tads.TaulaDispersio<C,E>
All Implemented Interfaces:
java.io.Serializable, Contenidor<E>, Diccionari<C,E>

public class TaulaDispersio<C,E>
extends java.lang.Object
implements Diccionari<C,E>

Classe que implementa les operacions d'un diccionari mitjançant una taula de dispersió indirecta, coneguda amb el nom de taula encadenada oberta (separate chaining). Segurament és la manera més senzilla de resoldre les col·lisions. Per la funció de dispersió s'accedeix a l'índex del vector i els sinònims s'encadenen a partir d'aquesta posició. Els diccionaris són estructures que emmagatzemen elements amb una clau associada. La clau ha de disposar d'una operació d'igualtat i l'element associat a la clau pot ser qualsevol objecte. En aquesta implementació s'utilitzen elements de la classe ClauValor que sobreescriu, per delegació en la clau, la funció hashCode().

Since:
1.5
See Also:
ClauValor, Serialized Form

Nested Class Summary
protected static class TaulaDispersio.RecorregutNodes<C,E>
          Classe que proporciona un recorregut de les posicions.
 
Field Summary
static int MIDA_TAULA_PER_DEFECTE
          Mida per defecte de la taula de dispersió.
protected  int n
          Nombre d'elements que hi ha actualment al contenidor.
protected  LlistaEncadenada<ClauValor<C,E>>[] taula
          Vector de nodes encadenats.
 
Constructor Summary
TaulaDispersio()
          Constructor sense paràmetres (mida de la taula per defecte).
TaulaDispersio(int mida)
          Constructor amb un paràmetre.
 
Method Summary
 void afegir(C clau, E elem)
          Afegeix un element amb una clau associada, si es pot.
protected  int calcularIndexTaula(C clau)
           
protected  Posicio<ClauValor<C,E>> cercarClauEnSinonims(LlistaEncadenada<ClauValor<C,E>> sinonims, C clau)
           
 Iterador<C> claus()
          Accessor de lectura dels elements que hi ha al contenidor.
 E consultar(C clau)
          Accesor de lectura de l'element associat amb una clau.
protected  LlistaEncadenada<ClauValor<C,E>> creaLlistaDeSinonims(int index, ClauValor<C,E> kv)
           
 Iterador<E> elements()
          Accessor de lectura dels elements que hi ha al contenidor.
 E esborrar(C clau)
          Esborra la primera clau coincident i l'element associat, si es pot.
protected  void esborrarLlistaDeSinonims(int index)
           
 boolean estaBuit()
          Mètode per a comprovar si el contenidor està buit.
 boolean hiEs(C clau)
          Comprova si hi ha un element amb una determinada clau.
 int nombreElems()
          Accessor de lectura del nombre d'elements que hi ha al contenidor.
 java.lang.String toString()
          Mètode que sobreescriu Object.toString().
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

MIDA_TAULA_PER_DEFECTE

public static final int MIDA_TAULA_PER_DEFECTE
Mida per defecte de la taula de dispersió.

See Also:
Constant Field Values

n

protected int n
Nombre d'elements que hi ha actualment al contenidor.


taula

protected LlistaEncadenada<ClauValor<C,E>>[] taula
Vector de nodes encadenats.

Constructor Detail

TaulaDispersio

public TaulaDispersio()
Constructor sense paràmetres (mida de la taula per defecte).


TaulaDispersio

public TaulaDispersio(int mida)
               throws ExcepcioParametreIncorrecte
Constructor amb un paràmetre. Crea un vector amb la mida donada.

Parameters:
mida - mida de la taula de dispersió
Throws:
ExcepcioParametreIncorrecte - si la mida és negativa
Method Detail

nombreElems

public int nombreElems()
Accessor de lectura del nombre d'elements que hi ha al contenidor.

Specified by:
nombreElems in interface Contenidor<E>
Returns:
nombre d'elements que conté actualment

estaBuit

public boolean estaBuit()
Mètode per a comprovar si el contenidor està buit.

Specified by:
estaBuit in interface Contenidor<E>
Returns:
cert o fals, segons si està buit o no ho està

afegir

public void afegir(C clau,
                   E elem)
Afegeix un element amb una clau associada, si es pot. Si troba un element amb la mateixa clau el sobreescriu.

Specified by:
afegir in interface Diccionari<C,E>
Parameters:
clau - clau associada a l'element que es vol afegir
elem - element que es vol afegir al diccionari
Throws:
ExcepcioTADs - si la clau és null
See Also:
ClauValor

hiEs

public boolean hiEs(C clau)
Comprova si hi ha un element amb una determinada clau.

Specified by:
hiEs in interface Diccionari<C,E>
Parameters:
clau - clau associada a un element
Returns:
cert o fals, segons si troba o no troba la clau

consultar

public E consultar(C clau)
Accesor de lectura de l'element associat amb una clau.

Specified by:
consultar in interface Diccionari<C,E>
Parameters:
clau - clau de referència
Returns:
element ClauValor associat amb la clau; o null, si no hi era
Throws:
ExcepcioElementsNoComparables - si l'element és no comparable
See Also:
ClauValor

esborrar

public E esborrar(C clau)
Esborra la primera clau coincident i l'element associat, si es pot.

Specified by:
esborrar in interface Diccionari<C,E>
Parameters:
clau - clau de referència
Returns:
element esborrat associat amb la clau; o null, si no hi era
Throws:
ExcepcioContenidorBuit - si la taula està buida
ExcepcioElementsNoComparables - si l'element és no comparable
See Also:
ClauValor

calcularIndexTaula

protected int calcularIndexTaula(C clau)

creaLlistaDeSinonims

protected LlistaEncadenada<ClauValor<C,E>> creaLlistaDeSinonims(int index,
                                                                ClauValor<C,E> kv)

esborrarLlistaDeSinonims

protected void esborrarLlistaDeSinonims(int index)

cercarClauEnSinonims

protected Posicio<ClauValor<C,E>> cercarClauEnSinonims(LlistaEncadenada<ClauValor<C,E>> sinonims,
                                                       C clau)

claus

public Iterador<C> claus()
Accessor de lectura dels elements que hi ha al contenidor. Retorna una enumeració. Es pot obtenir un llistat amb un parell de línies de codi:
 for ( Iterador it = tad.elements(); it.hiHaSeguent(); )
    System.out.println(it.seguent()); 
Enumerar és simplement enunciar l'una darrere l'altra (les coses d'una sèrie, les parts d'un tot). Però si el contenidor té definit algun tipus d'ordenació o de recorregut, l'enumeració ha de ser conseqüent i oferir els elements per ordre (FIFO, LIFO, inordre, etc.), sense alterar l'estat actual del contenidor.

Specified by:
claus in interface Diccionari<C,E>
Returns:
enumeració de les claus del contenidor sense ordenar
See Also:
Iterador.hiHaSeguent(), Iterador.seguent()

elements

public Iterador<E> elements()
Accessor de lectura dels elements que hi ha al contenidor. Retorna una enumeració. Es pot obtenir un llistat amb un parell de línies de codi:
 for ( Iterador it = tad.elements(); it.hiHaSeguent(); )
    System.out.println(it.seguent()); 
Enumerar és simplement enunciar l'una darrere l'altra (les coses d'una sèrie, les parts d'un tot). Però si el contenidor té definit algun tipus d'ordenació o de recorregut, l'enumeració ha de ser conseqüent i oferir els elements per ordre (FIFO, LIFO, inordre, etc.), sense alterar l'estat actual del contenidor.

Specified by:
elements in interface Contenidor<E>
Returns:
enumeració dels elements associats amb les claus
See Also:
Iterador.hiHaSeguent(), Iterador.seguent()

toString

public java.lang.String toString()
Mètode que sobreescriu Object.toString(). Treu parelles d'elements. Separa una parella de la següent amb el salt de línia de la plataforma.

Overrides:
toString in class java.lang.Object
Returns:
llistat de claus (entre claudàtors) seguides de l'element associat a cada clau