using System;
using System.Collections;
using System.Collections.Generic;
using System.Text.RegularExpressions;

namespace NaturalSort
{
    public class AlphanumComparer : IComparer, IComparer<string>
    {
        private const string ChunkExpression = @"\D+|\d+";
        private const string NumericMatchExpression = @"\d+";

        private static readonly Regex chunkRegex = new Regex(ChunkExpression, RegexOptions.Compiled);
        private static readonly Regex numericRegex = new Regex(NumericMatchExpression, RegexOptions.Compiled);

        public static int Compare(string s1, string s2)
        {
            List<string> s1Chunks = GetChunks(s1);
            List<string> s2Chunks = GetChunks(s2);

            if ((s1Chunks.Count == 0) && (s2Chunks.Count == 0))
            {
                return 0;
            }


            for (int chunkIndex = 0; chunkIndex < Math.Max(s1Chunks.Count, s2Chunks.Count); chunkIndex++)
            {
                if (chunkIndex >= s1Chunks.Count)
                {
                    return -1;
                }
                else if (chunkIndex >= s2Chunks.Count)
                {
                    return 1;
                }

                string chunk1 = s1Chunks[chunkIndex];
                string chunk2 = s2Chunks[chunkIndex];
                int compareValue = CompareChunks(chunk1, chunk2);
                if (compareValue != 0)
                {
                    return compareValue;
                }
            }

            return 0;
        }

        #region IComparer Methods

        int IComparer<string>.Compare(string s1, string s2)
        {
            return AlphanumComparer.Compare(s1, s2);
        }

        int IComparer.Compare(object s1, object s2)
        {
            return AlphanumComparer.Compare(s1 as string, s2 as string);
        }

        #endregion

        #region Private Methods

        private static int CompareChunks(string chunk1, string chunk2)
        {
            if (IsNumeric(chunk1) && IsNumeric(chunk2))
            {
                return int.Parse(chunk1) - int.Parse(chunk2);
            }
            return chunk1.CompareTo(chunk2);
        }

        private static List<string> GetChunks(string s)
        {
            Match match = chunkRegex.Match(s);
            List<string> results = new List<string>();
            while (match.Success)
            {
                results.Add(match.Value);
                match = match.NextMatch();
            }
            return results;
        }

        private static bool IsNumeric(string s)
        {
            return numericRegex.IsMatch(s);
        }

        #endregion
    }
}