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 
compile(final String pattern)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 
matches(String s)71     public abstract boolean matches (String s);
matches(char [] chars)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 
WCMatcher()111     WCMatcher () {}
112 
113     // private: ...............................................................
114 
115 
116     private static final class AllMatcher extends WCMatcher
117     {
matches(final String s)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 
matches(final char [] chars)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     {
matches(final String s)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 
matches(final char [] chars)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     {
matches(final String s)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 
matches(final char [] chars)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 
StartsWithMatcher(final char [] pattern, final int patternLength)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     {
matches(final String s)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 
matches(final char [] chars)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 
EndsWithMatcher(final char [] pattern, final int patternLength)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     {
matches(final String s)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 
matches(final char [] string)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 
PatternMatcher(final char [] pattern, final int patternLength)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 // ----------------------------------------------------------------------------