/**************************************************************************
*  Original Diku Mud copyright (C) 1990, 1991 by Sebastian Hammer,        *
*  Michael Seifert, Hans Henrik St{rfeldt, Tom Madsen, and Katja Nyboe.   *
*                                                                         *
*  Merc Diku Mud improvements copyright (C) 1992, 1993 by Michael         *
*  Chastain, Michael Quan, and Mitchell Tse.                              *
*                                                                         *
*  In order to use any part of this Merc Diku Mud, you must comply with   *
*  both the original Diku license in 'license.doc' as well the Merc       *
*  license in 'license.txt'.  In particular, you may not remove either of *
*  these copyright notices.                                               *
*                                                                         *
*  Much time and thought has gone into this software and you are          *
*  benefiting.  We hope that you share your changes too.  What goes       *
*  around, comes around.                                                  *
***************************************************************************
*       ROM 2.4 is copyright 1993-1998 Russ Taylor                        *
*       ROM has been brought to you by the ROM consortium                 *
*           Russ Taylor (rtaylor@hypercube.org)                           *
*           Gabrielle Taylor (gtaylor@hypercube.org)                      *
*           Brian Moore (zump@rom.org)                                    *
*       By using this code, you have agreed to follow the terms of the    *
*       ROM license, in the file Rom24/doc/rom.license                    *
***************************************************************************
*       1stMUD ROM Derivative (c) 2001-2003 by Ryan Jennings              *
*            http://1stmud.dlmud.com/  <r-jenn@shaw.ca>                   *
***************************************************************************/
#include "merc.h"
#include "interp.h"

struct hash_link
{
	int key;
	struct hash_link *next;
	void *data;
};

struct hash_header
{
	int rec_size;
	int table_size;
	int *keylist, klistsize, klistlen;

	struct hash_link **buckets;
};

#define	HASH_KEY(ht,key)((((unsigned int)(key))*17)%(ht)->table_size)

struct hunting_data
{
	char *name;
	CHAR_DATA **victim;
};

struct room_q
{
	int room_nr;
	struct room_q *next_q;
};

struct nodes
{
	int visited;
	int ancestor;
};

#define	IS_DIR          (get_room_index(q_head->room_nr)->exit[i])
#define	GO_OK           (!IS_SET( IS_DIR->exit_info, EX_CLOSED ))
#define	GO_OK_SMARTER   1

PROTOTYPE(void init_hash_table, (struct hash_header *, int, int));
PROTOTYPE(void init_world, (ROOM_INDEX_DATA * room_db[]));
PROTOTYPE(CHAR_DATA * get_char_area_restrict, (CHAR_DATA * ch, char *argument));
PROTOTYPE(void destroy_hash_table, (struct hash_header *));
PROTOTYPE(void _hash_enter, (struct hash_header *, int, void *));
PROTOTYPE(ROOM_INDEX_DATA * room_find, (ROOM_INDEX_DATA * room_db[], int));
PROTOTYPE(void *hash_find, (struct hash_header *, int));
PROTOTYPE(int room_enter, (ROOM_INDEX_DATA * rb[], int, ROOM_INDEX_DATA *));
PROTOTYPE(int hash_enter, (struct hash_header *, int, void *));
PROTOTYPE(ROOM_INDEX_DATA * room_find_or_create, (ROOM_INDEX_DATA * rb[], int));
PROTOTYPE(void *hash_find_or_create, (struct hash_header *, int));
PROTOTYPE(int room_remove, (ROOM_INDEX_DATA * rb[], int));
PROTOTYPE(void *hash_remove, (struct hash_header *, int));
PROTOTYPE(int exit_ok, (EXIT_DATA *));
PROTOTYPE(int find_path, (int, int, CHAR_DATA *, int, int));

void init_hash_table(struct hash_header *ht, int rec_size, int table_size)
{
	ht->rec_size = rec_size;
	ht->table_size = table_size;

	ht->buckets =
		(struct hash_link **) calloc(sizeof(*ht->buckets), table_size);

	ht->keylist = (int *) calloc(sizeof(*ht->keylist), (ht->klistsize = 128));
	ht->klistlen = 0;
}

void init_world(ROOM_INDEX_DATA * room_db[])
{
	memset(room_db, 0, sizeof(ROOM_INDEX_DATA *) * top_room);
}

CHAR_DATA *get_char_area(CHAR_DATA * ch, char *argument)
{
	char arg[MIL];
	CHAR_DATA *ach;
	int number;
	int count;

	if (IS_NULLSTR(argument))
		return NULL;

	if ((ach = get_char_room(ch, NULL, argument)) != NULL)
		return ach;

	number = number_argument(argument, arg);
	count = 0;
	for (ach = char_first; ach != NULL; ach = ach->next)
	{
		if (ach->in_room == NULL
			|| ach->in_room->area != ch->in_room->area
			|| !can_see(ch, ach) || !is_name(arg, ach->name))
			continue;
		if (++count == number)
			return ach;
	}

	return NULL;
}

void destroy_hash_table(struct hash_header *ht)
{
	int i;
	struct hash_link *scan, *temp;

	for (i = 0; i < ht->table_size; i++)
		for (scan = ht->buckets[i]; scan;)
		{
			temp = scan->next;
			free(scan);
			scan = temp;
		}
	free(ht->buckets);
	free(ht->keylist);
}

void _hash_enter(struct hash_header *ht, int key, void *data)
{

	struct hash_link *temp;
	int i;

	temp = (struct hash_link *) calloc(sizeof(*temp), 1);

	temp->key = key;
	temp->next = ht->buckets[HASH_KEY(ht, key)];
	temp->data = data;
	ht->buckets[HASH_KEY(ht, key)] = temp;
	if (ht->klistlen >= ht->klistsize)
	{
		ht->keylist =
			(int *) realloc(ht->keylist,
							sizeof(*ht->keylist) * (ht->klistsize *= 2));
	}
	for (i = ht->klistlen; i >= 0; i--)
	{
		if (ht->keylist[i - 1] < key)
		{
			ht->keylist[i] = key;
			break;
		}
		ht->keylist[i] = ht->keylist[i - 1];
	}
	ht->klistlen++;
}

ROOM_INDEX_DATA *room_find(ROOM_INDEX_DATA * room_db[], int key)
{
	return ((key < top_room && key > -1) ? room_db[key] : 0);
}

void *hash_find(struct hash_header *ht, int key)
{
	struct hash_link *scan;

	scan = ht->buckets[HASH_KEY(ht, key)];

	while (scan && scan->key != key)
		scan = scan->next;

	return scan ? scan->data : NULL;
}

int room_enter(ROOM_INDEX_DATA * rb[], int key, ROOM_INDEX_DATA * rm)
{
	ROOM_INDEX_DATA *temp;

	temp = room_find(rb, key);
	if (temp)
		return (0);

	rb[key] = rm;
	return (1);
}

int hash_enter(struct hash_header *ht, int key, void *data)
{
	void *temp;

	temp = hash_find(ht, key);
	if (temp)
		return 0;

	_hash_enter(ht, key, data);
	return 1;
}

ROOM_INDEX_DATA *room_find_or_create(ROOM_INDEX_DATA * rb[], int key)
{
	ROOM_INDEX_DATA *rv;

	rv = room_find(rb, key);
	if (rv)
		return rv;

	rv = (ROOM_INDEX_DATA *) calloc(sizeof(*rv), 1);
	rb[key] = rv;

	return rv;
}

void *hash_find_or_create(struct hash_header *ht, int key)
{
	void *rval;

	rval = hash_find(ht, key);
	if (rval)
		return rval;

	rval = (void *) malloc(ht->rec_size);
	_hash_enter(ht, key, rval);

	return rval;
}

int room_remove(ROOM_INDEX_DATA * rb[], int key)
{
	ROOM_INDEX_DATA *tmp;

	tmp = room_find(rb, key);
	if (tmp)
	{
		rb[key] = 0;
		free(tmp);
	}
	return (0);
}

void *hash_remove(struct hash_header *ht, int key)
{
	struct hash_link **scan;

	scan = ht->buckets + HASH_KEY(ht, key);

	while (*scan && (*scan)->key != key)
		scan = &(*scan)->next;

	if (*scan)
	{
		int i;
		struct hash_link *temp, *aux;

		temp = (struct hash_link *) (*scan)->data;
		aux = *scan;
		*scan = aux->next;
		free(aux);

		for (i = 0; i < ht->klistlen; i++)
			if (ht->keylist[i] == key)
				break;

		if (i < ht->klistlen)
		{
			memcpy((char *) ht->keylist + i + 1,
				   (char *) ht->keylist + i,
				   (ht->klistlen - i) * sizeof(*ht->keylist));
			ht->klistlen--;
		}

		return temp;
	}

	return NULL;
}

int exit_ok(EXIT_DATA * pexit)
{
	ROOM_INDEX_DATA *to_room;

	if ((pexit == NULL) || (to_room = pexit->u1.to_room) == NULL)
		return 0;

	return 1;
}

int find_path(int in_room_vnum, int out_room_vnum, CHAR_DATA * ch, int depth,
			  int in_zone)
{
	struct room_q *tmp_q, *q_head, *q_tail;
	struct hash_header x_room;
	int i, tmp_room, count = 0, thru_doors;
	ROOM_INDEX_DATA *herep;
	ROOM_INDEX_DATA *startp;
	EXIT_DATA *exitp;

	if (depth < 0)
	{
		thru_doors = TRUE;
		depth = -depth;
	}
	else
	{
		thru_doors = FALSE;
	}

	startp = get_room_index(in_room_vnum);

	init_hash_table(&x_room, sizeof(int), 2048);

	hash_enter(&x_room, in_room_vnum, (void *) -1);

	q_head = (struct room_q *) calloc(sizeof(*q_head), 1);

	q_tail = q_head;
	q_tail->room_nr = in_room_vnum;
	q_tail->next_q = 0;

	while (q_head)
	{
		herep = get_room_index(q_head->room_nr);

		if (herep->area == startp->area || !in_zone)
		{
			for (i = 0; i < MAX_DIR; i++)
			{
				exitp = herep->exit[i];
				if (exit_ok(exitp) && (thru_doors ? GO_OK_SMARTER : GO_OK))
				{

					tmp_room = herep->exit[i]->u1.to_room->vnum;
					if (tmp_room != out_room_vnum)
					{
						if (!hash_find(&x_room, tmp_room) && (count < depth))
						{
							count++;

							tmp_q = (struct room_q *) calloc(sizeof(*tmp_q), 1);
							tmp_q->room_nr = tmp_room;
							tmp_q->next_q = 0;
							q_tail->next_q = tmp_q;
							q_tail = tmp_q;

							hash_enter(&x_room,
									   tmp_room,
									   ((int)
										hash_find
										(&x_room,
										 q_head->room_nr) ==
										-1) ? (void
											   *) (i
												   +
												   1)
									   : hash_find(&x_room, q_head->room_nr));
						}
					}
					else
					{

						tmp_room = q_head->room_nr;
						for (; q_head; q_head = tmp_q)
						{
							tmp_q = q_head->next_q;
							free(q_head);
						}

						if ((int) hash_find(&x_room, tmp_room) == -1)
						{
							if (x_room.buckets)
							{
								destroy_hash_table(&x_room);
							}
							return (i);
						}
						else
						{
							i = (int) hash_find(&x_room, tmp_room);
							if (x_room.buckets)
							{
								destroy_hash_table(&x_room);
							}
							return (-1 + i);
						}
					}
				}
			}
		}

		tmp_q = q_head->next_q;
		free(q_head);
		q_head = tmp_q;
	}

	if (x_room.buckets)
	{

		destroy_hash_table(&x_room);
	}
	return -1;
}

CH_CMD(do_hunt)
{
	char buf[MSL];
	char arg[MSL];
	CHAR_DATA *victim;
	int direction;
	bool fArea;

	one_argument(argument, arg);

	if (get_skill(ch, gsn_hunt) == 0 || !can_use_skpell(ch, gsn_hunt))
	{
		chprintln(ch, "You don't know how to hunt.");
		return;
	}

	if (IS_NULLSTR(arg))
	{
		chprintln(ch, "Whom are you trying to hunt?");
		return;
	}

	fArea = (get_trust(ch) < MAX_LEVEL);

	if (IS_NPC(ch))
		victim = get_char_world(ch, arg);
	else if (fArea)
		victim = get_char_area(ch, arg);
	else
		victim = get_char_world(ch, arg);

	if (victim == NULL)
	{
		chprintln(ch, "No-one around by that name.");
		return;
	}

	if (ch->in_room == victim->in_room)
	{
		act("$N is here!", ch, NULL, victim, TO_CHAR);
		return;
	}

	if (ch->move > 2)
		ch->move -= 3;
	else
	{
		chprintln(ch, "You're too exhausted to hunt anyone!");
		return;
	}

	act("$n carefully sniffs the air.", ch, NULL, NULL, TO_ROOM);
	WAIT_STATE(ch, skill_table[gsn_hunt].beats);
	direction =
		find_path(ch->in_room->vnum, victim->in_room->vnum, ch, -40000, fArea);

	if (direction == -1)
	{
		act("You couldn't find a path to $N from here.",
			ch, NULL, victim, TO_CHAR);
		return;
	}

	if (direction < 0 || direction > 5)
	{
		chprintln(ch, "Hmm... Something seems to be wrong.");
		return;
	}

	if ((IS_NPC(ch) && number_percent() > 50) ||
		(!IS_NPC(ch) && number_percent() > get_skill(ch, gsn_hunt)))
	{
		do
		{
			direction = number_door();
		}
		while ((ch->in_room->exit[direction] == NULL) ||
			   (ch->in_room->exit[direction]->u1.to_room == NULL));
	}

	sprintf(buf, "$N is %s from here.", dir_name[direction]);
	act(buf, ch, NULL, victim, TO_CHAR);
	check_improve(ch, gsn_hunt, TRUE, 1);
	return;
}

void hunt_victim(CHAR_DATA * ch)
{
	int dir;
	bool found;
	CHAR_DATA *tmp;

	if (ch == NULL || ch->hunting == NULL || !IS_NPC(ch))
		return;

	for (found = 0, tmp = char_first; tmp && !found; tmp = tmp->next)
		if (ch->hunting == tmp)
			found = 1;

	if (!found || !can_see(ch, ch->hunting))
	{
		do_function(ch, &do_say, "Damn!  My prey is gone!!");
		ch->hunting = NULL;
		return;
	}

	if (ch->in_room == ch->hunting->in_room)
	{
		if (number_percent() < 60)
		{
			act("" CTAG(_SAY1) "$n" CTAG(_SAY1) " glares at $N"
				CTAG(_SAY1) " and says, '" CTAG(_SAY2)
				"Ye shall DIE!" CTAG(_SAY1) "'{x", ch, NULL,
				ch->hunting, TO_NOTVICT);
			act("" CTAG(_SAY1) "$n" CTAG(_SAY1)
				" glares at you and says, '" CTAG(_SAY2)
				"Ye shall DIE!" CTAG(_SAY1) "'{x", ch, NULL,
				ch->hunting, TO_VICT);
			act("" CTAG(_SAY1) "You glare at $N" CTAG(_SAY1)
				" and say, '" CTAG(_SAY2) "Ye shall DIE!"
				CTAG(_SAY1) "'{x", ch, NULL, ch->hunting, TO_CHAR);
		}
		else
		{
			act("" CTAG(_SAY1) "$n" CTAG(_SAY1) " glares at $N"
				CTAG(_SAY1) " and says, '" CTAG(_SAY2)
				"Hey, I remember you!" CTAG(_SAY1) "'{x", ch, NULL,
				ch->hunting, TO_NOTVICT);
			act("" CTAG(_SAY1) "$n" CTAG(_SAY1)
				" glares at you and says, '" CTAG(_SAY2)
				"Hey, I remember you!" CTAG(_SAY1) "'{x", ch, NULL,
				ch->hunting, TO_VICT);
			act("" CTAG(_SAY1) "You glare at $N" CTAG(_SAY1)
				" and say, '" CTAG(_SAY2) "Hey, I remember you!"
				CTAG(_SAY1) "'{x", ch, NULL, ch->hunting, TO_CHAR);
		}
		multi_hit(ch, ch->hunting, TYPE_UNDEFINED);
		ch->hunting = NULL;
		return;
	}

	WAIT_STATE(ch, skill_table[gsn_hunt].beats);
	dir =
		find_path(ch->in_room->vnum, ch->hunting->in_room->vnum, ch, -40000,
				  TRUE);

	if (dir < 0 || dir > 5)
	{
		act("" CTAG(_SAY1) "$n" CTAG(_SAY1) " says '" CTAG(_SAY2)
			"Damn!  Lost $M" CTAG(_SAY1) "!'{x", ch, NULL, ch->hunting,
			TO_ROOM);
		ch->hunting = NULL;
		return;
	}

	if (number_percent() > 50)
	{

		do
		{
			dir = number_door();
		}
		while ((ch->in_room->exit[dir] == NULL) ||
			   (ch->in_room->exit[dir]->u1.to_room == NULL));
	}

	if (IS_SET(ch->in_room->exit[dir]->exit_info, EX_CLOSED))
	{
		do_function(ch, &do_open, (char *) dir_name[dir]);
		return;
	}

	move_char(ch, dir, FALSE);
	return;
}