using System;
using System.Collections.Generic;
using System.Globalization;

public static class SpanExtensions
{
    private static ReadOnlySpan<char> TrimStart(this ReadOnlySpan<char> span, char trimChar)
    {
        int start = 0;
        while (start < span.Length && span[start] == trimChar)
            start++;
    
        return span.Slice(start);
    }
}

public class NaturalSort
{
    public static int CompareStrings(CultureInfo culture, CompareOptions options, string x, string y)
    {
        if (x == null || y == null) return string.Compare(x, y, StringComparison.Ordinal);

        var compareInfo = culture.CompareInfo;
        int xPos = 0, yPos = 0;

        while (xPos < x.Length && yPos < y.Length)
        {
            bool xIsDigit = char.IsDigit(x[xPos]);
            bool yIsDigit = char.IsDigit(y[yPos]);

            if (xIsDigit && yIsDigit)
            {
                int numberComparison = CompareNumbers(x, ref xPos, y, ref yPos);
                if (numberComparison != 0) return numberComparison;
            }
            else
            {
                int charComparison = compareInfo.Compare(x, xPos, 1, y, yPos, 1, options);
                if (charComparison != 0) return charComparison;
                xPos++;
                yPos++;
            }
        }

        // Handle remaining characters
        if (xPos < x.Length) return 1;
        if (yPos < y.Length) return -1;

        return 0;
    }
    
    private static int CompareNumbers(string x, ref int xPos, string y, ref int yPos)
    {
        int xStart = xPos, yStart = yPos;
    
        while (xPos < x.Length && char.IsDigit(x[xPos])) xPos++;
        while (yPos < y.Length && char.IsDigit(y[yPos])) yPos++;
    
        var xSpan = x.AsSpan(xStart, xPos - xStart).TrimStart('0');
        var ySpan = y.AsSpan(yStart, yPos - yStart).TrimStart('0');
    
        if (xSpan.Length != ySpan.Length)
            return xSpan.Length.CompareTo(ySpan.Length);
    
        for (int i = 0; i < xSpan.Length; i++)
        {
            if (xSpan[i] != ySpan[i])
                return xSpan[i].CompareTo(ySpan[i]);
        }
    
        return 0;
    }
}


public class NaturalSortComparer : IComparer<string>
{
    public static NaturalSortComparer Ordinal { get; } = new NaturalSortComparer(CultureInfo.InvariantCulture, CompareOptions.Ordinal);
    public static NaturalSortComparer OrdinalIgnoreCase { get; } = new NaturalSortComparer(CultureInfo.InvariantCulture, CompareOptions.OrdinalIgnoreCase);
    public static NaturalSortComparer CurrentCulture { get; } = new NaturalSortComparer(CultureInfo.CurrentCulture, CompareOptions.None);
    public static NaturalSortComparer CurrentCultureIgnoreCase { get; } = new NaturalSortComparer(CultureInfo.CurrentCulture, CompareOptions.IgnoreCase);
    public static NaturalSortComparer InvariantCulture { get; } = new NaturalSortComparer(CultureInfo.InvariantCulture, CompareOptions.None);
    public static NaturalSortComparer InvariantCultureIgnoreCase { get; } = new NaturalSortComparer(CultureInfo.InvariantCulture, CompareOptions.IgnoreCase);

    public NaturalSortComparer(CultureInfo culture, CompareOptions options)
    {
        Culture = culture;
        Options = options;
    }

    public CultureInfo Culture { get; }
    public CompareOptions Options { get; }

    public int Compare(string x, string y)
    {
        return NaturalSort.CompareStrings(Culture, Options, x, y);
    }
}

using System;
using System.Collections.Generic;
using System.Globalization;
using System.Linq;

class Program
{
    static void Main()
    {
        // Voorbeeldlijst met strings
        var items = new List<string>
        {
            "file10.txt",
            "file2.txt",
            "file1.txt",
            "file20.txt",
            "file3.txt"
        };

        Console.WriteLine("Oorspronkelijke lijst:");
        foreach (var item in items)
        {
            Console.WriteLine(item);
        }

        // Sorteer met NaturalSortComparer
        Console.WriteLine("\nGesorteerd (Natural Sort):");
        var sorted = items.OrderBy(x => x, NaturalSortComparer.InvariantCulture);
        foreach (var item in sorted)
        {
            Console.WriteLine(item);
        }

        // Sorteer omgekeerd met NaturalSortComparer
        Console.WriteLine("\nOmgekeerd gesorteerd (Natural Sort):");
        var reverseSorted = items.OrderByDescending(x => x, NaturalSortComparer.InvariantCulture);
        foreach (var item in reverseSorted)
        {
            Console.WriteLine(item);
        }
    }
}

function compareStrings(x: string, y: string): number {
    if (x === null || y === null) return x === y ? 0 : x === null ? -1 : 1;

    let xPos = 0, yPos = 0;

    while (xPos < x.length && yPos < y.length) {
        const xIsDigit = isDigit(x[xPos]);
        const yIsDigit = isDigit(y[yPos]);

        if (xIsDigit && yIsDigit) {
            const numberComparison = compareNumbers(x, xPos, y, yPos);
            if (numberComparison.result !== 0) return numberComparison.result;
            xPos = numberComparison.xPos;
            yPos = numberComparison.yPos;
        } else {
            const charComparison = x[xPos].localeCompare(y[yPos]);
            if (charComparison !== 0) return charComparison;
            xPos++;
            yPos++;
        }
    }

    // Handle remaining characters
    if (xPos < x.length) return 1;
    if (yPos < y.length) return -1;

    return 0;
}

function compareNumbers(
    x: string,
    xStart: number,
    y: string,
    yStart: number
): { result: number; xPos: number; yPos: number } {
    let xPos = xStart, yPos = yStart;

    // Find the end of the digit sequences
    while (xPos < x.length && isDigit(x[xPos])) xPos++;
    while (yPos < y.length && isDigit(y[yPos])) yPos++;

    // Extract number spans
    const xNumber = x.slice(xStart, xPos).replace(/^0+/, '');
    const yNumber = y.slice(yStart, yPos).replace(/^0+/, '');

    // Compare lengths first (natural sort behavior)
    if (xNumber.length !== yNumber.length) {
        return { result: xNumber.length - yNumber.length, xPos, yPos };
    }

    // Compare digit by digit
    const result = xNumber.localeCompare(yNumber);
    return { result, xPos, yPos };
}

function isDigit(char: string): boolean {
    return /\d/.test(char);
}

const items = ["file10.txt", "file2.txt", "file1.txt", "file20.txt", "file3.txt"];

console.log("Original list:");
console.log(items);

// Natural sort
const sorted = items.sort(compareStrings);

console.log("\nSorted list (Natural Sort):");
console.log(sorted);

// Reversed sort
const reverseSorted = items.sort((a, b) => compareStrings(b, a));

console.log("\nReverse sorted list:");
console.log(reverseSorted);