Re: Naive implementation of strverscmp(3)

[Ulrich Spoerlein]

Dan Nelson wrote:

This looks a lot like strnatcmp, which is "natural sort" or "do what I
mean" sort :)

http://sourcefrog.net/projects/natsort/

Heh, I didn't know about that one, but since gqview uses strverscmp I only google for that one.

Your function is simpler than the C implementation on that site, but
falls over when a run of numbers exceeds 2^31 (raise it to 2^64 if you
use strtoull, but that's as high as you can yet).

You may do with the code whatever you want. :)

Ulrich Spoerlein
--
 PGP Key ID: 20FEE9DD                           Encrypted mail welcome!
Fingerprint: AEC9 AF5E 01AC 4EE1 8F70  6CBD E76E 2227 20FE E9DD
Which is worse: ignorance or apathy?
Don't know. Don't care.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#ifdef __FreeBSD__
int
strverscmp(const char *s1, const char *s2);

int
strverscmp(const char *s1, const char *s2)
{
  static const char *digits = "0123456789";
  char *t1, *t2;
  int ret;
  long n1, n2;
  size_t p1, p2;

  p1 = strcspn(s1, digits);
  p2 = strcspn(s2, digits);
  while (p1 == p2 && s1[p1] != '\0' && s2[p2] != '\0') {
    /* Different prefix */
    if ((ret = strncmp(s1, s2, p1)) != 0)
      return ret;

    s1 += p1;
    s2 += p2;
    n1 = strtol(s1, &t1, 10);
    n2 = strtol(s2, &t2, 10);
    
    if (n1 < n2)
      return -1;
    else if (n1 > n2)
      return 1;

    /* One number is "shorter", e.g., "07" vs "007" */
    if (t1-s1 < t2-s2)
      return 1;
    else if (t1-s1 > t2-s2)
      return -1;

    /* Numbers are equal or not present, try with next ones. */
    s1 = t1;
    s2 = t2;
    p1 = strcspn(s1, digits);
    p2 = strcspn(s2, digits);
  }
  
  return strcmp(s1, s2);
}
#endif

int
main(int argc, char **argv)
{
  char **array, *temp;
  int i, j, n = 10;

  array = (char **) calloc(n, sizeof(char *));
  array[0] = strdup("10.jpg");
  array[1] = strdup("2.jpg");
  array[2] = strdup("1.jpg");
  array[3] = strdup("09.jpg");
  array[4] = strdup("a01b2");
  array[5] = strdup("a1b1");
  array[6] = strdup("a");
  array[7] = strdup("1.001");
  array[8] = strdup("1.1");
  array[9] = strdup("1.01");

  /* Bubble sort */
  for (i=0; i<n; ++i) {
    for (j=i; j<n; ++j) {
      if (strverscmp(array[i], array[j]) > 0) {
        temp = array[j];
        array[j] = array[i];
        array[i] = temp;
      }
    }
  }

  for (i=0; i<n; ++i) {
    printf("%s\n", array[i]);
  }

  printf("%d = 0\n", strverscmp("a", "a"));
  printf("%d < 0\n", strverscmp("item#99", "item#100"));
  printf("%d > 0\n", strverscmp("alpha1", "alpha001"));
  printf("%d > 0\n", strverscmp("part1_f012", "part1_f01"));
  printf("%d < 0\n", strverscmp("foo.009", "foo.0"));

  return 0;
}

That's true, I didn't think of that. It's funny how a simple function like comparing alphanumerical strings can cause that much trouble. Anyway, attached is a last version, which now also functions for strings starting with numbers and which I'll probably try getting committed to the gqview port.

pgpGCPqSlIXkY.pgp
Description: PGP signature