Java: How do I store a timeline/schedule, location full or empty from time x to y (interval)?

Question

Some brief background:

I have a java app that's used to see when certain locations (classrooms) are in use or not. The user puts a location identifier into a search box and the program displays any events (classes) matching. The app will display all the pertinent information (class name, room #, professor name, day of week, time of class), classes that are in-session (or soon to be) are color-coded so you can tell at-a-glance if there's anything coming up. The data comes from an html page I'm scraping from (I don't have SQL access).

Everything to this point works, I'm using JavaSwing for the UI. The events are stored as a basic object I made to hold it, the only part that matters for my question is that it stores to Java Date objects for the start and end time of each event.

What I'm trying to do now is add a way to check for and display the gaps between events (when a classroom is empty). I have all the data I need (all the start and end times) but I'm having trouble coming up with a way to actually to actually code the program to see the gaps.

And if that's not challenging enough: I want to implement it as simply as possible, not using any extra libraries. I don't want to re-create the wheel, but I'd much rather hash out the code by hand than just throw in an import and a couple method calls; half the point of this project is to challenge myself.

For now I'm not looking for advice on how to actually display the data, for now I'm just trying to logically organize it in a usable way. It will end up being displayed in a JTable, but I'm not working on that implementation yet.

---

My scraper pulls from an html table something like <td id=time>10:00AM - 11:15AM</td> and parses it down to two strings 10:00AM and 11:15AM. These get passed with other data to my Course object.

My Course object has a DateFormat set so it can interpret the incoming Strings into Dates.

public class Course {

static DateFormat tf = new SimpleDateFormat("h:mma");
private String name;
private String room;
private String instructor;
private Date start;
private Date end;
private String days;

public Course(String n, String r, String in, String st, String ed, String d) throws ParseException{
    name=n;
    room=r;
    instructor=in;
    start=tf.parse(st);
    end=tf.parse(ed);
    days=d;
}

//...basic getters, setters, and a toString()

The idea is that I'll set two times, setting the window in which I want to check for gaps. I want to pick an interval, say 15 minutes, and find all the gaps of 15 or more minutes during which a classroom is empty, i.e. no classes meeting.

Answer 1

I don't have a complete answer, but I have some suggestions.

Time Zone

A Date represents a date-time in UTC/GMT, that is, no time zone offset. Your values are in a time zone. In the long run, you'll be better off by not ignoring that time zone. Adjust your values. Generally think, work, and store date-times in UTC/GMT. Convert to local time as needed for presentation in the user interface.

While a java.util.Date has no time zone, a Joda-Time DateTime (discussed below) does indeed know its own time zone and time zone offset.

Avoid java.util.Date/Calendar

The java.util.Date and Calendar classes bundled with Java are notoriously troublesome. Avoid them.

Instead, use either:

• Joda-Time
• The new java.time.* package in Java 8.
  That package is inspired by Joda-Time, defined by JSR 310, and supplants the old bundled classes.

Don't think of Joda-Time as any old "extra library". The first thing I do when creating a new project in my IDE is add the Joda-Time library. It is just that good. Or j.u.Date/Calendar is just that bad, depending on your perspective.

Start Inclusive, End Exclusive

The best way to handle a span of time is to make the beginning inclusive and the ending exclusive. Write logic where you check for GREATER THAN OR EQUALS to the beginning and LESS THAN the ending (not testing for equals on the ending). I discuss this more in another answer along with a diagram.

Joda-Time

Joda-Time offers these classes for defining a span of time: Period, Duration, and Internal. The Hours and similar classes offer some handy utility methods.

Find Gaps

If your goal is to make a list of gaps, of spans of time where a classroom is not assigned to a class, then the obvious way it seems to me is to sort the classes chronologically (and by classroom) as in the answer by Rob Whiteside. Define an "available" span of time where its beginning is the prior class’ ending, and its ending is the next class’ beginning. I've no experience in this arena, so there may be a more clever way.

See this question about sorting a List of Intervals.

Example Code

Here is some example code using Joda-Time 2.3.

Specify a time zone rather than rely on default…

DateTimeZone timeZone = DateTimeZone.forID( "Europe/Paris" );

Create three classes as sample data, in arbitrary order…

Interval class_math = new Interval( new DateTime( 2014, 1, 24, 10, 0, 0, timeZone ), new DateTime( 2014, 1, 24, 11, 15, 0, timeZone ) );
Interval class_chemistry = new Interval( new DateTime( 2014, 1, 24, 8, 0, 0, timeZone ), new DateTime( 2014, 1, 24, 9, 15, 0, timeZone ) );
Interval class_french_lit = new Interval( new DateTime( 2014, 1, 24, 13, 0, 0, timeZone ), new DateTime( 2014, 1, 24, 14, 15, 0, timeZone ) );

Collect the sample data into a List…

java.util.List<Interval> classes = new java.util.ArrayList<Interval>( 3 );
classes.add( class_math );
classes.add( class_chemistry );
classes.add( class_french_lit );
System.out.println( "classes unsorted: " + classes );

Sort the List using a custom Comparator (see class definition below)…

java.util.Collections.sort( classes, new IntervalStartComparator() );
System.out.println( "classes sorted: " + classes );

Make a collection of objects representing each gap between classes we find…

java.util.List<Interval> gaps = new java.util.ArrayList<Interval>();

DateTime gapStart = null, gapStop = null;
for ( int i = 0; i < classes.size(); i++ ) {
    // For each class, take the prior class' end as the gap's beginning, and the next class' start as the gap's ending.
    Interval session = classes.get( i ); // Cannot name the var "class" because that is a keyword in Java.
    if ( i == 0 ) { // If first time through, grab the end of the first class as our first gap's start.
        gapStart = session.getEnd();
        continue;
    }
    gapStop = session.getStart();
    Interval gap = new Interval( gapStart, gapStop );
    gaps.add( gap );
    gapStart = session.getEnd();
}

System.out.println( "gaps: " + gaps );

The class definition for the Comparator used in code above and lifted from this answer by Jon Skeet…

class IntervalStartComparator implements java.util.Comparator<Interval> {

    @Override
    public int compare( Interval x, Interval y ) {
        return x.getStart().compareTo( y.getStart() );
    }
}

When run…

classes unsorted: [2014-01-24T10:00:00.000+01:00/2014-01-24T11:15:00.000+01:00, 2014-01-24T08:00:00.000+01:00/2014-01-24T09:15:00.000+01:00, 2014-01-24T13:00:00.000+01:00/2014-01-24T14:15:00.000+01:00]
classes sorted: [2014-01-24T08:00:00.000+01:00/2014-01-24T09:15:00.000+01:00, 2014-01-24T10:00:00.000+01:00/2014-01-24T11:15:00.000+01:00, 2014-01-24T13:00:00.000+01:00/2014-01-24T14:15:00.000+01:00]
gaps: [2014-01-24T09:15:00.000+01:00/2014-01-24T10:00:00.000+01:00, 2014-01-24T11:15:00.000+01:00/2014-01-24T13:00:00.000+01:00]

Duration

You said you only care about gaps at least 15 minutes long. A Duration instance in Joda-Time represents the milliseconds between the start and stop points of an Interval.

Here is some untested off-the-top-of-my-head code.

Renamed "gap" var from above to "gapInterval" to remind you it is an Interval instance.

Note that Minutes is a class. The "minutes" var seen below is an instance, not an integer primitive ("int"). Calling the getMinutes method renders an int primitive.

Duration duration = gapInterval.toDuration();
Minutes minutes = duration.toStandardMinutes(); // "Standard" means ignoring time zone anomalies such as Daylight Saving Time (DST).
int mins = minutes.getMinutes();
boolean isGapSignificant = ( mins >= 15 );

ISO 8601

The string outputs you see there are not arbitrary. Those are ISO 8601 formats. That handy standard defines string representations of single date-time values as well as the <start>/<end> time interval.

That standard also defines a string representation of durations that may prove useful to you, in the format of PnYnMnDTnHnMnS such as "P3Y6M4DT12H30M5S" meaning "three years, six months, four days, twelve hours, thirty minutes, and five seconds". Or shorter, as in your case, a class may be PT1H15M for one and a quarter hours.

Joda-Time uses ISO 8601 as its default for most everything, as both inputs and outputs.

Answer 2

Sorting is probably the key to your problem here.

Presumably you have a big collection of all the courses you've scraped. First you'll need to be able to pull out all the courses given a particular location into a new list. You'll want this list to be sorted by the course date. Check out the various sorted collections (e.g. TreeSet). You'll probably also need to make use of a "comparator" to make sure your courses get sorted by their date.

Once you have that list, it's just a matter of iterating over it and finding the gaps.