@ Updated natural comparison/sorting algorithm by Martin Pool

@ <mbp@humbug.org.au>. (Andrei)

Martin Pool updated the natural comparison/sort algorithm so that fractions
compare more "naturally", e.g. 1.002 < 1.1.

1 files changed, 83 insertions, 51 deletions

diff --git a/ext/standard/strnatcmp.c b/ext/standard/strnatcmp.c
index 2629f29c1b..42c26ce1cd 100644
--- a/ext/standard/strnatcmp.c
+++ b/ext/standard/strnatcmp.c
@@ -39,68 +39,100 @@
 static char const *version UNUSED =
     "$Id$";
 
+static int
+compare_right(char const **a, char const *aend, char const **b, char const *bend)
+{
+	int bias = 0;
+
+	/* The longest run of digits wins.  That aside, the greatest
+	   value wins, but we can't know that it will until we've scanned
+	   both numbers to know that they have the same magnitude, so we
+	   remember it in BIAS. */
+	for(;; (*a)++, (*b)++) {
+		if ((*a == aend || !isdigit((int)**a)) &&
+			(*b == bend || !isdigit((int)**b)))
+			return bias;
+		else if (*a == aend || !isdigit((int)**a))
+			return -1;
+		else if (*b == bend || !isdigit((int)**b))
+			return +1;
+		else if (**a < **b) {
+			if (!bias)
+				bias = -1;
+		} else if (**a > **b) {
+			if (!bias)
+				bias = +1;
+		}
+     }
+
+     return 0;
+}
+
+
+static int
+compare_left(char const **a, char const *aend, char const **b, char const *bend)
+{
+     /* Compare two left-aligned numbers: the first to have a
+        different value wins. */
+	for(;; (*a)++, (*b)++) {
+		if ((*a == aend || !isdigit((int)**a)) &&
+			(*b == bend || !isdigit((int)**b)))
+			return 0;
+		else if (*a == aend || !isdigit((int)**a))
+			return -1;
+		else if (*b == bend || !isdigit((int)**b))
+			return +1;
+		 else if (**a < **b)
+			 return -1;
+		 else if (**a > **b)
+			 return +1;
+     }
+	  
+     return 0;
+}
+
+
 PHPAPI int strnatcmp_ex(char const *a, size_t a_len, char const *b, size_t b_len, int fold_case)
 {
-	int ai, bi;
 	char ca, cb;
-	const char *aend = a + a_len,
+	char const *ap, *bp;
+	char const *aend = a + a_len,
 			   *bend = b + b_len;
+	int fractional, result;
 
 	if (a_len == 0 || b_len == 0)
 		return a_len - b_len;
 
-/*
-	assert(a && b);
-*/
-
-	ai = bi = 0;
+	ap = a;
+	bp = b;
 	while (1) {
-		ca = a[ai]; cb = b[bi];
+		ca = *ap; cb = *bp;
 
 		/* skip over leading spaces or zeros */
-		while (isspace(ca)  ||  ca == '0')
-			ca = a[++ai];
+		while (isspace((int)ca))
+			ca = *++ap;
 
-		while (isspace(cb)  ||  cb == '0')
-			cb = b[++bi];
+		while (isspace((int)cb))
+			cb = *++bp;
 
 		/* process run of digits */
-		if (isdigit(ca)  &&  isdigit(cb)) {
-			int bias = 0;
-			/* The longest run of digits (stripping off leading
-			   zeros) wins.  That aside, the greatest value wins,
-			   but we can't know that it will until we've scanned
-			   both numbers to know that they have the same
-			   magnitude, so we remember it in BIAS. */
-			while (1) {
-				if (!isdigit(ca)  &&  !isdigit(cb))
-					goto done_number;
-				else if (!isdigit(ca))
-					return -1;
-				else if (!isdigit(cb))
-					return +1;
-				else if (ca < cb) {
-					if (!bias)
-						bias = -1;
-				} else if (ca > cb) {
-					if (!bias)
-						bias = +1;
-				}
-
-				++ai; ++bi;
-				if (a + ai == aend && b + bi == bend)
-					/* Return the current bias if at the end of both strings. */
-					return bias;
-				else if (a + ai == aend)
-					return -1;
-				else if (b + bi == bend)
-					return 1;
-
-				ca = a[ai]; cb = b[bi];
+		if (isdigit((int)ca)  &&  isdigit((int)cb)) {
+			fractional = (ca == '0' || cb == '0');
+
+			if (fractional)
+				result = compare_left(&ap, aend, &bp, bend);
+			else
+				result = compare_right(&ap, aend, &bp, bend);
+
+			if (result != 0)
+				return result;
+			else if (ap == aend && bp == bend)
+				/* End of the strings. Let caller sort them out. */
+				return 0;
+			else {
+				/* Keep on comparing from the current point. */
+				ca = *ap; cb = *bp;
 			}
-done_number:
-			if (bias)
-				return bias;
 		}
 
 		if (fold_case) {
@@ -113,14 +145,14 @@ done_number:
 		else if (ca > cb)
 			return +1;
 
-		++ai; ++bi;
-		if (a + ai == aend && b + bi == bend)
+		++ap; ++bp;
+		if (ap == aend && bp == bend)
 			/* The strings compare the same.  Perhaps the caller
 			   will want to call strcmp to break the tie. */
 			return 0;
-		else if (a + ai == aend)
+		else if (ap == aend)
 			return -1;
-		else if (b + bi == bend)
+		else if (bp == bend)
 			return 1;
 	}
 }