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