BufferADT

[Pablo-Goros]

Buenas como va? Queria consultar si esta bien resuelto el siguiente ejercicio, hice un test y lo pasa. Queria saber si estaba bien el uso del 'last'.

#include "bufferADT.h"
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    elemType head;
    struct Node *tail;
} Node;

typedef struct Node *List;

typedef struct bufferCDT {
    List first;
    List last;
    size_t max;
    size_t size;
} bufferCDT;

/* Crea el buffer que tendrá un tamaño máximo dado por el parámetro max 
** El TAD almacenará como máximo max elementos de tipo elemType
*/
bufferADT newBuffer(size_t max) {
    bufferADT aux = calloc(1, sizeof(bufferCDT));
    aux->max = max;
    return aux;
}

static void freeBufferRec(List list) {
    if (list == NULL) {
        return;
    }

    freeBufferRec(list->tail);
    free(list);
}

void freeBuffer(bufferADT buffer) {
    freeBufferRec(buffer->first);
    free(buffer);
}

static List goToEnd(List list) {
    if (list == NULL) {
        return NULL;
    }

    if (list->tail == NULL) {
        return list;
    }

    return goToEnd(list->tail);
}

static List writeRec(List list, const elemType *vec, size_t dim) {
    if (dim == 0) {
        return NULL; 
    }

    List newNode = malloc(sizeof(Node));
    newNode->head = *vec;

    newNode->tail = writeRec(NULL, vec+1, dim-1);
    return newNode;
}

/* Agrega al final del buffer una cantidad de elementos que se 
** encuentran almacenados a partir de from. 
** La cantidad de elementos a agregar es dim
** Retorna la cantidad de elementos  que se pudieron agregar
*/
size_t write(bufferADT buffer, const elemType * from, size_t dim) {
    size_t allowedWrite = buffer->max - buffer->size; // calculo cuantos elems puedo agregar al buffer
    dim = allowedWrite < dim ? allowedWrite : dim; // uso el mas chico

    if (dim == 0) {
        return 0;
    }

    List lastAux = writeRec(NULL, from, dim);

    if (buffer->first == NULL) { // si todavia no hay ningun elemento
            buffer->first = lastAux; 
            buffer->last = goToEnd(buffer->first); // solo se usaria la fn cuando el buffer esta vacio
    } else {
            buffer->last->tail = lastAux; // conecto al final del buffer lo nuevo
    }

    buffer->size += dim;

    return dim;
}

static List readRec(List list, elemType *vec, size_t size) {
    if (size == 0) { //! pq esta llegando a list = NULL antes q size = 0???
        puts("Size = 0");
        return list;
    } else if (list == NULL) {
        puts("List = NULL");
        printf("Todavia tengo un size de: %ld\n", size);
        return list;
    }

    *vec = list->head;
    List aux = list->tail;
    free(list);
    return readRec(aux, vec+1, size-1);
}

/* Almacena a partir de la dirección target los primeros n elementos del buffer.
** En caso de haber menos elementos almacena los que quedan en el buffer
** Retorna la cantidad de elementos que pudo almacenar
** Los elementos que se almacenan en target son eliminados del buffer
*/
size_t read(bufferADT buffer, elemType * target, size_t dim) {
    dim = buffer->size < dim ? buffer->size : dim;

    buffer->first = readRec(buffer->first, target, dim);

    if (buffer->first == NULL) { // si vacie el buffer, tengo que hacer que el ultimo no apunte a memoria liberada
        buffer->last = NULL;
    }

    buffer->size -= dim;

    return dim;
}

/* Retorna la cantidad de elementos almacenados en el buffer */
size_t size(const bufferADT buffer) {
    return buffer->size;
}

/* Limpia el buffer, dejándolo vacío */
void clear(bufferADT buffer) {
    freeBufferRec(buffer->first);
    buffer->first = NULL;
    buffer->size = 0;
}

static void copyRec(List list, elemType *vec, size_t size) {
    if (size == 0 || list == NULL) {
        return;
    }

    *vec = list->head;

    copyRec(list->tail, vec+1, size-1);
}
/* Almacena a partir de la dirección target los primeros n elementos del buffer.
** En caso de haber menos elementos almacena los que quedan en el buffer
** Retorna la cantidad de elementos que pudo almacenar
** Los elementos que se almacenan en target NO son eliminados del buffer
*/
size_t copy(bufferADT buffer, elemType *target, size_t dim) {
    dim = buffer->size < dim ? buffer->size : dim;

    copyRec(buffer->first, target, dim);

    return dim;
}

Programa de testeo:

int main(void) {
    bufferADT buffer = newBuffer(5); // Create a buffer with max size 5
    assert(buffer != NULL);

    elemType data1[] = {1, 2, 3};
    size_t written = write(buffer, data1, 3);
    assert(written == 3); // Should write all 3 elements
    assert(size(buffer) == 3); // Buffer size should be 3

    elemType data2[] = {4, 5, 6};
    written = write(buffer, data2, 3);
    assert(written == 2); // Should only write 2 elements as buffer is full
    assert(size(buffer) == 5); // Buffer size should be 5

    elemType readData[5];
    size_t readCount = read(buffer, readData, 5);
    assert(readCount == 5); // Should read all 5 elements
    assert(size(buffer) == 0); // Buffer should be empty

    for (size_t i = 0; i < readCount; ++i) {
        printf("%d ", readData[i]); // Should print 1 2 3 4 5
    }
    printf("\n");

    elemType data3[] = {7, 8, 9, 10, 11};
    written = write(buffer, data3, 5);
    assert(written == 5); // Should write all 5 elements
    assert(size(buffer) == 5); // Buffer size should be 5

    elemType copyData[5];
    size_t copyCount = copy(buffer, copyData, 5);
    assert(copyCount == 5); // Should copy all 5 elements
    assert(size(buffer) == 5); // Buffer size should still be 5

    for (size_t i = 0; i < copyCount; ++i) {
        printf("%d ", copyData[i]); // Should print 7 8 9 10 11
    }
    printf("\n");

    clear(buffer);
    assert(size(buffer) == 0); // Buffer should be empty after clear

    freeBuffer(buffer);
    printf("All tests passed successfully.\n");

    return 0;
}

[marcelogarberoglio]

Cuando se tomó este ejercicio se había discutido en clase cómo hacer una queue pero de tamaño máximo. Al resolverlo lo hicimos con un vector creado en el new, con el tamaño máximo, en el cual se mantiene el índice del primero y el índice del último. Se termina haciendo un uso circular del vector, por ejemplo si se encolan 5 elementos, el first está en 0 y last en 4, al desencolar 2, se cambia first por el valor 2. Si el temaño máximo fuera 10 elementos (índice 0 a 9) y se encolan 6, entonces first sigue en 2 y last está en 0, y sólo hay lugar para encolar uno más. Como en clase se había discutido ese ejercicio, después en el parcial se tomó este del buffer, que es lo mismo que la cola de tamaño fijo pero con la variante que se "encolan" o "desencolan" varios elementos a la vez. Conclusión: no tomaríamos un ejercicio como este en este cuatrimestre porque la forma correcta de hacerlo no la discutimos.

[Pablo-Goros]

Ahhh nunca se me hubiera ocurrido eso. Gracias por la aclaracion. Mas alla de que no lo tomarian, queria sabe si estaba bien planteada la idea, mas que nada la parte del last y de como uso goToEnd.

[marcelogarberoglio]

No le veo muicho sentido a goToEnd, si se hiciera con una lista sería como una cola: un puntero al primero (para desencolar) y un puntero al último (para encolar). En ningún momento tendrían que estar recorriendo la cola.