uoc.ei.tads
Class ColaConPrioridad<E>

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

public class ColaConPrioridad<E>
extends java.lang.Object
implements Cola<E>

Clase que implementa las operaciones de las colas prioritarias (priority queue) y se distingue porque los elementos no se insertan por el final, sino que se ordenan según una prioridad que tienen asociada. Las operaciones de supresión y consulta afectan siempre al elemento que tiene una prioridad más pequeña. En consecuencia, los elementos deberán permitir una operación de comparación de donde se pueda deducir la prioridad. En la representación secuencial del arbol mediante un montículo se organizan los nodos del arbol dentro de de un vector de manera que los hijos y el padre son accesibles aplicando solo una formula. La primera posición del vector contendrá siempre la raíz del arbol que es, precisamente, el elemento más pequeño; si un nodo está en la posición [k], su izquierdo estará a [2*k] y su hijo derecho a [2*k+1].

See Also:
Serialized Form

Nested Class Summary
protected static class ColaConPrioridad.ArbolBinarioQuasicompletoVectorImpl<E>
          Clase que extiende el comportamiento de un arbol binario con dos métodos que nos proporcionan la funcionalidad de un arbol cuasicompleto.
 
Field Summary
protected  java.util.Comparator<E> comparador
          Comparador concreto que permite deducir la prioridad entre los elementos.
protected  ColaConPrioridad.ArbolBinarioQuasicompletoVectorImpl<E> heap
          Arbol binario vector que sirve de apoyo a la cola prioritaria.
 
Constructor Summary
ColaConPrioridad()
          Constructor sin parámetros (capacidad máxima, por defecto) y elementos de una clase que implementa java.lang.Comparable.
ColaConPrioridad(java.util.Comparator<E> comparador)
          Constructor con un parámetro (capacidad máxima, por defecto) y elementos de una clase comparable con el comparador dado.
ColaConPrioridad(int max)
          Constructor con un parámetro (capacidad dada) y elementos de una clase que implementa java.lang.Comparable.
ColaConPrioridad(int max, java.util.Comparator<E> comparador)
          Constructor con dos parámetros (capacidad dada) y elementos de una clase comparable con el comparador dado.
 
Method Summary
protected  Posicion<E> borrarUltimaPosicion()
           
protected  int comparar(Posicion<E> pos1, Posicion<E> pos2)
          Método protegido que compara los elementos contenidos en las posiciones recibidas.
 E desencolar()
          Borra el elemento de menor prioridad, si hay alguno.
 Iterador<E> elementos()
          Accesor de lectura de los elementos que hay en el contenedor.
 void encolar(E elem)
          Añade un elemento a la posición que le corresponde, si cabe.
 boolean estaLleno()
          Método para comprobar si el contenedor está lleno.
 boolean estaVacio()
          Método para comprobar si el contenedor está vacío.
protected  void hundirElemento(Posicion<E> posicioAOrdenar)
           
protected  Posicion<E> nuevaUltimaPosicion(E elem)
           
 int numElems()
          Accesor de lectura del número de elementos que hay en el contenedor.
 Recorrido posiciones()
          Método que soporta múltiples recorridos, de las posiciones del contenedor, simultáneos e independientes entre ellos.
 E primero()
          Accesor de lectura del elemento de menor prioridad, si hay.
protected  void subirElemento(Posicion<E> nuevaPosicion)
           
 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

heap

protected ColaConPrioridad.ArbolBinarioQuasicompletoVectorImpl<E> heap
Arbol binario vector que sirve de apoyo a la cola prioritaria.


comparador

protected java.util.Comparator<E> comparador
Comparador concreto que permite deducir la prioridad entre los elementos. Puede tener valor null y entonces se utiliza la interfaz java.lang.Comparable

Constructor Detail

ColaConPrioridad

public ColaConPrioridad()
Constructor sin parámetros (capacidad máxima, por defecto) y elementos de una clase que implementa java.lang.Comparable.


ColaConPrioridad

public ColaConPrioridad(int max)
Constructor con un parámetro (capacidad dada) y elementos de una clase que implementa java.lang.Comparable.

Parameters:
max - número máximo de elementos que puede contener la cola

ColaConPrioridad

public ColaConPrioridad(java.util.Comparator<E> comparador)
Constructor con un parámetro (capacidad máxima, por defecto) y elementos de una clase comparable con el comparador dado.

Parameters:
comparador - comparador que permite deducir la prioridad

ColaConPrioridad

public ColaConPrioridad(int max,
                        java.util.Comparator<E> comparador)
Constructor con dos parámetros (capacidad dada) y elementos de una clase comparable con el comparador dado.

Parameters:
max - número máximo de elementos que puede contener la cola
comparador - comparador que permite deducir la prioridad
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á

estaLleno

public boolean estaLleno()
Método para comprobar si el contenedor está lleno.

Returns:
cierto o falso, según si está lleno o no lo está

encolar

public void encolar(E elem)
Añade un elemento a la posición que le corresponde, si cabe.

Specified by:
encolar in interface Cola<E>
Parameters:
elem - elemento comparable que se quiere añadir a la cola

nuevaUltimaPosicion

protected Posicion<E> nuevaUltimaPosicion(E elem)

subirElemento

protected void subirElemento(Posicion<E> nuevaPosicion)

desencolar

public E desencolar()
Borra el elemento de menor prioridad, si hay alguno.

Specified by:
desencolar in interface Cola<E>
Returns:
primer elemento, que es el de menor prioridad
See Also:
escogeHijoAIntercambiar(Posicion)

borrarUltimaPosicion

protected Posicion<E> borrarUltimaPosicion()

hundirElemento

protected void hundirElemento(Posicion<E> posicioAOrdenar)

primero

public E primero()
Accesor de lectura del elemento de menor prioridad, si hay. Si se quiere desencolar el objeto se debe borrar seguidamente.

Specified by:
primero in interface Cola<E>
Returns:
primer elemento, que es el de menor prioridad
Throws:
ExcepcionContenedorVacio - si la cola está vacía

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 del contenedor inordre
Throws:
ExcepcionPosicionInvalida - si se quiere obtener el siguiente elemento de la enumeración y no hay ningún o no hay ningún más
See Also:
Iterador.haySiguiente(), Iterador.siguiente()

posiciones

public Recorrido posiciones()
Método que soporta múltiples recorridos, de las posiciones del contenedor, simultáneos e independientes entre ellos.

Returns:
enumeración de las posiciones del contenedor por nivel

toString

public java.lang.String toString()
Método que sobrescribe Object.toString(). Treo los elementos separados por el salto de línea de la plataforma.

Overrides:
toString in class java.lang.Object
Returns:
recorrido de los elementos en un recorrido por niveles

comparar

protected int comparar(Posicion<E> pos1,
                       Posicion<E> pos2)
Método protegido que compara los elementos contenidos en las posiciones recibidas. Si el constructor no ha definido un comparador, se utiliza java.lang.Comparable para deducir la prioridad entre ambos elementos.

Parameters:
pos1 - primera de las dos posiciones de referencia
pos2 - segunda de las dos posiciones de referencia
Returns:
un entero negativo, cero o positivo, según si el elemento de la primera posición tiene menos, igual o más prioridad que el elemento de la segunda posición, de acuerdo con la implementación del comparador
Throws:
ExcepcionPosicionInvalida - si alguna posición es null o no válida
ExcepcioElementsNoComparables - si alguno de los elementos contenidos en las posiciones es no comparable