-//\r
-// This software is now distributed according to\r
-// the Lesser Gnu Public License. Please see\r
-// http://www.gnu.org/copyleft/lesser.txt for\r
-// the details.\r
-// -- Happy Computing!\r
-//\r
-package com.stevesoft.pat;\r
-\r
-import java.util.*;\r
-\r
-/** Uses table lookup to match [] type constructs, but\r
- only if it can use a lookup table 256 bits in size.\r
- It is impractical to make a table if it is too large.\r
- */\r
-public class FastBracket\r
- extends Bracket\r
-{\r
- int min, max;\r
- BitSet bs;\r
- FastBracket(boolean n)\r
- {\r
- super(n);\r
- }\r
-\r
- // This routine can optimize a bracket, possibly\r
- // it will replace it with a FastBracket.\r
- static Bracket process(Bracket b, boolean ignc)\r
- {\r
- Vector v = b.v;\r
- b.pv = null;\r
- try\r
- {\r
-\r
- // Expand out the vector to make separate\r
- // entries for other cases if ignoreCase is\r
- // turned on.\r
- Vector nv = v;\r
- if (ignc)\r
- {\r
- nv = new Vector();\r
- for (int i = 0; i < v.size(); i++)\r
- {\r
- Pattern p = (Pattern) v.elementAt(i);\r
- nv.addElement(p);\r
- if (p instanceof oneChar)\r
- {\r
- oneChar oc = (oneChar) p;\r
- nv.addElement(new oneChar(oc.altc));\r
- }\r
- else if (p instanceof Range)\r
- {\r
- Range ra = (Range) p;\r
- nv.addElement(new Range(ra.altlo, ra.althi));\r
- }\r
- }\r
- }\r
- v = nv;\r
-\r
- // Bubble sort, make sure elements\r
- // are in order. This will allow us\r
- // to merge them.\r
- for (int i = 0; i < v.size() - 1; i++)\r
- {\r
- for (int j = 0; j < v.size() - 1; j++)\r
- {\r
- char c1 = getl(v.elementAt(j));\r
- char c2 = getl(v.elementAt(j + 1));\r
- if (c2 < c1)\r
- {\r
- Object o = v.elementAt(j);\r
- v.setElementAt(v.elementAt(j + 1), j);\r
- v.setElementAt(o, j + 1);\r
- }\r
- }\r
- }\r
-\r
- nv = new Vector();\r
- // merge -- remove overlaps\r
- Pattern p = (Pattern) v.elementAt(0);\r
- nv.addElement(p);\r
- for (int i = 1; i < v.size(); i++)\r
- {\r
- if (geth(p) + 1 >= getl(v.elementAt(i)))\r
- {\r
- Pattern p2 = (Pattern) v.elementAt(i);\r
- char lo = min(getl(p), getl(p2));\r
- char hi = max(geth(p), geth(p2));\r
- nv.setElementAt(p = mkelem(lo, hi), nv.size() - 1);\r
- }\r
- else\r
- {\r
- p = (Pattern) v.elementAt(i);\r
- nv.addElement(p);\r
- }\r
- }\r
-\r
- b.v = v = nv;\r
- }\r
- catch (RegSyntax e)\r
- {\r
- e.printStackTrace();\r
- }\r
-\r
- // We don't want these things to be empty.\r
- Vector negv = neg(v);\r
- if (v.size() == 1)\r
- {\r
- return b;\r
- }\r
- if (negv.size() == 1)\r
- {\r
- b.v = negv;\r
- b.neg = !b.neg;\r
- return b;\r
- }\r
-\r
- // Now consider if we can make a FastBracket.\r
- // Uses a BitSet to do a lookup.\r
- FastBracket fb = newbrack(v, b.neg);\r
- if (fb == null)\r
- {\r
- fb = newbrack(negv, !b.neg);\r
- }\r
- if (fb != null)\r
- {\r
- fb.parent = b.parent;\r
- fb.next = b.next;\r
- return fb;\r
- }\r
-\r
- // return the normal Bracket.\r
- return b;\r
- }\r
-\r
- // Build a FastBracket and set bits. If this can't\r
- // be done, return null.\r
- final static FastBracket newbrack(Vector v, boolean neg)\r
- {\r
- FastBracket fb = new FastBracket(neg);\r
- fb.v = v;\r
- if (v.size() == 0)\r
- {\r
- return null;\r
- }\r
- fb.min = getl(v.elementAt(0));\r
- fb.max = geth(v.elementAt(v.size() - 1));\r
- if (fb.max - fb.min <= 256)\r
- {\r
- fb.bs = new BitSet(fb.max - fb.min + 1);\r
- for (int i = 0; i < v.size(); i++)\r
- {\r
- Object o = v.elementAt(i);\r
- int min0 = getl(o) - fb.min;\r
- int max0 = geth(o) - fb.min;\r
- for (int j = min0; j <= max0; j++)\r
- {\r
- fb.bs.set(j);\r
- }\r
- }\r
- return fb;\r
- }\r
- return null;\r
- }\r
-\r
- // Negate a sorted Vector. Applying this\r
- // operation twice should yield the same Vector\r
- // back.\r
- final static Vector neg(Vector v)\r
- {\r
- try\r
- {\r
- Vector nv = new Vector();\r
- if (v.size() == 0)\r
- {\r
- nv.addElement(new Range( (char) 0, (char) 65535));\r
- return nv;\r
- }\r
- int p0 = getl(v.elementAt(0));\r
- if (p0 != 0)\r
- {\r
- nv.addElement(mkelem( (char) 0, (char) (p0 - 1)));\r
- }\r
- for (int i = 0; i < v.size() - 1; i++)\r
- {\r
- int hi = getl(v.elementAt(i + 1)) - 1;\r
- int lo = geth(v.elementAt(i)) + 1;\r
- nv.addElement(mkelem( (char) lo, (char) hi));\r
- }\r
- int pN = geth(v.lastElement());\r
- if (pN != 65535)\r
- {\r
- nv.addElement(mkelem( (char) (pN + 1), (char) 65535));\r
- }\r
- return nv;\r
- }\r
- catch (RegSyntax rs)\r
- {\r
- return null;\r
- }\r
- }\r
-\r
- // Make either a Range or oneChar Object, depending on which\r
- // is appropriate.\r
- final static Pattern mkelem(char lo, char hi)\r
- throws RegSyntax\r
- {\r
- return lo == hi ? (Pattern) (new oneChar(lo)) : (Pattern) (new Range(lo, hi));\r
- }\r
-\r
- static final char min(char a, char b)\r
- {\r
- return a < b ? a : b;\r
- }\r
-\r
- static final char max(char a, char b)\r
- {\r
- return a > b ? a : b;\r
- }\r
-\r
- // getl -- get lower value of Range object,\r
- // or get value of oneChar object.\r
- final static char getl(Object o)\r
- {\r
- Pattern p = (Pattern) o;\r
- if (p instanceof Range)\r
- {\r
- return ( (Range) p).lo;\r
- }\r
- return ( (oneChar) p).c;\r
- }\r
-\r
- // geth -- get higher value of Range object,\r
- // or get value of oneChar object.\r
- final static char geth(Object o)\r
- {\r
- Pattern p = (Pattern) o;\r
- if (p instanceof Range)\r
- {\r
- return ( (Range) p).hi;\r
- }\r
- return ( (oneChar) p).c;\r
- }\r
-\r
- // This is the easy part!\r
- public int matchInternal(int pos, Pthings pt)\r
- {\r
- if (pos >= pt.src.length() || Masked(pos, pt))\r
- {\r
- return -1;\r
- }\r
- char c = pt.src.charAt(pos);\r
- return (neg ^ (c >= min && c <= max && bs.get(c - min))) ?\r
- nextMatch(pos + 1, pt) : -1;\r
- }\r
-}\r
+//
+// This software is now distributed according to
+// the Lesser Gnu Public License. Please see
+// http://www.gnu.org/copyleft/lesser.txt for
+// the details.
+// -- Happy Computing!
+//
+package com.stevesoft.pat;
+
+import java.util.BitSet;
+import java.util.Vector;
+
+/**
+ * Uses table lookup to match [] type constructs, but only if it can use a
+ * lookup table 256 bits in size. It is impractical to make a table if it is too
+ * large.
+ */
+public class FastBracket extends Bracket
+{
+ int min, max;
+
+ BitSet bs;
+
+ FastBracket(boolean n)
+ {
+ super(n);
+ }
+
+ // This routine can optimize a bracket, possibly
+ // it will replace it with a FastBracket.
+ static Bracket process(Bracket b, boolean ignc)
+ {
+ Vector v = b.v;
+ b.pv = null;
+ try
+ {
+
+ // Expand out the vector to make separate
+ // entries for other cases if ignoreCase is
+ // turned on.
+ Vector nv = v;
+ if (ignc)
+ {
+ nv = new Vector();
+ for (int i = 0; i < v.size(); i++)
+ {
+ Pattern p = (Pattern) v.elementAt(i);
+ nv.addElement(p);
+ if (p instanceof oneChar)
+ {
+ oneChar oc = (oneChar) p;
+ nv.addElement(new oneChar(oc.altc));
+ }
+ else if (p instanceof Range)
+ {
+ Range ra = (Range) p;
+ nv.addElement(new Range(ra.altlo, ra.althi));
+ }
+ }
+ }
+ v = nv;
+
+ // Bubble sort, make sure elements
+ // are in order. This will allow us
+ // to merge them.
+ for (int i = 0; i < v.size() - 1; i++)
+ {
+ for (int j = 0; j < v.size() - 1; j++)
+ {
+ char c1 = getl(v.elementAt(j));
+ char c2 = getl(v.elementAt(j + 1));
+ if (c2 < c1)
+ {
+ Object o = v.elementAt(j);
+ v.setElementAt(v.elementAt(j + 1), j);
+ v.setElementAt(o, j + 1);
+ }
+ }
+ }
+
+ nv = new Vector();
+ // merge -- remove overlaps
+ Pattern p = (Pattern) v.elementAt(0);
+ nv.addElement(p);
+ for (int i = 1; i < v.size(); i++)
+ {
+ if (geth(p) + 1 >= getl(v.elementAt(i)))
+ {
+ Pattern p2 = (Pattern) v.elementAt(i);
+ char lo = min(getl(p), getl(p2));
+ char hi = max(geth(p), geth(p2));
+ nv.setElementAt(p = mkelem(lo, hi), nv.size() - 1);
+ }
+ else
+ {
+ p = (Pattern) v.elementAt(i);
+ nv.addElement(p);
+ }
+ }
+
+ b.v = v = nv;
+ } catch (RegSyntax e)
+ {
+ e.printStackTrace();
+ }
+
+ // We don't want these things to be empty.
+ Vector negv = neg(v);
+ if (v.size() == 1)
+ {
+ return b;
+ }
+ if (negv.size() == 1)
+ {
+ b.v = negv;
+ b.neg = !b.neg;
+ return b;
+ }
+
+ // Now consider if we can make a FastBracket.
+ // Uses a BitSet to do a lookup.
+ FastBracket fb = newbrack(v, b.neg);
+ if (fb == null)
+ {
+ fb = newbrack(negv, !b.neg);
+ }
+ if (fb != null)
+ {
+ fb.parent = b.parent;
+ fb.next = b.next;
+ return fb;
+ }
+
+ // return the normal Bracket.
+ return b;
+ }
+
+ // Build a FastBracket and set bits. If this can't
+ // be done, return null.
+ final static FastBracket newbrack(Vector v, boolean neg)
+ {
+ FastBracket fb = new FastBracket(neg);
+ fb.v = v;
+ if (v.size() == 0)
+ {
+ return null;
+ }
+ fb.min = getl(v.elementAt(0));
+ fb.max = geth(v.elementAt(v.size() - 1));
+ if (fb.max - fb.min <= 256)
+ {
+ fb.bs = new BitSet(fb.max - fb.min + 1);
+ for (int i = 0; i < v.size(); i++)
+ {
+ Object o = v.elementAt(i);
+ int min0 = getl(o) - fb.min;
+ int max0 = geth(o) - fb.min;
+ for (int j = min0; j <= max0; j++)
+ {
+ fb.bs.set(j);
+ }
+ }
+ return fb;
+ }
+ return null;
+ }
+
+ // Negate a sorted Vector. Applying this
+ // operation twice should yield the same Vector
+ // back.
+ final static Vector neg(Vector v)
+ {
+ try
+ {
+ Vector nv = new Vector();
+ if (v.size() == 0)
+ {
+ nv.addElement(new Range((char) 0, (char) 65535));
+ return nv;
+ }
+ int p0 = getl(v.elementAt(0));
+ if (p0 != 0)
+ {
+ nv.addElement(mkelem((char) 0, (char) (p0 - 1)));
+ }
+ for (int i = 0; i < v.size() - 1; i++)
+ {
+ int hi = getl(v.elementAt(i + 1)) - 1;
+ int lo = geth(v.elementAt(i)) + 1;
+ nv.addElement(mkelem((char) lo, (char) hi));
+ }
+ int pN = geth(v.lastElement());
+ if (pN != 65535)
+ {
+ nv.addElement(mkelem((char) (pN + 1), (char) 65535));
+ }
+ return nv;
+ } catch (RegSyntax rs)
+ {
+ return null;
+ }
+ }
+
+ // Make either a Range or oneChar Object, depending on which
+ // is appropriate.
+ final static Pattern mkelem(char lo, char hi) throws RegSyntax
+ {
+ return lo == hi ? (Pattern) (new oneChar(lo))
+ : (Pattern) (new Range(lo, hi));
+ }
+
+ static final char min(char a, char b)
+ {
+ return a < b ? a : b;
+ }
+
+ static final char max(char a, char b)
+ {
+ return a > b ? a : b;
+ }
+
+ // getl -- get lower value of Range object,
+ // or get value of oneChar object.
+ final static char getl(Object o)
+ {
+ Pattern p = (Pattern) o;
+ if (p instanceof Range)
+ {
+ return ((Range) p).lo;
+ }
+ return ((oneChar) p).c;
+ }
+
+ // geth -- get higher value of Range object,
+ // or get value of oneChar object.
+ final static char geth(Object o)
+ {
+ Pattern p = (Pattern) o;
+ if (p instanceof Range)
+ {
+ return ((Range) p).hi;
+ }
+ return ((oneChar) p).c;
+ }
+
+ // This is the easy part!
+ public int matchInternal(int pos, Pthings pt)
+ {
+ if (pos >= pt.src.length() || Masked(pos, pt))
+ {
+ return -1;
+ }
+ char c = pt.src.charAt(pos);
+ return (neg ^ (c >= min && c <= max && bs.get(c - min)))
+ ? nextMatch(pos + 1, pt)
+ : -1;
+ }
+}
git://source.jalview.org / jalview.git / blobdiff