/*
 * Copyright (c) 2002-2003 by OpenSymphony
 * All rights reserved.
 */
package com.opensymphony.oscache.util;

import java.text.ParseException;

import java.util.*;
import java.util.Calendar;

/**
 * Parses cron expressions and determines at what time in the past is the
 * most recent match for the supplied expression.
 *
 * @author <a href="&#109;a&#105;&#108;&#116;&#111;:chris&#64;swebtec.&#99;&#111;&#109;">Chris Miller</a>
 * @author $Author: ltorunski $
 * @version $Revision: 340 $
 */
public class FastCronParser {
    private static final int NUMBER_OF_CRON_FIELDS = 5;
    private static final int MINUTE = 0;
    private static final int HOUR = 1;
    private static final int DAY_OF_MONTH = 2;
    private static final int MONTH = 3;
    private static final int DAY_OF_WEEK = 4;

    // Lookup tables that hold the min/max/size of each of the above field types.
    // These tables are precalculated for performance.
    private static final int[] MIN_VALUE = {0, 0, 1, 1, 0};
    private static final int[] MAX_VALUE = {59, 23, 31, 12, 6};

    /**
     * A lookup table holding the number of days in each month (with the obvious exception
     * that February requires special handling).
     */
    private static final int[] DAYS_IN_MONTH = {
        31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31
    };

    /**
     * Holds the raw cron expression that this parser is handling.
     */
    private String cronExpression = null;

    /**
    * This is the main lookup table that holds a parsed cron expression. each long
    * represents one of the above field types. Bits in each long value correspond
    * to one of the possbile field values - eg, for the minute field, bits 0 -> 59 in
    * <code>lookup[MINUTE]</code> map to minutes 0 -> 59 respectively. Bits are set if
    * the corresponding value is enabled. So if the minute field in the cron expression
    * was <code>"0,2-8,50"</code>, bits 0, 2, 3, 4, 5, 6, 7, 8 and 50 will be set.
    * If the cron expression is <code>"*"</code>, the long value is set to
    * <code>Long.MAX_VALUE</code>.
    */
    private long[] lookup = {
        Long.MAX_VALUE, Long.MAX_VALUE, Long.MAX_VALUE, Long.MAX_VALUE,
        Long.MAX_VALUE
    };

    /**
    * This is based on the contents of the <code>lookup</code> table. It holds the
    * <em>highest</em> valid field value for each field type.
    */
    private int[] lookupMax = {-1, -1, -1, -1, -1};

    /**
    * This is based on the contents of the <code>lookup</code> table. It holds the
    * <em>lowest</em> valid field value for each field type.
    */
    private int[] lookupMin = {
        Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE,
        Integer.MAX_VALUE, Integer.MAX_VALUE
    };

    /**
    * Creates a FastCronParser that uses a default cron expression of <code>"* * * * *"</cron>.
    * This will match any time that is supplied.
    */
    public FastCronParser() {
    }

    /**
    * Constructs a new FastCronParser based on the supplied expression.
    *
    * @throws ParseException if the supplied expression is not a valid cron expression.
    */
    public FastCronParser(String cronExpression) throws ParseException {
        setCronExpression(cronExpression);
    }

    /**
    * Resets the cron expression to the value supplied.
    *
    * @param cronExpression the new cron expression.
    *
    * @throws ParseException if the supplied expression is not a valid cron expression.
    */
    public void setCronExpression(String cronExpression) throws ParseException {
        if (cronExpression == null) {
            throw new IllegalArgumentException("Cron time expression cannot be null");
        }

        this.cronExpression = cronExpression;
        parseExpression(cronExpression);
    }

    /**
    * Retrieves the current cron expression.
    *
    * @return the current cron expression.
    */
    public String getCronExpression() {
        return this.cronExpression;
    }

    /**
    * Determines whether this cron expression matches a date/time that is more recent
    * than the one supplied.
    *
    * @param time The time to compare the cron expression against.
    *
    * @return <code>true</code> if the cron expression matches a time that is closer
    * to the current time than the supplied time is, <code>false</code> otherwise.
    */
    public boolean hasMoreRecentMatch(long time) {
        return time < getTimeBefore(System.currentTimeMillis());
    }

    /**
    * Find the most recent time that matches this cron expression. This time will
    * always be in the past, ie a lower value than the supplied time.
    *
    * @param time The time (in milliseconds) that we're using as our upper bound.
    *
    * @return The time (in milliseconds) when this cron event last occurred.
    */
    public long getTimeBefore(long time) {
        // It would be nice to get rid of the Calendar class for speed, but it's a lot of work...
        // We create this
        Calendar cal = new GregorianCalendar();
        cal.setTimeInMillis(time);

        int minute = cal.get(Calendar.MINUTE);
        int hour = cal.get(Calendar.HOUR_OF_DAY);
        int dayOfMonth = cal.get(Calendar.DAY_OF_MONTH);
        int month = cal.get(Calendar.MONTH) + 1; // Calendar is 0-based for this field, and we are 1-based
        int year = cal.get(Calendar.YEAR);

        long validMinutes = lookup[MINUTE];
        long validHours = lookup[HOUR];
        long validDaysOfMonth = lookup[DAY_OF_MONTH];
        long validMonths = lookup[MONTH];
        long validDaysOfWeek = lookup[DAY_OF_WEEK];

        // Find out if we have a Day of Week or Day of Month field
        boolean haveDOM = validDaysOfMonth != Long.MAX_VALUE;
        boolean haveDOW = validDaysOfWeek != Long.MAX_VALUE;

        boolean skippedNonLeapYear = false;

        while (true) {
            boolean retry = false;

            // Clean up the month if it was wrapped in a previous iteration
            if (month < 1) {
                month += 12;
                year--;
            }

            // get month...................................................
            boolean found = false;

            if (validMonths != Long.MAX_VALUE) {
                for (int i = month + 11; i > (month - 1); i--) {
                    int testMonth = (i % 12) + 1;

                    // Check if the month is valid
                    if (((1L << (testMonth - 1)) & validMonths) != 0) {
                        if ((testMonth > month) || skippedNonLeapYear) {
                            year--;
                        }

                        // Check there are enough days in this month (catches non leap-years trying to match the 29th Feb)
                        int numDays = numberOfDaysInMonth(testMonth, year);

                        if (!haveDOM || (numDays >= lookupMin[DAY_OF_MONTH])) {
                            if ((month != testMonth) || skippedNonLeapYear) {
                                // New DOM = min(maxDOM, prevDays);  ie, the highest valid value
                                dayOfMonth = (numDays <= lookupMax[DAY_OF_MONTH]) ? numDays : lookupMax[DAY_OF_MONTH];
                                hour = lookupMax[HOUR];
                                minute = lookupMax[MINUTE];
                                month = testMonth;
                            }

                            found = true;
                            break;
                        }
                    }
                }

                skippedNonLeapYear = false;

                if (!found) {
                    // The only time we drop out here is when we're searching for the 29th of February and no other date!
                    skippedNonLeapYear = true;
                    continue;
                }
            }

            // Clean up if the dayOfMonth was wrapped. This takes leap years into account.
            if (dayOfMonth < 1) {
                month--;
                dayOfMonth += numberOfDaysInMonth(month, year);
                hour = lookupMax[HOUR];
                continue;
            }

            // get day...................................................
            if (haveDOM && !haveDOW) { // get day using just the DAY_OF_MONTH token

                int daysInThisMonth = numberOfDaysInMonth(month, year);
                int daysInPreviousMonth = numberOfDaysInMonth(month - 1, year);

                // Find the highest valid day that is below the current day
                for (int i = dayOfMonth + 30; i > (dayOfMonth - 1); i--) {
                    int testDayOfMonth = (i % 31) + 1;

                    // Skip over any days that don't actually exist (eg 31st April)
                    if ((testDayOfMonth <= dayOfMonth) && (testDayOfMonth > daysInThisMonth)) {
                        continue;
                    }

                    if ((testDayOfMonth > dayOfMonth) && (testDayOfMonth > daysInPreviousMonth)) {
                        continue;
                    }

                    if (((1L << (testDayOfMonth - 1)) & validDaysOfMonth) != 0) {
                        if (testDayOfMonth > dayOfMonth) {
                            // We've found a valid day, but we had to move back a month
                            month--;
                            retry = true;
                        }

                        if (dayOfMonth != testDayOfMonth) {
                            hour = lookupMax[HOUR];
                            minute = lookupMax[MINUTE];
                        }

                        dayOfMonth = testDayOfMonth;
                        break;
                    }
                }

                if (retry) {
                    continue;
                }
            } else if (haveDOW && !haveDOM) { // get day using just the DAY_OF_WEEK token

                int daysLost = 0;
                int currentDOW = dayOfWeek(dayOfMonth, month, year);

                for (int i = currentDOW + 7; i > currentDOW; i--) {
                    int testDOW = i % 7;

                    if (((1L << testDOW) & validDaysOfWeek) != 0) {
                        dayOfMonth -= daysLost;

                        if (dayOfMonth < 1) {
                            // We've wrapped back a month
                            month--;
                            dayOfMonth += numberOfDaysInMonth(month, year);
                            retry = true;
                        }

                        if (currentDOW != testDOW) {
                            hour = lookupMax[HOUR];
                            minute = lookupMax[MINUTE];
                        }

                        break;
                    }

                    daysLost++;
                }

                if (retry) {
                    continue;
                }
            }

            // Clean up if the hour has been wrapped
            if (hour < 0) {
                hour += 24;
                dayOfMonth--;
                continue;
            }

            // get hour...................................................
            if (validHours != Long.MAX_VALUE) {
                // Find the highest valid hour that is below the current hour
                for (int i = hour + 24; i > hour; i--) {
                    int testHour = i % 24;

                    if (((1L << testHour) & validHours) != 0) {
                        if (testHour > hour) {
                            // We've found an hour, but we had to move back a day
                            dayOfMonth--;
                            retry = true;
                        }

                        if (hour != testHour) {
                            minute = lookupMax[MINUTE];
                        }

                        hour = testHour;
                        break;
                    }
                }

                if (retry) {
                    continue;
                }
            }

            // get minute.................................................
            if (validMinutes != Long.MAX_VALUE) {
                // Find the highest valid minute that is below the current minute
                for (int i = minute + 60; i > minute; i--) {
                    int testMinute = i % 60;

                    if (((1L << testMinute) & validMinutes) != 0) {
                        if (testMinute > minute) {
                            // We've found a minute, but we had to move back an hour
                            hour--;
                            retry = true;
                        }

                        minute = testMinute;
                        break;
                    }
                }

                if (retry) {
                    continue;
                }
            }