/* lab17.h  (C) 2006  adolfo@di-mare.com  */

/** \file  lab17.h
    \brief Lista implementada usando el Rep de la biblioteca STL.

    \author Adolfo Di Mare <adolfo@di-mare.com>
    \date   2006
*/

#ifndef STL_list_h
#define STL_list_h   ///< Evita la inclusión múltiple

#include <iostream>
#include <cassert>   // #include <assert.h>
using namespace std;

namespace ADH {

// declaraciones hacia adelanta para que el compilador no se enrede
template <class T> class list;      // para definir check_ok( const list<E> & );
template <class T> class list_node; // para definir punteros list_node<T> * prev, * next;
template <class T> class list_node_base;
template <class T> class test_list;

/// Clase base para el nodo de la lista STL.
/// - Esta clase un truco para ahorrarse el campo \c m_val
///   del nodo cabezal de la lista.
template <class T>
class list_node_base {
    template <class E> friend class list;
    template <class E> friend class list_node;
    template <class E> friend class test_list;
private: // Todo el Rep es privado
      list_node_base() { }  ///< Constructor
public:
      list_node<T> * prev;  ///< Puntero al nodo anterior
      list_node<T> * next;  ///< Puntero al siguiente nodo
/* NOTA
   - Esta es una clase privada porque el programador cliente
     nunca tiene necesidad de usar nodos, pues para accesar
     los valores de la lista puede usar iteradores y las
     operaciones de inserción y borrado de la lista.
   - El constructor no inicializa los campos "next+prev" porque
     al crear un nodo siempre es necesario cambiarles el
     valor.
   - Esta clase no está definida dentro de las clase list<T>
     porque al usar plantillas el compilador no entiende bien
     las clases de plantilla anidadas. Por eso, el truco es
     usar una clase "externa" a list<T>, pero dejando privado
     su constructor para que el programador cliente no pueda
     usar esta clase directamente.
   - No se han usado los identificadores "m_next" y "m_prev"
     para los campos "next" y "prev" para que el código se
     parezca más al que aparece en los libros de texto.
   - Los campos "next" y "prev" son públicos por la misma
     razón por la que es público el campo "m_val" de la
     clase list_node<T>.
*/
}; // list_node_base

/// Nodos de la clase \c "list<T>".
/// - Esta es una clase privada para implementar la lista.
template <class T>
class list_node : public list_node_base<T> {
    template <class E> friend class list;
    template <class E> friend class list_node;
    template <class E> friend class test_list;
    template <class E> friend bool  check_ok( const list<E> & L );
private: // Todo el Rep es privado
     /// Constructor para \c "v"
     list_node(const T& v) : m_val(v) {}
public:
     T m_val;  ///< Valor almacenado en el nodo
/* NOTA
   - El constructor no inicializa los campos "next+prev" porque
     al crear un nodo siempre es necesario cambiarles el
     valor.
   - El campo "m_val" es público porque el compilador no permite
     declarar "friend" a la clase "iterator":
       template <class T> friend class list<T>::iterator; // NO COMPILA
     Al ser "m_val" un campo público, en el implementación de
     list<T>::iterator::operator*() es posible acceder a "m_val"
     sin que el compilador emita un error de violación de campo
     privado.
     - Como el constructor de list<T>::iterator es privado
       un programador que trate de crear nodos recibirá un error del
       compilador.
     - Lo mismo ocurrirá si el programador tratar de usar el campo
       "next" o "prev" a través de un iterador pues para llegar a
       cualquiera de esos campos antes necesita entrar al campo "m_p"
       que es un campo privador de la clase list<T>::iterator.
*/
}; // list_node

/// Lista implementada usando el Rep de la biblioteca STL.
/// - Esta clase tiene varias de las operaciones más importantes
///   de la clase \c "list" de la biblioteca estándar de C++.
template <class T>
class list : public list_node_base<T> {
    template <class E> friend class test_list;
public:
    typedef T  value_type;  ///< Nombre estándar del objeto contenido
    typedef value_type& reference; ///< Referencia al objeto contenido
    typedef const value_type& const_reference; ///< Referencia constante al objeto contenido
    typedef unsigned size_type;  ///< Nombre estándar del tipo retornado por \c size()
public:
    /** Iteradores bidireccionales para la clase \c list<T>.
        \dontinclude test_STL_list.cpp
        \skipline    test::iterator()
        \until       }}
        \see         ADH::test_list<T>::test_iterator()
    */
    class iterator {
        template <class E> friend class list;
        template <class E> friend class test_list;
    public:
        iterator() : m_p(0) { /* inicializo, como los de STL */ } ///< Constructor

        /// Constructor de copia
        iterator( const iterator& o ) : m_p(o.m_p) { }  // copia el Rep directo
        iterator& operator=( const iterator& o ) {
            m_p = o.m_p; // copia el Rep directo
            return *this;
        }

        /// ¿ <code>p == q</code> ?
        friend bool operator == ( const iterator& p, const iterator& q ) {
            return ( p.m_p == q.m_p );
        }
        /// ¿ <code>p != q</code> ?
        friend bool operator != ( const iterator& p, const iterator& q ) {
            return !( p == q ); // return operator == (p, q);
        }

        iterator operator++()
            { m_p = m_p -> next; return *this; }                   ///< \c ++p
        iterator operator++(int)
            { iterator q = (*this); m_p = m_p -> next; return q; } ///< \c p++
        iterator operator--()
            { m_p = m_p -> prev; return *this; }                   ///< \c --p
        iterator operator--(int)
            { iterator q = (*this); m_p = m_p -> prev; return q; } ///< \c p--

        value_type& operator*()  { return   m_p -> m_val ; } ///< \c *p
        value_type* operator->() { return &(m_p -> m_val); } ///< \c p->

    private:
        /// Verifica la invariante de la clase.
        bool ok( ) const;
        /// Verifica la invariante de la clase.
        template <class E> friend bool check_ok( const iterator & I ) {
            return I.ok();
        }
    private:
        list_node<T> * m_p;   ///< Puntero al nodo de \c "list"
    }; // list<T>::iterator


public:
     /** Constructor de vector.
        \dontinclude test_STL_list.cpp
        \skipline    test::constructor()
        \until       }}
        \see         ADH::test_list<T>::test_constructor()
    */
    list() { this->next = this->prev = static_cast< list_node<T>* >((void*) this); }
    /// Constructor de copia. \see ADH::list<T>::list()
    list(const list& L) {
        this->next = this->prev = static_cast< list_node<T>* >((void*) this);
        *this = L;
}
    ~list() { clear(); } ///< Destructor
    void clear();

    void push_front( const value_type& v );
    void push_back(  const value_type& v );

    void pop_front();
    void pop_back();

    /** Retorna "true" si la lista está vacía.
        \dontinclude test_STL_list.cpp
        \skipline    test::constructor()
        \until       }}
        \see         ADH::test_list<T>::test_constructor()
    */
    bool      empty() const { return this->next == static_cast< list_node<T>* >((void*) this); }
    size_type size()  const; ///< Cantidad de valores almacenados en \c "*this". \see ADH::list<T>::list()

    /// Referencia al primer valor de la lista. \pre <code> ! empty() </code>
    /// \see ADH::list<T>::push_front()
    const_reference front() const { return this->next->m_val;  }
    /// Referencia al último valor de la lista.  \pre <code> ! empty() </code>
    /// \see ADH::list<T>::push_back()
    const_reference back()  const { return this->prev->m_val;  }

    /** Denota al primer valor de la lista. \see ADH::list<T>::front().

        \dontinclude test_STL_list.cpp
        \skipline    test::iterator()
        \until       }}
        \see         ADH::test_list<T>::test_iterator()
    */
    iterator begin() const { iterator p; p.m_p = this->next; return p; }
    /// Denota el valor que ya está fuera del contenedor. \see ADH::list<T>::begin().
    iterator end  () const { iterator p; p.m_p = static_cast< list_node<T>* >((void*) this); return p; }

    list& operator=(const list& LO);
    /// Sinónimo de <code>L = LO</code>. \see ADH::list<T>::operator=().
    void copy(const list& LO) { *this = LO; }
    void move(list& L);
    void swap(list& L);   // Intercambia <code>*this <==> L</code>

    void insert(iterator p, const value_type& v) {
        list_node<T> *q;
        q = new list_node<T> (v);
        q->next = p.m_p;
        q->prev = p.m_p->prev;
        q->prev->next = q;
        p.m_p->prev   = q;
    }
    void erase (iterator p) {
        p.m_p->prev->next = p.m_p->next;
        p.m_p->next->prev = p.m_p->prev;
        delete p.m_p;
    }
    void remove(const value_type& v);
    void splice( iterator p, list& L, iterator from );

    template <class E> friend bool operator == (const list<E>&, const list<E>&);
    template <class E> friend bool check_ok( const list<E> & L );

private: // Rep
    // Como esta clase deriva directamente de la clase "list_node_base"
    // contiene todos los campos de esa clase. O sea, el Rep contiene:
    // list_node<T> * prev;  ///< Puntero al último nodo de la lista
    // list_node<T> * next;  ///< Puntero al primer nodo de la lista
}; // list

/** Verifica la invariante de la clase \c "list".
    - Regresa \c "true" si \c "L" contiene un valor correcto.
    - Podría retornar \c "true" aún cuando \c "L" tenga su valor corrupto.
    - Podría no retornar si \c "L" tiene su valor corrupto.

    \par Rep Diagrama de la clase
    \code
<=====================================================>   <=============>
|  next prev                                          |   |  next prev  |
|    +-+-+     +-+-+     +-+-+     +-+-+     +-+-+    |   |    +-+-+    |
<===>|*|*|<===>|*|*|<===>|*|*|<===>|*|*|<===>|*|*|<===>   <===>|*|*|<===>
     +-+-+     +-+-+     +-+-+     +-+-+     +-+-+             +-+-+
     | 1 |     | 2 |     | 3 |     | 4 |       L                 L
     +---+     +---+     +---+     +---+       ^             Lista vacía
       ^       m_val                 ^        /|\
       |                             |         |
    L.front()                     L.back()   L.end()
   \endcode

    \code
  Diagrama de herencia        - Como tanto list<T> como list_node<T> derivan de
   +----------------+[]-next    list_node_base<T>, ambas clases contienen los
   | list_node_base |           campos "next" y "prev".
   +----------------+[]-prev
      /          \            - Por esto, la lista "*this" se ve como un nodo más
+------+    +-----------+     - Sin embargo, la lista no contiene el campo "m_val"
| list |    | list_node |       que sí aparece en los nodos list_node<T>.
+------+    +-----------+     - ¡Todo esto ahorra el campo "m_val" en la lista!
   \endcode

    \par Descripción en palabras
    - Una lista es una secuencia de nodos enlazados del primero al último.
    - En esta implementación la lista es doblemente enlazada.
    - El último nodo de la lista apunta al nodo cabeza, de manera que si
      se siguen los punteros \c "next" en una lista que se obtendrían esta
      secuencia valores: 1->2->3->4-> end() ->1->2->3 ...
    - El puntero hacia atrás del primer nodo de la lista apunta hacia el
      nodo cabeza de la lista,  de manera que si se siguen los punteros
      \c "prev" en una lista que se obtendrían esta secuencia valores:
      4->3->2->1-> end() ->4->3->2 ...
    - En lugar de crear un nodo cabeza, el truco que se usó aquí es
      poner los campos \c "next" y \c "prev" como los campos del Rep de
      la lista. Para hacerlo, se usó herencia, derivando de la clase
      \c list_node_base<>. Por eso el Rep de la lista es un nodo cabeza
      que sólo contiene los punteros de enlace.
    - La clase "nodo" está partida en 2 pedazos para que en el Rep de la
      lista no aparezca el campo "m_val". De esta manera se logran 2
      mejoras:
      - No aparece el campo \c "m_val" en el Rep de la \c list<T>.
      - No hace falta crear en memoria dinámica el nodo cabeza de la
        lista porque sus valores están almacenados directamente en el
        Rep de la \c list<T>.

    - Para que el valor de la lista sea correcto es necesario que
      cada uno de los valores almacenados en la lista sea correcto.
    - El campo "next" debiera llamarse "m_next", como lo manda la convención
      para nombrar los campos de una clase.
    - En este caso, se ha mantenido el nombre "next" sin el prefijo "m_" porque en la
      mayor parte de los libros de texto, el nombre de este campo es "next", de manera
      que tiene un valor mnemónico-pedagógico usar "next" en lugar de "m_next".
    - El campo \c "next" no se llama \c "m_next" porque en los libros
      de texto el nombre que aparece siempre es \c "next". Lo mismo
      ocurre con el campo \c "prev".

    \pre Obliga al programador cliente a implementar la función
          \c bool check_ok( const value_type & );
*/
template <class E>
bool check_ok( const list<E> & L ) {
    if ( ! (&L != 0) ) {
        return false; /// - Invariante: la lista no puede estar almacenada en una posición nula.
    }

    if ( !( (L.prev != 0) && (L.next != 0 ) ) ) {
        return false; /// - Invariante: los campos \c next y \c prev siempre deben ser no nulos, aún si la lista está vacía.
    }

    if ( L.prev == L.next ) {
        if ( L.next == static_cast< list_node<E>* >(& L) ) {
            return true; /// - Invariante: la lista vacía siempre se representa como el nodo enlazado hacia sí mismo
        }
        else {
            return false; /// - Invariante: si la lista está vacía tanto \c next como \c prev debe estar
                          ///   enlazados hacia el mismo nodo.
        }
    }

    list_node<E> * p = L.next;
    while ( p->next != static_cast< list_node<E>* >(& L) ) {
        p = p->next;
        if ( !( (p->next->prev == p) && (p->prev->next == p) ) ){
            return false; /// - Invariante: Cada nodo debe estar enlazado con su nodo siguiente y anterior.
        }
        if ( ! check_ok( p->m_val ) ) {
            return false; /// - Invariante: El valor \c "m_val" almacenado en un nodo de la lista
                          ///   siempre debe ser un valor correcto.
        }
        p = p->next;
    }
    return true;
}

#undef NO_COMPILA
#ifdef NO_COMPILA
template <class T>
bool list<T>::iterator ok( ) const {
    if (m_p == 0) {
        return true; // "I.m_p" es un puntero nulo
    }
    list<T> TempL; TempL.m_first = m_p; // simula una lista a partir de "I.m_p"
    bool ok = check_ok( TempL );
    TempL.m_first = 0; // evita que el destructor de "TempL" destruya el resto
    if (! ok) {
        return false; // lista mala ==> iterador malo
    }
    return true;
}
#endif // NO_COMPILA

/** Agrega una copia del valor \c "v" al principio de la lista \c "*this".
    \par Complejidad
    - O ( \c 1 )

    \dontinclude test_STL_list.cpp
    \skipline    test::push_front_back()
    \until       }}
    \see         ADH::test_list<T>::test_push_front_back()
*/
template <class T>
inline void list<T>::push_front( const T& v ) {
//     void list<T>::push_front( const list<T>::value_type& ); // NO COMPILA
    insert( begin(), v );
} // list<T>::push_front()

/** Agrega una copia del valor \c "v" al final de la lista \c "*this".
    \par Complejidad
    - O ( \c 1 )
    \see         ADH::list<T>::push_front()
*/
template <class T>
inline void list<T>::push_back( const T& v ) {
    insert( end(), v );
} // list<T>::push_back()

/** Elimina el valor del principio de la lista.
    \pre
    \c !empty()

    \dontinclude test_STL_list.cpp
    \skipline    test::pop_front_back()
    \until       }}
    \see         ADH::test_list<T>::test_pop_front_back()
*/
template <class T>
inline void list<T>::pop_front() {
    erase( begin() );
} //  list<T>::pop_front()

/** Elimina el valor del final de la lista.
    \pre
    \c !empty()

    \par Complejidad
    - O ( \c 1 )

    \see         ADH::list<T>::pop_front()
*/
template <class T>
inline void list<T>::pop_back() {
    erase( --end() ); // erase( end()-- ); NO funciona
/*  NOTA
    Aunque en esta implementación sí ocurre que el "nodo"
    previo a "end()" es el último nodo de la lista, en
    general no se puede asegurar que sea cierto:
        assert( C.end() == ((C.end()--) ++) );
        // "C" es un contenedor STL.
*/
} //  list<T>::pop_back()

// list<T>::size_type list<T>::size( ) const { // NO COMPILA

template <class T>
unsigned list<T>::size( ) const {
    unsigned n = 0;
    iterator p = begin();
    while (p != end()) {
        n++;
        p++;
    }
    return n;
}

/** Elimina los valores del contenedor y lo deja vacío.
    \dontinclude test_STL_list.cpp
    \skipline    test::clear()
    \until       }}
    \see         ADH::test_list<T>::test_clear()
*/
template <class T>
void list<T>::clear() {
    #if 0
        while ( ! empty() ) { // No se le meta al Rep
            pop_front();      // - es "menos" eficiente
        }
    #endif

    #if 1
         // SI se le mete al Rep
        while ( this->next != static_cast< list_node<T>* >((void*) this) ) {
            list_node<T> *p = this->next;  // lo sostiene
            this->next = this->next->next; // avanza
            delete p;                      // lo mata
        }
        // Reconecta circular al puntero previo del Rep de list<T>
        this->prev = static_cast< list_node<T>* >((void*) this);
    #endif
} // list<T>::clear()


/** Copia ==> <code>L = LO</code>.
    \dontinclude test_STL_list.cpp
    \skipline    test::assign()
    \until       }}
    \see         ADH::test_list<T>::test_assign()
*/
template <class T>
list<T>& list<T>::operator=(const list<T>& LO) {
    if (&LO == this) {
        return *this; // evita autocopia
    }

    // borra todo
    clear();

    // copia
    iterator p = LO.begin();
    iterator L0_end = LO.end();
    while (p != L0_end) {
        push_back( *p );
        ++p;
    }
    return *this;
} // list<T>::operator=()

/// Copia el valor de \c Lsrc sobre \c Ldst.
/// - El valor anterior de \c Ldst se pierde.
template <class T>
void copy( list<T>& Ldst, const list<T>& Lsrc ) {
    if ( &Ldst == &Lsrc ) {
        return; // evita autocopia
    }

    // copia sobre los valores actuales de Ldst
    typename list<T>::iterator pDst = Ldst.begin(); typename list<T>::iterator endDst = Ldst.end();
    typename list<T>::iterator pSrc = Lsrc.begin(); typename list<T>::iterator endSrc = Lsrc.end();
    while ( (pSrc != endSrc) && (pDst != endDst) ) {
        *pDst  = *pSrc; // reutiliza los valores ya almacenados en Ldst
        ++pDst; ++pSrc;
    }
    if ( (pSrc == endSrc) && (pDst == endDst) ) {
        return; // ya no hay nada que copiar pues ambas listas son del mismo largo
    }
    else if (pDst == endDst) { // Ldst es una lista más corta
        while (pSrc != endSrc) {
            Ldst.push_back( *pSrc );
            pSrc++;
        }
    }
    else {
        assert( (pSrc == endSrc) );
        // list<T> Ltemp; Ltemp.splice( Ltemp.end(), Lsrc, pSrc, endSrc );
        typename list<T>::iterator pTmp;
        while (pDst != endDst) {
            pTmp = pDst;
            ++pTmp;       // avanza pTmp antes de
            Ldst.erase(pDst);  // matar a pDst
            pDst = pTmp;
        }
    }
}

/** Intercambia <code>*this <==> L</code>

    \dontinclude test_STL_list.cpp
    \skipline    test::move_swap()
    \until       }}
    \see         ADH::test_list<T>::test_move_swap()
*/
template <class T>
void list<T>::swap(list<T>& L) {
#if 1
    list tmp; // menos eficiente pero más claro
    tmp.move( L );       // tmp   <== L
    L.move( *this );     // L     <== *this
    this->move( tmp );   // *this <== tmp

#else
    assert( true && false && "list<T>::swap() IMPLEMENTACION INCORRECTA" );
    if (this->next==this->prev && L.next==L.prev) {
        return; // ambas listas están vacías
    }
    else if (this->next==this->prev && L.next != L.prev) { // sólo *this está vacía
        list_node<T> * p = end().m_p->next;
        list_node<T> * q = L.end().m_p;
        this->next = L.next;
        this->prev = L.prev;
        this->next->prev = p;
        this->prev->next = p;
        L.next = L.prev = q;
    }
    else if (this->next!=this->prev && L.next == L.prev) { // sólo L está vacía
        list_node<T> * p = L.end().m_p->next;
        L.next = this->next;
        L.prev = this->prev;
        L.next->prev = p;
        L.prev->next = p;
        this->next = this->prev = static_cast< list_node<T>* >((void*) this);
    }
    else if (this->next != this->prev && L.next != L.prev) {
        list_node<T> * tmp = L.next;
        list_node<T> * final = end().m_p;
        list_node<T> * finalL = end().m_p;
        L.next = this->next;
        this->next = tmp;
        L.next->prev = finalL;
        this->next->prev = final;

        tmp = L.prev;
        L.prev = this->prev;
        this->prev = tmp;
        L.prev->next = finalL;
        this->prev->next = final;
    }
#endif
}

/// Traslada el valor de \c "LO" a \c "*this"
template <class T>
void list<T>::move(list<T>& LO) {
    assert( true && "list<T>::move() NO IMPLEMENTADO" );
    if (&LO == this) {
        return; // evita autocopia
    }

    clear(); // borra todos lo valores de la lista actual
    if (LO.next == static_cast< list_node<T>* >( (void*)(& LO) )) {
        return; // se va porque LO está vacía
    }

#if 1
    // "end_this" es "this" y apunta al "cabús" de la lista
    list_node<T> * end_this = static_cast< list_node<T>* >((void*) this);
    end_this->next = LO.next;
    end_this->prev = LO.prev;
    end_this->next->prev = end_this;
    end_this->prev->next = end_this;
    LO.next = LO.prev = static_cast< list_node<T>* >( (void*)(& LO) );
#else
    list_node<T> * p = end().m_p->next; // le roba a LO todos sus valores
    list_node<T> * q = LO.end().m_p;
    this->next = LO.next;
    this->prev = LO.prev;
    this->next->prev = p;
    this->prev->next = p;
    LO.next = LO.prev = q;
#endif
}
/** \fn template <class T> inline  void ADH::list< T >::insert(iterator p, const value_type &v)

    \brief Agrega el valor \c "v" al contenedor.
    - El valor agregado queda antes de la posición \c "p" en el contenedor.
    - Si <code>p==this->end()</code> el valor queda al final de la lista.

    \par Complejidad
    - O ( \c 1 )
*/

/** \fn template <class T> inline void ADH::list<T>::erase(iterator p)

    \brief Elimina el valor \c "*p" del contenedor.
    - El valor agregado queda antes de la posición \c "p" en el contenedor.
    - Si <code>p==this->end()</code> el valor queda al final de la lista.

    \par Complejidad
    - O ( \c 1 )
*/

/// Elimina del contenedor cada uno de los valores iguales a \c "v"
template <class T>
void list<T>::remove(const T& v) {
    assert( true && "list<T>::remove() NO IMPLEMENTADO" );
    if ( empty() ) {
        return;
    }
    typename list<T>::iterator i = begin();
    typename list<T>::iterator q;
    while (i != end()) {
        if (*i == v) {
            q = i;    // como lo encontró
            ++i;
            erase(q); // lo borra
        }
        else {
            i++;      // se lo brinca
        }
    } // list<T>::remove()
}

/** \fn template <class T> inline void list<T>::splice( iterator p, list& L, iterator from )

    \brief Traslada el valor \c "from" de la lista \c "L" y lo coloca antes de \c "p".
    - El valor \c "from" deja de ser parte de \c "L" y pasa a estar almacenado
      dentro de \c "*this".
    - Todos los iteradores que denotan \c "from" quedan con su valor
      invalidado.

    \pre
    - El valor \c "p" debe denotar una posición en \c "*this" o \c "end()".
    - El valor \c "from" debe denotar una posición en \c "L".

    \remark
    - Al trasladar el valor se evita copiarlo.

    \par Complejidad
    - O ( \c size() )
*/

template <class T>
void list<T>::splice( iterator p, list& L, iterator from ) {
    assert( false && "list<T>::splice() NO IMPLEMENTADO" );
    if ( L.empty() || L.empty() ) {
        return ;
    } else {
        from.m_p->prev = from.m_p->next;
        from.m_p->next->prev = from.m_p->prev;

        p.m_p->prev->next = from.m_p;
        from.m_p->prev = p.m_p->prev;
        from.m_p->next = p.m_p->next;
        p.m_p->next->prev = from.m_p;
    }
}

/// ¿<code>L == LL</code>?
template <class E>
bool operator == (const list<E>& L, const list<E>& LL) {
    if ( L.empty() && LL.empty() ) {
        return true;
    }

    if ( L.empty() || LL.empty() ) {
        return false;
    }

    typename list<E>::iterator p =  L.begin();
    typename list<E>::iterator q = LL.begin();
    do {
        if ( *p != *q ) {
            return false;
        }
        ++p;
        ++q;
    } while ( p != L.end() && q != LL.end() );

    return  ( p == L.end() && q == LL.end() );
}

/// ¿<code>L != LL</code>?
template <class E>
inline bool operator != (const list<E>& L, const list<E>& LL) {
    return ! (L==LL);
}

/** Retorna un iterador que denota al último valor de a lista \c "L".
    - Retorna \c L.end() si la lista está vacía.
    - Es ineficiente porque ejecuta en tiempo O ( <code>L.size()</code> ).
    - El argumento \c "L" no es \c "const" porque el iterador retornado
      no es un \c "const".

    \dontinclude test_STL_list.cpp
    \skipline    test::last()
    \until       }}
    \see         ADH::test_list<T>::test_last()
*/
template <class T>
typename list<T>::iterator last( list<T> & L ) {
    typename list<T>::iterator p,q;
    q = L.end();
    p = L.begin();
    while ( p != L.end() ) {
        q = p; // "q" está "antes" de "p"
        ++p;
    } // es ineficiente porque NO se le mete al "Rep"
    return q;
}

/** Graba el valor de \c "L" en el flujo \c "COUT".
    - En particular, este es el operador que se invoca
      cuando se usa, por ejemplo, este tipo de instrucción:
      \code
      COUT << L << LO;
      \endcode
    - Los valores quedan separados por comas.
*/
template <class T>
std::ostream& operator<< (std::ostream &COUT, const ADH::list<T>& L) {
#if 1
{
    typename list<T>::iterator p;     // recorre la lista
    typename list<T>::iterator endL;  // después de la lista

    COUT << "(";
    {
        p    = L.begin();  // p.operator= ( Lista.begin() );
        endL = L.end();

        for ( ; p != endL; ++p ) {
            COUT << ( *p );
            if (p != last( L ) ) {
                COUT << ",";
            }
        }
    }
    COUT << ")";
}
#endif

#if 0
{
    COUT << "(";
    const list_node<T> *p = L.next;
    while ( p != static_cast< const list_node<T>* >( (void*)&L ) ) {
        COUT << p ->m_val;
        if ( p->next != static_cast< const list_node<T>* >( (void*)&L ) ) {
           COUT << ",";  // no es el último node de la lista
        }
        p = p->next;
    }
    COUT << ")";
}
#endif

#if 0
{
    if ( L.empty() ) {
        COUT << "()";
    }
    else {
        list<T> LO;
        LO = L; // Hace una copia
        COUT << "(";
        while (! LO.empty()) {
            typename list<T>::value_type val = *LO.front();
            COUT << val;
            if ( LO.size() > 1 ) {
                COUT << ',';
            }
            LO.pop_front();
        }
        COUT << ")";
    }
}
#endif

#if 0
{
    COUT << "(";
    for (list<T> LO = L; ! LO.empty(); LO.pop_front() ) {
        typename list<T>::value_type val = LO.front();
        COUT << val;
        if ( LO.size() > 1 ) {
            COUT << ',';
        }
    }
    COUT << ")";
}
#endif

    return COUT;
}  // operator <<

/// Lee del flujo de texto \c "CIN" el valor de \c "L".
/// - Se presume que el valor fue grabado con \c operator<<().
///   - "()"
///   - "(1 2 3)"
///   - "(1 2 3 77 888 999)"
template <class T>
std::istream& operator >> (std::istream &CIN, ADH::list<T>& L) {
    L.clear(); // borra todo el valor anterior

    char ch;
    do {
        ch = CIN.get(); // lee el '(' de la pura izquierda
    } while ( ch != '(' );
    assert( '(' == ch );
    typename list<T>::value_type v; // temporal para leer cada valor de la lista

    for (;;) {
        ch = CIN.peek(); // lee el delimitador o el ')'
        if (ch == ')') {
            ch = CIN.get(); // lee el ')' del final
            break;
        }
        else {
            CIN >> v;
            L.push_back( v );
        }
    }
    return CIN;
}  // operator >>

}   // namespace ADH

#endif // STL_list_h

/*
    /---------<-----------------<-----------------<-----------\
    |                                                         |
    |  /------>-------\  /------>-------\  /------>-------\   |
    |  |              |  |              |  |              |   |
    v  |              v  |              v  |              v   /
+-->+==/+=====+   /-->+==/+=====+   /-->+==/+=====+   /-->+==/+
|   | * |     |   |   | * |     |   |   | * |     |   |   | * | next
|   +---+ [1] |   |   +---+ [2] |   |   +---+ [3] |   |   +---+
|   | * |     |   |   | * |     |   |   | * |     |   |   | * | prev
|   +=|=+=====+   |   +=|=+=====+   |   +=|=+=====+   |   +=|=+
|     |  m_val    |     |           |     |           |     |
+-----|-------<---|----/            \-----|-------<---|-----/
      |           |                       |           |
      |           \-----------------------/           |
      \------->----------------->----------------->---/
                                              /\
                                              ||
                                         last_node(L)
*/

// EOF: lab17.h