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