#include <ctype.h>
#include <stdio.h>
#include <string.h>
#include <List.h>
#include "Words.h"

/* 
**  File METAPHON.C 
*/ 

/* 
**  MAXMETAPH is the length of the Metaphone code. 
** 
**  Four is a good compromise value for English names. For comparing words 
**  which are not names or for some non-English names, use a longer code 
**  length for more precise matches. 
** 
**  The default here is 5. 
*/ 

#define MAXMETAPH 6 

static const char *gCmpKey;
static int word_cmp( BString **firstArg, BString **secondArg );

static int word_cmp( BString **firstArg, BString **secondArg )
{
	return word_match( gCmpKey, (*firstArg)->String() ) - word_match( gCmpKey, (*secondArg)->String() );
}

Words::Words( bool useMetaphone )
	: fUseMetaphone( useMetaphone )
{
	
}

Words::Words( BPositionIO *thes, bool useMetaphone )
	: WIndex( thes ),
	fUseMetaphone( useMetaphone )
{
	
}

Words::~Words( void )
{
	
}

Words::Words( const char *dataPath, const char *indexPath, bool useMetaphone )
	: fUseMetaphone( useMetaphone )
{
	if( !useMetaphone )
		entrySize = sizeof( uint32 );
	SetTo( dataPath, indexPath );
}

enum
{
	FIND_WORD,
	GET_WORD,
	GET_FLAGS
};

// Parse the Words file...
status_t Words::BuildIndex( void )
{
	// Buffer Stuff
	char			buffer[16384];
	char			*nptr, *eptr;
	int64			blockOffset;
	int32			blockSize;
	
	// The Word Entry
	WIndexEntry		entry;
	char			entryName[256], *namePtr = entryName;
	char			suffixName[256];
	char			flags[32], *flagsPtr = flags;
	
	// State Info
	int32			state = FIND_WORD;
	
	// Make sure we are at start of file
	dataFile->Seek( 0, SEEK_SET );
	entry.offset = -1;
	
	// Read blocks from thes until eof
	while( true )
	{
		// Get next block
		blockOffset = dataFile->Position();
		if( (blockSize = dataFile->Read( buffer, 16384 )) == 0 )
			break;
		
		// parse block
		for( nptr = buffer, eptr = buffer + blockSize; nptr < eptr; nptr++ )
		{
			// Looking for start of word?
			if( state == FIND_WORD )
			{
				// Is start of word?
				if( isalpha(*nptr) )
				{
					state = GET_WORD;
					*namePtr++ = *nptr; // copy word
					entry.offset = blockOffset + (nptr - buffer);
				}
				else
					entry.offset++;
			}
			// End of word?
			else if( (*nptr == '\n')||(*nptr == '\r') )
			{
				if( namePtr != entryName )
				{
					// Add previous entry to word index
					*namePtr = 0; // terminate word
					*flagsPtr = 0; // terminate flags
					NormalizeWord( entryName, entryName );
					// Add base word
					entry.key = GetKey( entryName );
					AddItem( &entry );
					
					// Add suffixed words if any
					if( flagsPtr != flags )
					{
						//printf( "Base: %s, flags: %s\n", entryName, flags );
						for( flagsPtr=flags; *flagsPtr != 0; flagsPtr++ )
						{
							if( suffix_word( suffixName, entryName, *flagsPtr ) )
							{
								//printf( "Suffix: %s\n", suffixName );
								entry.key = GetKey( suffixName );
								AddItem( &entry );
							}
						}
					}
				}
				// Init new entry
				state = FIND_WORD;
				namePtr = entryName;
				flagsPtr = flags;
			}
			else if( state == GET_WORD ) // Are we looking for a word?
			{
				// Start of flags?
				if( *nptr == '/' )
				{
					*namePtr = 0; // terminate word
					//printf( "Found word: %s\n", entryName );
					
					// Set state to get flags
					state = GET_FLAGS;
				}
				else
					*namePtr++ = *nptr; // copy word
			}
			else if( state == GET_FLAGS ) // Are we getting the flags?
				*flagsPtr++ = *nptr; // copy flag
		} // End for( nptr = buffer, eptr = buffer + blockSize; nptr < eptr; nptr++, entry.size++ )
	} // End while( true )
	
	SortItems();
	return B_OK;
}

/*
**  Character coding array
*/

static char vsvfn[26] = {
      1,16,4,16,9,2,4,16,9,2,0,2,2,2,1,4,0,2,4,4,1,0,0,0,8,0};
/*    A  B C  D E F G  H I J K L M N O P Q R S T U V W X Y Z      */

int32 Words::GetKey( const char *s )
{
	if( fUseMetaphone )
	{
		char		Metaph[12];
		const char	*sPtr;
		int32		key = 0;
		int32		offset;
		char		c;
		
		metaphone( s, Metaph, GENERATE );
		// Compact Metaphone from 6 bytes to 4
		
		// printf( "%s -> %s: \n", s, Metaph );
		
		for( sPtr = Metaph, offset = 25; *sPtr; sPtr++, offset -= 5 )
		{
			c = *sPtr - 'A';
			// printf( "%d,", int16(c) );
			key |= int32(c) << offset;
		}
		for( ; offset >= 0; offset -= 5 )
			key |= int32(31) << offset;
		// printf( ": %ld\n", key );
	return key;
	}
	else
		return WIndex::GetKey( s );
}

/*
**  Macros to access the character coding array
*/

#define vowel(x)  (vsvfn[(x) - 'A'] & 1)  /* AEIOU    */
#define same(x)   (vsvfn[(x) - 'A'] & 2)  /* FJLMNR   */
#define varson(x) (vsvfn[(x) - 'A'] & 4)  /* CGPST    */
#define frontv(x) (vsvfn[(x) - 'A'] & 8)  /* EIY      */
#define noghf(x)  (vsvfn[(x) - 'A'] & 16) /* BDH      */
#define NUL '\0'
/*
**  metaphone()
**
**  Arguments: 1 - The word to be converted to a metaphone code.
**             2 - A MAXMETAPH+1 char field for the result.
**             3 - Function flag:
**                 If 0: Compute the Metaphone code for the first argument,
**                       then compare it to the Metaphone code passed in
**                       the second argument.
**                 If 1: Compute the Metaphone code for the first argument,
**                       then store the result in the area pointed to by the
**                       second argument.
**
**  Returns: If function code is 0, returns Success_ for a match, else Error_.
**           If function code is 1, returns Success_.
*/

bool metaphone(const char *Word, char *Metaph, metaphlag Flag)
{
      char *n, *n_start, *n_end;    /* Pointers to string               */
      char *metaph = NULL, *metaph_end;    /* Pointers to metaph               */
      char ntrans[512];             /* Word with uppercase letters      */
      char newm[MAXMETAPH + 4];     /* New metaph for comparison        */
      int KSflag;                   /* State flag for X translation     */

      /*
      ** Copy word to internal buffer, dropping non-alphabetic characters
      ** and converting to upper case.
      */

      for (n = ntrans + 1, n_end = ntrans + sizeof(ntrans) - 2;
            *Word && n < n_end; ++Word)
      {
            if (isalpha(*Word))
                  *n++ = toupper(*Word);
      }

      if (n == ntrans + 1)
            return false;           /* Return if zero characters        */
      else  n_end = n;              /* Set end of string pointer        */

      /*
      ** Pad with NULs, front and rear
      */

      *n++ = NUL;
      *n   = NUL;
      n    = ntrans;
      *n++ = NUL;

      /*
      ** If doing comparison, redirect pointers
      */

      if (COMPARE == Flag)
      {
            metaph = Metaph;
            Metaph = newm;
      }

      /*
      ** Check for PN, KN, GN, WR, WH, and X at start
      */

      switch (*n)
      {
      case 'P':
      case 'K':
      case 'G':
            if ('N' == *(n + 1))
                  *n++ = NUL;
            break;

      case 'A':
            if ('E' == *(n + 1))
                  *n++ = NUL;
            break;

      case 'W':
            if ('R' == *(n + 1))
                  *n++ = NUL;
            else if ('H' == *(n + 1))
            {
                  *(n + 1) = *n;
                  *n++ = NUL;
            }
            break;

      case 'X':
            *n = 'S';
            break;
      }

      /*
      ** Now loop through the string, stopping at the end of the string
      ** or when the computed Metaphone code is MAXMETAPH characters long.
      */

      KSflag = false;              /* State flag for KStranslation     */
      for (metaph_end = Metaph + MAXMETAPH, n_start = n;
            n <= n_end && Metaph < metaph_end; ++n)
      {
            if (KSflag)
            {
                  KSflag = false;
                  *Metaph++ = *n;
            }
            else
            {
                  /* Drop duplicates except for CC    */

                  if (*(n - 1) == *n && *n != 'C')
                        continue;

                  /* Check for F J L M N R  or first letter vowel */

                  if (same(*n) || (n == n_start && vowel(*n)))
                        *Metaph++ = *n;
                  else switch (*n)
                  {
                  case 'B':
                        if (n < n_end || *(n - 1) != 'M')
                              *Metaph++ = *n;
                        break;

                  case 'C':
                        if (*(n - 1) != 'S' || !frontv(*(n + 1)))
                        {
                              if ('I' == *(n + 1) && 'A' == *(n + 2))
                                    *Metaph++ = 'X';
                              else if (frontv(*(n + 1)))
                                    *Metaph++ = 'S';
                              else if ('H' == *(n + 1))
                                    *Metaph++ = ((n == n_start &&
                                          !vowel(*(n + 2))) ||
                                          'S' == *(n - 1)) ? 'K' : 'X';
                              else  *Metaph++ = 'K';
                        }
                        break;

                  case 'D':
                        *Metaph++ = ('G' == *(n + 1) && frontv(*(n + 2))) ?
                              'J' : 'T';
                        break;

                  case 'G':
                        if ((*(n + 1) != 'H' || vowel(*(n + 2))) &&
                              (*(n + 1) != 'N' || ((n + 1) < n_end &&
                              (*(n + 2) != 'E' || *(n + 3) != 'D'))) &&
                              (*(n - 1) != 'D' || !frontv(*(n + 1))))
                        {
                              *Metaph++ = (frontv(*(n + 1)) &&
                                    *(n + 2) != 'G') ? 'J' : 'K';
                        }
                        else if ('H' == *(n + 1) && !noghf(*(n - 3)) &&
                              *(n - 4) != 'H')
                        {
                              *Metaph++ = 'F';
                        }
                        break;

                  case 'H':
                        if (!varson(*(n - 1)) && (!vowel(*(n - 1)) ||
                              vowel(*(n + 1))))
                        {
                              *Metaph++ = 'H';
                        }
                        break;

                  case 'K':
                        if (*(n - 1) != 'C')
                              *Metaph++ = 'K';
                        break;

                  case 'P':
                        *Metaph++ = ('H' == *(n + 1)) ? 'F' : 'P';
                        break;

                  case 'Q':
                        *Metaph++ = 'K';
                        break;

                  case 'S':
                        *Metaph++ = ('H' == *(n + 1) || ('I' == *(n + 1) &&
                              ('O' == *(n + 2) || 'A' == *(n + 2)))) ?
                              'X' : 'S';
                        break;

                  case 'T':
                        if ('I' == *(n + 1) && ('O' == *(n + 2) ||
                              'A' == *(n + 2)))
                        {
                              *Metaph++ = 'X';
                        }
                        else if ('H' == *(n + 1))
                              *Metaph++ = 'O';
                        else if (*(n + 1) != 'C' || *(n + 2) != 'H')
                              *Metaph++ = 'T';
                        break;

                  case 'V':
                        *Metaph++ = 'F';
                        break;

                  case 'W':
                  case 'Y':
                        if (vowel(*(n + 1)))
                              *Metaph++ = *n;
                        break;

                  case 'X':
                        if (n == n_start)
                              *Metaph++ = 'S';
                        else
                        {
                              *Metaph++ = 'K';
                              KSflag = true;
                        }
                        break;

                  case 'Z':
                        *Metaph++ = 'S';
                        break;
                  }
            }

            /*
            ** Compare new Metaphone code with old
            */

            if (COMPARE == Flag &&
                  *(Metaph - 1) != metaph[(Metaph - newm) - 1])
            {
                  return false;
            }
      }

      /*
      ** If comparing, check if Metaphone codes were equal in length
      */

      if (COMPARE == Flag && metaph[Metaph - newm])
            return false;

      *Metaph = NUL;
      return true;
}

int word_match( const char *reference, const char *test )
{
	const char	*s1, *s2;
	int32 		x = 0;
	char		c1, c2;
	s1 = test;
	s2 = reference;
	
	bool a, b;
	
	while( *s2 || *s1 )
	{
		c1 = tolower(*s1);
		c2 = tolower(*s2);
		
		if( *s2 && *s1 )
		{
			if( c1 != c2 )
			{
				a = (tolower(s1[1]) == c2);
				b = (tolower(s2[1]) == c1);
				// Reversed pair
				if( a && b )
				{
					x += 1;
					s1++;
					s2++;
				}
				// Extra character
				if( a )
				{
					x += 1;
					s1++;
				}
				// Missing Character
				else if( b )
				{
					x += 1;
					s2++;
				}
				// Equivalent Character
				else if( vsvfn[c1] == vsvfn[c2] )
					x++;
				// Unrelated Character
				else
					x += 3;
			}
		}
		else
			x += 1;
		if( *s2 )
			s2++;
		if( *s1 )
			s1++;
	}
	
	return x;
}

int32 suffix_word( char *dst, const char *src, char flag )
{
	char *end;
	
	end = stpcpy( dst, src );
	flag = toupper( flag );
	switch( flag )
	{
		case 'V':
			switch( end[-1] )
			{
				case 'e':
					end = stpcpy( end-1, "ive" );
					break;
				default:
					end = stpcpy( end, "ive" );
					break;
			}
			break;
		case 'N':
			switch( end[-1] )
			{
				case 'e':
					end = stpcpy( end-1, "ion" );
					break;
				case 'y':
					end = stpcpy( end-1, "ication" );
					break;
				default:
					end = stpcpy( end, "en" );
					break;
			}
			break;
		case 'X':
			switch( end[-1] )
			{
				case 'e':
					end = stpcpy( end-1, "ions" );
					break;
				case 'y':
					end = stpcpy( end-1, "ications" );
					break;
				default:
					end = stpcpy( end, "ens" );
					break;
			}
			break;
		case 'H':
			switch( end[-1] )
			{
				case 'y':
					end = stpcpy( end-1, "ieth" );
					break;
				default:
					end = stpcpy( end, "th" );
					break;
			}
			break;
		case 'Y':
			end = stpcpy( end, "ly" );
			break;
		case 'G':
			switch( end[-1] )
			{
				case 'e':
					end = stpcpy( end-1, "ing" );
					break;
				default:
					end = stpcpy( end, "ing" );
					break;
			}
			break;
		case 'J':
			switch( end[-1] )
			{
				case 'e':
					end = stpcpy( end-1, "ings" );
					break;
				default:
					end = stpcpy( end, "ings" );
					break;
			}
			break;
		case 'D':
			switch( end[-1] )
			{
				case 'e':
					end = stpcpy( end-1, "ed" );
					break;
				case 'y':
					if( !strchr( "aeiou", end[-2] ) )
					{
						end = stpcpy( end-1, "ied" );
						break;
					}
					// Fall through
				default:
					end = stpcpy( end, "ed" );
					break;
			}
			break;
		case 'T':
			switch( end[-1] )
			{
				case 'e':
					end = stpcpy( end-1, "est" );
					break;
				case 'y':
					if( !strchr( "aeiou", end[-2] ) )
					{
						end = stpcpy( end-1, "iest" );
						break;
					}
					// Fall through
				default:
					end = stpcpy( end, "est" );
					break;
			}
			break;
		case 'R':
			switch( end[-1] )
			{
				case 'e':
					end = stpcpy( end-1, "er" );
					break;
				case 'y':
					if( !strchr( "aeiou", end[-2] ) )
					{
						end = stpcpy( end-1, "ier" );
						break;
					}
					// Fall through
				default:
					end = stpcpy( end, "er" );
					break;
			}
			break;
		case 'Z':
			switch( end[-1] )
			{
				case 'e':
					end = stpcpy( end-1, "ers" );
					break;
				case 'y':
					if( !strchr( "aeiou", end[-2] ) )
					{
						end = stpcpy( end-1, "iers" );
						break;
					}
					// Fall through
				default:
					end = stpcpy( end, "ers" );
					break;
			}
			break;
		case 'S':
			switch( end[-1] )
			{
				case 's':
				case 'x':
				case 'z':
				case 'h':
					end = stpcpy( end, "es" );
					break;
				case 'y':
					if( !strchr( "aeiou", end[-2] ) )
					{
						end = stpcpy( end-1, "ies" );
						break;
					}
					// Fall through
				default:
					end = stpcpy( end, "s" );
					break;
			}
			break;
		case 'P':
			switch( end[-1] )
			{
				case 'y':
					if( !strchr( "aeiou", end[-2] ) )
					{
						end = stpcpy( end-1, "iness" );
						break;
					}
					// Fall through
				default:
					end = stpcpy( end, "ness" );
					break;
			}
			break;
		case 'M':
			end = stpcpy( end, "'s" );
			break;
		default:
			return 0;
	}
	return end-dst;
}

int32 Words::FindBestMatches( BList *matches, const char *s )
{
	int32		index;
	// printf( "*** Looking for %s: ***\n", s );
	
	if( (index = FindFirst( s )) >= 0 )
	{
		BString		srcWord( s );
		FileEntry	*entry;
		WIndexEntry *indexEntry;
		
		int32		key = (ItemAt( index ))->key;
		int32		suffixLength;
		char		word[128], suffixWord[128];
		const char	*src, *testWord;
		const char 	*suffixFlags;
		char		*dst;
		
		gCmpKey = srcWord.String();
		
		uint8		hashTable[32];
		uint8		hashValue, highHash, lowHash;
		for( int32 i=0; i<32; i++ )
			hashTable[i] = 0;
		
		do
		{
			indexEntry = ItemAt( index );
			// Hash the entry offset; we use this to make sure we don't add
			// the same word file entry twice;
			// It is possible for the same entry in the words file to have
			// multiple entries in the index.
			
			hashValue = indexEntry->offset % 256;
			highHash = hashValue >> 3;
			lowHash = 0x01 << (hashValue & 0x07);
			
			//printf( "Testing Entry: %ld: hash=%d, highHash=%d, lowHash=%d\n", indexEntry->offset, hashValue, (uint16)highHash, (uint16)lowHash );
			
			// Has this entry offset been seen before?
			if( !(hashTable[highHash] & lowHash) )
			{
				//printf( "New Entry\n" );
				hashTable[highHash] |= lowHash; // Mark this offset so we don't add it twice
				
				entry = GetEntry( index );
				src = entry->String();
				while( *src && !isalpha(*src) )
					src++;
				dst = word;
				while( *src && *src != '/' )
					*dst++ = *src++;
				*dst = 0;
				if( *src == '/' )
					suffixFlags = src+1;
				else
					suffixFlags = src;
					
				//printf( "Base Word: %s\n", word );
				//printf( "Flags: %s\n", suffixFlags );
				testWord = word; // Test the base word first
				do
				{
					//printf( "Testing: %s\n", testWord );
					// Does this word match the key
					if( (GetKey( testWord ) == key) &&
					// And does it look close enough to the compare key?
					//word_match( gCmpKey, testWord ) <= int32((strlen( gCmpKey )-1)/2) )
					word_match( gCmpKey, testWord ) <= int32(float(strlen( gCmpKey )-1)*.75) )
					{
						//printf( "Added: %s\n", testWord );
						matches->AddItem( (void *)(new BString( testWord )) ); // Add it to the list
					}
					
					// If suffix, transform and test
					if( *suffixFlags )
					{
						// Repeat until valid suffix found or end is reached
						suffixLength = 0;
						while( *suffixFlags && !(suffixLength=suffix_word( suffixWord, word, *suffixFlags++ )) ) {}
						if( suffixLength )
							testWord = suffixWord;
						else
							testWord = NULL;
					}
					else
						testWord = NULL;
				}while( testWord );
				delete entry;
			}
			//else
				//printf( "Redundant entry\n" );
			index++;
		}while( key == (ItemAt( index ))->key );
		
		return matches->CountItems();
	}
	else
		return 0;
}

void sort_word_list( BList *matches, const char *reference )
{
	if( matches->CountItems() > 0 )
	{
		BString srcWord( reference );
		gCmpKey = srcWord.String();
		matches->SortItems( (int (*)(const void *, const void *))word_cmp );
	}
}
