tgmayfield's Journal

Couldn't help myself. Here's a not-simple-enough solution to Jeff Atwood's call for C# natural sorting algorithms.

This code likely goes too far (but there's that ever-present issue of seeing a solution to a problem and not being able to stop oneself).

The strings are divided into tokens, separating the text and numeric portions into different items in the list. So, z003a0005 would evaluate as equal to Z3A5. String.ToLower() is used on all the text portions, which is naive for internationalization, but otherwise workable.

I've not done enough with Unicode to include it in the algorithm. Anything I did with it would probably be hopeless naive.

public class NaturalSortComparer
	: IComparer<string>
{
	#region Unit Tests
	[TestFixture]
	public class Tests
	{
		[RowTest]
		[Row("abc001", "abc1", 0)]
		[Row("abc1", "abc10", -1)] // abc1 < abc10
		[Row("z102", "z2", 1)] // z102 > z2
		[Row("z010", "z001", 1)] // z010 > z001
		[Row("z3000", "z30", 1)] // z3000 > z30
		[Row("z3a10", "z03a2", 1)] // z3a10 > z3a2
		[Row("z3a3foo", "z3a3bar", 1)] // z3a3foo > z3a3bar
		public void TestCompare(string value1, string value2, int expectedResult)
		{
			NaturalSortComparer c = new NaturalSortComparer();
			int result = c.Compare(value1, value2);
			Assert.AreEqual(expectedResult, result);
		}
	}
	#endregion // Unit Tests

	#region IComparer<string> Members
	public int Compare(string x, string y)
	{
		NaturallySortableString sortableX = new NaturallySortableString(x);
		NaturallySortableString sortableY = new NaturallySortableString(y);

		return sortableX.CompareTo(sortableY);
	}
	#endregion // IComparer<string> Members

	#region Sortable class
	private class NaturallySortableString
		: IComparable<NaturallySortableString>
	{
		public NaturallySortableString(string source)
		{
			Source = source;
			Tokens = new List<NaturallySortableToken>();

			string lower = source.ToLower();
			StringBuilder current = new StringBuilder();
			bool workingOnANumber = false;
			
			for (int cnt = 0; cnt < lower.Length; cnt++)
			{
				long value = -1;
				string c = lower.Substring(cnt, 1);

				if (long.TryParse(c, out value))
				{
					if (!workingOnANumber && current.Length > 0)
					{
						Tokens.Add(new NaturallySortableToken() { Text = current.ToString() });
						current = new StringBuilder();
					}

					current.Append(c);
					workingOnANumber = true;
				}
				else
				{
					if (workingOnANumber && current.Length > 0)
					{
						// Convert the entire number
						value = long.Parse(current.ToString());
						Tokens.Add(new NaturallySortableToken() { Number = value });
						current = new StringBuilder();
					}

					current.Append(c);
					workingOnANumber = false;
				}
			}

			// Last token
			if (current != null)
			{
				if (workingOnANumber)
				{
					long value = long.Parse(current.ToString());
					Tokens.Add(new NaturallySortableToken() { Number = value });
				}
				else
				{
					Tokens.Add(new NaturallySortableToken() { Text = current.ToString() });
				}
			}
		}

		public string Source { get; private set; }

		private List<NaturallySortableToken> Tokens { get; set; }

		#region Token
		private class NaturallySortableToken
			: IComparable<NaturallySortableToken>
		{
			public string Text { get; set; }
			public long Number { get; set; }

			public int CompareTo(NaturallySortableToken token)
			{
				// Bug here if one token is text and the other a number. But it _should_ sort the number first. Needs to be explicit.
				if (Text != token.Text)
				{
					return String.Compare(Text, token.Text);
				}

				return (Number > token.Number ? 1 : (Number == token.Number ? 0 : -1));
			}
		}
		#endregion // Token

		#region IComparable<NaturallySortableString> Members
		public int CompareTo(NaturallySortableString other)
		{
			int compareValue = 0;
			int index = 0;
			while (compareValue == 0 && index < Tokens.Count && index < other.Tokens.Count)
			{
				NaturallySortableToken mine = Tokens[index];
				NaturallySortableToken theirs = other.Tokens[index];
				compareValue = mine.CompareTo(theirs);
				index++;
			}
			return compareValue;
		}
		#endregion
	}
	#endregion // Sortable class
}