String comparer for sorting numeric strings logically

[Peter-Juhasz]

Rationale

For sorting purposes it's common to need portions of strings containing numbers to be treated like numbers. Consider the list of strings "Windows 7", "Windows 10".

Using the Ordinal StringComparer to sort the list one would get

Windows 10
Windows 7

but the desired ascending logical sort would be

Windows 7
Windows 10

Proposed API

 namespace System {
     public class StringComparer {
+        public static StringComparer Create(CultureInfo culture, CompareOptions options);
     }
 }
 namespace System.Globalization {
     public enum CompareOptions {
+        NumericOrdering = 0x00000020
     }
 }

Usage

var list = new List<string> { "Windows 10", "Windows 7" };
list.Sort(StringComparer.Logical); // List is now "Windows 7", "Windows 10"

This would also be good for sorting strings containing IP addresses.

Details

• Logical is a convenience property equivalent to the result of Create(CultureInfo.CurrentCulture, CompareOptions.Logical)
• LogicalIgnoreCase is a convenience property equivalent to the result of Create(CultureInfo.CurrentCulture, CompareOptions.Logical | CompareOptions.IgnoreCase)
• Non-numeric sequences will be evaluated with the culture provided.
• Numeric sequences will be determined by the result of Char.IsDigit.
• All UTF-16 digits will be supported and are manually parsed using Char.GetNumericValue.
• Only positive integral values without digit separators will be supported directly.
• Numbers will be treated as ulongs. Logic for overflows will have to be considered.
• The string Windows 8.1 would be considered 4 sequences. The Windows would be a string sequence, the 8 would be a numeric sequence, the . would be another string sequence, and the 1 would be another numeric sequence.
• This API could later be expanded to include support for allowing signs, decimals, and digit separators through the use of overloads accepting a NumberStyles parameter.
• When a numeric and string sequence are considered at the same time the numeric sequence always comes before the string sequence so when sorting the following list, "a", "7" the number 7 will be sorted before the letter a.
• Existing methods that take a CompareOptions parameter as input will need to be updated to support the new Logical member.

Open Questions

• Should CompareOptions.Logical be implemented as the flag option SORT_DIGITSASNUMBERS to the dwCmpFlags parameter of CompareStringEx? Using it's implementation should be more efficient but later expanding support for NumberStyles will require a re-implementation with matching behavior.

Updates

• Added Logical and LogicalIgnoreCase properties.
• Added support for all UTF-16 digits.
• Added more CreateLogical overloads to match the Create method.
• Added retrieval of the NumberFormatInfo from the StringComparer parameter when not explicitly provided and is a CultureAwareComparer.
• Removed CreateLogical overloads that matched the Create method.
• Switched to only supporting positive integral values without digit separators.
• Added consideration of comparing a numeric sequence with a string sequence.
• Added the flag member CompareOptions.Logical and changed CreateLogical to be just an overload of Create.

[terrajobst]

That's a good suggestion. Would you be willing to make an API proposal?

[MgSam]

I think conceptually this is a good idea, but there are a lot of details that need to be worked out. It seems like such a comparer might want to take options which control how it behaves. For example, are commas in numbers ok? Spaces? Decimal points? How are different cultures handled?

[sharwell]

While it's easy to define the behavior on Windows systems as following StrCmpLogicalW, this could be problematic in the long run.

1. The precise behavior of StrCmpLogicalW is not only undocumented, but it explicitly states that it can change in future releases of Windows.
2. The behavior of this method is not case-sensitive, and there is no case-sensitive method which is otherwise equivalent. It would be strange, for example, to provide StringComparer.LogicalIgnoreCase without providing StringComparer.Logical.

I believe you could define a reasonable API proposal in terms of a lexicographical ordering of substrings divided at numeric boundaries. Sequences of non-digits would be compared using StringComparer.CurrentCulture or StringComparer.CurrentCultureIgnoreCase, and sequences of digits would be compared according to their numeric values.

[Peter-Juhasz]

The comparer should require an IFormatProvider or NumberFormatInfo; which can be passed in the constructor or it should use the current one from the owning thread.

@terrajobst This is a problem I am facing in almost every business application: proper ordering even if the strings contain numbers. I don't have time to make a PR or document it well, but I would be very happy to see it in the new releases of the core framework. I think the use case is clear enough.

[eatdrinksleepcode]

This is a need that I have often faced. If @Peter-Juhasz does not have the time to create the API proposal or implement it, I would be interested in taking it on.

[sharwell]

@Peter-Juhasz There is probably no need to consider the NumberFormatInfo. As stated in the documentation for NumberFormatInfo.NativeDigits:

The character set that is specified by the NativeDigits property has no effect on parsing or formatting operations. Only the Basic Latin digits 0 (U+0030) through 9 (U+0039) are used when formatting or parsing numeric values or date and time values.

If StringComparer.Logical and StringComparer.LogicalIgnoreCase were defined to use StringComparer.CurrentCulture and StringComparer.CurrentCultureIgnoreCase for comparing non-digits, the culture used for the comparison is clear.

On a side note, even if used there is no need to explicitly provide the NumberFormatInfo to the comparer since the current culture information already provides it.

[tarekgh]

Looks in Windows, CompareStringEx can be used with the flag SORT_DIGITSASNUMBERS. I didn't look at ICU if it support such functionality too.

[krwq]

I believe there is few things which need to be worked on here:

• check if there is linux implementation existing and if it behaves similarly to CompareStringEx with SORT_DIGITSASNUMBERS
• should we provide all permutations for all comparers now or perhaps generate comparer based on some settings (perhaps we already have something like that which we might be able to inject this log in and I might not be aware of it)

I think this would be a nice addition but it needs some work.