(svn r21343) -Add: Function that compares strings using case insensitive natural sort.

6 files changed, 79 insertions, 4 deletions

diff --git a/config.lib b/config.lib
index a3c34f755..c75c55811 100644
--- a/config.lib
+++ b/config.lib
@@ -2803,9 +2803,9 @@ detect_icu() {
 	log 2 "  returned $version"
 	log 2 "  exit code $ret"
 
-	if [ -z "$version" ] || [ "$ret" != "0" ] || [ "$shortversion" -lt "22" ]; then
-		if [ -n "$shortversion" ] && [ "$shortversion" -lt "22" ]; then
-			log 1 "checking libicu... needs at least version 2.2.0, icu NOT enabled"
+	if [ -z "$version" ] || [ "$ret" != "0" ] || [ "$shortversion" -lt "36" ]; then
+		if [ -n "$shortversion" ] && [ "$shortversion" -lt "36" ]; then
+			log 1 "checking libicu... needs at least version 3.6.0, icu NOT enabled"
 		else
 			log 1 "checking libicu... not found"
 		fi
diff --git a/readme.txt b/readme.txt
index 3a1e53582..690e69445 100644
--- a/readme.txt
+++ b/readme.txt
@@ -431,7 +431,8 @@ The following libraries are used by OpenTTD for:
   - libpng: making screenshots and loading heightmaps
   - libfreetype: loading generic fonts and rendering them
   - libfontconfig: searching for fonts, resolving font names to actual fonts
-  - libicu: handling of right-to-left scripts (e.g. Arabic and Persian)
+  - libicu: handling of right-to-left scripts (e.g. Arabic and Persian) and
+    natural sorting of strings.
 
 OpenTTD does not require any of the libraries to be present, but without
 liblzma you cannot open most recent savegames and without zlib you cannot
diff --git a/src/language.h b/src/language.h
index 5ba424c66..1b4fb497a 100644
--- a/src/language.h
+++ b/src/language.h
@@ -13,6 +13,9 @@
 #define LANGUAGE_H
 
 #include "core/smallvec_type.hpp"
+#ifdef WITH_ICU
+#include <unicode/coll.h>
+#endif /* WITH_ICU */
 
 static const uint8 CASE_GENDER_LEN = 16; ///< The (maximum) length of a case/gender string.
 static const uint8 MAX_NUM_GENDERS =  8; ///< Maximum number of supported genders.
@@ -102,6 +105,10 @@ extern LanguageList _languages;
 /** The currently loaded language. */
 extern const LanguageMetadata *_current_language;
 
+#ifdef WITH_ICU
+extern Collator *_current_collator;
+#endif /* WITH_ICU */
+
 bool ReadLanguagePack(const LanguageMetadata *lang);
 const LanguageMetadata *GetLanguage(byte newgrflangid);
 
diff --git a/src/string.cpp b/src/string.cpp
index bad29649d..c3d6f5bc0 100644
--- a/src/string.cpp
+++ b/src/string.cpp
@@ -24,6 +24,13 @@
 #include <errno.h> // required by vsnprintf implementation for MSVC
 #endif
 
+#ifdef WITH_ICU
+/* Required by strnatcmp. */
+#include <unicode/ustring.h>
+#include "language.h"
+#include "gfx_func.h"
+#endif /* WITH_ICU */
+
 /**
  * Safer implementation of vsnprintf; same as vsnprintf except:
  * - last instead of size, i.e. replace sizeof with lastof.
@@ -463,3 +470,38 @@ char *strcasestr(const char *haystack, const char *needle)
 	return NULL;
 }
 #endif /* DEFINE_STRCASESTR */
+
+/**
+ * Compares two strings using case insensitive natural sort.
+ *
+ * @param s1 First string to compare.
+ * @param s2 Second string to compare.
+ * @return Less than zero if s1 < s2, zero if s1 == s2, greater than zero if s1 > s2.
+ */
+int strnatcmp(const char *s1, const char *s2)
+{
+#ifdef WITH_ICU
+	if (_current_collator != NULL) {
+		UErrorCode status = U_ZERO_ERROR;
+		int result;
+
+		/* We want to use the new faster method for ICU 4.2 and higher. */
+#if U_ICU_VERSION_MAJOR_NUM > 4 || (U_ICU_VERSION_MAJOR_NUM == 4 && U_ICU_VERSION_MINOR_NUM >= 2)
+		/* The StringPiece parameter gets implicitly constructed from the char *. */
+		result = _current_collator->compareUTF8(s1, s2, status);
+#else /* The following for 4.0 and lower. */
+		UChar buffer1[DRAW_STRING_BUFFER];
+		u_strFromUTF8Lenient(buffer1, lengthof(buffer1), NULL, s1, -1, &status);
+		UChar buffer2[DRAW_STRING_BUFFER];
+		u_strFromUTF8Lenient(buffer2, lengthof(buffer2), NULL, s2, -1, &status);
+
+		result = _current_collator->compare(buffer1, buffer2, status);
+#endif /* ICU version check. */
+		if (U_SUCCESS(status)) return result;
+	}
+
+#endif /* WITH_ICU */
+
+	/* Do a normal comparison if ICU is missing or if we cannot create a collator. */
+	return strcasecmp(s1, s2);
+}
diff --git a/src/strings.cpp b/src/strings.cpp
index 03e6521cf..f6c62a947 100644
--- a/src/strings.cpp
+++ b/src/strings.cpp
@@ -48,6 +48,10 @@ const LanguageMetadata *_current_language = NULL; ///< The currently loaded lang
 TextDirection _current_text_dir; ///< Text direction of the currently selected language.
 uint64 _decode_parameters[20];   ///< Global array of string parameters. To access, use #SetDParam.
 
+#ifdef WITH_ICU
+Collator *_current_collator = NULL;               ///< Collator for the language currently in use.
+#endif /* WITH_ICU */
+
 static char *StationGetSpecialString(char *buff, int x, const char *last);
 static char *GetSpecialTownNameString(char *buff, int ind, uint32 seed, const char *last);
 static char *GetSpecialNameString(char *buff, int ind, int64 *argv, const char *last);
@@ -1392,6 +1396,25 @@ bool ReadLanguagePack(const LanguageMetadata *lang)
 	strecpy(_config_language_file, c_file, lastof(_config_language_file));
 	SetCurrentGrfLangID(_current_language->newgrflangid);
 
+#ifdef WITH_ICU
+	/* Delete previous collator. */
+	if (_current_collator != NULL) {
+		delete _current_collator;
+		_current_collator = NULL;
+	}
+
+	/* Create a collator instance for our current locale. */
+	UErrorCode status = U_ZERO_ERROR;
+	_current_collator = Collator::createInstance(Locale(_current_language->isocode), status);
+	/* Sort number substrings by their numerical value. */
+	if (_current_collator != NULL) _current_collator->setAttribute(UCOL_NUMERIC_COLLATION, UCOL_ON, status);
+	/* Avoid using the collator if it is not correctly set. */
+	if (U_FAILURE(status)) {
+		delete _current_collator;
+		_current_collator = NULL;
+	}
+#endif /* WITH_ICU */
+
 	/* Some lists need to be sorted again after a language change. */
 	InitializeSortedCargoSpecs();
 	SortIndustryTypes();
diff --git a/src/strings_func.h b/src/strings_func.h
index 706dbd1f0..49176fa1b 100644
--- a/src/strings_func.h
+++ b/src/strings_func.h
@@ -110,4 +110,6 @@ struct StringIDCompare
 
 void CheckForMissingGlyphsInLoadedLanguagePack();
 
+int strnatcmp(const char *s1, const char *s2);
+
 #endif /* STRINGS_TYPE_H */