source: GTP/trunk/Lib/Geom/shared/GTGeometry/src/libs/leaves/tlista.h @ 830

#ifndef TLISTA_H
#define TLISTA_H



#include <iostream>



template<class T>
struct dato_enlazado
{
        T dato; // El dato como tipo abstracto
        float prioridad; // Por si queremos ordenar la lista con prioridad
        dato_enlazado * sig; // Puntero al siguient
        dato_enlazado (void); // Constructor por defecto
        dato_enlazado (const T& a); // Constructor de copia
        dato_enlazado (const T& a, const float); // Constructor de copia
        dato_enlazado& operator =(const dato_enlazado& d); // Operador de asignación
        bool operator ==(const dato_enlazado& d) const; // Operador de igualdad
        bool operator !=(const dato_enlazado& d) const; // Operador de desigualdad
        //friend ostream& operator << (ostream& os, T& d);
};


//------------------------------------------------------------------------------------------------------------------------------
// NO LA BORRO PORQUE ES INTERESANTE
//------------------------------------------------------------------------------------------------------------------------------
/*template<class T>
ostream& operator << (ostream& os, T& d)
{
        os << d.dato;

        return os;
}*/


//------------------------------------------------------------------------------------------------------------------------------
// Constructor por defecto, inicializa el siguiente a nulo
// Parámetros : ninguno
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
dato_enlazado<T>::dato_enlazado (void) : sig(NULL), prioridad(0.0f)
{
}


//------------------------------------------------------------------------------------------------------------------------------
// Constructor de copia
// Parámetros : T& a --> Referencia constante al dato a copiar
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
dato_enlazado<T>::dato_enlazado (const T& a) : dato(a), sig(NULL)
{
}


//------------------------------------------------------------------------------------------------------------------------------
// Constructor con dato de prioridad
// Parámetros : T& a --> Referencia constante al dato a copiar
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
dato_enlazado<T>::dato_enlazado (const T& a, const float prior) : dato(a), sig(NULL), prioridad(prior)
{
}


//------------------------------------------------------------------------------------------------------------------------------
// Operador de asignación
// Parámetros : const dato_enlazado& d --> Referencia constante al dato que se va a copiar
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
dato_enlazado<T>& dato_enlazado<T>::operator =(const dato_enlazado& d)
{
        dato = d.dato;
        sig = NULL;
        return *this;
}


//------------------------------------------------------------------------------------------------------------------------------
// Operador de igualdad, devuelve true si los datos son iguales y false en caso contrario
// Parámetros : const dato_enlazado& d
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
bool dato_enlazado<T>::operator ==(const dato_enlazado<T>& d) const
{
        return dato == d.dato;
}


//------------------------------------------------------------------------------------------------------------------------------
// Operador de desigualdad, devuelve true si los datos son distintos y false si son iguales
// Parámetros : const dato_enlazado
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
bool dato_enlazado<T>::operator !=(const dato_enlazado<T>& d) const
{
        return dato != d.dato;
}


//------------------------------------------------------------------------------------------------------------------------------
template<class T> class iterador_lista;
template<class T> class iterador_prioridad;
//------------------------------------------------------------------------------------------------------------------------------

template<class T>
class lista
{
        protected :
                float Prioridad (const unsigned long); // Devuelve la prioridad del elemento seleccionado
        public :
        dato_enlazado<T> *cab;
        //dato_enlazado<T> *cola;
        dato_enlazado<T> *selec; // Puntero al dato actualmente 'encontrado', 
                                                         // aumenta la eficiencia en la busqueda de datos consecutivos
        dato_enlazado<T> *cola; // Esto es temporal, hay que borrarlo
        
public:
        lista (void); // Constructor vacio
        virtual ~lista (void); // Destructor
        lista (lista<T>&); // Constructor de copia
        bool operator == (lista<T>&) const; // Operador de comparación
        bool operator != (lista<T>&) const; // Idem
        virtual bool Inserta (const T& a); // Inserta un dato en la lista
        virtual bool InsertaPrioridad (const T&, const float, const bool); // Inserta manteniendo orden
        virtual bool Busca (const T& a);
        virtual bool Borra (const T& a);   // Borra a si existe
        virtual bool BorraLista (void);   // Borra todos los elementos de la lista
        virtual bool Cab (void); // Situa el seleccionado al principio de la lista
        virtual bool Sig (void);
        virtual T GetCab (void); // Extrae la cabeza de la lista
        virtual T GetCola (void);
        virtual bool BorraCola (void); //borra la cola
        virtual unsigned long NDatos (void) const; // Devuelve el número de datos en la lista
        virtual unsigned long NPrioridadDatos (void) const; //
        friend class iterador_lista<T>;
        friend class iterador_prioridad<T>;
        // A partir de aqui las funciones son sólo para depurar el código
        friend std::ostream& operator << (std::ostream& os, lista<T>& d);
};


//------------------------------------------------------------------------------------------------------------------------------
// PARA DEPURAR EL CÓDIGO, PERO ES INTERESANTE
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
std::ostream& operator << (std::ostream& os, lista<T>& l)
{
        dato_enlazado<T> * tmp = l.cab;

        while (tmp)
        {
                cout << (*tmp).dato;
                tmp = tmp->sig;
        }

        return os;
}


//------------------------------------------------------------------------------------------------------------------------------
// Constructor por defecto
// Parámetros : Ninguno
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
lista<T>::lista (void) : cab(NULL), selec(NULL), cola(NULL)
{
}


//------------------------------------------------------------------------------------------------------------------------------
// Constructor de copia
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
lista<T>::lista (lista<T>& l) : cab(NULL), selec(NULL), cola(NULL)
{
        dato_enlazado<T> *tmp = l.cab;
        dato_enlazado<T> *nuevo; // Apuntador a la memoria que se va a reservar

        while (tmp != NULL)
        {
                nuevo = new dato_enlazado<T> (*tmp); // Reservo espacio para el nuevo dato
                if (cola == NULL) cola = nuevo;
                nuevo->sig = cab; // El siguiente del nuevo dato será la cabeza de la lista     
                selec = cab = nuevo; // Ahora hago apuntar la cabeza al nuevo dato

                tmp = tmp->sig;
        }
}


//------------------------------------------------------------------------------------------------------------------------------
// Destructor por defecto
// Parámetros : Ninguno
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
lista<T>::~lista (void)
{
        //BorraLista ();
}


//------------------------------------------------------------------------------------------------------------------------------
// Operador de comparación. Dos listas son iguales si contienen los mismos elementos aunque no estén en el mismo orden
// Parámetros --> const lista<T>& l : Lista con la que se compara
// Salida --> 'true' si las dos listas contienen los mismos elementos
//                        'false' en cualquier otro caso
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
bool lista<T>::operator == (lista<T>& l) const
{
        if (NDatos () != l.NDatos ()) return false; // Si no tienen el mismo número de datos no pueden ser iguales

        //lista<T> tmp = *this;
        lista<T> tmpl = l;
        //iterador_lista<T> iterador (tmp); // Creo un iterador sobre esta lista
        //T* dato;

        //while (dato = iterador ())
                //if (!tmpl.Busca(*dato)) return false; // Si uno de los datos de la primera lista no lo encuentro en la segunda no son iguales

        dato_enlazado<T> *tmpd = cab;

        while (tmpd != NULL)
        {
                if (tmpl.Busca (tmpd->dato) == false) return false;
                tmpd = tmpd->sig;
        }

        return true; // si todos los de la primera están en la segunda y tienen el mismo tamaño es que son iguales
}


//------------------------------------------------------------------------------------------------------------------------------
// Operador de desigualdad
// Parámetros --> const lista<T>& l : Lista con la que se compara
// Salida --> 'true' si las listas son distintas
//                        'false' en caso contrario
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
bool lista<T>::operator != (lista<T>& l) const
{
        if (*this == l) return false;

        return true;
}


//------------------------------------------------------------------------------------------------------------------------------
// Devuelve la prioridad en la posición i-ésima
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
float lista<T>::Prioridad (const unsigned long i)
{
        unsigned long cont = 0L; // Inicializo el contador de posiciones

        selec = cab; //Inicio la búsqueda desde la cabeza
        while (i != cont && selec != NULL) // Mientras no haya encontrado la posición y me queden elementos
        {
                selec = selec->sig; // Paso al siguiente
                cont++; // e incremento en uno el contador
        }

        return selec->prioridad;
}


//------------------------------------------------------------------------------------------------------------------------------
// Inserta un nuevo elemento en la lista. El nuevo elemento se inserta en la cabeza
// Parámetros : a --> el dato que hay que añadir a la lista
// Salida : 'true' si el dato se ha podido insertar en la lista
//                      'false' en caso contrario
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
bool lista<T>::Inserta (const T& a)
{
        
        if (cola == NULL)
        {
                selec = cab = cola = new dato_enlazado<T> (a);
                return true;
        }
        else
        {
                if (!(cola->sig = new dato_enlazado<T> (a))) // Reservo espacio para el nuevo dato
                        return false;
                else
                {
                        cola = cola->sig;
                        selec = cola; // Ahora hago apuntar la cabeza al nuevo dato
                        return true;
                }
        }
}


//------------------------------------------------------------------------------------------------------------------------------
// Inserta manteniendo orden
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
bool lista<T>::InsertaPrioridad (const T& a, const float prior, const bool borra)
{
        dato_enlazado<T>* tmp = cola;

        selec = new dato_enlazado<T> (a, prior); // Creo el nodo a insertar

        if (cab == NULL) // No hay ningún dato en la lista
        {
                cab = cola = selec;
                return true;
        }
        // Tengo mas de uno en la lista y el que voy a insertar es el menor
        if (cola->prioridad >= prior)
        {
                if (cola->dato != a)
                {
                        selec->sig = cola;
                        cola = selec;
                }
                else if (cola->dato == a && borra)
                {
                        dato_enlazado<T>* tmp_selec = cola;
                        cola = cola->sig;
                        delete tmp_selec;
                }
                else delete selec;
                return true;
        }
        else
        {
                while (tmp != cab) // Mientras no llegue a la cabeza
                {
                        if (tmp->sig->prioridad >= prior) // inserto antes de tmp->sig
                        {
                                if (a != tmp->sig->dato) // Si no está ya presente en la lista
                                {
                                        selec->sig = tmp->sig; // lo inserto
                                        tmp->sig = selec;
                                }
                                else if (a == tmp->sig->dato && borra) // Si hay que borrarlo
                                {
                                        dato_enlazado<T>* tmp_selec = tmp->sig;
                                        if (tmp->sig == cab) cab = tmp;
                                        tmp->sig = tmp->sig->sig;
                                        delete tmp_selec;
                                }
                                else // si está presente
                                {
                                        delete selec; // Libero la memoria que había reservado
                                }
                                return true;
                        }
                        tmp = tmp->sig;
                }
                if ((tmp == cab) && (a != cab->dato)) // Si llego a la cabeza sin encontrar ninguno en la lista con prioridad mayor
                {                               // es porque el que voy a insertar tiene la mayor prioridad
                        cab->sig = selec;
                        cab = selec;
                        return true;
                }
                else
                {
                        delete selec;
                        selec = cab;
                }
        }
        return false;
}



//------------------------------------------------------------------------------------------------------------------------------
// Busca un elemento en la lista y deja el puntero selec apuntando a él si lo encuentra
// Parámetros : const T& a --> Referencia al dato que se está buscando
// Salida : true si el dato efectivamente es encontrado
//                      false si el dato no está en la lista
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
bool lista<T>::Busca (const T& a)
{
        dato_enlazado<T> *tmp; // Puntero de reserva

        if (!cab) return false; // Si no hay ningún dato no hay donde buscar

        if (selec && selec->dato != a)
        {
                tmp = selec; // Me guardo el actualmente seleccionado
                selec = selec->sig; // Iniciaré la búsqueda a partir del dato siguiente
        }
        else
        {
                selec = cab; // Iniciaré la busqueda desde la cabeza si no
                //tmp = NULL;
        }

        while (selec != NULL && selec->dato != a)
                selec = selec->sig; // lo busco a partir de la posición original hacia el final

        if (!selec) // Si antes habia uno seleccionado
        {
                selec = cab; // Iniciaré la búsqueda desde la cabeza
                while (selec != tmp && selec->dato != a) selec = selec->sig;
        }
        
        if (selec && selec->dato == a) return true;
        return false;
}


//------------------------------------------------------------------------------------------------------------------------------
// Borra el elemento indicado de la lista
// Parámetros : const T& a --> Referencia al elemento a borrar
// Salida --> true si el elemento ha sido encontrado y borrado
//                        false si no se ha encontrado el elemento
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
bool lista<T>::Borra (const T& a)
{
        dato_enlazado<T> *tmp = cab; // Me guardo la posición de lo que quiero borrar

        if (!Busca (a)) return false; // Si no lo encuentra devuelve false

        if (selec == cab) // Si lo que quiero borrar es la cabeza
        {
                cab = cab->sig; // Adelanto la cabeza
                delete selec; // Borro el dato
                selec = cab; // Hago apuntar el actual a la nueva cabeza
        }
        else
        {
                while (tmp->sig->dato != a) tmp = tmp->sig; // Encuentro el anterior al que quiero borrar
                if (tmp->sig == cola) cola = tmp;

                tmp->sig = selec->sig; // Saco el que voy a borrar fuera de la lista
                delete selec; // Borro el dato
                if (!(selec = tmp->sig)) selec = cab; // Si al avanzar el seleccionado llego al final, inicio desde la cabeza
        }

        return true;
}




//------------------------------------------------------------------------------------------------------------------------------
// Elimina todos los elementos de lista
// Parámetros : ninguno
// Salida : Si la lista ha sido efectivamente borrada true
//                      false en caso contrario
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
bool lista<T>::BorraLista (void)
{
        while (cab)
        {
                selec = cab;
                if (!Borra (selec->dato)) return false; // Borro siempre la cabeza
        }
        return true;
}


//------------------------------------------------------------------------------------------------------------------------------
// Coloca el seleccionado al inicio de la lista
// Parémetros --> ninguno
// Salida --> 'true' si efectivamente se ha colocado al inicio de la lista
//                        'false' si ha habido algún error y el seleccionado no apunta al inicio de la lista
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
bool lista<T>::Cab (void)
{
        if (cab)
        {
                selec = cab;
                return true;
        }
        return false;
}


//------------------------------------------------------------------------------------------------------------------------------
// Avanza el seleccionado hasta la siguiente posición, el siguiente del último es de nuevo la cabeza
// Parámetros : ninguno
// Salida : 'true' si se inicia desde la cabeza al avanzar
//                      'false' en cualquier otro caso
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
bool lista<T>::Sig (void)
{
        if (!(selec = selec->sig))
        {
                selec = cab; // Avanzo el seleccionado hasta el siguiente, y si me paso, lo llevo
                return true; // de nuevo a la cabeza
        }
        return false;
}


//------------------------------------------------------------------------------------------------------------------------------
// Extrae la cabeza de la lista
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
T lista<T>::GetCab (void)
{
        if (cab->dato == NULL) return NULL; // Si no hay nada en la lista devuelve NULL
        
                else    return cab->dato;
}


//------------------------------------------------------------------------------------------------------------------------------
// Extrae la cola de la lista  ///ACABAAAR melon
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
T lista<T>::GetCola (void)
{
        
        if (cola->dato == NULL) return NULL; // Si no hay nada en la lista devuelve NULL
        
                else    return cola->dato;
        
}
//------------------------------------------------------------------------------------------------------------------------------
// Extrae y borra la cola de la lista
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
bool lista<T>::BorraCola (void)
{
        /*dato_enlazado<T>* tmp = cab; // Nos situamos incialmente en la cabeza


        if (cab == NULL) return false; // Si no hay nada en la lista devuelve NULL
        if (cab == cola) // Si solo tenemos un elemento
        {
                delete cab;
                cab = cola = selec = NULL;
                return true;
        }
        else
        {
                while (tmp->sig != cola)
                        tmp = tmp->sig;
                delete cola;
                cola = tmp;
                cola->sig = NULL;
                selec = cab;
                return true;
        }*/
        return Borra (cola->dato);
}

//------------------------------------------------------------------------------------------------------------------------------
// Devuelve el número de datos actuales en la lista
// Parámetros --> Ninguno
// Salida --> int : el número de datos en la lista
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
unsigned long lista<T>::NDatos (void) const
{
        unsigned long nDatos = 0; // Para contar el número de datos de la lista
        /*lista<T> tmp = *this;
        /iterador_lista<T>  iterador(tmp); // Creo un iterador sobre la lista
        T * dato;

        while (dato = iterador ())
                nDatos++;*/

        dato_enlazado<T> * tmp = cab;

        while (tmp != NULL)
        {
                tmp = tmp->sig;
                nDatos++;
        }

        return nDatos;
}


template<class T>
unsigned long lista<T>::NPrioridadDatos (void) const
{
        unsigned nDatos = 0;

        dato_enlazado<T>* tmp = cola;

        while (tmp != NULL)
        {
                tmp = tmp->sig;
                nDatos++;
        }

        return nDatos;
}


//------------------------------------------------------------------------------------------------------------------------------
// Esta es la clase iterador, recorre la lista desde la cabeza a la cola devolviendo punteros a los datos
//------------------------------------------------------------------------------------------------------------------------------

template<class T>
class iterador_lista
{
        private:
                dato_enlazado<T> *iterador; // Elemento de la lista a devolver
                lista<T> *lista_iterada; // Puntero a la lista sobre la que se está iterando

        public:
                iterador_lista (lista<T>&); // Constructor con una lista
                T * const operator () (void); // Operador de iteracion
                T * const IteradorCircular (void); // Igual que el anterior, pero cuando llega al final, recomienza
};


//------------------------------------------------------------------------------------------------------------------------------
// Constructor con un lista
// Parámetros --> lista<T>& l : Referencia a la lista sobre la que se iterará
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
iterador_lista<T>::iterador_lista (lista<T>& l) : lista_iterada (&l), iterador(l.cab)
{
         // Hago que el primer elemento de iteración sea la cabeza
}


//------------------------------------------------------------------------------------------------------------------------------
// Operador () que es el que hace las funciones de iterador
// Párámetros --> Ninguno
// Salida --> T * const : un puntero constante al elemento devuelto por el iterador
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
T * const iterador_lista<T>::operator () (void)
{
        T * tmp = &iterador->dato;

        if (!iterador) iterador = lista_iterada->cab; // Si llegamos al final de la lista, dejamos el iterador 
        else iterador = iterador->sig;                                  // al inicio de la lista.

        return tmp;
}


//------------------------------------------------------------------------------------------------------------------------------
// Igual que el anterior, pero cuando llega al final de la lista empieza desde el principio
// Parametros --> Ninguno
// Salida T * const : un puntero constante al elemento devuelto
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
T * const iterador_lista<T>::IteradorCircular (void)
{
        if (iterador == NULL) return NULL;
        else
        {
                iterador = iterador->sig;
                if (!iterador) iterador = lista_iterada->cab;

                return &iterador->dato;
        }
}


//------------------------------------------------------------------------------------------------------------------------------
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
class iterador_prioridad
{
        private:
                dato_enlazado<T> *iterador; // Elemento de la lista a devolver
                lista<T> *lista_iterada; // Puntero a la lista sobre la que se está iterando

        public:
                iterador_prioridad (lista<T>&); // Constructor con una lista
                T * const operator () (void); // Operador de iteracion
};


//------------------------------------------------------------------------------------------------------------------------------
// Constructor con un lista
// Parámetros --> lista<T>& l : Referencia a la lista sobre la que se iterará
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
iterador_prioridad<T>::iterador_prioridad (lista<T>& l) : lista_iterada (&l), iterador(l.cola)
{
         // Hago que el primer elemento de iteración sea la cabeza
}


//------------------------------------------------------------------------------------------------------------------------------
// Operador () que es el que hace las funciones de iterador
// Párámetros --> Ninguno
// Salida --> T * const : un puntero constante al elemento devuelto por el iterador
//------------------------------------------------------------------------------------------------------------------------------
template<class T>
T * const iterador_prioridad<T>::operator () (void)
{
        T * tmp = &iterador->dato;

        if (!iterador) iterador = lista_iterada->cola; // Si llegamos al final de la lista, dejamos el iterador 
        else iterador = iterador->sig;                                  // al inicio de la lista.

        return tmp;
}




#endif