src/com/stevesoft/pat/FastMulti.java

   1 //
   2 // This software is now distributed according to
   3 // the Lesser Gnu Public License.  Please see
   4 // http://www.gnu.org/copyleft/lesser.txt for
   5 // the details.
   6 //    -- Happy Computing!
   7 //
   8 package com.stevesoft.pat;
   9
  10 import java.util.Hashtable;
  11
  12 /**
  13  * A special case of Multi, implemented when minChars().equals(maxChars()), and
  14  * some other conditions spelled out in RegOpt.safe4fm "Safe for FastMulti." It
  15  * avoids stack growth problems as well as being slightly faster.
  16  */
  17 class FastMulti extends PatternSub
  18 {
  19   patInt fewestMatches, mostMatches;
  20
  21   public patInt minChars()
  22   {
  23     return sub.countMinChars().mul(fewestMatches);
  24   }
  25
  26   public patInt maxChars()
  27   {
  28     return sub.countMaxChars().mul(mostMatches);
  29   }
  30
  31   public boolean matchFewest = false;
  32
  33   FastMulti(patInt a, patInt b, Pattern p) throws RegSyntax
  34   {
  35     if (p == null)
  36     {
  37       RegSyntaxError.endItAll("Null length pattern "
  38               + "followed by *, +, or other Multi.");
  39     }
  40     fewestMatches = a;
  41     mostMatches = b;
  42     sub = p;
  43     step = p.countMinChars().intValue();
  44     sub.setParent(null);
  45   }
  46
  47   public String toString()
  48   {
  49     return sub.toString() + "{" + fewestMatches + "," + mostMatches + "}"
  50             + (matchFewest ? "?" : "") + "(?# <= fast multi)"
  51             + nextString();
  52   }
  53
  54   int step = -1;
  55
  56   public int matchInternal(int pos, Pthings pt)
  57   {
  58     int m = -1;
  59     int i = pos;
  60     int endstr = pt.src.length() - step;
  61     patInt matches = new patInt(0);
  62     if (matchFewest)
  63     {
  64       if (fewestMatches.lessEq(matches))
  65       {
  66         int ii = nextMatch(i, pt);
  67         if (ii >= 0)
  68         {
  69           return ii;
  70         }
  71       }
  72       while (i >= 0 && i <= endstr)
  73       {
  74         i = sub.matchInternal(i, pt);
  75         if (i >= 0)
  76         {
  77           matches.inc();
  78           if (fewestMatches.lessEq(matches))
  79           {
  80             int ii = nextMatch(i, pt);
  81             if (ii >= 0)
  82             {
  83               return ii;
  84             }
  85           }
  86           if (matches.equals(mostMatches))
  87           {
  88             return -1;
  89           }
  90         }
  91       }
  92       return -1;
  93     }
  94     int nMatches = 0;
  95     while (fewestMatches.intValue() > nMatches)
  96     {
  97       i = sub.matchInternal(i, pt);
  98       if (i >= 0)
  99       {
 100         nMatches++;
 101       }
 102       else
 103       {
 104         return -1;
 105       }
 106     }
 107     m = i;
 108     if (mostMatches.finite())
 109     {
 110       while (nMatches < mostMatches.intValue())
 111       {
 112         i = sub.matchInternal(i, pt);
 113         if (i >= 0)
 114         {
 115           m = i;
 116           nMatches++;
 117         }
 118         else
 119         {
 120           break;
 121         }
 122       }
 123     }
 124     else
 125     {
 126       while (true)
 127       {
 128         i = sub.matchInternal(i, pt);
 129         if (i >= 0)
 130         {
 131           m = i;
 132           nMatches++;
 133         }
 134         else
 135         {
 136           break;
 137         }
 138       }
 139     }
 140     while (m >= pos)
 141     {
 142       int r = nextMatch(m, pt);
 143       if (r >= 0)
 144       {
 145         return r;
 146       }
 147       m -= step;
 148       nMatches--;
 149       if (nMatches < fewestMatches.intValue())
 150       {
 151         return -1;
 152       }
 153     }
 154     return -1;
 155   }
 156
 157   public Pattern clone1(Hashtable h)
 158   {
 159     try
 160     {
 161       FastMulti fm = new FastMulti(fewestMatches, mostMatches, sub.clone(h));
 162       fm.matchFewest = matchFewest;
 163       return fm;
 164     } catch (RegSyntax rs)
 165     {
 166       return null;
 167     }
 168   }
 169 }