Ordering Intervals

Assuming that you have a "DateRange" class, containing a start and end date, is there a sensible way to order instances, sort them, or to test if one date range is "less than" another?

Although this page is cast in terms of DateRanges, it's really about ordering intervals, and the fact that it's using dates is essentially irrelevant. Issues specifically arising from dates have been left on OrderingDateRanges. For the remainder of this page, assume we're working in a single time zone.

Almost all of the discussion below is covered by the ideas of a "PartialOrder" - see that page for more details.

With intervals in general there are several obvious partial orders that you might want to consider.

[a,b] <= [c,d] iff b<=c. (In other words, if the two ranges are disjoint, or only overlap on the boundary).
[a,b] <= [c,d] iff a <= c <= d <= b (In other words, if one range includes another)
[a,b] <= [c,d] iff a<=c and b<=d

None of these is a total ordering, each is justifiable, and there are many more.

If you want to define a total ordering on an interval there are several you can choose from. The ordering you choose should remain transitive and non-symmetric, and there are several pitfalls. Note that one person's "obvious" total ordering will almost certainly be counter-intuitive to someone else. Any total ordering chosen should be "obvious" from the context in which it's used, otherwise its existence will probably do more harm than good.

[This discussion started on the TestIfDateRangesOverlap page]

See also MartinFowler's RangePattern; a DesignPattern for date (and other) ranges. (It includes date ranges, because dates are comparable, but does not talk about OrderingDateRanges.)

(There are also a few comments in here about DegenerateDateRanges?: A range where start date = end date, which may mean "no dates at all," depending on your definitions.)

Here are some different interpretations for saying that date range 1 ("January 15th through December 1st") is less than, equal to, or greater than date range 2 ("March 24th through August 3rd"):

Compare the start dates of the two ranges: January < March.
Compare the end dates of the two ranges: December > October.
Compare the "middle of each range": late June > late May ["center of gravity" sorting, described below, for history books.]
Compare length of each range: 10.5 months > 4.3 months
Compare start dates. If equal, compare end dates. January < March. (If equal, the shorter range would be first.) [If start and end dates are equal, isn't the length also equal?]

[From the note on TestIfDateRangesOverlap: "Q: Why document such a simple and obvious pattern/idiom?" / "A: It's not as obvious as you may think."]

...which is why DateRange should be a class. Like Dates, DateRanges can also be ordered. Sometimes I play with the idea of treating a Date as a degenerate DateRange. -- MichaelFeathers

I'd have thought DateRanges couldn't be ordered for essentially the same reason the complex numbers can't. -- RonJeffries

Does "January 4th to January 5th" come before or after "January 1st to December 25th?"

(Like many users, once you tell me what you've implemented, I'll say I want the other one. ;-)

What you mean is that there is no unique ordering of DateRanges which seems intuitively the "correct" one, as there is for scalars and things that can be conceptually mapped to scalars. As the paragraph below points out, it is certainly possible to come up with an ordering which is meaningful in some context.

One could also reasonably order DateRange objects by their duration.

What I think of, at times, is using the starting date as the primary comparison. It matches the language of the example above. 1/1-12/25 sure does come before 1/4-1/5. Would any other way of introducing order on ranges make sense? My guess is that it is a rather natural way of dealing with DateRanges in applications, but I have not tried it. Related.. complex numbers can be roughly ordered by magnitude. (-2 + 0i) would then be greater than (1 + 0i), which doesn't seem very useful. The question is whether there is a collection of uses which would make that worthwhile. I've forgotten whether MartinFowler's use of ranges has something like this. (can not remember all of his former employer's copy of the AnalysisPatterns book or the one he has on order)

Playing "the evil customer," as I mentioned above, I'll now tell you that I'm most concerned with when things end, because our department's job is to send notices, clean the room, and do all other "end of event" processing. So... 1/1-12/25 comes after 1/4-1/5.

(Of course, if you had put them in that order, I'd have said that I really wanted them in the 1/1, 1/4 order. ;-) -- JeffGrigg

Would any other way of introducing order on ranges make sense?

I sort my history books by DateRange. I use the "center of gravity" of the DateRange to order the DateRanges. There are examples on GreatBooksListJasperPaulsen. -- JasperPaulsen

As for degenerate date ranges... Points, squares, triangles, and rectangles are degenerate polygons. But that's probably not a very efficient implementation strategy. (And circles... Would you like to put an infinite number of points in that polygon?) -- JeffGrigg

I'm just looking for common interface. Implementation can hide behind it. Within a certain scope of use, Dates and DateRanges can behave the same. Dates and DateRanges are orderable, they have a starting point and an ending point (which may or may not be coincident) and a non-negative duration. One may include another or not, etc. -- MichaelFeathers

Funny question.. what is it in algebra when you have < and =, but not(a < b) and not(b < a) does not imply a = b. Um, besides a mess? I can see that treating a Date as a degenerate DateRange may not be clean from a mathematical point of view, but before () and after () do not have to be < and >. -- mf

Yes, if your definition of date range is that it does not include the end date/time, then a "date range" where start and end dates are equal is an empty set: Technically, it does not contain any date at all. Yes, you can "interpret" start and end being equal as a special case, but then your formal logic gets messed up, and you'll find yourself forced to code the "special case for equals" logic lots of places in your code. -- JeffGrigg

I think the official math formulation for complex is that you don't have <. I think you are supposed to have transitivity with <, but I could be wrong, I frequently am.

- The problem with an order on the complex numbers is not that it couldn't be transitive. We could just order by their magnitudes. Also, the problem of (z1<=z2 /\ z2<=z1) not implying z1=z2 is just a minor one (Technically, it would be a preorder). The real problem is that any defined order on the complex numbers (and there are infinitely many such) doesn't "interface" right with + and *. The usual laws connecting <=, + and * on the reals cannot be maintained in C. -- BjarkeEbert

Sets can be "ordered", i.e. for all a, b in S, either a < b or b < a or a = b. They can be partially ordered, where for some a and b, none of the above hold. And they can be unordered, with no relation < at all. My recollection is that the complex numbers are unordered. Their magnitudes, i.e. the real numbers, of course are.

Ah. The reason the complexes aren't ordered is, as Michael says above, you're supposed to know that if not (a < b) and not (b < a), then a = b. This wouldn't work for complex. And would it for DateRange? -- RonJeffries

Actually, the ComplexNumbers can be ordered completely.
1. Use the canonical representation of a*e^(i*theta) with theta the smallest non-negative, and then say that if the magnitudes are different then that determines the order, otherwise the angle determines the order.
2. Use the canonical representation z=x+iy and say that is the x values are different then use that, otherwise use the y value.

: These are both total, transitive and asymmetric. They also don't play nice with + or *. Any given set can be totally ordered. The question is always whether you can get an ordering that plays nice with other structures on the set.

I can make it work for date ranges:

  boolean operator< (DateRange &left, DateRange &right) {
    if (left.start < right.start) {
      return true;
    } else if (left.start = right.start) {
      if (left.end < right.end) {
        return true;
      } else if (left.end = right.end) {
        return false;   // (date ranges are equal)
      } else {
        assert(left.end > right.end);
        return false;
      }
    } else {
      assert(left.start > right.start);
      return false;
    }

-- JeffGrigg

A date range be plotted as a point in 2 dimensions, but what can we do with that? Does the area defined by that point, the start/end axis, and 0,0, mean anything? Is the slope of the line from 0,0 to start,end meaningful? Is there a relationship between two points, start1,end1 and start2,end2, such that we can mathematically determine if the ranges overlap or have other interesting properties?

Yes, dates and times offer fertile ground for class creation: When I say "June 27th," I'm usually referring to the whole day, not just the first millisecond of it. (...as is assumed with many Date/Time classes.) I've seen patterns for such things as "every Tuesday and Thursday from July 14th to September 10th of 1999." And, there's the concept of "3 hours, 2 minutes long," independent of start and end dates/times.

Hmmm... This is the opposite assumption: Using a single date/time value as if it were a date range. When my Date variable has the value "exactly midnight at the start of January 1st, 2001," which of the following does it represent...

That instant of time only.
That millisecond only.
That first second or minute.
That day -- 24 hours, starting at that point.
That month.
That year.

As a stored representation, written to a database or file, it could be any of the above. (As an instance of a class in an application, it's behavior should clarify the situation.) -- JeffGrigg

"January 16th, 2001" is a date. Is "January 2001" a date range?

I think it is -- it's the range "[2001-01-01, 2001-02-01)". Now inside my "OneMonth" date class, I might store it as "month 01, year 2001," or as "month starting at date/time "2001-01-01 00:00:00.000," or as "DateRange(2001-01-01, 2001-02-01)" (with or without "zero times"). But the great thing about classes is that I can encapsulate those implementation decisions -- my class conforms to the DateRange interface, and callers don't need to worry about how I accomplish it. -- JeffGrigg