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

/**
 * @brief Find largest rectangle for a new window in a canvas with some existing windows.
 * @param width Canvas width in pixel
 * @param height Canvas height in pixel
 * @param objects Existing objects, in the form {{x_topleft,y_topleft,x_bottomright_y_bottomright},...}
 * @param num_objects Number of objects in previous parameter
 * @param output Array to store result as {x_topleft,y_topleft,x_bottomright_y_bottomright}
 */
void find_largest_rect(int width, int height, int (*objects)[4],
                       int num_objects, int* output) {
    // create canvas array
    unsigned char* canvas = (unsigned char*)malloc(width * height * sizeof(
                                unsigned char));
    int* up         = (int*)malloc(width * sizeof(int));
    int* up_last    = (int*)malloc(width * sizeof(int));
    int* left       = (int*)malloc(width * sizeof(int));
    int* left_last  = (int*)malloc(width * sizeof(int));
    int* right      = (int*)malloc(width * sizeof(int));
    int* right_last = (int*)malloc(width * sizeof(int));
    int ans = 0, lo = 0, ro = 0;
    int x1 = 0, y1 = 0, x2 = 0, y2 = 0;
    int i = 0, j = 0, k = 0;

    // set whole canvas to 1
    for (i = 0; i < height; i++)
        for (j = 0; j < width; j++) {
            canvas[i * (width) + j] = 1;
        }

    // initialize temp vars
    for (j = 0; j < width; j++) {
        up[j] = 0;
        up_last[j] = 0;
        left[j] = 0;
        left_last[j] = 0;
        right[j] = 0;
        right_last[j] = 0;
    }

    // set occupied points to 0
    for (i = 0; i < num_objects; i++) {
        x1 = objects[i][0];
        y1 = objects[i][1];
        x2 = objects[i][2];
        y2 = objects[i][3];

        // boundary check
        x1 = x1 < 0 ? 0 : (x1 > width ? width : x1);
        y1 = y1 < 0 ? 0 : (y1 > height ? height : y1);
        x2 = x2 < 0 ? 0 : (x2 > width ? width : x2);
        y2 = y2 < 0 ? 0 : (y2 > height ? height : y2);

        for (j = y1; j <= y2; j++) {
            for (k = x1; k <= x2; k++) {
                canvas[j * (width) + k] = 0;
            }
        }
    }

    x1 = 0, y1 = 0, x2 = 0, y2 = 0;

    for (i = 0; i < height; i++) {
        lo = -1;
        ro = width;

        // store last temp vars
        for (j = 0; j < width; j++) {
            up_last[j] = up[j];
            left_last[j] = left[j];
            right_last[j] = right[j];
        }

        // initialize up[] and left[] for current i
        for (j = 0; j < width; j++) {
            if (canvas[i * width + j] == 0) {
                left[j] = up[j] = 0;
                lo = j;
            }
            else {
                up[j] = (i == 0) ? 1 : up_last[j] + 1;
                left[j] = (i == 0) ? lo + 1 : ((left_last[j] > lo + 1) ?
                                               left_last[j] : lo + 1);
            }
        }

        for (j = width - 1; j >= 0; j--) {
            if (canvas[i * width + j] == 0) {
                right[j] = width;
                ro = j;
            }
            else {
                right[j] = (i == 0) ? ro - 1 : ((right_last[j] < ro - 1) ?
                                                right_last[j] : ro - 1);
            }

            if (up[j] * (right[j] - left[j] + 1) > ans) {
                ans = up[j] * (right[j] - left[j] + 1);
                x1 = left[j];
                y1 = i - up[j] + 1;
                x2 = j;
                y2 = i;
            }
        }
    }

    output[0] = x1;
    output[1] = y1;
    output[2] = x2;
    output[3] = y2;

    printf("Max rectangle area = %d\n", ans);

    // print canvas
    //    for (i = 0; i < height; i++) {
    //        printf("%d\t", i);

    //        for (j = 0; j < width; j++) {
    //            printf("%d", *(canvas + i * (width) + j));
    //        }

    //        printf("\n");
    //    }

    free(canvas);
    free(up);
    free(up_last);
    free(left);
    free(left_last);
    free(right);
    free(right_last);
}

int main(void) {
    //canvas properties
    int width = 30;
    int height = 20;

    // objects in canvas
    int num_objects = 3;
    int objects[3][4] = {{0, 0, 9, 9}, {20, 0, 29, 19}, {5, 14, 14, 18}};

    // var to store result coordinates of topleft and bottomright vertices (x1,y1,x2,y2)
    int output[4] = {0, 0, 0, 0};

    find_largest_rect(width, height, objects, num_objects, output);

    printf("(%d,%d)->(%d,%d)\n", output[0], output[1], output[2], output[3]);

    return 0;
}