Algorithm to determine if a given date/time is between two date/time pairs

Question

I have an array of dates in a one week range stored in an unusual way.

The Dates are stored in this numeric format: 12150

From left to right:

1st digit represents day: 1 = sunday, 2 = monday, 3 = tuesday, ...., 7 = saturday

next two digits represent hour in a 24 hour system: 00 = midnight, 23 = 11pm

next two digits represent minutes: 00-59

Given an input date and a start date and end date I need to know if the input date is between the start and end date.

I have an algorithm right now that I think works 100% of the time, but I am not sure.

In any case, I think there is probably a better and simpler way to do this and I was wondering if anybody knew what that algorithm was.

If not it would be cool if someone could double check my work and verify that it does actually work for 100% of valid cases.

What I have right now is:

if (startDate < inputDate && 
    endDate > inputDate) {
        inRange = yes;    
}
else if (endDate < startDate) {
        if((inputDate + 72359) > startDate &&
          (inputDate + 72359) < endDate) {
          inRange = yes; 
        }
        else if((inputDate + 72359) > startDate &&
               (inputDate + 72359) < (endDate + 72359)) {
          inRange = yes;   
        }

}

Answer 1

How about

const int MAX = 72460; // Or anything more than the highest legal value
inRange = (MAX + inputDate - startDate) % MAX < 
          (MAX + endDate - startDate) % MAX;

This assumes of course that all the dates are well formed (according to your specs).

This addresses the case where the start is "after" the end. (e.g. Friday is in range if start is Wednesday and end is Monday)

It may take a second to see (which probably isn't good, because readability is usually the most important) but I think it does work.

Here's the basic trick:

Legend: 

  0: Minimum time
  M: Maximum time

  S: Start time
  1,2,3: Input Time test points
  E: End Time

The S  E => Not in range
  2  In range
  3 > E => Not in range

The S > E case
                        0                 M
  Original              -1--E----2---S--3--
  Add Max               -------------------1--E----2---S--3--
  Subtract StartDate    ------1--E----2---S--3--      
  % Max                 S--3--1--E----2----

  1  In range
  2 > E => Not in range
  3  In range

If you really want to go nuts (and be even more difficult to decipher)

const int MAX = 0x20000; 
const int MASK = 0x1FFFF;
int maxMinusStart = MAX - startDate;
inRange = (maxMinusStart + inputDate) & MASK < 
          (maxMinusStart + endDate) & MASK;

which ought to be slightly faster (trading modulus for a bitwise and) which we can do since the value of MAX doesn't really matter (as long as it exceeds the maximum well-formed value) and we're free to choose one that makes our computations easy.

(And of course you can replace the < with a <= if that's what you really need)

Answer 2

There is some logic error with dates in that format. Since the month and year information is missing, you cannot know what calendar day is missing. e.g. 50755 might be Thursday March 12 2009, but it might just as well be exactly a week ago, or 18 weeks ahead. That for you could never be 100% sure if any date in that format is between any other 2 dates.

Answer 3

Here the condition of the inner if can never be true, since endDate < startDate:

if (endDate < startDate) {
  if((inputDate + 72359) > startDate &&
    (inputDate + 72359) < endDate) {
    // never reached
    inRange = yes; 
  }

The following if also can't be optimal, since the first part is always true and the second part is just identical to inputDate < endDate:

  if((inputDate + 72359) > startDate &&
     (inputDate + 72359) < (endDate + 72359))

I think you want something like this:

if (startDate < endDate)
  inRange = (startDate < inputDate) && (inputDate < endDate);
else
  inRange = (startDate < inputDate) || (inputDate < endDate);

Answer 4

you should use >= and <= if you really want it in range

say i pick this date 10000 or 72359, how you would handle this? it is in range or not?

also i didn't know value for startDate and endDate since you didn't initialize it, correct me if i were wrong, variable that didn't initialized will start with 0 or null or ''

so i assume the startDate = 10000 and endDate 72359

btw why you pick this kind of array (as int or string value?) why first value was day? not date example:
010000 -> date 1st of the month 00:00
312359 -> date 31th of the month 23:59

but it's up to you :D

so sorry if i were wrong i took algorithm class only on university and it was 5 years ago :D

Answer 5

A better approach might be to normalize your data converting all the day of the week values to be relative to the start date. Something like this:

const int dayScale = 10000;  // scale factor for the day of the week

int NormalizeDate(int date, int startDay) 
{
    int day = (date / dayScale) - 1;  // this would be a lot easier if Sunday was 0 
    int sday = startDay - 1;  

    if (day < sday)  
        day = (day + 7 - sday) % 7;

    return ((day+1) * dayScale) + (date % dayScale);
}

int startDay = startDate / dayScale;  // isolate the day of the week

int normalizedStartDate = NormalizeDate(startDate, startDay);
int normalizedEndDate = NormalizeDate(endDate, startDay);
int normalizedInputDate = NormalizeDate(inputDate, startDay);

inRange = normalizedInputDate >= normalizedStartDate && 
          normalizedInputDate <= normalizedEndDate;

I am pretty sure this will work as written. In any case, the concept is cleaner that multiple comparisons.