JAL-2629 can now filter by sequence e-value or bit score
[jalview.git] / src / com / stevesoft / pat / SkipBMH.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 com.stevesoft.pat.wrap.StringWrap;
11
12 /**
13  * Like Skip, but implements a <a
14  * href="http://www.dcc.uchile.cl/~rbaeza/handbook/algs/7/713b.srch.p.html">
15  * Boyer-Moore-Horspool</a> type search method that has been modified to be more
16  * like a "T-search" (see the Michael Tamm''s article in <i>C'T, magazin fuer
17  * computer und technic</i>, August 97 p 292). Yet another important source of
18  * information for me was the <a
19  * href="http://www.go2net.com/people/paulp/deep/1997/05/14/"> Deep Magic</a>
20  * article on string searching. As of this writing, I can beat String's indexOf
21  * method in many cases.
22  * 
23  * @see com.stevesoft.pat.Skip
24  * @see com.stevesoft.pat.Skip2
25  */
26 public class SkipBMH extends Skip
27 {
28   // This number could be 256, but I think it's
29   // big enough. Note, it must be a power of 2.
30   final int MAX_CHAR = 64;
31
32   final char[] skip = new char[MAX_CHAR];
33
34   int sm1;
35
36   int jump_ahead = 0;
37
38   char uc, lc, tc, x;
39
40   final boolean exact(char c)
41   {
42     return (ign && anyc(c)) || c == x;
43   }
44
45   final boolean anyc(char c)
46   {
47     return c == uc || c == lc || c == tc;
48   }
49
50   public SkipBMH(String pt, boolean ign)
51   {
52     this(pt, ign, 0);
53   }
54
55   public SkipBMH(String pt)
56   {
57     this(pt, false, 0);
58   }
59
60   public SkipBMH(String pt, boolean ign, int offset)
61   {
62     super(pt, ign, offset);
63     for (int k = 0; k < MAX_CHAR; k++)
64     {
65       skip[k] = (char) src.length();
66     }
67
68     sm1 = src.length() - 1;
69     x = src.charAt(sm1);
70     uc = CaseMgr.toUpperCase(x);
71     lc = CaseMgr.toLowerCase(x);
72     tc = CaseMgr.toTitleCase(x);
73
74     // We don't really want 65536 long arrays in skip[],
75     // so we mask of the higher bits. This can be combined
76     // with ignore case, so accounting for upper
77     // case costs us nothing extra.
78     for (int k = 0; k < src.length() - 1; k++)
79     {
80       char x_ = src.charAt(k);
81       if (ign)
82       {
83         char uc_ = CaseMgr.toUpperCase(x_);
84         char lc_ = CaseMgr.toLowerCase(x_);
85         char tc_ = CaseMgr.toTitleCase(x_);
86         skip[uc_ & (MAX_CHAR - 1)] = (char) (src.length() - k - 1);
87         skip[lc_ & (MAX_CHAR - 1)] = (char) (src.length() - k - 1);
88         skip[tc_ & (MAX_CHAR - 1)] = (char) (src.length() - k - 1);
89       }
90       else
91       {
92         skip[x_ & (MAX_CHAR - 1)] = (char) (src.length() - k - 1);
93       }
94     }
95
96     // This trick can be found in the July issue of
97     // C-T magazine. This makes the method a type of
98     // "T-search."
99     jump_ahead = src.length() - 1;
100     for (int k = 0; k < src.length() - 1; k++)
101     {
102       char y = src.charAt(sm1 - k - 1);
103       if (exact(y))
104       {
105         jump_ahead = k;
106         break;
107       }
108     }
109   }
110
111   /**
112    * Set to true if you only want to compare two of the characters in the
113    * String.
114    */
115   final public int searchRegion(String s, int start, int end)
116   {
117     return find(s, start, end);
118   }
119
120   final public int searchFrom(String s, int start)
121   {
122     return find(s, start, s.length());
123   }
124
125   final public int search(String s)
126   {
127     return find(s, 0, s.length());
128   }
129
130   public int find(String s, int start, int end)
131   {
132     start += offset + sm1;
133     int vend = min(s.length() - 1, end + sm1 + offset), k;
134     int vend1 = vend - jump_ahead;
135     if (ign)
136     {
137       for (k = start; k <= vend1; k += skip[s.charAt(k) & (MAX_CHAR - 1)])
138       {
139         // table look-up is expensive, avoid it if possible
140         if (anyc(s.charAt(k)))
141         {
142           if (CaseMgr.regionMatches(src, ign, 0, s, k - sm1, sm1))
143           {
144             return k - sm1 - offset;
145           }
146           k += jump_ahead;
147         }
148       }
149       for (; k <= vend; k += skip[s.charAt(k) & (MAX_CHAR - 1)])
150       {
151         // table look-up is expensive, avoid it if possible
152         if (anyc(s.charAt(k)))
153         {
154           if (CaseMgr.regionMatches(src, ign, 0, s, k - sm1, sm1))
155           {
156             return k - sm1 - offset;
157           }
158           k += jump_ahead;
159           if (k > vend)
160           {
161             return -1;
162           }
163         }
164       }
165     }
166     else
167     {
168       for (k = start; k <= vend1; k += skip[s.charAt(k) & (MAX_CHAR - 1)])
169       {
170         // table look-up is expensive, avoid it if possible
171         if (x == s.charAt(k))
172         {
173           // if(src.regionMatches(0,s,k-sm1,sm1))
174           if (CaseMgr.regionMatches(src, false, 0, s, k - sm1, sm1))
175           {
176             return k - sm1 - offset;
177           }
178           k += jump_ahead;
179         }
180       }
181       for (; k <= vend; k += skip[s.charAt(k) & (MAX_CHAR - 1)])
182       {
183         // table look-up is expensive, avoid it if possible
184         if (x == s.charAt(k))
185         {
186           // if(src.regionMatches(0,s,k-sm1,sm1))
187           if (CaseMgr.regionMatches(src, false, 0, s, k - sm1, sm1))
188           {
189             return k - sm1 - offset;
190           }
191           k += jump_ahead;
192           if (k > vend)
193           {
194             return -1;
195           }
196         }
197       }
198     }
199
200     return -1;
201   }
202
203   public int find(StringLike s, int start, int end)
204   {
205     if (s instanceof StringWrap)
206     {
207       return find(s.toString(), start, end);
208     }
209     start += offset + sm1;
210     int vend = min(s.length() - 1, end + sm1 + offset), k;
211     int vend1 = vend - jump_ahead;
212     if (ign)
213     {
214       for (k = start; k <= vend1; k += skip[s.charAt(k) & (MAX_CHAR - 1)])
215       {
216         // table look-up is expensive, avoid it if possible
217         if (anyc(s.charAt(k)))
218         {
219           if (CaseMgr.regionMatches(src, ign, 0, s, k - sm1, sm1))
220           {
221             return k - sm1 - offset;
222           }
223           k += jump_ahead;
224         }
225       }
226       for (; k <= vend; k += skip[s.charAt(k) & (MAX_CHAR - 1)])
227       {
228         // table look-up is expensive, avoid it if possible
229         if (anyc(s.charAt(k)))
230         {
231           if (CaseMgr.regionMatches(src, ign, 0, s, k - sm1, sm1))
232           {
233             return k - sm1 - offset;
234           }
235           k += jump_ahead;
236           if (k > vend)
237           {
238             return -1;
239           }
240         }
241       }
242     }
243     else
244     {
245       for (k = start; k <= vend1; k += skip[s.charAt(k) & (MAX_CHAR - 1)])
246       {
247         // table look-up is expensive, avoid it if possible
248         if (x == s.charAt(k))
249         {
250           // if(src.regionMatches(0,s,k-sm1,sm1))
251           if (CaseMgr.regionMatches(src, false, 0, s, k - sm1, sm1))
252           {
253             return k - sm1 - offset;
254           }
255           k += jump_ahead;
256         }
257       }
258       for (; k <= vend; k += skip[s.charAt(k) & (MAX_CHAR - 1)])
259       {
260         // table look-up is expensive, avoid it if possible
261         if (x == s.charAt(k))
262         {
263           // if(src.regionMatches(0,s,k-sm1,sm1))
264           if (CaseMgr.regionMatches(src, false, 0, s, k - sm1, sm1))
265           {
266             return k - sm1 - offset;
267           }
268           k += jump_ahead;
269           if (k > vend)
270           {
271             return -1;
272           }
273         }
274       }
275     }
276
277     return -1;
278   }
279 }