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