KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > columba > ristretto > parser > CharSequenceSearcher


1 /* ***** BEGIN LICENSE BLOCK *****
2  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
3  *
4  * The contents of this file are subject to the Mozilla Public License Version
5  * 1.1 (the "License"); you may not use this file except in compliance with
6  * the License. You may obtain a copy of the License at
7  * http://www.mozilla.org/MPL/
8  *
9  * Software distributed under the License is distributed on an "AS IS" basis,
10  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
11  * for the specific language governing rights and limitations under the
12  * License.
13  *
14  * The Original Code is Ristretto Mail API.
15  *
16  * The Initial Developers of the Original Code are
17  * Timo Stich and Frederik Dietz.
18  * Portions created by the Initial Developers are Copyright (C) 2004
19  * All Rights Reserved.
20  *
21  * Contributor(s):
22  *
23  * Alternatively, the contents of this file may be used under the terms of
24  * either the GNU General Public License Version 2 or later (the "GPL"), or
25  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
26  * in which case the provisions of the GPL or the LGPL are applicable instead
27  * of those above. If you wish to allow use of your version of this file only
28  * under the terms of either the GPL or the LGPL, and not to allow others to
29  * use your version of this file under the terms of the MPL, indicate your
30  * decision by deleting the provisions above and replace them with the notice
31  * and other provisions required by the GPL or the LGPL. If you do not delete
32  * the provisions above, a recipient may use your version of this file under
33  * the terms of any one of the MPL, the GPL or the LGPL.
34  *
35  * ***** END LICENSE BLOCK ***** */
36 package org.columba.ristretto.parser;
37
38 import java.util.ArrayList JavaDoc;
39 import java.util.Arrays JavaDoc;
40 import java.util.List JavaDoc;
41
42
43 /**
44  * Implementation of the Boyer-Moore search algorithm for
45  * CharSequences.
46  *
47  * @author Timo Stich <tstich@users.sourceforge.net>
48  */
49 public class CharSequenceSearcher {
50     private int[] badCharacterSkip;
51     private int[] goodSuffixSkip;
52     
53     private char[] pattern;
54     private int patternLength;
55
56     
57     /**
58      * Constructs the CharSequenceSearcher.
59      *
60      * @param pattern the pattern to search for.
61      */
62     public CharSequenceSearcher(String JavaDoc pattern) {
63         this(pattern.toCharArray());
64     }
65     
66     /**
67      * Constructs the CharSequenceSearcher.
68      *
69      * @param pattern the pattern to search for.
70      */
71     public CharSequenceSearcher(char[] pattern) {
72         badCharacterSkip = new int[256];
73
74         setPattern(pattern);
75     }
76
77     /**
78      * Sets the pattern to search for. This also
79      * resets the matcher.
80      *
81      * @param pattern the pattern to search for.
82      */
83     public void setPattern(char[] pattern) {
84         this.pattern = pattern;
85         patternLength = pattern.length;
86         goodSuffixSkip = new int[patternLength + 1];
87         
88         // init skip arrays
89 initGoodSuffixSkipArray();
90         initBadCharSkipArray();
91     }
92
93     private void initGoodSuffixSkipArray() {
94         int i,j,p;
95         int[] f = new int[patternLength + 1];
96
97         j = patternLength + 1;
98         f[patternLength] = j;
99
100         for (i = patternLength; i > 0; i--) {
101             while (j <= patternLength && pattern[i - 1] != pattern[j - 1]) {
102                 if (goodSuffixSkip[j] == 0) {
103                     goodSuffixSkip[j] = j - i;
104                 }
105                 j = f[j];
106             }
107             f[i - 1] = --j;
108         }
109
110         p = f[0];
111         for (j = 0; j <= patternLength; ++j) {
112             if (goodSuffixSkip[j] == 0) {
113                 goodSuffixSkip[j] = p;
114             }
115             if (j == p) {
116                 p = f[p];
117             }
118         }
119     }
120
121     private void initBadCharSkipArray() {
122         Arrays.fill(badCharacterSkip, patternLength);
123
124         for (int j = 0; j < patternLength - 1; j++) {
125             badCharacterSkip[pattern[j]] = patternLength - j - 1;
126         }
127     }
128
129     /**
130      * Searches the preciously set pattern in the given text.
131      * The resulting list contains the positions of the matches
132      * as Integer.
133      *
134      * @param text the text that is search in.
135      * @return a list of the positions of matches in the text.
136      */
137     public List JavaDoc match(CharSequence JavaDoc text) {
138         int i,j;
139         int textLength = text.length();
140         List JavaDoc result = new ArrayList JavaDoc();
141
142         i = 0;
143         while (i <= textLength - patternLength) {
144             for (j = patternLength - 1; j >= 0
145                     && pattern[j] == text.charAt(i + j); --j) {
146             }
147
148             if (j < 0) {
149                 result.add(new Integer JavaDoc(i));
150
151                 i += goodSuffixSkip[0];
152             } else {
153                 i += Math.max(
154                         goodSuffixSkip[j + 1],
155                         badCharacterSkip[text.charAt(i + j)] - patternLength + j + 1);
156             }
157         }
158
159         return result;
160     }
161 }
Popular Tags