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
256    /**
257     * Constructs a new <CODE>CronExpression</CODE> based on the specified
258     * parameter.
259     *
260     * @param cronExpression String representation of the cron expression the
261     *                       new object should represent
262     * @throws java.text.ParseException if the string expression cannot be parsed into a valid
263     *                                  <CODE>CronExpression</CODE>
264     */
265    public CronExpression(final String cronExpression) throws ParseException {
266        if (cronExpression == null) {
267            throw new IllegalArgumentException("cronExpression cannot be null");
268        }
269
270        this.cronExpression = cronExpression.toUpperCase(Locale.US);
271
272        buildExpression(this.cronExpression);
273    }
274
275    /**
276     * Indicates whether the given date satisfies the cron expression. Note that
277     * milliseconds are ignored, so two Dates falling on different milliseconds
278     * of the same second will always have the same result here.
279     *
280     * @param date the date to evaluate
281     * @return a boolean indicating whether the given date satisfies the cron
282     * expression
283     */
284    public boolean isSatisfiedBy(final Date date) {
285        final Calendar testDateCal = Calendar.getInstance(getTimeZone());
286        testDateCal.setTime(date);
287        testDateCal.set(Calendar.MILLISECOND, 0);
288        final Date originalDate = testDateCal.getTime();
289
290        testDateCal.add(Calendar.SECOND, -1);
291
292        final Date timeAfter = getTimeAfter(testDateCal.getTime());
293
294        return ((timeAfter != null) && (timeAfter.equals(originalDate)));
295    }
296
297    /**
298     * Returns the next date/time <I>after</I> the given date/time which
299     * satisfies the cron expression.
300     *
301     * @param date the date/time at which to begin the search for the next valid
302     *             date/time
303     * @return the next valid date/time
304     */
305    public Date getNextValidTimeAfter(final Date date) {
306        return getTimeAfter(date);
307    }
308
309    /**
310     * Returns the next date/time <I>after</I> the given date/time which does
311     * <I>not</I> satisfy the expression
312     *
313     * @param date the date/time at which to begin the search for the next
314     *             invalid date/time
315     * @return the next valid date/time
316     */
317    public Date getNextInvalidTimeAfter(final Date date) {
318        long difference = 1000;
319
320        //move back to the nearest second so differences will be accurate
321        final Calendar adjustCal = Calendar.getInstance(getTimeZone());
322        adjustCal.setTime(date);
323        adjustCal.set(Calendar.MILLISECOND, 0);
324        Date lastDate = adjustCal.getTime();
325
326        Date newDate;
327
328        //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.
329
330        //keep getting the next included time until it's farther than one second
331        // apart. At that point, lastDate is the last valid fire time. We return
332        // the second immediately following it.
333        while (difference == 1000) {
334            newDate = getTimeAfter(lastDate);
335            if (newDate == null) {
336                break;
337            }
338
339            difference = newDate.getTime() - lastDate.getTime();
340
341            if (difference == 1000) {
342                lastDate = newDate;
343            }
344        }
345
346        return new Date(lastDate.getTime() + 1000);
347    }
348
349    /**
350     * Returns the time zone for which this <code>CronExpression</code>
351     * will be resolved.
352     */
353    public TimeZone getTimeZone() {
354        if (timeZone == null) {
355            timeZone = TimeZone.getDefault();
356        }
357
358        return timeZone;
359    }
360
361    /**
362     * Sets the time zone for which  this <code>CronExpression</code>
363     * will be resolved.
364     */
365    public void setTimeZone(final TimeZone timeZone) {
366        this.timeZone = timeZone;
367    }
368
369    /**
370     * Returns the string representation of the <CODE>CronExpression</CODE>
371     *
372     * @return a string representation of the <CODE>CronExpression</CODE>
373     */
374    @Override
375    public String toString() {
376        return cronExpression;
377    }
378
379    /**
380     * Indicates whether the specified cron expression can be parsed into a
381     * valid cron expression
382     *
383     * @param cronExpression the expression to evaluate
384     * @return a boolean indicating whether the given expression is a valid cron
385     * expression
386     */
387    public static boolean isValidExpression(final String cronExpression) {
388
389        try {
390            new CronExpression(cronExpression);
391        } catch (final ParseException pe) {
392            return false;
393        }
394
395        return true;
396    }
397
398    public static void validateExpression(final String cronExpression) throws ParseException {
399
400        new CronExpression(cronExpression);
401    }
402
403
404    ////////////////////////////////////////////////////////////////////////////
405    //
406    // Expression Parsing Functions
407    //
408    ////////////////////////////////////////////////////////////////////////////
409
410    protected void buildExpression(final String expression) throws ParseException {
411        expressionParsed = true;
412
413        try {
414
415            if (seconds == null) {
416                seconds = new TreeSet<>();
417            }
418            if (minutes == null) {
419                minutes = new TreeSet<>();
420            }
421            if (hours == null) {
422                hours = new TreeSet<>();
423            }
424            if (daysOfMonth == null) {
425                daysOfMonth = new TreeSet<>();
426            }
427            if (months == null) {
428                months = new TreeSet<>();
429            }
430            if (daysOfWeek == null) {
431                daysOfWeek = new TreeSet<>();
432            }
433            if (years == null) {
434                years = new TreeSet<>();
435            }
436
437            int exprOn = SECOND;
438
439            final StringTokenizer exprsTok = new StringTokenizer(expression, " \t",
440                    false);
441
442            while (exprsTok.hasMoreTokens() && exprOn <= YEAR) {
443                final String expr = exprsTok.nextToken().trim();
444
445                // throw an exception if L is used with other days of the month
446                if (exprOn == DAY_OF_MONTH && expr.indexOf('L') != -1 && expr.length() > 1 && expr.contains(",")) {
447                    throw new ParseException("Support for specifying 'L' and 'LW' with other days of the month is not implemented", -1);
448                }
449                // throw an exception if L is used with other days of the week
450                if (exprOn == DAY_OF_WEEK && expr.indexOf('L') != -1 && expr.length() > 1 && expr.contains(",")) {
451                    throw new ParseException("Support for specifying 'L' with other days of the week is not implemented", -1);
452                }
453                if (exprOn == DAY_OF_WEEK && expr.indexOf('#') != -1 && expr.indexOf('#', expr.indexOf('#') + 1) != -1) {
454                    throw new ParseException("Support for specifying multiple \"nth\" days is not implemented.", -1);
455                }
456
457                final StringTokenizer vTok = new StringTokenizer(expr, ",");
458                while (vTok.hasMoreTokens()) {
459                    final String v = vTok.nextToken();
460                    storeExpressionVals(0, v, exprOn);
461                }
462
463                exprOn++;
464            }
465
466            if (exprOn <= DAY_OF_WEEK) {
467                throw new ParseException("Unexpected end of expression.",
468                        expression.length());
469            }
470
471            if (exprOn <= YEAR) {
472                storeExpressionVals(0, "*", YEAR);
473            }
474
475            final TreeSet<Integer> dow = getSet(DAY_OF_WEEK);
476            final TreeSet<Integer> dom = getSet(DAY_OF_MONTH);
477
478            // Copying the logic from the UnsupportedOperationException below
479            final boolean dayOfMSpec = !dom.contains(NO_SPEC);
480            final boolean dayOfWSpec = !dow.contains(NO_SPEC);
481
482            if (!dayOfMSpec || dayOfWSpec) {
483                if (!dayOfWSpec || dayOfMSpec) {
484                    throw new ParseException(
485                            "Support for specifying both a day-of-week AND a day-of-month parameter is not implemented.", 0);
486                }
487            }
488        } catch (final ParseException pe) {
489            throw pe;
490        } catch (final Exception e) {
491            throw new ParseException("Illegal cron expression format ("
492                    + e.toString() + ")", 0);
493        }
494    }
495
496    protected int storeExpressionVals(final int pos, final String s, final int type)
497            throws ParseException {
498
499        int incr = 0;
500        int i = skipWhiteSpace(pos, s);
501        if (i >= s.length()) {
502            return i;
503        }
504        char c = s.charAt(i);
505        if ((c >= 'A') && (c <= 'Z') && (!s.equals("L")) && (!s.equals("LW")) && (!s.matches("^L-[0-9]*[W]?"))) {
506            String sub = s.substring(i, i + 3);
507            int sval = -1;
508            int eval = -1;
509            if (type == MONTH) {
510                sval = getMonthNumber(sub) + 1;
511                if (sval <= 0) {
512                    throw new ParseException("Invalid Month value: '" + sub + "'", i);
513                }
514                if (s.length() > i + 3) {
515                    c = s.charAt(i + 3);
516                    if (c == '-') {
517                        i += 4;
518                        sub = s.substring(i, i + 3);
519                        eval = getMonthNumber(sub) + 1;
520                        if (eval <= 0) {
521                            throw new ParseException("Invalid Month value: '" + sub + "'", i);
522                        }
523                    }
524                }
525            } else if (type == DAY_OF_WEEK) {
526                sval = getDayOfWeekNumber(sub);
527                if (sval < 0) {
528                    throw new ParseException("Invalid Day-of-Week value: '"
529                            + sub + "'", i);
530                }
531                if (s.length() > i + 3) {
532                    c = s.charAt(i + 3);
533                    if (c == '-') {
534                        i += 4;
535                        sub = s.substring(i, i + 3);
536                        eval = getDayOfWeekNumber(sub);
537                        if (eval < 0) {
538                            throw new ParseException(
539                                    "Invalid Day-of-Week value: '" + sub
540                                            + "'", i);
541                        }
542                    } else if (c == '#') {
543                        try {
544                            i += 4;
545                            nthdayOfWeek = Integer.parseInt(s.substring(i));
546                            if (nthdayOfWeek < 1 || nthdayOfWeek > 5) {
547                                throw new Exception();
548                            }
549                        } catch (final Exception e) {
550                            throw new ParseException(
551                                    "A numeric value between 1 and 5 must follow the '#' option",
552                                    i);
553                        }
554                    } else if (c == 'L') {
555                        lastdayOfWeek = true;
556                        i++;
557                    }
558                }
559
560            } else {
561                throw new ParseException(
562                        "Illegal characters for this position: '" + sub + "'",
563                        i);
564            }
565            if (eval != -1) {
566                incr = 1;
567            }
568            addToSet(sval, eval, incr, type);
569            return (i + 3);
570        }
571
572        if (c == '?') {
573            i++;
574            if ((i + 1) < s.length()
575                    && (s.charAt(i) != ' ' && s.charAt(i + 1) != '\t')) {
576                throw new ParseException("Illegal character after '?': "
577                        + s.charAt(i), i);
578            }
579            if (type != DAY_OF_WEEK && type != DAY_OF_MONTH) {
580                throw new ParseException(
581                        "'?' can only be specfied for Day-of-Month or Day-of-Week.",
582                        i);
583            }
584            if (type == DAY_OF_WEEK && !lastdayOfMonth) {
585                final int val = daysOfMonth.last();
586                if (val == NO_SPEC_INT) {
587                    throw new ParseException(
588                            "'?' can only be specfied for Day-of-Month -OR- Day-of-Week.",
589                            i);
590                }
591            }
592
593            addToSet(NO_SPEC_INT, -1, 0, type);
594            return i;
595        }
596
597        if (c == '*' || c == '/') {
598            if (c == '*' && (i + 1) >= s.length()) {
599                addToSet(ALL_SPEC_INT, -1, incr, type);
600                return i + 1;
601            } else if (c == '/'
602                    && ((i + 1) >= s.length() || s.charAt(i + 1) == ' ' || s
603                    .charAt(i + 1) == '\t')) {
604                throw new ParseException("'/' must be followed by an integer.", i);
605            } else if (c == '*') {
606                i++;
607            }
608            c = s.charAt(i);
609            if (c == '/') { // is an increment specified?
610                i++;
611                if (i >= s.length()) {
612                    throw new ParseException("Unexpected end of string.", i);
613                }
614
615                incr = getNumericValue(s, i);
616
617                i++;
618                if (incr > 10) {
619                    i++;
620                }
621                if (incr > 59 && (type == SECOND || type == MINUTE)) {
622                    throw new ParseException("Increment > 60 : " + incr, i);
623                } else if (incr > 23 && (type == HOUR)) {
624                    throw new ParseException("Increment > 24 : " + incr, i);
625                } else if (incr > 31 && (type == DAY_OF_MONTH)) {
626                    throw new ParseException("Increment > 31 : " + incr, i);
627                } else if (incr > 7 && (type == DAY_OF_WEEK)) {
628                    throw new ParseException("Increment > 7 : " + incr, i);
629                } else if (incr > 12 && (type == MONTH)) {
630                    throw new ParseException("Increment > 12 : " + incr, i);
631                }
632            } else {
633                incr = 1;
634            }
635
636            addToSet(ALL_SPEC_INT, -1, incr, type);
637            return i;
638        } else if (c == 'L') {
639            i++;
640            if (type == DAY_OF_MONTH) {
641                lastdayOfMonth = true;
642            }
643            if (type == DAY_OF_WEEK) {
644                addToSet(7, 7, 0, type);
645            }
646            if (type == DAY_OF_MONTH && s.length() > i) {
647                c = s.charAt(i);
648                if (c == '-') {
649                    final ValueSet vs = getValue(0, s, i + 1);
650                    lastdayOffset = vs.value;
651                    if (lastdayOffset > 30) {
652                        throw new ParseException("Offset from last day must be <= 30", i + 1);
653                    }
654                    i = vs.pos;
655                }
656                if (s.length() > i) {
657                    c = s.charAt(i);
658                    if (c == 'W') {
659                        nearestWeekday = true;
660                        i++;
661                    }
662                }
663            }
664            return i;
665        } else if (c >= '0' && c <= '9') {
666            int val = Integer.parseInt(String.valueOf(c));
667            i++;
668            if (i >= s.length()) {
669                addToSet(val, -1, -1, type);
670            } else {
671                c = s.charAt(i);
672                if (c >= '0' && c <= '9') {
673                    final ValueSet vs = getValue(val, s, i);
674                    val = vs.value;
675                    i = vs.pos;
676                }
677                i = checkNext(i, s, val, type);
678                return i;
679            }
680        } else {
681            throw new ParseException("Unexpected character: " + c, i);
682        }
683
684        return i;
685    }
686
687    protected int checkNext(final int pos, final String s, final int val, final int type)
688            throws ParseException {
689
690        int end = -1;
691        int i = pos;
692
693        if (i >= s.length()) {
694            addToSet(val, end, -1, type);
695            return i;
696        }
697
698        char c = s.charAt(pos);
699
700        if (c == 'L') {
701            if (type == DAY_OF_WEEK) {
702                if (val < 1 || val > 7) {
703                    throw new ParseException("Day-of-Week values must be between 1 and 7", -1);
704                }
705                lastdayOfWeek = true;
706            } else {
707                throw new ParseException("'L' option is not valid here. (pos=" + i + ")", i);
708            }
709            final TreeSet<Integer> set = getSet(type);
710            set.add(val);
711            i++;
712            return i;
713        }
714
715        if (c == 'W') {
716            if (type == DAY_OF_MONTH) {
717                nearestWeekday = true;
718            } else {
719                throw new ParseException("'W' option is not valid here. (pos=" + i + ")", i);
720            }
721            if (val > 31) {
722                throw new ParseException("The 'W' option does not make sense with values larger than 31 (max number of days in a month)", i);
723            }
724            final TreeSet<Integer> set = getSet(type);
725            set.add(val);
726            i++;
727            return i;
728        }
729
730        if (c == '#') {
731            if (type != DAY_OF_WEEK) {
732                throw new ParseException("'#' option is not valid here. (pos=" + i + ")", i);
733            }
734            i++;
735            try {
736                nthdayOfWeek = Integer.parseInt(s.substring(i));
737                if (nthdayOfWeek < 1 || nthdayOfWeek > 5) {
738                    throw new Exception();
739                }
740            } catch (final Exception e) {
741                throw new ParseException(
742                        "A numeric value between 1 and 5 must follow the '#' option",
743                        i);
744            }
745
746            final TreeSet<Integer> set = getSet(type);
747            set.add(val);
748            i++;
749            return i;
750        }
751
752        if (c == '-') {
753            i++;
754            c = s.charAt(i);
755            final int v = Integer.parseInt(String.valueOf(c));
756            end = v;
757            i++;
758            if (i >= s.length()) {
759                addToSet(val, end, 1, type);
760                return i;
761            }
762            c = s.charAt(i);
763            if (c >= '0' && c <= '9') {
764                final ValueSet vs = getValue(v, s, i);
765                end = vs.value;
766                i = vs.pos;
767            }
768            if (i < s.length() && ((c = s.charAt(i)) == '/')) {
769                i++;
770                c = s.charAt(i);
771                final int v2 = Integer.parseInt(String.valueOf(c));
772                i++;
773                if (i >= s.length()) {
774                    addToSet(val, end, v2, type);
775                    return i;
776                }
777                c = s.charAt(i);
778                if (c >= '0' && c <= '9') {
779                    final ValueSet vs = getValue(v2, s, i);
780                    final int v3 = vs.value;
781                    addToSet(val, end, v3, type);
782                    i = vs.pos;
783                    return i;
784                } else {
785                    addToSet(val, end, v2, type);
786                    return i;
787                }
788            } else {
789                addToSet(val, end, 1, type);
790                return i;
791            }
792        }
793
794        if (c == '/') {
795            i++;
796            c = s.charAt(i);
797            final int v2 = Integer.parseInt(String.valueOf(c));
798            i++;
799            if (i >= s.length()) {
800                addToSet(val, end, v2, type);
801                return i;
802            }
803            c = s.charAt(i);
804            if (c >= '0' && c <= '9') {
805                final ValueSet vs = getValue(v2, s, i);
806                final int v3 = vs.value;
807                addToSet(val, end, v3, type);
808                i = vs.pos;
809                return i;
810            } else {
811                throw new ParseException("Unexpected character '" + c + "' after '/'", i);
812            }
813        }
814
815        addToSet(val, end, 0, type);
816        i++;
817        return i;
818    }
819
820    public String getCronExpression() {
821        return cronExpression;
822    }
823
824    public String getExpressionSummary() {
825        final StringBuilder buf = new StringBuilder();
826
827        buf.append("seconds: ");
828        buf.append(getExpressionSetSummary(seconds));
829        buf.append("\n");
830        buf.append("minutes: ");
831        buf.append(getExpressionSetSummary(minutes));
832        buf.append("\n");
833        buf.append("hours: ");
834        buf.append(getExpressionSetSummary(hours));
835        buf.append("\n");
836        buf.append("daysOfMonth: ");
837        buf.append(getExpressionSetSummary(daysOfMonth));
838        buf.append("\n");
839        buf.append("months: ");
840        buf.append(getExpressionSetSummary(months));
841        buf.append("\n");
842        buf.append("daysOfWeek: ");
843        buf.append(getExpressionSetSummary(daysOfWeek));
844        buf.append("\n");
845        buf.append("lastdayOfWeek: ");
846        buf.append(lastdayOfWeek);
847        buf.append("\n");
848        buf.append("nearestWeekday: ");
849        buf.append(nearestWeekday);
850        buf.append("\n");
851        buf.append("NthDayOfWeek: ");
852        buf.append(nthdayOfWeek);
853        buf.append("\n");
854        buf.append("lastdayOfMonth: ");
855        buf.append(lastdayOfMonth);
856        buf.append("\n");
857        buf.append("years: ");
858        buf.append(getExpressionSetSummary(years));
859        buf.append("\n");
860
861        return buf.toString();
862    }
863
864    protected String getExpressionSetSummary(final java.util.Set<Integer> set) {
865
866        if (set.contains(NO_SPEC)) {
867            return "?";
868        }
869        if (set.contains(ALL_SPEC)) {
870            return "*";
871        }
872
873        final StringBuilder buf = new StringBuilder();
874
875        final Iterator<Integer> itr = set.iterator();
876        boolean first = true;
877        while (itr.hasNext()) {
878            final Integer iVal = itr.next();
879            final String val = iVal.toString();
880            if (!first) {
881                buf.append(",");
882            }
883            buf.append(val);
884            first = false;
885        }
886
887        return buf.toString();
888    }
889
890    protected String getExpressionSetSummary(final java.util.ArrayList<Integer> list) {
891
892        if (list.contains(NO_SPEC)) {
893            return "?";
894        }
895        if (list.contains(ALL_SPEC)) {
896            return "*";
897        }
898
899        final StringBuilder buf = new StringBuilder();
900
901        final Iterator<Integer> itr = list.iterator();
902        boolean first = true;
903        while (itr.hasNext()) {
904            final Integer iVal = itr.next();
905            final String val = iVal.toString();
906            if (!first) {
907                buf.append(",");
908            }
909            buf.append(val);
910            first = false;
911        }
912
913        return buf.toString();
914    }
915
916    protected int skipWhiteSpace(int i, final String s) {
917        for (; i < s.length() && (s.charAt(i) == ' ' || s.charAt(i) == '\t'); i++) {
918            ;
919        }
920
921        return i;
922    }
923
924    protected int findNextWhiteSpace(int i, final String s) {
925        for (; i < s.length() && (s.charAt(i) != ' ' || s.charAt(i) != '\t'); i++) {
926            ;
927        }
928
929        return i;
930    }
931
932    protected void addToSet(final int val, final int end, int incr, final int type)
933            throws ParseException {
934
935        final TreeSet<Integer> set = getSet(type);
936
937        if (type == SECOND || type == MINUTE) {
938            if ((val < 0 || val > 59 || end > 59) && (val != ALL_SPEC_INT)) {
939                throw new ParseException(
940                        "Minute and Second values must be between 0 and 59",
941                        -1);
942            }
943        } else if (type == HOUR) {
944            if ((val < 0 || val > 23 || end > 23) && (val != ALL_SPEC_INT)) {
945                throw new ParseException(
946                        "Hour values must be between 0 and 23", -1);
947            }
948        } else if (type == DAY_OF_MONTH) {
949            if ((val < 1 || val > 31 || end > 31) && (val != ALL_SPEC_INT)
950                    && (val != NO_SPEC_INT)) {
951                throw new ParseException(
952                        "Day of month values must be between 1 and 31", -1);
953            }
954        } else if (type == MONTH) {
955            if ((val < 1 || val > 12 || end > 12) && (val != ALL_SPEC_INT)) {
956                throw new ParseException(
957                        "Month values must be between 1 and 12", -1);
958            }
959        } else if (type == DAY_OF_WEEK) {
960            if ((val == 0 || val > 7 || end > 7) && (val != ALL_SPEC_INT)
961                    && (val != NO_SPEC_INT)) {
962                throw new ParseException(
963                        "Day-of-Week values must be between 1 and 7", -1);
964            }
965        }
966
967        if ((incr == 0 || incr == -1) && val != ALL_SPEC_INT) {
968            if (val != -1) {
969                set.add(val);
970            } else {
971                set.add(NO_SPEC);
972            }
973
974            return;
975        }
976
977        int startAt = val;
978        int stopAt = end;
979
980        if (val == ALL_SPEC_INT && incr <= 0) {
981            incr = 1;
982            set.add(ALL_SPEC); // put in a marker, but also fill values
983        }
984
985        if (type == SECOND || type == MINUTE) {
986            if (stopAt == -1) {
987                stopAt = 59;
988            }
989            if (startAt == -1 || startAt == ALL_SPEC_INT) {
990                startAt = 0;
991            }
992        } else if (type == HOUR) {
993            if (stopAt == -1) {
994                stopAt = 23;
995            }
996            if (startAt == -1 || startAt == ALL_SPEC_INT) {
997                startAt = 0;
998            }
999        } else if (type == DAY_OF_MONTH) {
1000            if (stopAt == -1) {
1001                stopAt = 31;
1002            }
1003            if (startAt == -1 || startAt == ALL_SPEC_INT) {
1004                startAt = 1;
1005            }
1006        } else if (type == MONTH) {
1007            if (stopAt == -1) {
1008                stopAt = 12;
1009            }
1010            if (startAt == -1 || startAt == ALL_SPEC_INT) {
1011                startAt = 1;
1012            }
1013        } else if (type == DAY_OF_WEEK) {
1014            if (stopAt == -1) {
1015                stopAt = 7;
1016            }
1017            if (startAt == -1 || startAt == ALL_SPEC_INT) {
1018                startAt = 1;
1019            }
1020        } else if (type == YEAR) {
1021            if (stopAt == -1) {
1022                stopAt = MAX_YEAR;
1023            }
1024            if (startAt == -1 || startAt == ALL_SPEC_INT) {
1025                startAt = 1970;
1026            }
1027        }
1028
1029        // if the end of the range is before the start, then we need to overflow into
1030        // the next day, month etc. This is done by adding the maximum amount for that
1031        // type, and using modulus max to determine the value being added.
1032        int max = -1;
1033        if (stopAt < startAt) {
1034            switch (type) {
1035                case SECOND:
1036                    max = 60;
1037                    break;
1038                case MINUTE:
1039                    max = 60;
1040                    break;
1041                case HOUR:
1042                    max = 24;
1043                    break;
1044                case MONTH:
1045                    max = 12;
1046                    break;
1047                case DAY_OF_WEEK:
1048                    max = 7;
1049                    break;
1050                case DAY_OF_MONTH:
1051                    max = 31;
1052                    break;
1053                case YEAR:
1054                    throw new IllegalArgumentException("Start year must be less than stop year");
1055                default:
1056                    throw new IllegalArgumentException("Unexpected type encountered");
1057            }
1058            stopAt += max;
1059        }
1060
1061        for (int i = startAt; i <= stopAt; i += incr) {
1062            if (max == -1) {
1063                // ie: there's no max to overflow over
1064                set.add(i);
1065            } else {
1066                // take the modulus to get the real value
1067                int i2 = i % max;
1068
1069                // 1-indexed ranges should not include 0, and should include their max
1070                if (i2 == 0 && (type == MONTH || type == DAY_OF_WEEK || type == DAY_OF_MONTH)) {
1071                    i2 = max;
1072                }
1073
1074                set.add(i2);
1075            }
1076        }
1077    }
1078
1079    TreeSet<Integer> getSet(final int type) {
1080        switch (type) {
1081            case SECOND:
1082                return seconds;
1083            case MINUTE:
1084                return minutes;
1085            case HOUR:
1086                return hours;
1087            case DAY_OF_MONTH:
1088                return daysOfMonth;
1089            case MONTH:
1090                return months;
1091            case DAY_OF_WEEK:
1092                return daysOfWeek;
1093            case YEAR:
1094                return years;
1095            default:
1096                return null;
1097        }
1098    }
1099
1100    protected ValueSet getValue(final int v, final String s, int i) {
1101        char c = s.charAt(i);
1102        final StringBuilder s1 = new StringBuilder(String.valueOf(v));
1103        while (c >= '0' && c <= '9') {
1104            s1.append(c);
1105            i++;
1106            if (i >= s.length()) {
1107                break;
1108            }
1109            c = s.charAt(i);
1110        }
1111        final ValueSet val = new ValueSet();
1112
1113        val.pos = (i < s.length()) ? i : i + 1;
1114        val.value = Integer.parseInt(s1.toString());
1115        return val;
1116    }
1117
1118    protected int getNumericValue(final String s, final int i) {
1119        final int endOfVal = findNextWhiteSpace(i, s);
1120        final String val = s.substring(i, endOfVal);
1121        return Integer.parseInt(val);
1122    }
1123
1124    protected int getMonthNumber(final String s) {
1125        final Integer integer = monthMap.get(s);
1126
1127        if (integer == null) {
1128            return -1;
1129        }
1130
1131        return integer;
1132    }
1133
1134    protected int getDayOfWeekNumber(final String s) {
1135        final Integer integer = dayMap.get(s);
1136
1137        if (integer == null) {
1138            return -1;
1139        }
1140
1141        return integer;
1142    }
1143
1144    ////////////////////////////////////////////////////////////////////////////
1145    //
1146    // Computation Functions
1147    //
1148    ////////////////////////////////////////////////////////////////////////////
1149
1150    public Date getTimeAfter(Date afterTime) {
1151
1152        // Computation is based on Gregorian year only.
1153        final Calendar cl = new java.util.GregorianCalendar(getTimeZone());
1154
1155        // move ahead one second, since we're computing the time *after* the
1156        // given time
1157        afterTime = new Date(afterTime.getTime() + 1000);
1158        // CronTrigger does not deal with milliseconds
1159        cl.setTime(afterTime);
1160        cl.set(Calendar.MILLISECOND, 0);
1161
1162        boolean gotOne = false;
1163        // loop until we've computed the next time, or we've past the endTime
1164        while (!gotOne) {
1165
1166            //if (endTime != null && cl.getTime().after(endTime)) return null;
1167            if (cl.get(Calendar.YEAR) > 2999) { // prevent endless loop...
1168                return null;
1169            }
1170
1171            SortedSet<Integer> st = null;
1172            int t = 0;
1173
1174            int sec = cl.get(Calendar.SECOND);
1175            int min = cl.get(Calendar.MINUTE);
1176
1177            // get second.................................................
1178            st = seconds.tailSet(sec);
1179            if (st != null && st.size() != 0) {
1180                sec = st.first();
1181            } else {
1182                sec = seconds.first();
1183                min++;
1184                cl.set(Calendar.MINUTE, min);
1185            }
1186            cl.set(Calendar.SECOND, sec);
1187
1188            min = cl.get(Calendar.MINUTE);
1189            int hr = cl.get(Calendar.HOUR_OF_DAY);
1190            t = -1;
1191
1192            // get minute.................................................
1193            st = minutes.tailSet(min);
1194            if (st != null && st.size() != 0) {
1195                t = min;
1196                min = st.first();
1197            } else {
1198                min = minutes.first();
1199                hr++;
1200            }
1201            if (min != t) {
1202                cl.set(Calendar.SECOND, 0);
1203                cl.set(Calendar.MINUTE, min);
1204                setCalendarHour(cl, hr);
1205                continue;
1206            }
1207            cl.set(Calendar.MINUTE, min);
1208
1209            hr = cl.get(Calendar.HOUR_OF_DAY);
1210            int day = cl.get(Calendar.DAY_OF_MONTH);
1211            t = -1;
1212
1213            // get hour...................................................
1214            st = hours.tailSet(hr);
1215            if (st != null && st.size() != 0) {
1216                t = hr;
1217                hr = st.first();
1218            } else {
1219                hr = hours.first();
1220                day++;
1221            }
1222            if (hr != t) {
1223                cl.set(Calendar.SECOND, 0);
1224                cl.set(Calendar.MINUTE, 0);
1225                cl.set(Calendar.DAY_OF_MONTH, day);
1226                setCalendarHour(cl, hr);
1227                continue;
1228            }
1229            cl.set(Calendar.HOUR_OF_DAY, hr);
1230
1231            day = cl.get(Calendar.DAY_OF_MONTH);
1232            int mon = cl.get(Calendar.MONTH) + 1;
1233            // '+ 1' because calendar is 0-based for this field, and we are
1234            // 1-based
1235            t = -1;
1236            int tmon = mon;
1237
1238            // get day...................................................
1239            final boolean dayOfMSpec = !daysOfMonth.contains(NO_SPEC);
1240            final boolean dayOfWSpec = !daysOfWeek.contains(NO_SPEC);
1241            if (dayOfMSpec && !dayOfWSpec) { // get day by day of month rule
1242                st = daysOfMonth.tailSet(day);
1243                if (lastdayOfMonth) {
1244                    if (!nearestWeekday) {
1245                        t = day;
1246                        day = getLastDayOfMonth(mon, cl.get(Calendar.YEAR));
1247                        day -= lastdayOffset;
1248                        if (t > day) {
1249                            mon++;
1250                            if (mon > 12) {
1251                                mon = 1;
1252                                tmon = 3333; // ensure test of mon != tmon further below fails
1253                                cl.add(Calendar.YEAR, 1);
1254                            }
1255                            day = 1;
1256                        }
1257                    } else {
1258                        t = day;
1259                        day = getLastDayOfMonth(mon, cl.get(Calendar.YEAR));
1260                        day -= lastdayOffset;
1261
1262                        final java.util.Calendar tcal = java.util.Calendar.getInstance(getTimeZone());
1263                        tcal.set(Calendar.SECOND, 0);
1264                        tcal.set(Calendar.MINUTE, 0);
1265                        tcal.set(Calendar.HOUR_OF_DAY, 0);
1266                        tcal.set(Calendar.DAY_OF_MONTH, day);
1267                        tcal.set(Calendar.MONTH, mon - 1);
1268                        tcal.set(Calendar.YEAR, cl.get(Calendar.YEAR));
1269
1270                        final int ldom = getLastDayOfMonth(mon, cl.get(Calendar.YEAR));
1271                        final int dow = tcal.get(Calendar.DAY_OF_WEEK);
1272
1273                        if (dow == Calendar.SATURDAY && day == 1) {
1274                            day += 2;
1275                        } else if (dow == Calendar.SATURDAY) {
1276                            day -= 1;
1277                        } else if (dow == Calendar.SUNDAY && day == ldom) {
1278                            day -= 2;
1279                        } else if (dow == Calendar.SUNDAY) {
1280                            day += 1;
1281                        }
1282
1283                        tcal.set(Calendar.SECOND, sec);
1284                        tcal.set(Calendar.MINUTE, min);
1285                        tcal.set(Calendar.HOUR_OF_DAY, hr);
1286                        tcal.set(Calendar.DAY_OF_MONTH, day);
1287                        tcal.set(Calendar.MONTH, mon - 1);
1288                        final Date nTime = tcal.getTime();
1289                        if (nTime.before(afterTime)) {
1290                            day = 1;
1291                            mon++;
1292                        }
1293                    }
1294                } else if (nearestWeekday) {
1295                    t = day;
1296                    day = daysOfMonth.first();
1297
1298                    final java.util.Calendar tcal = java.util.Calendar.getInstance(getTimeZone());
1299                    tcal.set(Calendar.SECOND, 0);
1300                    tcal.set(Calendar.MINUTE, 0);
1301                    tcal.set(Calendar.HOUR_OF_DAY, 0);
1302                    tcal.set(Calendar.DAY_OF_MONTH, day);
1303                    tcal.set(Calendar.MONTH, mon - 1);
1304                    tcal.set(Calendar.YEAR, cl.get(Calendar.YEAR));
1305
1306                    final int ldom = getLastDayOfMonth(mon, cl.get(Calendar.YEAR));
1307                    final int dow = tcal.get(Calendar.DAY_OF_WEEK);
1308
1309                    if (dow == Calendar.SATURDAY && day == 1) {
1310                        day += 2;
1311                    } else if (dow == Calendar.SATURDAY) {
1312                        day -= 1;
1313                    } else if (dow == Calendar.SUNDAY && day == ldom) {
1314                        day -= 2;
1315                    } else if (dow == Calendar.SUNDAY) {
1316                        day += 1;
1317                    }
1318
1319
1320                    tcal.set(Calendar.SECOND, sec);
1321                    tcal.set(Calendar.MINUTE, min);
1322                    tcal.set(Calendar.HOUR_OF_DAY, hr);
1323                    tcal.set(Calendar.DAY_OF_MONTH, day);
1324                    tcal.set(Calendar.MONTH, mon - 1);
1325                    final Date nTime = tcal.getTime();
1326                    if (nTime.before(afterTime)) {
1327                        day = daysOfMonth.first();
1328                        mon++;
1329                    }
1330                } else if (st != null && st.size() != 0) {
1331                    t = day;
1332                    day = st.first();
1333                    // make sure we don't over-run a short month, such as february
1334                    final int lastDay = getLastDayOfMonth(mon, cl.get(Calendar.YEAR));
1335                    if (day > lastDay) {
1336                        day = daysOfMonth.first();
1337                        mon++;
1338                    }
1339                } else {
1340                    day = daysOfMonth.first();
1341                    mon++;
1342                }
1343
1344                if (day != t || mon != tmon) {
1345                    cl.set(Calendar.SECOND, 0);
1346                    cl.set(Calendar.MINUTE, 0);
1347                    cl.set(Calendar.HOUR_OF_DAY, 0);
1348                    cl.set(Calendar.DAY_OF_MONTH, day);
1349                    cl.set(Calendar.MONTH, mon - 1);
1350                    // '- 1' because calendar is 0-based for this field, and we
1351                    // are 1-based
1352                    continue;
1353                }
1354            } else if (dayOfWSpec && !dayOfMSpec) { // get day by day of week rule
1355                if (lastdayOfWeek) { // are we looking for the last XXX day of
1356                    // the month?
1357                    final int dow = daysOfWeek.first(); // desired
1358                    // d-o-w
1359                    final int cDow = cl.get(Calendar.DAY_OF_WEEK); // current d-o-w
1360                    int daysToAdd = 0;
1361                    if (cDow < dow) {
1362                        daysToAdd = dow - cDow;
1363                    }
1364                    if (cDow > dow) {
1365                        daysToAdd = dow + (7 - cDow);
1366                    }
1367
1368                    final int lDay = getLastDayOfMonth(mon, cl.get(Calendar.YEAR));
1369
1370                    if (day + daysToAdd > lDay) { // did we already miss the
1371                        // last one?
1372                        cl.set(Calendar.SECOND, 0);
1373                        cl.set(Calendar.MINUTE, 0);
1374                        cl.set(Calendar.HOUR_OF_DAY, 0);
1375                        cl.set(Calendar.DAY_OF_MONTH, 1);
1376                        cl.set(Calendar.MONTH, mon);
1377                        // no '- 1' here because we are promoting the month
1378                        continue;
1379                    }
1380
1381                    // find date of last occurrence of this day in this month...
1382                    while ((day + daysToAdd + 7) <= lDay) {
1383                        daysToAdd += 7;
1384                    }
1385
1386                    day += daysToAdd;
1387
1388                    if (daysToAdd > 0) {
1389                        cl.set(Calendar.SECOND, 0);
1390                        cl.set(Calendar.MINUTE, 0);
1391                        cl.set(Calendar.HOUR_OF_DAY, 0);
1392                        cl.set(Calendar.DAY_OF_MONTH, day);
1393                        cl.set(Calendar.MONTH, mon - 1);
1394                        // '- 1' here because we are not promoting the month
1395                        continue;
1396                    }
1397
1398                } else if (nthdayOfWeek != 0) {
1399                    // are we looking for the Nth XXX day in the month?
1400                    final int dow = daysOfWeek.first(); // desired
1401                    // d-o-w
1402                    final int cDow = cl.get(Calendar.DAY_OF_WEEK); // current d-o-w
1403                    int daysToAdd = 0;
1404                    if (cDow < dow) {
1405                        daysToAdd = dow - cDow;
1406                    } else if (cDow > dow) {
1407                        daysToAdd = dow + (7 - cDow);
1408                    }
1409
1410                    boolean dayShifted = false;
1411                    if (daysToAdd > 0) {
1412                        dayShifted = true;
1413                    }
1414
1415                    day += daysToAdd;
1416                    int weekOfMonth = day / 7;
1417                    if (day % 7 > 0) {
1418                        weekOfMonth++;
1419                    }
1420
1421                    daysToAdd = (nthdayOfWeek - weekOfMonth) * 7;
1422                    day += daysToAdd;
1423                    if (daysToAdd < 0
1424                            || day > getLastDayOfMonth(mon, cl
1425                            .get(Calendar.YEAR))) {
1426                        cl.set(Calendar.SECOND, 0);
1427                        cl.set(Calendar.MINUTE, 0);
1428                        cl.set(Calendar.HOUR_OF_DAY, 0);
1429                        cl.set(Calendar.DAY_OF_MONTH, 1);
1430                        cl.set(Calendar.MONTH, mon);
1431                        // no '- 1' here because we are promoting the month
1432                        continue;
1433                    } else if (daysToAdd > 0 || dayShifted) {
1434                        cl.set(Calendar.SECOND, 0);
1435                        cl.set(Calendar.MINUTE, 0);
1436                        cl.set(Calendar.HOUR_OF_DAY, 0);
1437                        cl.set(Calendar.DAY_OF_MONTH, day);
1438                        cl.set(Calendar.MONTH, mon - 1);
1439                        // '- 1' here because we are NOT promoting the month
1440                        continue;
1441                    }
1442                } else {
1443                    final int cDow = cl.get(Calendar.DAY_OF_WEEK); // current d-o-w
1444                    int dow = daysOfWeek.first(); // desired
1445                    // d-o-w
1446                    st = daysOfWeek.tailSet(cDow);
1447                    if (st != null && st.size() > 0) {
1448                        dow = st.first();
1449                    }
1450
1451                    int daysToAdd = 0;
1452                    if (cDow < dow) {
1453                        daysToAdd = dow - cDow;
1454                    }
1455                    if (cDow > dow) {
1456                        daysToAdd = dow + (7 - cDow);
1457                    }
1458
1459                    final int lDay = getLastDayOfMonth(mon, cl.get(Calendar.YEAR));
1460
1461                    if (day + daysToAdd > lDay) { // will we pass the end of
1462                        // the month?
1463                        cl.set(Calendar.SECOND, 0);
1464                        cl.set(Calendar.MINUTE, 0);
1465                        cl.set(Calendar.HOUR_OF_DAY, 0);
1466                        cl.set(Calendar.DAY_OF_MONTH, 1);
1467                        cl.set(Calendar.MONTH, mon);
1468                        // no '- 1' here because we are promoting the month
1469                        continue;
1470                    } else if (daysToAdd > 0) { // are we swithing days?
1471                        cl.set(Calendar.SECOND, 0);
1472                        cl.set(Calendar.MINUTE, 0);
1473                        cl.set(Calendar.HOUR_OF_DAY, 0);
1474                        cl.set(Calendar.DAY_OF_MONTH, day + daysToAdd);
1475                        cl.set(Calendar.MONTH, mon - 1);
1476                        // '- 1' because calendar is 0-based for this field,
1477                        // and we are 1-based
1478                        continue;
1479                    }
1480                }
1481            } else { // dayOfWSpec && !dayOfMSpec
1482                throw new UnsupportedOperationException(
1483                        "Support for specifying both a day-of-week AND a day-of-month parameter is not implemented.");
1484            }
1485            cl.set(Calendar.DAY_OF_MONTH, day);
1486
1487            mon = cl.get(Calendar.MONTH) + 1;
1488            // '+ 1' because calendar is 0-based for this field, and we are
1489            // 1-based
1490            int year = cl.get(Calendar.YEAR);
1491            t = -1;
1492
1493            // test for expressions that never generate a valid fire date,
1494            // but keep looping...
1495            if (year > MAX_YEAR) {
1496                return null;
1497            }
1498
1499            // get month...................................................
1500            st = months.tailSet(mon);
1501            if (st != null && st.size() != 0) {
1502                t = mon;
1503                mon = st.first();
1504            } else {
1505                mon = months.first();
1506                year++;
1507            }
1508            if (mon != t) {
1509                cl.set(Calendar.SECOND, 0);
1510                cl.set(Calendar.MINUTE, 0);
1511                cl.set(Calendar.HOUR_OF_DAY, 0);
1512                cl.set(Calendar.DAY_OF_MONTH, 1);
1513                cl.set(Calendar.MONTH, mon - 1);
1514                // '- 1' because calendar is 0-based for this field, and we are
1515                // 1-based
1516                cl.set(Calendar.YEAR, year);
1517                continue;
1518            }
1519            cl.set(Calendar.MONTH, mon - 1);
1520            // '- 1' because calendar is 0-based for this field, and we are
1521            // 1-based
1522
1523            year = cl.get(Calendar.YEAR);
1524            t = -1;
1525
1526            // get year...................................................
1527            st = years.tailSet(year);
1528            if (st != null && st.size() != 0) {
1529                t = year;
1530                year = st.first();
1531            } else {
1532                return null; // ran out of years...
1533            }
1534
1535            if (year != t) {
1536                cl.set(Calendar.SECOND, 0);
1537                cl.set(Calendar.MINUTE, 0);
1538                cl.set(Calendar.HOUR_OF_DAY, 0);
1539                cl.set(Calendar.DAY_OF_MONTH, 1);
1540                cl.set(Calendar.MONTH, 0);
1541                // '- 1' because calendar is 0-based for this field, and we are
1542                // 1-based
1543                cl.set(Calendar.YEAR, year);
1544                continue;
1545            }
1546            cl.set(Calendar.YEAR, year);
1547
1548            gotOne = true;
1549        } // while( !done )
1550
1551        return cl.getTime();
1552    }
1553
1554    /**
1555     * Advance the calendar to the particular hour paying particular attention
1556     * to daylight saving problems.
1557     *
1558     * @param cal  the calendar to operate on
1559     * @param hour the hour to set
1560     */
1561    protected void setCalendarHour(final Calendar cal, final int hour) {
1562        cal.set(java.util.Calendar.HOUR_OF_DAY, hour);
1563        if (cal.get(java.util.Calendar.HOUR_OF_DAY) != hour && hour != 24) {
1564            cal.set(java.util.Calendar.HOUR_OF_DAY, hour + 1);
1565        }
1566    }
1567
1568    /**
1569     * NOT YET IMPLEMENTED: Returns the time before the given time
1570     * that the <code>CronExpression</code> matches.
1571     */
1572    public Date getTimeBefore(final Date endTime) {
1573        // FUTURE_TODO: implement QUARTZ-423
1574        return null;
1575    }
1576
1577    /**
1578     * NOT YET IMPLEMENTED: Returns the final time that the
1579     * <code>CronExpression</code> will match.
1580     */
1581    public Date getFinalFireTime() {
1582        // FUTURE_TODO: implement QUARTZ-423
1583        return null;
1584    }
1585
1586    protected boolean isLeapYear(final int year) {
1587        return ((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0));
1588    }
1589
1590    protected int getLastDayOfMonth(final int monthNum, final int year) {
1591
1592        switch (monthNum) {
1593            case 1:
1594                return 31;
1595            case 2:
1596                return (isLeapYear(year)) ? 29 : 28;
1597            case 3:
1598                return 31;
1599            case 4:
1600                return 30;
1601            case 5:
1602                return 31;
1603            case 6:
1604                return 30;
1605            case 7:
1606                return 31;
1607            case 8:
1608                return 31;
1609            case 9:
1610                return 30;
1611            case 10:
1612                return 31;
1613            case 11:
1614                return 30;
1615            case 12:
1616                return 31;
1617            default:
1618                throw new IllegalArgumentException("Illegal month number: "
1619                        + monthNum);
1620        }
1621    }
1622
1623
1624    private class ValueSet {
1625        public int value;
1626
1627        public int pos;
1628    }
1629
1630
1631}