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 "ADH_port.h"  // Biblioteca de compatibilidad BC++ v3.1 && MS C++

#include <cstdlib>
#include <ctime>

/// 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 int 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;

    /// \v 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;
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;
};
class Ordenador_Insercion : public Algoritmo_Ordenador{
public:
    Ordenador_Insercion(); ///< Constructor
    virtual ~Ordenador_Insercion(); ///< Destructor

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


/// Clase de empaque alrededor del método de ordenamiento por "Mezcla".
/// - 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_Mezcla : public Algoritmo_Ordenador{
private:
        Lista_Ordenable TMP(20);
        /// Itera a través del vector temporal
        /// e inicializa cada elemento en cero
        for (int i=0; i < 20; ++i) {
                TMP[i] = 0;
        }
public:
    Ordenador_Mezcla(); ///< Constructor
    virtual ~Ordenador_Mezcla(); ///< Destructor

    /// Método que realiza el ordenamiento por "Mezcla".
        virtual void Ordene(Contenedor_Ordenable &);
        /// Método que recursivamente ordena las 2 mitades por separado del arreglo
        void m_sort(Contenedor_Ordenable &, Lista_Ordenable &, int left, int right);
        /// Método que mezcla ordenadamente las 2 mitades ya ordenadas del arreglo
        void merge(Contenedor_Ordenable &, Lista_Ordenable &, int left, int mid, int right);
    /// Retorna en nombre \c "Ordenador_Mezcla".
    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);
}

int& 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]);
}

int& 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_Insercion :: Ordene (Contenedor_Ordenable & C){
     // Ordenador insercion                                                     
     // ciclo atraves de todos los elementos de Contenedor_Ordenable                                
     for ( int next = 1; next < C.Dimension(); next++ )                        
     {                                                                     
        int moveItem = next; // inicializa el lugar para la colocacion de elementos       
                                                                           
        // busqueda del lugar en donde colocar el elemento actualmente analizado     
                while ( ( moveItem > 0 ) && ( C.Es_Menor(moveItem, moveItem-1) ) )    
        {                                                                  
           // intercambia los elementos en las posiciones determinadas                          
           C.Intercambie(moveItem, moveItem-1);                        
           moveItem--;                                                     
        } // fin del while                                                     
                                                                           
     } // fin del for                                                          
}
void Ordenador_Mezcla :: Ordene (Contenedor_Ordenable & C){
    /// Crea un vector temporal para almacenar los valores a ordenar
        
        m_sort(C, TMP, 0, C.Dimension() - 1);
}
void Ordenador_Mezcla :: m_sort(Contenedor_Ordenable & C, Lista_Ordenable & temp, int left, int right)
{ 
  /// Valor en la mitad del vector      
  int mid;

  if (right > left)
  {
    mid = (right + left) / 2;
    m_sort(C, temp, left, mid);
    m_sort(C, temp, mid+1, right);

    merge(C, temp, left, mid+1, right);
  }
}
void Ordenador_Mezcla :: merge(Contenedor_Ordenable & C, Lista_Ordenable & temp, int left, int mid, int right)
{
  int i, left_end, num_elements, tmp_pos;

  left_end = mid - 1;
  tmp_pos = left;
  num_elements = right - left + 1;

  while ((left <= left_end) && (mid <= right))
  {
          if (C[left] <= C[mid])
    {
      temp[tmp_pos] = C[left];
      tmp_pos = tmp_pos + 1;
      left = left +1;
    }
    else
    {
      temp[tmp_pos] = C[mid];
      tmp_pos = tmp_pos + 1;
      mid = mid + 1;
    }
  }

  while (left <= left_end)
  {
    temp[tmp_pos] = C[left];
    left = left + 1;
    tmp_pos = tmp_pos + 1;
  }
  while (mid <= right)
  {
    temp[tmp_pos] = C[mid];
    mid = mid + 1;
    tmp_pos = tmp_pos + 1;
  }

  for (i=0; i <= num_elements; i++)
  {
    C[right] = temp[right];
    right = right - 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[j] < C[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) */ C[j] < C[menor] ) {
                menor = j;
            }
        }
        C.Intercambie(i, menor);
    }
}

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_Insercion::~Ordenador_Insercion() {
    // No hace nada porque el "Rep" está vacío
}

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

const char* Ordenador_Insercion::Nombre() const {
    return "Ordenador_Insercion";
}
Ordenador_Mezcla::~Ordenador_Mezcla() {
    for(int i = 0; i< 20; i++)
                delete TMP[i];// No hace nada porque el "Rep" está vacío
}

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

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

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";
}


/// 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_Insercion();          break;
                                case 4: pOrdenador = new Ordenador_Mezcla();          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;
        }
    }
    return 0;
}
// EOF: HerenciaOrdenada.cpp

---

Hosted by www.Geocities.ws