View Javadoc

1   /*
2    * Copyright 2006-2007 the original author or authors.
3    *
4    * Licensed under the Apache License, Version 2.0 (the "License");
5    * you may not use this file except in compliance with the License.
6    * You may obtain a copy of the License at
7    *
8    *      http://www.apache.org/licenses/LICENSE-2.0
9    *
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS,
12   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   * See the License for the specific language governing permissions and
14   * limitations under the License.
15   */
16  package org.springframework.batch.support;
17  
18  import java.util.ArrayList;
19  import java.util.Collections;
20  import java.util.Comparator;
21  import java.util.HashMap;
22  import java.util.List;
23  import java.util.Map;
24  
25  import org.springframework.util.Assert;
26  
27  /**
28   * @author Dave Syer
29   * @author Dan Garrette
30   */
31  public class PatternMatcher<S> {
32  
33  	private Map<String, S> map = new HashMap<String, S>();
34  	private List<String> sorted = new ArrayList<String>();
35  
36  	/**
37  	 * Initialize a new {@link PatternMatcher} with a map of patterns to values
38  	 * @param map a map from String patterns to values
39  	 */
40  	public PatternMatcher(Map<String, S> map) {
41  		super();
42  		this.map = map;
43  		// Sort keys to start with the most specific
44  		sorted = new ArrayList<String>(map.keySet());
45  		Collections.sort(sorted, new Comparator<String>() {
46              @Override
47  			public int compare(String o1, String o2) {
48  				String s1 = o1; // .replace('?', '{');
49  				String s2 = o2; // .replace('*', '}');
50  				return s2.compareTo(s1);
51  			}
52  		});
53  	}
54  
55  	/**
56  	 * Lifted from AntPathMatcher in Spring Core. Tests whether or not a string
57  	 * matches against a pattern. The pattern may contain two special
58  	 * characters:<br>
59  	 * '*' means zero or more characters<br>
60  	 * '?' means one and only one character
61  	 * 
62  	 * @param pattern pattern to match against. Must not be <code>null</code>.
63  	 * @param str string which must be matched against the pattern. Must not be
64  	 * <code>null</code>.
65  	 * @return <code>true</code> if the string matches against the pattern, or
66  	 * <code>false</code> otherwise.
67  	 */
68  	public static boolean match(String pattern, String str) {
69  		char[] patArr = pattern.toCharArray();
70  		char[] strArr = str.toCharArray();
71  		int patIdxStart = 0;
72  		int patIdxEnd = patArr.length - 1;
73  		int strIdxStart = 0;
74  		int strIdxEnd = strArr.length - 1;
75  		char ch;
76  
77  		boolean containsStar = pattern.contains("*");
78  
79  		if (!containsStar) {
80  			// No '*'s, so we make a shortcut
81  			if (patIdxEnd != strIdxEnd) {
82  				return false; // Pattern and string do not have the same size
83  			}
84  			for (int i = 0; i <= patIdxEnd; i++) {
85  				ch = patArr[i];
86  				if (ch != '?') {
87  					if (ch != strArr[i]) {
88  						return false;// Character mismatch
89  					}
90  				}
91  			}
92  			return true; // String matches against pattern
93  		}
94  
95  		if (patIdxEnd == 0) {
96  			return true; // Pattern contains only '*', which matches anything
97  		}
98  
99  		// Process characters before first star
100 		while ((ch = patArr[patIdxStart]) != '*' && strIdxStart <= strIdxEnd) {
101 			if (ch != '?') {
102 				if (ch != strArr[strIdxStart]) {
103 					return false;// Character mismatch
104 				}
105 			}
106 			patIdxStart++;
107 			strIdxStart++;
108 		}
109 		if (strIdxStart > strIdxEnd) {
110 			// All characters in the string are used. Check if only '*'s are
111 			// left in the pattern. If so, we succeeded. Otherwise failure.
112 			for (int i = patIdxStart; i <= patIdxEnd; i++) {
113 				if (patArr[i] != '*') {
114 					return false;
115 				}
116 			}
117 			return true;
118 		}
119 
120 		// Process characters after last star
121 		while ((ch = patArr[patIdxEnd]) != '*' && strIdxStart <= strIdxEnd) {
122 			if (ch != '?') {
123 				if (ch != strArr[strIdxEnd]) {
124 					return false;// Character mismatch
125 				}
126 			}
127 			patIdxEnd--;
128 			strIdxEnd--;
129 		}
130 		if (strIdxStart > strIdxEnd) {
131 			// All characters in the string are used. Check if only '*'s are
132 			// left in the pattern. If so, we succeeded. Otherwise failure.
133 			for (int i = patIdxStart; i <= patIdxEnd; i++) {
134 				if (patArr[i] != '*') {
135 					return false;
136 				}
137 			}
138 			return true;
139 		}
140 
141 		// process pattern between stars. padIdxStart and patIdxEnd point
142 		// always to a '*'.
143 		while (patIdxStart != patIdxEnd && strIdxStart <= strIdxEnd) {
144 			int patIdxTmp = -1;
145 			for (int i = patIdxStart + 1; i <= patIdxEnd; i++) {
146 				if (patArr[i] == '*') {
147 					patIdxTmp = i;
148 					break;
149 				}
150 			}
151 			if (patIdxTmp == patIdxStart + 1) {
152 				// Two stars next to each other, skip the first one.
153 				patIdxStart++;
154 				continue;
155 			}
156 			// Find the pattern between padIdxStart & padIdxTmp in str between
157 			// strIdxStart & strIdxEnd
158 			int patLength = (patIdxTmp - patIdxStart - 1);
159 			int strLength = (strIdxEnd - strIdxStart + 1);
160 			int foundIdx = -1;
161 			strLoop: for (int i = 0; i <= strLength - patLength; i++) {
162 				for (int j = 0; j < patLength; j++) {
163 					ch = patArr[patIdxStart + j + 1];
164 					if (ch != '?') {
165 						if (ch != strArr[strIdxStart + i + j]) {
166 							continue strLoop;
167 						}
168 					}
169 				}
170 
171 				foundIdx = strIdxStart + i;
172 				break;
173 			}
174 
175 			if (foundIdx == -1) {
176 				return false;
177 			}
178 
179 			patIdxStart = patIdxTmp;
180 			strIdxStart = foundIdx + patLength;
181 		}
182 
183 		// All characters in the string are used. Check if only '*'s are left
184 		// in the pattern. If so, we succeeded. Otherwise failure.
185 		for (int i = patIdxStart; i <= patIdxEnd; i++) {
186 			if (patArr[i] != '*') {
187 				return false;
188 			}
189 		}
190 
191 		return true;
192 	}
193 
194 	/**
195 	 * <p>
196 	 * This method takes a String key and a map from Strings to values of any
197 	 * type. During processing, the method will identify the most specific key
198 	 * in the map that matches the line. Once the correct is identified, its
199 	 * value is returned. Note that if the map contains the wildcard string "*"
200 	 * as a key, then it will serve as the "default" case, matching every line
201 	 * that does not match anything else.
202 	 * 
203 	 * <p>
204 	 * If no matching prefix is found, a {@link IllegalStateException} will be
205 	 * thrown.
206 	 * 
207 	 * <p>
208 	 * Null keys are not allowed in the map.
209 	 * 
210 	 * @param line An input string
211 	 * @return the value whose prefix matches the given line
212 	 */
213 	public S match(String line) {
214 
215 		S value = null;
216 		Assert.notNull(line, "A non-null key must be provided to match against.");
217 
218 		for (String key : sorted) {
219 			if (PatternMatcher.match(key, line)) {
220 				value = map.get(key);
221 				break;
222 			}
223 		}
224 
225 		if (value == null) {
226 			throw new IllegalStateException("Could not find a matching pattern for key=[" + line + "]");
227 		}
228 		return value;
229 
230 	}
231 
232 }