diff options
author | Andrei Zmievski <andrei@php.net> | 2000-04-29 18:57:06 +0000 |
---|---|---|
committer | Andrei Zmievski <andrei@php.net> | 2000-04-29 18:57:06 +0000 |
commit | 9e9ba7d974333171ecaa57e2c92b0e0ee0dc0b2a (patch) | |
tree | 17f17635157b5b9ddd45db9ef734bae7f07a2e1d /ext/standard/strnatcmp.c | |
parent | 1a8683f976e2c44d4aacc316b0a9ba3bdf0e5d22 (diff) | |
download | php-git-9e9ba7d974333171ecaa57e2c92b0e0ee0dc0b2a.tar.gz |
@ 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.
Diffstat (limited to 'ext/standard/strnatcmp.c')
-rw-r--r-- | ext/standard/strnatcmp.c | 134 |
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; } } |