// Arup Guha
// 8/30/2023
// Solution to COP 3502 Fall 2023 Program 1: Assigned Seating

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

#define INITSIZE 10
#define MAXLEN 50
#define MAXROWS 100000

typedef struct order {
    int s_seat;
    int e_seat;
    char* name;
} order;

typedef struct theaterrow {
    order** list_orders;
    int max_size;
    int cur_size;
} theaterrow;

order* make_order(int start, int end, char* this_name);
theaterrow* make_empty_row();
int conflict(order* order1, order* order2);
int contains(order* myorder, int seat_no);
int can_add_order(theaterrow* this_row, order* this_order);
void add_order(theaterrow* this_row, order* this_order);
char* get_owner(theaterrow** theater, int row, int seat_num);
char* get_row_owner(theaterrow* this_row, int seat_num);
void free_order(order* this_order);
void free_row(theaterrow* this_row);

int main() {

    // Build the theater.
    theaterrow** amc = calloc(MAXROWS+1, sizeof(theaterrow*));
    for (int i=0; i<=MAXROWS; i++)
        amc[i] = make_empty_row();

    // Get first command.
    char cmd[MAXLEN+1];
    scanf("%s", cmd);

    // Loop until it's quit.
    while (strcmp(cmd, "QUIT")) {

        // Execute a buy
        if (strcmp(cmd, "BUY") == 0) {

            // Read in info for buy.
            int myrow, start, end;
            char name[MAXLEN+1];
            scanf("%d%d%d%s", &myrow, &start, &end, name);

            // Create this order.
            order* tmp = make_order(start, end, name);
            int cando = can_add_order(amc[myrow], tmp);

            // Great, let's add it.
            if (cando) {
                add_order(amc[myrow], tmp);
                printf("SUCCESS\n");
            }

            // Sorry, it can't be added, so free this memory.
            else {
                free_order(tmp);
                printf("FAILURE\n");
            }
        }

        // Execute a lookup
        else if (strcmp(cmd, "LOOKUP") == 0) {

            // Get query.
            int myrow, myseat;
            scanf("%d%d", &myrow, &myseat);
            char* res = get_owner(amc, myrow, myseat);

            // Output result appropriately.
            if (res == NULL)
                printf("No one\n");
            else
                printf("%s\n", res);
        }

        // Get next command.
        scanf("%s", cmd);
    }

    // Free memory.
    for (int i=0; i<=MAXROWS; i++)
        free_row(amc[i]);
    free(amc);

    return 0;
}

// Returns a pointer to a dynamically allocated order storing
// the given start row, end row, and the name this_name. Note:
// strcpy should be used to copy the contents into the struct
// after its name field is dynamically allocated.
order* make_order(int start, int end, char* this_name) {

    // Make room.
    order* tmp = malloc(sizeof(order));

    // Fill components, making sure string is allocated for right size.
    tmp->s_seat = start;
    tmp->e_seat = end;
    tmp->name = malloc( (strlen(this_name)+ 1)*sizeof(char));
    strcpy(tmp->name, this_name);

    // Return ptr to struct.
    return tmp;
}

// This function will allocate the memory for one theaterrow,
// including allocating its array of orders to a default maximum
// size of 10, and setting its current size to 0.
theaterrow* make_empty_row() {

    // Make room, set init size and current size.
    theaterrow* tmp = malloc(sizeof(theaterrow));
    tmp->list_orders = calloc(INITSIZE, sizeof(order*));
    tmp->max_size = INITSIZE;
    tmp->cur_size = 0;

    // Not necessary for correct solution, but just being safe.
    for (int i=0; i<INITSIZE; i++)
        tmp->list_orders[i] = NULL;

    return tmp;
}

// Pre-condition: Assumes order1 and order2 are pointing to orders on the same row.
// Post-condition: Returns 1 if both orders have at least one seat in common, meaning
//                 that the orders are conflicting orders. Returns 0 otherwise.
int conflict(order* order1, order* order2) {

    // Only 2 ways there is no conflict.
    if (order1->e_seat < order2->s_seat) return 0;
    if (order2->e_seat < order1->s_seat) return 0;

    // If we get here, there is a conflict.
    return 1;
}

// Pre-condition: Assumes the query about seat_no is about the same row as the order myorder is pointing to is made on.
// Returns 1 if sean_no is contained in the range of orders in myorder, and false other wise.
int contains(order* myorder, int seat_no) {
    return seat_no >= myorder->s_seat && seat_no <= myorder->e_seat;
}

// Returns 1 if the order pointed to by this_order can be
// added to the row pointed to by this_row. Namely, 1 is returned
// if and only if this_order does NOT have any seats in it that
// are part of any order already on this_row.
int can_add_order(theaterrow* this_row, order* this_order) {

    // Loop through each order ont his row.
    for (int i=0; i<this_row->cur_size; i++)

        // If we ever find a conflict, we can't add this.
        if (conflict(this_row->list_orders[i], this_order))
            return 0;

    // If we get here, we're good.
    return 1;
}

// This function tries to add this_order to this_row. If
// successful, the order is added and 1 is returned. Otherwise,
// 0 is returned and no change is made to this_row. If the memory
// for this_row is full, this function will double the maximum #
// of orders allocated for the row (via realloc), before adding
// this_order, and adjust max_size and cur_size of this_row.
void add_order(theaterrow* this_row, order* this_order) {

    // Time to grow!
    if (this_row->cur_size == this_row->max_size) {
        this_row->max_size *= 2;
        this_row->list_orders = realloc(this_row->list_orders, this_row->max_size*sizeof(order*));
    }

    // Add this order to this row. Update current size.
    this_row->list_orders[this_row->cur_size] = this_order;
    this_row->cur_size++;
}

// If seat_num seat number in row number row is occupied,
// return a pointer to the string storing the owner’s name.
// If no one is sitting in this seat, return NULL.
char* get_owner(theaterrow** theater, int row, int seat_num) {

    // Just go to the appropriate row.
    return get_row_owner(theater[row], seat_num);
}

// If seat_num in the row pointed to by this_row is occupied,
// return a pointer to the string storing the owner’s name.
// If no one is sitting in this seat, return NULL.
char* get_row_owner(theaterrow* this_row, int seat_num) {

    // Go through each order. If we find an order with this seat, return its owner.
    for (int i=0; i<this_row->cur_size; i++)
        if (contains(this_row->list_orders[i], seat_num))
            return this_row->list_orders[i]->name;

    // No one found.
    return NULL;
}

// Frees all memory associated with this_order.
void free_order(order* this_order) {
    free(this_order->name);
    free(this_order);
}

// Frees all memory associated with this_row.
void free_row(theaterrow* this_row) {
    for (int i=0; i<this_row->cur_size; i++)
        free_order(this_row->list_orders[i]);
    free(this_row->list_orders);
    free(this_row);
}