Source code: org/apache/xmlbeans/impl/regex/BMPattern.java
1 /* Copyright 2004 The Apache Software Foundation
2 *
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15
16 package org.apache.xmlbeans.impl.regex;
17
18 import java.text.CharacterIterator;
19
20 /**
21 * Boyer-Moore searcher.
22 */
23 public class BMPattern {
24 char[] pattern;
25 int[] shiftTable;
26 boolean ignoreCase;
27
28 public BMPattern(String pat, boolean ignoreCase) {
29 this(pat, 256, ignoreCase);
30 }
31
32 public BMPattern(String pat, int tableSize, boolean ignoreCase) {
33 this.pattern = pat.toCharArray();
34 this.shiftTable = new int[tableSize];
35 this.ignoreCase = ignoreCase;
36
37 int length = pattern.length;
38 for (int i = 0; i < this.shiftTable.length; i ++)
39 this.shiftTable[i] = length;
40
41 for (int i = 0; i < length; i ++) {
42 char ch = this.pattern[i];
43 int diff = length-i-1;
44 int index = ch % this.shiftTable.length;
45 if (diff < this.shiftTable[index])
46 this.shiftTable[index] = diff;
47 if (this.ignoreCase) {
48 ch = Character.toUpperCase(ch);
49 index = ch % this.shiftTable.length;
50 if (diff < this.shiftTable[index])
51 this.shiftTable[index] = diff;
52 ch = Character.toLowerCase(ch);
53 index = ch % this.shiftTable.length;
54 if (diff < this.shiftTable[index])
55 this.shiftTable[index] = diff;
56 }
57 }
58 }
59
60 /**
61 *
62 * @return -1 if <var>iterator</var> does not contain this pattern.
63 */
64 public int matches(CharacterIterator iterator, int start, int limit) {
65 if (this.ignoreCase) return this.matchesIgnoreCase(iterator, start, limit);
66 int plength = this.pattern.length;
67 if (plength == 0) return start;
68 int index = start+plength;
69 while (index <= limit) {
70 int pindex = plength;
71 int nindex = index+1;
72 char ch;
73 do {
74 if ((ch = iterator.setIndex(--index)) != this.pattern[--pindex])
75 break;
76 if (pindex == 0)
77 return index;
78 } while (pindex > 0);
79 index += this.shiftTable[ch % this.shiftTable.length]+1;
80 if (index < nindex) index = nindex;
81 }
82 return -1;
83 }
84
85 /**
86 *
87 * @return -1 if <var>str</var> does not contain this pattern.
88 */
89 public int matches(String str, int start, int limit) {
90 if (this.ignoreCase) return this.matchesIgnoreCase(str, start, limit);
91 int plength = this.pattern.length;
92 if (plength == 0) return start;
93 int index = start+plength;
94 while (index <= limit) {
95 //System.err.println("Starts at "+index);
96 int pindex = plength;
97 int nindex = index+1;
98 char ch;
99 do {
100 if ((ch = str.charAt(--index)) != this.pattern[--pindex])
101 break;
102 if (pindex == 0)
103 return index;
104 } while (pindex > 0);
105 index += this.shiftTable[ch % this.shiftTable.length]+1;
106 if (index < nindex) index = nindex;
107 }
108 return -1;
109 }
110 /**
111 *
112 * @return -1 if <var>chars</char> does not contain this pattern.
113 */
114 public int matches(char[] chars, int start, int limit) {
115 if (this.ignoreCase) return this.matchesIgnoreCase(chars, start, limit);
116 int plength = this.pattern.length;
117 if (plength == 0) return start;
118 int index = start+plength;
119 while (index <= limit) {
120 //System.err.println("Starts at "+index);
121 int pindex = plength;
122 int nindex = index+1;
123 char ch;
124 do {
125 if ((ch = chars[--index]) != this.pattern[--pindex])
126 break;
127 if (pindex == 0)
128 return index;
129 } while (pindex > 0);
130 index += this.shiftTable[ch % this.shiftTable.length]+1;
131 if (index < nindex) index = nindex;
132 }
133 return -1;
134 }
135
136 int matchesIgnoreCase(CharacterIterator iterator, int start, int limit) {
137 int plength = this.pattern.length;
138 if (plength == 0) return start;
139 int index = start+plength;
140 while (index <= limit) {
141 int pindex = plength;
142 int nindex = index+1;
143 char ch;
144 do {
145 char ch1 = ch = iterator.setIndex(--index);
146 char ch2 = this.pattern[--pindex];
147 if (ch1 != ch2) {
148 ch1 = Character.toUpperCase(ch1);
149 ch2 = Character.toUpperCase(ch2);
150 if (ch1 != ch2 && Character.toLowerCase(ch1) != Character.toLowerCase(ch2))
151 break;
152 }
153 if (pindex == 0)
154 return index;
155 } while (pindex > 0);
156 index += this.shiftTable[ch % this.shiftTable.length]+1;
157 if (index < nindex) index = nindex;
158 }
159 return -1;
160 }
161
162 int matchesIgnoreCase(String text, int start, int limit) {
163 int plength = this.pattern.length;
164 if (plength == 0) return start;
165 int index = start+plength;
166 while (index <= limit) {
167 int pindex = plength;
168 int nindex = index+1;
169 char ch;
170 do {
171 char ch1 = ch = text.charAt(--index);
172 char ch2 = this.pattern[--pindex];
173 if (ch1 != ch2) {
174 ch1 = Character.toUpperCase(ch1);
175 ch2 = Character.toUpperCase(ch2);
176 if (ch1 != ch2 && Character.toLowerCase(ch1) != Character.toLowerCase(ch2))
177 break;
178 }
179 if (pindex == 0)
180 return index;
181 } while (pindex > 0);
182 index += this.shiftTable[ch % this.shiftTable.length]+1;
183 if (index < nindex) index = nindex;
184 }
185 return -1;
186 }
187 int matchesIgnoreCase(char[] chars, int start, int limit) {
188 int plength = this.pattern.length;
189 if (plength == 0) return start;
190 int index = start+plength;
191 while (index <= limit) {
192 int pindex = plength;
193 int nindex = index+1;
194 char ch;
195 do {
196 char ch1 = ch = chars[--index];
197 char ch2 = this.pattern[--pindex];
198 if (ch1 != ch2) {
199 ch1 = Character.toUpperCase(ch1);
200 ch2 = Character.toUpperCase(ch2);
201 if (ch1 != ch2 && Character.toLowerCase(ch1) != Character.toLowerCase(ch2))
202 break;
203 }
204 if (pindex == 0)
205 return index;
206 } while (pindex > 0);
207 index += this.shiftTable[ch % this.shiftTable.length]+1;
208 if (index < nindex) index = nindex;
209 }
210 return -1;
211 }
212
213 /*
214 public static void main(String[] argv) {
215 try {
216 int[] shiftTable = new int[256];
217 initializeBoyerMoore(argv[0], shiftTable, true);
218 int o = -1;
219 CharacterIterator ite = new java.text.StringCharacterIterator(argv[1]);
220 long start = System.currentTimeMillis();
221 //for (int i = 0; i < 10000; i ++)
222 o = searchIgnoreCasesWithBoyerMoore(ite, 0, argv[0], shiftTable);
223 start = System.currentTimeMillis()-start;
224 System.out.println("Result: "+o+", Elapsed: "+start);
225 } catch (Exception ex) {
226 ex.printStackTrace();
227 }
228 }*/
229 }
230