Recuperatorio Parcial 2018 2C - Ejercicio 2 (Multiset)

[IgnacioSearles]

Hola Marcelo,

Quería consultar si está bien mi resolución del ejercicio de multisets.

Me genera duda si está bien la función removeRecursive en cuanto a estilo. Para no repetir código la escribí para poder usarla en remove y removeAll.

Archivo .h:

#ifndef _EJ2_H_
#define _EJ2_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();

/* 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);

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

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

/* 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)
*/
unsigned int remove(multiSetADT multiSet, elemType elem);

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

/* 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);

#endif

Archivo .c:

#define min(a, b) (((a) < (b)) ? (a) : (b))

typedef struct node {
    elemType elem;
    unsigned int count;
    struct node* next;
} Node;

typedef Node* List;

//Ordeno la lista por count.
struct multiSetCDT {
    List first;
    unsigned int uniqueElemCount;
};

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

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

static void swapNodes(List l1, List l2) {
    unsigned int countAux = l2->count;
    l2->count = l1->count;
    l1->count = countAux;

    elemType elemAux = l2->elem;
    l2->elem = l1->elem;
    l1->elem = elemAux;
}

static unsigned int addToCount(List list, elemType elem) {
    if (list == NULL)
        return 0;

    if (compare(list->elem, elem) == 0) {
        unsigned int aux = ++list->count;

        if (list->next != NULL && list->count > list->next->count)
            swapNodes(list, list->next);

        return aux;
    }

    return addToCount(list->next, elem);
}

unsigned int add(multiSetADT multiSet, elemType elem) {
    unsigned int count = addToCount(multiSet->first, elem);

    if (count == 0) {
        List newNode = malloc(sizeof(Node));
        newNode->elem = elem;
        newNode->count = 1;

        newNode->next = multiSet->first;
        
        multiSet->first = newNode;
        multiSet->uniqueElemCount++;

        return 1;
    }

    return count;
}

static unsigned int countRecursive(const List list, elemType elem) {
    if (list == NULL)
        return 0;
    if (compare(list->elem, elem) == 0)
        return list->count;

    return countRecursive(list->next, elem);
}

unsigned int count(const multiSetADT multiSet, elemType elem) {
    return countRecursive(multiSet->first, elem);
}

/*
 *  removeAll es un parametro de entrada-salida. Si se invoca la funcion con removeAll = 1 borra todas apariciones del elem.
 *                                               Como salida indica si se borraron todas las apariciones del elem.
 */
static List removeRecursive(List list, elemType elem, unsigned int* count, int* removeAll) {
    if (list == NULL) {
        *count = 0;
        *removeAll = 0;
        return NULL;
    }

    if (compare(list->elem, elem) == 0) {
        *count = --list->count;
        
        if (list->count == 0 || *removeAll) {
            List aux = list->next;
            free(list);

            *removeAll = 1;

            return aux;
        }

        return list;
    }

    list->next = removeRecursive(list->next, elem, count, removeAll);
    
    if (list->next != NULL && list->count > list->next->count)
        swapNodes(list, list->next);
    
    return list;
}

unsigned int remove(multiSetADT multiSet, elemType elem) {
    unsigned int count;
    int removeAll = 0;

    multiSet->first = removeRecursive(multiSet->first, elem, &count, &removeAll);
    multiSet->uniqueElemCount -= removeAll;

    return count;
}

void removeAll(multiSetADT multiSet, elemType elem) {
    unsigned int count;
    int removeAll = 1;

    multiSet->first = removeRecursive(multiSet->first, elem, &count, &removeAll);
    multiSet->uniqueElemCount -= removeAll;
}

elemType* minElements(const multiSetADT multiSet, int* dim) {
    if (multiSet->first == NULL)
        return NULL;

    *dim = min(multiSet->uniqueElemCount, *dim);

    elemType* out = malloc(*dim * sizeof(elemType));

    size_t i = 0;
    for (List aux = multiSet->first; aux != NULL && i < *dim; aux = aux->next) 
        out[i++] = aux->elem;

    return out;
}

[marcelogarberoglio]

Estás tratando de mantenerlo ordenado por apariciones, pero solamente contemplás swapear con el anterior o con el siguiente, ¿que sucede si tengo tres elementos ( A, B y C) con 1 aparición y se agrega otro A ? Debería quedar después de C.
Lo mismo si tengo 3 o más con la misma repetición y se borra una aparición del último de la secuencia.
Esto se discutió en clase, y se descartó la idea de tenerlo ordenado por repeticiones.
También se discutió cómo hacer minElements con un solo recorrido.