src/com/stevesoft/pat/FastBracket.java

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