View Javadoc
1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements. See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache license, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License. You may obtain a copy of the License at
8    *
9    *      http://www.apache.org/licenses/LICENSE-2.0
10   *
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the license for the specific language governing permissions and
15   * limitations under the license.
16   */
17  package org.apache.logging.log4j.core.util;
18  
19  /*
20   * This file originated from the Quartz scheduler with no change in licensing.
21   * Copyright Terracotta, Inc.
22   */
23  
24  import java.text.ParseException;
25  import java.util.Calendar;
26  import java.util.Date;
27  import java.util.HashMap;
28  import java.util.Iterator;
29  import java.util.Locale;
30  import java.util.Map;
31  import java.util.SortedSet;
32  import java.util.StringTokenizer;
33  import java.util.TimeZone;
34  import java.util.TreeSet;
35  
36  /**
37   * Provides a parser and evaluator for unix-like cron expressions. Cron
38   * expressions provide the ability to specify complex time combinations such as
39   * "At 8:00am every Monday through Friday" or "At 1:30am every
40   * last Friday of the month".
41   * <P>
42   * Cron expressions are comprised of 6 required fields and one optional field
43   * separated by white space. The fields respectively are described as follows:
44   * <p/>
45   * <table cellspacing="8">
46   * <tr>
47   * <th align="left">Field Name</th>
48   * <th align="left">&nbsp;</th>
49   * <th align="left">Allowed Values</th>
50   * <th align="left">&nbsp;</th>
51   * <th align="left">Allowed Special Characters</th>
52   * </tr>
53   * <tr>
54   * <td align="left"><code>Seconds</code></td>
55   * <td align="left">&nbsp;</th>
56   * <td align="left"><code>0-59</code></td>
57   * <td align="left">&nbsp;</th>
58   * <td align="left"><code>, - * /</code></td>
59   * </tr>
60   * <tr>
61   * <td align="left"><code>Minutes</code></td>
62   * <td align="left">&nbsp;</th>
63   * <td align="left"><code>0-59</code></td>
64   * <td align="left">&nbsp;</th>
65   * <td align="left"><code>, - * /</code></td>
66   * </tr>
67   * <tr>
68   * <td align="left"><code>Hours</code></td>
69   * <td align="left">&nbsp;</th>
70   * <td align="left"><code>0-23</code></td>
71   * <td align="left">&nbsp;</th>
72   * <td align="left"><code>, - * /</code></td>
73   * </tr>
74   * <tr>
75   * <td align="left"><code>Day-of-month</code></td>
76   * <td align="left">&nbsp;</th>
77   * <td align="left"><code>1-31</code></td>
78   * <td align="left">&nbsp;</th>
79   * <td align="left"><code>, - * ? / L W</code></td>
80   * </tr>
81   * <tr>
82   * <td align="left"><code>Month</code></td>
83   * <td align="left">&nbsp;</th>
84   * <td align="left"><code>0-11 or JAN-DEC</code></td>
85   * <td align="left">&nbsp;</th>
86   * <td align="left"><code>, - * /</code></td>
87   * </tr>
88   * <tr>
89   * <td align="left"><code>Day-of-Week</code></td>
90   * <td align="left">&nbsp;</th>
91   * <td align="left"><code>1-7 or SUN-SAT</code></td>
92   * <td align="left">&nbsp;</th>
93   * <td align="left"><code>, - * ? / L #</code></td>
94   * </tr>
95   * <tr>
96   * <td align="left"><code>Year (Optional)</code></td>
97   * <td align="left">&nbsp;</th>
98   * <td align="left"><code>empty, 1970-2199</code></td>
99   * <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  */
197 public 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 }