Ever had to do date math where you need to detect conflict schedules? Recently, I had to do some data analysis that involved checking for potential conflicts in a schedule, counting them, and figuring out how big the conflicts were. This isn't a live schedule, it's historical scheduling data used to model future demand against available resources. The idea is to surface obvious material shortfalls. If you were an event planner, you might use October 2016 demand to project 2017 demand to see if you have enough chairs, caterers, dancing bears, clowns, kegs of beer, etc. available. \Of course, scheduling efficiency and other constraints might be issues, but that's not what this model is working on...it's trying to measure fixed inventory against projected demand to see if more inventory is needed. Right, too much backstory...welcome to me.
Anyway, I've always "hated" date math. As it turns out, I just wasn't looking for existing solutions efficiently and I don't hate date math at all now. It didn't take long to find out that time interval calculations have been studied exhaustively as have algorithms for doing conflict detection, optimal fitting, etc. In my case, I just need a couple of things: * Do these two time ranges intersect? * By how much? My particular problem takes more than that to sort out, and I also do another form of projection that's a tweak on this, but that's the nub of the interval math right there. As a highlight of what I'm talking about, here are some comments adapted from a StackOverflow post on the subject: // Great explanation on StackOverflow here: // https://stackoverflow.com/questions/143552/comparing-date-ranges/143568#143568 // Best. Ascii. Diagram. Ever. This blocks out eleven possible interval comparison outcomes. // I've added discussion of two special cases and show what catches them. -- DPA // |-------------------| compare to this one // |---------| contained within // |----------| contained within, equal start // |-----------| contained within, equal end // |-------------------| contained within, equal start+end // |------------| not fully contained, overlaps start // |---------------| not fully contained, overlaps end // |-------------------------| overlaps start, bigger // |-----------------------| overlaps end, bigger // |------------------------------| // on the other hand, let me post all those that don't overlap: // // |-------------------| compare to this one // |---| ends before // |---| starts after // Notes about two possibly confusing cases // |-------------------| compare to this one // |-----| ends at start is a case of // |------------| not fully contained, overlaps start // |-------------------| compare to this one // |-----| starts at end is a case of // |---------------| not fully contained, overlaps end Below I'm posting a method for calculating the overlap between two time ranges in seconds. A few notes: * All of this code assumes and requires date times on a consistent timezone. If you do a lot of datetime stuff and haven't already moved everything to Zulu with offsets stored somewhere for display purposes, your making your life needlessly hard. But all this code requires is that datetimes are on the same time zone, whatever that is. * Midnight is just another moment like any other, with datetimes, midnight doesn't take any special consideration. * The routine has minimal error checking on the parameters. It chokes on end times earlier than start times and that's it. It doesn't detect 0000 type times and those might screw you up. * There are a bunch of subroutines listed that I'm not posting. Most folks will have their own versions or use a different style that doesn't require some of my subroutines. (I'm big on parameter checking, most people aren't.) * I didn't write the date time utilities and haven't even looked at them. They work, that's all I know. * I've also included a manual test routine that works in conjunction with the main method. Good luck trying to do something like this without a test case that you can run over an over until all of the bugs quit moving. Stay down bug! Just stay down! * Speaking of bugs, if anyone finds one (or more), PLEASE tell me. Ideally, fix it and tell me...but at least tell me/the list. * If anyone from 4D, etc. ever wants to clean this up and make it into a tech note, please post a link when it's published. I'd use it! * If all you need is to detect that two appointments overlap and don't care by how much, see the notes. It's eaasier to figure than you might expect - I put the relevant comprisons at the top of my big case of scenarios below. * You'll find lots of notes and some great ASCII charts throughout. I give credit to where I found everything. * Tip: If this approach isn't good enough for you and you're after optimal schedule detection (least CPU use), the data structure you want to look for is an "interval tree." Just google scheduling conflicts and interval trees and you'll be eyeballs-deep into big O notation before you can blink. Here's a link to a decent summary: http://www.geeksforgeeks.org/given-n-appointments-find-conflicting-appointments/ I'm not doing anything intensive enough to need interval trees here (I'm not schedule fitting, just counting stuff), but if you have a big scheduling system with lots of conflict detection, check out interval trees. (Not that list processing is easy or pleasurable in 4D, but you can do it.) Okay, here is the method and the test method to match. If (False) // =========================================== utl_DTS_GetIntervalOverlapSecs // DESCRIPTION: Returns overlap of date time stamps, if any. // Result is -1 if you pass bad inputs. // All inputs are date time stamps. // Notes: // There's a always a question of how to treat a case where the // end time of one interval is the start time of the other. In this case, // I've gone with treating it as an overlap when the boundaries touch. // This can be revisited if we need something different. // Great explanation on StackOverflow here: // https://stackoverflow.com/questions/143552/comparing-date-ranges/143568#143568 // Best. Ascii. Diagram. Ever. This blocks out eleven possible interval comparison outcomes. // I've added discussion of two special cases and show what catches them. -- DPA // |-------------------| compare to this one // |---------| contained within // |----------| contained within, equal start // |-----------| contained within, equal end // |-------------------| contained within, equal start+end // |------------| not fully contained, overlaps start // |---------------| not fully contained, overlaps end // |-------------------------| overlaps start, bigger // |-----------------------| overlaps end, bigger // |------------------------------| // on the other hand, let me post all those that don't overlap: // // |-------------------| compare to this one // |---| ends before // |---| starts after // Notes about two possibly confusing cases // |-------------------| compare to this one // |-----| ends at start is a case of // |------------| not fully contained, overlaps start // |-------------------| compare to this one // |-----| starts at end is a case of // |---------------| not fully contained, overlaps end // // The point of the art above is to show the possibilities, and to show a shortcut // to figuring out "do these overlap?" Only 'ends before' and 'starts after' aren't // overlaps. In other words, everything else is an overlap - even if by only 0 seconds. // In this method here, what we're trying to calculate are // the number of seconds of overlap, so all need to be covered explicitly. // The Wikipedia entry on Allen's interval algebra (what we're doing): // https://en.wikipedia.org/wiki/Allen%27s_interval_algebra // Dang, there's an entire book on time-data oriented SQL: // https://www2.cs.arizona.edu/people/rts/tdbbook.pdf // Note: // * You can _definitely_ reduce the number of comparisons in this method by collapsing and shortcutting // some of the comparisons. I was doing that, then I switched to this more explicit code. Your call. // * Not everyone counts the possible combinations the same way. // * You'll need to decide if you want times that overlap exactly to be considered matching or not. // For example, it's normal to say "this appointment runs from 9-10 and the next one from 10-11." // In normal language, Those don't overlap because you treat them as 09:00-09:59:59 and 10:00:00-10:59:59. // This routine treats 10-11 and 11-12 as overlapping but by 0 seconds. There are some notes above about // where these catch in the code, if you want to tweak the behavior. // See test routine utl_DTS_Overlap_Test // CREATED BY: David Adams // DATE: 01/07/2017 // LAST MODIFIED: End if // ============================================ C_LONGINT($0;$overlap_seconds) // Could change to return a descriptor or error. C_TEXT($1;$range_start_dts) C_TEXT($2;$range_end_dts) C_TEXT($3;$check_start_dts) C_TEXT($4;$check_end_dts) $overlap_seconds:=-1 // Result is ambiguous if you pass bad inputs. C_TEXT($error_name) $error_name:=MethodCheck_ParameterCount (Count parameters;4;4) If ($error_name="") $range_start_dts:=$1 $range_end_dts:=$2 $check_start_dts:=$3 $check_end_dts:=$4 Case of : ($range_start_dts>$range_end_dts) // Start after end? Bad input. $error_name:="BadDTS_StartsAfterEnding" : ($check_start_dts>$check_end_dts) // Start after end? Bad input. $error_name:="BadDTS_StartsAfterEnding" End case If ($error_name#"") C_TEXT($diagnostic_text) $diagnostic_text:="" $diagnostic_text:=$diagnostic_text+"$range_start_dts = "+$range_start_dts+Char(Carriage return) $diagnostic_text:=$diagnostic_text+"$range_end_dts = "+$range_end_dts+Char(Carriage return) $diagnostic_text:=$diagnostic_text+"$check_start_dts = "+$check_start_dts+Char(Carriage return) $diagnostic_text:=$diagnostic_text+"$check_end_dts = "+$check_end_dts+Char(Carriage return) ErrorStack_AddOnError ($error_name;Current method name;$diagnostic_text) End if End if If ($error_name="") C_LONGINT($check_length) // We use this a few places below. $check_length:=utl_DT_Difference_Seconds ($check_end_dts;$check_start_dts) Case of : ($check_end_dts<$range_start_dts) // Ends before: NO conflict // |-------------------| compare to this one // |---| ends before $overlap_seconds:=0 : ($check_start_dts>$range_end_dts) // Ends after: NO Conflict // |-------------------| compare to this one // |---| starts after // $overlap_seconds:=0 //--------------------------------------------------------------------------- // All other nine possible cases represent an overlap of some length. //--------------------------------------------------------------------------- : (($check_start_dts>$range_start_dts) & ($check_end_dts<$range_end_dts)) // Contained within // |-------------------| compare to this one // |---------| contained within $overlap_seconds:=$check_length : (($check_start_dts=$range_start_dts) & ($check_end_dts<$range_end_dts)) // contained within, equal start // |-------------------| compare to this one // |----------| contained within, equal start $overlap_seconds:=$check_length : (($check_start_dts>$range_start_dts) & ($check_end_dts=$range_end_dts)) // |-------------------| compare to this one // |-----------| contained within, equal end $overlap_seconds:=$check_length : (($check_start_dts=$range_start_dts) & ($check_end_dts=$range_end_dts)) // |-------------------| compare to this one // |-------------------| contained within, equal start+end $overlap_seconds:=$check_length : (($check_start_dts<$range_start_dts) & ($check_end_dts<$range_end_dts)) // |-------------------| compare to this one // |------------| not fully contained, overlaps start // |-----| ends at start $overlap_seconds:=utl_DT_Difference_Seconds ($check_end_dts;$range_start_dts) : (($check_start_dts>$range_start_dts) & ($check_end_dts>$range_end_dts)) // |-------------------| compare to this one // |---------------| not fully contained, overlaps end $overlap_seconds:=utl_DT_Difference_Seconds ($range_end_dts;$check_start_dts) : (($check_start_dts<$range_start_dts) & ($check_end_dts=$range_end_dts)) // |-------------------| compare to this one // |-------------------------| overlaps start, bigger $overlap_seconds:=$check_length : (($check_start_dts=$range_start_dts) & ($check_end_dts>$range_end_dts)) // |-------------------| compare to this one // |-----------------------| overlaps end, bigger $overlap_seconds:=$check_length : (($check_start_dts<$range_start_dts) & ($check_end_dts>$range_end_dts)) // |-------------------| compare to this one // |------------------------------| overlaps entire period $overlap_seconds:=$check_length Else // Starts during TRACE // If you're reading this note, I screwed up. End case End if $0:=$overlap_seconds And now the test method: If (False) // =========================================== utl_DTS_Overlap_Test // DESCRIPTION: Tests if date times overlap at all. // All inputs are date time stamps. // Checking my work here... // CREATED BY: David Adams // DATE: 01/07/2017 // LAST MODIFIED: End if // ============================================ C_TEXT($dts_9am) C_TEXT($dts_10am) C_TEXT($dts_11am) C_TEXT($dts_12_noon) C_TEXT($dts_1pm) C_TEXT($dts_2pm) C_TEXT($dts_3pm) C_TEXT($dts_4pm) C_TEXT($dts_5pm) $dts_9am:=utl_DT_Get (!2018-01-01!;?09:00:00?;True) $dts_10am:=utl_DT_Get (!2018-01-01!;?10:00:00?;True) $dts_11am:=utl_DT_Get (!2018-01-01!;?11:00:00?;True) $dts_12_noon:=utl_DT_Get (!2018-01-01!;?12:00:00?;True) $dts_1pm:=utl_DT_Get (!2018-01-01!;?13:00:00?;True) $dts_2pm:=utl_DT_Get (!2018-01-01!;?14:00:00?;True) $dts_3pm:=utl_DT_Get (!2018-01-01!;?15:00:00?;True) $dts_4pm:=utl_DT_Get (!2018-01-01!;?16:00:00?;True) $dts_5pm:=utl_DT_Get (!2018-01-01!;?17:00:00?;True) C_TEXT($cr) C_TEXT($tab) C_TEXT($results) $cr:=Char(Carriage return) $tab:=Char(Tab) $results:="" $results:=$results+"Description"+$tab $results:=$results+"Code"+$tab $results:=$results+"Errors Expected"+$tab $results:=$results+"Errors"+$tab $results:=$results+"Seconds Expected"+$tab $results:=$results+"Seconds"+$cr C_LONGINT($overlap_seconds) // |-------------------| compare to this one // |---------| contained within // |----------| contained within, equal start // |-----------| contained within, equal end // |-------------------| contained within, equal start+end // |------------| not fully contained, overlaps start // |---------------| not fully contained, overlaps end // |-------------------------| overlaps start, bigger // |-----------------------| overlaps end, bigger // |------------------------------| overlaps entire period // |---| ends before // |---| starts after // |-----| ends at start (caught by 'not fully contained, overlaps start') // |-----| starts at end (caught by 'not not fully contained, overlaps end') // utl_DTS_GetIntervalOverlapSecs (Range start;Range end;Test start;Test end) : Seconds with -1 for bad input error If (True) // Bad input cases. ErrorStack_ClearStack $results:=$results+"Bad range input"+$tab $overlap_seconds:=utl_DTS_GetIntervalOverlapSecs ($dts_10am;$dts_9am;$dts_12_noon;$dts_1pm) $results:=$results+"utl_DTS_GetIntervalOverlapSecs ($dts_10am;$dts_9am;$dts_12_noon;$dts_1pm)"+$tab $results:=$results+"1"+$tab $results:=$results+String(ErrorStack_Count )+$tab $results:=$results+"-1"+$tab $results:=$results+String($overlap_seconds)+$cr ErrorStack_ClearStack $results:=$results+"Bad check input"+$tab $overlap_seconds:=utl_DTS_GetIntervalOverlapSecs ($dts_9am;$dts_3pm;$dts_1pm;$dts_12_noon) $results:=$results+"utl_DTS_GetIntervalOverlapSecs ($dts_9am;$dts_3pm;$dts_1pm;$dts_12_noon)"+$tab $results:=$results+"1"+$tab $results:=$results+String(ErrorStack_Count )+$tab $results:=$results+"-1"+$tab $results:=$results+String($overlap_seconds)+$cr End if // |-------------------| compare to this one // |---------| contained within ErrorStack_ClearStack $results:=$results+"Contained within"+$tab $overlap_seconds:=utl_DTS_GetIntervalOverlapSecs ($dts_10am;$dts_3pm;$dts_11am;$dts_12_noon) $results:=$results+"utl_DTS_GetIntervalOverlapSecs ($dts_10am;$dts_3pm;$dts_11am;$dts_12_noon)"+$tab $results:=$results+"0"+$tab $results:=$results+String(ErrorStack_Count )+$tab $results:=$results+String(60*60)+$tab $results:=$results+String($overlap_seconds)+$cr // |-------------------| compare to this one // |----------| contained within, equal start ErrorStack_ClearStack $results:=$results+"Contained within, equal start"+$tab $overlap_seconds:=utl_DTS_GetIntervalOverlapSecs ($dts_10am;$dts_3pm;$dts_10am;$dts_11am) $results:=$results+"utl_DTS_GetIntervalOverlapSecs ($dts_10am;$dts_3pm;$dts_11am;$dts_11am)"+$tab $results:=$results+"0"+$tab $results:=$results+String(ErrorStack_Count )+$tab $results:=$results+String(60*60)+$tab $results:=$results+String($overlap_seconds)+$cr // |-------------------| compare to this one // |-----------| contained within, equal end ErrorStack_ClearStack $results:=$results+"Contained within, equal end"+$tab $overlap_seconds:=utl_DTS_GetIntervalOverlapSecs ($dts_10am;$dts_3pm;$dts_2pm;$dts_3pm) $results:=$results+"utl_DTS_GetIntervalOverlapSecs ($dts_10am;$dts_3pm;$dts_2pm;$dts_3pm)"+$tab $results:=$results+"0"+$tab $results:=$results+String(ErrorStack_Count )+$tab $results:=$results+String(60*60)+$tab $results:=$results+String($overlap_seconds)+$cr // |-------------------| compare to this one // |-------------------| contained within, equal start+end ErrorStack_ClearStack $results:=$results+"Contained within, equal start+end"+$tab $overlap_seconds:=utl_DTS_GetIntervalOverlapSecs ($dts_10am;$dts_11am;$dts_10am;$dts_11am) $results:=$results+"utl_DTS_GetIntervalOverlapSecs ($dts_10am;$dts_11am;$dts_10am;$dts_11am)"+$tab $results:=$results+"0"+$tab $results:=$results+String(ErrorStack_Count )+$tab $results:=$results+String(60*60)+$tab $results:=$results+String($overlap_seconds)+$cr // |-------------------| compare to this one // |------------| not fully contained, overlaps start ErrorStack_ClearStack $results:=$results+"Not fully contained, overlaps start"+$tab $overlap_seconds:=utl_DTS_GetIntervalOverlapSecs ($dts_10am;$dts_3pm;$dts_9am;$dts_11am) $results:=$results+"utl_DTS_GetIntervalOverlapSecs ($dts_10am;$dts_3pm;$dts_9am;$dts_11am)"+$tab $results:=$results+"0"+$tab $results:=$results+String(ErrorStack_Count )+$tab $results:=$results+String(60*60)+$tab $results:=$results+String($overlap_seconds)+$cr // |-------------------| compare to this one // |---------------| not fully contained, overlaps end ErrorStack_ClearStack $results:=$results+"Not fully contained, overlaps end"+$tab $overlap_seconds:=utl_DTS_GetIntervalOverlapSecs ($dts_10am;$dts_3pm;$dts_2pm;$dts_4pm) $results:=$results+"utl_DTS_GetIntervalOverlapSecs ($dts_10am;$dts_3pm;$dts_2pm;$dts_4pm)"+$tab $results:=$results+"0"+$tab $results:=$results+String(ErrorStack_Count )+$tab $results:=$results+String(60*60)+$tab $results:=$results+String($overlap_seconds)+$cr // |-------------------| compare to this one // |---| ends before ErrorStack_ClearStack $results:=$results+"Ends before"+$tab $overlap_seconds:=utl_DTS_GetIntervalOverlapSecs ($dts_11am;$dts_3pm;$dts_9am;$dts_10am) $results:=$results+"utl_DTS_GetIntervalOverlapSecs ($dts_11am;$dts_3pm;$dts_9am;$dts_10am)"+$tab $results:=$results+"0"+$tab $results:=$results+String(ErrorStack_Count )+$tab $results:=$results+String(0)+$tab $results:=$results+String($overlap_seconds)+$cr // |-------------------| compare to this one // |---| starts after ErrorStack_ClearStack $results:=$results+"Ends after"+$tab $overlap_seconds:=utl_DTS_GetIntervalOverlapSecs ($dts_10am;$dts_2pm;$dts_3pm;$dts_4pm) $results:=$results+"utl_DTS_GetIntervalOverlapSecs ($dts_10am;$dts_2pm;$dts_3pm;$dts_4pm)"+$tab $results:=$results+"0"+$tab $results:=$results+String(ErrorStack_Count )+$tab $results:=$results+String(0)+$tab $results:=$results+String($overlap_seconds)+$cr // |-------------------| compare to this one // |-----| ends at start ErrorStack_ClearStack $results:=$results+"Ends at start"+$tab $overlap_seconds:=utl_DTS_GetIntervalOverlapSecs ($dts_10am;$dts_2pm;$dts_9am;$dts_10am) $results:=$results+"utl_DTS_GetIntervalOverlapSecs ($dts_10am;$dts_2pm;$dts_9am;$dts_10am)"+$tab $results:=$results+"0"+$tab $results:=$results+String(ErrorStack_Count )+$tab $results:=$results+String(0)+$tab $results:=$results+String($overlap_seconds)+$cr // |-------------------| compare to this one // |-----| starts at end ErrorStack_ClearStack $results:=$results+"Starts at end"+$tab $overlap_seconds:=utl_DTS_GetIntervalOverlapSecs ($dts_10am;$dts_2pm;$dts_2pm;$dts_3pm) $results:=$results+"utl_DTS_GetIntervalOverlapSecs ($dts_10am;$dts_2pm;$dts_2pm;$dts_3pm)"+$tab $results:=$results+"0"+$tab $results:=$results+String(ErrorStack_Count )+$tab $results:=$results+String(0)+$tab $results:=$results+String($overlap_seconds)+$cr SET TEXT TO PASTEBOARD($results)// I usually set a breakpoint before or after this. ********************************************************************** 4D Internet Users Group (4D iNUG) FAQ: http://lists.4d.com/faqnug.html Archive: http://lists.4d.com/archives.html Options: http://lists.4d.com/mailman/options/4d_tech Unsub: mailto:4d_tech-unsubscr...@lists.4d.com **********************************************************************
