Recursive algorithm for coalescing / collapsing list of dates into ranges.

Question

Given a list of dates

12/07/2010
13/07/2010
14/07/2010
15/07/2010
12/08/2010
13/08/2010
14/08/2010
15/08/2010
19/08/2010
20/08/2010
21/08/2010

I'm looking for pointers towards a recursive pseudocode algorithm (which I can translate into a FileMaker custom function) for producing a list of ranges, i.e.

12/07/2010 to 15/07/2010, 12/08/2010 to 15/08/2010, 19/08/2010 to 20/08/2010

The list is presorted and de-duplicated. I've tried starting from both the first value and working forwards, and the last value and working backwards but I just can't seem to get it to work. Having one of those frustrating days... It would be nice if the signature was something like

CollapseDateList( dateList, separator, ellipsis )

:-)

Answer 1

The main routine would look something like this:

List<String> list  = new ArrayList<String>();

String firstDate   = dateList[0];
String lastDate    = dateList[0];
String currentDate = dateList[0];

for (int i = 1; i < dateList.length(); i++) {
    if (dateDiff(dateList[i], currentDate) == 1) {
        lastDate   = dateList[i];
    } else {
        list.add(firstDate + separator + lastDate);
        firstDate = dateList[i];
        lastDate  = dateList[i];
    }
    currentDate = dateList[i];
}
list.add(firstDate + separator + lastDate);

I'm assuming you have some function that tells you if two dates are consecutive or not.

Answer 2

Here's the recursive FileMaker code that does the job. The basic approach is to do the replacement in place, where necessary calculating the date from the last date (right most word) within a value. That way it can decide to when to check if the next value is still part of the first range, or mark the first range as done and focus in on the rest of the values. Hope it helps someone else.

// CollapseDateList( dates, comma, dash)

Let(
  countDates = ValueCount ( dates );

  If (
    countDates < 2 ; dates;  // return the dates we've been given...

    Let(
      [ 
        start_date = GetAsDate( LeftWords( GetValue ( dates ; 1 ); 1 ) );
        date_1 = GetAsDate( RightWords( GetValue ( dates ; 1 ); 1 ) );
        date_2 = GetAsDate( GetValue ( dates ; 2 ) );
        date_3 = GetAsDate( GetValue ( dates ; 3 ) );
        dv_1 = GetAsNumber( date_1 );
        dv_2 = GetAsNumber( date_2 );
        dv_3 = GetAsNumber( date_3 );
        twoFollowsOne = (dv_2 = dv_1 + 1);
        threeFollowsTwo = (dv_3 = dv_2 + 1)
      ];

       // compare dates
      Case(
        // only two dates in list
        countDates = 2;
          if (
            twoFollowsOne;
            start_date & dash & date_2;
            GetValue ( dates ; 1 ) & comma & date_2
          );

        // first three values are sequential
        threeFollowsTwo and twoFollowsOne; 
          CollapseDateList( start_date & dash & date_3 & ¶ & RightValues( dates; countDates - 3 ); comma; dash );

        // first two values are sequential only
        not threeFollowsTwo and twoFollowsOne; 
          start_date & dash & date_2 & comma & CollapseDateList(  RightValues(  dates; countDates - 2 ); comma; dash );

        // first two values are not sequential 
        // default
        GetValue ( dates ; 1 ) & comma & CollapseDateList( RightValues( dates; countDates - 1 ); comma; dash )
      ) 
    )
  )
)