[Scummvm-cvs-logs] SF.net SVN: scummvm: [31291] scummvm/trunk/engines/agi/predictive.cpp
fingolfin at users.sourceforge.net
fingolfin at users.sourceforge.net
Fri Mar 28 10:17:14 CET 2008
Revision: 31291
http://scummvm.svn.sourceforge.net/scummvm/?rev=31291&view=rev
Author: fingolfin
Date: 2008-03-28 02:17:13 -0700 (Fri, 28 Mar 2008)
Log Message:
-----------
Added FIXME comment regarding sorting of pred.dic; replaced weird binary search code with simple binary search code ;-)
Modified Paths:
--------------
scummvm/trunk/engines/agi/predictive.cpp
Modified: scummvm/trunk/engines/agi/predictive.cpp
===================================================================
--- scummvm/trunk/engines/agi/predictive.cpp 2008-03-28 09:00:30 UTC (rev 31290)
+++ scummvm/trunk/engines/agi/predictive.cpp 2008-03-28 09:17:13 UTC (rev 31291)
@@ -538,6 +538,9 @@
_predictiveDictLineCount = lines;
debug("Loaded %d lines", _predictiveDictLineCount);
+ // FIXME: We use binary search on _predictiveDictLine, yet we make no attempt
+ // to ever sort this array (except for the DS port). That seems risky, doesn't it?
+
#ifdef __DS__
// Sort the DS word completion list, to allow for a binary chop later (in the ds backend)
DS::sortAutoCompleteWordList();
@@ -552,7 +555,7 @@
return false;
}
// Lookup word in the dictionary
- int line = 0, span, cmpRes, len;
+ int line = 0, cmpRes, len;
char target[MAXWORDLEN];
strncpy(target, _currentCode.c_str(), MAXWORDLEN);
@@ -563,25 +566,20 @@
// if there is not an exact match, do it once more for the best matching prefix (drop the space)
len = _currentCode.size() + 1;
for (int i = 0; i < 2; ++i) {
- line = (_predictiveDictLineCount + 1) / 2 - 1;
- // find out the 2^upper_int(log2(_predictiveDictLineCount))
- for (span = 1; span < _predictiveDictLineCount; span <<= 1)
- ;
- span >>= 1;
- do {
+ // Perform a binary search.
+ int hi = _predictiveDictLineCount - 1;
+ int lo = 0;
+ while (lo <= hi) {
+ line = (lo + hi) / 2;
cmpRes = strncmp(_predictiveDictLine[line], target, len);
- if (cmpRes > 0) {
- span /= 2;
- line -= span;
- if (line < 0)
- line = 0;
- } else if (cmpRes < 0) {
- span /= 2;
- line += span;
- if (line >= _predictiveDictLineCount)
- line = _predictiveDictLineCount - 1;
- }
- } while (cmpRes && span);
+ if (cmpRes > 0)
+ hi = line - 1;
+ else if (cmpRes < 0)
+ lo = line + 1;
+ else
+ break;
+ }
+
if (cmpRes == 0) // Exact match found? -> stop now
break;
len--; // Remove the trailing space
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
More information about the Scummvm-git-logs
mailing list