Assignment-2/ass2.c

/* License: AGPLv3 or later. https://www.gnu.org/licenses/licenses.html
 * 
 * Assignment 2 - Discrete Simulation
 * Manish
 * Student Login: *****
 * 
 * Compile it as:
 * gcc -Wall -std=c11 -o ass2 ass2.c
 */

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

enum category
{
    TOURIST = 0,
    BUSINESS = 1,
};

typedef struct event
{
    // 0 for arrival 1+ for unique server ids
    int id;
    double time;
    int class; // 0 for tourist and 1 for business
    // service time for customer arrival and busy time for servers
    double duration;
} event;

// customers_queue is dynamically scaled
typedef struct customers_queue
{
    int first;
    int next;
    int size; // memory in use
    int capacity; // memory allocated to queue
    event* queue;
} customers_queue;

typedef struct id_busy
{
    int id; // unique server ID
    double busy; // time server was busy
} id_busy;

// servers_queue are dynamically infantilized than not re-scaled
typedef struct servers_queue
{
    int first;
    int next;
    int available;
    int capacity;
    id_busy* queue;
} servers_queue;

// Used as temporary storages for processing
event arrival;
event customer_in_queue;
id_busy server;

// Dynamically initialized than not re-scaled
event* heap;
int heap_size = 0;

customers_queue business_q;
customers_queue tourist_q;

servers_queue business_servers;
servers_queue tourist_servers;

bool dummy_arrival(const event* arrival);
int read_next_arrival(FILE* file, event* e);
void read_back_next_arrival(FILE* file, event* e);
void read_front_next_arrival(FILE* file, event* e);
void shiftdown(int i);
void shiftup(int i);
void swap(event* i, event* j);

event dequeue_customers(customers_queue* q);
void enqueue_customers(customers_queue* q, const event* e);
/* Used for sorting servers by id before printing output
 * Heap sort is used since we do not need stable sorting as all ids are unique
 * and heap sort sorts in place therefore require less memory than merge sort
 */
void server_shiftdown(servers_queue* heap, int i);
void server_makeheap(servers_queue* q);
void server_sort(servers_queue* q);
void server_swap(id_busy* i, id_busy* j);

id_busy dequeue_servers(servers_queue* q);
void enqueue_servers(servers_queue* q, const id_busy* s);
void free_server(servers_queue* q);

int max(int i, int j);

int main(void)
{
    printf("Enter file name: ");
    char filename[257];
    // Assuming filename/file path won't be longer than 256 characters
    scanf("%256s", filename);

    FILE* file = fopen(filename, "r");
    if (!file)
    {
        perror(filename);
        exit(EXIT_FAILURE);
    }

    for (int pass = 1; pass <= 2; pass++)
    {
        rewind(file); // move file pointer back to beginning

        // Read no. of business and & tourist servers
        fscanf(
            file,
            "%d %d",
            &business_servers.available,
            &tourist_servers.available);

        arrival.id = 0;
        if (read_next_arrival(file, &arrival) == EOF)
        {
            fprintf(stderr, "Error in reading 1st arrival. Exiting\n");
            return 1;
        }

        // INITIALIZE/RESET VARIABLES
        heap = malloc(
            sizeof(event)
            * (1 + business_servers.available + tourist_servers.available));

        business_servers.first = 0;
        business_servers.next = 0;
        business_servers.capacity = business_servers.available;
        business_servers.queue = malloc(
            sizeof(event) * business_servers.capacity);

        tourist_servers.first = 0;
        tourist_servers.next = 0;
        tourist_servers.capacity = tourist_servers.available;
        tourist_servers.queue = malloc(
            sizeof(event) * tourist_servers.capacity);

        if (heap == NULL
            || business_servers.queue == NULL
            || tourist_servers.queue == NULL)
        {
            fprintf(
                stderr,
                "Failed to allocate memory for all data structures\n");
            return 1;
        }

        business_q.first = 0;
        business_q.next = 0;
        business_q.size = 0;
        business_q.capacity = 0;
        // Memory is allocated only if needed
        business_q.queue = NULL;
        tourist_q.first = 0;
        tourist_q.next = 0;
        tourist_q.size = 0;
        tourist_q.capacity = 0;
        // Memory is allocated only if needed
        tourist_q.queue = NULL;

        for (int i = 0; i < business_servers.capacity; i++)
        {
            business_servers.queue[i].id = i + 1;
            business_servers.queue[i].busy = 0;
        }
        for (int i = 0; i < tourist_servers.capacity; i++)
        {
            tourist_servers.queue[i].id = i + business_servers.capacity + 1;
            tourist_servers.queue[i].busy = 0;
        }

        heap[heap_size++] = arrival;

        // Statistics Variables
        double time = 0;

        int max_q_length = 0;

        int no_of_business_customers = 0;
        double business_service_time = 0;
        double business_q_time = 0;
        int max_business_q_length = 0;

        int no_of_tourist_customers = 0;
        double tourist_service_time = 0;
        double tourist_q_time = 0;
        int max_tourist_q_length = 0;

        // MAIN LOOP
        while (heap_size > 0)
        {
            time = heap[0].time;
            if (heap[0].id == 0) // Arrival
            {
                if (heap[0].class == TOURIST)
                {
                    no_of_tourist_customers++;
                    tourist_service_time += heap[0].duration;
                    if (tourist_servers.available)
                    {
                        // Time when server will finish serving
                        heap[0].time += heap[0].duration;
                        server = dequeue_servers(&tourist_servers);
                        heap[0].id = server.id;
                        // Total busy time of server
                        heap[0].duration += server.busy;
                        shiftdown(0);
                        read_back_next_arrival(file, &arrival);
                    }
                    /* Available/free business servers will serve tourist
                     * customer in 2nd pass if no business customer in q
                     * NOTE: free server implies business_q is empty
                     */
                    else if (pass == 2 && business_servers.available)
                    {
                        // Time when server will finish serving
                        heap[0].time += heap[0].duration;
                        server = dequeue_servers(&business_servers);
                        heap[0].id = server.id;
                        // Total busy time of server
                        heap[0].duration += server.busy;
                        shiftdown(0);
                        read_back_next_arrival(file, &arrival);
                    }
                    // All relevant servers busy, add to tourist customers queue
                    else
                    {
                        enqueue_customers(&tourist_q, &heap[0]);
                        max_tourist_q_length = max(
                            max_tourist_q_length, tourist_q.size);
                        max_q_length = max(
                            max_q_length, tourist_q.size + business_q.size);
                        read_front_next_arrival(file, &arrival);
                    }
                }
                else if (heap[0].class == BUSINESS)
                {
                    no_of_business_customers++;
                    business_service_time += heap[0].duration;
                    if (business_servers.available)
                    {
                        // Time when server will finish serving
                        heap[0].time += heap[0].duration;
                        server = dequeue_servers(&business_servers);
                        heap[0].id = server.id;
                        // Total busy time of server
                        heap[0].duration += server.busy;
                        shiftdown(0);
                        read_back_next_arrival(file, &arrival);
                    }
                    // All relevant servers busy, add to tourist customers queue
                    else
                    {
                        enqueue_customers(&business_q, &heap[0]);
                        max_business_q_length = max(
                            max_business_q_length, business_q.size);
                        max_q_length = max(
                            max_q_length, tourist_q.size + business_q.size);
                        read_front_next_arrival(file, &arrival);
                    }
                }
                else
                {
                    fprintf(
                        stderr,
                        "Impossible scenario: Event = Arrival but Class = %d",
                        heap[0].class);
                    exit(1);
                }
            }
            else if ( // Business server finished serving
                heap[0].id >= 1 && heap[0].id <= business_servers.capacity)
            {
                if (business_q.size > 0) // Customers waiting in queue
                {
                    customer_in_queue = dequeue_customers(&business_q);
                    business_q_time += time - customer_in_queue.time;
                    // Time when server will finish serving
                    heap[0].time += customer_in_queue.duration;
                    // Total busy time of server
                    heap[0].duration += customer_in_queue.duration;
                    shiftdown(0);
                }
                /* Freed business servers will serve tourist customer
                 * 2nd pass if no business customer in q
                 */
                else if (pass == 2 && tourist_q.size > 0)
                {
                    customer_in_queue = dequeue_customers(&tourist_q);
                    // Time when server will finish serving
                    tourist_q_time += time - customer_in_queue.time;
                    heap[0].time += customer_in_queue.duration;
                    // Total busy time of server
                    heap[0].duration += customer_in_queue.duration;
                    shiftdown(0);
                }
                else // free server at heap[0] and enqueue to business_servers
                    free_server(&business_servers);
            }
            else if (
                heap[0].id > business_servers.capacity
                && heap[0].id <= (business_servers.capacity
                                  + tourist_servers.capacity))
            {
                if (tourist_q.size > 0) // Customers waiting in queue
                {
                    customer_in_queue = dequeue_customers(&tourist_q);
                    // Time when server will finish serving
                    tourist_q_time += time - customer_in_queue.time;
                    heap[0].time += customer_in_queue.duration;
                    // Total busy time of server
                    heap[0].duration += customer_in_queue.duration;
                    shiftdown(0);
                }
                else // free server at heap[0] and enqueue to tourist_servers
                    free_server(&tourist_servers);
            }
            else
            {
                fprintf(
                    stderr,
                    "Impossible scenario Heap[0].id = %d is out of range\n",
                    heap[0].id);
                exit(1);
            }
        }

        // COMPUTE REMAINING STATISTICS FROM TRACKED STATISTICS
        int total_customers = (
            no_of_business_customers + no_of_tourist_customers);
        double avg_q_time = (
            (business_q_time + tourist_q_time) / total_customers);
        double avg_q_length = ((business_q_time + tourist_q_time) / time);
        double avg_service_time = (
            (business_service_time
            + business_q_time
            + tourist_q_time
            + tourist_service_time)
            / total_customers);

        double avg_business_q_time = (
            business_q_time / no_of_business_customers);
        double avg_business_q_length = (business_q_time / time);
        double avg_business_service_time = (
            (business_service_time + business_q_time)
            / no_of_business_customers);

        double avg_tourist_q_time = (tourist_q_time / no_of_tourist_customers);
        double avg_tourist_q_length = (tourist_q_time / time);
        double avg_tourist_service_time = (
            (tourist_service_time + tourist_q_time) / no_of_tourist_customers);

        // SIMULATION OUTPUT/PRINT SIMULATION STATISTICS
        char pass_title[80];
        if (pass == 1)
            strncpy(
                pass_title,
                "Pass 1: Business servers exclusively serve business class",
                80);
        else if (pass == 2)
            strncpy(
                pass_title,
                "Pass 2: Idle business servers may serve tourist class",
                80);

        printf(
            "%s\n\n"
            "%-50s % 5d\n"
            "%-50s % 8.2lf\n\n"
            "%s\n"
            "%-50s % 8.2lf\n"
            "%-50s % 8.2lf\n"
            "%-50s % 8.2lf\n"
            "%-50s % 5d\n\n"
            "%s\n"
            "%-50s % 8.2lf\n"
            "%-50s % 8.2lf\n"
            "%-50s % 8.2lf\n"
            "%-50s % 5d\n\n"
            "%s\n"
            "%-50s % 8.2lf\n"
            "%-50s % 8.2lf\n"
            "%-50s % 8.2lf\n"
            "%-50s % 5d\n"
            "\n",
            pass_title,
            "Number of people served: ",
            total_customers,
            "Time last service is completed: ",
            time,
            "Business class customers: ",
            "Average total service time: ",
            avg_business_service_time,
            "Average total time in queue: ",
            avg_business_q_time,
            "Ave length of queue: ",
            avg_business_q_length,
            "Maximum number queued: ",
            max_business_q_length,
            "Tourist class customers:",
            "Average total service time: ",
            avg_tourist_service_time,
            "Average total time in queue: ",
            avg_tourist_q_time,
            "Ave length of queue: ",
            avg_tourist_q_length,
            "Maximum number queued: ",
            max_tourist_q_length,
            "All customers:",
            "Average total service time: ",
            avg_service_time,
            "Average total time in queue: ",
            avg_q_time,
            "Ave length of queue: ",
            avg_q_length,
            "Maximum number queued: ",
            max_q_length);

        // Sort servers by ID before printing
        server_sort(&business_servers);
        printf("Business class servers:\n");
        for (int i = 0; i < business_servers.capacity; i++)
            printf(
                "Total idle time for business class server %3d: %13.2lf\n",
                business_servers.queue[i].id,
                time - business_servers.queue[i].busy);

        // Sort servers by ID before printing
        server_sort(&tourist_servers);
        printf("\nTourist class servers:\n");
        for (int i = 0; i < tourist_servers.capacity; i++)
            printf(
                "Total idle time for tourist class server %3d: %14.2lf\n",
                tourist_servers.queue[i].id - business_servers.capacity,
                time - tourist_servers.queue[i].busy);

        printf("\n\n\n");

        // FREE DYNAMICALLY ALLOCATED MEMORY
        free(heap);
        free(business_servers.queue);
        free(tourist_servers.queue);
        free(business_q.queue);
        free(tourist_q.queue);
    }

    fclose(file);
    return 0;
}

bool dummy_arrival(const event* arrival)
{
    return (
        arrival->time == 0 && arrival->duration == 0);
}

int read_next_arrival(FILE* file, event* e)
{
    return fscanf(file, "%lf %d %lf", &e->time, &e->class, &e->duration);
}

void read_back_next_arrival(FILE* file, event* e)
{
    // WARNING: Potential BUG: dummy_arrival(e) gets old arrival or new?
    if (fscanf(file, "%lf %d %lf", &e->time, &e->class, &e->duration) != EOF
        && dummy_arrival(e) == false)
    {
        heap[heap_size++] = *e;
        shiftup(heap_size - 1);
    }
}

void read_front_next_arrival(FILE* file, event* e)
{
    if (fscanf(file, "%lf %d %lf", &e->time, &e->class, &e->duration) != EOF
        && dummy_arrival(e) == false)
    {
        heap[0] = *e;
    }
    else
    { // Since dummy arrival or EOF reached, pop heap[0]
        swap(&heap[0], &heap[--heap_size]);
    }
    shiftdown(0);
}

void shiftdown(int i)
{
    int child = (i * 2) + 1; // left child
    if (child < heap_size) // has at least one child
    {
        if (child < heap_size - 1) // has both children
        {
            // if right child smaller
            if (heap[child].time > heap[child + 1].time)
                child++; // pick right child
        }
        if (heap[i].time > heap[child].time)
        {
            swap(&heap[i], &heap[child]);
            shiftdown(child);
        }
    }
}

void shiftup(int i)
{
    if (i == 0)
        return;
    int parent = (i - 1) / 2;
    if (heap[parent].time > heap[i].time)
    {
        swap(&heap[parent], &heap[i]);
        shiftup(parent);
    }
}

void swap(event* i, event* j)
{
    event tmp = *i;
    *i = *j;
    *j = tmp;
}

event dequeue_customers(customers_queue* q)
{
    if (q->size-- == 0)
    {
        fprintf(
            stderr,
            "Impossible scenario: dequeue_customers when queue empty");
        exit(1);
    }
    event customer = q->queue[q->first++];
    q->first %= q->capacity;
    if (q->size < q->capacity / 4)
    {
        int new_capacity = (q->capacity / 2) + (q->capacity % 2);
        if (q->size != 0
            && (q->first >= new_capacity || q->next >= new_capacity))
        {
            /* Original queue:
             * XX--------|-------XXX
             * OR
             * --------XX|XXX-------
             * OR
             * -----------|-XXXXX----
             * Where X has some number, - is empty place & | is new_capacity
             * Than, copy queue to next location and free old space
             */
            event* new_q = malloc(sizeof(event) * new_capacity);
            if (new_q == NULL)
            {
                fprintf(
                    stderr,
                    "Failed to reallocate memory for customer_queue\n");
                exit(1);
            }
            int j = 0;
            for (int i = q->first; i != q->next; i = (i + 1) % q->capacity)
            {
                new_q[j++] = q->queue[i];
            }
            free(q->queue);
            q->queue = new_q;
            q->first = 0;
            q->next = j;
        }
        else
        {
            q->queue = realloc(q->queue, sizeof(event) * new_capacity);
            if (q->queue == NULL) // Probably unnecessary since shrinking
            {
                fprintf(
                    stderr, "Failed to reallocate memory for customer_queue\n");
                exit(1);
            }
            if (q->size == 0)
            {
                q->first = 0;
                q->next = 0;
            }
        }
        q->capacity = new_capacity;
    }
    return customer;
}

void enqueue_customers(customers_queue* q, const event* e)
{
    if (q->size == q->capacity) // Queue full
    {
        // Double queue and adjust pointers
        // max() for when no space allocated previously i.e. capacity == 0
        int new_capacity = max(q->capacity * 2, 1);
        q->queue = realloc(q->queue, sizeof(event) * new_capacity);
        if (q->queue == NULL)
        {
            fprintf(
                stderr, "Failed to reallocate memory for customer_queue\n");
            exit(1);
        }
        if (q->first != 0)
        {
            /* Original queue:
             * XXX|XXXXXXX
             * After realloc:
             * XX|XXXXXXXX----------
             * After this loop:
             * XX----------|XXXXXXXX
             * Where X has some number, - is empty place
             * and | is q->first pointer
             */
            for (int i = q->first; i < q->capacity; i++)
            {
                q->queue[i + q->capacity] = q->queue[i];
            }
            q->first += q->capacity;
        }
        /// MISSING THIS CORNER CASE WAS CAUSE OF A MAJOR BUG
        else
            q->next = q->size;

        q->capacity = new_capacity;
    }
    q->size++;
    q->queue[q->next++] = *e;
    q->next %= q->capacity;
}

id_busy dequeue_servers(servers_queue* q)
{
    if (q->available-- == 0)
    {
        fprintf(
            stderr,
            "Impossible scenario: dequeue_servers when queue empty");
        exit(1);
    }
    server = q->queue[q->first++];
    q->first %= q->capacity;
    return server;
}

void enqueue_servers(servers_queue* q, const id_busy* s)
{
    if (q->available++ == q->capacity)
    {
        fprintf(
            stderr, "Impossible scenario: enqueue_servers when queue full");
        exit(1);
    }
    q->queue[q->next++] = *s;
    q->next %= q->capacity;
}

void free_server(servers_queue* q)
{
    server.id = heap[0].id;
    server.busy = heap[0].duration;
    enqueue_servers(q, &server);
    heap[0] = heap[--heap_size];
    shiftdown(0);
}

int max(int i, int j)
{
    return (i > j) ? i : j;
}

void server_shiftdown(servers_queue* heap, int i)
{
    int child = (i * 2) + 1; // left child
    if (child < heap->available) // has at least one child
    {
        if (child < heap->available - 1) // has both children
        {
            // if right child smaller
            if (heap->queue[child].id < heap->queue[child + 1].id)
                child++; // pick right child
        }
        if (heap->queue[i].id < heap->queue[child].id)
        {
            server_swap(&heap->queue[child], &heap->queue[i]);
            server_shiftdown(heap, child);
        }
    }
}

void server_makeheap(servers_queue* q)
{
    // Shiftdown Method
    int shiftdowns_required = (q->capacity / 2)-1;
    for (int i = shiftdowns_required; i >= 0; i--)
    {
        server_shiftdown(q, i);
    }
}

void server_sort(servers_queue* q)
{
    server_makeheap(q);
    while(q->available > 0)
    {
        server_swap(q->queue, &q->queue[--q->available]);
        server_shiftdown(q, 0);
    }
    q->available = q->capacity;
}

void server_swap(id_busy* i, id_busy* j)
{
    id_busy tmp = *i;
    *i = *j;
    *j = tmp;
}