HerenciaOrdenada.cpp

Ir a la documentación de este archivo.

// HerenciaOrdenada.cpp (c) 2005 [email protected]

/** \file  HerenciaOrdenada.cpp
    \brief Ejemplo de uso de funciones virtuales usando algoritmos de ordenamiento.

    \author Alejandro Di Mare <[email protected]>
    \author Adolfo Di Mare <[email protected]>
    \date   2005
*/

#define  INCLUDE_iostream
#include "conio.h"
#include "ADH_port.h"  // Biblioteca de compatibilidad BC++ v3.1 && MS C++

#include <cstdlib>
#include <ctime>
#include "rational.h"
USING_namespace(ADH);

/// Clase abstracta cuyos hijos son contenedores que pueden ser ordenados.
/// - Tanto la \c "Lista_Ordenable" como el \c "Vector_Ordenable" son sus clases derivadas
class Contenedor_Ordenable {
protected:
    /// Cantidad de valores almacenados en el \c "Contenedor_Ordenable"
    int m_cantidad_de_elementos;

public:
    typedef rational value_type; ///< Tipo de valor almacenado en el contenedor

    Contenedor_Ordenable(unsigned N); ///< Constructor
    virtual ~Contenedor_Ordenable(); ///< Destructor

    /// Intercambia los valores de los elementos que están
    /// en las posiciones [i] <=> [j].
    virtual void Intercambie(int i, int j) = 0;

    /// Compara los elementos en las dos posiciones \c "i" && \c "j" del contenedor.
    /// - Retorna \c "true" cuando el primero es menor que el segundo.
    /// - Retorna \c "false" cuando el primero es mayor o igual que el segundo.
    ///   \pre <code>(i < Dimension()) && (j < Dimension())</code>
    virtual bool Es_Menor(int, int) const = 0;

        /// Muestra el i-ésimo término del contenedor \c V[i]
    virtual value_type& operator[](int) = 0;

    /// Devuelve la cantidad de valores almacenados en el \c "Contenedor_Ordenable".
    unsigned Dimension() const { return m_cantidad_de_elementos; }

    /// Graba en \c "cout" todos los valores almacenados en el contendor.
    /// - Los graba en el orden en el que se encuentran almacenados.
    virtual void ImprimaSe() const = 0;

    /// Nombre del contenedor
    virtual const char* Nombre() const = 0;
};


/// Lista ordenable simple, compuesta de nodos, que almacena números enteros.
/// - Este \c "Contenedor_Ordenable" es una lista de enteros de tamaño
///   \c "Contenedor_Ordenable::_cantidad_de_elementos".
class Lista_Ordenable : public Contenedor_Ordenable {

private:
    /// Nodos de la \c "Lista_Ordenable"
    class Nodo {
    public:
        /// Construye un nuevo \c "Nodo" cuyo valor almacenado es \c "v"
        Nodo(value_type v);
        ~Nodo(); ///< Destructor

        Nodo *     next;  ///< Puntero al próximo nodo
        value_type m_val; ///< Valor entero almacenado en el nodo
        };

    /// Agrega una copia de \c "v" al prinicipio de \c "*this"
    void Agregar_Valor(value_type v);

public:
    /// Constructor que inserta \c "N" valores (aleatorios) en el contenedor.
    Lista_Ordenable(unsigned N);
    virtual ~Lista_Ordenable(); ///< Destructor

    virtual void Intercambie(int, int);
    virtual bool Es_Menor(int, int) const;
        virtual value_type& operator[](int);

    virtual void ImprimaSe() const;
    virtual const char* Nombre() const;
        /*virtual int Obtener_Valor(int);
        virtual void Inserta_Valor(int, int);*/
private:
    Nodo * m_cabeza; ///< Primer \c "Nodo" de la lista
};


/// Vector ordenable que almacena enteros.
/// - Este \c "Contenedor_Ordenable" es un vector de enteros de tamaño
///   \c "Contenedor_Ordenable::m_cantidad_de_elementos"
class Vector_Ordenable : public Contenedor_Ordenable {

private:
    value_type * m_vec;


public:
    /// Constructor que inserta \c "N" valores (aleatorios) en el contenedor.
    Vector_Ordenable(unsigned N);
    virtual ~Vector_Ordenable(); ///< Destructor

    virtual void Intercambie(int, int);
    virtual bool Es_Menor(int, int) const;
        virtual value_type& operator[](int);

    virtual void ImprimaSe() const;
    virtual const char* Nombre() const;
};


/// Clase abstracta que se usa para derivar de ella los algoritmos
/// que sirven para ordenar instancias de \c "Contenedor_Ordenable".
/// - No contiene campo alguno; sirve como "funtor" polimórfico.
class Algoritmo_Ordenador {
private: // "Rep vacío"
public:
    /// Este es el método que hace todo el trabajo.
    /// - Ordena el \c "Contenedor_Ordenable" usando el
    ///   \c "Algoritmo_Ordenador"
    virtual void Ordene(Contenedor_Ordenable &C) = 0;

    Algoritmo_Ordenador(); ///< Constructor
    virtual ~Algoritmo_Ordenador(); ///< Destructor

    // Nombre del algoritmo de ordenamiento
    virtual const char* Nombre() const = 0;
};


/// Clase de empaque alrededor del método de ordenamiento por "Burbuja".
/// - Está derivada de \c "Algoritmo_Ordenador" para homologar su funcionalidad.
/// - El método \c Ordene() es el que implementa el algoritmo de ordenamiento.
class Ordenador_Burbuja : public Algoritmo_Ordenador {
public:
    Ordenador_Burbuja(); ///< Constructor
    virtual ~Ordenador_Burbuja(); ///< Destructor

    /// Método que realiza el ordenamiento por "Burbuja".
    virtual void Ordene(Contenedor_Ordenable &);
    /// Retorna en nombre \c "Ordenador_Burbuja".
    virtual const char* Nombre() const;
};


/// Clase de empaque alrededor del método de ordenamiento por "Burbuja Optimizada".
/// - Está derivada de \c "Algoritmo_Ordenador" para homologar su funcionalidad.
/// - El método \c Ordene() es el que implementa el algoritmo de ordenamiento.
class Ordenador_Burbuja_Optimizada : public Algoritmo_Ordenador {
public:
    Ordenador_Burbuja_Optimizada(); ///< Constructor
    virtual ~Ordenador_Burbuja_Optimizada(); ///< Destructor

    /// Método que realiza el ordenamiento por "Burbuja Optimizada".
    virtual void Ordene(Contenedor_Ordenable &);
    /// Retorna en nombre \c "Ordenador_Burbuja_Optimizada".
    virtual const char* Nombre() const;
};


/// Clase de empaque alrededor del método de ordenamiento por "Selección".
/// - Está derivada de \c "Algoritmo_Ordenador" para homologar su funcionalidad.
/// - El método \c Ordene() es el que implementa el algoritmo de ordenamiento.
class Ordenador_Seleccion : public Algoritmo_Ordenador {
public:
    Ordenador_Seleccion(); ///< Constructor
    virtual ~Ordenador_Seleccion(); ///< Destructor

    virtual void Ordene(Contenedor_Ordenable &);
    /// Retorna en nombre \c "Ordenador_Seleccion".
    virtual const char* Nombre() const;
};


/// Clase de empaque alrededor del método de ordenamiento por "Insertion Sort".
/// - Está derivada de \c "Algoritmo_Ordenador" para homologar su funcionalidad.
/// - El método \c Ordene() es el que implementa el algoritmo de ordenamiento.
class Ordenador_Insertion_Sort : public Algoritmo_Ordenador {
public:
        Ordenador_Insertion_Sort();///<Constructor
        virtual ~Ordenador_Insertion_Sort(); ///<Destructor

        virtual void Ordene(Contenedor_Ordenable &);
    /// Retorna en nombre \c "Insertion_Sort"".
    virtual const char* Nombre() const;
};


/// Clase de empaque alrededor del método de ordenamiento por "Merge Sort".
/// - Está derivada de \c "Algoritmo_Ordenador" para homologar su funcionalidad.
/// - El método \c Ordene() es el que implementa el algoritmo de ordenamiento.
class Ordenador_Merge_Sort : public Algoritmo_Ordenador {
public:
        Ordenador_Merge_Sort();///<Constructor
        virtual ~Ordenador_Merge_Sort(); ///<Destructor

        virtual void Ordene(Contenedor_Ordenable &);
        void m_sort(Contenedor_Ordenable &, rational [], int, int);
        void merge(Contenedor_Ordenable &, rational [], int, int, int);

    /// Retorna en nombre \c "Merge_Sort"".
    virtual const char* Nombre() const;
};


Lista_Ordenable::Lista_Ordenable(unsigned N) : Contenedor_Ordenable(N) {
    m_cabeza = 0;
    this->m_cantidad_de_elementos = N;

    srand(time(0));
    for (unsigned i = 0; i < N; ++i) {
        Agregar_Valor( rand() % 100 );
    }
}

Lista_Ordenable::~Lista_Ordenable() {
    if (m_cabeza != 0) {
        delete m_cabeza;
    }
}

Lista_Ordenable::Nodo::Nodo(value_type v) {
    this->m_val = v;
    next = 0;
}

Lista_Ordenable::Nodo::~Nodo() {
    // Implementación recursiva de la destrucción de la lista de nodos
    if (next != 0) {
        delete next; // HORRIBLE: ==> Usa O( size() ) espacio
    }
}

void Lista_Ordenable::Agregar_Valor(value_type v) {
    if (m_cabeza == 0) {
        m_cabeza = new Nodo(v);
    }
    else {
        Nodo * p  = new Nodo(v);
        p->next   = m_cabeza;
        m_cabeza    = p;
    }
}

void Lista_Ordenable::Intercambie(int i, int j) {
    Nodo * pI = m_cabeza;
    Nodo * pJ = m_cabeza;

    int k;
    for (k = 0; k < i; ++k) {
        pI = pI->next;
    }
    for (k = 0; k < j; ++k) {
        pJ = pJ->next;
    }

    value_type temp;
    temp = pJ->m_val;
    pJ->m_val = pI->m_val; // NO intercambia los nodos
    pI->m_val = temp;      // intercambia los valores
}

bool Lista_Ordenable::Es_Menor(int i, int j) const {
    Nodo * pI = m_cabeza;
    Nodo * pJ = m_cabeza;

    int k;
    for (k = 0; k < i; ++k) {
        pI = pI->next;
    }

    for (k = 0; k < j; ++k) {
        pJ = pJ->next;
    }
    return (pI->m_val  <  pJ->m_val);
}

rational& Lista_Ordenable::operator[](int i) {
    Nodo * pI = m_cabeza;

    int k;
    for (k = 0; k < i; ++k) {
        pI = pI->next;
    }
    return pI->m_val;
}

void Lista_Ordenable::ImprimaSe() const {
    Nodo * p = m_cabeza;
    Nodo * end = 0;
    cout << "[";
    while (p != end) {
        cout << p ->m_val;
        if (p->next != end) { // ¿último nodo de la lista?
            cout << " ";
        }
        p = p->next;
    }
    cout << "]" << endl;
}

const char* Lista_Ordenable::Nombre() const {
    #ifdef    __BORLANDC__
        // Este método no puede ser definido dentro de la clase porque
        // BC++ lo considera "inline", lo que impide que sea "virtual"
    #endif // __BORLANDC__
    return "Lista_Ordenable";
}
Vector_Ordenable::Vector_Ordenable(unsigned N) : Contenedor_Ordenable(N) {
    // assert( N == m_cantidad_de_elementos );
    m_vec = new Contenedor_Ordenable::value_type [ m_cantidad_de_elementos ];
    srand( time(0) );

    for (int i = 0; i < m_cantidad_de_elementos; ++i) {
        m_vec[i] = rand() % 100;
    }
}

Vector_Ordenable::~Vector_Ordenable() {
    if (m_vec != 0) {
        delete [] m_vec;
    }
}

void Vector_Ordenable::ImprimaSe() const {
    value_type * p = m_vec;
    value_type * end = & m_vec[ m_cantidad_de_elementos ];
    cout << "[";
    while (p != end) {
        cout << *p;
        if (p+1 != end) { // ¿último valor del vector?
           cout << " ";
        }
        p++;
    }
    cout << "]" << endl;
}

bool Vector_Ordenable::Es_Menor(int i, int j) const {
    return (m_vec[i] < m_vec[j]);
}

rational& Vector_Ordenable::operator[](int i) {
    return m_vec[i];
}

void Vector_Ordenable::Intercambie(int i, int j) {
    value_type temp;

    temp   = m_vec[i];
    m_vec[i] = m_vec[j];
    m_vec[j] = temp;
}

const char* Vector_Ordenable::Nombre() const {
    return "Vector_Ordenable";
}

void Ordenador_Burbuja::Ordene(Contenedor_Ordenable & C) {
    int i,j;
    for (i = C.Dimension(); i > 0; --i) {
        for (j = 1; j < i; j++) {
            if ( C.Es_Menor(j, j-1) ) {
                C.Intercambie(j, j-1);
            }
        }
    }
}

void Ordenador_Burbuja_Optimizada::Ordene(Contenedor_Ordenable & C) {
    bool cambio = true;
    for (int i = C.Dimension(); i > 0 && cambio; --i) {
        cambio = false;
        for (int j = 1; j < i; j++) {
            if ( C.Es_Menor(j, j-1) ) {
                C.Intercambie(j, j-1);
                cambio = true;
            }
        }
    }
}

void Ordenador_Seleccion::Ordene(Contenedor_Ordenable & C) {
    int n = C.Dimension();
    for (int i=0; i < n-1; i++) {
        int menor = i;

        for (int j=i+1; j<n; j++) {
            if (C.Es_Menor(j,menor)) {
                menor = j;
            }
        }
        C.Intercambie(i, menor);
    }
}


void Ordenador_Insertion_Sort::Ordene(Contenedor_Ordenable & C){
        int n= C.Dimension();
        for (int i=1; i < n; i++){
                int j= i-1;
                while (C.Es_Menor(i,j)){
                        C.Intercambie(i,j);
                        i--;
                        j--;
                }
        }
}

void Ordenador_Merge_Sort::Ordene(Contenedor_Ordenable & C){
        int tamañoTotal= C.Dimension();
        int primero=0;
        rational vec_Temporal [20];
        m_sort (C,vec_Temporal,primero,tamañoTotal-1);

}

void Ordenador_Merge_Sort::m_sort(Contenedor_Ordenable & C, rational vector [],int inicio,int fin){
        int mitad;

        if (fin > inicio){
                mitad= (fin + inicio)/2;
                m_sort( C, vector, inicio, mitad);
                m_sort( C, vector, mitad+1, fin);

                merge(C, vector, inicio, mitad+1, fin);
        }
}

void Ordenador_Merge_Sort:: merge(Contenedor_Ordenable & C,rational vector[],int inicio, int mitad, int tamaño){
        int i, final_izquierda, num_elements, tmp_pos;
        

        final_izquierda = mitad - 1; ///Marca el ultimo indice de la primera mitad del contenedor
        tmp_pos = inicio;
        num_elements = (tamaño - inicio);

        while ((inicio <= final_izquierda) && (mitad <= tamaño)){
                if (C[inicio]<=C[mitad]){
                        vector[tmp_pos]= C[inicio];
                        tmp_pos++;
                        inicio++;
                }
                else{
                        vector[tmp_pos]= C[mitad];
                        tmp_pos++;
                        mitad++;
                }
        }

        while (inicio <= final_izquierda){
                vector[tmp_pos]= C[inicio];
                inicio++;
                tmp_pos++;
        }
        while (mitad <= tamaño){
                vector[tmp_pos]= C[mitad];
                mitad++;
                tmp_pos++;
        }
        
        for (i=0; i <= num_elements; i++){
                C[tamaño]= vector[tamaño];
                tamaño--;
                }
}

Contenedor_Ordenable::Contenedor_Ordenable(unsigned N)
    : m_cantidad_de_elementos(N) {
}

Contenedor_Ordenable::~Contenedor_Ordenable() {
    // No hace nada porque no usa memoria dinámica
}

Algoritmo_Ordenador::Algoritmo_Ordenador() {
    // No hace nada porque el "Rep" está vacío
}

Algoritmo_Ordenador::~Algoritmo_Ordenador() {
    // No hace nada porque el "Rep" está vacío
}

Ordenador_Burbuja::Ordenador_Burbuja() {
    // No hace nada porque el "Rep" está vacío
}

Ordenador_Burbuja::~Ordenador_Burbuja() {
    // No hace nada porque el "Rep" está vacío
}

const char* Ordenador_Burbuja::Nombre() const {
    return "Ordenador_Burbuja";
}

Ordenador_Seleccion::Ordenador_Seleccion() {
    // No hace nada porque el "Rep" está vacío
}

Ordenador_Seleccion::~Ordenador_Seleccion() {
    // No hace nada porque el "Rep" está vacío
}

const char* Ordenador_Seleccion::Nombre() const {
    return "Ordenador_Seleccion";
}

Ordenador_Burbuja_Optimizada::Ordenador_Burbuja_Optimizada() {
    // No hace nada porque el "Rep" está vacío
}

Ordenador_Burbuja_Optimizada::~Ordenador_Burbuja_Optimizada() {
    // No hace nada porque el "Rep" está vacío
}

const char* Ordenador_Burbuja_Optimizada::Nombre() const {
    return "Ordenador_Burbuja_Optimizada";
}

Ordenador_Insertion_Sort::Ordenador_Insertion_Sort() {
    // No hace nada porque el "Rep" está vacío
}

Ordenador_Insertion_Sort::~Ordenador_Insertion_Sort() {
    // No hace nada porque el "Rep" está vacío
}

const char* Ordenador_Insertion_Sort::Nombre() const {
    return "Ordenador_Insertion_Sort";
}

Ordenador_Merge_Sort::Ordenador_Merge_Sort() {
    // No hace nada porque el "Rep" está vacío
}

Ordenador_Merge_Sort::~Ordenador_Merge_Sort() {
    // No hace nada porque el "Rep" está vacío
}

const char* Ordenador_Merge_Sort::Nombre() const {
    return "Ordenador_Merge_Sort";
}


/// Retorna \c "true" cuando el contenedor \c "C" está ordenado no decrecientemente.
bool Esta_Ordenado ( const Contenedor_Ordenable &C ) {
    unsigned i;
    for (i = 0; i < C.Dimension()-1; ++i) {
        if ( C.Es_Menor(i+1,i) ) {
            return false;
        }
    }
    return true;
}

#include <assert.h>

/// Rutina principal del programa.
/// - En cada iteración de su ciclo principal elije un contenedor para almacenar
///   valores (lista vs vector), y un algoritmo de ordenamiento
///   (Burbuja vs Burbuja_Optimizada vs Seleccion).
int main() {
    Algoritmo_Ordenador  * pOrdenador;  // puntero "polimórfico" para el algoritmo
    Contenedor_Ordenable * pContenedor; // puntero "polimórfico" para el contenedor
    srand( time(0) );
    cout << endl << endl << endl;
    for (int i = 0; i < 5; ++i) {         // Algoritmo_Ordenador
        for (int j = 0; j < 2; ++j) {     // Contenedor_Ordenable

            cout << endl;
            cout << "======================";
            cout << "======================";
            cout << "======================" << endl;

            // Selecciona el algoritmo de ordenamiento
            switch ( i ) {
                case 0: pOrdenador = new Ordenador_Burbuja();            break;
                case 1: pOrdenador = new Ordenador_Burbuja_Optimizada(); break;
                case 2: pOrdenador = new Ordenador_Seleccion();          break;
                                case 3: pOrdenador = new Ordenador_Insertion_Sort();     break;
                                case 4: pOrdenador = new Ordenador_Merge_Sort();                 break;
            }

            // Selecciona "Lista_Ordenable" o "Vector_Ordenable" como contenedor
            switch ( j ) {
                case 0: pContenedor = new Vector_Ordenable( 20 ); break;
                case 1: pContenedor = new Lista_Ordenable(  20 ); break;
            }

            cout << "<<< " << 2*i+j+1 << " >>> => ";
            cout << pContenedor->Nombre() << " <===> ";
            cout << pOrdenador->Nombre() << endl;
            // Se imprime la lista desordenada generada al azar
            cout << endl << "[Sin orden]: ";
            pContenedor->ImprimaSe();

            pOrdenador->Ordene( *pContenedor );
            cout << endl << "[Ordenados]: ";
            pContenedor->ImprimaSe();

            if (! Esta_Ordenado( *pContenedor ) ) {
                cout << endl;
                cout << "ERRROR: El contenedor " << pContenedor->Nombre() << " NO está ordenado" << endl;
                assert( "ERRROR: El contenedor NO está ordenado" && false );
            }

            // Destruye "pOrdenador" && "pContenedor"
            delete pOrdenador;
            delete pContenedor;
        }
    }
        getch();
    return 0;
}
// EOF: HerenciaOrdenada.cpp

---

Hosted by www.Geocities.ws