home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / vol_200 / 290_01 / ecs.c < prev    next >
Text File  |  1990-05-14  |  6KB  |  207 lines
  1. /* ecs - equivalence class routines */
  2.  
  3. /*
  4.  * Copyright (c) 1987, the University of California
  5.  * 
  6.  * The United States Government has rights in this work pursuant to
  7.  * contract no. DE-AC03-76SF00098 between the United States Department of
  8.  * Energy and the University of California.
  9.  * 
  10.  * This program may be redistributed.  Enhancements and derivative works
  11.  * may be created provided the new works, if made available to the general
  12.  * public, are made available for use by anyone.
  13.  */
  14.  
  15. #include "flexdef.h"
  16. #include "ecs.h"
  17.  
  18. /* ccl2ecl - convert character classes to set of equivalence classes
  19.  *
  20.  * synopsis
  21.  *    ccl2ecl();
  22.  */
  23.  
  24. void ccl2ecl()
  25.  
  26. {
  27.     int i, ich, newlen, cclp, ccls, cclmec;
  28.  
  29.     for ( i = 1; i <= lastccl; ++i )
  30.     {
  31.         /* we loop through each character class, and for each character
  32.          * in the class, add the character's equivalence class to the
  33.          * new "character" class we are creating.  Thus when we are all
  34.          * done, character classes will really consist of collections
  35.          * of equivalence classes
  36.          */
  37.  
  38.         newlen = 0;
  39.         cclp = cclmap[i];
  40.  
  41.         for ( ccls = 0; ccls < ccllen[i]; ++ccls )
  42.         {
  43.             ich = ccltbl[cclp + ccls];
  44.             cclmec = ecgroup[ich];
  45.             if ( cclmec > 0 )
  46.             {
  47.                 ccltbl[cclp + newlen] = (char) cclmec;
  48.                 ++newlen;
  49.             }
  50.         }
  51.  
  52.         ccllen[i] = newlen;
  53.     }
  54. }
  55.  
  56.  
  57. /* cre8ecs - associate equivalence class numbers with class members
  58.  *
  59.  * synopsis
  60.  *    int cre8ecs();
  61.  *    number of classes = cre8ecs( fwd, bck, num );
  62.  *
  63.  *  fwd is the forward linked-list of equivalence class members.  bck
  64.  *  is the backward linked-list, and num is the number of class members.
  65.  *  Returned is the number of classes.
  66.  */
  67.  
  68. int cre8ecs( fwd, bck, num )
  69. int fwd[], bck[], num;
  70.  
  71. {
  72.     int i, j, numcl;
  73.  
  74.     numcl = 0;
  75.  
  76.     /* create equivalence class numbers.  From now on, abs( bck(x) )
  77.      * is the equivalence class number for object x.  If bck(x)
  78.      * is positive, then x is the representative of its equivalence
  79.      * class.
  80.      */
  81.  
  82.     for ( i = 1; i <= num; ++i )
  83.         if ( bck[i] == NIL )
  84.         {
  85.             bck[i] = ++numcl;
  86.             for ( j = fwd[i]; j != NIL; j = fwd[j] )
  87.                 bck[j] = -numcl;
  88.         }
  89.  
  90.     return ( numcl );
  91. }
  92.  
  93.  
  94. #define PROCFLG 0x80
  95.  
  96. /* mkeccl - update equivalence classes based on character class xtions
  97.  *
  98.  * synopsis
  99.  *    char ccls[];
  100.  *    int lenccl, fwd[llsiz], bck[llsiz], llsiz;
  101.  *    mkeccl( ccls, lenccl, fwd, bck, llsiz );
  102.  *
  103.  * where ccls contains the elements of the character class, lenccl is the
  104.  * number of elements in the ccl, fwd is the forward link-list of equivalent
  105.  * characters, bck is the backward link-list, and llsiz size of the link-list
  106.  */
  107.  
  108. void mkeccl( ccls, lenccl, fwd, bck, llsiz )
  109. char ccls[];
  110. int lenccl, fwd[], bck[], llsiz;
  111.  
  112. {
  113.     int cclp, oldec, newec;
  114.     int cclm, i, j;
  115.  
  116.     /* note that it doesn't matter whether or not the character class is
  117.      * negated.  The same results will be obtained in either case.
  118.      */
  119.  
  120.     cclp = 0;
  121.  
  122.     while ( cclp < lenccl )
  123.     {
  124.         cclm = ccls[cclp];
  125.         oldec = bck[cclm];
  126.         newec = cclm;
  127.  
  128.         j = cclp + 1;
  129.  
  130.         for ( i = fwd[cclm]; i != NIL && i <= llsiz; i = fwd[i] )
  131.         { /* look for the symbol in the character class */
  132.             for ( ; (j < lenccl) && (ccls[j] <= (unsigned char) i || (ccls[j] & PROCFLG));
  133.               ++j )
  134.                 if ( ccls[j] == (unsigned char) i )
  135.                 {
  136.                     /* we found an old companion of cclm in the ccl.
  137.                      * link it into the new equivalence class and flag it as
  138.                      * having been processed
  139.                      */
  140.  
  141.                     bck[i] = newec;
  142.                     fwd[newec] = i;
  143.                     newec = i;
  144.                     ccls[j] |= PROCFLG; /* set flag so we don't reprocess */
  145.  
  146.                     /* get next equivalence class member */
  147.                     /* next 2 */ goto next_pt;
  148.                 }
  149.  
  150.             /* symbol isn't in character class.  Put it in the old equivalence
  151.              * class
  152.              */
  153.  
  154.             bck[i] = oldec;
  155.  
  156.             if ( oldec != NIL )
  157.                 fwd[oldec] = i;
  158.  
  159.             oldec = i;
  160. next_pt:
  161.             ;
  162.         }
  163.  
  164.         if ( bck[cclm] != NIL || oldec != bck[cclm] )
  165.         {
  166.             bck[cclm] = NIL;
  167.             fwd[oldec] = NIL;
  168.         }
  169.  
  170.         fwd[newec] = NIL;
  171.  
  172.         /* find next ccl member to process */
  173.  
  174.         for ( ++cclp; (ccls[cclp] & PROCFLG) && cclp < lenccl; ++cclp )
  175.         {
  176.             /* reset "doesn't need processing" flag */
  177.             ccls[cclp] &= ~PROCFLG;
  178.         }
  179.     }
  180. }
  181.  
  182.  
  183. /* mkechar - create equivalence class for single character
  184.  *
  185.  * synopsis
  186.  *    int tch, fwd[], bck[];
  187.  *    mkechar( tch, fwd, bck );
  188.  */
  189.  
  190. void mkechar( tch, fwd, bck )
  191. int tch, fwd[], bck[];
  192.  
  193. {
  194.     /* if until now the character has been a proper subset of
  195.      * an equivalence class, break it away to create a new ec
  196.      */
  197.  
  198.     if ( fwd[tch] != NIL )
  199.         bck[fwd[tch]] = bck[tch];
  200.  
  201.     if ( bck[tch] != NIL )
  202.         fwd[bck[tch]] = fwd[tch];
  203.  
  204.     fwd[tch] = NIL;
  205.     bck[tch] = NIL;
  206. }
  207.