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
8 package com.stevesoft.pat;
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
17 public class FastBracket extends Bracket
23 FastBracket(boolean n)
28 // This routine can optimize a bracket, possibly
29 // it will replace it with a FastBracket.
30 static Bracket process(Bracket b, boolean ignc)
37 // Expand out the vector to make separate
38 // entries for other cases if ignoreCase is
44 for (int i = 0; i < v.size(); i++)
46 Pattern p = (Pattern) v.elementAt(i);
48 if (p instanceof oneChar)
50 oneChar oc = (oneChar) p;
51 nv.addElement(new oneChar(oc.altc));
53 else if (p instanceof Range)
56 nv.addElement(new Range(ra.altlo, ra.althi));
62 // Bubble sort, make sure elements
63 // are in order. This will allow us
65 for (int i = 0; i < v.size() - 1; i++)
67 for (int j = 0; j < v.size() - 1; j++)
69 char c1 = getl(v.elementAt(j));
70 char c2 = getl(v.elementAt(j + 1));
73 Object o = v.elementAt(j);
74 v.setElementAt(v.elementAt(j + 1), j);
75 v.setElementAt(o, j + 1);
81 // merge -- remove overlaps
82 Pattern p = (Pattern) v.elementAt(0);
84 for (int i = 1; i < v.size(); i++)
86 if (geth(p) + 1 >= getl(v.elementAt(i)))
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);
95 p = (Pattern) v.elementAt(i);
101 } catch (RegSyntax e)
106 // We don't want these things to be empty.
107 Vector negv = neg(v);
112 if (negv.size() == 1)
119 // Now consider if we can make a FastBracket.
120 // Uses a BitSet to do a lookup.
121 FastBracket fb = newbrack(v, b.neg);
124 fb = newbrack(negv, !b.neg);
128 fb.parent = b.parent;
133 // return the normal Bracket.
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)
141 FastBracket fb = new FastBracket(neg);
147 fb.min = getl(v.elementAt(0));
148 fb.max = geth(v.elementAt(v.size() - 1));
149 if (fb.max - fb.min <= 256)
151 fb.bs = new BitSet(fb.max - fb.min + 1);
152 for (int i = 0; i < v.size(); i++)
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++)
167 // Negate a sorted Vector. Applying this
168 // operation twice should yield the same Vector
170 final static Vector neg(Vector v)
174 Vector nv = new Vector();
177 nv.addElement(new Range((char) 0, (char) 65535));
180 int p0 = getl(v.elementAt(0));
183 nv.addElement(mkelem((char) 0, (char) (p0 - 1)));
185 for (int i = 0; i < v.size() - 1; i++)
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));
191 int pN = geth(v.lastElement());
194 nv.addElement(mkelem((char) (pN + 1), (char) 65535));
197 } catch (RegSyntax rs)
203 // Make either a Range or oneChar Object, depending on which
205 final static Pattern mkelem(char lo, char hi) throws RegSyntax
207 return lo == hi ? (Pattern) (new oneChar(lo)) : (Pattern) (new Range(
211 static final char min(char a, char b)
213 return a < b ? a : b;
216 static final char max(char a, char b)
218 return a > b ? a : b;
221 // getl -- get lower value of Range object,
222 // or get value of oneChar object.
223 final static char getl(Object o)
225 Pattern p = (Pattern) o;
226 if (p instanceof Range)
228 return ((Range) p).lo;
230 return ((oneChar) p).c;
233 // geth -- get higher value of Range object,
234 // or get value of oneChar object.
235 final static char geth(Object o)
237 Pattern p = (Pattern) o;
238 if (p instanceof Range)
240 return ((Range) p).hi;
242 return ((oneChar) p).c;
245 // This is the easy part!
246 public int matchInternal(int pos, Pthings pt)
248 if (pos >= pt.src.length() || Masked(pos, pt))
252 char c = pt.src.charAt(pos);
253 return (neg ^ (c >= min && c <= max && bs.get(c - min))) ? nextMatch(