Fully Managed alternative to StrCmpLogicalW

Benchmark.txt

BenchmarkDotNet=v0.10.13, OS=Windows 10 Redstone 3 [1709, Fall Creators Update] (10.0.16299.309)
Intel Core i7-6700HQ CPU 2.60GHz (Skylake), 1 CPU, 8 logical cores and 4 physical cores
Frequency=2531253 Hz, Resolution=395.0613 ns, Timer=TSC
  [Host] : .NET Framework 4.7 (CLR 4.0.30319.42000), 64bit RyuJIT-v4.7.2633.0
  Clr    : .NET Framework 4.7 (CLR 4.0.30319.42000), 64bit RyuJIT-v4.7.2633.0

Job=Clr  Runtime=Clr

                      Method |     Mean |    Error |   StdDev | Allocated |
---------------------------- |---------:|---------:|---------:|----------:|
 LexicographicStringComparer | 276.0 us | 5.419 us | 8.595 us |      28 B |
              StrCmpLogicalW | 295.2 us | 5.897 us | 9.181 us |      28 B |
              
BenchmarkDotNet=v0.10.13, OS=Windows 10 Redstone 3 [1709, Fall Creators Update] (10.0.16299.309)
Intel Core i7-6700HQ CPU 2.60GHz (Skylake), 1 CPU, 8 logical cores and 4 physical cores
Frequency=2531253 Hz, Resolution=395.0613 ns, Timer=TSC
.NET Core SDK=2.1.101
  [Host] : .NET Core 2.0.6 (CoreCLR 4.6.26212.01, CoreFX 4.6.26212.01), 64bit RyuJIT
  Core   : .NET Core 2.0.6 (CoreCLR 4.6.26212.01, CoreFX 4.6.26212.01), 64bit RyuJIT

Job=Core  Runtime=Core

                      Method |     Mean |    Error |   StdDev | Allocated |
---------------------------- |---------:|---------:|---------:|----------:|
 LexicographicStringComparer | 124.5 us | 1.617 us | 1.512 us |      88 B |
              StrCmpLogicalW | 119.0 us | 2.215 us | 1.849 us |      88 B |

LexicographicStringComparer.cs

using System;
using System.Collections.Generic;

namespace stuff
{
    /// <summary>
    /// A string comparer that behaves like StrCmpLogicalW
    /// https://msdn.microsoft.com/en-us/library/windows/desktop/bb759947
    /// 
    /// This means:
    /// * case insensitive (ZA == za)
    /// * numbers are treated as numbers (z20 &gt; z3) and assumed positive
    ///     (-100 comes AFTER 10 and 100, because the minus is seen
    ///         as a char, not as part of the number)
    /// * leading zeroes come before anything else (z001 &lt; z01 &lt; z1)
    /// 
    /// Note: Instead of instantiating this, you can also use
    /// <see cref="Comparison(string, string)"/>
    /// if you don't need an <see cref="IComparer{string}"/> but can
    /// use a <see cref="Comparison{string}"/> delegate instead.
    /// </summary>
    /// <remarks>
    /// NOTE: This behaves slightly different than StrCmpLogicalW because
    /// it handles large numbers.
    /// 
    /// At some point, StrCmpLogicalW just gives up trying to parse
    /// something as a number (see the Test cases), while we keep going.
    /// Since we want to sort lexicographily as much as possible,
    /// that difference makes sense.
    /// </remarks>
    public class LexicographicStringComparer : IComparer<string>
    {
        /// <summary>
        /// A <see cref="Comparison{string}"/> delegate.
        /// </summary>
        public static int Comparison(string x, string y)
        {
            // 1 = x > y, -1 = y > x, 0 = x == y
            // Rules: Numbers < Letters. Space < everything
            if (x == y) return 0;
            if (string.IsNullOrEmpty(x) && !string.IsNullOrEmpty(y)) return -1;
            if (!string.IsNullOrEmpty(x) && string.IsNullOrEmpty(y)) return 1;
            if (string.IsNullOrEmpty(x) && string.IsNullOrEmpty(y)) return 0; // "" and null are the same for the purposes of this

            var yl = y.Length;
            for (int i = 0; i < x.Length; i++)
            {
                if (yl <= i) return 1;
                var cx = x[i];
                var cy = y[i];

                if (Char.IsWhiteSpace(cx) && !Char.IsWhiteSpace(cy)) return -1;
                if (!Char.IsWhiteSpace(cx) && Char.IsWhiteSpace(cy)) return 1;

                if (IsDigit(cx))
                {
                    if (!IsDigit(cy))
                    {
                        return -1;
                    }
                    
                    // Both are digits, but now we need to look at them as a whole, since
                    // 10 > 2, but 10 > 002 > 02 > 2
                    var numCmp = CompareNumbers(x, y, i, out int numChars);
                    if (numCmp != 0) return numCmp;
                    i += numChars; // We might have looked at more than one char, e.g., "10" is 2 chars
                }
                else if (IsDigit(cy))
                {
                    return 1;
                }
                else
                {
                    // Do this after the digit check
                    // Case insensitive
                    // Normalize to Uppercase:
                    // https://docs.microsoft.com/en-US/visualstudio/code-quality/ca1308-normalize-strings-to-uppercase
                    var cmp = Char.ToUpper(cx).CompareTo(Char.ToUpper(cy));
                    if (cmp != 0) return cmp;
                }
            }

            // Strings are equal to that point, and y is at least as large as x
            if (y.Length > x.Length) return -1;

            return 0;
        }

        /// <see cref="IComparer{T}.Compare(T, T)"/>
        public int Compare(string x, string y)
            => Comparison(x, y);

        private static int CompareNumbers(string x, string y, int ix, out int numChars)
        {
            var xParsed = ParseNumber(x, ix);
            var yParsed = ParseNumber(y, ix);

            numChars = yParsed.NumCharsRead > xParsed.NumCharsRead
                ? xParsed.NumCharsRead
                : yParsed.NumCharsRead;

            return xParsed.CompareTo(yParsed);
        }

        private unsafe static ParsedNumber ParseNumber(string str, int offset)
        {
            var result = 0;
            var numChars = 0;
            var leadingZeroes = 0;
            var numOverflows = 0;
            bool countZeroes = true;

            fixed (char* strPtr = str)
            {
                for (int j = offset; j < str.Length; j++)
                {
                    char c = *(strPtr + j);
                    if (IsDigit(c))
                    {
                        var cInt = (c - 48); // 48/0x30 is '0'

                        checked
                        {
                            long tmp = (result * 10L) + cInt;
                            if (tmp > int.MaxValue)
                            {
                                numOverflows++;
                                tmp = tmp % int.MaxValue;
                            }
                            result = (int)tmp;
                            numChars++;
                        }

                        if (cInt == 0 && countZeroes)
                        {
                            leadingZeroes++;
                        }
                        else
                        {
                            countZeroes = false;
                        }
                    }
                    else
                    {
                        break;
                    }
                }
            }
            return new ParsedNumber(result, numOverflows, leadingZeroes, numChars);
        }

        private static bool IsDigit(char c) => (c >= '0' && c <= '9');

        /// <summary>
        /// Note that the ParsedNumber is not very useful as a number,
        /// but purely as a way to compare two numbers that are stored in a string.
        /// </summary>
        private struct ParsedNumber : IComparable<ParsedNumber>, IComparer<ParsedNumber>
        {
            /// <summary>
            /// The remainder, that is, the part of the number that
            /// didn't overflow int.MaxValue.
            /// </summary>
            public int Remainder;

            /// <summary>
            /// How often did the number overflow int.MaxValue during parsing?
            /// </summary>
            public int Overflows;

            /// <summary>
            /// How many leading zeroes were there in the string during parsing?
            /// "001" has a LeadingZeroesCount of 2.
            /// "100" has a LeadingZeroesCount of 0.
            /// "010" has a LeadingZeroesCount of 1.
            /// 
            /// This is important, because 001 comes before 01 comes before 1.
            /// </summary>
            public int LeadingZeroesCount;

            /// <summary>
            /// How many characters were read from the input during parsing?
            /// </summary>
            public int NumCharsRead;

            public ParsedNumber(int remainder, int overflows, int leadingZeroes, int numChars)
            {
                Remainder = remainder;
                Overflows = overflows;
                LeadingZeroesCount = leadingZeroes;
                NumCharsRead = numChars;
            }

            public int Compare(ParsedNumber x, ParsedNumber y)
            {
                // Note: if numCharsX and Y aren't equal, this doesn't matter
                // as the return value will be either -1 or 1 anyway

                if (x.Overflows > y.Overflows) return 1;
                if (x.Overflows < y.Overflows) return -1;

                // 001 > 01 > 1
                if (x.Remainder == y.Remainder)
                {
                    if (x.LeadingZeroesCount > y.LeadingZeroesCount) return -1;
                    if (x.LeadingZeroesCount < y.LeadingZeroesCount) return 1;
                }

                if (x.Remainder > y.Remainder) return 1;
                if (x.Remainder < y.Remainder) return -1;
                return 0;
            }

            public int CompareTo(ParsedNumber other)
                => Compare(this, other);
        }
    }
}

LexicographicStringComparerTests.cs

using System.Collections.Generic;
using System.Linq;
using Xunit;

namespace stuff.Tests
{
    public class LexicographicStringComparerTests
    {
        [Fact]
        public void SortsLexicopgrahicly()
        {
            List<string> testItems = new[]{"👾", "z24", "a1", "z2", "z2", "z15", "z1", "🤑",
                       "z3", "z20", "z5", "", "z1a", "za1", "z11", "z 21", "z22", "z a", "za0",
                       "za05", "za01", "za10", "za001", "za005", "ZA7",
                       "za100vx100", "za200vx100","za100vx200","za200vx200",
                       "za100vx20", "za10vx200","za20vx100","za200vx10"
            }.ToList();

            var expectedOrder = new[] { "",
                                "a1", "z 21", "z a", "z1", "z1a", "z2", "z2", "z3", "z5",
                                "z11", "z15", "z20", "z22", "z24", "za0", "za001", "za01", "za1",
                                "za005", "za05", "ZA7", "za10",
                                "za10vx200", "za20vx100", "za100vx20", "za100vx100",
                                "za100vx200", "za200vx10", "za200vx100","za200vx200",
                                "👾", "🤑"};

            testItems.Sort(LexicographicStringComparer.Comparison);
            Assert.Equal(expectedOrder, testItems);
        }

        [Fact]
        public void DealsWithOverflow()
        {
            List<string> testItems = new[]{"a2147483648z",
                       "a2147483647z",
                       "a2147483646z",
                       "a2147483649z",
            }.ToList();

            var expectedOrder = new[] { "a2147483646z", "a2147483647z",
                                        "a2147483648z","a2147483649z",};

            testItems.Sort(LexicographicStringComparer.Comparison);
            Assert.Equal(expectedOrder, testItems);
        }

        [Fact]
        public void DealsWithHugeOverflow()
        {
            // NOTE: This behaves slightly different than StrCmpLogicalW because
            // it handles large numbers.
            //
            // Here, 5 comes first and 401 comes last (before the really long ones)
            // 5, 39, 40, 41, 401
            //
            // Windows however sorts them like this:
            // 39, 40, 401, 41, 5
            //
            // So Windows just gives up parsing them as a number at some point.
            // Since we want to sort lexicographily as much as possible,
            // we keep on treating them as numbers.

            List<string> testItems = new[]{"340282366920938463444927863358058659839",
                       "340282366920938463444927863358058659840",
                       "3402823669209384634449278633580586598401",
                       "340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401",
                       "340282366920938463444927863358058659841",
                       "abc340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401xyz",
                       "ab340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401xyz",
                       "bcd340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401xyz",
                       "34028236692093846344492786335805865985"
            }.ToList();

            var expectedOrder = new[] { "34028236692093846344492786335805865985",
                       "340282366920938463444927863358058659839",
                       "340282366920938463444927863358058659840",
                       "340282366920938463444927863358058659841",
                       "3402823669209384634449278633580586598401",
                       "340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401",
                       "ab340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401xyz",
                       "abc340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401xyz",
                       "bcd340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401xyz" };

            testItems.Sort(LexicographicStringComparer.Comparison);
            Assert.Equal(expectedOrder, testItems);
        }

        [Fact]
        public void LeadingZeroes()
        {
            List<string> testItems = new[] { "1", "0002", "002", "02", "001", "01", "0030", "2", "003", "03", "3", "0031" }.ToList();
            var expectedOrder = new[] { "001", "01", "1", "0002", "002", "02", "2", "003", "03", "3", "0030", "0031" };

            testItems.Sort(LexicographicStringComparer.Comparison);
            Assert.Equal(expectedOrder, testItems);
        }
    }
}

BTW, to test it: just go to https://rextester.com/, start a new C# program, and copy the following there:

            string s = "1234";
            Console.WriteLine(s[0]);
            Console.WriteLine(s[1]);
            Console.WriteLine(s[2]);
            Console.WriteLine(s[3]);