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