Mini ASCII Art Studio II

Napraviti napredniju varijantu mini ASCII art studija. Platno koristi dinamičku memoriju i radi isključivo preko pokazivača na strukture. Dodatno se vodi evidencija o bojama na platnu (paleta) putem dinamičkog niza koji se održava sortiran pozivima qsort, a pretrage se obavljaju bsearch-om.

Zadatak rešiti u fajlovima: main.c, canvas.h, canvas.c.

Platno Canvas treba da podržava sledeće funkcionalnosti (sve funkcije primaju pokazivače):

int canvas_init(Canvas *c, size_t w, size_t h, char fill) – alocira platno i popunjava ga bojom fill;
void canvas_free(Canvas *c) – oslobađa zauzetu memoriju;
int canvas_resize(Canvas *c, size_t w, size_t h, char fill) – ponovo alocira platno i popunjava bojom fill;
void canvas_set(Canvas *c, size_t x, size_t y, char col) – postavlja piksel;
void canvas_hline(Canvas *c, size_t y, size_t x1, size_t x2, char col) – horizontalna linija;
void canvas_vline(Canvas *c, size_t x, size_t y1, size_t y2, char col) – vertikalna linija;
void canvas_fill_rect(Canvas *c, size_t x, size_t y, size_t w, size_t h, char col) – puni pravougaonik;
void canvas_mirror(Canvas *c, char axis) – axis='H' horizontalno, axis='V' vertikalno preslikavanje;
int canvas_rotate90(Canvas *c) – rotira platno za $90^{\circ}$ udesno, dimenzije se prilagođavaju;
size_t canvas_distinct_colors(const Canvas *c) – vraća broj različitih boja (veličina sortiranog paleta-niza);
size_t canvas_color_count(Canvas *c, char col) – koristi bsearch da vrati broj pojavljivanja date boje;
void canvas_print_palette(Canvas *c) – ispisuje sve boje i broj ponavljanja u rastućem poretku karaktera; i
void canvas_print(const Canvas *c) – ispisuje platno.

U implementaciji je obavezno koristiti dinamičku alokaciju za piksele i za niz struktura koji predstavlja paletu (boja, broj ponavljanja). Paleta se pri svakoj promeni piksela ažurira, a po potrebi realocira. Pre bsearch poziva, niz boja mora biti sortiran pomoću qsort.

Ulaz

Sa standardnog ulaza se učitava broj upita $q$ ($1 \leq q \leq 500$). Zatim sledi $q$ upita:

c <w> <h> <fill> – kreira platno dimenzije <w>x<h> i popunjava njegove piksele bojom <fill>;
s <x> <y> <col> – postavlja piksel (<x>,<y>) bojom col;
h <y> <x1> <x2> <col> – horizontalna linija;
v <x> <y1> <y2> <col> – vertikalna linija;
r <x> <y> <w> <h> <col> – puni pravougaonik;
m <axis> – preslikava platno;
t – rotira platno za $90^{\circ}$ udesno;
p – ispisuje platno;
n – ispisuje broj različitih boja;
k – ispisuje sortiranu paletu u formatu col=count (za svaku boju); i
f <col> – pronalazi (binarnom pretragom) koliko se puta col pojavljuje i ispisuje vrednost (ili 0 ako boja ne postoji).

Svi indeksi su nula-bazirani. Pretpostaviti da su dimenzije najviše $64 \times 64$ i da su uneti indeksi u granicama platna.

Izlaz

Ispisati platno pri upitu p.
Za n ispisati broj različitih boja.
Za k ispisati boje onim redom kojim ih canvas_print_palette vraća, odvojene razmakom.
Za f <col> ispisati samo broj pojavljivanja date boje, ili 0.

Primer

Ulaz

11
c 4 3 .
h 1 0 3 A
v 0 0 2 B
r 2 0 2 3 C
p
n
k
f .
f C
m H
p

Izlaz

B.CC
BACC
B.CC
4
.=2 A=1 B=3 C=6
2
6
CC.B
CCAB
CC.B

Rešenje

`canvas.h`

#ifndef CANVAS_H
#define CANVAS_H

#include <stdbool.h>
#include <stddef.h>

typedef struct {
    char color;
    size_t count;
} ColorStat;

typedef struct {
    ColorStat *colors;
    size_t size;
    size_t capacity;
    bool sorted;
} Palette;

typedef struct {
    size_t w; size_t h;
    char *pixels;
    Palette palette;
} Canvas;

int    canvas_init(Canvas *c, size_t w, size_t h, char fill);
void   canvas_free(Canvas *c);
int    canvas_resize(Canvas *c, size_t w, size_t h, char fill);

void   canvas_set(Canvas *c, size_t x, size_t y, char col);
void   canvas_hline(Canvas *c, size_t y, size_t x1, size_t x2, char col);
void   canvas_vline(Canvas *c, size_t x, size_t y1, size_t y2, char col);
void   canvas_fill_rect(Canvas *c, size_t x, size_t y, size_t w, size_t h, char col);
void   canvas_mirror(Canvas *c, char axis);
int    canvas_rotate90(Canvas *c);

size_t canvas_distinct_colors(const Canvas *c);
size_t canvas_color_count(Canvas *c, char col);

void   canvas_print_palette(Canvas *c);
void   canvas_print(const Canvas *c);

#endif // CANVAS_H

`canvas.c`

#include "canvas.h"

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

static size_t canvas_index(const Canvas *c, size_t x, size_t y)
{
    return y * c->w + x;
}

static int color_cmp(const void *a, const void *b)
{
    const ColorStat *ca = (const ColorStat *) a;
    const ColorStat *cb = (const ColorStat *) b;

    return ca->color - cb->color;
}

static int palette_reserve(Canvas *c, size_t needed)
{
    if (needed <= c->palette.capacity) {
        return 1;
    }

    size_t new_capacity = c->palette.capacity ? c->palette.capacity * 2 : 4;
    while (new_capacity < needed) {
        new_capacity *= 2;
    }

    ColorStat *tmp_colors = realloc(c->palette.colors, new_capacity * sizeof (ColorStat));
    if (tmp_colors == 0) {
        return 0;
    }

    c->palette.colors = tmp_colors;
    c->palette.capacity = new_capacity;

    return 1;
}

static void palette_sort(Canvas *c)
{
    if (!c->palette.sorted && c->palette.size > 1) {
        qsort(c->palette.colors, c->palette.size, sizeof (ColorStat), color_cmp);
        c->palette.sorted = true;
    }
}

static ColorStat *palette_find(Canvas *c, char color)
{
    if (c->palette.size == 0) {
        return NULL;
    }

    palette_sort(c);

    ColorStat key = { color, 0 };
    return (ColorStat *)bsearch(&key, c->palette.colors, c->palette.size, sizeof (ColorStat), color_cmp);
}

static int palette_increment(Canvas *c, char color, int delta)
{
    if (delta == 0) {
        return 1;
    }

    ColorStat *entry = palette_find(c, color);
    if (entry != NULL) {
        entry->count += delta;
        if (entry->count == 0) {
            size_t idx = entry - c->palette.colors;
            if (idx + 1 < c->palette.size) {
                memmove(entry, entry + 1, (c->palette.size - idx - 1) * sizeof (ColorStat));
            }
            c->palette.size--;
        }
        return 1;
    }

    if (delta < 0) {
        return 1;
    }

    if (!palette_reserve(c, c->palette.size + 1)) {
        return 0;
    }

    c->palette.colors[c->palette.size].color = color;
    c->palette.colors[c->palette.size].count = delta;
    c->palette.size++;
    c->palette.sorted = false;

    return 1;
}

static int palette_set_fill(Canvas *c, char fill)
{
    if (!palette_reserve(c, 1)) {
        return 0;
    }

    c->palette.colors[0].color = fill;
    c->palette.colors[0].count = c->w * c->h;
    c->palette.size = 1;
    c->palette.sorted = true;

    return 1;
}

int canvas_init(Canvas *c, size_t w, size_t h, char fill)
{
    if (c == NULL) {
        return 0;
    }

    c->w = w; c->h = h;
    c->palette.colors = NULL;
    c->palette.size = 0;
    c->palette.capacity = 0;
    c->palette.sorted = true;

    size_t total = w * h;
    c->pixels = malloc(total * sizeof (char));
    if (c->pixels == NULL) {
        return 0;
    }

    memset(c->pixels, fill, total);

    if (!palette_set_fill(c, fill)) {
        free(c->pixels);
        c->pixels = NULL;
        return 0;
    }

    return 1;
}

void canvas_free(Canvas *c)
{
    if (c == NULL) {
        return;
    }

    if (c->pixels != NULL) {
        free(c->pixels);
    }

    if (c->palette.colors != NULL) {
        free(c->palette.colors);
    }

    c->w = 0; c->h = 0;
    c->pixels = NULL;
    c->palette.colors = NULL;
    c->palette.size = 0;
    c->palette.capacity = 0;
    c->palette.sorted = true;
}

int canvas_resize(Canvas *c, size_t w, size_t h, char fill)
{
    if (c == NULL) {
        return 0;
    }

    canvas_free(c);
    return canvas_init(c, w, h, fill);
}

void canvas_set(Canvas *c, size_t x, size_t y, char col)
{
    if (c == NULL || c->pixels == NULL) {
        return;
    }

    size_t idx = canvas_index(c, x, y);
    char old = c->pixels[idx];
    if (old == col) {
        return;
    }

    c->pixels[idx] = col;
    palette_increment(c, old, -1);
    palette_increment(c, col, +1);
}

void canvas_hline(Canvas *c, size_t y, size_t x1, size_t x2, char col)
{
    if (c == NULL) {
        return;
    }

    for (size_t x = x1; x <= x2; x++) {
        canvas_set(c, x, y, col);
    }
}

void canvas_vline(Canvas *c, size_t x, size_t y1, size_t y2, char col)
{
    if (c == NULL) {
        return;
    }

    for (size_t y = y1; y <= y2; y++) {
        canvas_set(c, x, y, col);
    }
}

void canvas_fill_rect(Canvas *c, size_t x, size_t y, size_t w, size_t h, char col)
{
    if (c == NULL) {
        return;
    }

    size_t x2 = x + w - 1;
    size_t y2 = y + h - 1;

    for (size_t yy = y; yy <= y2; yy++) {
        for (size_t xx = x; xx <= x2; xx++) {
            canvas_set(c, xx, yy, col);
        }
    }
}

void canvas_mirror(Canvas *c, char axis)
{
    if (c == NULL || c->pixels == NULL) {
        return;
    }

    if (axis == 'H') {
        for (size_t y = 0; y < c->h; y++) {
            for (size_t x = 0; x < c->w / 2; x++) {
                size_t left = canvas_index(c, x, y);
                size_t right = canvas_index(c, c->w - 1 - x, y);
                char tmp = c->pixels[left];
                c->pixels[left] = c->pixels[right];
                c->pixels[right] = tmp;
            }
        }
    } else if (axis == 'V') {
        for (size_t y = 0; y < c->h / 2; y++) {
            for (size_t x = 0; x < c->w; x++) {
                size_t top = canvas_index(c, x, y);
                size_t bottom = canvas_index(c, x, c->h - 1 - y);
                char tmp = c->pixels[top];
                c->pixels[top] = c->pixels[bottom];
                c->pixels[bottom] = tmp;
            }
        }
    }
}

int canvas_rotate90(Canvas *c)
{
    if (c == NULL || c->pixels == NULL) {
        return 0;
    }

    int old_w = c->w;
    int old_h = c->h;
    size_t total = c->w * c->h;

    char *rotated = malloc(total * sizeof (char));
    if (rotated == NULL) {
        return 0;
    }

    int new_w = old_h;
    int new_h = old_w;

    for (int y = 0; y < new_h; y++) {
        for (int x = 0; x < new_w; x++) {
            int ox = y, oy = c->h - 1 - x;
            rotated[y * new_w + x] = c->pixels[oy * old_w + ox];
        }
    }

    free(c->pixels);

    c->pixels = rotated;
    c->w = new_w;
    c->h = new_h;

    return 1;
}

size_t canvas_distinct_colors(const Canvas *c)
{
    if (c == NULL) {
        return 0;
    }

    return c->palette.size;
}

size_t canvas_color_count(Canvas *c, char col)
{
    if (c == NULL) {
        return 0;
    }

    ColorStat *entry = palette_find(c, col);
    return entry == NULL ? 0 : entry->count;
}

void canvas_print_palette(Canvas *c)
{
    if (c == NULL) {
        return;
    }

    palette_sort(c);
    for (size_t i = 0; i < c->palette.size; i++) {
        if (i > 0) {
            printf(" ");
        }
        printf("%c=%zu", c->palette.colors[i].color, c->palette.colors[i].count);
    }
}

void canvas_print(const Canvas *c)
{
    if (c == NULL || c->pixels == NULL) {
        return;
    }

    for (size_t y = 0; y < c->h; y++) {
        for (size_t x = 0; x < c->w; x++) {
            putchar(c->pixels[canvas_index(c, x, y)]);
        }
        putchar('\n');
    }
}

`main.c`

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

#include "canvas.h"

int main(void)
{
    Canvas canvas;;

    int q;
    scanf("%d", &q);

    while (q--) {
        char op;
        scanf(" %c", &op);

        if (op == 'c') {
            size_t w, h; char fill;
            scanf("%zu %zu %c", &w, &h, &fill);
            if (!canvas_init(&canvas, w, h, fill)) {
                exit(EXIT_FAILURE);
            }
        } else if (op == 's') {
            size_t x, y; char col;
            scanf("%zu %zu %c", &x, &y, &col);
            canvas_set(&canvas, x, y, col);
        } else if (op == 'h') {
            size_t y, x1, x2; char col;
            scanf("%zu %zu %zu %c", &y, &x1, &x2, &col);
            canvas_hline(&canvas, y, x1, x2, col);
        } else if (op == 'v') {
            size_t x, y1, y2; char col;
            scanf("%zu %zu %zu %c", &x, &y1, &y2, &col);
            canvas_vline(&canvas, x, y1, y2, col);
        } else if (op == 'r') {
            size_t x, y, w, h; char col;
            scanf("%zu %zu %zu %zu %c", &x, &y, &w, &h, &col);
            canvas_fill_rect(&canvas, x, y, w, h, col);
        } else if (op == 'm') {
            char axis;
            scanf(" %c", &axis);
            canvas_mirror(&canvas, axis);
        } else if (op == 't') {
            if (!canvas_rotate90(&canvas)) {
                canvas_free(&canvas);
                exit(EXIT_FAILURE);
            }
        } else if (op == 'p') {
            canvas_print(&canvas);
        } else if (op == 'n') {
            printf("%zu\n", canvas_distinct_colors(&canvas));
        } else if (op == 'k') {
            canvas_print_palette(&canvas);
            printf("\n");
        } else if (op == 'f') {
            char col;
            scanf(" %c", &col);
            printf("%zu\n", canvas_color_count(&canvas, col));
        }
    }

    canvas_free(&canvas);

    return 0;
}

`Makefile`

CC = gcc
CFLAGS = -Wall -Wextra -pedantic -std=c11

.PHONY: all clean

all: main

main: main.o canvas.o
	$(CC) $(CFLAGS) -o main main.o canvas.o

main.o: main.c canvas.h
	$(CC) $(CFLAGS) -c main.c -o main.o

canvas.o: canvas.c canvas.h
	$(CC) $(CFLAGS) -c canvas.c -o canvas.o

clean:
	rm -f main main.o canvas.o