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}