An Effective Way to Find Period Differences and Many Ranges in Ruby

Question

I have a number of time ranges in Ruby:

period = Time.parse('8:00am')..Time.parse('8:00pm') incidents = [ Time.parse('7:00am')..Time.parse('9:00am'), Time.parse('1:00pm')..Time.parse('3:00pm'), Time.parse('1:30pm')..Time.parse('3:30pm'), Time.parse('7:00pm')..Time.parse('9:00pm'), ] 

I am trying to get an array of incident-free blocks over this period. For the above, it will be:

 [ Time.parse('9:00am')..Time.parse('1:00pm') Time.parse('3:30pm')..Time.parse('7:00pm') ] 

From the foregoing, it is possible that incidents may intersect or go beyond the period. Are there any range operations or something similar that will simplify this kind of calculation?

Answer 1

Let full_range be a range, and ranges an array of ranges representing what period and incidents asked. I suggested that the elements contained in all ranges can be any objects, provided that they can be compared with the applicable class' method <=> and that the Comparable module was include d.

the code

 def uncovered_ranges(full_range, ranges) ucrs = [full_range] ranges.each do |r| ucrs = ucrs.flat_map do |ucr| if ucr.first >= r.last || ucr.last <= r.first ucr elsif r.first <= ucr.first && r.last >= ucr.last nil elsif r.first <= ucr.first && r.last < ucr.last r.last..ucr.last elsif r.first > ucr.first && r.last >= ucr.last ucr.first..r.first else [ucr.first..r.first, r.last..ucr.last] end end.compact end ucrs end 

<strong> Examples

 full_range = 1..20 ranges = [3..4, 6..8, 10..12, 8..14, 16..17, 20..20] uncovered_ranges(full_range, ranges) #=> [1..3, 4..6, 14..16, 17..20] require 'time' full_range = Time.parse('8:00am')..Time.parse('8:00pm') #=> 2016-12-22 08:00:00 -0800..2016-12-22 20:00:00 -0800 ranges = [ Time.parse('7:00am')..Time.parse('9:00am'), Time.parse('1:00pm')..Time.parse('3:00pm'), Time.parse('1:30pm')..Time.parse('3:30pm'), Time.parse('7:00pm')..Time.parse('9:00pm'), ] #=> [2016-12-22 07:00:00 -0800..2016-12-22 09:00:00 -0800, # 2016-12-22 13:00:00 -0800..2016-12-22 15:00:00 -0800, # 2016-12-22 13:30:00 -0800..2016-12-22 15:30:00 -0800, # 2016-12-22 19:00:00 -0800..2016-12-22 21:00:00 -0800] uncovered_ranges(full_range, ranges) #=> [2016-12-22 09:00:00 -0800..2016-12-22 13:00:00 -0800, # 2016-12-22 15:30:00 -0800..2016-12-22 19:00:00 -0800] 

Explanation

Perhaps the easiest and most capable way to explain what is happening is to insert some puts statements and run the code for the first example above.

 def uncovered_ranges(full_range, ranges) ucrs = [full_range] puts "ucrs initially=#{ucrs}" ranges.each do |r| puts "\ncovering range r=#{r}" ucrs = ucrs.flat_map do |ucr| puts " range uncovered so far ucr=#{ucr}" if ucr.first >= r.last || ucr.last <= r.first puts " in if #1, returning #{ucr}" ucr elsif r.first <= ucr.first && r.last >= ucr.last puts " in if #2, returning nil" nil elsif r.first <= ucr.first && r.last < ucr.last puts " in if #3, returning #{r.last..ucr.last}" r.last..ucr.last elsif r.first > ucr.first && r.last >= ucr.last puts " in if #4, returning #{ucr.first..r.first}" ucr.first..r.first else puts " in else, returning #{[ucr.first..r.first, r.last..ucr.last]}" [ucr.first..r.first, r.last..ucr.last] end end.tap { |u| puts "ucrs after processing range #{r}=#{u}" }. compact. tap { |u| puts "ucrs after compact=#{u}" } end ucrs end uncovered_ranges 1..20, [3..4, 6..8, 10..12, 8..14, 16..17, 20..20] 

prints the following.

 ucrs initially=[1..20] 

 covering range r=3..4 range uncovered so far ucr=1..20 in else, returning [1..3, 4..20] ucrs after processing range 3..4=[1..3, 4..20] ucrs after compact=[1..3, 4..20] 

 covering range r=6..8 range uncovered so far ucr=1..3 in if #1, returning 1..3 range uncovered so far ucr=4..20 in else, returning [4..6, 8..20] ucrs after processing range 6..8=[1..3, 4..6, 8..20] ucrs after compact=[1..3, 4..6, 8..20] 

 covering range r=10..12 range uncovered so far ucr=1..3 in if #1, returning 1..3 range uncovered so far ucr=4..6 in if #1, returning 4..6 range uncovered so far ucr=8..20 in else, returning [8..10, 12..20] ucrs after processing range 10..12=[1..3, 4..6, 8..10, 12..20] ucrs after compact=[1..3, 4..6, 8..10, 12..20] 

 covering range r=8..14 range uncovered so far ucr=1..3 in if #1, returning 1..3 range uncovered so far ucr=4..6 in if #1, returning 4..6 range uncovered so far ucr=8..10 in if #2, returning nil range uncovered so far ucr=12..20 in if #3, returning 14..20 ucrs after processing range 8..14=[1..3, 4..6, nil, 14..20] ucrs after compact=[1..3, 4..6, 14..20] 

 covering range r=16..17 range uncovered so far ucr=1..3 in if #1, returning 1..3 range uncovered so far ucr=4..6 in if #1, returning 4..6 range uncovered so far ucr=14..20 in else, returning [14..16, 17..20] ucrs after processing range 16..17=[1..3, 4..6, 14..16, 17..20] ucrs after compact=[1..3, 4..6, 14..16, 17..20] 

 covering range r=20..20 range uncovered so far ucr=1..3 in if #1, returning 1..3 range uncovered so far ucr=4..6 in if #1, returning 4..6 range uncovered so far ucr=14..16 in if #1, returning 14..16 range uncovered so far ucr=17..20 in if #1, returning 17..20 ucrs after processing range 20..20=[1..3, 4..6, 14..16, 17..20] ucrs after compact=[1..3, 4..6, 14..16, 17..20] #=> [1..3, 4..6, 14..16, 17..20] 

Answer 2

Possible Solution

Using this range of the gem operator , this script will (almost) return what you want.

It starts with period and subtracts each incident one by one.

Since subtracting a range from another can lead to two ranges, the script starts with [period] and saves an array of free incident intervals between iterations:

 require 'range_operators' incident_free = incidents.inject([period]) do |free_ranges, incident| free_ranges.flat_map do |free_range| free_range - incident end end p incident_free #=> [2016-12-22 09:00:01 +0100..2016-12-22 12:59:59 +0100, 2016-12-22 15:30:01 +0100..2016-12-22 18:59:59 +0100] 

Notes

He complains that Time#succ out of date. You can add

 class Time def succ self+1 end end 

to remove obsolescence warnings or use the gemfile with:

 gem 'range_operators', :git => 'https://github.com/monocle/range_operators.git' 

to install a newer version of the gem with a fix for Time .

The script works with a resolution of 1 second, and the first range starts at 09:00:01 , because the incident occurred before 09:00:00 .