• FoxyBrown (71/71) Jun 30 2017 Spent the last hour trying to get a natural sort. Ended up having

FoxyBrown <Foxy Brown.IPT> writes:

Spent the last hour trying to get a natural sort. Ended up having 
to create my own(not sure if it's 100% correct though but works 
in practice). The Rosetta one is not correct.

Here is my implementation, anyone care to perfect it?

// Compares the strings a and b numerically, e.g., "04038284" and 
"000002"  returns 1, the first is larger.
int compareStringNum(string a, string b)
{
	// Remove leading 0's
	a = a.stripLeft('0');
	b = b.stripLeft('0');
	if (a.length > b.length) return 1;
	if (a.length < b.length) return -1;
	auto m = a.length;
	for(int i = 0; i < m; i++)
	{
		auto qqx = a[i];
		auto qqy = b[i];
		// Assume ascii comparision holds, i.e., '0' < '1' < ... < '9'
		if (a[i] > b[i]) return 1;
		if (a[i] < b[i]) return -1;
	}

	return 0;
}

string[] naturalSort(string[] arr) /*pure  safe*/
{
	alias myComp = (x, y) {
		auto ml = min(x.length, y.length)-1;
		auto ofsx = -1; auto ofsy = -1;
		auto numx_found = -1;
		auto numy_found = -1;
		for(int i = 0; i < ml; i++)
		{
			ofsx++;
			ofsy++;

			// If we have not found any numbers(that are not the same) and 
we have a difference, the strings must be different, fall back on 
standard character comparer
			if (!isDigit(x[ofsx]) && !isDigit(y[ofsy]) && x[ofsx] != 
y[ofsy] && numx_found < 0 && numy_found < 0)
				return x[ofsx] > y[ofsy];

			// We are at a position in the string where either we are at 
the end of a digit sequence or the characters have been identical 
up to this point
			if (isDigit(x[ofsx]) && numx_found < 0) numx_found = ofsx;
			if (isDigit(y[ofsy]) && numy_found < 0) numy_found = ofsy;
		
			if (!isDigit(x[ofsx]) && !isDigit(y[ofsy]) && numx_found >= 0 
&& numy_found >= 0)
			{
				auto numx = x[numx_found..ofsx];
				auto numy = y[numy_found..ofsy];
				auto res = compareStringNum(numx, numy);		
				if (res != 0) return (res != 1);
			}

			if (!isDigit(x[ofsx]) && !isDigit(y[ofsy]))
			{
				numx_found = -1;
				numy_found = -1;
			} else
			{
				if (!isDigit(x[ofsx]) && numx_found >= 0) ofsx--;
				if (!isDigit(y[ofsy]) && numy_found >= 0) ofsy--;
			}

			
		}

		return x > y;
	};

	auto x = arr.sort!(myComp).release;
	return x;
}