001/*
002 * Copyright 2006-2007 the original author or authors.
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 *      https://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016package org.springframework.batch.support;
017
018import java.util.ArrayList;
019import java.util.Collections;
020import java.util.Comparator;
021import java.util.HashMap;
022import java.util.List;
023import java.util.Map;
024
025import org.springframework.util.Assert;
026
027/**
028 * @author Dave Syer
029 * @author Dan Garrette
030 */
031public class PatternMatcher<S> {
032
033        private Map<String, S> map = new HashMap<String, S>();
034        private List<String> sorted = new ArrayList<String>();
035
036        /**
037         * Initialize a new {@link PatternMatcher} with a map of patterns to values
038         * @param map a map from String patterns to values
039         */
040        public PatternMatcher(Map<String, S> map) {
041                super();
042                this.map = map;
043                // Sort keys to start with the most specific
044                sorted = new ArrayList<String>(map.keySet());
045                Collections.sort(sorted, new Comparator<String>() {
046            @Override
047                        public int compare(String o1, String o2) {
048                                String s1 = o1; // .replace('?', '{');
049                                String s2 = o2; // .replace('*', '}');
050                                return s2.compareTo(s1);
051                        }
052                });
053        }
054
055        /**
056         * Lifted from AntPathMatcher in Spring Core. Tests whether or not a string
057         * matches against a pattern. The pattern may contain two special
058         * characters:<br>
059         * '*' means zero or more characters<br>
060         * '?' means one and only one character
061         * 
062         * @param pattern pattern to match against. Must not be <code>null</code>.
063         * @param str string which must be matched against the pattern. Must not be
064         * <code>null</code>.
065         * @return <code>true</code> if the string matches against the pattern, or
066         * <code>false</code> otherwise.
067         */
068        public static boolean match(String pattern, String str) {
069                char[] patArr = pattern.toCharArray();
070                char[] strArr = str.toCharArray();
071                int patIdxStart = 0;
072                int patIdxEnd = patArr.length - 1;
073                int strIdxStart = 0;
074                int strIdxEnd = strArr.length - 1;
075                char ch;
076
077                boolean containsStar = pattern.contains("*");
078
079                if (!containsStar) {
080                        // No '*'s, so we make a shortcut
081                        if (patIdxEnd != strIdxEnd) {
082                                return false; // Pattern and string do not have the same size
083                        }
084                        for (int i = 0; i <= patIdxEnd; i++) {
085                                ch = patArr[i];
086                                if (ch != '?') {
087                                        if (ch != strArr[i]) {
088                                                return false;// Character mismatch
089                                        }
090                                }
091                        }
092                        return true; // String matches against pattern
093                }
094
095                if (patIdxEnd == 0) {
096                        return true; // Pattern contains only '*', which matches anything
097                }
098
099                // 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}