KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > sun > org > apache > xerces > internal > impl > xpath > regex > BMPattern


1 /*
2  * The Apache Software License, Version 1.1
3  *
4  *
5  * Copyright (c) 1999-2002 The Apache Software Foundation. All rights
6  * reserved.
7  *
8  * Redistribution and use in source and binary forms, with or without
9  * modification, are permitted provided that the following conditions
10  * are met:
11  *
12  * 1. Redistributions of source code must retain the above copyright
13  * notice, this list of conditions and the following disclaimer.
14  *
15  * 2. Redistributions in binary form must reproduce the above copyright
16  * notice, this list of conditions and the following disclaimer in
17  * the documentation and/or other materials provided with the
18  * distribution.
19  *
20  * 3. The end-user documentation included with the redistribution,
21  * if any, must include the following acknowledgment:
22  * "This product includes software developed by the
23  * Apache Software Foundation (http://www.apache.org/)."
24  * Alternately, this acknowledgment may appear in the software itself,
25  * if and wherever such third-party acknowledgments normally appear.
26  *
27  * 4. The names "Xerces" and "Apache Software Foundation" must
28  * not be used to endorse or promote products derived from this
29  * software without prior written permission. For written
30  * permission, please contact apache@apache.org.
31  *
32  * 5. Products derived from this software may not be called "Apache",
33  * nor may "Apache" appear in their name, without prior written
34  * permission of the Apache Software Foundation.
35  *
36  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
37  * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
38  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
39  * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
40  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
41  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
42  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
43  * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
44  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
45  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
46  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
47  * SUCH DAMAGE.
48  * ====================================================================
49  *
50  * This software consists of voluntary contributions made by many
51  * individuals on behalf of the Apache Software Foundation and was
52  * originally based on software copyright (c) 1999, International
53  * Business Machines, Inc., http://www.apache.org. For more
54  * information on the Apache Software Foundation, please see
55  * <http://www.apache.org/>.
56  */

57
58 package com.sun.org.apache.xerces.internal.impl.xpath.regex;
59
60 import java.text.CharacterIterator JavaDoc;
61
62 /**
63  * Boyer-Moore searcher.
64  *
65  * @version $Id: BMPattern.java,v 1.3 2002/08/09 15:18:17 neilg Exp $
66  */

67 public class BMPattern {
68     char[] pattern;
69     int[] shiftTable;
70     boolean ignoreCase;
71
72     public BMPattern(String JavaDoc pat, boolean ignoreCase) {
73         this(pat, 256, ignoreCase);
74     }
75
76     public BMPattern(String JavaDoc pat, int tableSize, boolean ignoreCase) {
77         this.pattern = pat.toCharArray();
78         this.shiftTable = new int[tableSize];
79         this.ignoreCase = ignoreCase;
80
81         int length = pattern.length;
82         for (int i = 0; i < this.shiftTable.length; i ++)
83             this.shiftTable[i] = length;
84
85         for (int i = 0; i < length; i ++) {
86             char ch = this.pattern[i];
87             int diff = length-i-1;
88             int index = ch % this.shiftTable.length;
89             if (diff < this.shiftTable[index])
90                 this.shiftTable[index] = diff;
91             if (this.ignoreCase) {
92                 ch = Character.toUpperCase(ch);
93                 index = ch % this.shiftTable.length;
94                 if (diff < this.shiftTable[index])
95                     this.shiftTable[index] = diff;
96                 ch = Character.toLowerCase(ch);
97                 index = ch % this.shiftTable.length;
98                 if (diff < this.shiftTable[index])
99                     this.shiftTable[index] = diff;
100             }
101         }
102     }
103
104     /**
105      *
106      * @return -1 if <var>iterator</var> does not contain this pattern.
107      */

108     public int matches(CharacterIterator JavaDoc iterator, int start, int limit) {
109         if (this.ignoreCase) return this.matchesIgnoreCase(iterator, start, limit);
110         int plength = this.pattern.length;
111         if (plength == 0) return start;
112         int index = start+plength;
113         while (index <= limit) {
114             int pindex = plength;
115             int nindex = index+1;
116             char ch;
117             do {
118                 if ((ch = iterator.setIndex(--index)) != this.pattern[--pindex])
119                     break;
120                 if (pindex == 0)
121                     return index;
122             } while (pindex > 0);
123             index += this.shiftTable[ch % this.shiftTable.length]+1;
124             if (index < nindex) index = nindex;
125         }
126         return -1;
127     }
128
129     /**
130      *
131      * @return -1 if <var>str</var> does not contain this pattern.
132      */

133     public int matches(String JavaDoc str, int start, int limit) {
134         if (this.ignoreCase) return this.matchesIgnoreCase(str, start, limit);
135         int plength = this.pattern.length;
136         if (plength == 0) return start;
137         int index = start+plength;
138         while (index <= limit) {
139             //System.err.println("Starts at "+index);
140
int pindex = plength;
141             int nindex = index+1;
142             char ch;
143             do {
144                 if ((ch = str.charAt(--index)) != this.pattern[--pindex])
145                     break;
146                 if (pindex == 0)
147                     return index;
148             } while (pindex > 0);
149             index += this.shiftTable[ch % this.shiftTable.length]+1;
150             if (index < nindex) index = nindex;
151         }
152         return -1;
153     }
154     /**
155      *
156      * @return -1 if <var>chars</char> does not contain this pattern.
157      */

158     public int matches(char[] chars, int start, int limit) {
159         if (this.ignoreCase) return this.matchesIgnoreCase(chars, start, limit);
160         int plength = this.pattern.length;
161         if (plength == 0) return start;
162         int index = start+plength;
163         while (index <= limit) {
164             //System.err.println("Starts at "+index);
165
int pindex = plength;
166             int nindex = index+1;
167             char ch;
168             do {
169                 if ((ch = chars[--index]) != this.pattern[--pindex])
170                     break;
171                 if (pindex == 0)
172                     return index;
173             } while (pindex > 0);
174             index += this.shiftTable[ch % this.shiftTable.length]+1;
175             if (index < nindex) index = nindex;
176         }
177         return -1;
178     }
179
180     int matchesIgnoreCase(CharacterIterator JavaDoc iterator, int start, int limit) {
181         int plength = this.pattern.length;
182         if (plength == 0) return start;
183         int index = start+plength;
184         while (index <= limit) {
185             int pindex = plength;
186             int nindex = index+1;
187             char ch;
188             do {
189                 char ch1 = ch = iterator.setIndex(--index);
190                 char ch2 = this.pattern[--pindex];
191                 if (ch1 != ch2) {
192                     ch1 = Character.toUpperCase(ch1);
193                     ch2 = Character.toUpperCase(ch2);
194                     if (ch1 != ch2 && Character.toLowerCase(ch1) != Character.toLowerCase(ch2))
195                         break;
196                 }
197                 if (pindex == 0)
198                     return index;
199             } while (pindex > 0);
200             index += this.shiftTable[ch % this.shiftTable.length]+1;
201             if (index < nindex) index = nindex;
202         }
203         return -1;
204     }
205     
206     int matchesIgnoreCase(String JavaDoc text, int start, int limit) {
207         int plength = this.pattern.length;
208         if (plength == 0) return start;
209         int index = start+plength;
210         while (index <= limit) {
211             int pindex = plength;
212             int nindex = index+1;
213             char ch;
214             do {
215                 char ch1 = ch = text.charAt(--index);
216                 char ch2 = this.pattern[--pindex];
217                 if (ch1 != ch2) {
218                     ch1 = Character.toUpperCase(ch1);
219                     ch2 = Character.toUpperCase(ch2);
220                     if (ch1 != ch2 && Character.toLowerCase(ch1) != Character.toLowerCase(ch2))
221                         break;
222                 }
223                 if (pindex == 0)
224                     return index;
225             } while (pindex > 0);
226             index += this.shiftTable[ch % this.shiftTable.length]+1;
227             if (index < nindex) index = nindex;
228         }
229         return -1;
230     }
231     int matchesIgnoreCase(char[] chars, int start, int limit) {
232         int plength = this.pattern.length;
233         if (plength == 0) return start;
234         int index = start+plength;
235         while (index <= limit) {
236             int pindex = plength;
237             int nindex = index+1;
238             char ch;
239             do {
240                 char ch1 = ch = chars[--index];
241                 char ch2 = this.pattern[--pindex];
242                 if (ch1 != ch2) {
243                     ch1 = Character.toUpperCase(ch1);
244                     ch2 = Character.toUpperCase(ch2);
245                     if (ch1 != ch2 && Character.toLowerCase(ch1) != Character.toLowerCase(ch2))
246                         break;
247                 }
248                 if (pindex == 0)
249                     return index;
250             } while (pindex > 0);
251             index += this.shiftTable[ch % this.shiftTable.length]+1;
252             if (index < nindex) index = nindex;
253         }
254         return -1;
255     }
256
257     /*
258     public static void main(String[] argv) {
259         try {
260             int[] shiftTable = new int[256];
261             initializeBoyerMoore(argv[0], shiftTable, true);
262             int o = -1;
263             CharacterIterator ite = new java.text.StringCharacterIterator(argv[1]);
264             long start = System.currentTimeMillis();
265             //for (int i = 0; i < 10000; i ++)
266                 o = searchIgnoreCasesWithBoyerMoore(ite, 0, argv[0], shiftTable);
267             start = System.currentTimeMillis()-start;
268             System.out.println("Result: "+o+", Elapsed: "+start);
269         } catch (Exception ex) {
270             ex.printStackTrace();
271         }
272     }*/

273 }
274
275
Popular Tags