Index: glib/gunicollate.c
===================================================================
RCS file: /cvs/gnome/glib/glib/gunicollate.c,v
retrieving revision 1.16
diff -u -p -r1.16 gunicollate.c
--- glib/gunicollate.c	14 Mar 2005 04:26:57 -0000	1.16
+++ glib/gunicollate.c	27 May 2005 16:06:17 -0000
@@ -1,6 +1,6 @@
 /* gunicollate.c - Collation
  *
- *  Copyright 2001 Red Hat, Inc.
+ *  Copyright 2001,2005 Red Hat, Inc.
  *
  * The Gnome Library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Lesser General Public License as
@@ -164,7 +164,8 @@ utf8_encode (char *buf, wchar_t val)
  * @len: length of @str, in bytes, or -1 if @str is nul-terminated.
  *
  * Converts a string into a collation key that can be compared
- * with other collation keys using strcmp(). 
+ * with other collation keys produced by the same function using 
+ * strcmp(). 
  * The results of comparing the collation keys of two strings 
  * with strcmp() will always be the same as 
  * comparing the two original keys with g_utf8_collate().
@@ -261,6 +262,196 @@ g_utf8_collate_key (const gchar *str,
 
   return result;
 }
+
+/* This is a collation key that is very very likely to sort before any
+   collation key that libc strxfrm generates. We use this before any
+   special case (dot or number) to make sure that its sorted before
+   anything else.
+ */
+#define COLLATION_SENTINEL "\1\1\1"
+
+/**
+ * g_utf8_collate_key_for_filename:
+ * @str: a UTF-8 encoded string.
+ * @len: length of @str, in bytes, or -1 if @str is nul-terminated.
+ *
+ * Converts a string into a collation key that can be compared
+ * with other collation keys produced by the same function using strcmp(). 
+ * 
+ * In order to sort filenames correctly, this function treats the dot '.' 
+ * as a special case. Most dictionary orderings seem to consider it
+ * insignificant, thus producing the ordering "event.c" "eventgenerator.c"
+ * "event.h" instead of "event.c" "event.h" "eventgenerator.c". Also, we
+ * would like to treat numbers intelligently so that "file1" "file10" "file5"
+ * is sorted as "file1" "file5" "file10".
+ */
+gchar*
+g_utf8_collate_key_for_filename (const gchar *str,
+				 gssize       len)
+{
+  GString *result;
+  GString *append;
+  const gchar *p;
+  const gchar *prev;
+  gchar *collate_key;
+  gint digits;
+  gint leading_zeros;
+
+  /*
+   * How it works:
+   *
+   * Split the filename into collatable substrings which do
+   * not contain [.0-9] and special-cased substrings. The collatable 
+   * substrings are run through the normal g_utf8_collate_key and the 
+   * resulting keys are concatenated with keys generated from the 
+   * special-cased substrings.
+   *
+   * Special cases: Dots are handled by replacing them with '\1' which 
+   * implies that short dot-delimited substrings are before long ones, 
+   * e.g.
+   * 
+   *   a\1a   (a.a)
+   *   a-\1a  (a-.a)
+   *   aa\1a  (aa.a)
+   * 
+   * Numbers are handled by prepending to each number d-1 superdigits 
+   * where d = number of digits in the number and SUPERDIGIT is a 
+   * character with an integer value higher than any digit (for instance 
+   * ':'). This ensures that single-digit numbers are sorted before 
+   * double-digit numbers which in turn are sorted separately from 
+   * triple-digit numbers, etc. To avoid strange side-effects when 
+   * sorting strings that already contain SUPERDIGITs, a '\2'
+   * is also prepended, like this
+   *
+   *   file\21      (file1)
+   *   file\25      (file5)
+   *   file\2:10    (file10)
+   *   file\2:26    (file26)
+   *   file\2::100  (file100)
+   *   file:foo     (file:foo)
+   * 
+   * This has the side-effect of sorting numbers before everything else (except
+   * dots), but this is probably OK.
+   *
+   * Leading digits are ignored when doing the above. To discriminate
+   * numbers which differ only in the number of leading digits, we append
+   * the number of leading digits as a byte at the very end of the collation
+   * key.
+   *
+   * To try avoid conflict with any collation key sequence generated by libc we
+   * start each switch to a special cased part with a sentinel that hopefully
+   * will sort before anything libc will generate.
+   */
+
+  if (len < 0)
+    len = strlen (str);
+
+  result = g_string_sized_new (len * 2);
+  append = g_string_sized_new (0);
+
+  /* No need to use utf8 functions, since we're only looking for ascii chars */
+  for (prev = p = str; *p != '\0'; p++)
+    {
+      switch (*p)
+	{
+	case '.':
+	  if (prev != p) 
+	    {
+	      collate_key = g_utf8_collate_key (prev, p - prev);
+	      g_string_append (result, collate_key);
+	      g_free (collate_key);
+	    }
+	  
+	  g_string_append (result, COLLATION_SENTINEL "\1");
+	  
+	  /* skip the dot */
+	  prev = p + 1;
+	  break;
+	  
+	case '0':
+	case '1':
+	case '2':
+	case '3':
+	case '4':
+	case '5':
+	case '6':
+	case '7':
+	case '8':
+	case '9':
+	  if (prev != p) 
+	    {
+	      collate_key = g_utf8_collate_key (prev, p - prev);
+	      g_string_append (result, collate_key);
+	      g_free (collate_key);
+	    }
+	  
+	  g_string_append (result, COLLATION_SENTINEL "\2");
+	  
+	  prev = p;
+	  
+	  /* write d-1 colons */
+	  if (*p == '0')
+	    {
+	      leading_zeros = 1;
+	      digits = 0;
+	    }
+	  else
+	    {
+	      leading_zeros = 0;
+	      digits = 1;
+	    }
+	  
+	  do
+	    {
+	      p++;
+	      
+	      if (*p == '0' && !digits)
+		++leading_zeros;
+	      else if (g_ascii_isdigit(*p))
+		++digits;
+	      else
+		break;
+	    }
+	  while (*p != '\0');
+
+	  while (digits > 1)
+	    {
+	      g_string_append_c (result, ':');
+	      --digits;
+	    }
+
+	  if (leading_zeros > 0)
+	    {
+	      g_string_append_c (append, (char)leading_zeros);
+	      prev += leading_zeros;
+	    }
+	  
+	  /* write the number itself */
+	  g_string_append_len (result, prev, p - prev);
+	  
+	  prev = p;
+	  --p;	  /* go one step back to avoid disturbing outer loop */
+	  break;
+	  
+	default:
+	  /* other characters just accumulate */
+	  break;
+	}
+    }
+  
+  if (prev != p) 
+    {
+      collate_key = g_utf8_collate_key (prev, p - prev);
+      g_string_append (result, collate_key);
+      g_free (collate_key);
+    }
+  
+  g_string_append (result, append->str);
+  g_string_free (append, TRUE);
+
+  return g_string_free (result, FALSE);
+}
+
 
 #define __G_UNICOLLATE_C__
 #include "galiasdef.c"
