home *** CD-ROM | disk | FTP | other *** search
/ Java Programmer's Toolkit / Java Programmer's Toolkit.iso / hotjava3 / hotjava3.exe / hotjava / classsrc / java / util / RegexpPool.java < prev    next >
Encoding:
Java Source  |  1995-08-11  |  6.4 KB  |  225 lines
  1. /*
  2.  * @(#)RegexpPool.java    1.2 95/04/03
  3.  * 
  4.  * Copyright (c) 1995 Sun Microsystems, Inc.  All Rights reserved Permission to
  5.  * use, copy, modify, and distribute this software and its documentation for
  6.  * NON-COMMERCIAL purposes and without fee is hereby granted provided that
  7.  * this copyright notice appears in all copies. Please refer to the file
  8.  * copyright.html for further important copyright and licensing information.
  9.  * 
  10.  * SUN MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF THE
  11.  * SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE
  12.  * IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE,
  13.  * OR NON-INFRINGEMENT. SUN SHALL NOT BE LIABLE FOR ANY DAMAGES SUFFERED BY
  14.  * LICENSEE AS A RESULT OF USING, MODIFYING OR DISTRIBUTING THIS SOFTWARE OR
  15.  * ITS DERIVATIVES.
  16.  */
  17.  
  18. package java.util;
  19.  
  20. /**
  21.  * A class to represent a pool of regular expressions.  A string
  22.  * can be matched against the whole pool all at once.  It is much
  23.  * faster than doing individual regular expression matches one-by-one.
  24.  * @see java.util.RegexpTarget
  25.  * @author  James Gosling
  26.  */
  27.  
  28. public class RegexpPool {
  29.     private RegexpNode prefixMachine = new RegexpNode(0);
  30.     private RegexpNode suffixMachine = new RegexpNode(0);
  31.     private static final int BIG = 0x7FFFFFFF;
  32.     private int lastBestRank = BIG;
  33.     public RegexpPool () {
  34.     prefixMachine.rank = BIG;
  35.     suffixMachine.rank = BIG;
  36.     }
  37.     /** Add a regular expression to the pool of regular expressions.
  38.         @param    re  The regular expression to add to the pool.
  39.         For now, only handles strings that either begin or end with
  40.         a '*'.
  41.     @param    ret The object to be returned when this regular expression is
  42.         matched.  If ret is an instance of the RegexpTarget class, ret.found
  43.         is called with the string fragment that matched the '*' as its parameter.
  44.      */
  45.     public void add(String re, Object ret) {
  46.     int len = re.length();
  47.     RegexpNode p;
  48.     if (re.charAt(0) == '*') {
  49.         p = suffixMachine;
  50.         while (len > 1)
  51.         p = p.add(re.charAt(--len));
  52.     } else {
  53.         boolean exact = false;
  54.         if (re.charAt(len - 1) == '*')
  55.         len--;
  56.         else
  57.         exact = true;
  58.         p = prefixMachine;
  59.         for (int i = 0; i < len; i++)
  60.         p = p.add(re.charAt(i));
  61.         p.exact = exact;
  62.     }
  63.     if (p.result != null)
  64.         throw new REException(re + " is a duplicate");
  65.     p.result = ret;
  66.     p.rank = RegexpNode.masterrank++;
  67.  
  68.     }
  69.  
  70.     /** Search for a match to a string & return the object associated
  71.     with it with the match.  When multiple regular expressions
  72.     would match the string, the one returned is the one first added
  73.     to the pool.
  74.     @param s    The string to match against the regular expressions
  75.             in the pool.
  76.     @return        null on failure, otherwise the object associated with
  77.             the regular expression when it was added to the pool.
  78.             If the object is an instance of RegexpTarget, then
  79.             the return value is the result from calling
  80.             return.found(string_that_matched_wildcard).
  81.     */
  82.     public Object match(String s) {
  83.     return matchAfter(s, BIG);
  84.     }
  85.  
  86.     /** Identical to match except that it will only find matches to
  87.     regular expressions that were added to the pool <i>after<i>
  88.     the last regular expression that matched in the last call
  89.     to match() or matchNext() */
  90.     public Object matchNext(String s) {
  91.     return matchAfter(s, lastBestRank);
  92.     }
  93.  
  94.     private Object matchAfter(String s, int bestRank) {
  95.     RegexpNode p = prefixMachine;
  96.     RegexpNode best = p;
  97.     int bst = 0;
  98.     int bend = 0;
  99.     int len = s.length();
  100.     int i;
  101.     if (len <= 0)
  102.         return null;
  103.     /* March forward through the prefix machine */
  104.     for (i = 0; p != null; i++) {
  105.         if (p.result != null && p.rank < bestRank
  106.         && (!p.exact || i == len)) {
  107.         bestRank = p.rank;
  108.         best = p;
  109.         bst = i;
  110.         bend = len;
  111.         }
  112.         if (i >= len)
  113.         break;
  114.         p = p.find(s.charAt(i));
  115.     }
  116.     /* march backward through the suffix machine */
  117.     p = suffixMachine;
  118.     for (i = len; --i >= 0 && p != null;) {
  119.         if (p.result != null && p.rank < bestRank) {
  120.         bestRank = p.rank;
  121.         best = p;
  122.         bst = 0;
  123.         bend = i+1;
  124.         }
  125.         p = p.find(s.charAt(i));
  126.     }
  127.     Object o = best.result;
  128.     if (o != null && o instanceof RegexpTarget)
  129.         o = ((RegexpTarget) o).found(s.substring(bst, bend));
  130.     lastBestRank = bestRank;
  131.     return o;
  132.     }
  133.  
  134.     /** Resets the pool so that the next call to matchNext looks
  135.     at all regular expressions in the pool.  match(s); is equivalent
  136.     to reset(); matchNext(s);
  137.     <p><b>Multithreading note:</b> reset/nextMatch leave state in the
  138.     regular expression pool.  If multiple threads could be using this
  139.     pool this way, they should be syncronized to avoid race hazards.
  140.     match() was done in such a way that there are no such race
  141.     hazards: multiple threads can be matching in the same pool
  142.     simultaneously. */
  143.     public void reset() {
  144.     lastBestRank = BIG;
  145.     }
  146.  
  147.     static public void main(String argv[]) {
  148.     RegexpPool rp = new RegexpPool ();
  149.     for (int i = 1; i < argv.length; i++)
  150.         rp.add(argv[i], argv[i]);
  151.     rp.print();
  152.     }
  153.  
  154.     /** Print this pool to standard output */
  155.     public void print() {
  156.     System.out.print("Regexp pool:\n");
  157.     if (suffixMachine.firstchild != null) {
  158.         System.out.print(" Suffix machine: ");
  159.         suffixMachine.firstchild.print();
  160.         System.out.print("\n");
  161.     }
  162.     if (prefixMachine.firstchild != null) {
  163.         System.out.print(" Prefix machine: ");
  164.         prefixMachine.firstchild.print();
  165.         System.out.print("\n");
  166.     }
  167.     }
  168. }
  169.  
  170. /* A node in a regular expression finite state machine. */
  171. class RegexpNode {
  172.     char c;
  173.     RegexpNode firstchild;
  174.     RegexpNode nextsibling;
  175.     int rank;
  176.     boolean exact;
  177.     static int masterrank;
  178.     Object result;
  179.     RegexpNode (char C) {
  180.     c = C;
  181.     }
  182.     RegexpNode add(char C) {
  183.     RegexpNode p = firstchild;
  184.     if (p == null)
  185.         p = new RegexpNode (C);
  186.     else {
  187.         while (p != null)
  188.         if (p.c == C)
  189.             return p;
  190.         else
  191.             p = p.nextsibling;
  192.         p = new RegexpNode (C);
  193.         p.nextsibling = firstchild;
  194.     }
  195.     firstchild = p;
  196.     return p;
  197.     }
  198.     RegexpNode find(char C) {
  199.     for (RegexpNode p = firstchild;
  200.         p != null;
  201.         p = p.nextsibling)
  202.         if (p.c == C)
  203.         return p;
  204.     return null;
  205.     }
  206.     void print() {
  207.     if (nextsibling != null) {
  208.         RegexpNode p = this;
  209.         System.out.print("(");
  210.         while (p != null) {
  211.         System.out.write(p.c);
  212.         if (p.firstchild != null)
  213.             p.firstchild.print();
  214.         p = p.nextsibling;
  215.         System.out.write(p != null ? '|' : ')');
  216.         }
  217.     } else {
  218.         System.out.write(c);
  219.         if (firstchild != null)
  220.         firstchild.print();
  221.     }
  222.     }
  223.  
  224. }
  225.