1 /* Copyright (C) 2003 Vladimir Roubtsov. All rights reserved. 2 * 3 * This program and the accompanying materials are made available under 4 * the terms of the Common Public License v1.0 which accompanies this distribution, 5 * and is available at http://www.eclipse.org/legal/cpl-v10.html 6 * 7 * $Id: WCMatcher.java,v 1.1.1.1 2004/05/09 16:57:56 vlad_r Exp $ 8 */ 9 package com.vladium.util; 10 11 // ---------------------------------------------------------------------------- 12 /** 13 * @author Vlad Roubtsov, (C) 2002 14 */ 15 public 16 abstract class WCMatcher 17 { 18 // public: ................................................................ 19 20 21 public static WCMatcher compile (final String pattern) 22 { 23 if (pattern == null) throw new IllegalArgumentException ("null input: pattern"); 24 25 final char [] chars = pattern.toCharArray (); // is this faster than using charAt()? 26 final int charsLength = chars.length; 27 28 if (charsLength == 0) 29 return EMPTY_MATCHER; // TODO: should be an EMPTY_MATCHER 30 else 31 { 32 int patternLength = 0, starCount = 0, questionCount = 0; 33 boolean star = false; 34 35 for (int c = 0; c < charsLength; ++ c) 36 { 37 final char ch = chars [c]; 38 if (ch == '*') 39 { 40 if (! star) 41 { 42 star = true; 43 ++ starCount; 44 chars [patternLength ++] = '*'; 45 } 46 } 47 else 48 { 49 star = false; 50 if (ch == '?') ++ questionCount; 51 chars [patternLength ++] = ch; 52 } 53 } 54 55 // [assertion: patternLength > 0] 56 57 if ((starCount == 1) && (questionCount == 0)) 58 { 59 if (patternLength == 1) 60 return ALL_MATCHER; 61 else if (chars [0] == '*') 62 return new EndsWithMatcher (chars, patternLength); 63 else if (chars [patternLength - 1] == '*') 64 return new StartsWithMatcher (chars, patternLength); 65 } 66 67 return new PatternMatcher (chars, patternLength); 68 } 69 } 70 71 public abstract boolean matches (String s); 72 public abstract boolean matches (char [] chars); 73 74 75 // private boolean matches (int pi, int si, final char [] string) 76 // { 77 // System.out.println ("pi = " + pi + ", si = " + si); 78 // 79 // if (pi == m_pattern.length) 80 // return si == string.length; 81 // else 82 // { 83 // switch (m_pattern [pi]) 84 // { 85 // case '?': 86 // { 87 // return (si < string.length) && matches (pi + 1, si + 1, string); 88 // } 89 // 90 // case '*': 91 // { 92 // return matches (pi + 1, si, string) || ((si < string.length) && matches (pi, si + 1, string)); 93 // } 94 // 95 // default: 96 // { 97 // return (si < string.length) && (m_pattern [pi] == string [si]) && matches (pi + 1, si + 1, string); 98 // } 99 // 100 // } // end of switch 101 // } 102 // } 103 104 105 106 // protected: ............................................................. 107 108 // package: ............................................................... 109 110 111 WCMatcher () {} 112 113 // private: ............................................................... 114 115 116 private static final class AllMatcher extends WCMatcher 117 { 118 public final boolean matches (final String s) 119 { 120 if (s == null) throw new IllegalArgumentException ("null input: s"); 121 122 return true; 123 } 124 125 public final boolean matches (final char [] chars) 126 { 127 if (chars == null) throw new IllegalArgumentException ("null input: chars"); 128 129 return true; 130 } 131 132 } // end of nested class 133 134 135 private static final class EmptyMatcher extends WCMatcher 136 { 137 public final boolean matches (final String s) 138 { 139 if (s == null) throw new IllegalArgumentException ("null input: s"); 140 141 return false; 142 } 143 144 public final boolean matches (final char [] chars) 145 { 146 if (chars == null) throw new IllegalArgumentException ("null input: chars"); 147 148 return chars.length == 0; 149 } 150 151 } // end of nested class 152 153 154 private static final class StartsWithMatcher extends WCMatcher 155 { 156 public final boolean matches (final String s) 157 { 158 if (s == null) throw new IllegalArgumentException ("null input: s"); 159 160 return s.startsWith (m_prefix); 161 } 162 163 public final boolean matches (final char [] chars) 164 { 165 if (chars == null) throw new IllegalArgumentException ("null input: chars"); 166 167 final char [] prefixChars = m_prefixChars; 168 final int prefixLength = prefixChars.length - 1; 169 170 if (chars.length < prefixLength) return false; 171 172 for (int c = 0; c < prefixLength; ++ c) 173 { 174 if (chars [c] != prefixChars [c]) return false; 175 } 176 177 return true; 178 } 179 180 StartsWithMatcher (final char [] pattern, final int patternLength) 181 { 182 m_prefixChars = pattern; 183 m_prefix = new String (pattern, 0, patternLength - 1); 184 } 185 186 private final char [] m_prefixChars; 187 private final String m_prefix; 188 189 } // end of nested class 190 191 192 private static final class EndsWithMatcher extends WCMatcher 193 { 194 public final boolean matches (final String s) 195 { 196 if (s == null) throw new IllegalArgumentException ("null input: s"); 197 198 return s.endsWith (m_suffix); 199 } 200 201 public final boolean matches (final char [] chars) 202 { 203 if (chars == null) throw new IllegalArgumentException ("null input: chars"); 204 205 final char [] suffixChars = m_suffixChars; 206 final int suffixLength = suffixChars.length - 1; 207 final int charsLength = chars.length; 208 209 if (charsLength < suffixLength) return false; 210 211 for (int c = 0; c < suffixLength; ++ c) 212 { 213 if (chars [charsLength - 1 - c] != suffixChars [suffixLength - c]) return false; 214 } 215 216 return true; 217 } 218 219 EndsWithMatcher (final char [] pattern, final int patternLength) 220 { 221 m_suffixChars = pattern; 222 m_suffix = new String (pattern, 1, patternLength - 1); 223 } 224 225 private final char [] m_suffixChars; 226 private final String m_suffix; 227 228 } // end of nested class 229 230 231 private static final class PatternMatcher extends WCMatcher 232 { 233 public final boolean matches (final String s) 234 { 235 if (s == null) throw new IllegalArgumentException ("null input: s"); 236 237 final char [] string = s.toCharArray (); // implies an array copy; is this faster than using charAt()? 238 final int stringLength = string.length; 239 240 final char [] pattern = m_pattern; 241 final int patternLength = m_patternLength; 242 243 // [assertion: patternLength > 0] 244 245 int si = 0, pi = 0; 246 boolean star = false; 247 248 249 next: while (true) 250 { 251 //System.out.println ("pi = " + pi + ", si = " + si); 252 253 int i = 0; 254 for ( ; pi + i < patternLength; ++ i) 255 { 256 final char patternChar = pattern [pi + i]; 257 258 if (patternChar == '*') 259 { 260 si += i; 261 pi += (i + 1); 262 263 star = true; 264 continue next; 265 } 266 267 final int si_i = si + i; 268 269 if (si_i == stringLength) return false; 270 271 if (patternChar != string [si_i]) 272 { 273 if (patternChar == '?') continue; 274 275 if (! star) return false; 276 ++ si; 277 278 continue next; 279 } 280 281 } // end of for 282 283 if (si + i == stringLength) return true; 284 285 if (! star) return false; 286 ++ si; 287 288 // [continue next;] 289 } 290 } 291 292 293 public final boolean matches (final char [] string) 294 { 295 if (string == null) throw new IllegalArgumentException ("null input: string"); 296 297 final int stringLength = string.length; 298 299 final char [] pattern = m_pattern; 300 final int patternLength = m_patternLength; 301 302 // [assertion: patternLength > 0] 303 304 int si = 0, pi = 0; 305 boolean star = false; 306 307 308 next: while (true) 309 { 310 //System.out.println ("pi = " + pi + ", si = " + si); 311 312 int i = 0; 313 for ( ; pi + i < patternLength; ++ i) 314 { 315 final char patternChar = pattern [pi + i]; 316 317 if (patternChar == '*') 318 { 319 si += i; 320 pi += (i + 1); 321 322 star = true; 323 continue next; 324 } 325 326 final int si_i = si + i; 327 328 if (si_i == stringLength) return false; 329 330 if (patternChar != string [si_i]) 331 { 332 if (patternChar == '?') continue; 333 334 if (! star) return false; 335 ++ si; 336 337 continue next; 338 } 339 340 } // end of for 341 342 if (si + i == stringLength) return true; 343 344 if (! star) return false; 345 ++ si; 346 347 // [continue next;] 348 } 349 } 350 351 PatternMatcher (final char [] pattern, final int patternLength) 352 { 353 m_pattern = pattern; 354 m_patternLength = patternLength; 355 } 356 357 358 private final char [] m_pattern; 359 private final int m_patternLength; 360 361 } // end of nested class 362 363 364 private static final WCMatcher ALL_MATCHER = new AllMatcher (); 365 private static final WCMatcher EMPTY_MATCHER = new EmptyMatcher (); 366 367 } // end of class 368 // ----------------------------------------------------------------------------
