JAL-2629 can now filter by sequence e-value or bit score
[jalview.git] / src / com / stevesoft / pat / RegOpt.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.Enumeration;
11 import java.util.Hashtable;
12 import java.util.Vector;
13
14 /** This class is just like oneChar, but doesn't worry about case. */
15 class FastChar extends oneChar
16 {
17   FastChar(char c)
18   {
19     super(c);
20   }
21
22   public int matchInternal(int p, Pthings pt)
23   {
24     return (p < pt.src.length() && pt.src.charAt(p) == c) ? nextMatch(
25             p + 1, pt) : -1;
26   }
27
28   Pattern clone1(Hashtable h)
29   {
30     return new FastChar(c);
31   }
32 }
33
34 /**
35  * This class is a hashtable keyed by Character Objects. It is used to match
36  * things of the form (?:a..|b..|c..|..) match with greater efficiency -- by
37  * using a Hashtable that indexes into the group of patterns.
38  */
39 class Branch extends Pattern
40 {
41   Hashtable h = new Hashtable();
42
43   // We need to keep track of the order
44   // of the keys -- if we don't then
45   // recompiling the output of toString
46   // may produce errors by re-ordering
47   // ()'s and changing the id number of
48   // the backreference associated with
49   // a subpattern.
50   Vector keys = new Vector();
51
52   Branch()
53   {
54   }
55
56   Pattern clone1(Hashtable x)
57   {
58     Branch b = new Branch();
59     b.keys = (Vector) keys.clone();
60     x.put(this, b);
61     x.put(b, b);
62
63     for (int i = 0; i < keys.size(); i++)
64     {
65       Pattern p = (Pattern) h.get(keys.elementAt(i));
66       b.h.put(keys.elementAt(i), p.clone(x));
67     }
68     return b;
69   }
70
71   // this function eliminates Branches with 0 or 1 elements.
72   final Pattern reduce(boolean ignoreCase, boolean dontMinQ)
73   {
74     if (h.size() == 1)
75     {
76       Enumeration e = h.keys();
77       Character c = (Character) e.nextElement();
78       Pattern oc;
79       if (ignoreCase || dontMinQ)
80       {
81         oc = new oneChar(c.charValue());
82       }
83       else
84       {
85         oc = new FastChar(c.charValue());
86       }
87       oc.next = (Pattern) h.get(c);
88       oc.add(next);
89       return oc;
90     }
91     else if (h.size() == 0)
92     {
93       return null;
94     }
95     return this;
96   }
97
98   public patInt maxChars()
99   {
100     Enumeration e = h.keys();
101     patInt count = new patInt(0);
102     while (e.hasMoreElements())
103     {
104       Object key = e.nextElement();
105       Pattern pa = (Pattern) h.get(key);
106       patInt pi = pa.maxChars();
107       pi.inc();
108       count.maxeq(pi);
109     }
110     return count;
111   }
112
113   public patInt minChars()
114   {
115     Enumeration e = h.keys();
116     patInt count = new patInt(0);
117     while (e.hasMoreElements())
118     {
119       Object key = e.nextElement();
120       Pattern pa = (Pattern) h.get(key);
121       patInt pi = pa.minChars();
122       pi.inc();
123       count.mineq(pi);
124     }
125     return count;
126   }
127
128   // adds a oneChar object to this Branch
129   void addc(oneChar o, boolean ignoreCase, boolean dontMinQ)
130   {
131     Pattern n = o.next;
132     if (n == null)
133     {
134       n = new NullPattern();
135     }
136     else
137     {
138       n = RegOpt.opt(n, ignoreCase, dontMinQ);
139     }
140     n.setParent(this);
141     set(Character.valueOf(o.c), n, ignoreCase, dontMinQ);
142     if (ignoreCase)
143     {
144       if (o.c != o.altc)
145       {
146         set(Character.valueOf(o.altc), n, ignoreCase, dontMinQ);
147       }
148       if (o.c != o.altc2 && o.altc != o.altc2)
149       {
150         set(Character.valueOf(o.altc2), n, ignoreCase, dontMinQ);
151       }
152     }
153   }
154
155   void set(Character c, Pattern n, boolean igc, boolean dontMinQ)
156   {
157     Pattern p = (Pattern) h.get(c);
158     next = null;
159     // This letter is not yet used in the Branch object.
160     // We need to add it.
161     if (p == null)
162     {
163       if (n instanceof Or)
164       {
165         // A NullPattern is prepended to an Or
166         // to prevent confusing this object.
167         // For example: (boo|bug) => (b(?:oo|ug))
168         // during this process. However, we
169         // want (b(?:oo|ell)|bug)
170         NullPattern np = new NullPattern();
171         np.add(n);
172         h.put(c, np);
173       }
174       else
175       {
176         h.put(c, n);
177       }
178       // Make sure we remember the order things were
179       // added into the Branch object so that we can
180       // properly convert it to a String.
181       keys.addElement(c);
182     }
183     else if (p instanceof Or)
184     {
185       ((Or) p).addOr(n);
186     }
187     else if (p instanceof oneChar && n instanceof oneChar
188             && ((oneChar) p).c != ((oneChar) n).c)
189     {
190       Branch b = new Branch();
191       b.addc((oneChar) p, igc, dontMinQ);
192       b.addc((oneChar) n, igc, dontMinQ);
193       h.put(c, b);
194       b.setParent(this);
195     }
196     else if (p instanceof Branch && n instanceof oneChar)
197     {
198       ((Branch) p).addc((oneChar) n, igc, dontMinQ);
199       n.setParent(p);
200     }
201     else
202     {
203       // Create an Or object to receive the variety
204       // of branches in the pattern if the current letter
205       // is matched. We do not attempt to make these
206       // sub-branches into a Branch object yet.
207       Or o = new Or();
208       o.setParent(this);
209
210       // Remove NullPattern from p -- it's no longer needed.
211       if (p instanceof NullPattern && p.parent == null && p.next != null)
212       {
213         o.addOr(p.next);
214       }
215       else
216       {
217         o.addOr(p);
218       }
219       o.addOr(n);
220
221       Pattern optpat = RegOpt.opt(o, igc, dontMinQ);
222       h.put(c, optpat);
223       optpat.setParent(this);
224     }
225   }
226
227   public String toString()
228   {
229     StringBuffer sb = new StringBuffer();
230     // should protect this...
231     sb.append("(?:(?#branch)"); // Hashtable)");
232     for (int i = 0; i < keys.size(); i++)
233     {
234       Character c = (Character) keys.elementAt(i);
235       sb.append(c);
236       sb.append(h.get(c));
237       if (i + 1 < keys.size())
238       {
239         sb.append("|");
240       }
241     }
242     sb.append(")");
243     sb.append(nextString());
244     return sb.toString();
245   }
246
247   public int matchInternal(int pos, Pthings pt)
248   {
249     if (pos >= pt.src.length())
250     {
251       return -1;
252     }
253     Pattern n = (Pattern) h.get(Character.valueOf(pt.src.charAt(pos)));
254     if (n == null)
255     {
256       return -1;
257     }
258     if (pt.cbits != null && pt.cbits.get(pos))
259     {
260       return -1;
261     }
262     return n.matchInternal(pos + 1, pt);
263   }
264 }
265
266 /**
267  * This is just a place to put the optimizing function. It is never instantiated
268  * as an Object. It just sorts through the RegOpt looking for things it can
269  * change and make faster.
270  */
271 public class RegOpt
272 {
273   static Pattern opt(Pattern p, boolean ignoreCase, boolean dontMinQ)
274   {
275     if (p == null)
276     {
277       return p;
278     }
279     if (p instanceof Bracket)
280     {
281       Bracket b = (Bracket) p;
282       // FastBracket is the only special
283       // optimized class to have its own
284       // source file.
285       p = FastBracket.process(b, ignoreCase);
286       // if(!(p instanceof FastBracket)
287       // p = Switch.process(b,ignoreCase);
288       p.next = b.next;
289       p.parent = b.parent;
290     }
291     else if (p instanceof oneChar && !ignoreCase && !dontMinQ)
292     {
293       oneChar o = (oneChar) p;
294       p = new FastChar(o.c);
295       p.next = o.next;
296       p.parent = o.parent;
297     }
298     else if (p instanceof Or && ((Or) p).leftForm().equals("(?:")
299             && ((Or) p).v.size() == 1)
300     { // Eliminate this Or Object.
301       Or o = (Or) p;
302       p = (Pattern) o.v.elementAt(0);
303       p.setParent(null);
304       p = RegOpt.opt(p, ignoreCase, dontMinQ);
305       p.add(o.next);
306     }
307     else if (p instanceof Or)
308     {
309       Or o = (Or) p;
310       o.pv = null;
311       Vector v = o.v;
312       o.v = new Vector();
313       Branch b = new Branch();
314       b.parent = o.parent;
315       for (int i = 0; i < v.size(); i++)
316       {
317         Pattern pp = (Pattern) v.elementAt(i);
318         // We want to have at least two oneChar's in
319         // the Or Object to consider making a Branch.
320         if (pp instanceof oneChar
321                 && (b.h.size() >= 1 || (i + 1 < v.size() && v
322                         .elementAt(i + 1) instanceof oneChar)))
323         {
324           b.addc((oneChar) pp, ignoreCase, dontMinQ);
325         }
326         else
327         {
328           if (b.keys.size() > 0)
329           {
330             Pattern p2 = (Pattern) b.reduce(ignoreCase, dontMinQ);
331             if (p2 != null)
332             {
333               o.addOr(p2);
334               b = new Branch();
335               b.parent = o.parent;
336             }
337           }
338           o.addOr(opt(pp, ignoreCase, dontMinQ));
339         }
340       }
341       if (b.keys.size() > 0)
342       {
343         Pattern p2 = (Pattern) b.reduce(ignoreCase, dontMinQ);
344         if (p2 != null)
345         {
346           o.addOr(p2);
347         }
348       }
349       if (o.v.size() == 1 && o.leftForm().equals("(?:"))
350       { // Eliminate Or Object
351         p = (Pattern) o.v.elementAt(0);
352         p.setParent(null);
353         p = RegOpt.opt(p, ignoreCase, dontMinQ);
354         p.add(o.next);
355       }
356     }
357     else if (p instanceof FastMulti)
358     {
359       PatternSub ps = (PatternSub) p;
360       ps.sub = RegOpt.opt(ps.sub, ignoreCase, dontMinQ);
361     }
362     else if (p instanceof Multi && safe4fm(((PatternSub) p).sub))
363     {
364       Multi m = (Multi) p;
365       FastMulti fm = null;
366       try
367       {
368         fm = new FastMulti(m.a, m.b, opt(m.sub, ignoreCase, dontMinQ));
369       } catch (RegSyntax rs)
370       {
371       }
372       fm.parent = m.parent;
373       fm.matchFewest = m.matchFewest;
374       fm.next = m.next;
375       p = fm;
376     }
377     if (p.next != null)
378     {
379       p.next = opt(p.next, ignoreCase, dontMinQ);
380     }
381     return p;
382   }
383
384   final static boolean safe4fm(Pattern x)
385   {
386     while (x != null)
387     {
388       if (x instanceof Bracket)
389       {
390         ;
391       }
392       else if (x instanceof Range)
393       {
394         ;
395       }
396       else if (x instanceof oneChar)
397       {
398         ;
399       }
400       else if (x instanceof Any)
401       {
402         ;
403       }
404       else if (x instanceof Custom
405               && ((Custom) x).v instanceof UniValidator)
406       {
407         ;
408       }
409       else if (x instanceof Or)
410       {
411         Or o = (Or) x;
412         if (!o.leftForm().equals("(?:"))
413         {
414           return false;
415         }
416         patInt lo = o.countMinChars();
417         patInt hi = o.countMaxChars();
418         if (!lo.equals(hi))
419         {
420           return false;
421         }
422         for (int i = 0; i < o.v.size(); i++)
423         {
424           if (!safe4fm((Pattern) o.v.elementAt(i)))
425           {
426             return false;
427           }
428         }
429       }
430       else
431       {
432         return false;
433       }
434       x = x.next;
435     }
436     return true;
437   }
438   /*
439    * public static void setParents(Regex r) { setParents(r.thePattern,null); }
440    * static void setParents(Pattern p,Pattern x) { if(p instanceof PatternSub &&
441    * !(p instanceof FastMulti) && !(p instanceof DotMulti)) RegOpt.setParents(
442    * ((PatternSub)p).sub, p); else if(p instanceof Or && !(p instanceof
443    * Bracket)) { Or o = (Or)p; for(int i=0;i<o.v.size();i++)
444    * RegOpt.setParents((Pattern)o.v.elementAt(i),o); } else if(p instanceof
445    * Branch) { Branch b = (Branch)p; Enumeration e = b.h.keys();
446    * while(e.hasMoreElements()) { Object o = e.nextElement(); RegOpt.setParents(
447    * (Pattern)b.h.get(o), b); } } if(p.next == null) p.parent = x; else {
448    * p.parent = null; RegOpt.setParents(p.next,x); } }
449    */
450 }