[HaBo]

#include <stdio.h>
#include <stdlib.h>
#ifndef XALLOC_H
    #include "xalloc.h"
#endif
#include "voidStack.h"

typedef struct {
    int x1, y1, x2, y2;     /* with x2 > x1 and y2 > y1 */
} rect;

typedef struct {
    int **f;
    rect *r;        /* the rect describing the field */
    int xdim, ydim; /* redundant, since those infos are already contained within
                       the supplied rect, but it's easier to read that way.. */
} field;

void printField(field *f);

field *createField(int xdim, int ydim);
void delField(field *f);
void setField(field *f, rect *r, int val);
void copyField(field *src, field *dest);
int isFree(field *f, rect *r);      /* returns 1 if the area described by rect is all zeros in field */
int getFreeCount(field *f);
rect *getBiggestFree(field *f);     /* gets biggest free rect in field *f */
stack getAllFree(field *f, rect *r);
void fillField(field *f, rect *r);
int fillFieldRec(field *f, rect *r, int rectcount, int *max, field *sol);

rect *createRect(int startx, int starty, int xsize, int ysize);
void copyRect(rect *src, rect *dest);
void setRect(rect *r, int x1, int y1, int x2, int y2);
int getArea(rect *r);
void delRect(rect *r);
void moveRect(rect *r, int x, int y);
void resizeRect(rect *r, int xsize, int ysize);
void rotateRect(rect *r);           /* rotates *r by 90 degrees. (the top left corner will be the same) */
int isInRect(rect *r, int x, int y);
int isSubRect(rect *r, rect *sub);
int areCongruent(rect *r, rect *s);



void fillField(field *f, rect *r) {
    int max = 0;
    field *solution = createField(f->xdim, f->ydim);
    fillFieldRec(f, r, 1, &max, solution);
    printField(solution);
}

int fillFieldRec(field *f, rect *r, int rectcount, int *max, field *sol) {
    stack p = getAllFree(f, r);
    rect *new = shift(p);
    if (new == NULL) {
        destroyStack(p);
        if (rectcount > *max) {
            *max = rectcount;
            copyField(f, sol);
            if (getFreeCount(f) < getArea(r)) {
                return 1;
            }
            printField(f);  /* print intermediate solutions */
        }
        return 0;
    }
    while (new != NULL) {
        setField(f, new, rectcount);
        if (fillFieldRec(f, r, rectcount + 1, max, sol)) {
            return 1;
        }
        setField(f, new, 0);
        delRect(new);
        new = shift(p);
    }
    destroyStack(p);
    return 0;
}

rect *createRect(int startx, int starty, int xsize, int ysize) {
    rect *r = xmalloc(sizeof(rect));
    r->x1 = startx;
    r->y1 = starty;
    r->x2 = startx + xsize - 1;
    r->y2 = startx + ysize - 1;
    return r;
}

void delRect(rect *r) {
    free(r);
}

void setRect(rect *r, int x1, int y1, int x2, int y2) {
    r->x1 = x1;
    r->y1 = y1;
    r->x2 = x2;
    r->y2 = y2;
}

void copyRect(rect *src, rect *dest) {
    /* sets *dest to describe the same area as *src */
    dest->x1 = src->x1;
    dest->y1 = src->y1;
    dest->x2 = src->x2;
    dest->y2 = src->y2;
}

int getArea(rect *r) {
    return ( ((r->x2 - r->x1) + 1) * ((r->y2 - r->y1) + 1) );
}

void resizeRect(rect *r, int xsize, int ysize) {
    r->x2 = r->x1 + xsize;
    r->y2 = r->y1 + ysize;
}

void moveRect(rect *r, int x, int y) {
    int xsize, ysize;
    xsize = r->x2 - r->x1;
    ysize = r->y2 - r->y1;
    r->x1 = x;
    r->y1 = y;
    resizeRect(r, xsize, ysize);
}

void rotateRect(rect *r) {
    /* rotates *r by 90 degrees. (the top left corner will stay the same) */
    int xsize, ysize;
    xsize = r->x2 - r->x1;
    ysize = r->y2 - r->y1;
    resizeRect(r, ysize, xsize);
}

field *createField(int xdim, int ydim) {
    int *rows = xmalloc(xdim * ydim * sizeof(int));
    int **cols = xmalloc(ydim * sizeof(int *));
    int i;
    for (i = 0; i < ydim; i++) {
        cols[i] = &rows[i * xdim];
    }
    rect *r = xmalloc(sizeof(rect));
    r->x1 = 0;
    r->y1 = 0;
    r->x2 = xdim - 1;
    r->y2 = ydim - 1;
    field *f = xmalloc(sizeof(field));
    f->f = cols;
    f->r = r;
    f->xdim = xdim;
    f->ydim = ydim;
    setField(f, f->r, 0);
    return f;
}

void delField(field *f) {
    free(f->r);
    int i;
    for (i = 0; i < f->ydim; i++) {
        free(f->f[i]);
    }
    free(f->f);
    free(f);
}

void setField(field *f, rect *r, int val) {
    if (! isSubRect(f->r, r)) {
        return;
    }
    int x, y;
    for (y = r->y1; y <= r->y2; y++) {
        for (x = r->x1; x <= r->x2; x++) {
            f->f[y][x] = val;
        }
    }
}

void copyField(field *src, field *dest) {
    int x, y;
    for (y = 0; (y < src->ydim && y < dest->ydim); y++) {
        for (x = 0; (x < src->xdim && x < dest->xdim); x++) {
            dest->f[y][x] = src->f[y][x];
        }
    }
}

int isFree(field *f, rect *r) {
    /* returns true if the area described by *r is all zeros in *f */
    if (! isSubRect(f->r, r)) {
        return 0;
    }
    int x, y;
    for (y = r->y1; y <= r->y2; y++) {
        for (x = r->x1; x <= r->x2; x++) {
            if (f->f[y][x]) {
                /* nonzero */
                return 0;
            }
        }
    }
    return 1;
}

int getFreeCount(field *f) {
    int x, y, count = 0;
    for (y = 0; y < f->ydim; y++) {
        for (x = 0; x < f->xdim; x++) {
            if (f->f[y][x] == 0) {
                count++;
            }
        }
    }
    return count;
}

rect *getBiggestFree(field *f) {
    int x1, y1, x2, y2, size, maxsize;
    rect *tmp = createRect(0, 0, 1, 1);
    rect *max = createRect(0, 0, 1, 1);
    maxsize = 0;
    for (x1 = 0; x1 < f->xdim; x1++) {
    for (y1 = 0; y1 < f->ydim; y1++) {
    for (x2 = x1; x2 < f->xdim; x2++) {
    for (y2 = y1; y2 < f->ydim; y2++) {
        setRect(tmp, x1, y1, x2, y2);
        size = getArea(tmp);
        if (size > maxsize && isFree(f, tmp)) {
            maxsize = size;
            copyRect(tmp, max);    /* max now describes the same rect as tmp */
        }
    }
    }
    }
    }
    delRect(tmp);
    if (getArea(max) == 1) {
        delRect(max);
        return NULL;
    }
    return max;
}

stack getAllFree(field *f, rect *r) {
    /* gets free areas within *f where *r fits (actually not all, see optimization below) */
    int x1, y1, x2, y2;
    stack s = newStack(2);
    rect *tmp = createRect(0, 0, 1, 1);
    int xmin, ymin;
    xmin = r->x2 - r->x1;
    ymin = r->y2 - r->y1;
    for (x1 = 0; x1 < f->xdim; x1++) {
    for (y1 = 0; y1 < f->ydim; y1++) {
    for (x2 = x1; x2 < f->xdim; x2++) {
    for (y2 = y1; y2 < f->ydim; y2++) {
        if (         
            ((x1 == 0) || f->f[y1][x1-1])   /* only allow "continuous" placement */
         && ((y1 == 0) || f->f[y1-1][x1])
        ) { 
            setRect(tmp, x1, y1, x2, y2);
            if (areCongruent(tmp, r) && isFree(f, tmp)) {
                push(s, tmp);
                tmp = createRect(0, 0, 1, 1); 
            }   
        }   
    }   
    }   
    }
    }
    push(s, NULL);
    return s;
}

void printField(field *f) {
    int x, y;
    for (y = 0; y < f->ydim; y++) {
        for (x = 0; x < f->xdim; x++) {
            printf("%c ", f->f[y][x] ? f->f[y][x] + 64 : '.');
        }
        printf("\n");
    }
    printf("-- \n");
}

int isInRect(rect *r, int x, int y) {
    if (x >= r->x1 && x <= r->x2 && y >= r->y1 && y <= r->y2) {
        return 1;
    }
    return 0;
}

int isSubRect(rect *r, rect *sub) {
    if (isInRect(r, sub->x1, sub->y1) && isInRect(r, sub->x2, sub->y2)) {
        return 1;
    }
    return 0;
}

int areCongruent(rect *r, rect *s) {
    int rxsize, rysize, sxsize, sysize, success = 0;
    rxsize = r->x2 - r->x1;
    rysize = r->y2 - r->y1;
    sxsize = s->x2 - s->x1;
    sysize = s->y2 - s->y1;
    if (
        (rxsize == sxsize && rysize == sysize)
     || (rxsize == sysize && rysize == sxsize)
    ) {
        success = 1;
    }
    return success;
}

#include <stdio.h>
#include <stdlib.h>
#ifndef XALLOC_H
    #include "xalloc.h"
#endif

#define POP_EMPTY NULL

typedef struct stackStruct {
    void **ptr;
    int pos;
    int size;
} *stack;

stack newStack(int size);
void destroyStackDeep(stack s);
void destroyStack(stack s);
void push(stack s, void *ptr);
void *pop(stack s);
void *top(stack s);
void *shift(stack s);

stack newStack(int size) {
    stack stck = xmalloc(sizeof(struct stackStruct));
    void **ptr = xmalloc(size * sizeof(void *));
    stck->ptr = ptr;
    stck->pos = 0;
    stck->size = size;
    return stck;
}

void destroyStack(stack s) {
    free(s->ptr);
    free(s);
}

void destroyStackDeep(stack s) {
    void *ptr = pop(s);
    while (ptr != NULL) {
        free(ptr);  /* make sure the ptrs in the stack are actually free()able if you call this method */
        ptr = pop(s);
    }
    destroyStack(s);
}


void push(stack s, void *ptr) {
    if (s->pos == s->size - 1) {
        s->size *= 2;
        s->ptr = xrealloc(s->ptr, s->size * sizeof(void *));
    }
    s->ptr[s->pos] = ptr;
    s->pos++;
}

void *pop(stack s) {
    if (s->pos == 0) {
      return POP_EMPTY;
    }
    s->pos--;
    return s->ptr[s->pos+1];
}

void *top(stack s) {
    return s->ptr[s->pos];
}

void *shift(stack s) {
    void *retptr = s->ptr[0];
    int i;
    for (i = 1; i < s->size; i++) {
        s->ptr[i-1] = s->ptr[i];
    }
    return retptr;
}

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

#define XALLOC_H 1

void *xmalloc(int size) {
    void *ptr = malloc(size);
    if (ptr == NULL) {
        fprintf(stderr, "not enough memory\n");
        exit(EXIT_FAILURE);
    }
    return ptr;
}

void *xcalloc(int nitems, int size) {
    void *ptr = calloc(nitems, size);
    if (ptr == NULL) {
        fprintf(stderr, "not enough memory\n");
        exit(EXIT_FAILURE);
    }
    return ptr;
}

void *xrealloc(void *ptr, int size) {
    ptr = realloc(ptr, size);
    if (ptr == NULL) {
        fprintf(stderr, "not enough memory\n");
        exit(EXIT_FAILURE);
    }
    return ptr;
}