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