001// Licensed under the Apache License, Version 2.0 (the "License");
002// you may not use this file except in compliance with the License.
003// You may obtain a copy of the License at
004//
005//     http://www.apache.org/licenses/LICENSE-2.0
006//
007// Unless required by applicable law or agreed to in writing, software
008// distributed under the License is distributed on an "AS IS" BASIS,
009// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
010// See the License for the specific language governing permissions and
011// limitations under the License.
012
013package org.apache.tapestry5.ioc.internal.services.cron;
014
015import java.io.Serializable;
016import java.text.ParseException;
017import java.util.*;
018
019/**
020 * Provides a parser and evaluator for unix-like cron expressions. Cron 
021 * expressions provide the ability to specify complex time combinations such as
022 * "At 8:00am every Monday through Friday" or "At 1:30am every 
023 * last Friday of the month". 
024 * <P>
025 * Cron expressions are comprised of 6 required fields and one optional field
026 * separated by white space. The fields respectively are described as follows:
027 * 
028 * <table>
029 * <caption>Supported Cron fields</caption>
030 * <tr>
031 * <th style="text-align: left;">Field Name</th>
032 * <th style="text-align: left;">&nbsp;</th>
033 * <th style="text-align: left;">Allowed Values</th>
034 * <th style="text-align: left;">&nbsp;</th>
035 * <th style="text-align: left;">Allowed Special Characters</th>
036 * </tr>
037 * <tr>
038 * <td style="text-align: left;"><code>Seconds</code></td>
039 * <td style="text-align: left;">&nbsp;</td>
040 * <td style="text-align: left;"><code>0-59</code></td>
041 * <td style="text-align: left;">&nbsp;</td>
042 * <td style="text-align: left;"><code>, - * /</code></td>
043 * </tr>
044 * <tr>
045 * <td style="text-align: left;"><code>Minutes</code></td>
046 * <td style="text-align: left;">&nbsp;</td>
047 * <td style="text-align: left;"><code>0-59</code></td>
048 * <td style="text-align: left;">&nbsp;</td>
049 * <td style="text-align: left;"><code>, - * /</code></td>
050 * </tr>
051 * <tr>
052 * <td style="text-align: left;"><code>Hours</code></td>
053 * <td style="text-align: left;">&nbsp;</td>
054 * <td style="text-align: left;"><code>0-23</code></td>
055 * <td style="text-align: left;">&nbsp;</td>
056 * <td style="text-align: left;"><code>, - * /</code></td>
057 * </tr>
058 * <tr>
059 * <td style="text-align: left;"><code>Day-of-month</code></td>
060 * <td style="text-align: left;">&nbsp;</td>
061 * <td style="text-align: left;"><code>1-31</code></td>
062 * <td style="text-align: left;">&nbsp;</td>
063 * <td style="text-align: left;"><code>, - * ? / L W</code></td>
064 * </tr>
065 * <tr>
066 * <td style="text-align: left;"><code>Month</code></td>
067 * <td style="text-align: left;">&nbsp;</td>
068 * <td style="text-align: left;"><code>0-11 or JAN-DEC</code></td>
069 * <td style="text-align: left;">&nbsp;</td>
070 * <td style="text-align: left;"><code>, - * /</code></td>
071 * </tr>
072 * <tr>
073 * <td style="text-align: left;"><code>Day-of-Week</code></td>
074 * <td style="text-align: left;">&nbsp;</td>
075 * <td style="text-align: left;"><code>1-7 or SUN-SAT</code></td>
076 * <td style="text-align: left;">&nbsp;</td>
077 * <td style="text-align: left;"><code>, - * ? / L #</code></td>
078 * </tr>
079 * <tr>
080 * <td style="text-align: left;"><code>Year (Optional)</code></td>
081 * <td style="text-align: left;">&nbsp;</td>
082 * <td style="text-align: left;"><code>empty, 1970-2199</code></td>
083 * <td style="text-align: left;">&nbsp;</td>
084 * <td style="text-align: left;"><code>, - * /</code></td>
085 * </tr>
086 * </table>
087 * <P>
088 * The '*' character is used to specify all values. For example, &quot;*&quot; 
089 * in the minute field means &quot;every minute&quot;.
090 * <P>
091 * The '?' character is allowed for the day-of-month and day-of-week fields. It
092 * is used to specify 'no specific value'. This is useful when you need to
093 * specify something in one of the two fields, but not the other.
094 * <P>
095 * The '-' character is used to specify ranges For example &quot;10-12&quot; in
096 * the hour field means &quot;the hours 10, 11 and 12&quot;.
097 * <P>
098 * The ',' character is used to specify additional values. For example
099 * &quot;MON,WED,FRI&quot; in the day-of-week field means &quot;the days Monday,
100 * Wednesday, and Friday&quot;.
101 * <P>
102 * The '/' character is used to specify increments. For example &quot;0/15&quot;
103 * in the seconds field means &quot;the seconds 0, 15, 30, and 45&quot;. And 
104 * &quot;5/15&quot; in the seconds field means &quot;the seconds 5, 20, 35, and
105 * 50&quot;.  Specifying '*' before the  '/' is equivalent to specifying 0 is
106 * the value to start with. Essentially, for each field in the expression, there
107 * is a set of numbers that can be turned on or off. For seconds and minutes, 
108 * the numbers range from 0 to 59. For hours 0 to 23, for days of the month 0 to
109 * 31, and for months 0 to 11 (JAN to DEC). The &quot;/&quot; character simply helps you turn
110 * on every &quot;nth&quot; value in the given set. Thus &quot;7/6&quot; in the
111 * month field only turns on month &quot;7&quot;, it does NOT mean every 6th 
112 * month, please note that subtlety.  
113 * <P>
114 * The 'L' character is allowed for the day-of-month and day-of-week fields.
115 * This character is short-hand for &quot;last&quot;, but it has different 
116 * meaning in each of the two fields. For example, the value &quot;L&quot; in 
117 * the day-of-month field means &quot;the last day of the month&quot; - day 31 
118 * for January, day 28 for February on non-leap years. If used in the 
119 * day-of-week field by itself, it simply means &quot;7&quot; or 
120 * &quot;SAT&quot;. But if used in the day-of-week field after another value, it
121 * means &quot;the last xxx day of the month&quot; - for example &quot;6L&quot;
122 * means &quot;the last friday of the month&quot;. You can also specify an offset 
123 * from the last day of the month, such as "L-3" which would mean the third-to-last 
124 * day of the calendar month. <i>When using the 'L' option, it is important not to 
125 * specify lists, or ranges of values, as you'll get confusing/unexpected results.</i>
126 * <P>
127 * The 'W' character is allowed for the day-of-month field.  This character 
128 * is used to specify the weekday (Monday-Friday) nearest the given day.  As an 
129 * example, if you were to specify &quot;15W&quot; as the value for the 
130 * day-of-month field, the meaning is: &quot;the nearest weekday to the 15th of
131 * the month&quot;. So if the 15th is a Saturday, the trigger will fire on 
132 * Friday the 14th. If the 15th is a Sunday, the trigger will fire on Monday the
133 * 16th. If the 15th is a Tuesday, then it will fire on Tuesday the 15th. 
134 * However if you specify &quot;1W&quot; as the value for day-of-month, and the
135 * 1st is a Saturday, the trigger will fire on Monday the 3rd, as it will not 
136 * 'jump' over the boundary of a month's days.  The 'W' character can only be 
137 * specified when the day-of-month is a single day, not a range or list of days.
138 * <P>
139 * The 'L' and 'W' characters can also be combined for the day-of-month 
140 * expression to yield 'LW', which translates to &quot;last weekday of the 
141 * month&quot;.
142 * <P>
143 * The '#' character is allowed for the day-of-week field. This character is
144 * used to specify &quot;the nth&quot; XXX day of the month. For example, the 
145 * value of &quot;6#3&quot; in the day-of-week field means the third Friday of 
146 * the month (day 6 = Friday and &quot;#3&quot; = the 3rd one in the month). 
147 * Other examples: &quot;2#1&quot; = the first Monday of the month and 
148 * &quot;4#5&quot; = the fifth Wednesday of the month. Note that if you specify
149 * &quot;#5&quot; and there is not 5 of the given day-of-week in the month, then
150 * no firing will occur that month.  If the '#' character is used, there can
151 * only be one expression in the day-of-week field (&quot;3#1,6#3&quot; is 
152 * not valid, since there are two expressions).
153 * <P>
154 * <!--The 'C' character is allowed for the day-of-month and day-of-week fields.
155 * This character is short-hand for "calendar". This means values are
156 * calculated against the associated calendar, if any. If no calendar is
157 * associated, then it is equivalent to having an all-inclusive calendar. A
158 * value of "5C" in the day-of-month field means "the first day included by the
159 * calendar on or after the 5th". A value of "1C" in the day-of-week field
160 * means "the first day included by the calendar on or after Sunday".-->
161 * <P>
162 * The legal characters and the names of months and days of the week are not
163 * case sensitive.
164 * 
165 * <p>
166 * <b>NOTES:</b>
167 * </p>
168 * <ul>
169 * <li>Support for specifying both a day-of-week and a day-of-month value is
170 * not complete (you'll need to use the '?' character in one of these fields).
171 * </li>
172 * <li>Overflowing ranges is supported - that is, having a larger number on 
173 * the left hand side than the right. You might do 22-2 to catch 10 o'clock 
174 * at night until 2 o'clock in the morning, or you might have NOV-FEB. It is 
175 * very important to note that overuse of overflowing ranges creates ranges 
176 * that don't make sense and no effort has been made to determine which 
177 * interpretation CronExpression chooses. An example would be 
178 * "0 0 14-6 ? * FRI-MON". </li>
179 * </ul>
180 * 
181 * 
182 * @author Sharada Jambula, James House
183 * @author Contributions from Mads Henderson
184 * @author Refactoring from CronTrigger to CronExpression by Aaron Craven
185 */
186public final class CronExpression implements Serializable, Cloneable {
187
188    private static final long serialVersionUID = 12423409423L;
189    
190    protected static final int SECOND = 0;
191    protected static final int MINUTE = 1;
192    protected static final int HOUR = 2;
193    protected static final int DAY_OF_MONTH = 3;
194    protected static final int MONTH = 4;
195    protected static final int DAY_OF_WEEK = 5;
196    protected static final int YEAR = 6;
197    protected static final int ALL_SPEC_INT = 99; // '*'
198    protected static final int NO_SPEC_INT = 98; // '?'
199    protected static final Integer ALL_SPEC = ALL_SPEC_INT;
200    protected static final Integer NO_SPEC = NO_SPEC_INT;
201    
202    protected static final Map<String, Integer> monthMap = new HashMap<String, Integer>(20);
203    protected static final Map<String, Integer> dayMap = new HashMap<String, Integer>(60);
204    static {
205        monthMap.put("JAN", 0);
206        monthMap.put("FEB", 1);
207        monthMap.put("MAR", 2);
208        monthMap.put("APR", 3);
209        monthMap.put("MAY", 4);
210        monthMap.put("JUN", 5);
211        monthMap.put("JUL", 6);
212        monthMap.put("AUG", 7);
213        monthMap.put("SEP", 8);
214        monthMap.put("OCT", 9);
215        monthMap.put("NOV", 10);
216        monthMap.put("DEC", 11);
217
218        dayMap.put("SUN", 1);
219        dayMap.put("MON", 2);
220        dayMap.put("TUE", 3);
221        dayMap.put("WED", 4);
222        dayMap.put("THU", 5);
223        dayMap.put("FRI", 6);
224        dayMap.put("SAT", 7);
225    }
226
227    private final String cronExpression;
228    private TimeZone timeZone = null;
229    protected transient TreeSet<Integer> seconds;
230    protected transient TreeSet<Integer> minutes;
231    protected transient TreeSet<Integer> hours;
232    protected transient TreeSet<Integer> daysOfMonth;
233    protected transient TreeSet<Integer> months;
234    protected transient TreeSet<Integer> daysOfWeek;
235    protected transient TreeSet<Integer> years;
236
237    protected transient boolean lastdayOfWeek = false;
238    protected transient int nthdayOfWeek = 0;
239    protected transient boolean lastdayOfMonth = false;
240    protected transient boolean nearestWeekday = false;
241    protected transient int lastdayOffset = 0;
242    protected transient boolean expressionParsed = false;
243    
244    public static final int MAX_YEAR = Calendar.getInstance().get(Calendar.YEAR) + 100;
245
246    /**
247     * Constructs a new <CODE>CronExpression</CODE> based on the specified 
248     * parameter.
249     * 
250     * @param cronExpression String representation of the cron expression the
251     *                       new object should represent
252     * @throws java.text.ParseException
253     *         if the string expression cannot be parsed into a valid 
254     *         <CODE>CronExpression</CODE>
255     */
256    public CronExpression(String cronExpression) throws ParseException {
257        if (cronExpression == null) {
258            throw new IllegalArgumentException("cronExpression cannot be null");
259        }
260        
261        this.cronExpression = cronExpression.toUpperCase(Locale.US);
262        
263        buildExpression(this.cronExpression);
264    }
265    
266    /**
267     * Constructs a new {@code CronExpression} as a copy of an existing
268     * instance.
269     * 
270     * @param expression
271     *            The existing cron expression to be copied
272     */
273    public CronExpression(CronExpression expression) {
274        /*
275         * We don't call the other constructor here since we need to swallow the
276         * ParseException. We also elide some of the sanity checking as it is
277         * not logically trippable.
278         */
279        this.cronExpression = expression.getCronExpression();
280        try {
281            buildExpression(cronExpression);
282        } catch (ParseException ex) {
283            throw new AssertionError("Could not parse expression!", ex);
284        }
285        if (expression.getTimeZone() != null) {
286            setTimeZone((TimeZone) expression.getTimeZone().clone());
287        }
288    }
289
290    /**
291     * Indicates whether the given date satisfies the cron expression. Note that
292     * milliseconds are ignored, so two Dates falling on different milliseconds
293     * of the same second will always have the same result here.
294     * 
295     * @param date the date to evaluate
296     * @return a boolean indicating whether the given date satisfies the cron
297     *         expression
298     */
299    public boolean isSatisfiedBy(Date date) {
300        Calendar testDateCal = Calendar.getInstance(getTimeZone());
301        testDateCal.setTime(date);
302        testDateCal.set(Calendar.MILLISECOND, 0);
303        Date originalDate = testDateCal.getTime();
304        
305        testDateCal.add(Calendar.SECOND, -1);
306        
307        Date timeAfter = getTimeAfter(testDateCal.getTime());
308
309        return ((timeAfter != null) && (timeAfter.equals(originalDate)));
310    }
311    
312    /**
313     * Returns the next date/time <I>after</I> the given date/time which
314     * satisfies the cron expression.
315     * 
316     * @param date the date/time at which to begin the search for the next valid
317     *             date/time
318     * @return the next valid date/time
319     */
320    public Date getNextValidTimeAfter(Date date) {
321        return getTimeAfter(date);
322    }
323    
324    /**
325     * Returns the next date/time <I>after</I> the given date/time which does
326     * <I>not</I> satisfy the expression
327     * 
328     * @param date the date/time at which to begin the search for the next 
329     *             invalid date/time
330     * @return the next valid date/time
331     */
332    public Date getNextInvalidTimeAfter(Date date) {
333        long difference = 1000;
334        
335        //move back to the nearest second so differences will be accurate
336        Calendar adjustCal = Calendar.getInstance(getTimeZone());
337        adjustCal.setTime(date);
338        adjustCal.set(Calendar.MILLISECOND, 0);
339        Date lastDate = adjustCal.getTime();
340        
341        Date newDate;
342        
343        //FUTURE_TODO: (QUARTZ-481) IMPROVE THIS! The following is a BAD solution to this problem. Performance will be very bad here, depending on the cron expression. It is, however A solution.
344        
345        //keep getting the next included time until it's farther than one second
346        // apart. At that point, lastDate is the last valid fire time. We return
347        // the second immediately following it.
348        while (difference == 1000) {
349            newDate = getTimeAfter(lastDate);
350            if(newDate == null)
351                break;
352            
353            difference = newDate.getTime() - lastDate.getTime();
354            
355            if (difference == 1000) {
356                lastDate = newDate;
357            }
358        }
359        
360        return new Date(lastDate.getTime() + 1000);
361    }
362    
363    /**
364     * Returns the time zone for which this <code>CronExpression</code> 
365     * will be resolved.
366     */
367    public TimeZone getTimeZone() {
368        if (timeZone == null) {
369            timeZone = TimeZone.getDefault();
370        }
371
372        return timeZone;
373    }
374
375    /**
376     * Sets the time zone for which  this <code>CronExpression</code> 
377     * will be resolved.
378     */
379    public void setTimeZone(TimeZone timeZone) {
380        this.timeZone = timeZone;
381    }
382    
383    /**
384     * Returns the string representation of the <CODE>CronExpression</CODE>
385     * 
386     * @return a string representation of the <CODE>CronExpression</CODE>
387     */
388    @Override
389    public String toString() {
390        return cronExpression;
391    }
392
393    /**
394     * Indicates whether the specified cron expression can be parsed into a 
395     * valid cron expression
396     * 
397     * @param cronExpression the expression to evaluate
398     * @return a boolean indicating whether the given expression is a valid cron
399     *         expression
400     */
401    public static boolean isValidExpression(String cronExpression) {
402        
403        try {
404            new CronExpression(cronExpression);
405        } catch (ParseException pe) {
406            return false;
407        }
408        
409        return true;
410    }
411
412    public static void validateExpression(String cronExpression) throws ParseException {
413        
414        new CronExpression(cronExpression);
415    }
416    
417    
418    ////////////////////////////////////////////////////////////////////////////
419    //
420    // Expression Parsing Functions
421    //
422    ////////////////////////////////////////////////////////////////////////////
423
424    protected void buildExpression(String expression) throws ParseException {
425        expressionParsed = true;
426
427        try {
428
429            if (seconds == null) {
430                seconds = new TreeSet<Integer>();
431            }
432            if (minutes == null) {
433                minutes = new TreeSet<Integer>();
434            }
435            if (hours == null) {
436                hours = new TreeSet<Integer>();
437            }
438            if (daysOfMonth == null) {
439                daysOfMonth = new TreeSet<Integer>();
440            }
441            if (months == null) {
442                months = new TreeSet<Integer>();
443            }
444            if (daysOfWeek == null) {
445                daysOfWeek = new TreeSet<Integer>();
446            }
447            if (years == null) {
448                years = new TreeSet<Integer>();
449            }
450
451            int exprOn = SECOND;
452
453            StringTokenizer exprsTok = new StringTokenizer(expression, " \t",
454                    false);
455
456            while (exprsTok.hasMoreTokens() && exprOn <= YEAR) {
457                String expr = exprsTok.nextToken().trim();
458
459                // throw an exception if L is used with other days of the month
460                if(exprOn == DAY_OF_MONTH && expr.indexOf('L') != -1 && expr.length() > 1 && expr.contains(",")) {
461                    throw new ParseException("Support for specifying 'L' and 'LW' with other days of the month is not implemented", -1);
462                }
463                // throw an exception if L is used with other days of the week
464                if(exprOn == DAY_OF_WEEK && expr.indexOf('L') != -1 && expr.length() > 1  && expr.contains(",")) {
465                    throw new ParseException("Support for specifying 'L' with other days of the week is not implemented", -1);
466                }
467                if(exprOn == DAY_OF_WEEK && expr.indexOf('#') != -1 && expr.indexOf('#', expr.indexOf('#') +1) != -1) {
468                    throw new ParseException("Support for specifying multiple \"nth\" days is not implemented.", -1);
469                }
470                
471                StringTokenizer vTok = new StringTokenizer(expr, ",");
472                while (vTok.hasMoreTokens()) {
473                    String v = vTok.nextToken();
474                    storeExpressionVals(0, v, exprOn);
475                }
476
477                exprOn++;
478            }
479
480            if (exprOn <= DAY_OF_WEEK) {
481                throw new ParseException("Unexpected end of expression.",
482                            expression.length());
483            }
484
485            if (exprOn <= YEAR) {
486                storeExpressionVals(0, "*", YEAR);
487            }
488
489            TreeSet<Integer> dow = getSet(DAY_OF_WEEK);
490            TreeSet<Integer> dom = getSet(DAY_OF_MONTH);
491
492            // Copying the logic from the UnsupportedOperationException below
493            boolean dayOfMSpec = !dom.contains(NO_SPEC);
494            boolean dayOfWSpec = !dow.contains(NO_SPEC);
495
496            if (!dayOfMSpec || dayOfWSpec) {
497                if (!dayOfWSpec || dayOfMSpec) {
498                    throw new ParseException(
499                            "Support for specifying both a day-of-week AND a day-of-month parameter is not implemented.", 0);
500                }
501            }
502        } catch (ParseException pe) {
503            throw pe;
504        } catch (Exception e) {
505            throw new ParseException("Illegal cron expression format ("
506                    + e.toString() + ")", 0);
507        }
508    }
509
510    protected int storeExpressionVals(int pos, String s, int type)
511        throws ParseException {
512
513        int incr = 0;
514        int i = skipWhiteSpace(pos, s);
515        if (i >= s.length()) {
516            return i;
517        }
518        char c = s.charAt(i);
519        if ((c >= 'A') && (c <= 'Z') && (!s.equals("L")) && (!s.equals("LW")) && (!s.matches("^L-[0-9]*[W]?"))) {
520            String sub = s.substring(i, i + 3);
521            int sval = -1;
522            int eval = -1;
523            if (type == MONTH) {
524                sval = getMonthNumber(sub) + 1;
525                if (sval <= 0) {
526                    throw new ParseException("Invalid Month value: '" + sub + "'", i);
527                }
528                if (s.length() > i + 3) {
529                    c = s.charAt(i + 3);
530                    if (c == '-') {
531                        i += 4;
532                        sub = s.substring(i, i + 3);
533                        eval = getMonthNumber(sub) + 1;
534                        if (eval <= 0) {
535                            throw new ParseException("Invalid Month value: '" + sub + "'", i);
536                        }
537                    }
538                }
539            } else if (type == DAY_OF_WEEK) {
540                sval = getDayOfWeekNumber(sub);
541                if (sval < 0) {
542                    throw new ParseException("Invalid Day-of-Week value: '"
543                                + sub + "'", i);
544                }
545                if (s.length() > i + 3) {
546                    c = s.charAt(i + 3);
547                    if (c == '-') {
548                        i += 4;
549                        sub = s.substring(i, i + 3);
550                        eval = getDayOfWeekNumber(sub);
551                        if (eval < 0) {
552                            throw new ParseException(
553                                    "Invalid Day-of-Week value: '" + sub
554                                        + "'", i);
555                        }
556                    } else if (c == '#') {
557                        try {
558                            i += 4;
559                            nthdayOfWeek = Integer.parseInt(s.substring(i));
560                            if (nthdayOfWeek < 1 || nthdayOfWeek > 5) {
561                                throw new Exception();
562                            }
563                        } catch (Exception e) {
564                            throw new ParseException(
565                                    "A numeric value between 1 and 5 must follow the '#' option",
566                                    i);
567                        }
568                    } else if (c == 'L') {
569                        lastdayOfWeek = true;
570                        i++;
571                    }
572                }
573
574            } else {
575                throw new ParseException(
576                        "Illegal characters for this position: '" + sub + "'",
577                        i);
578            }
579            if (eval != -1) {
580                incr = 1;
581            }
582            addToSet(sval, eval, incr, type);
583            return (i + 3);
584        }
585
586        if (c == '?') {
587            i++;
588            if ((i + 1) < s.length() 
589                    && (s.charAt(i) != ' ' && s.charAt(i + 1) != '\t')) {
590                throw new ParseException("Illegal character after '?': "
591                            + s.charAt(i), i);
592            }
593            if (type != DAY_OF_WEEK && type != DAY_OF_MONTH) {
594                throw new ParseException(
595                            "'?' can only be specified for Day-of-Month or Day-of-Week.",
596                            i);
597            }
598            if (type == DAY_OF_WEEK && !lastdayOfMonth) {
599                int val = daysOfMonth.last();
600                if (val == NO_SPEC_INT) {
601                    throw new ParseException(
602                                "'?' can only be specified for Day-of-Month -OR- Day-of-Week.",
603                                i);
604                }
605            }
606
607            addToSet(NO_SPEC_INT, -1, 0, type);
608            return i;
609        }
610
611        if (c == '*' || c == '/') {
612            if (c == '*' && (i + 1) >= s.length()) {
613                addToSet(ALL_SPEC_INT, -1, incr, type);
614                return i + 1;
615            } else if (c == '/'
616                    && ((i + 1) >= s.length() || s.charAt(i + 1) == ' ' || s
617                            .charAt(i + 1) == '\t')) { 
618                throw new ParseException("'/' must be followed by an integer.", i);
619            } else if (c == '*') {
620                i++;
621            }
622            c = s.charAt(i);
623            if (c == '/') { // is an increment specified?
624                i++;
625                if (i >= s.length()) {
626                    throw new ParseException("Unexpected end of string.", i);
627                }
628
629                incr = getNumericValue(s, i);
630
631                i++;
632                if (incr > 10) {
633                    i++;
634                }
635                checkIncrementRange(incr, type, i);
636            } else {
637                incr = 1;
638            }
639
640            addToSet(ALL_SPEC_INT, -1, incr, type);
641            return i;
642        } else if (c == 'L') {
643            i++;
644            if (type == DAY_OF_MONTH) {
645                lastdayOfMonth = true;
646            }
647            if (type == DAY_OF_WEEK) {
648                addToSet(7, 7, 0, type);
649            }
650            if(type == DAY_OF_MONTH && s.length() > i) {
651                c = s.charAt(i);
652                if(c == '-') {
653                    ValueSet vs = getValue(0, s, i+1);
654                    lastdayOffset = vs.value;
655                    if(lastdayOffset > 30)
656                        throw new ParseException("Offset from last day must be <= 30", i+1);
657                    i = vs.pos;
658                }                        
659                if(s.length() > i) {
660                    c = s.charAt(i);
661                    if(c == 'W') {
662                        nearestWeekday = true;
663                        i++;
664                    }
665                }
666            }
667            return i;
668        } else if (c >= '0' && c <= '9') {
669            int val = Integer.parseInt(String.valueOf(c));
670            i++;
671            if (i >= s.length()) {
672                addToSet(val, -1, -1, type);
673            } else {
674                c = s.charAt(i);
675                if (c >= '0' && c <= '9') {
676                    ValueSet vs = getValue(val, s, i);
677                    val = vs.value;
678                    i = vs.pos;
679                }
680                i = checkNext(i, s, val, type);
681                return i;
682            }
683        } else {
684            throw new ParseException("Unexpected character: " + c, i);
685        }
686
687        return i;
688    }
689
690    private void checkIncrementRange(int incr, int type, int idxPos) throws ParseException {
691        if (incr > 59 && (type == SECOND || type == MINUTE)) {
692            throw new ParseException("Increment > 60 : " + incr, idxPos);
693        } else if (incr > 23 && (type == HOUR)) {
694            throw new ParseException("Increment > 24 : " + incr, idxPos);
695        } else if (incr > 31 && (type == DAY_OF_MONTH)) {
696            throw new ParseException("Increment > 31 : " + incr, idxPos);
697        } else if (incr > 7 && (type == DAY_OF_WEEK)) {
698            throw new ParseException("Increment > 7 : " + incr, idxPos);
699        } else if (incr > 12 && (type == MONTH)) {
700            throw new ParseException("Increment > 12 : " + incr, idxPos);
701        }
702    }
703
704    protected int checkNext(int pos, String s, int val, int type)
705        throws ParseException {
706        
707        int end = -1;
708        int i = pos;
709
710        if (i >= s.length()) {
711            addToSet(val, end, -1, type);
712            return i;
713        }
714
715        char c = s.charAt(pos);
716
717        if (c == 'L') {
718            if (type == DAY_OF_WEEK) {
719                if(val < 1 || val > 7)
720                    throw new ParseException("Day-of-Week values must be between 1 and 7", -1);
721                lastdayOfWeek = true;
722            } else {
723                throw new ParseException("'L' option is not valid here. (pos=" + i + ")", i);
724            }
725            TreeSet<Integer> set = getSet(type);
726            set.add(val);
727            i++;
728            return i;
729        }
730        
731        if (c == 'W') {
732            if (type == DAY_OF_MONTH) {
733                nearestWeekday = true;
734            } else {
735                throw new ParseException("'W' option is not valid here. (pos=" + i + ")", i);
736            }
737            if(val > 31)
738                throw new ParseException("The 'W' option does not make sense with values larger than 31 (max number of days in a month)", i); 
739            TreeSet<Integer> set = getSet(type);
740            set.add(val);
741            i++;
742            return i;
743        }
744
745        if (c == '#') {
746            if (type != DAY_OF_WEEK) {
747                throw new ParseException("'#' option is not valid here. (pos=" + i + ")", i);
748            }
749            i++;
750            try {
751                nthdayOfWeek = Integer.parseInt(s.substring(i));
752                if (nthdayOfWeek < 1 || nthdayOfWeek > 5) {
753                    throw new Exception();
754                }
755            } catch (Exception e) {
756                throw new ParseException(
757                        "A numeric value between 1 and 5 must follow the '#' option",
758                        i);
759            }
760
761            TreeSet<Integer> set = getSet(type);
762            set.add(val);
763            i++;
764            return i;
765        }
766
767        if (c == '-') {
768            i++;
769            c = s.charAt(i);
770            int v = Integer.parseInt(String.valueOf(c));
771            end = v;
772            i++;
773            if (i >= s.length()) {
774                addToSet(val, end, 1, type);
775                return i;
776            }
777            c = s.charAt(i);
778            if (c >= '0' && c <= '9') {
779                ValueSet vs = getValue(v, s, i);
780                end = vs.value;
781                i = vs.pos;
782            }
783            if (i < s.length() && ((c = s.charAt(i)) == '/')) {
784                i++;
785                c = s.charAt(i);
786                int v2 = Integer.parseInt(String.valueOf(c));
787                i++;
788                if (i >= s.length()) {
789                    addToSet(val, end, v2, type);
790                    return i;
791                }
792                c = s.charAt(i);
793                if (c >= '0' && c <= '9') {
794                    ValueSet vs = getValue(v2, s, i);
795                    int v3 = vs.value;
796                    addToSet(val, end, v3, type);
797                    i = vs.pos;
798                    return i;
799                } else {
800                    addToSet(val, end, v2, type);
801                    return i;
802                }
803            } else {
804                addToSet(val, end, 1, type);
805                return i;
806            }
807        }
808
809        if (c == '/') {
810            if ((i + 1) >= s.length() || s.charAt(i + 1) == ' ' || s.charAt(i + 1) == '\t') {
811                throw new ParseException("'/' must be followed by an integer.", i);
812            }
813
814            i++;
815            c = s.charAt(i);
816            int v2 = Integer.parseInt(String.valueOf(c));
817            i++;
818            if (i >= s.length()) {
819                checkIncrementRange(v2, type, i);
820                addToSet(val, end, v2, type);
821                return i;
822            }
823            c = s.charAt(i);
824            if (c >= '0' && c <= '9') {
825                ValueSet vs = getValue(v2, s, i);
826                int v3 = vs.value;
827                checkIncrementRange(v3, type, i);
828                addToSet(val, end, v3, type);
829                i = vs.pos;
830                return i;
831            } else {
832                throw new ParseException("Unexpected character '" + c + "' after '/'", i);
833            }
834        }
835
836        addToSet(val, end, 0, type);
837        i++;
838        return i;
839    }
840
841    public String getCronExpression() {
842        return cronExpression;
843    }
844    
845    public String getExpressionSummary() {
846        StringBuilder buf = new StringBuilder();
847
848        buf.append("seconds: ");
849        buf.append(getExpressionSetSummary(seconds));
850        buf.append("\n");
851        buf.append("minutes: ");
852        buf.append(getExpressionSetSummary(minutes));
853        buf.append("\n");
854        buf.append("hours: ");
855        buf.append(getExpressionSetSummary(hours));
856        buf.append("\n");
857        buf.append("daysOfMonth: ");
858        buf.append(getExpressionSetSummary(daysOfMonth));
859        buf.append("\n");
860        buf.append("months: ");
861        buf.append(getExpressionSetSummary(months));
862        buf.append("\n");
863        buf.append("daysOfWeek: ");
864        buf.append(getExpressionSetSummary(daysOfWeek));
865        buf.append("\n");
866        buf.append("lastdayOfWeek: ");
867        buf.append(lastdayOfWeek);
868        buf.append("\n");
869        buf.append("nearestWeekday: ");
870        buf.append(nearestWeekday);
871        buf.append("\n");
872        buf.append("NthDayOfWeek: ");
873        buf.append(nthdayOfWeek);
874        buf.append("\n");
875        buf.append("lastdayOfMonth: ");
876        buf.append(lastdayOfMonth);
877        buf.append("\n");
878        buf.append("years: ");
879        buf.append(getExpressionSetSummary(years));
880        buf.append("\n");
881
882        return buf.toString();
883    }
884
885    protected String getExpressionSetSummary(java.util.Set<Integer> set) {
886
887        if (set.contains(NO_SPEC)) {
888            return "?";
889        }
890        if (set.contains(ALL_SPEC)) {
891            return "*";
892        }
893
894        StringBuilder buf = new StringBuilder();
895
896        Iterator<Integer> itr = set.iterator();
897        boolean first = true;
898        while (itr.hasNext()) {
899            Integer iVal = itr.next();
900            String val = iVal.toString();
901            if (!first) {
902                buf.append(",");
903            }
904            buf.append(val);
905            first = false;
906        }
907
908        return buf.toString();
909    }
910
911    protected String getExpressionSetSummary(java.util.ArrayList<Integer> list) {
912
913        if (list.contains(NO_SPEC)) {
914            return "?";
915        }
916        if (list.contains(ALL_SPEC)) {
917            return "*";
918        }
919
920        StringBuilder buf = new StringBuilder();
921
922        Iterator<Integer> itr = list.iterator();
923        boolean first = true;
924        while (itr.hasNext()) {
925            Integer iVal = itr.next();
926            String val = iVal.toString();
927            if (!first) {
928                buf.append(",");
929            }
930            buf.append(val);
931            first = false;
932        }
933
934        return buf.toString();
935    }
936
937    protected int skipWhiteSpace(int i, String s) {
938        for (; i < s.length() && (s.charAt(i) == ' ' || s.charAt(i) == '\t'); i++) {
939            ;
940        }
941
942        return i;
943    }
944
945    protected int findNextWhiteSpace(int i, String s) {
946        for (; i < s.length() && (s.charAt(i) != ' ' || s.charAt(i) != '\t'); i++) {
947            ;
948        }
949
950        return i;
951    }
952
953    protected void addToSet(int val, int end, int incr, int type)
954        throws ParseException {
955        
956        TreeSet<Integer> set = getSet(type);
957
958        if (type == SECOND || type == MINUTE) {
959            if ((val < 0 || val > 59 || end > 59) && (val != ALL_SPEC_INT)) {
960                throw new ParseException(
961                        "Minute and Second values must be between 0 and 59",
962                        -1);
963            }
964        } else if (type == HOUR) {
965            if ((val < 0 || val > 23 || end > 23) && (val != ALL_SPEC_INT)) {
966                throw new ParseException(
967                        "Hour values must be between 0 and 23", -1);
968            }
969        } else if (type == DAY_OF_MONTH) {
970            if ((val < 1 || val > 31 || end > 31) && (val != ALL_SPEC_INT) 
971                    && (val != NO_SPEC_INT)) {
972                throw new ParseException(
973                        "Day of month values must be between 1 and 31", -1);
974            }
975        } else if (type == MONTH) {
976            if ((val < 1 || val > 12 || end > 12) && (val != ALL_SPEC_INT)) {
977                throw new ParseException(
978                        "Month values must be between 1 and 12", -1);
979            }
980        } else if (type == DAY_OF_WEEK) {
981            if ((val == 0 || val > 7 || end > 7) && (val != ALL_SPEC_INT)
982                    && (val != NO_SPEC_INT)) {
983                throw new ParseException(
984                        "Day-of-Week values must be between 1 and 7", -1);
985            }
986        }
987
988        if ((incr == 0 || incr == -1) && val != ALL_SPEC_INT) {
989            if (val != -1) {
990                set.add(val);
991            } else {
992                set.add(NO_SPEC);
993            }
994            
995            return;
996        }
997
998        int startAt = val;
999        int stopAt = end;
1000
1001        if (val == ALL_SPEC_INT && incr <= 0) {
1002            incr = 1;
1003            set.add(ALL_SPEC); // put in a marker, but also fill values
1004        }
1005
1006        if (type == SECOND || type == MINUTE) {
1007            if (stopAt == -1) {
1008                stopAt = 59;
1009            }
1010            if (startAt == -1 || startAt == ALL_SPEC_INT) {
1011                startAt = 0;
1012            }
1013        } else if (type == HOUR) {
1014            if (stopAt == -1) {
1015                stopAt = 23;
1016            }
1017            if (startAt == -1 || startAt == ALL_SPEC_INT) {
1018                startAt = 0;
1019            }
1020        } else if (type == DAY_OF_MONTH) {
1021            if (stopAt == -1) {
1022                stopAt = 31;
1023            }
1024            if (startAt == -1 || startAt == ALL_SPEC_INT) {
1025                startAt = 1;
1026            }
1027        } else if (type == MONTH) {
1028            if (stopAt == -1) {
1029                stopAt = 12;
1030            }
1031            if (startAt == -1 || startAt == ALL_SPEC_INT) {
1032                startAt = 1;
1033            }
1034        } else if (type == DAY_OF_WEEK) {
1035            if (stopAt == -1) {
1036                stopAt = 7;
1037            }
1038            if (startAt == -1 || startAt == ALL_SPEC_INT) {
1039                startAt = 1;
1040            }
1041        } else if (type == YEAR) {
1042            if (stopAt == -1) {
1043                stopAt = MAX_YEAR;
1044            }
1045            if (startAt == -1 || startAt == ALL_SPEC_INT) {
1046                startAt = 1970;
1047            }
1048        }
1049
1050        // if the end of the range is before the start, then we need to overflow into 
1051        // the next day, month etc. This is done by adding the maximum amount for that 
1052        // type, and using modulus max to determine the value being added.
1053        int max = -1;
1054        if (stopAt < startAt) {
1055            switch (type) {
1056              case       SECOND : max = 60; break;
1057              case       MINUTE : max = 60; break;
1058              case         HOUR : max = 24; break;
1059              case        MONTH : max = 12; break;
1060              case  DAY_OF_WEEK : max = 7;  break;
1061              case DAY_OF_MONTH : max = 31; break;
1062              case         YEAR : throw new IllegalArgumentException("Start year must be less than stop year");
1063              default           : throw new IllegalArgumentException("Unexpected type encountered");
1064            }
1065            stopAt += max;
1066        }
1067
1068        for (int i = startAt; i <= stopAt; i += incr) {
1069            if (max == -1) {
1070                // ie: there's no max to overflow over
1071                set.add(i);
1072            } else {
1073                // take the modulus to get the real value
1074                int i2 = i % max;
1075
1076                // 1-indexed ranges should not include 0, and should include their max
1077                if (i2 == 0 && (type == MONTH || type == DAY_OF_WEEK || type == DAY_OF_MONTH) ) {
1078                    i2 = max;
1079                }
1080
1081                set.add(i2);
1082            }
1083        }
1084    }
1085
1086    TreeSet<Integer> getSet(int type) {
1087        switch (type) {
1088            case SECOND:
1089                return seconds;
1090            case MINUTE:
1091                return minutes;
1092            case HOUR:
1093                return hours;
1094            case DAY_OF_MONTH:
1095                return daysOfMonth;
1096            case MONTH:
1097                return months;
1098            case DAY_OF_WEEK:
1099                return daysOfWeek;
1100            case YEAR:
1101                return years;
1102            default:
1103                return null;
1104        }
1105    }
1106
1107    protected ValueSet getValue(int v, String s, int i) {
1108        char c = s.charAt(i);
1109        StringBuilder s1 = new StringBuilder(String.valueOf(v));
1110        while (c >= '0' && c <= '9') {
1111            s1.append(c);
1112            i++;
1113            if (i >= s.length()) {
1114                break;
1115            }
1116            c = s.charAt(i);
1117        }
1118        ValueSet val = new ValueSet();
1119        
1120        val.pos = (i < s.length()) ? i : i + 1;
1121        val.value = Integer.parseInt(s1.toString());
1122        return val;
1123    }
1124
1125    protected int getNumericValue(String s, int i) {
1126        int endOfVal = findNextWhiteSpace(i, s);
1127        String val = s.substring(i, endOfVal);
1128        return Integer.parseInt(val);
1129    }
1130
1131    protected int getMonthNumber(String s) {
1132        Integer integer = monthMap.get(s);
1133
1134        if (integer == null) {
1135            return -1;
1136        }
1137
1138        return integer;
1139    }
1140
1141    protected int getDayOfWeekNumber(String s) {
1142        Integer integer = dayMap.get(s);
1143
1144        if (integer == null) {
1145            return -1;
1146        }
1147
1148        return integer;
1149    }
1150
1151    ////////////////////////////////////////////////////////////////////////////
1152    //
1153    // Computation Functions
1154    //
1155    ////////////////////////////////////////////////////////////////////////////
1156
1157    public Date getTimeAfter(Date afterTime) {
1158
1159        // Computation is based on Gregorian year only.
1160        Calendar cl = new java.util.GregorianCalendar(getTimeZone()); 
1161
1162        // move ahead one second, since we're computing the time *after* the
1163        // given time
1164        afterTime = new Date(afterTime.getTime() + 1000);
1165        // CronTrigger does not deal with milliseconds
1166        cl.setTime(afterTime);
1167        cl.set(Calendar.MILLISECOND, 0);
1168
1169        boolean gotOne = false;
1170        // loop until we've computed the next time, or we've past the endTime
1171        while (!gotOne) {
1172
1173            //if (endTime != null && cl.getTime().after(endTime)) return null;
1174            if(cl.get(Calendar.YEAR) > 2999) { // prevent endless loop...
1175                return null;
1176            }
1177
1178            SortedSet<Integer> st = null;
1179            int t = 0;
1180
1181            int sec = cl.get(Calendar.SECOND);
1182            int min = cl.get(Calendar.MINUTE);
1183
1184            // get second.................................................
1185            st = seconds.tailSet(sec);
1186            if (st != null && st.size() != 0) {
1187                sec = st.first();
1188            } else {
1189                sec = seconds.first();
1190                min++;
1191                cl.set(Calendar.MINUTE, min);
1192            }
1193            cl.set(Calendar.SECOND, sec);
1194
1195            min = cl.get(Calendar.MINUTE);
1196            int hr = cl.get(Calendar.HOUR_OF_DAY);
1197            t = -1;
1198
1199            // get minute.................................................
1200            st = minutes.tailSet(min);
1201            if (st != null && st.size() != 0) {
1202                t = min;
1203                min = st.first();
1204            } else {
1205                min = minutes.first();
1206                hr++;
1207            }
1208            if (min != t) {
1209                cl.set(Calendar.SECOND, 0);
1210                cl.set(Calendar.MINUTE, min);
1211                setCalendarHour(cl, hr);
1212                continue;
1213            }
1214            cl.set(Calendar.MINUTE, min);
1215
1216            hr = cl.get(Calendar.HOUR_OF_DAY);
1217            int day = cl.get(Calendar.DAY_OF_MONTH);
1218            t = -1;
1219
1220            // get hour...................................................
1221            st = hours.tailSet(hr);
1222            if (st != null && st.size() != 0) {
1223                t = hr;
1224                hr = st.first();
1225            } else {
1226                hr = hours.first();
1227                day++;
1228            }
1229            if (hr != t) {
1230                cl.set(Calendar.SECOND, 0);
1231                cl.set(Calendar.MINUTE, 0);
1232                cl.set(Calendar.DAY_OF_MONTH, day);
1233                setCalendarHour(cl, hr);
1234                continue;
1235            }
1236            cl.set(Calendar.HOUR_OF_DAY, hr);
1237
1238            day = cl.get(Calendar.DAY_OF_MONTH);
1239            int mon = cl.get(Calendar.MONTH) + 1;
1240            // '+ 1' because calendar is 0-based for this field, and we are
1241            // 1-based
1242            t = -1;
1243            int tmon = mon;
1244            
1245            // get day...................................................
1246            boolean dayOfMSpec = !daysOfMonth.contains(NO_SPEC);
1247            boolean dayOfWSpec = !daysOfWeek.contains(NO_SPEC);
1248            if (dayOfMSpec && !dayOfWSpec) { // get day by day of month rule
1249                st = daysOfMonth.tailSet(day);
1250                if (lastdayOfMonth) {
1251                    if(!nearestWeekday) {
1252                        t = day;
1253                        day = getLastDayOfMonth(mon, cl.get(Calendar.YEAR));
1254                        day -= lastdayOffset;
1255                        if(t > day) {
1256                            mon++;
1257                            if(mon > 12) { 
1258                                mon = 1;
1259                                tmon = 3333; // ensure test of mon != tmon further below fails
1260                                cl.add(Calendar.YEAR, 1);
1261                            }
1262                            day = 1;
1263                        }
1264                    } else {
1265                        t = day;
1266                        day = getLastDayOfMonth(mon, cl.get(Calendar.YEAR));
1267                        day -= lastdayOffset;
1268                        
1269                        java.util.Calendar tcal = java.util.Calendar.getInstance(getTimeZone());
1270                        tcal.set(Calendar.SECOND, 0);
1271                        tcal.set(Calendar.MINUTE, 0);
1272                        tcal.set(Calendar.HOUR_OF_DAY, 0);
1273                        tcal.set(Calendar.DAY_OF_MONTH, day);
1274                        tcal.set(Calendar.MONTH, mon - 1);
1275                        tcal.set(Calendar.YEAR, cl.get(Calendar.YEAR));
1276                        
1277                        int ldom = getLastDayOfMonth(mon, cl.get(Calendar.YEAR));
1278                        int dow = tcal.get(Calendar.DAY_OF_WEEK);
1279
1280                        if(dow == Calendar.SATURDAY && day == 1) {
1281                            day += 2;
1282                        } else if(dow == Calendar.SATURDAY) {
1283                            day -= 1;
1284                        } else if(dow == Calendar.SUNDAY && day == ldom) { 
1285                            day -= 2;
1286                        } else if(dow == Calendar.SUNDAY) { 
1287                            day += 1;
1288                        }
1289                    
1290                        tcal.set(Calendar.SECOND, sec);
1291                        tcal.set(Calendar.MINUTE, min);
1292                        tcal.set(Calendar.HOUR_OF_DAY, hr);
1293                        tcal.set(Calendar.DAY_OF_MONTH, day);
1294                        tcal.set(Calendar.MONTH, mon - 1);
1295                        Date nTime = tcal.getTime();
1296                        if(nTime.before(afterTime)) {
1297                            day = 1;
1298                            mon++;
1299                        }
1300                    }
1301                } else if(nearestWeekday) {
1302                    t = day;
1303                    day = daysOfMonth.first();
1304
1305                    java.util.Calendar tcal = java.util.Calendar.getInstance(getTimeZone());
1306                    tcal.set(Calendar.SECOND, 0);
1307                    tcal.set(Calendar.MINUTE, 0);
1308                    tcal.set(Calendar.HOUR_OF_DAY, 0);
1309                    tcal.set(Calendar.DAY_OF_MONTH, day);
1310                    tcal.set(Calendar.MONTH, mon - 1);
1311                    tcal.set(Calendar.YEAR, cl.get(Calendar.YEAR));
1312                    
1313                    int ldom = getLastDayOfMonth(mon, cl.get(Calendar.YEAR));
1314                    int dow = tcal.get(Calendar.DAY_OF_WEEK);
1315
1316                    if(dow == Calendar.SATURDAY && day == 1) {
1317                        day += 2;
1318                    } else if(dow == Calendar.SATURDAY) {
1319                        day -= 1;
1320                    } else if(dow == Calendar.SUNDAY && day == ldom) { 
1321                        day -= 2;
1322                    } else if(dow == Calendar.SUNDAY) { 
1323                        day += 1;
1324                    }
1325                        
1326                
1327                    tcal.set(Calendar.SECOND, sec);
1328                    tcal.set(Calendar.MINUTE, min);
1329                    tcal.set(Calendar.HOUR_OF_DAY, hr);
1330                    tcal.set(Calendar.DAY_OF_MONTH, day);
1331                    tcal.set(Calendar.MONTH, mon - 1);
1332                    Date nTime = tcal.getTime();
1333                    if(nTime.before(afterTime)) {
1334                        day = daysOfMonth.first();
1335                        mon++;
1336                    }
1337                } else if (st != null && st.size() != 0) {
1338                    t = day;
1339                    day = st.first();
1340                    // make sure we don't over-run a short month, such as february
1341                    int lastDay = getLastDayOfMonth(mon, cl.get(Calendar.YEAR));
1342                    if (day > lastDay) {
1343                        day = daysOfMonth.first();
1344                        mon++;
1345                    }
1346                } else {
1347                    day = daysOfMonth.first();
1348                    mon++;
1349                }
1350                
1351                if (day != t || mon != tmon) {
1352                    cl.set(Calendar.SECOND, 0);
1353                    cl.set(Calendar.MINUTE, 0);
1354                    cl.set(Calendar.HOUR_OF_DAY, 0);
1355                    cl.set(Calendar.DAY_OF_MONTH, day);
1356                    cl.set(Calendar.MONTH, mon - 1);
1357                    // '- 1' because calendar is 0-based for this field, and we
1358                    // are 1-based
1359                    continue;
1360                }
1361            } else if (dayOfWSpec && !dayOfMSpec) { // get day by day of week rule
1362                if (lastdayOfWeek) { // are we looking for the last XXX day of
1363                    // the month?
1364                    int dow = daysOfWeek.first(); // desired
1365                    // d-o-w
1366                    int cDow = cl.get(Calendar.DAY_OF_WEEK); // current d-o-w
1367                    int daysToAdd = 0;
1368                    if (cDow < dow) {
1369                        daysToAdd = dow - cDow;
1370                    }
1371                    if (cDow > dow) {
1372                        daysToAdd = dow + (7 - cDow);
1373                    }
1374
1375                    int lDay = getLastDayOfMonth(mon, cl.get(Calendar.YEAR));
1376
1377                    if (day + daysToAdd > lDay) { // did we already miss the
1378                        // last one?
1379                        cl.set(Calendar.SECOND, 0);
1380                        cl.set(Calendar.MINUTE, 0);
1381                        cl.set(Calendar.HOUR_OF_DAY, 0);
1382                        cl.set(Calendar.DAY_OF_MONTH, 1);
1383                        cl.set(Calendar.MONTH, mon);
1384                        // no '- 1' here because we are promoting the month
1385                        continue;
1386                    }
1387
1388                    // find date of last occurrence of this day in this month...
1389                    while ((day + daysToAdd + 7) <= lDay) {
1390                        daysToAdd += 7;
1391                    }
1392
1393                    day += daysToAdd;
1394
1395                    if (daysToAdd > 0) {
1396                        cl.set(Calendar.SECOND, 0);
1397                        cl.set(Calendar.MINUTE, 0);
1398                        cl.set(Calendar.HOUR_OF_DAY, 0);
1399                        cl.set(Calendar.DAY_OF_MONTH, day);
1400                        cl.set(Calendar.MONTH, mon - 1);
1401                        // '- 1' here because we are not promoting the month
1402                        continue;
1403                    }
1404
1405                } else if (nthdayOfWeek != 0) {
1406                    // are we looking for the Nth XXX day in the month?
1407                    int dow = daysOfWeek.first(); // desired
1408                    // d-o-w
1409                    int cDow = cl.get(Calendar.DAY_OF_WEEK); // current d-o-w
1410                    int daysToAdd = 0;
1411                    if (cDow < dow) {
1412                        daysToAdd = dow - cDow;
1413                    } else if (cDow > dow) {
1414                        daysToAdd = dow + (7 - cDow);
1415                    }
1416
1417                    boolean dayShifted = false;
1418                    if (daysToAdd > 0) {
1419                        dayShifted = true;
1420                    }
1421
1422                    day += daysToAdd;
1423                    int weekOfMonth = day / 7;
1424                    if (day % 7 > 0) {
1425                        weekOfMonth++;
1426                    }
1427
1428                    daysToAdd = (nthdayOfWeek - weekOfMonth) * 7;
1429                    day += daysToAdd;
1430                    if (daysToAdd < 0
1431                            || day > getLastDayOfMonth(mon, cl
1432                                    .get(Calendar.YEAR))) {
1433                        cl.set(Calendar.SECOND, 0);
1434                        cl.set(Calendar.MINUTE, 0);
1435                        cl.set(Calendar.HOUR_OF_DAY, 0);
1436                        cl.set(Calendar.DAY_OF_MONTH, 1);
1437                        cl.set(Calendar.MONTH, mon);
1438                        // no '- 1' here because we are promoting the month
1439                        continue;
1440                    } else if (daysToAdd > 0 || dayShifted) {
1441                        cl.set(Calendar.SECOND, 0);
1442                        cl.set(Calendar.MINUTE, 0);
1443                        cl.set(Calendar.HOUR_OF_DAY, 0);
1444                        cl.set(Calendar.DAY_OF_MONTH, day);
1445                        cl.set(Calendar.MONTH, mon - 1);
1446                        // '- 1' here because we are NOT promoting the month
1447                        continue;
1448                    }
1449                } else {
1450                    int cDow = cl.get(Calendar.DAY_OF_WEEK); // current d-o-w
1451                    int dow = daysOfWeek.first(); // desired
1452                    // d-o-w
1453                    st = daysOfWeek.tailSet(cDow);
1454                    if (st != null && st.size() > 0) {
1455                        dow = st.first();
1456                    }
1457
1458                    int daysToAdd = 0;
1459                    if (cDow < dow) {
1460                        daysToAdd = dow - cDow;
1461                    }
1462                    if (cDow > dow) {
1463                        daysToAdd = dow + (7 - cDow);
1464                    }
1465
1466                    int lDay = getLastDayOfMonth(mon, cl.get(Calendar.YEAR));
1467
1468                    if (day + daysToAdd > lDay) { // will we pass the end of
1469                        // the month?
1470                        cl.set(Calendar.SECOND, 0);
1471                        cl.set(Calendar.MINUTE, 0);
1472                        cl.set(Calendar.HOUR_OF_DAY, 0);
1473                        cl.set(Calendar.DAY_OF_MONTH, 1);
1474                        cl.set(Calendar.MONTH, mon);
1475                        // no '- 1' here because we are promoting the month
1476                        continue;
1477                    } else if (daysToAdd > 0) { // are we swithing days?
1478                        cl.set(Calendar.SECOND, 0);
1479                        cl.set(Calendar.MINUTE, 0);
1480                        cl.set(Calendar.HOUR_OF_DAY, 0);
1481                        cl.set(Calendar.DAY_OF_MONTH, day + daysToAdd);
1482                        cl.set(Calendar.MONTH, mon - 1);
1483                        // '- 1' because calendar is 0-based for this field,
1484                        // and we are 1-based
1485                        continue;
1486                    }
1487                }
1488            } else { // dayOfWSpec && !dayOfMSpec
1489                throw new UnsupportedOperationException(
1490                        "Support for specifying both a day-of-week AND a day-of-month parameter is not implemented.");
1491            }
1492            cl.set(Calendar.DAY_OF_MONTH, day);
1493
1494            mon = cl.get(Calendar.MONTH) + 1;
1495            // '+ 1' because calendar is 0-based for this field, and we are
1496            // 1-based
1497            int year = cl.get(Calendar.YEAR);
1498            t = -1;
1499
1500            // test for expressions that never generate a valid fire date,
1501            // but keep looping...
1502            if (year > MAX_YEAR) {
1503                return null;
1504            }
1505
1506            // get month...................................................
1507            st = months.tailSet(mon);
1508            if (st != null && st.size() != 0) {
1509                t = mon;
1510                mon = st.first();
1511            } else {
1512                mon = months.first();
1513                year++;
1514            }
1515            if (mon != t) {
1516                cl.set(Calendar.SECOND, 0);
1517                cl.set(Calendar.MINUTE, 0);
1518                cl.set(Calendar.HOUR_OF_DAY, 0);
1519                cl.set(Calendar.DAY_OF_MONTH, 1);
1520                cl.set(Calendar.MONTH, mon - 1);
1521                // '- 1' because calendar is 0-based for this field, and we are
1522                // 1-based
1523                cl.set(Calendar.YEAR, year);
1524                continue;
1525            }
1526            cl.set(Calendar.MONTH, mon - 1);
1527            // '- 1' because calendar is 0-based for this field, and we are
1528            // 1-based
1529
1530            year = cl.get(Calendar.YEAR);
1531            t = -1;
1532
1533            // get year...................................................
1534            st = years.tailSet(year);
1535            if (st != null && st.size() != 0) {
1536                t = year;
1537                year = st.first();
1538            } else {
1539                return null; // ran out of years...
1540            }
1541
1542            if (year != t) {
1543                cl.set(Calendar.SECOND, 0);
1544                cl.set(Calendar.MINUTE, 0);
1545                cl.set(Calendar.HOUR_OF_DAY, 0);
1546                cl.set(Calendar.DAY_OF_MONTH, 1);
1547                cl.set(Calendar.MONTH, 0);
1548                // '- 1' because calendar is 0-based for this field, and we are
1549                // 1-based
1550                cl.set(Calendar.YEAR, year);
1551                continue;
1552            }
1553            cl.set(Calendar.YEAR, year);
1554
1555            gotOne = true;
1556        } // while( !done )
1557
1558        return cl.getTime();
1559    }
1560
1561    /**
1562     * Advance the calendar to the particular hour paying particular attention
1563     * to daylight saving problems.
1564     * 
1565     * @param cal the calendar to operate on
1566     * @param hour the hour to set
1567     */
1568    protected void setCalendarHour(Calendar cal, int hour) {
1569        cal.set(java.util.Calendar.HOUR_OF_DAY, hour);
1570        if (cal.get(java.util.Calendar.HOUR_OF_DAY) != hour && hour != 24) {
1571            cal.set(java.util.Calendar.HOUR_OF_DAY, hour + 1);
1572        }
1573    }
1574
1575    /**
1576     * NOT YET IMPLEMENTED: Returns the time before the given time
1577     * that the <code>CronExpression</code> matches.
1578     */ 
1579    public Date getTimeBefore(Date endTime) { 
1580        // FUTURE_TODO: implement QUARTZ-423
1581        return null;
1582    }
1583
1584    /**
1585     * NOT YET IMPLEMENTED: Returns the final time that the 
1586     * <code>CronExpression</code> will match.
1587     */
1588    public Date getFinalFireTime() {
1589        // FUTURE_TODO: implement QUARTZ-423
1590        return null;
1591    }
1592    
1593    protected boolean isLeapYear(int year) {
1594        return ((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0));
1595    }
1596
1597    protected int getLastDayOfMonth(int monthNum, int year) {
1598
1599        switch (monthNum) {
1600            case 1:
1601                return 31;
1602            case 2:
1603                return (isLeapYear(year)) ? 29 : 28;
1604            case 3:
1605                return 31;
1606            case 4:
1607                return 30;
1608            case 5:
1609                return 31;
1610            case 6:
1611                return 30;
1612            case 7:
1613                return 31;
1614            case 8:
1615                return 31;
1616            case 9:
1617                return 30;
1618            case 10:
1619                return 31;
1620            case 11:
1621                return 30;
1622            case 12:
1623                return 31;
1624            default:
1625                throw new IllegalArgumentException("Illegal month number: "
1626                        + monthNum);
1627        }
1628    }
1629    
1630
1631    private void readObject(java.io.ObjectInputStream stream)
1632        throws java.io.IOException, ClassNotFoundException {
1633        
1634        stream.defaultReadObject();
1635        try {
1636            buildExpression(cronExpression);
1637        } catch (Exception ignore) {
1638        } // never happens
1639    }    
1640    
1641    @Override
1642    @Deprecated
1643    public Object clone() {
1644        return new CronExpression(this);
1645    }
1646}
1647
1648class ValueSet {
1649    public int value;
1650
1651    public int pos;
1652}