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