Graphical bits moved into files to save jar size
[jalview.git] / src / com / stevesoft / pat / SkipBMH.java
1 //\r
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
5 // the details.\r
6 //    -- Happy Computing!\r
7 //\r
8 package com.stevesoft.pat;\r
9 \r
10 import com.stevesoft.pat.wrap.StringWrap;\r
11 \r
12 /** Like Skip, but implements a\r
13     <a href="http://www.dcc.uchile.cl/~rbaeza/handbook/algs/7/713b.srch.p.html">\r
14     Boyer-Moore-Horspool</a> type search\r
15     method that has been modified to be more like a "T-search" (see\r
16     the Michael Tamm''s article in <i>C'T, magazin fuer computer und technic</i>, August 97\r
17     p 292).  Yet another important source of information for me was\r
18     the <a href="http://www.go2net.com/people/paulp/deep/1997/05/14/">\r
19     Deep Magic</a> article on string searching.  As of this writing, I can\r
20     beat String's indexOf method in many cases.\r
21     @see com.stevesoft.pat.Skip\r
22     @see com.stevesoft.pat.Skip2\r
23     */\r
24 public class SkipBMH extends Skip {\r
25     // This number could be 256, but I think it's\r
26     // big enough.  Note, it must be a power of 2.\r
27     final int MAX_CHAR = 64;\r
28     final char[] skip = new char[MAX_CHAR];\r
29     int sm1;\r
30     int jump_ahead = 0;\r
31     char uc,lc,tc,x;\r
32     final boolean exact(char c) {\r
33         return (ign && anyc(c))||c==x;\r
34     }\r
35     final boolean anyc(char c) {\r
36         return c==uc||c==lc||c==tc;\r
37     }\r
38     public SkipBMH(String pt,boolean ign) { this(pt,ign,0); }\r
39     public SkipBMH(String pt) { this(pt,false,0); }\r
40     public SkipBMH(String pt,boolean ign,int offset) {\r
41         super(pt,ign,offset);\r
42         for(int k=0;k<MAX_CHAR;k++)\r
43             skip[k] = (char)src.length();\r
44 \r
45         sm1 = src.length()-1;\r
46         x = src.charAt(sm1);\r
47         uc=CaseMgr.toUpperCase(x);\r
48         lc=CaseMgr.toLowerCase(x);\r
49         tc=CaseMgr.toTitleCase(x);\r
50 \r
51         // We don't really want 65536 long arrays in skip[],\r
52         // so we mask of the higher bits.  This can be combined\r
53         // with ignore case, so accounting for upper\r
54         // case costs us nothing extra.\r
55         for(int k=0;k<src.length()-1;k++) {\r
56             char x_ = src.charAt(k);\r
57             if(ign) {\r
58                 char uc_ = CaseMgr.toUpperCase(x_);\r
59                 char lc_ = CaseMgr.toLowerCase(x_);\r
60                 char tc_ = CaseMgr.toTitleCase(x_);\r
61                 skip[uc_ & (MAX_CHAR-1)]=(char)(src.length()-k-1);\r
62                 skip[lc_ & (MAX_CHAR-1)]=(char)(src.length()-k-1);\r
63                 skip[tc_ & (MAX_CHAR-1)]=(char)(src.length()-k-1);\r
64             } else\r
65                 skip[x_ & (MAX_CHAR-1)] = (char)(src.length()-k-1);\r
66         }\r
67 \r
68         // This trick can be found in the July issue of\r
69         // C-T magazine.  This makes the method a type of\r
70         // "T-search."\r
71         jump_ahead = src.length()-1;\r
72         for(int k=0;k<src.length()-1;k++) {\r
73             char y=src.charAt(sm1-k-1);\r
74             if(exact(y)) {\r
75                 jump_ahead = k;\r
76                 break;\r
77             }\r
78         }\r
79     }\r
80     /** Set to true if you only want to compare two of the\r
81         characters in the String. */\r
82     final public int searchRegion(String s,int start,int end) {\r
83         return find(s,start,end);\r
84     }\r
85     final public int searchFrom(String s,int start) {\r
86         return find(s,start,s.length());\r
87     }\r
88     final public int search(String s) { return find(s,0,s.length()); }\r
89     public int find(String s,int start,int end) {\r
90         start += offset+sm1;\r
91         int vend = min(s.length()-1,end+sm1+offset),k;\r
92         int vend1 = vend-jump_ahead;\r
93         if(ign) {\r
94             for(k=start; k <= vend1;k += skip[s.charAt(k) & (MAX_CHAR-1)] ) {\r
95                 // table look-up is expensive, avoid it if possible\r
96                 if( anyc(s.charAt(k)) ) {\r
97                     if(CaseMgr.regionMatches(src,ign,0,s,k-sm1,sm1))\r
98                         return k-sm1-offset;\r
99                     k += jump_ahead;\r
100                 }\r
101             }\r
102             for(; k <= vend;k += skip[s.charAt(k) & (MAX_CHAR-1)] ) {\r
103                 // table look-up is expensive, avoid it if possible\r
104                 if( anyc(s.charAt(k)) ) {\r
105                     if(CaseMgr.regionMatches(src,ign,0,s,k-sm1,sm1))\r
106                         return k-sm1-offset;\r
107                     k += jump_ahead;\r
108                     if(k > vend) return -1;\r
109                 }\r
110             }\r
111         } else {\r
112             for(k=start; k <= vend1;k += skip[s.charAt(k) & (MAX_CHAR-1)] ) {\r
113                 // table look-up is expensive, avoid it if possible\r
114                 if( x==s.charAt(k) ) {\r
115                     //if(src.regionMatches(0,s,k-sm1,sm1))\r
116                     if(CaseMgr.regionMatches(src,false,0,s,k-sm1,sm1))\r
117                         return k-sm1-offset;\r
118                     k += jump_ahead;\r
119                 }\r
120             }\r
121             for(; k <= vend;k += skip[s.charAt(k) & (MAX_CHAR-1)] ) {\r
122                 // table look-up is expensive, avoid it if possible\r
123                 if( x==s.charAt(k) ) {\r
124                     //if(src.regionMatches(0,s,k-sm1,sm1))\r
125                     if(CaseMgr.regionMatches(src,false,0,s,k-sm1,sm1))\r
126                         return k-sm1-offset;\r
127                     k += jump_ahead;\r
128                     if(k > vend) return -1;\r
129                 }\r
130             }\r
131         }\r
132 \r
133         return -1;\r
134     }\r
135     public int find(StringLike s,int start,int end) {\r
136         if(s instanceof StringWrap)\r
137           return find(s.toString(),start,end);\r
138         start += offset+sm1;\r
139         int vend = min(s.length()-1,end+sm1+offset),k;\r
140         int vend1 = vend-jump_ahead;\r
141         if(ign) {\r
142             for(k=start; k <= vend1;k += skip[s.charAt(k) & (MAX_CHAR-1)] ) {\r
143                 // table look-up is expensive, avoid it if possible\r
144                 if( anyc(s.charAt(k)) ) {\r
145                     if(CaseMgr.regionMatches(src,ign,0,s,k-sm1,sm1))\r
146                         return k-sm1-offset;\r
147                     k += jump_ahead;\r
148                 }\r
149             }\r
150             for(; k <= vend;k += skip[s.charAt(k) & (MAX_CHAR-1)] ) {\r
151                 // table look-up is expensive, avoid it if possible\r
152                 if( anyc(s.charAt(k)) ) {\r
153                     if(CaseMgr.regionMatches(src,ign,0,s,k-sm1,sm1))\r
154                         return k-sm1-offset;\r
155                     k += jump_ahead;\r
156                     if(k > vend) return -1;\r
157                 }\r
158             }\r
159         } else {\r
160             for(k=start; k <= vend1;k += skip[s.charAt(k) & (MAX_CHAR-1)] ) {\r
161                 // table look-up is expensive, avoid it if possible\r
162                 if( x==s.charAt(k) ) {\r
163                     //if(src.regionMatches(0,s,k-sm1,sm1))\r
164                     if(CaseMgr.regionMatches(src,false,0,s,k-sm1,sm1))\r
165                         return k-sm1-offset;\r
166                     k += jump_ahead;\r
167                 }\r
168             }\r
169             for(; k <= vend;k += skip[s.charAt(k) & (MAX_CHAR-1)] ) {\r
170                 // table look-up is expensive, avoid it if possible\r
171                 if( x==s.charAt(k) ) {\r
172                     //if(src.regionMatches(0,s,k-sm1,sm1))\r
173                     if(CaseMgr.regionMatches(src,false,0,s,k-sm1,sm1))\r
174                         return k-sm1-offset;\r
175                     k += jump_ahead;\r
176                     if(k > vend) return -1;\r
177                 }\r
178             }\r
179         }\r
180 \r
181         return -1;\r
182     }\r
183 }\r