// fits.c — compara best fit, worst fit, first fit y next fit sobre la misma
// lista de huecos y la misma secuencia de peticiones.
//
// Uso:   ./fits huecos peticiones
//        huecos y peticiones: listas separadas por comas (en KB, por ejemplo)
// Ejemplo (el de las diapositivas):
//   ./fits 10,20,6,14 4,8,4,16
//
// Modelo simplificado, como malloc.py de OSTEP: no hay encabezados y los
// huecos no se fusionan. Cada petición se toma del inicio del hueco elegido.
// Desempate: ante dos huecos igual de buenos, el de menor dirección.
// Next fit sigue buscando desde el hueco donde asignó la última vez.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXN 32

enum policy { BEST, WORST, FIRST, NEXT };
static const char *names[] = {"best", "worst", "first", "next"};

static int parse(const char *s, int *v) {
    int n = 0;
    char *copy = strdup(s);
    for (char *t = strtok(copy, ","); t != NULL && n < MAXN; t = strtok(NULL, ","))
        v[n++] = atoi(t);
    free(copy);
    return n;
}

// Devuelve el índice del hueco elegido, o -1 si ninguno alcanza.
static int choose(enum policy pol, const int *hole, int nh, int req, int last) {
    int pick = -1;
    for (int k = 0; k < nh; k++) {
        int i = (pol == NEXT) ? (last + k) % nh : k;
        if (hole[i] < req)
            continue;
        if (pol == FIRST || pol == NEXT)
            return i;
        if (pick < 0 || (pol == BEST && hole[i] < hole[pick]) ||
            (pol == WORST && hole[i] > hole[pick]))
            pick = i;
    }
    return pick;
}

static void print_holes(const int *hole, int nh) {
    printf("[");
    for (int i = 0; i < nh; i++)
        printf("%s%2d", i ? " " : "", hole[i]);
    printf("]");
}

int main(int argc, char *argv[]) {
    if (argc != 3) {
        fprintf(stderr, "uso: %s huecos peticiones   (ej: %s 10,20,6,14 4,8,4,16)\n",
                argv[0], argv[0]);
        return 1;
    }
    int init[MAXN], req[MAXN];
    int nh = parse(argv[1], init), nr = parse(argv[2], req);

    // Encabezado: una columna por petición.
    printf("huecos iniciales ");
    print_holes(init, nh);
    printf("\n\npolítica ");
    for (int r = 0; r < nr; r++)
        printf(" %3d", req[r]);
    printf("   huecos al final\n");

    for (int pol = BEST; pol <= NEXT; pol++) {
        int hole[MAXN], last = 0, fails = 0;
        memcpy(hole, init, sizeof(int) * nh);
        printf("%-8s ", names[pol]);
        for (int r = 0; r < nr; r++) {
            int i = choose(pol, hole, nh, req[r], last);
            if (i < 0) {
                printf("  --");  // ningún hueco alcanza
                fails++;
                continue;
            }
            hole[i] -= req[r];
            last = i;
            printf("  h%d", i);
        }
        printf("   ");
        print_holes(hole, nh);
        if (fails > 0)
            printf("  %d sin hueco", fails);
        printf("\n");
    }
    return 0;
}