/**************************************************************************
*  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-2004 by Markanth                *
*            http://www.firstmud.com/  <markanth@firstmud.com>            *
*         By using this code you have agreed to follow the term of        *
*             the 1stMud license in ../doc/1stMud/LICENSE                 *
***************************************************************************/

#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;
	CharData **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           (!IsSet( IS_DIR->exit_info, EX_CLOSED ))
#define    	GO_OK_SMARTER   1

Proto(void init_hash_table, (struct hash_header *, int, int));
Proto(void init_world, (RoomIndex * room_db[]));

Proto(CharData * get_char_area_restrict, (CharData * ch, char *argument));
Proto(void destroy_hash_table, (struct hash_header *));
Proto(void _hash_enter, (struct hash_header *, int, void *));

Proto(RoomIndex * room_find, (RoomIndex * room_db[], int));
Proto(void *hash_find, (struct hash_header *, int));
Proto(int room_enter, (RoomIndex * rb[], int, RoomIndex *));
Proto(int hash_enter, (struct hash_header *, int, void *));

Proto(RoomIndex * room_find_or_create, (RoomIndex * rb[], int));
Proto(void *hash_find_or_create, (struct hash_header *, int));
Proto(int room_remove, (RoomIndex * rb[], int));
Proto(void *hash_remove, (struct hash_header *, int));
Proto(int exit_ok, (ExitData *));
Proto(int find_path, (int, int, CharData *, int, bool));

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

	alloc_mem(ht->buckets, struct hash_link *, table_size);
	alloc_mem(ht->keylist, int, (ht->klistsize = 128));

	ht->klistlen = 0;
}

void init_world(RoomIndex * room_db[])
{
	memset(room_db, 0, sizeof(RoomIndex *) * top_room_index);
}

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

	if (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_mem(scan);
			scan = temp;
		}
	}
	free_mem(ht->buckets);
	free_mem(ht->keylist);
}

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

	struct hash_link *temp;
	int i;

	alloc_mem(temp, struct hash_link, 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->klistsize *= 2;
		realloc_mem(ht->keylist, int, ht->klistsize);
	}
	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++;
}

RoomIndex *room_find(RoomIndex * room_db[], int key)
{
	return ((key < top_room_index && 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(RoomIndex * rb[], int key, RoomIndex * rm)
{
	RoomIndex *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;
}

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

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

	alloc_mem(rv, RoomIndex, 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;

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

	return rval;
}

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

	tmp = room_find(rb, key);
	if (tmp)
	{
		rb[key] = 0;
		free_mem(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_mem(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(ExitData * pexit)
{
	RoomIndex *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, CharData * ch, int depth,
			  bool in_zone)
{
	struct room_q *tmp_q, *q_head, *q_tail;
	struct hash_header x_room;
	int i, tmp_room, count = 0, thru_doors;
	RoomIndex *herep;
	RoomIndex *startp;
	ExitData *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);

	alloc_mem(q_head, struct room_q, 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))
				{
					void *res;

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

count++;

							alloc_mem(tmp_q, struct room_q, 1);

							tmp_q->room_nr = tmp_room;
							tmp_q->next_q = 0;
							q_tail->next_q = tmp_q;
							q_tail = tmp_q;

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

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

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

	if (x_room.buckets)
	{
		destroy_hash_table(&x_room);
	}
	return -1;
}

Do_Fun(do_hunt)
{
	char buf[MSL];
	char arg[MSL];
	CharData *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 (NullStr(arg))
	{
		chprintln(ch, "Whom are you trying to hunt?");
		return;
	}

	fArea = (get_trust(ch) < MAX_LEVEL);

	if (IsNPC(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);
	WaitState(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 >= MAX_DIR)
	{
		chprintln(ch, "Hmm... Something seems to be wrong.");
		return;
	}

	if ((IsNPC(ch) && number_percent() > 50)
		|| (!IsNPC(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(CharData * ch)
{
	int dir;
	bool found;
	CharData *tmp;

	if (ch == NULL || ch->hunting == NULL || !IsNPC(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;
	}

	WaitState(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 >= MAX_DIR)
	{
		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 (IsSet(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;
}