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 FastBracket(boolean n)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. process(Bracket b, boolean ignc)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. newbrack(Vector v, boolean neg)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. neg(Vector v)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. mkelem(char lo, char hi)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 min(char a, char b)212 static final char min(char a, char b) 213 { 214 return a < b ? a : b; 215 } 216 max(char a, char b)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. getl(Object o)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. geth(Object o)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! matchInternal(int pos, Pthings pt)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 } 258