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                    switch (c) {
539                    case '-':
540                        i += 4;
541                        sub = s.substring(i, i + 3);
542                        eval = getDayOfWeekNumber(sub);
543                        if (eval < 0) {
544                            throw new ParseException(
545                                    "Invalid Day-of-Week value: '" + sub
546                                            + "'", i);
547                        }
548                        break;
549                    case '#':
550                        try {
551                            i += 4;
552                            nthdayOfWeek = Integers.parseInt(s.substring(i));
553                            if (nthdayOfWeek < 1 || nthdayOfWeek > 5) {
554                                throw new Exception();
555                            }
556                        } catch (final Exception e) {
557                            throw new ParseException(
558                                    "A numeric value between 1 and 5 must follow the '#' option",
559                                    i);
560                        }
561                        break;
562                    case 'L':
563                        lastdayOfWeek = true;
564                        i++;
565                        break;
566                    default:
567                        break;
568                    }
569                }
570
571            } else {
572                throw new ParseException(
573                        "Illegal characters for this position: '" + sub + "'",
574                        i);
575            }
576            if (eval != -1) {
577                incr = 1;
578            }
579            addToSet(sval, eval, incr, type);
580            return (i + 3);
581        }
582
583        switch (c) {
584        case '?':
585            i++;
586            if ((i + 1) < s.length()
587                    && (s.charAt(i) != ' ' && s.charAt(i + 1) != '\t')) {
588                throw new ParseException("Illegal character after '?': "
589                        + s.charAt(i), i);
590            }
591            if (type != DAY_OF_WEEK && type != DAY_OF_MONTH) {
592                throw new ParseException(
593                        "'?' can only be specfied for Day-of-Month or Day-of-Week.",
594                        i);
595            }
596            if (type == DAY_OF_WEEK && !lastdayOfMonth) {
597                final int val = daysOfMonth.last();
598                if (val == NO_SPEC_INT) {
599                    throw new ParseException(
600                            "'?' can only be specfied for Day-of-Month -OR- Day-of-Week.",
601                            i);
602                }
603            }
604            addToSet(NO_SPEC_INT, -1, 0, type);
605            return i;
606        case '*':
607        case '/':
608            if (c == '*' && (i + 1) >= s.length()) {
609                addToSet(ALL_SPEC_INT, -1, incr, type);
610                return i + 1;
611            } else if (c == '/'
612                    && ((i + 1) >= s.length() || s.charAt(i + 1) == ' ' || s
613                    .charAt(i + 1) == '\t')) {
614                throw new ParseException("'/' must be followed by an integer.", i);
615            } else if (c == '*') {
616                i++;
617            }
618            c = s.charAt(i);
619            if (c == '/') { // is an increment specified?
620                i++;
621                if (i >= s.length()) {
622                    throw new ParseException("Unexpected end of string.", i);
623                }
624
625                incr = getNumericValue(s, i);
626
627                i++;
628                if (incr > 10) {
629                    i++;
630                }
631                if (incr > 59 && (type == SECOND || type == MINUTE)) {
632                    throw new ParseException("Increment > 60 : " + incr, i);
633                } else if (incr > 23 && (type == HOUR)) {
634                    throw new ParseException("Increment > 24 : " + incr, i);
635                } else if (incr > 31 && (type == DAY_OF_MONTH)) {
636                    throw new ParseException("Increment > 31 : " + incr, i);
637                } else if (incr > 7 && (type == DAY_OF_WEEK)) {
638                    throw new ParseException("Increment > 7 : " + incr, i);
639                } else if (incr > 12 && (type == MONTH)) {
640                    throw new ParseException("Increment > 12 : " + incr, i);
641                }
642            } else {
643                incr = 1;
644            }
645            addToSet(ALL_SPEC_INT, -1, incr, type);
646            return i;
647        case 'L':
648            i++;
649            if (type == DAY_OF_MONTH) {
650                lastdayOfMonth = true;
651            }
652            if (type == DAY_OF_WEEK) {
653                addToSet(7, 7, 0, type);
654            }
655            if (type == DAY_OF_MONTH && s.length() > i) {
656                c = s.charAt(i);
657                if (c == '-') {
658                    final ValueSet vs = getValue(0, s, i + 1);
659                    lastdayOffset = vs.value;
660                    if (lastdayOffset > 30) {
661                        throw new ParseException("Offset from last day must be <= 30", i + 1);
662                    }
663                    i = vs.pos;
664                }
665                if (s.length() > i) {
666                    c = s.charAt(i);
667                    if (c == 'W') {
668                        nearestWeekday = true;
669                        i++;
670                    }
671                }
672            }
673            return i;
674        default:
675            if (c >= '0' && c <= '9') {
676                int val = Integer.parseInt(String.valueOf(c));
677                i++;
678                if (i >= s.length()) {
679                    addToSet(val, -1, -1, type);
680                } else {
681                    c = s.charAt(i);
682                    if (c >= '0' && c <= '9') {
683                        final ValueSet vs = getValue(val, s, i);
684                        val = vs.value;
685                        i = vs.pos;
686                    }
687                    i = checkNext(i, s, val, type);
688                    return i;
689                }
690            } else {
691                throw new ParseException("Unexpected character: " + c, i);
692            }
693            break;
694        }
695
696        return i;
697    }
698
699    protected int checkNext(final int pos, final String s, final int val, final int type)
700            throws ParseException {
701
702        int end = -1;
703        int i = pos;
704
705        if (i >= s.length()) {
706            addToSet(val, end, -1, type);
707            return i;
708        }
709
710        char c = s.charAt(pos);
711
712        if (c == 'L') {
713            if (type == DAY_OF_WEEK) {
714                if (val < 1 || val > 7) {
715                    throw new ParseException("Day-of-Week values must be between 1 and 7", -1);
716                }
717                lastdayOfWeek = true;
718            } else {
719                throw new ParseException("'L' option is not valid here. (pos=" + i + ")", i);
720            }
721            final TreeSet<Integer> set = getSet(type);
722            set.add(val);
723            i++;
724            return i;
725        }
726
727        if (c == 'W') {
728            if (type == DAY_OF_MONTH) {
729                nearestWeekday = true;
730            } else {
731                throw new ParseException("'W' option is not valid here. (pos=" + i + ")", i);
732            }
733            if (val > 31) {
734                throw new ParseException("The 'W' option does not make sense with values larger than 31 (max number of days in a month)", i);
735            }
736            final TreeSet<Integer> set = getSet(type);
737            set.add(val);
738            i++;
739            return i;
740        }
741
742        switch (c) {
743        case '#':
744            if (type != DAY_OF_WEEK) {
745                throw new ParseException("'#' option is not valid here. (pos=" + i + ")", i);
746            }
747            i++;
748            try {
749                nthdayOfWeek = Integers.parseInt(s.substring(i));
750                if (nthdayOfWeek < 1 || nthdayOfWeek > 5) {
751                    throw new Exception();
752                }
753            } catch (final Exception e) {
754                throw new ParseException(
755                        "A numeric value between 1 and 5 must follow the '#' option",
756                        i);
757            }
758            final TreeSet<Integer> set = getSet(type);
759            set.add(val);
760            i++;
761            return i;
762        case '-':
763            i++;
764            c = s.charAt(i);
765            final int v = Integer.parseInt(String.valueOf(c));
766            end = v;
767            i++;
768            if (i >= s.length()) {
769                addToSet(val, end, 1, type);
770                return i;
771            }
772            c = s.charAt(i);
773            if (c >= '0' && c <= '9') {
774                final ValueSet vs = getValue(v, s, i);
775                end = vs.value;
776                i = vs.pos;
777            }
778            if (i < s.length() && ((c = s.charAt(i)) == '/')) {
779                i++;
780                c = s.charAt(i);
781                final int v2 = Integer.parseInt(String.valueOf(c));
782                i++;
783                if (i >= s.length()) {
784                    addToSet(val, end, v2, type);
785                    return i;
786                }
787                c = s.charAt(i);
788                if (c >= '0' && c <= '9') {
789                    final ValueSet vs = getValue(v2, s, i);
790                    final int v3 = vs.value;
791                    addToSet(val, end, v3, type);
792                    i = vs.pos;
793                } else {
794                    addToSet(val, end, v2, type);
795                }
796                return i;
797            } else {
798                addToSet(val, end, 1, type);
799                return i;
800            }
801        case '/':
802            i++;
803            c = s.charAt(i);
804            final int v2 = Integer.parseInt(String.valueOf(c));
805            i++;
806            if (i >= s.length()) {
807                addToSet(val, end, v2, type);
808                return i;
809            }
810            c = s.charAt(i);
811            if (c >= '0' && c <= '9') {
812                final ValueSet vs = getValue(v2, s, i);
813                final int v3 = vs.value;
814                addToSet(val, end, v3, type);
815                i = vs.pos;
816                return i;
817            } else {
818                throw new ParseException("Unexpected character '" + c + "' after '/'", i);
819            }
820        default:
821            break;
822        }
823
824        addToSet(val, end, 0, type);
825        i++;
826        return i;
827    }
828
829    public String getCronExpression() {
830        return cronExpression;
831    }
832
833    public String getExpressionSummary() {
834        final StringBuilder buf = new StringBuilder();
835
836        buf.append("seconds: ");
837        buf.append(getExpressionSetSummary(seconds));
838        buf.append("\n");
839        buf.append("minutes: ");
840        buf.append(getExpressionSetSummary(minutes));
841        buf.append("\n");
842        buf.append("hours: ");
843        buf.append(getExpressionSetSummary(hours));
844        buf.append("\n");
845        buf.append("daysOfMonth: ");
846        buf.append(getExpressionSetSummary(daysOfMonth));
847        buf.append("\n");
848        buf.append("months: ");
849        buf.append(getExpressionSetSummary(months));
850        buf.append("\n");
851        buf.append("daysOfWeek: ");
852        buf.append(getExpressionSetSummary(daysOfWeek));
853        buf.append("\n");
854        buf.append("lastdayOfWeek: ");
855        buf.append(lastdayOfWeek);
856        buf.append("\n");
857        buf.append("nearestWeekday: ");
858        buf.append(nearestWeekday);
859        buf.append("\n");
860        buf.append("NthDayOfWeek: ");
861        buf.append(nthdayOfWeek);
862        buf.append("\n");
863        buf.append("lastdayOfMonth: ");
864        buf.append(lastdayOfMonth);
865        buf.append("\n");
866        buf.append("years: ");
867        buf.append(getExpressionSetSummary(years));
868        buf.append("\n");
869
870        return buf.toString();
871    }
872
873    protected String getExpressionSetSummary(final java.util.Set<Integer> set) {
874
875        if (set.contains(NO_SPEC)) {
876            return "?";
877        }
878        if (set.contains(ALL_SPEC)) {
879            return "*";
880        }
881
882        final StringBuilder buf = new StringBuilder();
883
884        final Iterator<Integer> itr = set.iterator();
885        boolean first = true;
886        while (itr.hasNext()) {
887            final Integer iVal = itr.next();
888            final String val = iVal.toString();
889            if (!first) {
890                buf.append(",");
891            }
892            buf.append(val);
893            first = false;
894        }
895
896        return buf.toString();
897    }
898
899    protected String getExpressionSetSummary(final java.util.ArrayList<Integer> list) {
900
901        if (list.contains(NO_SPEC)) {
902            return "?";
903        }
904        if (list.contains(ALL_SPEC)) {
905            return "*";
906        }
907
908        final StringBuilder buf = new StringBuilder();
909
910        final Iterator<Integer> itr = list.iterator();
911        boolean first = true;
912        while (itr.hasNext()) {
913            final Integer iVal = itr.next();
914            final String val = iVal.toString();
915            if (!first) {
916                buf.append(",");
917            }
918            buf.append(val);
919            first = false;
920        }
921
922        return buf.toString();
923    }
924
925    protected int skipWhiteSpace(int i, final String s) {
926        for (; i < s.length() && (s.charAt(i) == ' ' || s.charAt(i) == '\t'); i++) {
927            // empty
928        }
929
930        return i;
931    }
932
933    protected int findNextWhiteSpace(int i, final String s) {
934        for (; i < s.length() && (s.charAt(i) != ' ' || s.charAt(i) != '\t'); i++) {
935            // empty
936        }
937
938        return i;
939    }
940
941    protected void addToSet(final int val, final int end, int incr, final int type)
942            throws ParseException {
943
944        final TreeSet<Integer> set = getSet(type);
945
946        switch (type) {
947        case SECOND:
948        case MINUTE:
949            if ((val < 0 || val > 59 || end > 59) && (val != ALL_SPEC_INT)) {
950                throw new ParseException(
951                        "Minute and Second values must be between 0 and 59",
952                        -1);
953            }
954            break;
955        case HOUR:
956            if ((val < 0 || val > 23 || end > 23) && (val != ALL_SPEC_INT)) {
957                throw new ParseException(
958                        "Hour values must be between 0 and 23", -1);
959            }
960            break;
961        case DAY_OF_MONTH:
962            if ((val < 1 || val > 31 || end > 31) && (val != ALL_SPEC_INT)
963                    && (val != NO_SPEC_INT)) {
964                throw new ParseException(
965                        "Day of month values must be between 1 and 31", -1);
966            }
967            break;
968        case MONTH:
969            if ((val < 1 || val > 12 || end > 12) && (val != ALL_SPEC_INT)) {
970                throw new ParseException(
971                        "Month values must be between 1 and 12", -1);
972            }
973            break;
974        case DAY_OF_WEEK:
975            if ((val == 0 || val > 7 || end > 7) && (val != ALL_SPEC_INT)
976                    && (val != NO_SPEC_INT)) {
977                throw new ParseException(
978                        "Day-of-Week values must be between 1 and 7", -1);
979            }
980            break;
981        default:
982            break;
983        }
984
985        if ((incr == 0 || incr == -1) && val != ALL_SPEC_INT) {
986            if (val != -1) {
987                set.add(val);
988            } else {
989                set.add(NO_SPEC);
990            }
991
992            return;
993        }
994
995        int startAt = val;
996        int stopAt = end;
997
998        if (val == ALL_SPEC_INT && incr <= 0) {
999            incr = 1;
1000            set.add(ALL_SPEC); // put in a marker, but also fill values
1001        }
1002
1003        switch (type) {
1004        case SECOND:
1005        case MINUTE:
1006            if (stopAt == -1) {
1007                stopAt = 59;
1008            }
1009            if (startAt == -1 || startAt == ALL_SPEC_INT) {
1010                startAt = 0;
1011            }
1012            break;
1013        case HOUR:
1014            if (stopAt == -1) {
1015                stopAt = 23;
1016            }
1017            if (startAt == -1 || startAt == ALL_SPEC_INT) {
1018                startAt = 0;
1019            }
1020            break;
1021        case DAY_OF_MONTH:
1022            if (stopAt == -1) {
1023                stopAt = 31;
1024            }
1025            if (startAt == -1 || startAt == ALL_SPEC_INT) {
1026                startAt = 1;
1027            }
1028            break;
1029        case MONTH:
1030            if (stopAt == -1) {
1031                stopAt = 12;
1032            }
1033            if (startAt == -1 || startAt == ALL_SPEC_INT) {
1034                startAt = 1;
1035            }
1036            break;
1037        case DAY_OF_WEEK:
1038            if (stopAt == -1) {
1039                stopAt = 7;
1040            }
1041            if (startAt == -1 || startAt == ALL_SPEC_INT) {
1042                startAt = 1;
1043            }
1044            break;
1045        case YEAR:
1046            if (stopAt == -1) {
1047                stopAt = MAX_YEAR;
1048            }
1049            if (startAt == -1 || startAt == ALL_SPEC_INT) {
1050                startAt = 1970;
1051            }
1052            break;
1053        default:
1054            break;
1055        }
1056
1057        // if the end of the range is before the start, then we need to overflow into
1058        // the next day, month etc. This is done by adding the maximum amount for that
1059        // type, and using modulus max to determine the value being added.
1060        int max = -1;
1061        if (stopAt < startAt) {
1062            switch (type) {
1063                case SECOND:
1064                    max = 60;
1065                    break;
1066                case MINUTE:
1067                    max = 60;
1068                    break;
1069                case HOUR:
1070                    max = 24;
1071                    break;
1072                case MONTH:
1073                    max = 12;
1074                    break;
1075                case DAY_OF_WEEK:
1076                    max = 7;
1077                    break;
1078                case DAY_OF_MONTH:
1079                    max = 31;
1080                    break;
1081                case YEAR:
1082                    throw new IllegalArgumentException("Start year must be less than stop year");
1083                default:
1084                    throw new IllegalArgumentException("Unexpected type encountered");
1085            }
1086            stopAt += max;
1087        }
1088
1089        for (int i = startAt; i <= stopAt; i += incr) {
1090            if (max == -1) {
1091                // ie: there's no max to overflow over
1092                set.add(i);
1093            } else {
1094                // take the modulus to get the real value
1095                int i2 = i % max;
1096
1097                // 1-indexed ranges should not include 0, and should include their max
1098                if (i2 == 0 && (type == MONTH || type == DAY_OF_WEEK || type == DAY_OF_MONTH)) {
1099                    i2 = max;
1100                }
1101
1102                set.add(i2);
1103            }
1104        }
1105    }
1106
1107    TreeSet<Integer> getSet(final int type) {
1108        switch (type) {
1109            case SECOND:
1110                return seconds;
1111            case MINUTE:
1112                return minutes;
1113            case HOUR:
1114                return hours;
1115            case DAY_OF_MONTH:
1116                return daysOfMonth;
1117            case MONTH:
1118                return months;
1119            case DAY_OF_WEEK:
1120                return daysOfWeek;
1121            case YEAR:
1122                return years;
1123            default:
1124                return null;
1125        }
1126    }
1127
1128    protected ValueSet getValue(final int v, final String s, int i) {
1129        char c = s.charAt(i);
1130        final StringBuilder s1 = new StringBuilder(String.valueOf(v));
1131        while (c >= '0' && c <= '9') {
1132            s1.append(c);
1133            i++;
1134            if (i >= s.length()) {
1135                break;
1136            }
1137            c = s.charAt(i);
1138        }
1139        final ValueSet val = new ValueSet();
1140
1141        val.pos = (i < s.length()) ? i : i + 1;
1142        val.value = Integers.parseInt(s1.toString());
1143        return val;
1144    }
1145
1146    protected int getNumericValue(final String s, final int i) {
1147        final int endOfVal = findNextWhiteSpace(i, s);
1148        final String val = s.substring(i, endOfVal);
1149        return Integers.parseInt(val);
1150    }
1151
1152    protected int getMonthNumber(final String s) {
1153        final Integer integer = monthMap.get(s);
1154
1155        if (integer == null) {
1156            return -1;
1157        }
1158
1159        return integer;
1160    }
1161
1162    protected int getDayOfWeekNumber(final String s) {
1163        final Integer integer = dayMap.get(s);
1164
1165        if (integer == null) {
1166            return -1;
1167        }
1168
1169        return integer;
1170    }
1171
1172    ////////////////////////////////////////////////////////////////////////////
1173    //
1174    // Computation Functions
1175    //
1176    ////////////////////////////////////////////////////////////////////////////
1177
1178    public Date getTimeAfter(Date afterTime) {
1179
1180        // Computation is based on Gregorian year only.
1181        final Calendar cl = new java.util.GregorianCalendar(getTimeZone());
1182
1183        // move ahead one second, since we're computing the time *after* the
1184        // given time
1185        afterTime = new Date(afterTime.getTime() + 1000);
1186        // CronTrigger does not deal with milliseconds
1187        cl.setTime(afterTime);
1188        cl.set(Calendar.MILLISECOND, 0);
1189
1190        boolean gotOne = false;
1191        // loop until we've computed the next time, or we've past the endTime
1192        while (!gotOne) {
1193            //if (endTime != null && cl.getTime().after(endTime)) return null;
1194            if (cl.get(Calendar.YEAR) > 2999) { // prevent endless loop...
1195                return null;
1196            }
1197
1198            int sec = cl.get(Calendar.SECOND);
1199            int min = cl.get(Calendar.MINUTE);
1200
1201            // get second.................................................
1202            SortedSet<Integer> st = seconds.tailSet(sec);
1203            if (st != null && st.size() != 0) {
1204                sec = st.first();
1205            } else {
1206                sec = seconds.first();
1207                min++;
1208                cl.set(Calendar.MINUTE, min);
1209            }
1210            cl.set(Calendar.SECOND, sec);
1211
1212            min = cl.get(Calendar.MINUTE);
1213            int hr = cl.get(Calendar.HOUR_OF_DAY);
1214            int t = -1;
1215
1216            // get minute.................................................
1217            st = minutes.tailSet(min);
1218            if (st != null && st.size() != 0) {
1219                t = min;
1220                min = st.first();
1221            } else {
1222                min = minutes.first();
1223                hr++;
1224            }
1225            if (min != t) {
1226                cl.set(Calendar.SECOND, 0);
1227                cl.set(Calendar.MINUTE, min);
1228                setCalendarHour(cl, hr);
1229                continue;
1230            }
1231            cl.set(Calendar.MINUTE, min);
1232
1233            hr = cl.get(Calendar.HOUR_OF_DAY);
1234            int day = cl.get(Calendar.DAY_OF_MONTH);
1235            t = -1;
1236
1237            // get hour...................................................
1238            st = hours.tailSet(hr);
1239            if (st != null && st.size() != 0) {
1240                t = hr;
1241                hr = st.first();
1242            } else {
1243                hr = hours.first();
1244                day++;
1245            }
1246            if (hr != t) {
1247                cl.set(Calendar.SECOND, 0);
1248                cl.set(Calendar.MINUTE, 0);
1249                cl.set(Calendar.DAY_OF_MONTH, day);
1250                setCalendarHour(cl, hr);
1251                continue;
1252            }
1253            cl.set(Calendar.HOUR_OF_DAY, hr);
1254
1255            day = cl.get(Calendar.DAY_OF_MONTH);
1256            int mon = cl.get(Calendar.MONTH) + 1;
1257            // '+ 1' because calendar is 0-based for this field, and we are
1258            // 1-based
1259            t = -1;
1260            int tmon = mon;
1261
1262            // get day...................................................
1263            final boolean dayOfMSpec = !daysOfMonth.contains(NO_SPEC);
1264            final boolean dayOfWSpec = !daysOfWeek.contains(NO_SPEC);
1265            if (dayOfMSpec && !dayOfWSpec) { // get day by day of month rule
1266                st = daysOfMonth.tailSet(day);
1267                if (lastdayOfMonth) {
1268                    if (!nearestWeekday) {
1269                        t = day;
1270                        day = getLastDayOfMonth(mon, cl.get(Calendar.YEAR));
1271                        day -= lastdayOffset;
1272                        if (t > day) {
1273                            mon++;
1274                            if (mon > 12) {
1275                                mon = 1;
1276                                tmon = 3333; // ensure test of mon != tmon further below fails
1277                                cl.add(Calendar.YEAR, 1);
1278                            }
1279                            day = 1;
1280                        }
1281                    } else {
1282                        t = day;
1283                        day = getLastDayOfMonth(mon, cl.get(Calendar.YEAR));
1284                        day -= lastdayOffset;
1285
1286                        final java.util.Calendar tcal = java.util.Calendar.getInstance(getTimeZone());
1287                        tcal.set(Calendar.SECOND, 0);
1288                        tcal.set(Calendar.MINUTE, 0);
1289                        tcal.set(Calendar.HOUR_OF_DAY, 0);
1290                        tcal.set(Calendar.DAY_OF_MONTH, day);
1291                        tcal.set(Calendar.MONTH, mon - 1);
1292                        tcal.set(Calendar.YEAR, cl.get(Calendar.YEAR));
1293
1294                        final int ldom = getLastDayOfMonth(mon, cl.get(Calendar.YEAR));
1295                        final int dow = tcal.get(Calendar.DAY_OF_WEEK);
1296
1297                        if (dow == Calendar.SATURDAY && day == 1) {
1298                            day += 2;
1299                        } else if (dow == Calendar.SATURDAY) {
1300                            day -= 1;
1301                        } else if (dow == Calendar.SUNDAY && day == ldom) {
1302                            day -= 2;
1303                        } else if (dow == Calendar.SUNDAY) {
1304                            day += 1;
1305                        }
1306
1307                        tcal.set(Calendar.SECOND, sec);
1308                        tcal.set(Calendar.MINUTE, min);
1309                        tcal.set(Calendar.HOUR_OF_DAY, hr);
1310                        tcal.set(Calendar.DAY_OF_MONTH, day);
1311                        tcal.set(Calendar.MONTH, mon - 1);
1312                        final Date nTime = tcal.getTime();
1313                        if (nTime.before(afterTime)) {
1314                            day = 1;
1315                            mon++;
1316                        }
1317                    }
1318                } else if (nearestWeekday) {
1319                    t = day;
1320                    day = daysOfMonth.first();
1321
1322                    final java.util.Calendar tcal = java.util.Calendar.getInstance(getTimeZone());
1323                    tcal.set(Calendar.SECOND, 0);
1324                    tcal.set(Calendar.MINUTE, 0);
1325                    tcal.set(Calendar.HOUR_OF_DAY, 0);
1326                    tcal.set(Calendar.DAY_OF_MONTH, day);
1327                    tcal.set(Calendar.MONTH, mon - 1);
1328                    tcal.set(Calendar.YEAR, cl.get(Calendar.YEAR));
1329
1330                    final int ldom = getLastDayOfMonth(mon, cl.get(Calendar.YEAR));
1331                    final int dow = tcal.get(Calendar.DAY_OF_WEEK);
1332
1333                    if (dow == Calendar.SATURDAY && day == 1) {
1334                        day += 2;
1335                    } else if (dow == Calendar.SATURDAY) {
1336                        day -= 1;
1337                    } else if (dow == Calendar.SUNDAY && day == ldom) {
1338                        day -= 2;
1339                    } else if (dow == Calendar.SUNDAY) {
1340                        day += 1;
1341                    }
1342
1343
1344                    tcal.set(Calendar.SECOND, sec);
1345                    tcal.set(Calendar.MINUTE, min);
1346                    tcal.set(Calendar.HOUR_OF_DAY, hr);
1347                    tcal.set(Calendar.DAY_OF_MONTH, day);
1348                    tcal.set(Calendar.MONTH, mon - 1);
1349                    final Date nTime = tcal.getTime();
1350                    if (nTime.before(afterTime)) {
1351                        day = daysOfMonth.first();
1352                        mon++;
1353                    }
1354                } else if (st != null && st.size() != 0) {
1355                    t = day;
1356                    day = st.first();
1357                    // make sure we don't over-run a short month, such as february
1358                    final int lastDay = getLastDayOfMonth(mon, cl.get(Calendar.YEAR));
1359                    if (day > lastDay) {
1360                        day = daysOfMonth.first();
1361                        mon++;
1362                    }
1363                } else {
1364                    day = daysOfMonth.first();
1365                    mon++;
1366                }
1367
1368                if (day != t || mon != tmon) {
1369                    cl.set(Calendar.SECOND, 0);
1370                    cl.set(Calendar.MINUTE, 0);
1371                    cl.set(Calendar.HOUR_OF_DAY, 0);
1372                    cl.set(Calendar.DAY_OF_MONTH, day);
1373                    cl.set(Calendar.MONTH, mon - 1);
1374                    // '- 1' because calendar is 0-based for this field, and we
1375                    // are 1-based
1376                    continue;
1377                }
1378            } else if (dayOfWSpec && !dayOfMSpec) { // get day by day of week rule
1379                if (lastdayOfWeek) { // are we looking for the last XXX day of
1380                    // the month?
1381                    final int dow = daysOfWeek.first(); // desired
1382                    // d-o-w
1383                    final int cDow = cl.get(Calendar.DAY_OF_WEEK); // current d-o-w
1384                    int daysToAdd = 0;
1385                    if (cDow < dow) {
1386                        daysToAdd = dow - cDow;
1387                    }
1388                    if (cDow > dow) {
1389                        daysToAdd = dow + (7 - cDow);
1390                    }
1391
1392                    final int lDay = getLastDayOfMonth(mon, cl.get(Calendar.YEAR));
1393
1394                    if (day + daysToAdd > lDay) { // did we already miss the
1395                        // last one?
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, 1);
1400                        cl.set(Calendar.MONTH, mon);
1401                        // no '- 1' here because we are promoting the month
1402                        continue;
1403                    }
1404
1405                    // find date of last occurrence of this day in this month...
1406                    while ((day + daysToAdd + 7) <= lDay) {
1407                        daysToAdd += 7;
1408                    }
1409
1410                    day += daysToAdd;
1411
1412                    if (daysToAdd > 0) {
1413                        cl.set(Calendar.SECOND, 0);
1414                        cl.set(Calendar.MINUTE, 0);
1415                        cl.set(Calendar.HOUR_OF_DAY, 0);
1416                        cl.set(Calendar.DAY_OF_MONTH, day);
1417                        cl.set(Calendar.MONTH, mon - 1);
1418                        // '- 1' here because we are not promoting the month
1419                        continue;
1420                    }
1421
1422                } else if (nthdayOfWeek != 0) {
1423                    // are we looking for the Nth XXX day in the month?
1424                    final int dow = daysOfWeek.first(); // desired
1425                    // d-o-w
1426                    final int cDow = cl.get(Calendar.DAY_OF_WEEK); // current d-o-w
1427                    int daysToAdd = 0;
1428                    if (cDow < dow) {
1429                        daysToAdd = dow - cDow;
1430                    } else if (cDow > dow) {
1431                        daysToAdd = dow + (7 - cDow);
1432                    }
1433
1434                    boolean dayShifted = false;
1435                    if (daysToAdd > 0) {
1436                        dayShifted = true;
1437                    }
1438
1439                    day += daysToAdd;
1440                    int weekOfMonth = day / 7;
1441                    if (day % 7 > 0) {
1442                        weekOfMonth++;
1443                    }
1444
1445                    daysToAdd = (nthdayOfWeek - weekOfMonth) * 7;
1446                    day += daysToAdd;
1447                    if (daysToAdd < 0
1448                            || day > getLastDayOfMonth(mon, cl
1449                            .get(Calendar.YEAR))) {
1450                        cl.set(Calendar.SECOND, 0);
1451                        cl.set(Calendar.MINUTE, 0);
1452                        cl.set(Calendar.HOUR_OF_DAY, 0);
1453                        cl.set(Calendar.DAY_OF_MONTH, 1);
1454                        cl.set(Calendar.MONTH, mon);
1455                        // no '- 1' here because we are promoting the month
1456                        continue;
1457                    } else if (daysToAdd > 0 || dayShifted) {
1458                        cl.set(Calendar.SECOND, 0);
1459                        cl.set(Calendar.MINUTE, 0);
1460                        cl.set(Calendar.HOUR_OF_DAY, 0);
1461                        cl.set(Calendar.DAY_OF_MONTH, day);
1462                        cl.set(Calendar.MONTH, mon - 1);
1463                        // '- 1' here because we are NOT promoting the month
1464                        continue;
1465                    }
1466                } else {
1467                    final int cDow = cl.get(Calendar.DAY_OF_WEEK); // current d-o-w
1468                    int dow = daysOfWeek.first(); // desired
1469                    // d-o-w
1470                    st = daysOfWeek.tailSet(cDow);
1471                    if (st != null && st.size() > 0) {
1472                        dow = st.first();
1473                    }
1474
1475                    int daysToAdd = 0;
1476                    if (cDow < dow) {
1477                        daysToAdd = dow - cDow;
1478                    }
1479                    if (cDow > dow) {
1480                        daysToAdd = dow + (7 - cDow);
1481                    }
1482
1483                    final int lDay = getLastDayOfMonth(mon, cl.get(Calendar.YEAR));
1484
1485                    if (day + daysToAdd > lDay) { // will we pass the end of
1486                        // the month?
1487                        cl.set(Calendar.SECOND, 0);
1488                        cl.set(Calendar.MINUTE, 0);
1489                        cl.set(Calendar.HOUR_OF_DAY, 0);
1490                        cl.set(Calendar.DAY_OF_MONTH, 1);
1491                        cl.set(Calendar.MONTH, mon);
1492                        // no '- 1' here because we are promoting the month
1493                        continue;
1494                    } else if (daysToAdd > 0) { // are we switching days?
1495                        cl.set(Calendar.SECOND, 0);
1496                        cl.set(Calendar.MINUTE, 0);
1497                        cl.set(Calendar.HOUR_OF_DAY, 0);
1498                        cl.set(Calendar.DAY_OF_MONTH, day + daysToAdd);
1499                        cl.set(Calendar.MONTH, mon - 1);
1500                        // '- 1' because calendar is 0-based for this field,
1501                        // and we are 1-based
1502                        continue;
1503                    }
1504                }
1505            } else { // dayOfWSpec && !dayOfMSpec
1506                throw new UnsupportedOperationException(
1507                        "Support for specifying both a day-of-week AND a day-of-month parameter is not implemented.");
1508            }
1509            cl.set(Calendar.DAY_OF_MONTH, day);
1510
1511            mon = cl.get(Calendar.MONTH) + 1;
1512            // '+ 1' because calendar is 0-based for this field, and we are
1513            // 1-based
1514            int year = cl.get(Calendar.YEAR);
1515            t = -1;
1516
1517            // test for expressions that never generate a valid fire date,
1518            // but keep looping...
1519            if (year > MAX_YEAR) {
1520                return null;
1521            }
1522
1523            // get month...................................................
1524            st = months.tailSet(mon);
1525            if (st != null && st.size() != 0) {
1526                t = mon;
1527                mon = st.first();
1528            } else {
1529                mon = months.first();
1530                year++;
1531            }
1532            if (mon != t) {
1533                cl.set(Calendar.SECOND, 0);
1534                cl.set(Calendar.MINUTE, 0);
1535                cl.set(Calendar.HOUR_OF_DAY, 0);
1536                cl.set(Calendar.DAY_OF_MONTH, 1);
1537                cl.set(Calendar.MONTH, mon - 1);
1538                // '- 1' because calendar is 0-based for this field, and we are
1539                // 1-based
1540                cl.set(Calendar.YEAR, year);
1541                continue;
1542            }
1543            cl.set(Calendar.MONTH, mon - 1);
1544            // '- 1' because calendar is 0-based for this field, and we are
1545            // 1-based
1546
1547            year = cl.get(Calendar.YEAR);
1548            t = -1;
1549
1550            // get year...................................................
1551            st = years.tailSet(year);
1552            if (st != null && st.size() != 0) {
1553                t = year;
1554                year = st.first();
1555            } else {
1556                return null; // ran out of years...
1557            }
1558
1559            if (year != t) {
1560                cl.set(Calendar.SECOND, 0);
1561                cl.set(Calendar.MINUTE, 0);
1562                cl.set(Calendar.HOUR_OF_DAY, 0);
1563                cl.set(Calendar.DAY_OF_MONTH, 1);
1564                cl.set(Calendar.MONTH, 0);
1565                // '- 1' because calendar is 0-based for this field, and we are
1566                // 1-based
1567                cl.set(Calendar.YEAR, year);
1568                continue;
1569            }
1570            cl.set(Calendar.YEAR, year);
1571
1572            gotOne = true;
1573        } // while( !done )
1574
1575        return cl.getTime();
1576    }
1577
1578    /**
1579     * Advance the calendar to the particular hour paying particular attention
1580     * to daylight saving problems.
1581     *
1582     * @param cal  the calendar to operate on
1583     * @param hour the hour to set
1584     */
1585    protected void setCalendarHour(final Calendar cal, final int hour) {
1586        cal.set(java.util.Calendar.HOUR_OF_DAY, hour);
1587        if (cal.get(java.util.Calendar.HOUR_OF_DAY) != hour && hour != 24) {
1588            cal.set(java.util.Calendar.HOUR_OF_DAY, hour + 1);
1589        }
1590    }
1591
1592    protected Date getTimeBefore(final Date targetDate) {
1593        final Calendar cl = Calendar.getInstance(getTimeZone());
1594
1595        // CronTrigger does not deal with milliseconds, so truncate target
1596        cl.setTime(targetDate);
1597        cl.set(Calendar.MILLISECOND, 0);
1598        final Date targetDateNoMs = cl.getTime();
1599
1600        // to match this
1601        Date start = targetDateNoMs;
1602        final long minIncrement = findMinIncrement();
1603        Date prevFireTime;
1604        do {
1605            final Date prevCheckDate = new Date(start.getTime() - minIncrement);
1606            prevFireTime = getTimeAfter(prevCheckDate);
1607            if (prevFireTime == null || prevFireTime.before(MIN_DATE)) {
1608                return null;
1609            }
1610            start = prevCheckDate;
1611        } while (prevFireTime.compareTo(targetDateNoMs) >= 0);
1612        return prevFireTime;
1613    }
1614
1615    public Date getPrevFireTime(final Date targetDate) {
1616        return getTimeBefore(targetDate);
1617    }
1618
1619    private long findMinIncrement() {
1620        if (seconds.size() != 1) {
1621            return minInSet(seconds) * 1000;
1622        } else if (seconds.first() == ALL_SPEC_INT) {
1623            return 1000;
1624        }
1625        if (minutes.size() != 1) {
1626            return minInSet(minutes) * 60000;
1627        } else if (minutes.first() == ALL_SPEC_INT) {
1628            return 60000;
1629        }
1630        if (hours.size() != 1) {
1631            return minInSet(hours) * 3600000;
1632        } else if (hours.first() == ALL_SPEC_INT) {
1633            return 3600000;
1634        }
1635        return 86400000;
1636    }
1637
1638    private int minInSet(final TreeSet<Integer> set) {
1639        int previous = 0;
1640        int min = Integer.MAX_VALUE;
1641        boolean first = true;
1642        for (final int value : set) {
1643            if (first) {
1644                previous = value;
1645                first = false;
1646                continue;
1647            } else {
1648                final int diff = value - previous;
1649                if (diff < min) {
1650                    min = diff;
1651                }
1652            }
1653        }
1654        return min;
1655    }
1656
1657    /**
1658     * NOT YET IMPLEMENTED: Returns the final time that the
1659     * <code>CronExpression</code> will match.
1660     */
1661    public Date getFinalFireTime() {
1662        // FUTURE_TODO: implement QUARTZ-423
1663        return null;
1664    }
1665
1666    protected boolean isLeapYear(final int year) {
1667        return ((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0));
1668    }
1669
1670    protected int getLastDayOfMonth(final int monthNum, final int year) {
1671
1672        switch (monthNum) {
1673            case 1:
1674                return 31;
1675            case 2:
1676                return (isLeapYear(year)) ? 29 : 28;
1677            case 3:
1678                return 31;
1679            case 4:
1680                return 30;
1681            case 5:
1682                return 31;
1683            case 6:
1684                return 30;
1685            case 7:
1686                return 31;
1687            case 8:
1688                return 31;
1689            case 9:
1690                return 30;
1691            case 10:
1692                return 31;
1693            case 11:
1694                return 30;
1695            case 12:
1696                return 31;
1697            default:
1698                throw new IllegalArgumentException("Illegal month number: "
1699                        + monthNum);
1700        }
1701    }
1702
1703
1704    private class ValueSet {
1705        public int value;
1706
1707        public int pos;
1708    }
1709
1710
1711}