//-----------------------------------------------------------------------------
//
//  $Logfile:: /Source/alias.c                                                $
// $Revision:: 2                                                              $
//   $Author:: Burgermac                                                      $
//     $Date:: 12/27/00 7:49 PM                                               $
//
// Copyright (C) 1997 by Ritual Entertainment, Inc.
// All rights reserved.
//
// This source is may not be distributed and/or modified without
// expressly written permission by Ritual Entertainment, Inc.
//
// DESCRIPTION:
// Generic alias system for files.
//

#include "alias.h"
#include <ctype.h>

#define MAX_SEARCH_ALIASES 64

//
// static variables
//
static AliasList_t *Aliases;
static AliasListNode_t *foundlist[MAX_SEARCH_ALIASES];

AliasList_t * AliasList_New( const char * name )
{
	AliasList_t * list;

	list = ( AliasList_t * )Z_Malloc( sizeof( AliasList_t ) );
//	list->num_in_list = 0;
//	list->sorted_list = NULL;
//	list->data_list = NULL;
//	list->dirty = FALSE;
	if ( name ) {
		strncpy( list->name, name, MAX_ALIASLIST_NAME_LENGTH );
	} else {
		list->name[ 0 ] = 0;
	}
	return list;
}

void Alias_ListClear( AliasList_t * list )
{
	AliasListNode_t *WorkPtr;
	if(list->sorted_list)
	{
		Z_Free( list->sorted_list );
	}
	WorkPtr = list->data_list;
	if (WorkPtr) {
		do {
			AliasListNode_t *Next;
			Next = WorkPtr->next;
			Z_Free( WorkPtr );
			WorkPtr = Next;
		} while (WorkPtr);
	}
	list->num_in_list = 0;
	list->dirty = false;
	list->sorted_list = NULL;
	list->data_list = NULL;
}

void Alias_ListDelete( AliasList_t * list )
{
	if (list) {
		Alias_ListClear( list );
		Z_Free( list );
	}
}

qboolean Alias_ListAdd( AliasList_t * list, const char * alias, const char * name, float weight )
{
	int i;
	AliasListNode_t * node;

	assert( alias );
	assert( name );
	//
	// if the list is sorted, lets try to find our alias before adding it
	//
	if ( list && !list->dirty ) {
		const char * real_name;
		real_name = Alias_ListFind( list, alias );
		if ( real_name ) {
			if ( strcmp( name, real_name ) ) {
				Com_DPrintf( DEVELOPER_MSG_IO, "Duplicate Aliases for %s in list %s.\n", alias, list->name );
			}
			return true;
		}
	}

	node = (AliasListNode_t *)Z_Malloc( sizeof(AliasListNode_t));
	if ( !node ) {
		// will always break if in debugger
		assert( NULL );
		Sys_Error( "Alias_ListAdd : Out of memory" );
	}

	assert( strlen( alias ) < MAX_ALIAS_NAME_LENGTH );
	assert( strlen( name ) < MAX_REAL_NAME_LENGTH );

	strncpy( node->alias_name, alias, MAX_ALIAS_NAME_LENGTH-1 );
	//
	// lowercase alias
	//
	for ( i = 0; i < MAX_ALIAS_NAME_LENGTH; i++ ) {
		node->alias_name[ i ] = tolower( node->alias_name[ i ] );
	}
	strncpy( node->real_name, name, MAX_REAL_NAME_LENGTH-1 );
	node->weight = weight;

	assert( list );
	if ( list ) {
		list->dirty = true;
		list->num_in_list++;
		node->next = list->data_list;
		list->data_list = node;
		return true;
	}
	return false;
}

#define Alias_CompareNames( name1, name2, length ) ( strncmp( (name1), (name2), (length) ) )

static void Alias_ListSort( AliasList_t * list )
{
	int num, size, i, index;
	AliasListNode_t *root, *ptr, *smallest, *prev, *smallestprev, *last;

	assert( list );
	if ( !list )
		return;

	assert( list->dirty );
	if ( !list->dirty )
		return;

	// save off data list
	root = list->data_list;
	// clear out data_list
	list->data_list = NULL;

	// clear out sorted_list
	if(list->sorted_list)
		Z_Free( list->sorted_list );

	// find out how many we have
	num = list->num_in_list;
	// allocate sorted list
	size = num * sizeof( AliasListNode_t * );
	list->sorted_list = ( AliasListNode_t ** )Z_Malloc( size );

	// sort the list
	last = NULL;
	smallestprev = NULL;/* silence compiler */
	for ( i = 0, index = 0; i < num; i++ )
	{
		prev = root;
		smallest = root;
		for ( ptr = root->next; ptr != NULL; prev = ptr, ptr = ptr->next )
		{
			if ( Alias_CompareNames( ptr->alias_name, smallest->alias_name, strlen( ptr->alias_name ) ) < 0 )
			{
				smallestprev = prev;
				smallest = ptr;
			}
		}
		if ( smallest == root )
		{
			root = smallest->next;
		}
		else
		{
			smallestprev->next = smallest->next;
		}
		//
		// look for duplicates
		//
		if (
			last &&
			( Alias_CompareNames( last->alias_name, smallest->alias_name, strlen( last->alias_name ) ) == 0 )
			)
		{
			if ( strcmp( last->real_name, smallest->real_name ) )
			{
				Com_DPrintf( DEVELOPER_MSG_IO, "Duplicate Aliases for %s in list %s.\n", last->alias_name, list->name );
			}
			Z_Free( smallest );
		}
		else
		{
			list->sorted_list[ index++ ] = smallest;
			smallest->next = list->data_list;
			list->data_list = smallest;
			last = smallest;
		}
	}
	list->dirty = false;
	list->num_in_list = index;
}

const char * Alias_ListFind( AliasList_t * list, const char * alias )
{
	char convalias[ MAX_ALIAS_NAME_LENGTH ];
	int index, l, r, diff, length;

	assert( list );
	if ( !list )
		return NULL;

	assert( alias );
	if ( !alias )
		return NULL;

	if ( list->dirty )
	{
		Alias_ListSort( list );
	}

	length = (int)strlen( alias );
	//
	// convert alias
	//
	for ( l = 0; l < length; l++ )
	{
		convalias[ l ] = tolower( alias[ l ] );
	}
	convalias[ l ] = 0;

	l = 0;
	r = list->num_in_list-1;
	while( r >= l )
	{
		index = ( l + r ) >> 1;
		diff = Alias_CompareNames( convalias, list->sorted_list[ index ]->alias_name, length );
		if ( diff < 0 )
		{
			r = index - 1;
		}
		else if ( diff > 0 )
		{
			l = index + 1;
		}
		else
		{
			return list->sorted_list[ index ]->real_name;
		}
	}
	return NULL;
}

static float randweight( void )
{
	return ( ( float )( rand() & 0x7fff ) ) / ( ( float )0x8000 );
}

const char * Alias_ListFindRandom( AliasList_t * list, const char * alias )
{
	char convalias[ MAX_ALIAS_NAME_LENGTH ];
	int index, l, r, diff, i, length, numfound, numsearches;
	float weight, num, totalfoundweight;
	AliasListNode_t ** ptr;

	assert( list );
	if ( !list )
		return NULL;

	assert( alias );
	if ( !alias )
		return NULL;

	if ( list->dirty )
	{
		Alias_ListSort( list );
	}

	numsearches = 0;
	length = (int)strlen( alias );
	//
	// convert alias
	//
	for ( l = 0; l < length; l++ )
	{
		convalias[ l ] = tolower( alias[ l ] );
	}
	convalias[ l ] = 0;

	l = 0;
	r = list->num_in_list-1;
	while( r >= l )
	{
		index = ( l + r ) >> 1;
		diff = Alias_CompareNames( convalias, list->sorted_list[ index ]->alias_name, length );
		numsearches++;
		if ( diff < 0 )
		{
			r = index - 1;
		}
		else if ( diff > 0 )
		{
			l = index + 1;
		}
		else
		{
			break;
		}
	}
	//
	// did we find at least one?
	//
	if ( r < l )
		return NULL;

	numfound = 0;
	totalfoundweight = 0;

	//
	// find the beginnning of the matches
	//
	i = index;
	ptr = &list->sorted_list[ i ];
	while ( ( i >= 0 ) && ( Alias_CompareNames( convalias, (*ptr)->alias_name, length ) == 0 ) )
	{
		if ( ( numfound < MAX_SEARCH_ALIASES ) && ( (*ptr)->alias_name[length] != '_' ) )
		{
			foundlist[ numfound++ ] = (*ptr);
			totalfoundweight += (*ptr)->weight;
		}
		ptr--;
		i--;
	}
	//
	// find the end of the matches
	//
	i = index + 1;
	ptr = &list->sorted_list[ i ];
	while ( ( i < list->num_in_list ) && ( Alias_CompareNames( convalias, (*ptr)->alias_name, length ) == 0 ) )
	{
		if ( ( numfound < MAX_SEARCH_ALIASES ) && ( (*ptr)->alias_name[length] != '_' ) )
		{
			foundlist[ numfound++ ] = (*ptr);
			totalfoundweight += (*ptr)->weight;
		}
		ptr++;
		i++;
	}

//	Com_DPrintf( DEVELOPER_MSG_IO, "alias %s searches = %d numfound = %d\n", convalias, numsearches, numfound);
	//
	// see if we found any
	//
	if ( !numfound )
		return NULL;

	weight = 0;
	num = totalfoundweight * randweight();

	for ( i=0; i < numfound; i++ )
	{
		weight += foundlist[i]->weight;
		if (num < weight)
		{
			return foundlist[i]->real_name;
		}
	}

	return NULL;
}

void Alias_ListDump( AliasList_t * list )
{
	AliasListNode_t * ptr;
	int i;

	assert( list );
	if ( !list )
		return;

	if ( list->dirty )
	{
		Alias_ListSort( list );
	}

	Com_DPrintf( DEVELOPER_MSG_IO, "Alias List: %s\n", list->name );
	Com_DPrintf( DEVELOPER_MSG_IO, "Alias Name / Weight / Real Name\n" );
	for ( i = 0; i < list->num_in_list; i++ )
	{
		ptr = list->sorted_list[ i ];
		Com_DPrintf( DEVELOPER_MSG_IO, "%32s %3.2f %s\n", ptr->alias_name, ptr->weight, ptr->real_name );
	}
	Com_DPrintf( DEVELOPER_MSG_IO, "%d total aliases\n", list->num_in_list );
}


//
// PUBLIC FUNCTIONS (Default List)
//

const char *   Alias_Find( const char * alias )
{
	if ( !Aliases )
	{
		Aliases = AliasList_New( "Global" );
	}
	return Alias_ListFind( Aliases, alias );
}

qboolean Alias_Add( const char * alias, const char * name, float weight )
{
	if ( !Aliases )
	{
		Aliases = AliasList_New( "Global" );
	}
	return Alias_ListAdd( Aliases, alias, name, weight );
}

qboolean Alias_Delete( const char * alias )
{
	return true;
}

const char *   Alias_FindRandom( const char * alias )
{
	if ( !Aliases ) {
		Aliases = AliasList_New( "Global" );
	}
	return Alias_ListFindRandom( Aliases, alias );
}

void Alias_Dump( void )
{
	if ( !Aliases ) {
		Aliases = AliasList_New( "Global" );
	}
	Alias_ListDump( Aliases );
}

void Alias_Clear( void )
{
	if ( !Aliases ) {
		Aliases = AliasList_New( "Global" );
	}
	Alias_ListClear( Aliases );
}

void AliasRelease( void )
{
	Alias_ListDelete( Aliases );
	Aliases = 0;
}
