How to improve this algorithm which fills up a calendar grid?

Question

I have Grid which will render a calendar, and I'm provided with an ArrayList<CalendarEventEntity> which contains events. Those events have to be highlighted in the grid.

As I have to fill the grid by my self I have something like this:

for( loop through the days of the month ){
    Calendar eventDate = event.getDate();
    // look for the events in the calendar that matchs this day
    for(CalendarEventEntity event : events) {
        // if there are events in this specific day
        if( eventDate.get(Calendar.YEAR) == calendarMonth.get(Calendar.YEAR) &&
            eventDate.get(Calendar.MONTH) == calendarMonth.get(Calendar.MONTH) &&
            eventDate.get(Calendar.DAY_OF_MONTH) == dayIndex ) {
            // highlight it!!!
        }
    }

}

This works fine, but it's too slow. So I want to speed it up! I added this before the inner for:

// ignore dates which does not make part of this month or year
if( eventDate.get(Calendar.YEAR) < calendarMonth.get(Calendar.YEAR) ||
    eventDate.get(Calendar.MONTH) < calendarMonth.get(Calendar.MONTH) ||
    eventDate.get(Calendar.DAY_OF_MONTH) != DateIdx ) {
    continue;
}

// stop when processing dates which are higher than this month or year
if( eventDate.get(Calendar.YEAR) > calendarMonth.get(Calendar.YEAR) ||
    eventDate.get(Calendar.MONTH) > calendarMonth.get(Calendar.MONTH) 
    || eventDate.get(Calendar.DAY_OF_MONTH) != DateIdx ) {
    break;
}

and that made if faster, but it's still too slow. How can I improve this algorithm?

Answer 1

The problem is that each day you have to search every event looking for events on that date. You need to find a way to only be searching through events on that day, or to know if events are on that day at all.

You should consider using a HashMap to store your events indexed by date. Then you can just check to see if there's a HashMap entry for the day in question. You'll have to pick a way to represent a day that would be universal enough to be used as a key.

This will also be handy when you have to drill down into the details of one specific day and show only the events on that day. You shouldn't have to search through all events every time you want to find events for one specific day.

Answer 2

This is a classic example of a problem that would benefit from using a (sorted) tree. Java provides one in TreeMap. You can get events that begin on a day using the subMap method. Calendar implements Comparable, so it should just work. (Use the calendar entries as keys; use subMap from the last second of the preceding day to the first second of the following day to get all events that are on the day in question.)

If you have many multi-day events, then you'd need an interval tree, but it might just be easier to split the single event "Five Day Workshop" into five entries "Workshop, Day One of Five" etc. so that no events spill over from one day to another.