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 */
9package com.vladium.util;
10
11// ----------------------------------------------------------------------------
12/**
13 * @author Vlad Roubtsov, (C) 2002
14 */
15public
16abstract 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// ----------------------------------------------------------------------------