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

#include <iostream>
using namespace std;

#include "ColaPrioridad.h"

template <class T>
ColaPrioridad<T>::Nodo::Nodo(const T & d, Nodo *s) : dato(d), sig(s) {
}

template <class T>
ColaPrioridad<T>::ColaPrioridad()
  : datos(NULL), talla(0), minimo(NULL) {
}

template <class T>
ColaPrioridad<T>::ColaPrioridad (const ColaPrioridad<T> & p)
  : datos(NULL), talla(0), minimo(NULL) {
  *this = p;
}

template <class T>
ColaPrioridad<T> & ColaPrioridad<T>::operator= (const ColaPrioridad<T> &p) {
  if (this != &p) {
    Nodo *anterior;
    Vaciar();
    talla = p.talla;
    for (Nodo *aux = p.datos; aux != NULL; aux = aux->sig) {
      Nodo *nuevo = new Nodo(aux->dato);
      if (datos == NULL)
	anterior = datos = nuevo;
      else
	anterior = anterior->sig = nuevo;
      if (p.minimo == aux)
	minimo = nuevo;
    }
  }
  return *this;
}

template <class T>
ColaPrioridad<T>::~ColaPrioridad(){
  Vaciar();
}

template <class T>
void ColaPrioridad<T>::Ver() const {
  cout << "[";
  for (Nodo *aux = datos; aux != NULL; aux = aux->sig) {
    cout << aux->dato;
    if (aux->sig != NULL) cout << ",";
  }
  cout << "] (talla = " << talla << ")";
  if (minimo != NULL)
    cout << " (minimo = " << minimo->dato << ")";
  cout << endl;
}

template <class T>
void ColaPrioridad<T>::Insertar(const T & d) {
  datos = new Nodo(d, datos);
  talla++;  // Asi se mantiene el campo talla actualizado,
            // lo que permite que el coste de Talla() sea O(1),
            // y el coste de Insertar(d) sigue siendo O(1).
  if (minimo == NULL || d < minimo->dato)
    minimo = datos; // Asi se mantiene el campo minimo actualizado,
                    // lo que permite que el coste de Minimo() sea O(1),
                    // y el coste de Insertar(d) sigue siendo O(1).
}

template <class T>
void ColaPrioridad<T>::EliminarMinimo() {

  if (datos == NULL) return;
  // En lo que sigue, sabemos que la cola tiene uno o mas nodos

  Nodo *anterior;
  Nodo *nuevoMinimo = NULL;
  
  for (Nodo *aux = datos; aux != NULL; aux = aux->sig) {
    // Averiguamos cual es el nuevo minimo y al mismo tiempo localizamos
    // el nodo que precede al actual minimo y cambiamos su puntero sig
    if (aux != minimo) {
      if (nuevoMinimo == NULL || aux->dato < nuevoMinimo->dato)
	nuevoMinimo = aux;
    } else {
      if (aux == datos)
	datos = aux->sig;
      else
	anterior->sig = aux->sig;
    }
    anterior = aux;
  }
  delete minimo;
  minimo = nuevoMinimo;
    
  talla--;
}

template <class T>
int ColaPrioridad<T>::Talla() const {
  return talla;
}

template <class T>
bool ColaPrioridad<T>::EstaVacia() const {
  return talla==0;
}

template <class T>
void ColaPrioridad<T>::Vaciar(){
  Nodo *aux;
  while(datos != NULL) {
    aux = datos;
    datos = datos->sig;
    delete aux;
  }
  talla = 0;
  minimo = NULL;
}

// Otra solucion, algo mas estructurada, MUCHO menos eficiente en este caso:
// fijate en que esta solucion tendria un coste O(n*n) y la anterior O(n)
// template <class T>
// void ColaPrioridad<T>::Vaciar(){
//   while(! EstaVacia())
//     EliminarMinimo();
// }


template <class T>
const T & ColaPrioridad<T>::Minimo() const throw(int) {
  if(minimo != NULL)
    return minimo->dato;
  else
    throw -1;
}