Word completion code that uses predictive dictionary ported from branch0-10-0

svn-id: r28124

2 files changed, 148 insertions, 32 deletions

diff --git a/backends/platform/ds/arm9/source/wordcompletion.cpp b/backends/platform/ds/arm9/source/wordcompletion.cpp
index a73656ea61..b8fbf6c5cd 100644
--- a/backends/platform/ds/arm9/source/wordcompletion.cpp
+++ b/backends/platform/ds/arm9/source/wordcompletion.cpp
@@ -5,8 +5,85 @@
 #ifndef DISABLE_AGI
 
 namespace DS {
+// Default dictionary is about 64Kb, so 128Kb should be enough for future expansion
+#define WORD_BUFFER_SIZE (128 * 1024)
+
+// Default dictionary has ~8000 words
+#define MAX_WORD_COUNT 16000
+
+char wordBuffer[WORD_BUFFER_SIZE];
+int wordBufferPos = 0;
+
+char* wordBufferPtr[MAX_WORD_COUNT];
+int wordBufferPtrPos = 0;
+
+void addAutoCompleteLine(char* line) {
+
+	while (*line != 0)
+	{
+		char word[32];
+		int length;
+		
+		// Skip the T9-style numbers
+		while (*line != ' ')
+		{
+			line++;
+		}
+		line++;
+
+		do {
+			length = 0;
+
+			if (*line == ' ') line++;
+
+
+			// Copy the new word 
+			do {
+				word[length++] = *line++;
+			} while ((*line != '\0') && (*line != ' ') && (*line != '\n'));
+
+			word[length] = '\0';
+
+
+			// Store a pointer to the start of the word
+			wordBufferPtr[wordBufferPtrPos++] = &wordBuffer[wordBufferPos];
+	
+			// copy the new word into the buffer
+			strcpy(&wordBuffer[wordBufferPos], word);
+			wordBufferPos += strlen(word) + 1;
+		} while (*line == ' ');
+	}
+}
+
+int stringCompare(const void* a, const void* b) {
+	const char** as = (const char **) a;
+	const char** bs = (const char **) b;
+
+	return scumm_stricmp(*as, *bs);
+}
+
+void sortAutoCompleteWordList() {
+	// Sort the whole word list into alphabetical order
+	qsort((void *) wordBufferPtr, wordBufferPtrPos, 4, stringCompare);
+}
+
+// Sends the current available words to the virtual keyboard code for display
+bool findWordCompletions(char* input)
+{
+	char testWord[32];
+	int min = 0;
+	int max = wordBufferPtrPos - 1;
+	char* word;
+	int position;
+	char partialWord[32];
+
+	// Early out if dictionary not loaded
+	if (wordBufferPtrPos == 0)
+		return false;
+
+	OSystem_DS* system = (OSystem_DS *) g_system;
+	system->clearAutoComplete();
 
-void findWordCompletions(char* input) {
 	int start = 0;
 	for (int r = strlen(input) - 1; r>0; r--) {
 		if (input[r] == ' ') {
@@ -14,52 +91,89 @@ void findWordCompletions(char* input) {
 			break;
 		}
 	}
+	strcpy(partialWord, &input[start]);
+
+	if (strlen(partialWord) == 0)
+	{
+		return false;
+	}
 
-	char word[32];
-	strcpy(word, &input[start]);
+	do {
+		position = min + ((max - min) / 2);
 
-	int fchr = word[0] - 'a';
-	int len = strlen(word);
+		// Get the word from the dictonary line
+		word = wordBufferPtr[position];
 
-	OSystem_DS* system = (OSystem_DS *) g_system;
-	system->clearAutoComplete();
-	system->setCharactersEntered(strlen(word));
+		
 
-	if (strlen(word) == 0) {
-		return;
-	}		
+		// Now check to see if the word is before or after the stub we're after
+		int result = scumm_stricmp((const char *) partialWord, (const char *) word);
+		
+		if (result == 0) {
+			// We've found the whole word.  Aren't we good.
+			break;
+		} else if (result > 0) {
+			// We're too early, so change the minimum position
+			min = position + 1;
+		} else if (result < 0) {
+			// We're too early, so change the maximum position
+			max = position - 1;
+		}
+
+//		consolePrintf("Word: %s, (%d, %d) result: %d\n", word, min, max, result);
 
-	uint8 *wordList = Agi::AgiEngine::getWordsData();
-	uint8 *wordListEnd = Agi::AgiEngine::getWordsData() + Agi::AgiEngine::getWordsDataSize();
+	} while (max - min > 0);
 
-	/* Get the offset to the first word beginning with the
-	 * right character
-	 */
-	wordList += READ_BE_UINT16(wordList + 2 * fchr);
+	position = min;
+	word = wordBufferPtr[position];
+	//consolePrintf("Final word: %s\n", word);
 
-	char currentWord[32];
+	
 
+	system->setCharactersEntered(strlen(partialWord));
 	
-	while (wordList < wordListEnd) {
-		int pos = *wordList++;		// Number of chars to keep from previous word
 
-		if (wordList == wordListEnd)
+	bool match = true;
+
+
+	for (int r = 0; r < strlen(partialWord); r++) {
+		if (word[r] != partialWord[r]) {
+			match = false;
 			break;
+		}
+	}
 
-		char c;
-		do {
-			c = *wordList++;
-			currentWord[pos++] =  (~c) & 0x7F;
-		} while ((c & 0x80) == 0);		// Top bit indicates end of word
-		currentWord[pos++] = '\0';
+	if (!match) {
+		position++;
+		if (position == wordBufferPtrPos) return false;
+		word = wordBufferPtr[position];
+//		consolePrintf("Final word: %s\n", word);
+	}
+
+
+	match = true;
 
-		if (!strncmp(currentWord, word, strlen(word))) {
-			system->addAutoComplete(currentWord);
+	do {
+
+		for (int r = 0; r < strlen(partialWord); r++) {
+			if (word[r] != partialWord[r]) {
+				match = false;
+				break;
+			}
+		}
+	
+		if (match) {
+			system->addAutoComplete(word);
 		}
 
-		wordList += 2;	// Skip the two byte word id.
+		position++;
+		if (position < wordBufferPtrPos) {
+			word = wordBufferPtr[position];
+		}
 
-	}
+	} while ((match) && (position < wordBufferPtrPos));
+
+	return true;
 
 }
 
diff --git a/backends/platform/ds/arm9/source/wordcompletion.h b/backends/platform/ds/arm9/source/wordcompletion.h
index b0d43713cc..39be8511bf 100644
--- a/backends/platform/ds/arm9/source/wordcompletion.h
+++ b/backends/platform/ds/arm9/source/wordcompletion.h
@@ -3,6 +3,8 @@
 
 namespace DS {
 
-extern void findWordCompletions(char* input);
+extern bool findWordCompletions(char* input);
+extern void addAutoCompleteLine(char* line);
+extern void sortAutoCompleteWordList();
 
 }
\ No newline at end of file