Implement binary search in QLocale's likely sub-tag lookup

Follow through on a comment from 2012: sort the likely subtag array
(in the CLDR update script) and use bsearch to find entries in it.

This simplifies QLocaleXmlReader.likelyMap() slightly, moving the
detection of last entry to LocaleDataWriter.likelySubtags(), but
requires collecting all likely sub-tag mapping pairs (rather than just
passing them through from read to write via generators) in order to
sort them.

Change-Id: Ieb6875ccde1ddbd475ae68c0766a666ec32b7005
Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io>

2 files changed, 19 insertions, 5 deletions

diff --git a/util/locale_database/qlocalexml.py b/util/locale_database/qlocalexml.py
index 97b369fde8..e5aadba995 100644
--- a/util/locale_database/qlocalexml.py
+++ b/util/locale_database/qlocalexml.py
@@ -183,12 +183,11 @@ class QLocaleXmlReader (object):
         def ids(t):
             return tuple(x[0] for x in t)
 
-        for i, pair in enumerate(self.__likely, 1):
+        for pair in self.__likely:
             have = self.__fromNames(pair[0])
             give = self.__fromNames(pair[1])
             yield ('_'.join(tag(have)), ids(have),
-                   '_'.join(tag(give)), ids(give),
-                   i == len(self.__likely))
+                   '_'.join(tag(give)), ids(give))
 
     def defaultMap(self):
         """Map language and script to their default country by ID.
diff --git a/util/locale_database/qlocalexml2cpp.py b/util/locale_database/qlocalexml2cpp.py
index 40f5ef3735..1483545ce7 100755
--- a/util/locale_database/qlocalexml2cpp.py
+++ b/util/locale_database/qlocalexml2cpp.py
@@ -163,11 +163,26 @@ class LocaleSourceEditor (SourceFileEditor):
 
 class LocaleDataWriter (LocaleSourceEditor):
     def likelySubtags(self, likely):
+        # First sort likely, so that we can use binary search in C++
+        # code. Although the entries are (lang, script, region), sort
+        # as (lang, region, script) and sort 0 after all non-zero
+        # values. This ensures that, when several mappings partially
+        # match a requested locale, the one we should prefer to use
+        # appears first.
+        huge = 0x10000 # > any ushort; all tag values are ushort
+        def keyLikely(entry):
+            have = entry[1] # Numeric id triple
+            return have[0] or huge, have[2] or huge, have[1] or huge # language, region, script
+        likely = list(likely) # Turn generator into list so we can sort it
+        likely.sort(key=keyLikely)
+
+        i = 0
         self.writer.write('static const QLocaleId likely_subtags[] = {\n')
-        for had, have, got, give, last in likely:
+        for had, have, got, give in likely:
+            i += 1
             self.writer.write('    {{ {:3d}, {:3d}, {:3d} }}'.format(*have))
             self.writer.write(', {{ {:3d}, {:3d}, {:3d} }}'.format(*give))
-            self.writer.write(' ' if last else ',')
+            self.writer.write(' ' if i == len(likely) else ',')
             self.writer.write(' // {} -> {}\n'.format(had, got))
         self.writer.write('};\n\n')