|
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectuoc.ei.tads.CuaAmbPrioritat<E>
public class CuaAmbPrioritat<E>
Classe que implementa les operacions de les cues prioritàries (priority queue) i es distingeix perquè els elements no s'insereixen pel final, sinó que s'ordenen segons una prioritat que tenen associada. Les operacions de supressió i consulta afecten sempre l'element que té una prioritat més petita. En conseqüència, els elements hauran de permetre una operació de comparació d'on es pugui deduir la prioritat. En la representació seqüencial de l'arbre mitjançant un pilò s'organitzen els nodes de l'arbre dins d'un vector de manera que els fills i el pare són accessibles aplicant només una fòrmula. La primera posició del vector contindrà sempre l'arrel de l'arbre que és, precisament, l'element més petit; si un node està a la posició [k], el seu fill esquerre estarà a [2*k] i el seu fill dret a [2*k+1].
Nested Class Summary | |
---|---|
protected static class |
CuaAmbPrioritat.ArbreBinariQuasicompletVectorImpl<E>
Classe que exten el comportament d'un arbre binari amb dos mètodes que ens proporcionen la funcionalitat d'un arbre quasicomplet. |
Field Summary | |
---|---|
protected java.util.Comparator<E> |
comparador
Comparador concret que permet deduir la prioritat entre els elements. |
protected CuaAmbPrioritat.ArbreBinariQuasicompletVectorImpl<E> |
heap
Arbre binari vector que serveix de suport a la cua prioritària. |
Constructor Summary | |
---|---|
CuaAmbPrioritat()
Constructor sense paràmetres (capacitat màxima, per defecte) i elements d'una classe que implementa java.lang.Comparable. |
|
CuaAmbPrioritat(java.util.Comparator<E> comparador)
Constructor amb un paràmetre (capacitat màxima, per defecte) i elements d'una classe comparable amb el comparador donat. |
|
CuaAmbPrioritat(int max)
Constructor amb un paràmetre (capacitat donada) i elements d'una classe que implementa java.lang.Comparable. |
|
CuaAmbPrioritat(int max,
java.util.Comparator<E> comparador)
Constructor amb dos paràmetres (capacitat donada) i elements d'una classe comparable amb el comparador donat. |
Method Summary | |
---|---|
protected int |
comparar(Posicio<E> pos1,
Posicio<E> pos2)
Mètode protegit que compara els elements continguts a les posicions rebudes. |
E |
desencuar()
Esborra l'element de menor prioritat, si n'hi ha algun. |
Iterador<E> |
elements()
Accessor de lectura dels elements que hi ha al contenidor. |
void |
encuar(E elem)
Afegeix un element a la posició que li correspon, si hi cap. |
protected void |
enfonsarElement(Posicio<E> posicioAOrdenar)
|
protected Posicio<E> |
esborrarDarreraPosicio()
|
boolean |
estaBuit()
Mètode per a comprovar si el contenidor està buit. |
boolean |
estaPle()
Mètode per a comprovar si el contenidor està ple. |
int |
nombreElems()
Accessor de lectura del nombre d'elements que hi ha al contenidor. |
protected Posicio<E> |
novaDarreraPosicio(E elem)
|
Recorregut |
posicions()
Mètode que soporta múltiples recorreguts, de les posicions del contenidor, simultanis i independents entre ells. |
E |
primer()
Accessor de lectura de l'element de menor prioritat, si n'hi ha. |
protected void |
pujarElement(Posicio<E> novaPosicio)
|
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 |
---|
protected CuaAmbPrioritat.ArbreBinariQuasicompletVectorImpl<E> heap
protected java.util.Comparator<E> comparador
Constructor Detail |
---|
public CuaAmbPrioritat()
public CuaAmbPrioritat(int max)
max
- nombre màxim d'elements que pot contenir la cuapublic CuaAmbPrioritat(java.util.Comparator<E> comparador)
comparador
- comparador que permet deduir la prioritatpublic CuaAmbPrioritat(int max, java.util.Comparator<E> comparador)
max
- nombre màxim d'elements que pot contenir la cuacomparador
- comparador que permet deduir la prioritatMethod Detail |
---|
public int nombreElems()
nombreElems
in interface Contenidor<E>
public boolean estaBuit()
estaBuit
in interface Contenidor<E>
public boolean estaPle()
public void encuar(E elem)
encuar
in interface Cua<E>
elem
- element comparable que es vol afegir a la cuaprotected Posicio<E> novaDarreraPosicio(E elem)
protected void pujarElement(Posicio<E> novaPosicio)
public E desencuar()
desencuar
in interface Cua<E>
triarFillAIntercanviar(Posicio)
protected Posicio<E> esborrarDarreraPosicio()
protected void enfonsarElement(Posicio<E> posicioAOrdenar)
public E primer()
primer
in interface Cua<E>
ExcepcioContenidorBuit
- si la cua està buidapublic Iterador<E> elements()
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.
elements
in interface Contenidor<E>
ExcepcioPosicioInvalida
- si es vol obtenir el següent
element de l'enumeració i no n'hi ha cap o no n'hi ha cap
mésIterador.hiHaSeguent()
,
Iterador.seguent()
public Recorregut posicions()
public java.lang.String toString()
toString
in class java.lang.Object
protected int comparar(Posicio<E> pos1, Posicio<E> pos2)
pos1
- primera de les dues posicions de referènciapos2
- segona de les dues posicions de referència
ExcepcioPosicioInvalida
- si alguna posició és null o no
vàlida
ExcepcioElementsNoComparables
- si algun dels elements
continguts a les posicions és no comparable
|
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |