home *** CD-ROM | disk | FTP | other *** search
/ Nebula 1995 August / NEBULA.mdf / SourceCode / libcs / stabsearch.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-12-11  |  6.8 KB  |  201 lines
  1. /*
  2.  * Copyright (c) 1990 Carnegie Mellon University
  3.  * All Rights Reserved.
  4.  * 
  5.  * Permission to use, copy, modify and distribute this software and its
  6.  * documentation is hereby granted, provided that both the copyright
  7.  * notice and this permission notice appear in all copies of the
  8.  * software, derivative works or modified versions, and any portions
  9.  * thereof, and that both notices appear in supporting documentation.
  10.  *
  11.  * THE SOFTWARE IS PROVIDED "AS IS" AND CARNEGIE MELLON UNIVERSITY
  12.  * DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING ALL
  13.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS.  IN NO EVENT
  14.  * SHALL CARNEGIE MELLON UNIVERSITY BE LIABLE FOR ANY SPECIAL, DIRECT,
  15.  * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER
  16.  * RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF
  17.  * CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
  18.  * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  19.  *
  20.  * Users of this software agree to return to Carnegie Mellon any
  21.  * improvements or extensions that they make and grant Carnegie the
  22.  * rights to redistribute these changes.
  23.  *
  24.  * Export of this software is permitted only after complying with the
  25.  * regulations of the U.S. Deptartment of Commerce relating to the
  26.  * Export of Technical Data.
  27.  */
  28. /*  stabsearch --  search for best match within string table
  29.  *
  30.  *  int stabsearch (arg,table,quiet);
  31.  *  char *arg;
  32.  *  char **table;
  33.  *  int quiet;
  34.  *
  35.  *  Just like stablk(3), but a match score is determined for each
  36.  *  string in the table, and the best match is used.  If quiet=0,
  37.  *  the user will be asked if he really meant the best matching
  38.  *  string; if he says "no", a list of several other good matches
  39.  *  will be printed.
  40.  *  If there is exactly one perfect match, then its index will be
  41.  *  returned, and the user will not be asked anything.  If there are
  42.  *  several perfect matches, then up to 50 will be listed for the
  43.  *  user to review and among which he can select one.
  44.  *
  45.  * HISTORY
  46.  * $Log:    stabsearch.c,v $
  47.  * Revision 1.2  90/12/11  17:59:43  mja
  48.  *     Add copyright/disclaimer for distribution.
  49.  * 
  50.  * 28-Apr-85  Steven Shafer (sas) at Carnegie-Mellon University
  51.  *    Modified for 4.2 BSD.  Now puts output on std. error using fprintf
  52.  *    and fprstab.
  53.  *
  54.  * 13-Mar-85  Glenn Marcy (gm0w) at Carnegie-Mellon University
  55.  *    Return NOMATCH if arg is zero.
  56.  *
  57.  * 26-Oct-83  Leonard Hamey (lgh) at Carnegie-Mellon University
  58.  *    Included code to detect exact matches.
  59.  *
  60.  * 06-Feb-81  Steven Shafer (sas) at Carnegie-Mellon University
  61.  *    Fixed bug in previous bug fixes.
  62.  *
  63.  * 27-Jan-81  Steven Shafer (sas) at Carnegie-Mellon University
  64.  *    Added SCROLLSIZE, KEEPPERFECT, and associated code for better
  65.  *    handling of long string tables.
  66.  *
  67.  * 16-Apr-80  Steven Shafer (sas) at Carnegie-Mellon University
  68.  *    Changed option-printing code to use "prstab"; this will use
  69.  *    multiple columns where appropriate.
  70.  *
  71.  * 12-Mar-80  Steven Shafer (sas) at Carnegie-Mellon University
  72.  *    Added check for unique perfect match; will now return appropriate index
  73.  *    without asking "Did you mean X?".
  74.  *
  75.  * 23-Jan-80  Steven Shafer (sas) at Carnegie-Mellon University
  76.  *    Created.  Almost identical to Dave McKeown's matching routine from
  77.  *    the PDP-11, but the scores are normalized to lie in the range 0 to 100.
  78.  *
  79.  */
  80.  
  81. #include <stdio.h>
  82.  
  83. #define KEEPBEST 6        /* # of matches to keep around */
  84. #define KEEPPERFECT 50        /* # of perfect matches to keep */
  85. #define KEEPEXACT 50        /* # of exact matches to keep */
  86. #define PERFECT 100        /* perfect match score */
  87. #define EXACT 101        /* exact match pseudo-score */
  88. #define THRESHOLD 35        /* minimum acceptable score */
  89. #define NOMATCH -1        /* return value if no match */
  90. #define MAXLENGTH 400        /* max length of arg and table entries */
  91. #define SCROLLSIZE 20        /* size of each screenful for scrolling */
  92.  
  93. int srchscore();        /* score function */
  94.  
  95. int stabsearch (arg,table,quiet)
  96. char *arg,**table;
  97. int quiet;
  98. {
  99.     int bestentry[KEEPPERFECT], bestscore[KEEPPERFECT];
  100.     int arglen;
  101.     int maxscore;        /* best possible score */
  102.     register int i,j,k;    /* temps */
  103.     int nperfect;        /* # of perfect matches */
  104.     int nexact;         /* # of exact matches */
  105.     int nentries;        /* # of entries in table */
  106.     char line[MAXLENGTH];
  107.     char a[MAXLENGTH],e[MAXLENGTH];
  108.  
  109.     if (arg == 0)
  110.         return (NOMATCH);
  111.     if (strcmp (arg,"?") != 0) {
  112.  
  113.         for (i=0; i<KEEPPERFECT; i++) {
  114.             bestentry[i] = -1;
  115.             bestscore[i] = -1;
  116.         }
  117.         arglen = strlen (arg);
  118.         maxscore = arglen * arglen;
  119.         folddown (a,arg);
  120.  
  121.         nperfect = 0;
  122.         nexact = 0;
  123.         for (i=0; table[i]; i++) {
  124.             folddown (e,table[i]);
  125.             j = (srchscore (e,a) * PERFECT) / maxscore;
  126.             if (nperfect == 0 && nexact == 0 && j != PERFECT) {
  127.                 if (j >= bestscore[KEEPBEST-1]) {
  128.                     k = KEEPBEST - 1;
  129.                     while ((k > 0) && (j > bestscore[k-1])) {
  130.                         bestscore[k] = bestscore[k-1];
  131.                         bestentry[k] = bestentry[k-1];
  132.                         --k;
  133.                     }
  134.                     bestscore[k] = j;
  135.                     bestentry[k] = i;
  136.                 }
  137.             }
  138.             else if (j == PERFECT && arglen == strlen (e))
  139.             {    bestscore[0] = EXACT;
  140.                 if (nexact < KEEPEXACT)
  141.                     bestentry[nexact++] = i;
  142.             }
  143.             else if (j == PERFECT && nperfect < KEEPPERFECT && !nexact) {
  144.                 bestscore[0] = PERFECT;
  145.                 bestentry[nperfect] = i;
  146.                 nperfect++;
  147.             }
  148.         }
  149.         nentries = i;
  150.  
  151.         if (bestscore[0] <= THRESHOLD) {
  152.             if (!quiet) {
  153.                 fprintf (stderr,"Sorry, nothing matches \"%s\" reasonably.\n",arg);
  154.                 if (getbool("Do you want a list?",(nentries<=SCROLLSIZE))) goto makelist;
  155.             }
  156.             return (NOMATCH);
  157.         }
  158.  
  159.         if (quiet)  return (bestentry[0]);
  160.         if (nexact > 1)
  161.         {    fprintf (stderr,"There are %d exact matches for \"%s\":\n",nexact,arg);
  162.             j = getint ("Which one should be used?  (0 if none ok)",0,nexact,1);
  163.             return ((j > 0) ? bestentry[j-1] : NOMATCH);
  164.         }
  165.         else if (nexact == 1) return (bestentry[0]);
  166.  
  167.         if (nperfect > 1) {    /* multiple max matches */
  168.             fprintf (stderr,"There are %d perfect matches for \"%s\":\n",nperfect,arg);
  169.             for (j=0; j<nperfect && ((j%SCROLLSIZE!=SCROLLSIZE-1) || getbool("Continue?",1)); j++) {
  170.                 fprintf (stderr,"(%d)\t%s\n",j+1,table[bestentry[j]]);
  171.             }
  172.             j = getint ("Which one should be used?  (0 if none ok)",0,nperfect,1);
  173.             return ((j > 0) ? bestentry[j-1] : NOMATCH);
  174.         }
  175.         else if (nperfect == 1) {    /* unique perfect match */
  176.             return (bestentry[0]);
  177.         }
  178.  
  179.         sprintf (line,"Did you mean \"%s\" [%d] ?",
  180.             table[bestentry[0]],bestscore[0]);
  181.         if (getbool(line,1))  return (bestentry[0]);
  182.  
  183.         fprintf (stderr,"May I suggest the following?\n");
  184.         for (i=0; i<KEEPBEST && bestscore[i] >= THRESHOLD; i++) {
  185.             fprintf (stderr,"(%d)\t%-15s \t[%d]\n",i+1,table[bestentry[i]],bestscore[i]);
  186.         }
  187.         j = getint ("Which one should be used?  (0 if none ok)",0,i,1);
  188.         if (j>0)  return (bestentry[j-1]);
  189.         if (getbool("Do you want a list of all possibilities?",(nentries<=SCROLLSIZE)))  goto makelist;
  190.  
  191.     }
  192.     else {
  193. makelist:
  194.  
  195.         fprintf (stderr,"The choices are as follows:\n");
  196.         fprstab (stderr,table);
  197.     }
  198.  
  199.     return (NOMATCH);
  200. }
  201.