KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > net > percederberg > grammatica > parser > re > RepeatElement


1 /*
2  * RepeatElement.java
3  *
4  * This library is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU Lesser General Public License
6  * as published by the Free Software Foundation; either version 2.1
7  * of the License, or (at your option) any later version.
8  *
9  * This library is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12  * Lesser General Public License for more details.
13  *
14  * You should have received a copy of the GNU Lesser General Public
15  * License along with this library; if not, write to the Free
16  * Software Foundation, Inc., 59 Temple Place, Suite 330, Boston,
17  * MA 02111-1307, USA.
18  *
19  * Copyright (c) 2003-2005 Per Cederberg. All rights reserved.
20  */
21
22 package net.percederberg.grammatica.parser.re;
23
24 import java.io.IOException JavaDoc;
25 import java.io.PrintWriter JavaDoc;
26 import java.util.BitSet JavaDoc;
27
28 import net.percederberg.grammatica.parser.LookAheadReader;
29
30 /**
31  * A regular expression element repeater. The element repeats the
32  * matches from a specified element, attempting to reach the maximum
33  * repetition count.
34  *
35  * @author Per Cederberg, <per at percederberg dot net>
36  * @version 1.5
37  */
38 class RepeatElement extends Element {
39
40     /**
41      * The greedy repeat type constant.
42      */
43     public static final int GREEDY = 1;
44
45     /**
46      * The reluctant repeat type constant.
47      */
48     public static final int RELUCTANT = 2;
49
50     /**
51      * The possesive repeat type constant.
52      */
53     public static final int POSSESSIVE = 3;
54
55     /**
56      * The element to repeat.
57      */
58     private Element elem;
59
60     /**
61      * The minimum number of repetitions.
62      */
63     private int min;
64
65     /**
66      * The maximum number of repetitions.
67      */
68     private int max;
69
70     /**
71      * The repeat type.
72      */
73     private int type;
74
75     /**
76      * The start position of the last set of matches.
77      */
78     private int matchStart;
79
80     /**
81      * A set with all matches starting as matchStart. A match with a
82      * specific length is reported by a non-zero bit in the bit set.
83      */
84     private BitSet JavaDoc matches;
85
86     /**
87      * Creats a new element repeater.
88      *
89      * @param elem the element to repeat
90      * @param min the minimum count
91      * @param max the maximum count
92      * @param type the repeat type constant
93      *
94      * @see #GREEDY
95      * @see #RELUCTANT
96      * @see #POSSESSIVE
97      */
98     public RepeatElement(Element elem, int min, int max, int type) {
99         this.elem = elem;
100         this.min = min;
101         if (max <= 0) {
102             this.max = Integer.MAX_VALUE;
103         } else {
104             this.max = max;
105         }
106         this.type = type;
107         this.matchStart = -1;
108         this.matches = null;
109     }
110
111     /**
112      * Creates a copy of this element. The copy will be an instance
113      * of the same class matching the same strings. Copies of elements
114      * are necessary to allow elements to cache intermediate results
115      * while matching strings without interfering with other threads.
116      *
117      * @return a copy of this element
118      */
119     public Object JavaDoc clone() {
120         return new RepeatElement((Element) elem.clone(), min, max, type);
121     }
122
123     /**
124      * Returns the length of a matching string starting at the
125      * specified position. The number of matches to skip can also be
126      * specified.
127      *
128      * @param m the matcher being used
129      * @param input the input character stream to match
130      * @param start the starting position
131      * @param skip the number of matches to skip
132      *
133      * @return the length of the matching string, or
134      * -1 if no match was found
135      *
136      * @throws IOException if an I/O error occurred
137      */
138     public int match(Matcher m, LookAheadReader input, int start, int skip)
139         throws IOException JavaDoc {
140
141         if (skip == 0) {
142             matchStart = -1;
143             matches = null;
144         }
145         switch (type) {
146         case GREEDY:
147             return matchGreedy(m, input, start, skip);
148         case RELUCTANT:
149             return matchReluctant(m, input, start, skip);
150         case POSSESSIVE:
151             if (skip == 0) {
152                 return matchPossessive(m, input, start, 0);
153             }
154             break;
155         }
156         return -1;
157     }
158
159     /**
160      * Returns the length of the longest possible matching string
161      * starting at the specified position. The number of matches to
162      * skip can also be specified.
163      *
164      * @param m the matcher being used
165      * @param input the input character stream to match
166      * @param start the starting position
167      * @param skip the number of matches to skip
168      *
169      * @return the length of the longest matching string, or
170      * -1 if no match was found
171      *
172      * @throws IOException if an I/O error occurred
173      */
174     private int matchGreedy(Matcher m,
175                             LookAheadReader input,
176                             int start,
177                             int skip)
178         throws IOException JavaDoc {
179
180         // Check for simple case
181 if (skip == 0) {
182             return matchPossessive(m, input, start, 0);
183         }
184
185         // Find all matches
186 if (matchStart != start) {
187             matchStart = start;
188             matches = new BitSet JavaDoc();
189             findMatches(m, input, start, 0, 0, 0);
190         }
191
192         // Find first non-skipped match
193 for (int i = matches.size(); i >= 0; i--) {
194             if (matches.get(i)) {
195                 if (skip == 0) {
196                     return i;
197                 }
198                 skip--;
199             }
200         }
201         return -1;
202     }
203
204     /**
205      * Returns the length of the shortest possible matching string
206      * starting at the specified position. The number of matches to
207      * skip can also be specified.
208      *
209      * @param m the matcher being used
210      * @param input the input character stream to match
211      * @param start the starting position
212      * @param skip the number of matches to skip
213      *
214      * @return the length of the shortest matching string, or
215      * -1 if no match was found
216      *
217      * @throws IOException if an I/O error occurred
218      */
219     private int matchReluctant(Matcher m,
220                                LookAheadReader input,
221                                int start,
222                                int skip)
223         throws IOException JavaDoc {
224
225         // Find all matches
226 if (matchStart != start) {
227             matchStart = start;
228             matches = new BitSet JavaDoc();
229             findMatches(m, input, start, 0, 0, 0);
230         }
231
232         // Find first non-skipped match
233 for (int i = 0; i <= matches.size(); i++) {
234             if (matches.get(i)) {
235                 if (skip == 0) {
236                     return i;
237                 }
238                 skip--;
239             }
240         }
241         return -1;
242     }
243
244     /**
245      * Returns the length of the maximum number of elements matching
246      * the string starting at the specified position. This method
247      * allows no backtracking, i.e. no skips..
248      *
249      * @param m the matcher being used
250      * @param input the input character stream to match
251      * @param start the starting position
252      * @param count the start count, normally zero (0)
253      *
254      * @return the length of the longest matching string, or
255      * -1 if no match was found
256      *
257      * @throws IOException if an I/O error occurred
258      */
259     private int matchPossessive(Matcher m,
260                                 LookAheadReader input,
261                                 int start,
262                                 int count)
263         throws IOException JavaDoc {
264
265         int length = 0;
266         int subLength = 1;
267
268         // Match as many elements as possible
269 while (subLength > 0 && count < max) {
270             subLength = elem.match(m, input, start + length, 0);
271             if (subLength >= 0) {
272                 count++;
273                 length += subLength;
274             }
275         }
276
277         // Return result
278 if (min <= count && count <= max) {
279             return length;
280         } else {
281             return -1;
282         }
283     }
284
285     /**
286      * Finds all matches and adds the lengths to the matches set.
287      *
288      * @param m the matcher being used
289      * @param input the input character stream to match
290      * @param start the starting position
291      * @param length the match length at the start position
292      * @param count the number of sub-elements matched
293      * @param attempt the number of match attempts here
294      *
295      * @throws IOException if an I/O error occurred
296      */
297     private void findMatches(Matcher m,
298                              LookAheadReader input,
299                              int start,
300                              int length,
301                              int count,
302                              int attempt)
303         throws IOException JavaDoc {
304
305         int subLength;
306
307         // Check match ending here
308 if (count > max) {
309             return;
310         }
311         if (min <= count && attempt == 0) {
312             matches.set(length);
313         }
314
315         // Check element match
316 subLength = elem.match(m, input, start, attempt);
317         if (subLength < 0) {
318             return;
319         } else if (subLength == 0) {
320             if (min == count + 1) {
321                 matches.set(length);
322             }
323             return;
324         }
325
326         // Find alternative and subsequent matches
327 findMatches(m, input, start, length, count, attempt + 1);
328         findMatches(m,
329                     input,
330                     start + subLength,
331                     length + subLength,
332                     count + 1,
333                     0);
334     }
335
336     /**
337      * Prints this element to the specified output stream.
338      *
339      * @param output the output stream to use
340      * @param indent the current indentation
341      */
342     public void printTo(PrintWriter JavaDoc output, String JavaDoc indent) {
343         output.print(indent + "Repeat (" + min + "," + max + ")");
344         if (type == RELUCTANT) {
345             output.print("?");
346         } else if (type == POSSESSIVE) {
347             output.print("+");
348         }
349         output.println();
350         elem.printTo(output, indent + " ");
351     }
352 }
353
Popular Tags