/* $Id: steps.c,v 1.19 2017/05/21 22:18:11 kili Exp $ */
/*
 * Copyright (c) 2016 Matthias Kilian <kili@outback.escape.de>
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

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

#include "steps.h"

static int
gcd(int a, int b)
{
	int r;

	a = abs(a);
	b = abs(b);

	if ((r = a) < b) {
		a = b;
		b = r;
	}

	while ((r = a % b)) {
		a = b;
		b = r;
	}

	return b;
}

/* Modified bresenham algorithm; initially taken by quabla from the C
 * implementation from wikipedia, modified to find all touched fields
 * and ported to PHP, then ported by Didi to JavaScript (see
 * https://github.com/karopapier/KaroBackbone/blob/master/src/model/Vector.js),
 * ported back to C and simplified a little bit by me.
 * Simplifications are:
 * - Operate on the first octant (0 <= dy <= dx) only.
 * - Don't use a triple case (err < 0, err > 0, err == 0) but just
 *   handle both cases (err <= 0 and err >= 0).
 * - Reduce dx and dy by gcd(dx, dy); the client should calculate
 *   r = gcd(dx, dy), too, and repeat the steps r times.
 */
int
walk_steps(int (*f) (void *, int, int), void *data, int x0, int y0, int dx, int dy)
{
	/* XXX the size should be calculated or at least be based
	 * on MAP_MAX.
	 */
	static int steps[2 * 1024][2];
	int hp;		/* horizontal positive */
	int vp;		/* vertical positive */
	int st;		/* steep */
	int rep;	/* repetition */
	int dx1, dy1, err, i, nerr, r, ret, stepcount, t, x, y, x_off, y_off;

	if (!dx && !dy)
		return 0;

	if (!(hp = dx >= 0)) {
		dx = -dx;
		hp = -1;
	}

	if (!(vp = dy >= 0)) {
		dy = -dy;
		vp = -1;
	}

	if ((st = dx < dy)) {
		t = dx;
		dx = dy;
		dy = t;
	}

	if ((rep = dy ? gcd(dx, dy) : dx) > 1) {
		dx /= rep;
		dy /= rep;
	}

	err = dx - dy;
	for (stepcount = x = y = 0; x < dx || y < dy; stepcount++) {
		nerr = err;
		if (err <= 0) {
			nerr += 2 * dx;
			y++;
		}
		if (err >= 0) {
			nerr -= 2 * dy;
			x++;
		}
		err = nerr;
		assert(stepcount < 2 * 1024);
		steps[stepcount][0] = hp * (st ? y : x);
		steps[stepcount][1] = vp * (st ? x : y);
	}

	for (x_off = y_off = 0, r = 1; r <= rep; r++) {
		for (i = 0; i < stepcount; i++) {
			dx1 = x_off + steps[i][0];
			dy1 = y_off + steps[i][1];
			if ((ret = f(data, x0 + dx1, y0 + dy1)))
				return ret;
		}
		x_off += hp * (st ? dy : dx);
		y_off += vp * (st ? x : y);
	}

	return 0;
}