excit_hilbert2d.c 1.97 KB
Newer Older
Brice Videau's avatar
Brice Videau committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "excit.h"
#include "excit_test.h"

/* Helper functions from: https://en.wikipedia.org/wiki/Hilbert_curve */

//rotate/flip a quadrant appropriately
static void rot(ssize_t n, ssize_t *x, ssize_t *y, ssize_t rx, ssize_t ry)
{
	if (ry == 0) {
		if (rx == 1) {
			*x = n - 1 - *x;
			*y = n - 1 - *y;
		}
		//Swap x and y
		ssize_t t = *x;

		*x = *y;
		*y = t;
	}
}

//convert d to (x,y)
static void d2xy(ssize_t n, ssize_t d, ssize_t *x, ssize_t *y)
{
	ssize_t rx, ry, s, t = d;

	*x = *y = 0;
	for (s = 1; s < n; s *= 2) {
		rx = 1 & (t / 2);
		ry = 1 & (t ^ rx);
		rot(s, x, y, rx, ry);
		*x += s * rx;
		*y += s * ry;
		t /= 4;
	}
}

/* End helper functions */

void test_alloc_init_hilbert2d(int order)
{
	excit_t it;
	ssize_t dim, size;

	it = excit_alloc_test(EXCIT_HILBERT2D);
	assert(excit_dimension(it, &dim) == ES);
	assert(dim == 0);

	assert(excit_hilbert2d_init(it, order) == ES);
	assert(excit_dimension(it, &dim) == ES);
	assert(dim == 2);
	assert(excit_size(it, &size) == ES);
	assert(size == (1 << order) * (1 << order));

	excit_free(it);
}

excit_t create_test_hilbert2d(int order)
{
	excit_t it;
	it = excit_alloc_test(EXCIT_HILBERT2D);
	assert(excit_hilbert2d_init(it, order) == ES);
	return it;
}

void test_next_hilbert2d(int order)
{
	excit_t it = create_test_hilbert2d(order);
	ssize_t indexes1[2], indexes2[2];

	for (int i = 0; i < (1 << order) * (1 << order); i++) {
		assert(excit_next(it, indexes1) == ES);
		d2xy(1<<order, i, indexes2, indexes2 + 1);
		assert(indexes1[0] == indexes2[0]);
		assert(indexes1[1] == indexes2[1]);
	}
	excit_free(it);
}

void test_hilbert2d_iterator(int order)
{
	test_alloc_init_hilbert2d(order);

	test_next_hilbert2d(order);

	int i = 0;
	while (synthetic_tests[i]) {
		excit_t it = create_test_hilbert2d(order);

		synthetic_tests[i](it);
		excit_free(it);
		i++;
	}
	
}

int main(int argc, char *argv[])
{
	test_hilbert2d_iterator(3);
	test_hilbert2d_iterator(4);
}