// RE: https://stackoverflow.com/q/75986766/1690217

​

using System;

using System.Linq;

using System.Collections.Generic;

public class Program

{

    public static void Main()

    {

        Console.WriteLine("Test LexicographicToAlphaNumeric output:");

        var tests = new string [] {

            "Bird 10",

            "Bird 2",

            "Bird 1",

            "20Lions",

            "5Lions",

            "red10blue",

            "Red9blue",

            "red100Blue"

        };

        foreach(var x in tests.Select(x => LexicographicToAlphaNumeric(x)).OrderBy(x => x))

            Console.WriteLine(x);

        Console.WriteLine();

        Console.WriteLine();

        Console.WriteLine("Test Categorized Sorting output:");

        var somedata = new List<string> {"<some data>",

            "  <some data else>",

            "</some data>",

            "<Animal>",

            "  <Animal Name=\"Lion\" Group=\"Feline\" Colour=\"Brown\" />",

            "  <Animal Name=\"Zebra\" Group=\"Equidae\" Colour=\"Black and White\" />",

            "  <Animal Name=\"Tuna\" Group=\"Fish\" Colour=\"Gray\" />",

            "  <Animal Name=\"Horse1\" Group=\"Equidae\" Colour=\"Black\" />",

            "  <Animal Name=\"Horse10\" Group=\"Equidae\" Colour=\"White\" />",

            "  <Animal Name=\"Horse2\" Group=\"Equidae\" Colour=\"White\" />",

            "  <Animal Name=\"Dog20\" Group=\"Canidae\" Colour=\"Black\" />",

            "  <Animal Name=\"Dog2\" Group=\"Canidae\" Colour=\"Black\" />",

            "  <Animal Name=\"Cat\" Group=\"Feline\" Colour=\"Various\" />",

            "  <Animal Name=\"Falcon\" Group=\"Bird 1\" Colour=\"Brown\" />",

            "  <Animal Name=\"Duck\" Group=\"Bird 2\" Colour=\"White\" />",

            "  <Animal Name=\"Eagle\" Group=\"Bird 1\" Colour=\"Brown\" />",

            "  <Animal Name=\"Shark\" Group=\"Fish\" Colour=\"Gray\" />",

            "  <Animal Name=\"Mouse\" Group=\"Rodent\" Colour=\"Brown\" />",

            "</Animal>",

            "<some other data>",

            "  <bla bla bla>",

            "</some other data>"};

        // make the items quite large

        //foreach(var i in Enumerable.Range(1,12))

        //  somedata.AddRange(somedata);

​

        // Helpers for the top level grouping set

        int setId = 0;

        string sortSetPrefix = "<Animal Name=";

        bool isInSortSet = false;

        // Helpers for the "Group=" grouping set

        var groupRegex = new System.Text.RegularExpressions.Regex(@"Group=\""([^\""]*)\""");

        var nameRegex = new System.Text.RegularExpressions.Regex(@"Name=\""([^\""]*)\""");

        var sortedData = somedata.Select((line, index) => 

                                    {

                                        var lineInSortSet = line.Trim().StartsWith(sortSetPrefix);

                                        if (lineInSortSet != isInSortSet) 

                                        {

                                            setId ++;

                                            isInSortSet = lineInSortSet;

                                        }

​

                                        // NOTE: Match.Value is NOT the captured value, but the whole value: Group="Equidae"

                                        //       This will produce the correct results for less code/effort 

                                        var groupName = LexicographicToAlphaNumeric(groupRegex.Match(line).Value);

                                        var animalName = LexicographicToAlphaNumeric(nameRegex.Match(line).Value);

                                        return new { line, index, setId, groupName, animalName };

                                    })

                                 .ToList() // Cache the results to reduce re-entry of the above logic during sorting.

                                 .OrderBy(x => x.setId).ThenBy(x => x.groupName).ThenBy(x => x.animalName).ThenBy(x => x.index)

                                 //.Select(x => x.line) // Commented out this line so we can see the details in the output

                                 .ToList();

        // Write the results to the output

        foreach(var x in sortedData)

        {

            Console.Write(String.Format("{0},{1},{2},{3:000}: ", x.setId, x.groupName, x.animalName, x.index).PadRight(50));

            Console.WriteLine(x.line);

        }

    }

    /// <summary> Pad numeric portions of a string to allow natural lexicographic sorting to behave like numerical sorting for the numeric components</summary>

    /// <remarks> using the same categorization technique to simplify the explanation, have not tested this for performance, and I just love the name ;)</remarks>

    /// <param name="value">The string value to pad the numbers in</param>

    /// <param name="size">The number of digits to pad the numeric values out to, by default 3 digits</param>

    /// <returns> alphanumeric string that so that "Bird 2" becomes "Bird 02", to allow "Bird 2" to be sorted before "Bird 10"<returns>

    public static string LexicographicToAlphaNumeric(string value, int size = 3)

    {

        // exit if there is nothing to process.

        if (String.IsNullOrWhiteSpace(value)) return value;

        int groupId = 0;

        bool isNumberGroup = false;

        return String.Join("", value.Select((c, index) => {

            var isNumber = Char.IsDigit(c); // NOTE: will not support decimals

            if( isNumber != isNumberGroup)

            {

                groupId ++;

                isNumberGroup = isNumber;

            }

            return new { c, isNumber, groupId, index };

        })

            .GroupBy(c => c.groupId)

            .Select(g => g.First().isNumber ? new string(g.Select(x => x.c).ToArray()).PadLeft(size, '0') : new string(g.Select(x => x.c).ToArray())));

    }

}