// disksched.c — planificación de disco sobre una misma cola de pedidos.
//
// Uso: ./disksched            orden y costo de cada algoritmo
//      ./disksched detalle    además, el costo de cada pedido desde el inicio
//
// Compara FCFS, SSTF, SCAN, C-SCAN y SPTF con un modelo simple de disco:
//   pistas 0..99; el cabezal empieza en la pista START, subiendo
//   búsqueda(d)    = 0 si d = 0; si no, SEEK_BASE + SEEK_PER_TRACK * d  (ms)
//   rotación       = 10 000 RPM: una vuelta en 6 ms, 60 grados por ms
//   transferencia  = XFER ms por pedido
// Cada pedido es (pista, ángulo): el ángulo dice cuántos grados le faltan
// al sector para pasar bajo el cabezal en el instante 0.
// SCAN llega hasta la pista 99 y regresa. C-SCAN llega hasta la 99, vuelve a
// la 0 sin atender (ese viaje cuenta) y sigue subiendo.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define NREQ 8
#define MAXTRACK 99
#define START 50
#define SEEK_BASE 0.5
#define SEEK_PER_TRACK 0.05
#define DEG_PER_MS 60.0
#define XFER 0.1

struct req {
    int track;
    double angle;
};

// La cola, en orden de llegada.
static const struct req queue[NREQ] = {
    {85, 300}, {20, 90}, {58, 330}, {93, 150},
    {41, 30}, {10, 240}, {67, 120}, {46, 200},
};

struct state {
    int track;      // pista actual del cabezal
    double t;       // tiempo actual (ms)
    int moved;      // pistas recorridas en total
};

static double seek_ms(int d) {
    d = abs(d);
    return d == 0 ? 0 : SEEK_BASE + SEEK_PER_TRACK * d;
}

// Espera rotacional si llegamos a la pista en el instante t.
static double rot_wait(double angle, double t) {
    double left = angle - DEG_PER_MS * t;
    left -= 360.0 * (long)(left / 360.0);
    if (left < 0)
        left += 360.0;
    return left / DEG_PER_MS;
}

// Mover el cabezal a una pista sin atender nada (fin de SCAN y C-SCAN).
static void move_to(struct state *s, int track) {
    s->t += seek_ms(track - s->track);
    s->moved += abs(track - s->track);
    s->track = track;
}

// Costo (ms) de atender r desde el estado s.
static double cost(const struct state *s, const struct req *r) {
    double seek = seek_ms(r->track - s->track);
    return seek + rot_wait(r->angle, s->t + seek) + XFER;
}

static void serve(struct state *s, const struct req *r) {
    double c = cost(s, r);
    s->moved += abs(r->track - s->track);
    s->track = r->track;
    s->t += c;
    printf(" %d", r->track);
}

static void finish(const struct state *s) {
    printf(" | %3d pistas, %5.2f ms\n", s->moved, s->t);
}

static void fcfs(void) {
    struct state s = {START, 0, 0};
    printf("FCFS   :");
    for (int i = 0; i < NREQ; i++)
        serve(&s, &queue[i]);
    finish(&s);
}

// Elegir el pendiente que minimiza la distancia (SSTF) o el tiempo (SPTF).
static void greedy(const char *name, int by_time) {
    struct state s = {START, 0, 0};
    int done[NREQ] = {0};
    printf("%-7s:", name);
    for (int k = 0; k < NREQ; k++) {
        int best = -1;
        double best_v = 1e9;
        for (int i = 0; i < NREQ; i++) {
            if (done[i])
                continue;
            double v = by_time ? cost(&s, &queue[i])
                               : abs(queue[i].track - s.track);
            if (v < best_v) {
                best_v = v;
                best = i;
            }
        }
        done[best] = 1;
        serve(&s, &queue[best]);
    }
    finish(&s);
}

static int by_track(const void *a, const void *b) {
    return ((const struct req *)a)->track - ((const struct req *)b)->track;
}

static void scan(int circular) {
    struct req sorted[NREQ];
    memcpy(sorted, queue, sizeof sorted);
    qsort(sorted, NREQ, sizeof sorted[0], by_track);
    struct state s = {START, 0, 0};
    printf("%-7s:", circular ? "C-SCAN" : "SCAN");
    for (int i = 0; i < NREQ; i++)          // subiendo
        if (sorted[i].track >= START)
            serve(&s, &sorted[i]);
    move_to(&s, MAXTRACK);                  // hasta el borde
    if (circular) {
        move_to(&s, 0);                     // regreso sin atender
        printf(" (99->0)");
        for (int i = 0; i < NREQ; i++)      // subiendo otra vez
            if (sorted[i].track < START)
                serve(&s, &sorted[i]);
    } else {
        for (int i = NREQ - 1; i >= 0; i--) // bajando
            if (sorted[i].track < START)
                serve(&s, &sorted[i]);
    }
    finish(&s);
}

// Primera decisión: cuánto cuesta cada pedido desde el estado inicial.
static void detail(void) {
    struct state s = {START, 0, 0};
    printf("desde la pista %d en t = 0:\n", START);
    for (int i = 0; i < NREQ; i++) {
        const struct req *r = &queue[i];
        double seek = seek_ms(r->track - s.track);
        double rot = rot_wait(r->angle, seek);
        printf("  pista %2d: %2d pistas, búsqueda %.2f + rotación %.2f"
               " + transf. %.1f = %.2f ms\n", r->track,
               abs(r->track - START), seek, rot, XFER, seek + rot + XFER);
    }
}

int main(int argc, char *argv[]) {
    printf("cola (pista/ángulo):");
    for (int i = 0; i < NREQ; i++)
        printf(" %d/%.0f", queue[i].track, queue[i].angle);
    printf("\ncabezal en la pista %d, subiendo\n", START);
    fcfs();
    greedy("SSTF", 0);
    scan(0);
    scan(1);
    greedy("SPTF", 1);
    if (argc > 1 && strcmp(argv[1], "detalle") == 0)
        detail();
    return 0;
}