====== Examen Parcial - 75.41. Algoritmos y Programación II ======

**Cátedra:** Mandrafina\\
**Fecha:** Primera Oportunidad - Segundo Cuatrimestre 2004\\
**Día:** 08/10/2004

<note important>
Esta página está incompleta; podés ayudar completando el material.
</note>

===== Enunciado =====
==== Punto I ====
Dado el siguiente programa se requiere indicar lo que se mostraría por pantalla: 

<code cpp>
#include <iostream> 
using namespace std; 
 
int main(){ 
    int *A, *C; 
    int **B; 
    char *D, *E, *F; 
    char G; 
    int H; 
 
    H = 15; 
    G = 'B'; 
    A = new int();

    *A = 64; 
    cout << H << G << *A << endl; 
    B = &A; 
    cout << **B << endl; 
    D = (char*) A; 
    C = (int*) D; 
    cout << *D << *C << endl; 
    delete A; 
    if ( *D == '?' ) { 
        cout << G << H << endl; 
    } 
} 
 
</code>

==== Punto II ====
¿Qué es programación por contrato? Explique los conceptos de precondición, postcondición y axioma, dentro de la teoría de Tipos de Datos Abstractos.

==== Punto III ====

Construtir un TDA ConsultaCompetidor que permita acceder a la información del siguiente archivo:
^  Campo  ^  Tipo  ^
|  NumeroCompetidor  |  int  |
|  NombreCompetidor  |  char[30]  | 
|  TiempoVuelta  |  “mmss” (char[4])  | 
|  Pais  |  char[35]  | 
|  Edad  |  unsigned int  |

Las primitivas que debe ofrecer son (agregue las que considere necesarias):
  * obtenerTiempoPromedio( ConsultaCompetidor cc )
  * obtenerCompetidorMejorTiempo(ConsultaCompetidor cc )
  * obtenerCompetidorPeorTiempo(ConsultaCompetidor cc )
  * obtenerCompetidor(ConsultaCompetidor cc, int nroCompetidor ) 
 
La implementación del TDA puede hacer con la estructura de datos que se considere conveniente, pero deben especificarse e implementarse todas las primitivas.



==== Punto IV ====
Resolución de problema de aplicación (1hr 20 min)

Dado los archivos descriptos más abajo, totalmente desordenados, construir un programa para emitir un listado de ciudades, ordenado por código de país y cantidad de habitantes, para el continente con CodigoContinente = 1:
^ PAIS ^ CIUDAD ^ CANTIDAD DE HABITANTES ^
| ar | Buenos Aires | 3500000 |
| br | San Pablo | 4000000 |

Los archivos tienen la siguiente estructura:
^Campo ^ Tipo ^
| CodigoPais | char[2] |
| CodigoContinente | int |
| NombrePais | char[30] |

^Campo ^ Tipo ^
| CodigoCiudad | int |
| CodigoPais | char[2] |
| NombreCiudad | char[40] |
| CantidadHabitantes | int |

Nota:
  - Explicar la estrategia de solución adoptada con claridad (usar esquemas)
  - Los archivos se procesarán secuencialmente, una sola vez, luego en forma directa 
  - Los archivos no deben almacenarse en memoria bajo ninguna circunstancia
  - Completar todo lo necesario para la resolución del problema, tipos, variables, procedimientos, etc.

===== Resolución =====


==== Punto III ====
<code cpp>
/************************************************************************************
El ordenamiento de la lista se hace de la siguiente manera:

ResultadoComparacion compararDato(Dato dato1, Dato dato2) {
    if (getTiempoVuelta(dato1.competidor) == getTiempoVuelta(dato2.competidor)) {
        if (getNombre(dato1.competidor) == getNombre(dato2.competidor))
            return igual;
        else {
            if (getNombre(dato1.competidor) > getNombre(dato2.competidor))
                return mayor;
            else
                return menor;
        }
    }

    else
        if (getTiempoVuelta(dato1.competidor) > getTiempoVuelta(dato2.competidor))
            return mayor;
        else
            return menor;
}
*******************************************************************************************/
/*
Pre: Ninguna
Post: La consulta queda creada y lista para ser usada
*/
void crear(cCompetidor &miConsulta) {
    crearLista(miConsulta.competidores);
}

/*
Pre: La consulta debe haber sido creada
Post: La consulta queda destruída e inutilizable
*/
void destruir(cCompetidor &miConsulta) {
    PtrNodoLista ptrCompetidor;
    Dato datoCompetidor;

    ptrCompetidor = primero(miConsulta.competidores);
    while (ptrCompetidor != fin()) {
        obtenerDato(miConsulta.competidores,datoCompetidor,ptrCompetidor);
        destruir(datoCompetidor.competidor);
        colocarDato(miConsulta.competidores,datoCompetidor,ptrCompetidor);
        ptrCompetidor = siguiente(miConsulta.competidores,ptrCompetidor);
    }
    eliminarLista(miConsulta.competidores);
}

/*
Pre: La consulta debe haber sido creada, así como el competidor a agregar
Post: El competidor queda agregado a la consulta
*/
void agregarCompetidor(cCompetidor &miConsulta, Competidor* miCompetidor) {
    Dato datoCompetidor;

    datoCompetidor.competidor = miCompetidor;
    insertarDato(miConsulta.competidores,datoCompetidor);
}

/*
Pre: La consulta debe haber sido creada, y miCompetidor debe referenciar a un competidor
Post: Se elimina al competidor de la consulta (no se destruye el competidor)
*/
void quitarCompetidor(cCompetidor &miConsulta, Competidor* miCompetidor){
    PtrNodoLista ptrCompetidor;
    Dato datoCompetidor;
    bool encontrado = false;
    
    ptrCompetidor = primero(miConsulta.competidores);
    while ((ptrCompetidor != fin()) && (!encontrado)){
        obtenerDato(miConsulta.competidores,datoCompetidor,ptrCompetidor);
        if (datoCompetidor.competidor == miCompetidor){
            encontrado = true;
        }
        else {
            ptrCompetidor = siguiente(miConsulta.competidores,ptrCompetidor);
        }
    }
    
    if (encontrado){
        eliminarNodo(miConsulta.competidores,ptrCompetidor);    
    }
}

/*
Pre: La consulta debe haber sido creada y "pathCompetidores" debe ser la ruta a un archivo con formato correcto
Post: Se agregan todos los competidores del archivo a la consulta
*/
void cargarCompetidores(cCompetidor &miConsulta, string pathCompetidores) {
    ArchivoRegistros fCompetidores;
    regCompetidor registro;
    Competidor* nvoCompetidor;
    unsigned int tiempo;

    crear(fCompetidores,pathCompetidores,sizeof(regCompetidor));
    while (!fin(fCompetidores)) {
        leer(fCompetidores,static_cast<void*>(&registro));
        crear(nvoCompetidor,registro.numero,registro.nombre);
        setEdad(nvoCompetidor,registro.edad);
        tiempo = convertirTiempo(registro.tiempo);
        setTiempoVuelta(nvoCompetidor,tiempo);
        setPais(nvoCompetidor,registro.pais);
        agregarCompetidor(miConsulta,nvoCompetidor);
    }
    destruir(fCompetidores);
}

/*
Pre: La consulta debe haber sido creada
Post: Se devuelve el tiempo promedio de los competidores de la consulta. En caso de haber un error se retorna "0"
*/
float obtenerTiempoPromedio(cCompetidor &miConsulta) {
    float promedio = 0;
    int cantidadCompetidores = 0;
    int sumatoria = 0;
    PtrNodoLista ptrCompetidor;
    Dato datoCompetidor;

    ptrCompetidor = primero(miConsulta.competidores);
    while (ptrCompetidor != fin()) {
        cantidadCompetidores++;
        obtenerDato(miConsulta.competidores,datoCompetidor,ptrCompetidor);
        sumatoria += getTiempoVuelta(datoCompetidor.competidor);
        ptrCompetidor = siguiente(miConsulta.competidores,ptrCompetidor);
    }

    if (cantidadCompetidores != 0) {
        promedio = (float)sumatoria/cantidadCompetidores;
    }

    return promedio;
}

/*
Pre: La consulta debe haber sido creada
Post: Se retorna una referencia el competidor de mejor tiempo. En caso que no hay competidores, se retorna "0"
*/
Competidor* obtenerCompetidorMejorTiempo(cCompetidor &miConsulta) {
    Competidor* competidor = 0;
    PtrNodoLista ptrCompetidor;
    Dato datoCompetidor;

    ptrCompetidor = primero(miConsulta.competidores);
    if (ptrCompetidor != fin()) {
        obtenerDato(miConsulta.competidores,datoCompetidor,ptrCompetidor);
        competidor = datoCompetidor.competidor;
    }
    return competidor;
}

/*
Pre: La consulta debe haber sido creada
Post: Se retorna una referencia el competidor de peor tiempo. En caso que no hay competidores, se retorna "0"
*/
Competidor* obtenerCompetidorPeorTiempo(cCompetidor &miConsulta) {
    Competidor* competidor = 0;
    PtrNodoLista ptrCompetidor;
    Dato datoCompetidor;

    ptrCompetidor = ultimo(miConsulta.competidores);
    if (ptrCompetidor != fin()) {
        obtenerDato(miConsulta.competidores,datoCompetidor,ptrCompetidor);
        competidor = datoCompetidor.competidor;
    }
    return competidor;
}

/*
Pre: La consulta debe haber sido creada
Post: Se retorna una referencia al competidor cuyo número es nroCompetidor. En caso de no existir en la consulta, se retorna 0
*/
Competidor* obtenerCompetidor(cCompetidor &miConsulta, int nroCompetidor) {
    PtrNodoLista ptrCompetidor;
    Dato datoCompetidor;
    bool encontrado = false;
    Competidor* competidor = 0;

    ptrCompetidor = primero(miConsulta.competidores);
    while ((ptrCompetidor != fin()) && (!encontrado)) {
    obtenerDato(miConsulta.competidores,datoCompetidor,ptrCompetidor);
        if (getNumero(datoCompetidor.competidor) == nroCompetidor) {
            encontrado = true;
            competidor = datoCompetidor.competidor;
        }
        else
            ptrCompetidor = siguiente(miConsulta.competidores,ptrCompetidor);
    }
    return competidor;
}
</code>

Para que todo esto ande, obviamente hace falta el **TDA Competidor**:

<code cpp>
using namespace std;

const string NOPAIS = "Orígen Indefinido";

typedef struct Competidor{
    int numero;
    string nombre;
    unsigned int edad;
    string pais;
    unsigned int tiempoVuelta;
};

/*
Pre: Ninguna
Post: Crea el dato y lo deja listo para su uso
*/
void crear(Competidor* &miCompetidor, int numero, string nombre){
    miCompetidor = new Competidor;
    miCompetidor->numero = numero;
    miCompetidor->nombre = nombre;
    miCompetidor->edad = 0;
    miCompetidor->pais = NOPAIS;
    miCompetidor->tiempoVuelta = 0;
}

/*
Pre: El dato debe haber sido creado
Post: Destruye el dato, y lo deja inutilizable
*/
void destruir(Competidor* &miCompetidor){
    miCompetidor->numero = 0;
    delete miCompetidor;
    miCompetidor = NULL;
}

/*
Pre: El dato debe haber sido creado
Post: Establece el nombre del competidor
*/
void setNombre(Competidor* miCompetidor, string nombre){
    miCompetidor->nombre = nombre;
}

/*
Pre: El dato debe haber sido creado
Post: Establece la edad del competidor
*/
void setEdad(Competidor* miCompetidor, unsigned int edad){
    miCompetidor->edad = edad;
}

/*
Pre: El dato debe haber sido creado
Post: Establece el país del competidor
*/
void setPais(Competidor* miCompetidor, string pais){
    miCompetidor->pais = pais;
}

/*
Pre: El dato debe haber sido creado y tiempoVuelta debe ser un entero, representado en segundos
Post: Establece el tiempo de vuelta del competidor
*/
void setTiempoVuelta(Competidor* miCompetidor, unsigned int tiempoVuelta){
    miCompetidor->tiempoVuelta = tiempoVuelta;
}

/*
Pre: El dato debe haber sido creado
Post: Establece el tiempo de vuelta del competidor (en segundos)
*/
int getNumero(Competidor* miCompetidor){
    return miCompetidor->numero;
}

/*
Pre: El dato debe haber sido creado
Post: Retorna el nombre del competidor
*/
string getNombre(Competidor* miCompetidor){
    return miCompetidor->nombre;
}

/*
Pre: El dato debe haber sido creado
Post: Retorna la edad del competidor
*/
unsigned int getEdad(Competidor* miCompetidor){
    return miCompetidor->edad;
}

/*
Pre: El dato debe haber sido creado
Post: Retorna el país del competidor
*/
string getPais(Competidor* miCompetidor){
    return miCompetidor->pais;
}

/*
Pre: El dato debe haber sido creado
Post: Retorna el tiempo de vuelta del competidor (en segundos)
*/
unsigned int getTiempoVuelta(Competidor* miCompetidor){
    return miCompetidor->tiempoVuelta;
}
</code>


==== Punto IV ====

==Estrategia==

Se cargan todos los paises en el continente 1, ordenándolos por código ascendente.
Luego se lee el archivo de ciudades insertándolas en la lista de ciudades del pais correspondiente, si existiera ( se inserta en forma ascendente por habitantes )
{{:materias:75:41:diagrama.png|:materias:75:41:diagrama.png}}
==Implementación==

<code cpp>
struct tPais{
    PtrNodoLista corriente;
    char codigo[3];
    Lista ciudades;
};
struct tCiudad{
    int habitantes;
    long prr;
};
struct RegPais{
    char codigo[2];
    int continente;
    char nombre[30];
};
struct RegCiudad{
    int codigo;
    char cod_pais[2];
    char nombre[40];
    int habitantes;
};

const int IGUAL = 0;
const int MAYOR = 1;
const int MENOR = -1;

int compararPais( tPais& p1, tPais& p2 )
{
    string cod1 = getCodigo( p1 );
    string cod2 = getCodigo( p2 );
    
    if( cod1 == cod2 ) return IGUAL;
    if( cod1 < cod2 ) return MENOR;
    if( cod1 > cod2 ) return MAYOR;
}

int main()
{
    Lista paises;
    
    crearLista( paises );
    cargarPaises( paises );
    cargarCiudades( paises );
    mostrarListado( paises );
    
    liberarListaPais( paises );
    eliminarLista( paises );
    return 0;
}

void cargarPaises( Lista paises )
{
    ArchivoRegistro arch;
    RegPais aux;
    tPais pais;

    crearArchivoReg( arch, “paises.dat”, sizeof( RegPais ) );
    while( !fin(arch) ){
        leer(arch, &aux);
        if( aux.continente == 1 ){
            crearPais(pais, aux.codigo );
            insertarDato( paises, pais );
            destruirPais( pais );
        }
    }
    destruirArchivo( arch );
}

void cargarCiudades( Lista paises )
{
    PtrNodoLista pOrigen; // puntero al nodo del pais encontrado
    tPais pais; // patron de busqueda
    ArchivoRegistro arch;
    RegCiudad aux;
    tCiudad ciudad;
    
    crearArchivoReg(arch, “ciudades.dat”, sizeof(RegCiudad));
    while(!fin(arch)){
        leer(arch,aux);
        crearPais( pais, aux.cod_pais);
        pOrigen = localizarDato( paises, pais );
        destruirPais( pais );
        if( pOrigen != fin( paises ) ){
            obtenerDato( paises, pais, pOrigen );
            crearCiudad( ciudad, aux.habitantes, posicion(arch) );
            agregarCiudad( pais, ciudad );
            colocarDato( paises, pais, pOrigen );
            destruirCiudad( ciudad );
        }
    }
    destruirArchivo(arch);
}

void liberarListaPais( Lista paises )
{
    tPais pais;
    PtrNodoLista pNodo;
    
    pNodo = primero( paises );
    while( pNodo != fin( paises) ){
        obtenerDato(paises, pais, pNodo );
        destruirPais(pais);
        colocarDato( paises, pais, pNodo);
        pNodo = siguiente( paises, pNodo );
    }
}

void mostrarListado( Lista paises )
{
    long prr:
    tPais pais;
    tCiudad ciudad;
    RegCiudad aux;
    PtrNodoLista pNodo;
    ArchivoRegistro arch;
    
    crearArchivoReg( arch, “ciudades.dat”, sizeof(RegCiudad)),
    cout << “PAIS\tCIUDAD\t\tHABITANTES\n”;
    pNodo = primero( paises );
    while( pNodo != fin(paises)){
        obtenerDato(paises, pais, pNodo);
        primerCiudad( pais );
        while( obtenerCiudad( pais, ciudad) ){
            prr = getPrr( ciudad );
            posicionarse( arch, prr);
            leer( arch, aux);
            cout << getCodigo(pais) << “\t” << aux.nombre << “\t\t”;
            cout << getHabitantes(ciudad) << endl;
        }
        pNodo = siguiente(paises, pNodo );
    }
    destruirArchivo( arch );
}

// TDAs utilizados ( structs declarados arriba )
// tPais

void crearPais( tPais& pais, char cod[] )
{
    pais.codigo[2] = '\0'; // fin de cadena
    pais.codigo[0] = cod[0];
    pais.codigo[1] = cod[1];
    crearLista( pais.ciudades );
}

void destruirPais( tPais& pais )
{
    tCiudad ciudad;
    PtrNodoLista pNodo;

    pNodo = primero( pais.ciudades);
    while( pNodo != fin(pais.ciudades) ){
        obtenerDato( pais.ciudades, ciudad, pNodo);
        destruirCiudad( ciudad );
        colocarDato( pais.ciudades, ciudad, pNodo);
        pNodo = siguiente( pais.ciudades, pNodo );
    }
    eliminarLista( pais.ciudades );
}

//mueve el puntero corriente a la primer ciudad, sin obtenerla
void primerCiudad( tPais& pais )
{
    pais.corriente = primero( pais.ciudades );
}

//obtiene la ciudad actual, mueve el puntero al siguiente, devuelve true si la ciudad
// obtenida es válida
bool obtenerCiudad( tPais& pais, tCiudad& ciudad )
{
    if( pais.corriente == fin( pais.ciudades ) )
        return false;

    obtenerDato( pais.ciudades, ciudad, pais.corriente );
    pais.corriente = siguiente( pais.ciudades, pais.corriente );
    return true;
}

//obtiene el codigo
string getCodigo( tPais& pais )
{
    return string( pais.codigo );
}

//TDA Ciudad
// tCiudad
void crearCiudad( tCiudad& ciudad, int habitantes, long prr )
{
    ciudad.habitantes = habitantes;
    ciudad.prr = prr;
}

void destruirCiudad( tCiudad& ciudad )
{
}

long getPrr( tCiudad& ciudad )
{
    return ciudad.prr;
}

int getHabitantes( tCiudad& ciudad )
{
    return ciudad.habitantes;
}
</code>

Hasta acá llevo 1 hora 16 minutos. Más tarde, cuando pasaba la resolución, me di cuenta que faltaba la primitiva agregarCiudad. La listo a continuación:
<code cpp>
void agregarCiudad( tPais& pais, const tCiudad& ciudad )
{
    insertarDato( pais.ciudades, ciudad );
}
</code>

===== Discusión =====

<note warning>
Si ves algo que te parece incorrecto en la resolución y no te animás a cambiarlo, dejá tu comentario acá </note>