JAL-2629 can now filter by sequence e-value or bit score
[jalview.git] / src / com / stevesoft / pat / FastBracket.java
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
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.
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.
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.
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.
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
212   static final char min(char a, char b)
213   {
214     return a < b ? a : b;
215   }
216
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.
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.
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!
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 }