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