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