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
6 // -- Happy Computing!
\r
8 package com.stevesoft.pat;
\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
16 public class FastBracket
\r
21 FastBracket(boolean n)
\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
35 // Expand out the vector to make separate
\r
36 // entries for other cases if ignoreCase is
\r
42 for (int i = 0; i < v.size(); i++)
\r
44 Pattern p = (Pattern) v.elementAt(i);
\r
46 if (p instanceof oneChar)
\r
48 oneChar oc = (oneChar) p;
\r
49 nv.addElement(new oneChar(oc.altc));
\r
51 else if (p instanceof Range)
\r
53 Range ra = (Range) p;
\r
54 nv.addElement(new Range(ra.altlo, ra.althi));
\r
60 // Bubble sort, make sure elements
\r
61 // are in order. This will allow us
\r
63 for (int i = 0; i < v.size() - 1; i++)
\r
65 for (int j = 0; j < v.size() - 1; j++)
\r
67 char c1 = getl(v.elementAt(j));
\r
68 char c2 = getl(v.elementAt(j + 1));
\r
71 Object o = v.elementAt(j);
\r
72 v.setElementAt(v.elementAt(j + 1), j);
\r
73 v.setElementAt(o, j + 1);
\r
79 // merge -- remove overlaps
\r
80 Pattern p = (Pattern) v.elementAt(0);
\r
82 for (int i = 1; i < v.size(); i++)
\r
84 if (geth(p) + 1 >= getl(v.elementAt(i)))
\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
93 p = (Pattern) v.elementAt(i);
\r
100 catch (RegSyntax e)
\r
102 e.printStackTrace();
\r
105 // We don't want these things to be empty.
\r
106 Vector negv = neg(v);
\r
111 if (negv.size() == 1)
\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
123 fb = newbrack(negv, !b.neg);
\r
127 fb.parent = b.parent;
\r
132 // return the normal Bracket.
\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
140 FastBracket fb = new FastBracket(neg);
\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
150 fb.bs = new BitSet(fb.max - fb.min + 1);
\r
151 for (int i = 0; i < v.size(); i++)
\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
166 // Negate a sorted Vector. Applying this
\r
167 // operation twice should yield the same Vector
\r
169 final static Vector neg(Vector v)
\r
173 Vector nv = new Vector();
\r
176 nv.addElement(new Range( (char) 0, (char) 65535));
\r
179 int p0 = getl(v.elementAt(0));
\r
182 nv.addElement(mkelem( (char) 0, (char) (p0 - 1)));
\r
184 for (int i = 0; i < v.size() - 1; i++)
\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
190 int pN = geth(v.lastElement());
\r
193 nv.addElement(mkelem( (char) (pN + 1), (char) 65535));
\r
197 catch (RegSyntax rs)
\r
203 // Make either a Range or oneChar Object, depending on which
\r
205 final static Pattern mkelem(char lo, char hi)
\r
208 return lo == hi ? (Pattern) (new oneChar(lo)) : (Pattern) (new Range(lo, hi));
\r
211 static final char min(char a, char b)
\r
213 return a < b ? a : b;
\r
216 static final char max(char a, char b)
\r
218 return a > b ? a : b;
\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
225 Pattern p = (Pattern) o;
\r
226 if (p instanceof Range)
\r
228 return ( (Range) p).lo;
\r
230 return ( (oneChar) p).c;
\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
237 Pattern p = (Pattern) o;
\r
238 if (p instanceof Range)
\r
240 return ( (Range) p).hi;
\r
242 return ( (oneChar) p).c;
\r
245 // This is the easy part!
\r
246 public int matchInternal(int pos, Pthings pt)
\r
248 if (pos >= pt.src.length() || Masked(pos, pt))
\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