RogueLife/src/util.c

#include "util.h"

#include <gint/display.h>

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

//---
// Heap sort
//---

/* Edges in the heap's tree, materialized as array index computations */
#define TOP 0
#define parent(i) (((i)-1)/2)
#define child_left(i) (2*(i)+1)
#define child_right(i) (2*(i)+2)

/* Create a priority queue with the requested number of elements. */
pqueue_t pqueue_alloc(size_t size, size_t elsize,
    int (*compare)(void const *, void const *))
{
    /* First element of the queue is unused, it just makes edges simpler */
    return (pqueue_t){
        .alloc_size = size,
        .size = 0,
        .elsize = elsize,
        .array = malloc((size+1) * elsize),
        .compare = compare,
    };
}

/* Pointer to nth element. */
static inline void *pqueue_nth(pqueue_t *q, int n)
{
    return q->array + n * q->elsize;
}

/* Swap elements i and j. */
static void pqueue_swap(pqueue_t *q, int i, int j)
{
    if(i == j) return;

    uint8_t tmp[q->elsize];
    memcpy(&tmp, pqueue_nth(q, i), q->elsize);
    memcpy(pqueue_nth(q, i), pqueue_nth(q, j), q->elsize);
    memcpy(pqueue_nth(q, j), &tmp, q->elsize);
}

/* Free a priority queue */
void pqueue_destroy(pqueue_t *q)
{
    free(q->array);
}

/* Whether the queue is empty */
bool pqueue_empty(pqueue_t const *q)
{
    return (q->size <= 0);
}

/* Add a value to the queue. */
void pqueue_add(pqueue_t *q, void const *element)
{
    if(q->size >= q->alloc_size) return;
    int i = q->size++;

    if(element != pqueue_nth(q, i))
        memcpy(pqueue_nth(q, i), element, q->elsize);

    /* Percolate up */
    while(i > TOP) {
        int p = parent(i);
        if(q->compare(pqueue_nth(q, p), pqueue_nth(q, i)) <= 0) break;

        pqueue_swap(q, p, i);
        i = p;
    }
}

/* Pop the minimum value from the queue. */
void pqueue_pop(pqueue_t *q, void *ret)
{
    if(pqueue_empty(q)) return;
    memcpy(ret, pqueue_nth(q, TOP), q->elsize);

    /* Move last element at the top */
    int i = TOP;
    memcpy(pqueue_nth(q, i), pqueue_nth(q, q->size-1), q->elsize);
    q->size--;

    /* Percolate down */
    while(1) {
        int l = child_left(i);
        int r = child_right(i);

        /* If there are no children, we're done */
        if(l >= q->size) break;

        /* Exchange with minimum of children */
        int minimum = l;
        if(r < q->size && q->compare(pqueue_nth(q, r), pqueue_nth(q, l)) < 0)
            minimum = r;

        if(q->compare(pqueue_nth(q, i), pqueue_nth(q, minimum)) <= 0)
            break;

        pqueue_swap(q, minimum, i);
        i = minimum;
    }
}

/* TODO: heap_sort can be made in-place with smart layout within (base) */
void heap_sort(void *base, size_t n, size_t elsize,
    int (*compare)(void const *, void const *))
{
    pqueue_t q = pqueue_alloc(n, elsize, compare);
    if(!q.array) return;

    for(size_t i = 0; i < n; i++)
        pqueue_add(&q, base + i * elsize);
    for(size_t i = 0; i < n; i++)
        pqueue_pop(&q, base + i * elsize);

    pqueue_destroy(&q);
}

//---
// Integer square root
//---

int64_t sqrtll(int64_t n)
{
    if(n <= 0) return 0;
    if(n < 4) return 1;

    int64_t low_bound = sqrtll(n / 4) * 2;
    int64_t high_bound = low_bound + 1;

    return (high_bound * high_bound <= n) ? high_bound : low_bound;
}

//---
// Rendering
//---

void fkey_button(int position, char const *text, int color)
{
    int width;
    dsize(text, NULL, &width, NULL);

    int x = 4 + 65 * (position - 1);
    int y = 207;
    int w = 63;

    dline(x + 1, y, x + w - 2, y, C_BLACK);
    dline(x + 1, y + 14, x + w - 2, y + 14, C_BLACK);
    drect(x, y + 1, x + w - 1, y + 13, C_BLACK);

    dtext(x + ((w - width) >> 1), y + 3, color, text);
}

void font_damage_size(int value, int *w, int *h)
{
    extern bopti_image_t img_font_damage_white;
    bopti_image_t *img = &img_font_damage_white;

    int char_w = (img->width + 1) / 10 - 1;
    int char_h = img->height;

    char str[16];
    int n = snprintf(str, 16, "%d", value);

    if(w) *w = n * char_w;
    if(h) *h = char_h;
}

void font_damage_print(int x, int y, int color, int align_x, int align_y,
    int value)
{
    extern bopti_image_t img_font_damage_white;
    extern bopti_image_t img_font_damage_red;

    bopti_image_t *img = (color == C_RED) ? &img_font_damage_red :
        &img_font_damage_white;

    int char_w = (img->width + 1) / 10 - 1;
    int char_h = img->height;

    /* Determine number of characters */
    char str[16];
    int n = snprintf(str, 16, "%d", value);

    if(align_x == DTEXT_CENTER)
        x -= (char_w * n) / 2;
    else if(align_x == DTEXT_RIGHT)
        x -= (char_w * n) - 1;

    if(align_y == DTEXT_MIDDLE)
        y -= char_h / 2;
    else if(align_y == DTEXT_BOTTOM)
        y -= char_h - 1;

    for(int i = 0; i < n; i++) {
        int offset = (char_w + 1) * (str[i] - '0');
        dsubimage(x, y, img, offset, 0, char_w, char_h, DIMAGE_NONE);
        x += char_w;
    }
}

int cubic(int start, int end, fixed_t t, fixed_t tmax)
{
    if(t >= tmax)
        return end;

    t = fdiv(t, tmax);
    fixed_t x = fix(1.0) - fmul(fmul(fix(1.0)-t, fix(1.0)-t), fix(1.0)-t);
    x = fix(start) + fmul(fix(end - start), x);
    return fround(x);
}