Ej 2 - Segundo Recuperatorio 2018 2C

[SrMathew]

Buenas tardes,

Le adjunto solución al problema, notamos que las soluciones propuestas admiten tanto listas como vectores, y utilizamos el testeo propuesto para verificar correcto funcionamiento. El testo pasa bien : D

Quisiera saber si las funciones tienen funcionamiento correcto y buen estilo ya que difieren un poco de las indicadas en la solucion correspondiente, adjunto codigo del ADT, CDT y test correspondientemente. Mil gracias por la atencion de siempre

#include <stdlib.h>

typedef struct multiSetCDT * multiSetADT;
typedef int elemType; // Tipo de elemento a insertar

/**
** Retorna 0 si los elementos son iguales, negativo si e1 es "menor" que e2 y positivo
** si e1 es "mayor" que e2
*/
static int compare (elemType e1, elemType e2) {
    return e1 -e2;
}

/* Retorna un nuevo multiSet de elementos genéricos. Al inicio está vacío */
multiSetADT newMultiSet(); // listo

/* Inserta un elemento. Retorna cuántas veces está elem en el conjunto
** luego de haberlo insertado (p.e. si es la primera inserción retorna 1).
*/
unsigned int add(multiSetADT multiSet, elemType elem); // listo

/* Retorna cuántas veces aparece el elemento en el multiSet */
unsigned int count(const multiSetADT multiSet, elemType elem); // listo

/* Retorna la cantidad de elementos distintos que hay en el multiSet */
unsigned int size(const multiSetADT multiSet); // listo

/* Elimina una repetición del elemento. Retorna cuántas veces está elem el conjunto
** luego de haberlo borrado (si el elemento no estaba, retorna cero)
*/
int removeOne(multiSetADT multiSet, elemType elem); // listo

/* Elimina todas las apariciones de un elemento. */
void removeAll(multiSetADT multiSet, elemType elem); // listo

/* Retorna un vector con los elementos que menos aparecen en el conjunto
** Si el conjunto está vacío retorna NULL
** En el parámetro de salida dim almacena la cantidad de elementos del vector
*/
elemType * minElements(const multiSetADT multiSet, int * dim);

void freeMultiSet(multiSetADT multiSet);

#include <stdlib.h>
#include "multiSetADT.h"

#define BLOQUE 10

typedef struct multiSetCDT{
    elemType * elementos;  // 2 5 7 8 10 11 (dim = 6)
    size_t * apariciones;  // 0 3 0 3 1  1 (size = 4)
    size_t size; // cant de elementos distintos con aparicion > 0
    size_t dim; // largo arreglos
}multiSetCDT;

multiSetADT newMultiSet(){
    return calloc(1,sizeof(multiSetCDT));
}

unsigned int add(multiSetADT multiSet, elemType elem){
    size_t i;
    for ( i = 0; i < multiSet->dim; i++){ // veo si ya existe
        if (compare(multiSet->elementos[i],elem) == 0){
            multiSet->apariciones[i] += 1;
            if (multiSet->apariciones[i] == 1){ // antes era 0, no disponible
                multiSet->size += 1;
            }
            return multiSet->apariciones[i];
        }
    }
    // si no existe
    if ( multiSet->dim % BLOQUE == 0){
        multiSet->elementos = realloc(multiSet->elementos, (multiSet->dim + BLOQUE) * sizeof(elemType));
        multiSet->apariciones = realloc(multiSet->apariciones, (multiSet->dim + BLOQUE) * sizeof(size_t));
    }
    multiSet->elementos[multiSet->dim] = elem;
    multiSet->apariciones[multiSet->dim] = 1;
    multiSet->dim +=1;
    multiSet->size += 1; // elemento nuevo disponible
    return 1;
}

unsigned int count(const multiSetADT multiSet, elemType elem){
    size_t i;
    for ( i = 0; i < multiSet->dim; i++){ // veo si ya existe
        if (compare(multiSet->elementos[i],elem) == 0){
           return multiSet->apariciones[i];
        }
    }
    return 0;
}

unsigned int size(const multiSetADT multiSet){
    return multiSet->size;
}

int removeOne(multiSetADT multiSet, elemType elem){
    size_t i;
    for ( i = 0; i < multiSet->dim; i++){ // veo si ya existe
        if (compare(multiSet->elementos[i],elem) == 0 && multiSet->apariciones[i]!=0){
            multiSet->apariciones[i] -= 1;
            if (multiSet->apariciones[i] == 0)
            {
                multiSet->size -= 1;
            }
            
            return multiSet->apariciones[i];
        }
    }
    return 0; // si ya era 0 o no existe
}

void removeAll(multiSetADT multiSet, elemType elem){
    size_t i;
    for ( i = 0; i < multiSet->dim; i++){ // veo si ya existe
        if (compare(multiSet->elementos[i],elem) == 0){
            multiSet->apariciones[i] = 0;
            multiSet->size -= 1;
            return;
        }
    }
    return;
}

elemType * minElements(const multiSetADT multiSet, int * dim){
    size_t cantMin=0, i=0;
    *dim = 0;
    for ( i = 0; i < multiSet->dim; i++){ // si veo uno menor piso cantMin y mientras encuentre uno igual sumo 1 a minSize
        if ( multiSet->apariciones[i] != 0 ){
            if ( cantMin == 0 || cantMin > multiSet->apariciones[i])
            {
                cantMin = multiSet->apariciones[i];
                *dim = 1;
            }
            else if ( cantMin == multiSet->apariciones[i] )
            {
                (*dim)++;
            }
        }
    }
    
    // ahora que conozco el mas chico (cantMin) y cuantos son (*dim) puedo crear el nuevo vector
    // vuelvo a recorrer para asignar los elementos
    elemType * newVec = malloc( (*dim) * sizeof(elemType) );
    size_t j;
    for ( i = 0, j=0; i < multiSet->dim && j < (*dim); i++){ // si veo uno menor piso cantMin y mientras encuentre uno igual sumo 1 a *dim
        if ( multiSet->apariciones[i] != 0 ){
            if ( cantMin == multiSet->apariciones[i] )
            {
                newVec[j] = multiSet->elementos[i];
                j++;
            }
        }
    }
    return newVec;
}

void freeMultiSet(multiSetADT multiSet){ // No se pedia en el .h pero se hizo para practicar
    free(multiSet->apariciones); // vector
    free(multiSet->elementos); // vector
    free(multiSet);
    return;
}

#include <stdio.h>
#include <assert.h>
#include "multiSetADT.h"

int main (void){
    multiSetADT mySet=newMultiSet();
    int v[]={1,2,3,4,5,6,7,8,9,10};

    for ( int i=0 ; i<10 ; i++ ){
        assert(add(mySet,v[i])==1);
    }
    assert(size(mySet)==10);
    printf("Cantalo\n");

    int x=11;
    for ( int i=0 ; i<10 ; i++ ){
        assert(add(mySet,x )==i+1);//agrego 10 veces x
    }
    printf("Cantalo\n");

    assert(size(mySet)==11);
    int aux=count(mySet,x);
    assert(aux==10);

    for ( int i=0 ; i<(aux) ; i++ ){
        assert(removeOne(mySet,x)==(aux-1-i));
    } 

    assert(size(mySet)==10);
    assert(removeOne(mySet,x)==0);
    assert(count(mySet,x)==0);

    printf("Cantalo\n");

    removeAll(mySet,1);

    assert(size(mySet)==9);
    assert(count(mySet,1)==0);

    //lista tiene 2,3,4,5,6,7,8,9,10
    

    add(mySet,2);
    add(mySet,2);//2 tiene 3

    printf("Cantalo\n");

    add(mySet,3);
    add(mySet,3);
    add(mySet,3);//3 tiene 4

    add(mySet,4);//4 tiene 2
    
    //5,6 tiene 1

    add(mySet,7);
    add(mySet,7);//7 tiene 3

    //8,9 tiene 1
    add(mySet,10);//10 tiene 2
    add(mySet,-1);
    add(mySet,13);

    printf("Cantalo\n");

    int dim;
    int *w=minElements(mySet,&dim);
    assert(dim==6);

   /* int expectedList[]={-1,5,6,8,9,13};//para listas, porque esta ordenado ascendente
    for (size_t i = 0; i < dim; i++){
        assert(w[i]==expectedList[i]);
    }//hasta aca testlista*/

    int expectedVec[]={5,6,8,9,-1,13};//para vec (no ordenado)}
    int flagsVec[6]={0};
    int flag;
    for (size_t i=0; i < dim ; i++){
        flag=1;
        for ( size_t j=0 ; j<dim && flag ;j++){
            if ( w[i]==expectedVec[j] ){
                flagsVec[i]=1;
                flag=0;
            }
        }
    }

    for (size_t i = 0; i < dim; i++){
        assert(flagsVec[i]);   
    }
    //como no se sabe en que orden pueden salir del vector, unicamente revisamos que esten

    //es el unico test que queda diferente por si se plantea con vec o con TList
    
    free(w);
    freeMultiSet(mySet);

    printf("GOOOOLLLLL\n");

}

[marcelogarberoglio]

El multiset es lo mismo que el bag de la práctica, así que se podía resolver con vectores (guardando cada elemento nuevo al final) o con listas (guardando en forma ordenada para aprovechar que es más eficiente en una lista)
El código en general está bien.
Un par de observaciones:
-En removeOne, si lo encuentran pero con cero apariciones, igual seguís recorriendo hasta el final
-En removeAll decrementás el size, incluso si ya antes el elemento figuraba con cero apariciones (llamo dos veces seguidas a removeAll para el mismo elemento y decrementa size las dos veces)
La función minElements la discutimos en clase, y les di la idea para hacerla con un solo recorrido.