lista.h

/* Por Martín Miguel y Federico Lebrón */
#ifndef __LISTA_H__
#define __LISTA_H__

#include <iostream>
#include <cassert>
using namespace std;

//se puede asumir que el tipo T tiene constructor por copia
//no se puede asumir que el tipo T tenga operator=
template<class T>
class Lista {
public:
    /*constructor por defecto, crea una lista vacia*/
    Lista();

    /*constructor por copia, una vez copiada, ambas listas deben ser
     *independientes, es decir, cuando se borre una no debe morir la otra.
     *El cursor de la lista otra no debe cambiar de posición, mientras que
     *el cursor de la lista creada *DEBE* apuntar al primer elemento de la
     *lista (o a NULL si la lista es vacia)*/
    Lista(const Lista& otra);

    /*Constructor que genera una lista con n copias del elemento e.
     *El cursor debe apuntar al primer elemento.*/
    Lista(int n, const T& e);

    /*Destructor. Acordarse de liberar toda la memoria!*/
    ~Lista();

    /*Dice cuantos elementos tiene la lista. No modifica el cursor!*/
    int tamanio() const;

    /*Dice si la lista es vacia. Esta funcion debe ser muy rapida.*/
    bool esVacia() const;

    /*Muestra la lista en formato [e1,e2,...,en] por el stream que recibe
     *como parametro. La lista vacia se muestra como [] y una lista
     *con un solo elemento e como [e].
     *No puede modificar el cursor.*/
    void mostrarLista(ostream&) const;

    /**********************
     * Manejo del CURSOR  *
     **********************/
    /*Mueve el cursor para que apunte al primer elemento.  Si la lista
     *es vacia, no hace nada*/
    void retrocederCursorAlInicio() const;

    /*mueve el cursor para que apunte al ultimo elemento. Si la lista
     *es vacia, no hace nada.*/
    void avanzarCursorAlFinal() const;

    /*avanza el cursor al elemento siguiente.  Si no hay mas elementos
     *adelante o la lista es vacia, entonces no hace nada.*/
    void avanzarCursor() const;

    /*retrocede el cursor al elemento anterior.  Si no hay mas elementos
     *atras o la lista es vacia, entonces no hace nada.*/
    void retrocederCursor() const;

    /*devuelve el valor en la posicion apuntada por el cursor.
     *PRE: la lista no es vacia.*/
    const T& actual() const;

    /*devuelve el valor en la posicion apuntada por el cursor.
     *PRE: la lista no es vacia.*/
    T& actual();

    /*agrega un elemento en la posicion siguiente al cursor.
     *El cursor no cambia de posicion.*/
    void insertarAtrasDelCursor(const T& elem);

    /*agrega un elemento en la posicion siguiente al cursor.
     *El cursor no cambia de posicion.*/
    void insertarAdelanteDelCursor(const T& elem);

    /*elimina el elemento apuntado por el cursor.
     *Si el elemento eliminado es el ultimo, entonces el cursor debe
     *apuntar al ultimo elemento de la lista modificada.  En caso
     *contrario, el cursor debe apuntar al elemento que le sigue al cursor.*/
    void eliminarCursor();

private:
    //No se puede modificar esta funcion.
    Lista<T>& operator=(const Lista<T>& lista) {
        assert(false);
    }

    //Aca va la implementacion del nodo.
    template<typename T2>struct Nodo {
        Nodo* next;
        Nodo* prev;
        T2 value;
        Nodo(T2 &elem) :value(elem) {
            next = next = NULL;
        }

        Nodo(const T2 &elem) :value(elem) {
            prev = next = NULL;
        }
    };

    mutable Nodo<T>* cursor;
    Nodo<T>* first;
    Nodo<T>* last;

    unsigned int length;

    void borrarNodos(Nodo<T>* n);
    void copiarNodos(Nodo<T>* next);
};

// O(l.length)
template<class T>
ostream& operator<<(ostream& out, const Lista<T>& l) {
    l.mostrarLista(out);
    return out;
}

// O(1)
template<typename T> Lista<T>::Lista() {
    length = 0;
    cursor = first = last = NULL;
}

template<typename T> void Lista<T>::copiarNodos(Nodo<T>* next) {
    if(!next) return;
    insertarAtrasDelCursor(next->value);
    cursor = last;
    copiarNodos(next->next);
}

// O(otra.length), asumiendo el constructor por copia de T es O(1)
template<typename T> Lista<T>::Lista(const Lista& otra) {
    cursor = first = last = NULL;
    length = 0;
    if(otra.first) copiarNodos(otra.first);
    cursor = first;
}

// O(n)
template<typename T>Lista<T>::Lista(int n, const T& e) {
    length = 0;
    cursor = first = last = NULL;
    while(n--) {
        insertarAtrasDelCursor(e);
        if(!length) last = first;
        length++;
    }
    cursor = first;
}

// O(length)
template<typename T>Lista<T>::~Lista() {
    if(!first) return;
    borrarNodos(first);
    delete first;
}

template<typename T>void Lista<T>::borrarNodos(Nodo<T>* n) {
    if(n->next == NULL) return;
    borrarNodos(n->next);
    delete n->next;
}

// O(1), podría ser O(length) si camináramos hasta el final
template<typename T> int Lista<T>::tamanio() const {
    return length;
}

// O(1), podría seguir O(1) sin el length cacheado, devolviendo !first
template<typename T> bool Lista<T>::esVacia() const {
    return !length;
}

// O(length)
template<typename T> void Lista<T>::mostrarLista(ostream& os) const {
    os << "[";
    Nodo<T>* pie = first;
    while(pie) {
        os << pie->value;
        if(pie = pie->next) os << ",";
    }
    os << "]";
}

// O(1)
template<typename T> void Lista<T>::retrocederCursorAlInicio() const {
    if(!esVacia()) cursor = first;
}

// O(1)
template<typename T> void Lista<T>::avanzarCursorAlFinal() const {
    if(!esVacia()) cursor = last;
}

// O(1)
template<typename T> void Lista<T>::avanzarCursor() const {
    if (!esVacia() && cursor->next) cursor = cursor->next;
}

// O(1)
template<typename T> void Lista<T>::retrocederCursor() const {
    if (!esVacia() && cursor->prev) cursor = cursor->prev;
}

// O(1)
template<typename T> const T& Lista<T>::actual() const {
    return cursor->value;
}

// O(1)
template<typename T> T& Lista<T>::actual() {
    return cursor->value;
}

// O(1), asumiendo que el constructor por copia de T es O(1)

template<typename T> void Lista<T>::insertarAtrasDelCursor(const T& elem) {
    Nodo<T>* n = new Nodo<T>(elem);
    n->prev = cursor;
    if(esVacia()) first = last = cursor = n;
    else {
        if(cursor == last) last = n;
        else {
            n->next = cursor->next;
            cursor->next->prev = n;
        }
        cursor->next = n;
    }
    length++;
}

// O(1), asumiendo que el constructor por copia de T es O(1)

template<typename T> void Lista<T>::insertarAdelanteDelCursor(const T& elem) {
    Nodo<T>* n = new Nodo<T>(elem);
    n->next = cursor;
    if(esVacia()) first = last = cursor = n;
    else {
        if(cursor == first) first = n;
        else {
            n->prev = cursor->prev;
            cursor->prev->next = n;
        }
        cursor->prev = n;
    }
    length++;
}

// O(1)
template<typename T> void Lista<T>::eliminarCursor() {
    assert(cursor && length);

    if(cursor == first) {
        if(length == 1) first = last = NULL;
        else {
            first = first->next;
            first->prev = NULL;
        }
    } else if(cursor == last) {
        last = last->prev;
        last->next = NULL;
    } else {
        cursor->next->prev = cursor->prev;
        cursor->prev->next = cursor->next;
    }

    Nodo<T>* basura = cursor;
    cursor = cursor->next ? cursor->next : last;
    delete basura;

    length--;
}

#endif