src/com/stevesoft/pat/FastBracket.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.*;
  11
  12 /**
  13  * Uses table lookup to match [] type constructs, but only if it can use a
  14  * lookup table 256 bits in size. It is impractical to make a table if it is too
  15  * large.
  16  */
  17 public class FastBracket extends Bracket
  18 {
  19   int min, max;
  20
  21   BitSet bs;
  22
  23   FastBracket(boolean n)
  24   {
  25     super(n);
  26   }
  27
  28   // This routine can optimize a bracket, possibly
  29   // it will replace it with a FastBracket.
  30   static Bracket process(Bracket b, boolean ignc)
  31   {
  32     Vector v = b.v;
  33     b.pv = null;
  34     try
  35     {
  36
  37       // Expand out the vector to make separate
  38       // entries for other cases if ignoreCase is
  39       // turned on.
  40       Vector nv = v;
  41       if (ignc)
  42       {
  43         nv = new Vector();
  44         for (int i = 0; i < v.size(); i++)
  45         {
  46           Pattern p = (Pattern) v.elementAt(i);
  47           nv.addElement(p);
  48           if (p instanceof oneChar)
  49           {
  50             oneChar oc = (oneChar) p;
  51             nv.addElement(new oneChar(oc.altc));
  52           }
  53           else if (p instanceof Range)
  54           {
  55             Range ra = (Range) p;
  56             nv.addElement(new Range(ra.altlo, ra.althi));
  57           }
  58         }
  59       }
  60       v = nv;
  61
  62       // Bubble sort, make sure elements
  63       // are in order. This will allow us
  64       // to merge them.
  65       for (int i = 0; i < v.size() - 1; i++)
  66       {
  67         for (int j = 0; j < v.size() - 1; j++)
  68         {
  69           char c1 = getl(v.elementAt(j));
  70           char c2 = getl(v.elementAt(j + 1));
  71           if (c2 < c1)
  72           {
  73             Object o = v.elementAt(j);
  74             v.setElementAt(v.elementAt(j + 1), j);
  75             v.setElementAt(o, j + 1);
  76           }
  77         }
  78       }
  79
  80       nv = new Vector();
  81       // merge -- remove overlaps
  82       Pattern p = (Pattern) v.elementAt(0);
  83       nv.addElement(p);
  84       for (int i = 1; i < v.size(); i++)
  85       {
  86         if (geth(p) + 1 >= getl(v.elementAt(i)))
  87         {
  88           Pattern p2 = (Pattern) v.elementAt(i);
  89           char lo = min(getl(p), getl(p2));
  90           char hi = max(geth(p), geth(p2));
  91           nv.setElementAt(p = mkelem(lo, hi), nv.size() - 1);
  92         }
  93         else
  94         {
  95           p = (Pattern) v.elementAt(i);
  96           nv.addElement(p);
  97         }
  98       }
  99
 100       b.v = v = nv;
 101     } catch (RegSyntax e)
 102     {
 103       e.printStackTrace();
 104     }
 105
 106     // We don't want these things to be empty.
 107     Vector negv = neg(v);
 108     if (v.size() == 1)
 109     {
 110       return b;
 111     }
 112     if (negv.size() == 1)
 113     {
 114       b.v = negv;
 115       b.neg = !b.neg;
 116       return b;
 117     }
 118
 119     // Now consider if we can make a FastBracket.
 120     // Uses a BitSet to do a lookup.
 121     FastBracket fb = newbrack(v, b.neg);
 122     if (fb == null)
 123     {
 124       fb = newbrack(negv, !b.neg);
 125     }
 126     if (fb != null)
 127     {
 128       fb.parent = b.parent;
 129       fb.next = b.next;
 130       return fb;
 131     }
 132
 133     // return the normal Bracket.
 134     return b;
 135   }
 136
 137   // Build a FastBracket and set bits. If this can't
 138   // be done, return null.
 139   final static FastBracket newbrack(Vector v, boolean neg)
 140   {
 141     FastBracket fb = new FastBracket(neg);
 142     fb.v = v;
 143     if (v.size() == 0)
 144     {
 145       return null;
 146     }
 147     fb.min = getl(v.elementAt(0));
 148     fb.max = geth(v.elementAt(v.size() - 1));
 149     if (fb.max - fb.min <= 256)
 150     {
 151       fb.bs = new BitSet(fb.max - fb.min + 1);
 152       for (int i = 0; i < v.size(); i++)
 153       {
 154         Object o = v.elementAt(i);
 155         int min0 = getl(o) - fb.min;
 156         int max0 = geth(o) - fb.min;
 157         for (int j = min0; j <= max0; j++)
 158         {
 159           fb.bs.set(j);
 160         }
 161       }
 162       return fb;
 163     }
 164     return null;
 165   }
 166
 167   // Negate a sorted Vector. Applying this
 168   // operation twice should yield the same Vector
 169   // back.
 170   final static Vector neg(Vector v)
 171   {
 172     try
 173     {
 174       Vector nv = new Vector();
 175       if (v.size() == 0)
 176       {
 177         nv.addElement(new Range((char) 0, (char) 65535));
 178         return nv;
 179       }
 180       int p0 = getl(v.elementAt(0));
 181       if (p0 != 0)
 182       {
 183         nv.addElement(mkelem((char) 0, (char) (p0 - 1)));
 184       }
 185       for (int i = 0; i < v.size() - 1; i++)
 186       {
 187         int hi = getl(v.elementAt(i + 1)) - 1;
 188         int lo = geth(v.elementAt(i)) + 1;
 189         nv.addElement(mkelem((char) lo, (char) hi));
 190       }
 191       int pN = geth(v.lastElement());
 192       if (pN != 65535)
 193       {
 194         nv.addElement(mkelem((char) (pN + 1), (char) 65535));
 195       }
 196       return nv;
 197     } catch (RegSyntax rs)
 198     {
 199       return null;
 200     }
 201   }
 202
 203   // Make either a Range or oneChar Object, depending on which
 204   // is appropriate.
 205   final static Pattern mkelem(char lo, char hi) throws RegSyntax
 206   {
 207     return lo == hi ? (Pattern) (new oneChar(lo)) : (Pattern) (new Range(
 208             lo, hi));
 209   }
 210
 211   static final char min(char a, char b)
 212   {
 213     return a < b ? a : b;
 214   }
 215
 216   static final char max(char a, char b)
 217   {
 218     return a > b ? a : b;
 219   }
 220
 221   // getl -- get lower value of Range object,
 222   // or get value of oneChar object.
 223   final static char getl(Object o)
 224   {
 225     Pattern p = (Pattern) o;
 226     if (p instanceof Range)
 227     {
 228       return ((Range) p).lo;
 229     }
 230     return ((oneChar) p).c;
 231   }
 232
 233   // geth -- get higher value of Range object,
 234   // or get value of oneChar object.
 235   final static char geth(Object o)
 236   {
 237     Pattern p = (Pattern) o;
 238     if (p instanceof Range)
 239     {
 240       return ((Range) p).hi;
 241     }
 242     return ((oneChar) p).c;
 243   }
 244
 245   // This is the easy part!
 246   public int matchInternal(int pos, Pthings pt)
 247   {
 248     if (pos >= pt.src.length() || Masked(pos, pt))
 249     {
 250       return -1;
 251     }
 252     char c = pt.src.charAt(pos);
 253     return (neg ^ (c >= min && c <= max && bs.get(c - min))) ? nextMatch(
 254             pos + 1, pt) : -1;
 255   }
 256 }