// IG17 2004-05
// ColaPrioridad.h
// 17-12-2004, 18-12-2004

// Ejemplo del Tema 4: cola de prioridad generica

// Una cola de prioridad es una estructura de datos para almacenar
// eficientemente datos con los que se desea realizar las siguientes
// operaciones:
//
//    cola.Insertar(d) : inserta el dato d en la cola
//    d = cola.Minimo() : devuelve el dato de menor valor en la cola
//    cola.EliminarMinimo() : elimina el dato de menor valor de la cola
//
// La cola puede contener mas de un dato con el mismo valor. En caso de
// que varios sean minimos, EliminarMinimo() elimina solo uno de ellos.
//
// Existen varias implementaciones posibles de una cola de prioridad,
// por ejemplo (no son las unicas):
//
// - Empleando monticulos (heaps), se puede conseguir que el tiempo de
//   ejecucion en el peor de los casos de Insertar(d) sea O(log n), el
//   de Minimo() sea O(1) y el de EliminarMinimo() sea O(log n), siendo
//   n el numero de datos en la cola.
//
// - Empleando una lista ordenada, el tiempo de ejecucion en el peor
//   de los casos de Insertar(d) seria O(n), el de Minimo() seria O(1) y
//   el de EliminarMinimo() seria O(1).
//
// - Empleando una lista desordenada con acceso directo al minimo, el
//   tiempo de ejecucion en el peor de los casos de Insertar(d) seria
//   O(1), el de Minimo() seria O(1) y el de EliminarMinimo() seria O(n).
//
// Aqui puedes ver como se implementaria la tercera solucion. Como
// ejercicio, puedes implementar la segunda. La primera (que es mejor
// excepto en situaciones en las que se ejecute muchisimas menos veces
// EliminarMinimo que Insertar) puedes encontrarla en cualquier libro
// o asignatura de Estructuras de Datos.

// EJERCICIO: Una cola de prioridad de doble fin es una cola de prioridad
// que, ademas de las 3 anteriores, proporciona tambien las operaciones:
//
//    d = cola.Maximo() : devuelve el dato de mayor valor en la cola
//    cola.EliminarMaximo() : elimina el dato de mayor valor de la cola
//
// Haciendo algo similar a lo que se ha hecho en las funciones
// Minimo() y EliminarMinimo(), anyade Maximo() y EliminarMaximo() a
// esta implementacion, de modo que Maximo() se ejecute en tiempo
// O(1), EliminarMaximo en O(n), y el coste asintotico de las ya
// implementadas no aumente. Ten en cuenta la posibilidad de que el
// nodo con el valor minimo y el nodo con el valor maximo sean el
// mismo (porque la cola tiene un solo dato, o porque todos los datos
// coinciden).

#ifndef _COLA_PRIORIDAD
#define _COLA_PRIORIDAD

template <class T>
class ColaPrioridad {
  struct Nodo {
    T dato;
    Nodo *sig;
    Nodo(const T &, Nodo* = NULL);
  };
  Nodo *datos;
  Nodo *minimo; // Manteniendo este campo podemos ejecutar Minimo() en tiempo O(1)
  int talla; // Manteniendo este campo podemos ejecutar Talla() en tiempo O(1)
 public:

  ColaPrioridad();
  ColaPrioridad (const ColaPrioridad &);
  ColaPrioridad & operator= (const ColaPrioridad &);
  ~ColaPrioridad();
  void Vaciar();
  bool EstaVacia() const;
  int Talla() const;
  void Ver() const;
  void Insertar(const T &);
  void EliminarMinimo(); // No hace nada si se llama con una cola vacia

  const T & Minimo() const throw(int);
     // No modifica la cola.
     // Devuelve T por referencia por eficiencia, y por referencia
     // constante para impedir que se use a la izquierda de la
     // asignacion, porque si el usuario cambiase el valor de T podria
     // dejar de ser el minimo, dejando la cola en una situacion incoherente.
     // Lanza una excepcion si se llama con una cola vacia.
};

#endif