/*- blockmap.c --------------------------------------------------------------*

 Node builder for DOOM levels (c) 1998 Colin Reed, version 3.0 (dos extended)

 Credit to:-

 Raphael Quinet (A very small amount of code has been borrowed from DEU).

 Matt Fell for the doom specs.

 Lee Killough for performance tuning, support for multilevel wads, special
 effects, and wads with lumps besides levels.

 Also, the original idea for some of the techniques where also taken from the
 comment at the bottom of OBJECTS.C in DEU, and the doc by Matt Fell about
 the nodes.

 Use this code for your own editors, but please credit me.

*---------------------------------------------------------------------------*/
/*
 * Separated from bsp.c 2000/08/26 by Colin Phipps
 * Modified 2010/08/04 by Christopher Bazley
 */

#include "structs.h"
#include "bsp.h"

/*--------------------------------------------------------------------------*/

static void write_hdr(struct lumplist *lump, const struct Block* blockmaphead)
{
	if (write_int16(&blockmaphead->minx) ||
	    write_int16(&blockmaphead->miny) ||
	    write_int16(&blockmaphead->xblocks) ||
	    write_int16(&blockmaphead->yblocks))
		write_error(lump);
}

/*--------------------------------------------------------------------------*/

static int
IsLineDefInside(int ldnum, int xmin, int ymin, int xmax, int ymax)
{
	int             x1 = vertices[linedefs[ldnum].start].x;
	int             y1 = vertices[linedefs[ldnum].start].y;
	int             x2 = vertices[linedefs[ldnum].end].x;
	int             y2 = vertices[linedefs[ldnum].end].y;
	int             count = 2;

	for (;;)
		if (y1 > ymax) {
			if (y2 > ymax)
				return (FALSE);
			x1 = x1 + (x2 - x1) * (double) (ymax - y1) / (y2 - y1);
			y1 = ymax;
			count = 2;
		} else if (y1 < ymin) {
			if (y2 < ymin)
				return (FALSE);
			x1 = x1 + (x2 - x1) * (double) (ymin - y1) / (y2 - y1);
			y1 = ymin;
			count = 2;
		} else if (x1 > xmax) {
			if (x2 > xmax)
				return (FALSE);
			y1 = y1 + (y2 - y1) * (double) (xmax - x1) / (x2 - x1);
			x1 = xmax;
			count = 2;
		} else if (x1 < xmin) {
			if (x2 < xmin)
				return (FALSE);
			y1 = y1 + (y2 - y1) * (double) (xmin - x1) / (x2 - x1);
			x1 = xmin;
			count = 2;
		} else {
			int             t;
			if (!--count)
				return (TRUE);
			t = x1;
			x1 = x2;
			x2 = t;
			t = y1;
			y1 = y2;
			y2 = t;
		}
}

/*- Create blockmap --------------------------------------------------------*/

void 
CreateBlockmap_old(struct lumplist *lump)
{
	struct Block    blockhead;
	unsigned short *blockptrs;
	short int      *blocklists = NULL;
	long            blocknum = 0, blockoffs = 0, num_blockptrs, n;
	int             x, y;
	const bbox_t   *bbox = lump->data;

	Verbose("Creating Blockmap... ");

	blockhead.minx = (*bbox)[BB_LEFT] & -8;
	blockhead.miny = (*bbox)[BB_BOTTOM] & -8;
	blockhead.xblocks = (((*bbox)[BB_RIGHT] - ((*bbox)[BB_LEFT] & -8)) / 128) + 1;
	blockhead.yblocks = (((*bbox)[BB_TOP] - ((*bbox)[BB_BOTTOM] & -8)) / 128) + 1;

	num_blockptrs = (long)blockhead.xblocks * blockhead.yblocks;
	blockptrs = GetMemory(num_blockptrs * sizeof(*blockptrs));

	for (y = 0; y < blockhead.yblocks; y++) {
		for (x = 0; x < blockhead.xblocks; x++) {
			progress();

			blockptrs[blocknum] = blockoffs + 4 + num_blockptrs;

			blocklists = ResizeMemory(blocklists, ((blockoffs + 1) * sizeof(*blocklists)));
			blocklists[blockoffs] = 0;
			blockoffs++;
			for (n = 0; n < num_lines; n++) {
				if (IsLineDefInside(n, (blockhead.minx + (x * 128)), (blockhead.miny + (y * 128)), (blockhead.minx + (x * 128)) + 127, (blockhead.miny + (y * 128)) + 127)) {
					/*
					 * printf("found line %d in block
					 * %d\n",n,blocknum);
					 */
					blocklists = ResizeMemory(blocklists, ((blockoffs + 1) * sizeof(*blocklists)));
					blocklists[blockoffs] = n;
					blockoffs++;
				}
			}
			blocklists = ResizeMemory(blocklists, ((blockoffs + 1) * sizeof(*blocklists)));
			blocklists[blockoffs] = -1;
			blockoffs++;

			blocknum++;
		}
	}

	write_hdr(lump, &blockhead);

	for (blocknum = 0; blocknum < num_blockptrs; blocknum++)
	{
		if (write_uint16(&blockptrs[blocknum]))
			write_error(lump);
	}

	for (blocknum = 0; blocknum < blockoffs; blocknum++)
	{
		if (write_int16(&blocklists[blocknum]))
			write_error(lump);
	}
	free(blockptrs);
	free(blocklists);

	Verbose("done.\n");
}

/*- Create blockmap (compressed) ----------------------------------------
 * Contributed by Simon "fraggle" Howard <sdh300@ecs.soton.ac.uk>
 * Merged 2001/11/17 */

struct blocklist_s {
	int num_lines;
	unsigned short offset;
	unsigned short *lines;
	struct blocklist_s *next;          /* for hash table */
};

static struct blocklist_s **blockhash;
static int blockhash_size;

/* offset pointers */

static struct blocklist_s **blockptrs;
static int num_blockptrs;

/* hashkey function for search */

static int blockhash_key(struct blocklist_s *bl)
{
	int i;
	int hash = 0;

	/* this is a pretty lame hash function
	   it has to be associative though (ie, 1 2 3 == 3 2 1) */

	for(i=0; i<bl->num_lines; ++i)
		hash += bl->lines[i];

	return hash % blockhash_size;
}

/* compare two struct blocklist_s's
   like strcmp: a 0 return value means they are identical */

static int blocklist_cmp(struct blocklist_s *bl1, struct blocklist_s *bl2)
{
	int i;

	if(bl1->num_lines != bl2->num_lines)
		return 1;

	for(i=0; i<bl1->num_lines; ++i) {
		if(bl1->lines[i] != bl2->lines[i])
			return 1;
	}

	return 0;
}

/* search for an identical blocklist */

static struct blocklist_s *blockhash_search(struct blocklist_s *bl)
{
	int hash = blockhash_key(bl);
	struct blocklist_s *search;

	for(search=blockhash[hash]; search; search=search->next) {
		if(!blocklist_cmp(bl, search))
			return search;
	}

	/* not found */

	return NULL;
}

/* add a new blocklist to the hashtable */

static struct blocklist_s *blockhash_add(struct blocklist_s *newbl)
{
	struct blocklist_s *bl;
	int hash;

	/* first, check an identical one doesnt already exist */

	bl = blockhash_search(newbl);

	if(bl)
		return bl;

	/* need to add new blocklist */

	/* make a copy */

	bl = GetMemory(sizeof(*bl));
	bl->num_lines = newbl->num_lines;
	bl->lines = GetMemory(sizeof(*bl->lines) * bl->num_lines);
	memcpy(bl->lines, newbl->lines,
	       sizeof(*bl->lines) * bl->num_lines);

	/* link into hash table */

	hash = blockhash_key(bl);

	bl->next = blockhash[hash];
	blockhash[hash] = bl;

	return bl;
}

static void blockmap_assemble(struct lumplist *lump, const struct Block* blockmaphead)
{
	int i;
	int offset;

	/* header */
	write_hdr(lump, blockmaphead);

	/* every hash chain */

	for(i=0,offset=num_blockptrs+sizeof(*blockmaphead)/sizeof(short);
			i<blockhash_size; ++i) {
		struct blocklist_s *bl;

		/* every blocklist in the chain */

		for(bl=blockhash[i]; bl; bl = bl->next) {

			/* offset is in short ints, not bytes */
			bl->offset = offset;
			offset += bl->num_lines;
		}
	}

	for(i=0; i<num_blockptrs; ++i) {
		if (write_uint16(&blockptrs[i]->offset))
			write_error(lump);
	}

	/* every hash chain */

	for(i=0;i<blockhash_size; ++i) {
		struct blocklist_s *bl;

		/* every blocklist in the chain */

		for(bl=blockhash[i]; bl; bl = bl->next) {

			int l;

			/* write each line */

			for(l=0; l<bl->num_lines; ++l) {
				if (write_uint16(&bl->lines[l]))
					write_error(lump);
			}
		}
	}
}

void
CreateBlockmap_compressed(struct lumplist *lump)
{
	int             x, y, n;
	int             blocknum = 0;
	unsigned short *templines;
	int             num_templines;
	struct Block	blockhead;
	const bbox_t   *bbox = lump->data;

	Verbose("Creating compressed blockmap... ");

	/* header */

	blockhead.minx = (*bbox)[BB_LEFT] & -8;
	blockhead.miny = (*bbox)[BB_BOTTOM] & -8;
	blockhead.xblocks = (((*bbox)[BB_RIGHT] - ((*bbox)[BB_LEFT] & -8)) / 128) + 1;
	blockhead.yblocks = (((*bbox)[BB_TOP] - ((*bbox)[BB_BOTTOM] & -8)) / 128) + 1;

	/* build hash table */

	blockhash_size = blockhead.xblocks * blockhead.yblocks;
	blockhash = GetMemory(blockhash_size * sizeof(*blockhash));
	for(n=0; n<blockhash_size; ++n)
		blockhash[n] = NULL;

	/* pointers */

	num_blockptrs = blockhead.xblocks * blockhead.yblocks;
	blockptrs = GetMemory(num_blockptrs * sizeof(*blockptrs));

	num_templines = 10240;
	templines = GetMemory(num_templines * sizeof(*templines));

	/* build all blocklists */

	for (y = 0; y < blockhead.yblocks; y++) {
		for (x = 0; x < blockhead.xblocks; x++) {
			struct blocklist_s tempbl;

			tempbl.num_lines = 0;
			tempbl.lines = templines;

			progress();

			/* first line is a 0 */

			tempbl.lines[tempbl.num_lines++] = 0;

			for (n = 0; n < num_lines; n++) {
				if (IsLineDefInside(n, (blockhead.minx + (x * 128)), (blockhead.miny + (y * 128)), (blockhead.minx + (x * 128)) + 127, (blockhead.miny + (y * 128)) + 127)) {
					/*
					 * printf("found line %d in block
					 * %d\n",n,blocknum);
					 */

					if(tempbl.num_lines >= num_templines-5) {
						num_lines *= 2;
						templines = ResizeMemory(templines,
									 num_templines * sizeof(*templines));
						tempbl.lines = templines;
					}

					tempbl.lines[tempbl.num_lines++] = n;
				}
			}

			/* last is 0xffff */

			tempbl.lines[tempbl.num_lines++] = 0xffff;

			blockptrs[blocknum++] = blockhash_add(&tempbl);
		}
	}

	free(templines);

	/* assemble */

	blockmap_assemble(lump, &blockhead);

	/* deconstruct the hash table */

	for(n=0; n<blockhash_size; ++n) {
		while(blockhash[n]) {
			struct blocklist_s *del = blockhash[n];
			blockhash[n] = blockhash[n]->next;
			free(del->lines);
			free(del);
		}
	}

	free(blockhash);
	free(blockptrs);

	Verbose("done.\n");

	return;
}

