comparison tools/strmatch.c @ 0:5242703e91d3 tip

Initial checkin for AIM92 aimR8.2 (last updated May 1997).

+/***************************************************************************
+
+strmatch.c      String matching routines to supplement those defined in
+----------      <strings.h>.
+
+
+Character classification macros defined in <ctype.h>
+These return truth values [0,1].
+
+
+     int isalpha(c)     c is a letter
+     int c;
+
+     int isupper(c)     c is an uppercase letter
+     int c;
+
+     int islower(c)     c is a lowercase letter
+     int c;
+
+     int isdigit(c)     c is a digit
+     int c;
+
+     int isxdigit(c)    c is a hexadecimal digit, by default [0-9], [A-F], or
+     int c;             [a-f].
+
+     int isalnum(c)     c is an alphanumeric character
+     int c;
+
+     int isspace(c)     c is a space, tab, carriage return, new line, or form
+     int c;             feed.
+
+     int ispunct(c)     c is a punctuation character (neither control,
+     int c;             alphanumeric, nor space)
+
+
+     int isprint(c)     c is a printing character, by default code 040(8)
+     int c;             (space) through 0176 (tilde)
+
+
+     int isgraph(c)     c is a printing character, like isprint except false
+     int c;             for space.
+
+     int iscntrl(c)     c is a delete character (0177) or ordinary control
+     int c;             character (less than 040) except for space characters
+
+
+     int isascii(c)     c is an ASCII character, code less than 0200
+     int c;
+
+
+Character translation macros defined in <ctype.h>
+
+
+     int toupper(c)     return upper-case letter corresponding to c.
+     int c;
+
+     int tolower(c)     return lower-case letter corresponding to c.
+     int c;
+
+     int toascii(c)     return ascii value corresponding to c.
+     int c;
+
+
+String handling routines defined in <strings.h>
+A `span' is the length of a segment of a string, ie a number of characters.
+
+
+     char *strcat(s1, s2)       Append a copy of string s2 to the end of
+     char *s1, *s2;             string s1. Return a ptr to s1.
+
+     char *strncat(s1, s2, n)   Append n chars of s2 to the end of string s1.
+     char *s1, *s2;             Return a ptr to s1.
+
+     int strcmp(s1, s2)         Compare strings. Return 0 if equal.
+     unsigned char *s1, *s2;    Otherwise return difference number of chars.
+
+     int strncmp(s1, s2, n)     Compare n chars of strings. Return 0 if equal.
+     unsigned char *s1, *s2;    Otherwise return difference number of chars.
+     int n
+
+     strcasecmp(s1, s2)         As strcmp, but case insensitive.
+     char *s1, *s2;
+
+     strncasecmp(s1, s2, n)     As strncmp, but case insensitive.
+     char *s1, *s2;
+
+     char *strcpy(s1, s2)       Copy s2 to s1, including null char.
+     char *s1, *s2;
+
+     char *strncpy(s1, s2, n)   Copy n chars of s2 to s1. Truncate or pad s2
+     char *s1, *s2;             with nulls to make up n chars. If s2 needs to
+     int n                      be truncated, s1 will not be null terminated.
+
+     int strlen(s)              Return number of chars in s, not including
+     char *s;                   the terminating null character.
+
+     char *strstr(s1, s2)       Return a ptr to the first occurrence of s2
+     char *s1, *s2;             in s1. Otherwise return a null ptr.
+
+     char *strchr(s, c)         Return a ptr to the first occurrence of c
+     char *s;                   in s. Otherwise return a null ptr.
+     int c;
+
+     char *strrchr(s, c)        Return a ptr to the last occurrence of c
+     char *s;                   in s. Otherwise return a null ptr.
+     int c;
+
+     char *strpbrk(s1, s2)      Return a ptr to the first occurrence of any
+     char *s1, *s2;             char in s2 in s1. Otherwise return a null ptr.
+
+     int strspn(s1, s2)         Return the span from the head of s1 which
+     char *s1, *s2;             consists of chars which are in s2.
+
+     int strcspn(s1, s2)        Return the span from the head of s1 which
+     char *s1, *s2;             consists of chars which are not in s2.
+
+     char *strtok(s1, s2)       See below:
+     char *s1, *s2;
+
+     The strtok	subroutine considers the string	s1 to consist of a sequence
+     of	zero or	more text tokens separated by spans of one or more characters
+     from the separator	string s2.  The	first call (with pointer s1 speci-
+     fied) returns a pointer to	the first character of the first token,	and
+     will have written a null character	into s1	immediately following the
+     returned token.  The function keeps track of its position in the string
+     between separate calls, so	that subsequent	calls (which must be made
+     with the first argument a NULL pointer) will work through the string s1
+     immediately following that	token.	In this	way, subsequent	calls will
+     work through the string s1	until no tokens	remain.	 The separator string
+     s2	may be different from call to call.  When no token remains in s1, a
+     NULL pointer is returned.
+
+
+***************************************************************************/
+
+
+
+#include <math.h>
+#include "strmatch.h"
+
+
+/*
+Test for a NULL pointer to a character or string
+*/
+
+int isnull( s )
+char *s ;
+{
+    if ( s == (char *)0 ) return 1 ;
+    else                  return 0 ;
+}
+
+/*
+Test for an empty string
+*/
+
+
+int isempty( s )
+char *s ;
+{
+    if ( *s == '\0' ) return 1 ;
+    else              return 0 ;
+}
+
+/*
+Test for NULL string pointer or empty string
+*/
+
+int isnullorempty( s )
+char *s ;
+{
+    if ( s == (char *)0 || *s == '\0' ) return 1 ;
+    else                                return 0 ;
+}
+
+
+/*
+Return a pointer to the terminator '\0' at the tail of string `s'.
+*/
+
+char *terminator( s )
+char *s ;
+{
+    return ( s + strlen( s ) ) ;
+}
+
+
+/*
+Test strings s1==s2. Return 1 if true, 0 otherwise.
+*/
+
+int isstr( s1, s2 )
+char *s1, *s2 ;
+{
+    return ( strcmp( s1, s2 ) == 0 ) ;
+}
+
+
+/*
+Test strings s1==s2 up to the length of string s1 (ie allowing truncation).
+Return 1 if true, 0 otherwise.
+*/
+
+int iststr( s1, s2 )
+char *s1, *s2 ;
+{
+    return ( strncmp( s1, s2, strlen( s1 ) ) == 0 ) ;
+}
+
+
+/*
+Copy s2 to s1 up to (but not including) the first occurrence of character c
+in s2. Ensure s1 is then null terminated.
+Return s1 or a null ptr if c is not found in s2.
+*/
+
+char *strccpy( s1, s2, c )
+char *s1, *s2 ;
+char  c ;
+{
+    char *s ;
+
+    if ( ( s = strchr( s2, c ) ) == (char *)0 ) return (char *)0 ;
+    strncpy( s1, s2, (int)( s - s2 ) ) ;
+    *( s1 +  ( s - s2 ) ) == '\0' ;
+    return ( s1 ) ;
+}
+
+
+/*
+Return a ptr to the first occurrence of any char in s1 which is not in s2.
+Otherwise return a null ptr. (This complements strpbrk() in the Unix string
+library).
+*/
+
+char *strcbrk(s1, s2)
+char *s1, *s2;
+{
+    int  spn ;
+
+    if ( ( spn = strspn( s1, s2 ) ) == strlen( s1 ) )
+	return ( (char *)0 ) ;
+    return ( (char *)( s1 + spn ) ) ;
+}
+
+
+
+/*
+Return the span from the head of s1 to the first occurrence of any char in s2.
+Otherwise (if no such char found) return -1.
+*/
+
+int strspnbrk(s1, s2)
+char *s1, *s2;
+{
+    int  spn ;
+
+    if ( ( spn = strcspn( s1, s2 ) ) == strlen( s1 ) )
+	return ( -1 ) ;
+    return ( spn ) ;
+}
+
+
+/*
+Return the span from the head of s1 to the first occurrence of any char not
+in s2. Otherwise (if no such char found) return -1.
+*/
+
+int strcspnbrk(s1, s2)
+char *s1, *s2;
+{
+    int  spn ;
+
+    if ( ( spn = strspn( s1, s2 ) ) == strlen( s1 ) )
+	return ( -1 ) ;
+    return ( spn ) ;
+}
+
+
+
+/*
+Compare the heads of strings s1 and s2 up to the length of string s1.
+Return 0 if equal, otherwise return difference number of chars.
+*/
+
+int strtcmp( s1, s2 )
+char *s1, *s2 ;
+{
+    return ( strncmp( s1, s2, strlen( s1 ) ) ) ;
+}
+
+
+/*
+Compare the tails of strings s1 and s2 back to the length of string s2.
+Return 0 if equal, otherwise return difference number of chars.
+*/
+
+int strtrcmp( s1, s2 )
+char *s1, *s2 ;
+{
+    int  i, j ;
+
+    if ( ( i = strlen( s1 ) ) >=  ( j = strlen( s2 ) ) )
+	return ( strcmp( s1+i-j, s2 ) ) ;
+    return ( i-j ) ;
+}
+
+
+/*
+Return the span (number of chars) over which the head of string s1 equals the
+head of string s2.
+*/
+
+int streqspn( s1, s2 )
+char *s1, *s2 ;
+{
+    int  spn=0 ;
+
+    while ( !isempty(s1) && *s1++ == *s2++ ) spn++ ;
+    return spn ;
+}
+
+
+/*
+Return the span (number of chars) of a <number> at the head of string s.
+   <number> = [-]<digits>[.]<digits>
+where either, but not both, of the digit strings may be empty.
+*/
+
+int strnumspn( s )
+char *s ;
+{
+    int j0=0, j1, j2 ;
+
+    if ( *s == '-' )  j0++ ;               /* span of '-'                   */
+    j1 = strspn( s+j0, "0123456789" ) ;    /* span of digits left  of point */
+    if ( *( s+j0+j1 ) == '.' ) j1++ ;      /* span of '.'                   */
+    j2 = strspn( s+j0+j1, "0123456789" ) ; /* span of digits right of point */
+    if ( *( s+j0+j1+j2 ) == '.' ) j2++ ;
+
+    if ( j1>0 || j2>0 )
+	return ( j0+j1+j2 ) ;
+    return 0 ;                             /* zero span means no number     */
+}
+
+
+/*
+Test for a <number>.
+*/
+
+int isnumber( s )
+char *s ;
+{
+    if ( strnumspn( s ) > 0 ) return 1 ;
+    else                      return 0 ;
+}
+
+
+/*
+Return a ptr to the first char after a <number> at the head of string s.
+*/
+
+char *strnumptr( s )
+char *s ;
+{
+    return ( s + strnumspn( s ) ) ;
+}
+
+
+/*
+Return a ptr to the first occurrence of any number char in s.
+(where a number char includes '-' and '.' as well as any digit).
+*/
+
+char *strpnum(s)
+char *s ;
+{
+    return ( strpbrk( s, "-.0123456789" ) ) ;
+}
+
+/*
+Return a ptr to the first occurrence of any char in s not a number char.
+(where a number char includes '-' and '.' as well as any digit).
+*/
+
+char *strcnum(s)
+char *s ;
+{
+    return ( strcbrk( s, "-.0123456789" ) ) ;
+}
+
+
+/*
+Separate string `s1' into two string tokens at the first occurrence of a
+separator character `s2'. (Given as a string of one char).
+Numbers at the head of `s1' are skipped. (This skips leading hyphens or points
+which are part of a number, and so allows negative numbers with splitting
+hyphens, real numbers with splitting decimal point, etc.).
+Four possible outcomes, depending upon form of `s1':
+1. Null or empty.           - return NULL ptr, (missing 1st and 2nd tokens).
+2. No separator char.       - return ptr to empty string, (empty 2nd token).
+3. Separator is last char.  - return NULL ptr, (missing 2nd token).
+4. Separator within `s1'.   - return ptr to 2nd token, (two correct tokens).
+String `s1' is unchanged at the end.
+*/
+
+char *strpsep( s1, s2 )
+char *s1, *s2 ;
+{
+    char *s ;
+
+    if ( isnullorempty( s1 ) )
+	return ( (char *)0 ) ;
+
+    s1 = strnumptr( s1 ) ;              /* skip leading numbers */
+
+    if ( ( s = strpbrk( s1, s2 ) ) == (char *)0 )
+	return ( s1 + strlen( s1 ) ) ;  /* ptr to empty string at end s1 */
+
+    if ( isempty( ( s2 = s+1 ) ) )
+	return ( (char *)0 ) ;          /* separator is last char */
+
+    return ( s2 ) ;
+}
+
+/* Replace above last 4 lines of routine, and also mod strsep, to get proper
+   string separator
+    if ( ( s2 = strcbrk( s, s2 ) ) == (char *)0 )
+	return ( (char *)0 ) ;
+    while ( --s2 > s && isnumber( s2 ) ) ;
+    return ( ++s2 ) ;
+*/
+
+/*
+Separate string `s1' into two string tokens.
+strsep() is the same as strpsep() except that, in the event of two correct
+tokens, insert '\0' at the separator.
+String `s1' is thus separated and becomes the first token.
+*/
+
+char *strsep( s1, s2 )
+char *s1, *s2 ;
+{
+    char *s = strpsep( s1, s2 ) ;       /* ptr to 2nd token */
+
+    if ( isnullorempty( s ) )
+	return s ;
+
+    *(s-1) = '\0' ;     /* insert '\0' and return 2nd token */
+    return ( s ) ;
+}
+
+
+/*
+Compare the head of string `s' with null-terminated list of strings `list'.
+Return the longest matching string from `list'.
+Return a NULL pointer if no match is found, or if the (possibly abbreviated)
+head of string `s' is ambiguous (ie. matches more than once in the list).
+*/
+
+char *listcmp( list, s )
+char **list ;
+char  *s  ;
+{
+    int  i, j = (-1) ;
+
+    for ( i=0; list[i] != (char *)0 ; i++)
+	if ( strtcmp( s, list[i] ) == 0 ) {
+	    if ( j >= 0 ) return (char *)0 ;    /* ambiguous match */
+	    else j = i;
+	}
+    if ( j < 0 ) return (char *)0 ;             /* match not found */
+    return ( list[j] ) ;
+}
+
+
+/*
+Compare the tail of string `s' with null-terminated list of strings `list'.
+Return the longest matching string from `list'.
+Return a NULL pointer if no match is found, or if the (possibly abbreviated)
+tail of string `s' is ambiguous (ie. matches more than once in the list).
+*/
+
+char *listrcmp( list, s )
+char **list ;
+char  *s ;
+{
+    int  i, j = (-1), k, maxlen = 0 ;
+
+    for ( i=0; list[i] != (char *)0 ; i++)
+	if ( strtrcmp( s, list[i] ) == 0 && ( k = strlen( list[i] ) ) > maxlen ) {
+	    maxlen = k ;
+	    j      = i ;
+	}
+    if ( j < 0 ) return (char *)0 ;             /* match not found */
+    return ( list[j] ) ;
+}
+
+
+/*
+Compare the head of string `s' with null-terminated list of strings `list'.
+Find the string in `list' having the longest matching span with the head of
+`s' (which is possibly abbreviated).
+Return the list index of the matching string.
+Return (-1) if there is no match in the list (all spans are zero).
+Return (-2) if the longest matching span is ambiguous (ie occurs more
+than once in the list).
+*/
+
+int listindex( list, s )
+char   **list ;
+char    *s    ;
+{
+    int  i, j, jmax = 0, index = (-1) ;
+
+    for ( i=0; list[i] != (char *)0 ; i++) {
+	if ( ( j = streqspn( s, list[i] ) ) > jmax ) {
+	    jmax   = j ;
+	    index  = i ;
+	}
+	else if ( j > 0 && j == jmax )
+		index = (-2) ;
+    }
+    return index ;
+}
+
+
+/*
+Return the length of the null-terminated list of strings `list', ie. the
+number of strings it contains.
+*/
+
+listsize( list )
+char **list ;
+{
+    int  i ;
+
+    for ( i = 0 ; list[i] != (char *)0 ; i++ )
+	;
+    return i ;
+}
+
+
+/*
+For each string in list1, find the index of the matching string in list2
+and store it in the index array, (which must be at least the size of list1).
+The string match allows for abbreviations in the list1 strings.
+Return the number of matching strings found. (If this is less than the size
+of list1 then list1 contains an unknown or an ambiguous string).
+*/
+
+mapindices( list1, list2, index )
+char **list1, **list2 ;
+int   *index ;
+{
+    int  i, j, n = 0 ;
+
+    for ( i = 0 ; list1[i] != (char *)0 ; i++ )
+	if ( ( j = listindex( list2, list1[i] ) ) >= 0 )
+	    index[n++] = j ;
+
+    return n ;
+}
+
+
+/*
+Split the given string `str' into tokens at occurrences of separator char c.
+Store pointers to each token in `list', and null-terminate each token
+by overwriting the separator char with null.
+The list must contain at most n pointers.
+Return the number of tokens, or 0 if an error.
+*/
+
+tokens( str, list, n, c )
+char  *str  ;
+char **list ;
+int    n    ;
+char   c    ;
+{
+    int   i ;
+    char *s ;
+
+    if ( isempty( str ) || *str == c || n <= 0 )  return 0 ;
+    list[0] = str ;
+
+    for ( i = 1 ; i < n && ( s = strchr( str, c ) ) != (char *)0 ; i++ ) {
+	*s = '\0' ;
+	str = s + 1 ;
+	if ( isempty( str ) || *str == c )  return 0 ;
+	list[i] = str ;
+    }
+
+    if ( i == n && strchr( str, c ) != (char *)0 ) return 0 ;
+
+    return i ;
+}
+
+
+
+/*
+Return ASCII string of integer i. (Inverse of atoi()).
+*/
+
+char *itoa( i )
+int  i ;
+{
+    char s[64], *s1 ;
+
+    sprintf( s, "%d", i ) ;
+    s1 = (char *)malloc( strlen( s ) + 1 ) ;
+    strcpy( s1, s ) ;
+    return s1 ;
+}