haiku.git

/*
Open Tracker License

Terms and Conditions

Copyright (c) 1991-2001, Be Incorporated. All rights reserved.

Permission is hereby granted, free of charge, to any person obtaining a copy of
this software and associated documentation files (the "Software"), to deal in
the Software without restriction, including without limitation the rights to
use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
of the Software, and to permit persons to whom the Software is furnished to do
so, subject to the following conditions:

The above copyright notice and this permission notice applies to all licensees
and shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF TITLE, MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
BE INCORPORATED BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF, OR IN CONNECTION
WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Except as contained in this notice, the name of Be Incorporated shall not be
used in advertising or otherwise to promote the sale, use or other dealings in
this Software without prior written authorization from Be Incorporated.

BeMail(TM), Tracker(TM), Be(R), BeOS(R), and BeIA(TM) are trademarks or registered trademarks
of Be Incorporated in the United States and other countries. Other brand product
names are registered trademarks or trademarks of their respective holders.
All rights reserved.
*/


#include "Words.h"

#include <ctype.h>
#include <stdio.h>
#include <string.h>


enum {
	FIND_WORD,
	GET_WORD,
	GET_FLAGS
};


/*
	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


// Character coding array, A-Z
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};


static const char* gCmpKey;


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)
		fEntrySize = sizeof(uint32);
	SetTo(dataPath, indexPath);
}


status_t
Words::BuildIndex(void)
{
	// Parse the Words file...

	// 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
	fDataFile->Seek(0, SEEK_SET);
	entry.offset = -1;

	// Read blocks from thes until eof
	while (true) {
		// Get next block
		blockOffset = fDataFile->Position();
		if ((blockSize = fDataFile->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++;
				}
			} else if ((*nptr == '\n') || (*nptr == '\r')) {
				// End of word?

				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) {
				// Start of flags?
				if (*nptr == '/') {
					*namePtr = 0; // terminate word
					// printf("Found word: %s\n", entryName);

					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;
}


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[(unsigned)c1] == vsvfn[(unsigned)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(new BString(testWord));
					}

					// 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);
	}
}