Source code: org/media/mn8/util/SimpleExpression.java
1 /*
2 * $COPYRIGHT$
3 * $Id: SimpleExpression.java,v 1.28 2002/03/22 18:38:24 atech Exp $
4 *
5 * Date Author Changes
6 * Apr 08 2001 Remus Pereni Created
7 */
8 package org.media.mn8.util;
9
10 import java.util.Vector;
11 import java.util.StringTokenizer;
12 import java.util.Collection;
13
14 /**
15 * The SimpleExpression class implements a simple expression parser.
16 * The only operators of a simple expression are:
17 * <ul>
18 * <li><b>*</b> - match everything, like the "." in regular
19 * expressions</li>
20 * <li><b>#</b> - selects everything</li>
21 * </ul>
22 * It performs only two functions:
23 * <ul>
24 * <li><b>select</b> -selects all the apparence of the strings marked
25 * with the select ("#") operator</li>
26 * <li><b>match</b> - verifies if a string matches the pattern specified
27 * using normal characters and the two operators.
28 * </ul>
29 * It is intended as a simple replacement for regular expression in the case
30 * of simple expressions.
31 * @author <a href="mailto:remus@nolimits.ro">Remus Pereni</a>
32 * @version $Revision: 1.28 $ $Date: 2002/03/22 18:38:24 $
33 * @see String
34 */
35 public class SimpleExpression {
36
37 private static final String _MATCH_ALL = "*";
38 private static final String _SELECT_ALL = "#";
39
40 /**
41 * Selects a collection of strings from the target using as mask the pattern
42 * and the two operators "#" and "*".
43 * @param target The string to be matched
44 * @param pattern The pattern
45 * @return A collection (Vector) of string arrays containing the selected
46 * strings as specified through the pattern or null of none find or
47 * specified.
48 * @see java.util.Collection
49 * @see java.util.Vector
50 */
51 public static Collection select (String target, String pattern) {
52 Vector selection = null;
53 int pattern_index = 0;
54 int target_index = 0;
55 String[] pattern_tokens = makeTokens (pattern);
56 String[] current_selection = new String [ operatorOccurences ( pattern, _SELECT_ALL) ];
57 int la1_index;
58 int select_op_index;
59 boolean failed = false;
60 target = convert( target );
61
62 if (!contains (target, pattern)) return selection;
63
64 outer:
65 while (target_index < target.length()) {
66
67 for (pattern_index =0, select_op_index=0;
68 pattern_index < pattern_tokens.length;
69 pattern_index++) {
70
71 if ( pattern_tokens[pattern_index].equals( _MATCH_ALL ) ) {
72
73 if ( pattern_index + 1 < pattern_tokens.length ) {
74 la1_index = lookAhead ( pattern_tokens[pattern_index + 1],
75 target,
76 target_index);
77 if ( la1_index != -1 ){
78 target_index = la1_index + pattern_tokens[pattern_index + 1].length();
79 pattern_index ++;
80 }
81 else {
82 target_index = target.length();
83 /* there is another pattern token, yet not to be found in
84 in target */
85 failed = true;
86 break;
87 }
88 }
89 else break;
90
91 }
92
93 else if ( pattern_tokens[pattern_index].equals( _SELECT_ALL ) ) {
94
95 if ( pattern_index + 1 < pattern_tokens.length ) {
96 la1_index = lookAhead ( pattern_tokens[pattern_index + 1],
97 target,
98 target_index);
99 if ( la1_index != -1 ) {
100 current_selection [select_op_index] = target.substring( target_index,
101 la1_index );
102 target_index = la1_index + pattern_tokens[pattern_index + 1].length();
103 select_op_index++;
104 pattern_index = pattern_index + 1;
105 }
106 else {
107 target_index = target.length();
108 /* there is another pattern token, yet not to be found in
109 in target */
110 failed = true;
111 break;
112 }
113 }
114 else {
115 current_selection [select_op_index] = target.substring( target_index );
116 target_index = target.length();
117 break;
118 }
119 }
120
121 else {
122 if ( target.startsWith(pattern_tokens[pattern_index], target_index) ) {
123 target_index += pattern_tokens[pattern_index].length();
124 }
125 else {
126 failed = true;
127 break outer;
128 }
129 }
130 }
131
132 if ( operatorOccurences ( pattern, _SELECT_ALL ) > 0 &&
133 !failed &&
134 current_selection[0] != null ) {
135 if ( selection== null ) selection = new Vector();
136 selection.add( current_selection );
137 current_selection = new String [ operatorOccurences ( pattern, _SELECT_ALL) ];
138 }
139 }
140
141 if ( target_index != target.length() ) {
142 // not all the target characters where parsed, that means that either
143 // the pattern is not vell specified or it does not match
144 selection = null;
145 }
146
147 return selection;
148 }
149
150
151 /**
152 * Specifies if a pattern matches the target string or not.
153 * @param target The string to be matched
154 * @param pattern The pattern
155 * @return True if the pattern is present in the target, false otherway.
156 */
157 public static boolean match (String target, String pattern) {
158 boolean matched = false;
159 int pattern_index = 0;
160 int target_index = 0;
161 String[] pattern_tokens = makeTokens (pattern);
162 int crt_target_index =0;
163 target = convert( target );
164
165 if ( !isValidPattern (pattern) ) {
166 throw new RuntimeException ( "Indetermination! There seems to be two consecutive " +
167 "operators in your pattern (\"" + pattern + "\") , please revise it.");
168 }
169
170 // if simple expression, whithout operators looking for equality
171 if ( pattern_tokens.length == 1 && !isOperator( pattern_tokens[0] ) )
172 return target.equals( pattern );
173
174 while ( !matched && target_index < target.length() ) {
175 if ( isOperator(pattern_tokens[pattern_index]) ) pattern_index ++;
176 else {
177 crt_target_index = target.indexOf( pattern_tokens[pattern_index], target_index );
178 if (crt_target_index == -1) return false;
179 else {
180 target_index = crt_target_index + pattern_tokens[pattern_index].length();
181 pattern_index ++;
182 }
183 }
184 if ( pattern_index >= pattern_tokens.length ) matched = true;
185 }
186
187 if ( ( isStartsWithMatch( target, pattern_tokens) || isStartsOpened( pattern_tokens, pattern_index) ) &&
188 matched &&
189 (target_index == target.length() || isOpenEnded(pattern_tokens, pattern_index) ) ) return true;
190 else return false;
191 }
192
193 private static boolean isOpenEnded( String[] tokens, int index ) {
194 if ( tokens[index-1].equals(_MATCH_ALL) || tokens[index-1].equals(_SELECT_ALL) ) return true;
195 else return false;
196 }
197
198
199 private static boolean isStartsWithMatch( String target, String[] tokens ) {
200 if ( target.startsWith( tokens[0] ) ) return true;
201 else return false;
202 }
203
204
205 private static boolean isStartsOpened( String[] tokens, int index ) {
206 if ( tokens[0].equals(_MATCH_ALL) || tokens[0].equals(_SELECT_ALL) ) return true;
207 else return false;
208 }
209
210
211 private static String convert( String target ) {
212 int cnt = 0;
213 String result = "";
214 if ( target.indexOf("\n\r") != -1 ) {
215 StringTokenizer tokenizer = new StringTokenizer ( target, "\n\r" );
216 while ( tokenizer.hasMoreTokens() ) {
217 result += tokenizer.nextToken() +"\n";
218 }
219 return result;
220 }
221 else return target;
222 }
223
224 public static boolean contains (String target, String pattern) {
225 boolean matched = false;
226 int pattern_index = 0;
227 int target_index = 0;
228 String[] pattern_tokens = makeTokens (pattern);
229 int crt_target_index =0;
230 target = convert( target );
231
232 if ( !isValidPattern (pattern) ) {
233 throw new RuntimeException ( "Indetermination! There seems to be two consecutive " +
234 "operators in your pattern (\"" + pattern + "\") , please revise it.");
235 }
236
237 // if simple expression, whithout operators looking for equality
238 if ( pattern_tokens.length == 1 && !isOperator( pattern_tokens[0] ) )
239 return target.equals( pattern );
240
241 while ( !matched && target_index < target.length() ) {
242 if ( isOperator(pattern_tokens[pattern_index]) ) {
243 pattern_index ++;
244 }else {
245 crt_target_index = target.indexOf( pattern_tokens[pattern_index], target_index );
246 if (crt_target_index == -1) {
247 return false;
248 } else {
249 target_index = crt_target_index + pattern_tokens[pattern_index].length();
250 pattern_index ++;
251 }
252 }
253
254 if ( pattern_index >= pattern_tokens.length )
255 matched = true;
256 }
257 return matched;
258 }
259
260
261 /**
262 * Tries to find the token in the target string starting with the
263 * targetIndex position.
264 * @param token The token to be looked for.
265 * @param target The string where we look for the token.
266 * @param targetIndex the position in the target where we begin the search.
267 * @return The position of the first found token in the target or -1 in
268 * case was not found.
269 */
270 protected static int lookAhead (String token, String target, int targetIndex) {
271 return target.indexOf(token, targetIndex);
272 }
273
274
275 protected static String[] makeTokens (String pattern) {
276 String[] result= null;
277 int tokens = operatorOccurences (pattern, _MATCH_ALL)
278 + operatorOccurences (pattern, _SELECT_ALL);
279
280 if ( tokens == 0 ) {
281 result = new String [1];
282 result[0] = pattern;
283 } else {
284 int cnt = 0;
285 StringTokenizer tokenizer = new StringTokenizer ( pattern,
286 _MATCH_ALL + _SELECT_ALL,
287 true);
288 result = new String [tokenizer.countTokens()];
289 while ( tokenizer.hasMoreTokens() ) {
290 result[cnt] = tokenizer.nextToken();
291 cnt++;
292 }
293 }
294 return result;
295 }
296
297
298 protected static int operatorOccurences (String target, String operator) {
299 int currentIndex = 0;
300 int occurence=0;
301
302 while ( currentIndex != -1 ){
303 currentIndex = target.indexOf (operator, currentIndex) ;
304 if ( currentIndex != -1){
305 occurence ++;
306 currentIndex ++;
307 }
308 }
309 return occurence;
310 }
311
312
313 protected static boolean isOperator (String target) {
314 if ( target.equals ( _MATCH_ALL ) ||
315 target.equals ( _SELECT_ALL ) )
316 return true;
317 else
318 return false;
319 }
320
321
322 private static boolean isValidPattern ( String pattern ) {
323 if ( pattern.indexOf( _MATCH_ALL + _SELECT_ALL ) != -1 ||
324 pattern.indexOf( _SELECT_ALL + _MATCH_ALL ) != -1 ||
325 pattern.indexOf( _MATCH_ALL + _MATCH_ALL ) != -1 ||
326 pattern.indexOf( _SELECT_ALL + _SELECT_ALL ) != -1 ) return false;
327 else return true;
328 }
329
330 }