uoc.ei.tads
Class CuaAmbPrioritat<E>

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

public class CuaAmbPrioritat<E>
extends java.lang.Object
implements Cua<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].

Since:
1.5
See Also:
Serialized Form

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

heap

protected CuaAmbPrioritat.ArbreBinariQuasicompletVectorImpl<E> heap
Arbre binari vector que serveix de suport a la cua prioritària.


comparador

protected java.util.Comparator<E> comparador
Comparador concret que permet deduir la prioritat entre els elements. Pot tenir valor null i aleshores s'utilitza la interfície java.lang.Comparable

Constructor Detail

CuaAmbPrioritat

public CuaAmbPrioritat()
Constructor sense paràmetres (capacitat màxima, per defecte) i elements d'una classe que implementa java.lang.Comparable.


CuaAmbPrioritat

public CuaAmbPrioritat(int max)
Constructor amb un paràmetre (capacitat donada) i elements d'una classe que implementa java.lang.Comparable.

Parameters:
max - nombre màxim d'elements que pot contenir la cua

CuaAmbPrioritat

public 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.

Parameters:
comparador - comparador que permet deduir la prioritat

CuaAmbPrioritat

public 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.

Parameters:
max - nombre màxim d'elements que pot contenir la cua
comparador - comparador que permet deduir la prioritat
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à

estaPle

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

Returns:
cert o fals, segons si està ple o no ho està

encuar

public void encuar(E elem)
Afegeix un element a la posició que li correspon, si hi cap.

Specified by:
encuar in interface Cua<E>
Parameters:
elem - element comparable que es vol afegir a la cua

novaDarreraPosicio

protected Posicio<E> novaDarreraPosicio(E elem)

pujarElement

protected void pujarElement(Posicio<E> novaPosicio)

desencuar

public E desencuar()
Esborra l'element de menor prioritat, si n'hi ha algun.

Specified by:
desencuar in interface Cua<E>
Returns:
primer element, que és el de menor prioritat
See Also:
triarFillAIntercanviar(Posicio)

esborrarDarreraPosicio

protected Posicio<E> esborrarDarreraPosicio()

enfonsarElement

protected void enfonsarElement(Posicio<E> posicioAOrdenar)

primer

public E primer()
Accessor de lectura de l'element de menor prioritat, si n'hi ha. Si es vol desencuar l'objecte s'ha d'esborrar seguidament.

Specified by:
primer in interface Cua<E>
Returns:
primer element, que és el de menor prioritat
Throws:
ExcepcioContenidorBuit - si la cua està buida

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 del contenidor inordre
Throws:
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és
See Also:
Iterador.hiHaSeguent(), Iterador.seguent()

posicions

public Recorregut posicions()
Mètode que soporta múltiples recorreguts, de les posicions del contenidor, simultanis i independents entre ells.

Returns:
enumeració de les posicions del contenidor per nivell

toString

public java.lang.String toString()
Mètode que sobreescriu Object.toString(). Treu els elements separats pel salt de línia de la plataforma.

Overrides:
toString in class java.lang.Object
Returns:
llistat dels elements en un recorregut per nivells

comparar

protected int comparar(Posicio<E> pos1,
                       Posicio<E> pos2)
Mètode protegit que compara els elements continguts a les posicions rebudes. Si el constructor no ha definit un comparador, s'utilitza java.lang.Comparable per deduir la prioritat entre ambdós elements.

Parameters:
pos1 - primera de les dues posicions de referència
pos2 - segona de les dues posicions de referència
Returns:
un enter negatiu, zero o positiu, segons si l'element de la primera posició té menys, igual o més prioritat que l'element de la segona posició, d'acord amb la implementació del comparador
Throws:
ExcepcioPosicioInvalida - si alguna posició és null o no vàlida
ExcepcioElementsNoComparables - si algun dels elements continguts a les posicions és no comparable