Site hosted by Angelfire.com: Build your free website today!

Volver a Principal

 

 

USE_list.cpp

 

#include <iostream>

#include "ADH_port.h"

 

#include "ADH_list.h"

 

USING_namespace( ADH ); // using namespace ADH;

USING_namespace( std ); // using namespace std;

 

/// Graba en \c "cout" el contenido de \c "L"

inline void printList( const list& L ) {

    cout << L <<endl;

}

 

/// Función principal en la que empieza la ejecución del programa

int main() {

    int a[] = { 2, 6, 4, 8 };

    const int SIZE = sizeof(a) / sizeof(a[0]);

    list LV, LO;

 

    printList( LV );

 

    LV.push_front( 1 );

    printList( LV );

    cout << ( * LV.last() );

 

    LV.push_front( 2 );

    printList( LV );

    cout << ( * LV.last() );

 

    LV.push_front( 5 );

    printList( LV );

    cout << ( * LV.last() );

 

    LV.push_back( 4 );     printList( LV );

    cout << ( * LV.last() );

 

    LV.push_back( 3 );     printList( LV );

    cout << ( * LV.last() );

 

 

    cout << "LV contains: ";

    printList( LV );

 

    (* LV.last() ) = 18;

    printList( LV );

 

//  LV.sort();

    cout << "\nLV after sorting contains: ";

    printList( LV );

 

//  LO.insert( LO.begin(), a, a + SIZE );

    cout << "\nLO contains: ";

    printList( LO );

 

//  LV.sort();

    cout << "\nLV contains: ";

 

    LV.pop_front();

    LV.pop_back();   // all sequence containers

    cout << "\nAfter pop_front and pop_back LV contains:\n";

    printList( LV );

 

    // method swap is available in all containers

    LV.swap( LO );

    cout << "\nAfter swap:\n   LV contains: ";

    printList( LV );

    cout << "\n   LO contains: ";

    printList( LO );

 

    LO.remove( 4 );

    cout << "\nAfter remove( 4 ) LO contains: ";

    printList( LO );

    cout << endl;

    return 0;

}

 

 

 

ADH_list.h

 

 

#ifndef ADH_list_h

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

 

#include "ADH_port.h"

#include <iostream>

#include "Tdef.h" // truco para usar pseudo-plantillas

 

OPEN_namespace( ADH ) // namespace ADH {

 

class list {

    public: class node;

    public:  class iterator;

    friend   class iterator;

 

public:

    /// Nodos de la clase \c "list"

    class node {

        friend class list;

        friend class iterator;

 

        node(const T& v) : m_val(v) { /* next = 0; */ } ///< Constructor para \c "v"

 

    private:

        friend std::ostream& operator<< (std::ostream &, const list& );

        friend bool check_ok( const list & L );

        friend node * prev_node( const list& L, const node * p );

        friend node * last_node( const list& L);

    private:

        T     m_val;  ///< Valor almacenado en el nodo

        node * next; ///< Puntero al siguiente nodo

    };  // node

 

public:

    class iterator {

        friend class list;

    public:

        iterator() : m_p(0) {

        /// Constructor de copia

        iterator( const iterator& o)

             { m_p = o.m_p;}  // copia el Rep directo

        iterator& operator=( const iterator& ); ///< Copia

 

        friend bool operator == ( const iterator&, const iterator& );

        friend bool operator != ( const iterator&, const iterator& );

 

        iterator operator++()

            { m_p = m_p -> next; return *this;

        iterator operator++(int)

            { iterator q = (*this); m_p = m_p -> next; return q; }

 

        T& operator*()  { return   m_p -> m_val ; }

        T* operator->() { return &(m_p -> m_val); }

    private:

        node * m_p;   ///< Puntero al nodo de \c "list"

    }; // list::iterator

 

public:

    list() : m_first(0) { } ///< Constructor de vector

    list(const list& L) : m_first(0) { *this = L; } ///< Constructor de copia

    ~list() { clear(); } ///< Destructor

    void clear(); ///< Elimina los valores del contenedor y lo deja vacío

 

    void push_front( const T& v );

    void push_back(  const T& v );

 

    void pop_front();

    void pop_back();

 

    bool empty() const;      ///< Retorna "true" si la lista está vacía

    iterator first() const;  ///< Denota al primer valor de la lista

    iterator last()  const;  ///< Denota al último valor de la lista

 

    /// Denota al primer valor de la lista

    iterator begin() const { iterator p; p.m_p = m_first; return p; }

    /// Denota el valor que ya está fuera del contenedor

    iterator end  () const { iterator p; p.m_p = 0;      return p; }

 

    list& operator=(const list& LO); ///< Copia ==> <code>L = LO</code>

    void move(list& L);

    void swap(list& L);   // Intercambia <code>*this <==> L</code>

 

    void insert(iterator position, const T& v);

    void remove(const T& v);

 

    friend std::ostream& operator<< (std::ostream &, const list& );

    friend std::istream& operator>> (std::istream &,       list& );

 

    friend bool check_ok( const list& );

               

private:

    friend node * prev_node( const list& L, const node * p );

    friend node * last_node( const list& L);

 

private:

    node * m_first;  ///< Puntero al primer nodo de la lista

}; // list

 

inline bool list::empty() const {

    return (m_first == 0);

}

 

/// Primer valor de la lista

inline list::iterator list::first() const {

    list::iterator p;

    p.m_p = m_first;

    return p;

} // list::first()

 

/// Denota el último valor de la lista

inline list::iterator list::last() const {

    list::iterator p;

    p.m_p = ( m_first == 0 ? 0 : last_node( *this ) );

    return p;

} // list::last()

 

/// Copia

inline list::iterator& list::iterator::operator= (

    const list::iterator& o

) {

    m_p = o.m_p; // copia el Rep directo

    return *this;

}

 

/// ¿ <code>p == q</code> ?

inline bool operator == (

    const list::iterator& p,

    const list::iterator& q

) {

    return p.m_p==q.m_p;

}

/// ¿ <code>p != q</code> ?

inline bool operator != (

    const list::iterator& p,

    const list::iterator& q

) {

    return !(p==q); // return operator == (p, q);

}

 

#if 0

        iterator( const iterator& o) // ; // constructor de copia

             { m_p = o.m_p;}  // copia el Rep directo

 

inline list::iterator( const list::iterator& o ) {

//  constructor de copia

    m_p = o.m_p; // copia el Rep directo

}

#endif

 

CLOSE_namespace( ADH ) // } // namespace ADH

 

#endif

 

 

 

ADH_list.cpp

 

 

#include "ADH_list.h"

 

OPEN_namespace( ADH ) // namespace ADH {

 

bool check_ok( const list & L ) {

    if ( L.m_first == 0 ) {

        return true; /// - Invariante: la lista nula siempre tiene un valor correcto

    }

 

    list::node * p = L.m_first;

    while ( p != 0 ) {

        if ( ! check_ok( p->m_val ) ) {

            return false; /// - Invariante: El valor \c "m_val" almacenado en un nodo de la lista no contiene un valor correcto

        }

        p = p->next;

    }

    return true;

}

 

/// Agrega una copia del valor "v" al principio de la lista "*this"

void list::push_front( const T& v ) {

    if (m_first == 0) {

        this->m_first = new node(v);

        m_first->next = 0;  // (*m_first).next = 0;

    }

    else {

        node *p;

        p = new node(v);

        p->next = m_first;  // (*p).next = (*this).m_first;

        m_first = p; // this->m_first = p;

    }

} // list::push_front()

 

void list::push_back(  const T& v ) {

    if ( empty() ) {

        m_first = new node(v);

        m_first->next = 0;  // (*m_first).next = 0;

    }

    else {

        node * p = last_node( *this );

        p->next = new node(v);

        p->next->next = 0;

    }

} // list::push_back()

 

void list::pop_front() {

    #if defined(NDEBUG)

    //  #define NDEBUG ==> Activo para obtener al versión de producción

        if ( empty() ) {

            throw (BOOOM!!!);

        }

    #endif

 

    node *p = m_first;    // recuerda adónde está el siguiente node

    m_first = m_first->next;

 

    delete p;

} //  list::pop_front()

 

void list::pop_back() {

    #if defined(NDEBUG)

        if ( empty() ) {

            throw (BOOOM!!!);

        }

    #endif

 

    // avanza hasta el final

    node *p = m_first;

    node *q = 0;    // valor anterior de "p"

    while (p->next != 0) {

        q = p;

        p = p->next;

    }

 

    if (q == 0)

        delete m_first; // mata al node

        m_first = 0;    // marca la lista como vacía

    }

    else {

       q->next = 0;

       delete p;

    }

} //  list::pop_back()

 

void list::clear() {

    #if 0

        while ( ! empty() ) { // No se le meta al Rep

            pop_front();      // - es "menos" eficiente

        }

    #endif

 

    #if 1

        while ( ! empty() ) {  // SI se le meta al Rep

            node *p = m_first;     // a la larga vale la pena que

            m_first = m_first->next;  // pop_front() sea inline...

            delete p;

        }

    #endif

} // list::clear()

 

list::node * last_node( const list& L ) {

            list::node *p = L.m_first;

    while (p->next != 0) {

        p = p->next;

    }

            return p;

} // last_node()

 

list::node * prev_node( const list& L, const list::node * p ) {

    if (p == L.m_first) {

        return 0;

    }

 

    list::node* q;

    q  = L.m_first; // busca desde el principio de la lista

    while (q != 0) {

        if ( p == q->next ) {

            return q;

        }

        q = q->next;

    }

    return 0;

} // prev_node()

 

 

 

list& list::operator=(const list& LO) {

    if (&LO == this) {

        return *this; // evita autocopia

    }

 

    // borra todo

    while ( ! empty() ) {

        pop_front();

    }

 

    // copia

    node *p = LO.m_first;

    while (p != 0) {

        push_back(p->m_val);

        p = p->next;

    }

    return *this;

} // list::operator=()

 

void list::swap(list& L) {

    node *tmp = L.m_first;

    L.m_first = m_first;

    m_first = tmp;

}

 

void list::move(list& LO) {

    if (&LO == this) {

        return; // evita autocopia

    }

 

    // borra todo

    while ( ! empty() ) {

        pop_front();

    }

 

    m_first    = LO.m_first;    // le roba a LO todos sus valores

    LO.m_first = 0;

}

 

#include <assert.h>

 

void list::insert(list::iterator p, const T& v) {

//    assert( false && "list::insert() ==> NO IMPLEMENTADO" );

 

    node* q = new node(v);

    if ( m_first==0 ) { // push_front(v)

        q->next = 0;

        m_first = q;

    }

    else if ( m_first==p.m_p ) { // push_front(v)

        q->next = m_first;

        m_first = q;

    }

    else if ( p.m_p==0 ) { // push_back(v)

        node *last = last_node( *this );

        q->next    = 0;

        last->next = q;

    }

    else {

        node *prev = prev_node(*this, p.m_p);

        q->next = prev->next;

        prev->next = q;

    }

} // list::insert()

 

#include <assert.h>

 

/// Elimina cada uno de los valores iguales a "v"

void list::remove(const T& v) {

    if (m_first == 0) {      //¿Está vacía?

                        return;

            }

            node* p = m_first;

            while (p->next != 0) {

                        if (m_first->m_val == v) {  // ¿"v" es el primer valor de la lista?

                                   m_first = m_first->next;

                                   p = p->next;

                        } else if (p->next->m_val == v) {

                                   p->next = p->next->next;

                                   p = p->next;

                                   if (p == 0) {

                                       return;

                                   }

                        } else {

                                   p = p->next;

                        }

                       

            }

 

} // list::remove()

 

std::ostream& operator<< (std::ostream &COUT, const list& L) {

#if 1

    COUT << "(";

    list::node *p = L.m_first;

    while (p != 0) {

        COUT << p ->m_val;

        if (! (p->next == 0) ) { // ¿último node de la lista?

           COUT << ", ";

        }

        p = p->next;

    }

    COUT << ")";

#endif

 

#if 0

    list::iterator p;     // recorre la lista

    list::iterator endL;  // después de la lista

 

    COUT << "(";

 

    p    = L.begin();  // p.operator= ( Lista.begin() );

    endL = L.end();    // generalmente NULL==0

 

    for ( ; p != endL; ++p) {

        COUT << ( *p );

        if (p != L.last() ) {

            COUT << ", ";

        }

    }

 

    COUT << ")";

#endif

 

#if 0

    COUT << "(";

    list::node *p = L.m_first;

    while (p != 0) {

        COUT << p ->m_val;

        if (! (p->next == 0) ) { // ¿último node de la lista?

           COUT << ", ";

        }

        p = p->next;

    }

    COUT << ")";

#endif

 

#if 0

    if ( L.empty() ) {

        COUT << "()";

    }

    else {

        list LO;

        LO = L; // Hace una copia

        COUT << "(";

        while (! LO.empty()) {

            T val = *LO.first();

            COUT << "  " << val;

            LO.pop_front();

        }

        COUT << ")";

    }

#endif

 

#if 0

    COUT << "(";

    for (list LO = L; ! LO.empty(); LO.pop_front() ) {

        T val = *LO.first();

        COUT << "  " << val;

    }

    COUT << ")";

#endif

 

    return COUT;

}  // operator <<

 

#include <assert.h>

std::istream& operator >> (std::istream &CIN, list& r) {

    assert( false && "operator >> (istream &, list& r) ==>NO IMPLEMENTADO");

 

    return CIN;

}  // operator >>

 

CLOSE_namespace( ADH )

 

 

 

 

ADH_port.h

 

#ifndef ADH_port_h

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

 

// Documentados acá para Doxygen

#undef  CLOSE_namespace

#undef  USING_namespace

#undef  OPEN_namespace

 

/// Abre namespace   \c "N"

#define OPEN_namespace(N) namespace N {

 

/// Cierra namespace \c "N"

#define CLOSE_namespace(N) }

 

/// Usa namespace    \c "N"

#define USING_namespace(N) using namespace N

 

// Los anula para luego definirlos dentro del #ifdef correcto

#undef  CLOSE_namespace

#undef  USING_namespace

#undef  OPEN_namespace

 

#ifdef DOXYGEN_COMMENT   // Documentados acá para Doxygen

    /// Definido por la biblioteca C++ estándar

    namespace std {} // Está acá para que Doxygen lo documente

    /// ADH son las siglas de \c adolfo@di-mare.com

    namespace ADH {} // Está acá para que Doxygen lo documente

    #define INCLUDE_fstream   Truco para "include <fstream>"   portable

    #define INCLUDE_io        Truco para "include <io>"        portable

    #define INCLUDE_iomanip   Truco para "include <iomanip>"   portable

    #define INCLUDE_iostream  Truco para "include <iostream>"  portable

    #define INCLUDE_list      Truco para "include <list>"      portable

    #define INCLUDE_map       Truco para "include <map>"       portable

    #define INCLUDE_stdexcept Truco para "include <stdexcept>" portable

    #define INCLUDE_vector    Truco para "include <vector>"    portable

#endif

 

// Borland C++

#ifdef __BORLANDC__               ///< Definida para Borland C++

    #if (__BORLANDC__ <= 0x0410)  //   Identifica a BC++ v3.1 y anterior

        #undef false

        #undef true

        #undef bool

 

        // Declara el tipo "bool" porque BC++ v3.1 NO tiene "bool"

        typedef int bool;

        const int false = 0;

        const int true  = ! false; // BC++ v3.1 NO tiene "bool"

 

        class istream; class ostream;

 

        #define using              // BC++ v3.1 NO tiene "namespace"

        #define namespace

        #define std

        #define ADH

 

        #define OPEN_namespace(N)  // BC++ v3.1 NO tiene "namespace"

        #define CLOSE_namespace(N)

        #define USING_namespace(N)

 

        #ifdef INCLUDE_fstream

            #include  <fstream.h>

        #endif

        #ifdef INCLUDE_io

            #include  <io.h>

        #endif

        #ifdef INCLUDE_iomanip

            #include  <iomanip.h>

        #endif

        #ifdef INCLUDE_iostream

            #include  <iostream.h>

        #endif

        #ifdef INCLUDE_list

            #include  <list.h>

        #endif

        #ifdef INCLUDE_map

            #include  <map.h>

        #endif

        #ifdef INCLUDE_stdexcept

            #include  <stdexcept.h>

        #endif

        #ifdef INCLUDE_vector

            #include  <vector.h>

        #endif

    #endif

 

    #if (__BORLANDC__ >  0x0410)  // Versiones posteriores a BC++ v3.1

        #define OPEN_namespace(N) namespace N {

        #define CLOSE_namespace(N) }

        #define USING_namespace(N) using namespace N

        #error Ajuste ADH_port.h para compìlar con versiones nuevas de BC++

    #endif

#endif

 

// Microsoft C++ (Visual Studio)

#ifdef _MSC_VER                   ///< Definida para Micrsoft C++

    // namespace

    #define OPEN_namespace(N) namespace N {

    #define CLOSE_namespace(N) }

    #define USING_namespace(N) using namespace N

 

    #if (_MSC_VER >= 1300)        //   Identifica a VC++ .net

        // Definido por la biblioteca C++ estándar

        namespace std {} // Está acá para que Doxygen lo documente

        using namespace std;

 

        #ifdef INCLUDE_fstream

            #include  <fstream>

        #endif

        #ifdef INCLUDE_io

            #include  <io>

        #endif

        #ifdef INCLUDE_iomanip

            #include  <iomanip>

        #endif

        #ifdef INCLUDE_iostream

            #include  <iostream>

        #endif

        #ifdef INCLUDE_list

            #include  <list>

        #endif

        #ifdef INCLUDE_map

            #include  <map>

        #endif

        #ifdef INCLUDE_stdexcept

            #include  <stdexcept>

        #endif

        #ifdef INCLUDE_vector

            #include  <vector>

        #endif

    #endif

 

    #if (_MSC_VER < 1300)         //   Identifica a VC++ v6 y anterior

        namespace std {} // Está acá para que Doxygen lo documente

        // Antes de MSC++ .NET hay que usar <.h>

        #ifdef INCLUDE_fstream

            #include  <fstream.h>

        #endif

        #ifdef INCLUDE_io

            #include  <io.h>

        #endif

        #ifdef INCLUDE_iomanip

            #include  <iomanip.h>

        #endif

        #ifdef INCLUDE_iostream

            #include  <iostream.h>

        #endif

        #ifdef INCLUDE_list

            #include  <list.h>

        #endif

        #ifdef INCLUDE_map

            #include  <map.h>

        #endif

        #ifdef INCLUDE_stdexcept

            #include  <stdexcept.h>

        #endif

        #ifdef INCLUDE_vector

            #include  <vector.h>

        #endif

    #endif

#endif

 

#endif

 

 

Tdef.h

 

#ifndef _Tdef_h

#define _Tdef_h

 

typedef    long    T;         

 

OPEN_namespace( ADH )

 

inline bool check_ok( const T ) {

    return true;

}

 

CLOSE_namespace( ADH )

 

#endif

 

 

Volver a Principal