#include "hexagon.h"

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

/* constructor function */
struct HL_hex HL_hex_xy(int x, int y) {
	struct HL_hex h;
	h.x = x;
	h.y = y;
	return h;
}

int HL_hex_cmp(struct HL_hex const *a, struct HL_hex const *b) {
        if (a->x != b->x) {
                return a->x > b->x ? 1 : -1;
        }
        if (a->y != b->y) {
                return a->y > b->y ? 1 : -1;
        }
        return 0;
}

int HL_hex_eq(struct HL_hex const *a, struct HL_hex const *b) {
        return a->x == b->x && a->y == b->y;
}

/*
 * This file is written by Nathan Wagner and dedicated to the public
 * domain
 */

double HL_vertexv[12] = {
	.577350269189625764509148780502, 0.0,
	.288675134594812882254574390251, 0.5,
	-.288675134594812882254574390251, 0.5,
	-.577350269189625764509148780502, 0.0,
	-.288675134594812882254574390251, -0.5,
	.288675134594812882254574390251, -0.5};

double HL_fand[16] = {
	0.0, 0.0,
	.577350269189625764509148780502, 0.0,
	.288675134594812882254574390251, 0.5,
	-.288675134594812882254574390251, 0.5,
	-.577350269189625764509148780502, 0.0,
	-.288675134594812882254574390251, -0.5,
	.288675134594812882254574390251, -0.5,
	.577350269189625764509148780502, 0.0
};

double HL_hfand[16] = {
	0.0, 0.0,
	0.0, .577350269189625764509148780502,
	0.5, .288675134594812882254574390251,
	0.5, -.288675134594812882254574390251,
	0.0, -.577350269189625764509148780502,
	-0.5, -.288675134594812882254574390251,
	-0.5, .288675134594812882254574390251,
	0.0, .577350269189625764509148780502
};

float HL_fanf[16] = {
	0.0f, 0.0f,
	.577350269189625764509148780502f, 0.0f,
	.288675134594812882254574390251f, 0.5f,
	-.288675134594812882254574390251f, 0.5f,
	-.577350269189625764509148780502f, 0.0f,
	-.288675134594812882254574390251f, -0.5f,
	.288675134594812882254574390251f, -0.5f,
	.577350269189625764509148780502f, 0.0f
};

float HL_hfanf[16] = {
	0.0f, 0.0f,
	0.0f, .577350269189625764509148780502f,
	0.5f, .288675134594812882254574390251f,
	0.5f, -.288675134594812882254574390251f,
	0.0f, -.577350269189625764509148780502f,
	-0.5f, -.288675134594812882254574390251f,
	-0.5f, .288675134594812882254574390251f,
	0.0f, .577350269189625764509148780502f
};

/* size of a square that will exactly fit in a hexagon */
/* 2.0/(1+sqrt(3.0)) */
double HL_square = .73205080756887729352;

/* these all are for a hex one unit across */
static double          hexptvd[6][2] = {
	{.577350269189625764509148780502, 0.0},	/* 1.0/sqrt3 */
	{.288675134594812882254574390251, 0.5},	/* 0.5/sqrt3 */
	{-.288675134594812882254574390251, 0.5},
	{-.577350269189625764509148780502, 0.0},
	{-.288675134594812882254574390251, -0.5},
	{.288675134594812882254574390251, -0.5}
};

#if 0

/* TODO how is this related? to the above? */
static double          texptvd[6][2] = {
	{1.154700538379251529018297561004, 0.5},	/* 2.0/sqrt3 */
	{.866025403784438646763723170753, 1.0},	/* 1.5/sqrt3 */
	{.288675134594812882254574390251, 1.0},
	{0.0, 0.5},
	{.288675134594812882254574390251, 0.0},
	{.866025403784438646763723170753, 0.0}
};

static double          hexpthd[6][2] = {
	{0.0, .577350269189625764509148780502},
	{0.5, .288675134594812882254574390251},
	{0.5, -.288675134594812882254574390251},
	{0.0, -.577350269189625764509148780502},
	{-0.5, -.288675134594812882254574390251},
	{-0.5, .288675134594812882254574390251}
};

#endif

#define RD (180.0 / M_PI)
/* angle ranges from 0-6 */
/* distance is 0 at origin, 1.0 at the hex side */

#if 0
	double sqrt3;

	sqrt3 = sqrt(3.0);

        1
      /---\
    2/     \0
    /       \
    \       /
    3\     /5
      \---/
        4

      /\
    0/  \5
    /    \
    |    |
   1|    |4
    |    |
    \    /
    2\  /3
      \/

#endif

/* return the polar distance */
struct HL_point HL_polar(double angle, double distance, double *d) {
	double A, B, C, b;
	struct HL_point pt;

#if 0
           C
          /\
       b /  \ a
        /    \
       /      \
     A -------- B
           c

     c = 1 ; fixed, will scale later
     B = 60 ; exterior angle of hextant
     C = 180-B-A = 120-A ; sum of angles of a triangle
     A = function argument ; the polar coordinate we are calculating
     b = c * sin(B) / sin(C) ; law of sines

#endif
	/* convert angle to radians */
	angle = angle * M_PI / 3.0;

	/* calculate the distance along the ray to the hex side */

	A = fmod(angle, M_PI/3.0); /* constrain to within an equilateral */
	B = M_PI / 3.0;
	C = M_PI - B - A;

	b = sin(B) / sin(C);

	/* scale for hex one unit from side to side, rather than
	 * one unit from center to vertex
	 */
/*	b = b * sqrt(3.0) / 2.0 / 2.0; */
	b = b / sqrt(3);

	pt.x = distance * b * cos(angle);
	pt.y = distance * b * sin(angle);
	
	if (d) {
		*d = distance * b;
	}

	return pt;
}

void HL_vertices(struct HL_hex hex, double *vc) {
	int i;
	double xc, yc;
	struct HL_point center;

	center = HL_hexcenter(hex);
	xc = center.x;
	yc = center.y;

	for (i=0; i<6; i++) {
		*vc++ = hexptvd[i][0] + xc;
		*vc++ = hexptvd[i][1] + yc;
	}
	*vc++ = hexptvd[0][0] + xc;
	*vc++ = hexptvd[0][1] + yc;
}

#if 0
void HL_trianglefan(int cantor, double *vc) {
	HL_hexcenter(cantor, vc, vc+1);
	HL_vertices(cantor, vc+2);
}
#endif

struct HL_point HL_hexcenter(struct HL_hex hex) {
	int x, y;
	struct HL_point center;
	double yc;

	double stride = 1.5/sqrt(3.0);

	x = hex.x;
	y = hex.y;

	center.x = x * stride;

	if (x >= 0) yc = y + ((x + 1) % 2) / 2.0 - 0.5;
	if (x < 0) yc = y + ((-x + 1) % 2) / 2.0 - 0.5;

	center.y = yc;

	return center;
}

/*
 * This function assumes that the hexes are one unit across, and vertically
 * oriented.  If that is not the case, you will need to transform
 * your input coordinates first.
 */
struct HL_hex HL_bin(double x, double y) {
	return HL_hexbin(1.0, x, y);
}

struct HL_isohex HL_xy2ijk(struct HL_hex hex) {
	int pi, pj, pk;
	int x, y;
	struct HL_isohex iso;

	x = hex.x;
	y = hex.y;

	pi = x;
	pj = -y;

	if (x < 0) {
		pj = pj + (-x + 1) / 2;
	} else {
		pj = pj - x/2;
	}
	pk = -pi - pj;

	iso.i = pi;
	iso.j = pj;
	iso.k = pk;

	return iso;
}

#if 0

static int xy2ijk(int x, int y, int *i, int *j, int *k) {
	int pi, pj, pk;

	pi = x;
	pj = -y;
	if (x < 0) {
		pj = pj + (-x + 1) / 2;
	} else {
		pj = pj - x/2;
	}
	pk = -pi - pj;

	if (i) *i = pi;
	if (j) *j = pj;
	if (k) *k = pk;

	return HL_cantor_xy(x,y);
}
static int ijk2xy(int i, int j, int k, int *x, int *y) {
	int px, py;

	px = i;

	/* py = -j - i/2; */
	py = -j;

	if (i < 0) {
		py += (-i + 1)/2;
	} else {
		py -= i/2;
	}

	if (x) *x = px;
	if (y) *y = py;

	return HL_cantor_xy(px,py);
}

#endif

struct HL_hex HL_ijk2xy(struct HL_isohex iso) {
	int px, py;
	struct HL_hex xy;
	int i,j;

	i = iso.i;
	j = iso.j;

	px = i;

	/* py = -j - i/2; */
	py = -j;

	if (i < 0) {
		py += (-i + 1)/2;
	} else {
		py -= i/2;
	}

	xy.x = px;
	xy.y = py;

	return xy;
}


static void xy2ijkp(struct HL_hex h, int *ijk) {
	struct HL_isohex iso;

	iso = HL_xy2ijk(h);
	ijk[0] = iso.i;
	ijk[1] = iso.j;
	ijk[2] = iso.k;
}

int HL_distance(struct HL_hex from, struct HL_hex to) {
	int dist = 0, i;;
	int fc[3], tc[3];

	xy2ijkp(from, fc);
	xy2ijkp(to, tc);

	for (i=0;i<=2;i++) {
		dist += abs(fc[i] - tc[i]);
	}

	return dist / 2;
}

int HL_hexes_within_range(struct HL_hex hex, int range, struct HL_hex *list, int size) {
	int count = 0;
	int i;

	if (range == 0) {
		return HL_hexes_at_range(hex, 0, list, size);
	}

	for (i=1;i<=range;i++) {
		count += HL_hexes_at_range(hex, i, count > size ? 0 : list+count, size-count);
	}
	return count;
}

int HL_hexes_at_range(struct HL_hex hex, int range, struct HL_hex *list, int size) {
	int q; /* p and q are count/loop vars */
	struct HL_isohex iso;


	if (range == 0) {
		if (list) {
			list[0] = hex;
		}
		return 1;
	} else if (range < 0) {
		return 0;
	}

	/* TODO don't bother to collect if the list isn't big enough? */
	/* i.e. if (!list || size < range * 6) */
	if (!list || size < 1) return range * 6;

	iso = HL_xy2ijk(hex);

	iso.i += range;
	iso.k = -iso.i - iso.j;

	hex = HL_ijk2xy(iso);

	for(q=0; q<size && q < range * 6; q++) { 
		list[q] = hex;
		hex = HL_adjhex(hex, q/range+2);
	}

	return range * 6;
}

/* direction 0 is positive X , counter clockwise from there */
struct HL_hex HL_adjhex(struct HL_hex hex, int dir) {
	int c[3];
	struct HL_isohex iso;

	iso = HL_xy2ijk(hex);
	c[0] = iso.i;
	c[1] = iso.j;
	c[2] = iso.k;

	switch (dir%6) {
		case 2:
			c[0]--; c[1]++; break;
		case 1:
			        c[1]++; c[2]--; break;
		case 0:
			c[0]++;         c[2]--; break;
		case 5:
			c[0]++; c[1]--; break;
		case 4:
			        c[1]--; c[2]++; break;
		case 3:
			c[0]--;       ; c[2]++; break;
	}

	iso.i = c[0];
	iso.j = c[1];
	iso.k = c[2];

	return HL_ijk2xy(iso);
}

int HL_adjhexp(struct HL_hex hex, int dir, struct HL_hex *adj) {
	if (adj) {
		*adj = HL_adjhex(hex, dir);
	}
	return dir;
}

/* Determine if a map with these dimensions will overflow */
int HL_map_bounds_ok(int xdim, int ydim) {
	
	/* return (x+y) * (x + y + 1) / 2 + y+1; */

	if (INT_MAX - xdim - 1 < ydim) return 0;
	if (INT_MAX / (xdim+ydim) < (xdim+ydim+1)) return 0;
	if ( (xdim+ydim) * (xdim+ydim+1) / 2 > INT_MAX - ydim - 1)
		return 0;

	return 1;
}

int HL_map_max_dimension(void) {
	int low, high, try;

	low = 1; high = INT_MAX/2;

        while (low != high - 1) {
                try = (low + high) / 2;
                if (HL_map_bounds_ok(try,try)) {
                        low = try;
                } else {
                        high = try;
                }
        }

        return low;
}

struct hex {
        int iso;
        int x, y, z;
};

/* y *must* be positive down as the xy /iso conversion assumes this */
static int hex_xy(struct hex *h) {
	if (!h->iso) return 1;
	if (h->x >= 0) {
		h->y = -h->y - (h->x+1)/2;
	} else {
		/* need to round toward -inf, not toward zero, so x-1 */
		h->y = -h->y - h->x/2;
	}
	h->iso = 0;

	return 1;
}

#if 0

static int hex_iso(struct hex *h) {
	if (h->iso) return 1;

	if (h->x >= 0) {
		h->y = (-h->y - (h->x+1)/2);
	} else {
		/* need to round toward -inf, not toward zero, so x-1 */
		h->y = (-h->y - (h->x)/2);
	}

	h->z = -h->x - h->y;
	h->iso = 1;
	return 1;
}

#endif

#define COS30 (.866025403784438646763723170752)

struct HL_hex HL_hexbin(double width, double x, double y) {
	double z, rx, ry, rz;
	double abs_dx, abs_dy, abs_dz;
	int ix, iy, iz, s;
	struct hex h;
	struct HL_hex hex;

	/*x = x / cos(30 * M_PI / 180.0); */ /* rotated X coord */
	x = x / COS30;
	y = y - x / 2.0; /* adjustment for rotated X */

	/* adjust for actual hexwidth */
	x /= width;
	y /= width;

	z = -x - y;

	ix = rx = floor(x + 0.5);
	iy = ry = floor(y + 0.5);
	iz = rz = floor(z + 0.5);

	s = ix + iy + iz;

	if (s) {
		abs_dx = fabs(rx - x);
		abs_dy = fabs(ry - y);
		abs_dz = fabs(rz - z);

		if (abs_dx >= abs_dy && abs_dx >= abs_dz) {
			ix -= s;
		} else if (abs_dy >= abs_dx && abs_dy >= abs_dz) {
			iy -= s;
		} else {
			iz -= s;
		}
	}
	h.x = ix;
	h.y = iy;
	h.z = iz;
	h.iso = 1;

	hex_xy(&h);

	hex.x = h.x;
	hex.y = h.y;

	return hex;
}