286N/A/*
286N/A * reserved comment block
286N/A * DO NOT REMOVE OR ALTER!
286N/A */
286N/A/*
286N/A * Copyright 1999-2002,2004 The Apache Software Foundation.
286N/A *
286N/A * Licensed under the Apache License, Version 2.0 (the "License");
286N/A * you may not use this file except in compliance with the License.
286N/A * You may obtain a copy of the License at
286N/A *
286N/A * http://www.apache.org/licenses/LICENSE-2.0
286N/A *
286N/A * Unless required by applicable law or agreed to in writing, software
286N/A * distributed under the License is distributed on an "AS IS" BASIS,
286N/A * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
286N/A * See the License for the specific language governing permissions and
286N/A * limitations under the License.
286N/A */
286N/A
286N/Apackage com.sun.org.apache.xerces.internal.impl.xpath.regex;
286N/A
286N/Aimport java.text.CharacterIterator;
286N/A
286N/A/**
286N/A * Boyer-Moore searcher.
286N/A *
286N/A * @xerces.internal
286N/A *
286N/A */
286N/Apublic class BMPattern {
286N/A char[] pattern;
286N/A int[] shiftTable;
286N/A boolean ignoreCase;
286N/A
286N/A public BMPattern(String pat, boolean ignoreCase) {
286N/A this(pat, 256, ignoreCase);
286N/A }
286N/A
286N/A public BMPattern(String pat, int tableSize, boolean ignoreCase) {
286N/A this.pattern = pat.toCharArray();
286N/A this.shiftTable = new int[tableSize];
286N/A this.ignoreCase = ignoreCase;
286N/A
286N/A int length = pattern.length;
286N/A for (int i = 0; i < this.shiftTable.length; i ++)
286N/A this.shiftTable[i] = length;
286N/A
286N/A for (int i = 0; i < length; i ++) {
286N/A char ch = this.pattern[i];
286N/A int diff = length-i-1;
286N/A int index = ch % this.shiftTable.length;
286N/A if (diff < this.shiftTable[index])
286N/A this.shiftTable[index] = diff;
286N/A if (this.ignoreCase) {
286N/A ch = Character.toUpperCase(ch);
286N/A index = ch % this.shiftTable.length;
286N/A if (diff < this.shiftTable[index])
286N/A this.shiftTable[index] = diff;
286N/A ch = Character.toLowerCase(ch);
286N/A index = ch % this.shiftTable.length;
286N/A if (diff < this.shiftTable[index])
286N/A this.shiftTable[index] = diff;
286N/A }
286N/A }
286N/A }
286N/A
286N/A /**
286N/A *
286N/A * @return -1 if <var>iterator</var> does not contain this pattern.
286N/A */
286N/A public int matches(CharacterIterator iterator, int start, int limit) {
286N/A if (this.ignoreCase) return this.matchesIgnoreCase(iterator, start, limit);
286N/A int plength = this.pattern.length;
286N/A if (plength == 0) return start;
286N/A int index = start+plength;
286N/A while (index <= limit) {
286N/A int pindex = plength;
286N/A int nindex = index+1;
286N/A char ch;
286N/A do {
286N/A if ((ch = iterator.setIndex(--index)) != this.pattern[--pindex])
286N/A break;
286N/A if (pindex == 0)
286N/A return index;
286N/A } while (pindex > 0);
286N/A index += this.shiftTable[ch % this.shiftTable.length]+1;
286N/A if (index < nindex) index = nindex;
286N/A }
286N/A return -1;
286N/A }
286N/A
286N/A /**
286N/A *
286N/A * @return -1 if <var>str</var> does not contain this pattern.
286N/A */
286N/A public int matches(String str, int start, int limit) {
286N/A if (this.ignoreCase) return this.matchesIgnoreCase(str, start, limit);
286N/A int plength = this.pattern.length;
286N/A if (plength == 0) return start;
286N/A int index = start+plength;
286N/A while (index <= limit) {
286N/A //System.err.println("Starts at "+index);
286N/A int pindex = plength;
286N/A int nindex = index+1;
286N/A char ch;
286N/A do {
286N/A if ((ch = str.charAt(--index)) != this.pattern[--pindex])
286N/A break;
286N/A if (pindex == 0)
286N/A return index;
286N/A } while (pindex > 0);
286N/A index += this.shiftTable[ch % this.shiftTable.length]+1;
286N/A if (index < nindex) index = nindex;
286N/A }
286N/A return -1;
286N/A }
286N/A /**
286N/A *
286N/A * @return -1 if <var>chars</char> does not contain this pattern.
286N/A */
286N/A public int matches(char[] chars, int start, int limit) {
286N/A if (this.ignoreCase) return this.matchesIgnoreCase(chars, start, limit);
286N/A int plength = this.pattern.length;
286N/A if (plength == 0) return start;
286N/A int index = start+plength;
286N/A while (index <= limit) {
286N/A //System.err.println("Starts at "+index);
286N/A int pindex = plength;
286N/A int nindex = index+1;
286N/A char ch;
286N/A do {
286N/A if ((ch = chars[--index]) != this.pattern[--pindex])
286N/A break;
286N/A if (pindex == 0)
286N/A return index;
286N/A } while (pindex > 0);
286N/A index += this.shiftTable[ch % this.shiftTable.length]+1;
286N/A if (index < nindex) index = nindex;
286N/A }
286N/A return -1;
286N/A }
286N/A
286N/A int matchesIgnoreCase(CharacterIterator iterator, int start, int limit) {
286N/A int plength = this.pattern.length;
286N/A if (plength == 0) return start;
286N/A int index = start+plength;
286N/A while (index <= limit) {
286N/A int pindex = plength;
286N/A int nindex = index+1;
286N/A char ch;
286N/A do {
286N/A char ch1 = ch = iterator.setIndex(--index);
286N/A char ch2 = this.pattern[--pindex];
286N/A if (ch1 != ch2) {
286N/A ch1 = Character.toUpperCase(ch1);
286N/A ch2 = Character.toUpperCase(ch2);
286N/A if (ch1 != ch2 && Character.toLowerCase(ch1) != Character.toLowerCase(ch2))
286N/A break;
286N/A }
286N/A if (pindex == 0)
286N/A return index;
286N/A } while (pindex > 0);
286N/A index += this.shiftTable[ch % this.shiftTable.length]+1;
286N/A if (index < nindex) index = nindex;
286N/A }
286N/A return -1;
286N/A }
286N/A
286N/A int matchesIgnoreCase(String text, int start, int limit) {
286N/A int plength = this.pattern.length;
286N/A if (plength == 0) return start;
286N/A int index = start+plength;
286N/A while (index <= limit) {
286N/A int pindex = plength;
286N/A int nindex = index+1;
286N/A char ch;
286N/A do {
286N/A char ch1 = ch = text.charAt(--index);
286N/A char ch2 = this.pattern[--pindex];
286N/A if (ch1 != ch2) {
286N/A ch1 = Character.toUpperCase(ch1);
286N/A ch2 = Character.toUpperCase(ch2);
286N/A if (ch1 != ch2 && Character.toLowerCase(ch1) != Character.toLowerCase(ch2))
286N/A break;
286N/A }
286N/A if (pindex == 0)
286N/A return index;
286N/A } while (pindex > 0);
286N/A index += this.shiftTable[ch % this.shiftTable.length]+1;
286N/A if (index < nindex) index = nindex;
286N/A }
286N/A return -1;
286N/A }
286N/A int matchesIgnoreCase(char[] chars, int start, int limit) {
286N/A int plength = this.pattern.length;
286N/A if (plength == 0) return start;
286N/A int index = start+plength;
286N/A while (index <= limit) {
286N/A int pindex = plength;
286N/A int nindex = index+1;
286N/A char ch;
286N/A do {
286N/A char ch1 = ch = chars[--index];
286N/A char ch2 = this.pattern[--pindex];
286N/A if (ch1 != ch2) {
286N/A ch1 = Character.toUpperCase(ch1);
286N/A ch2 = Character.toUpperCase(ch2);
286N/A if (ch1 != ch2 && Character.toLowerCase(ch1) != Character.toLowerCase(ch2))
286N/A break;
286N/A }
286N/A if (pindex == 0)
286N/A return index;
286N/A } while (pindex > 0);
286N/A index += this.shiftTable[ch % this.shiftTable.length]+1;
286N/A if (index < nindex) index = nindex;
286N/A }
286N/A return -1;
286N/A }
286N/A
286N/A /*
286N/A public static void main(String[] argv) {
286N/A try {
286N/A int[] shiftTable = new int[256];
286N/A initializeBoyerMoore(argv[0], shiftTable, true);
286N/A int o = -1;
286N/A CharacterIterator ite = new java.text.StringCharacterIterator(argv[1]);
286N/A long start = System.currentTimeMillis();
286N/A //for (int i = 0; i < 10000; i ++)
286N/A o = searchIgnoreCasesWithBoyerMoore(ite, 0, argv[0], shiftTable);
286N/A start = System.currentTimeMillis()-start;
286N/A System.out.println("Result: "+o+", Elapsed: "+start);
286N/A } catch (Exception ex) {
286N/A ex.printStackTrace();
286N/A }
286N/A }*/
286N/A}