Merge intersecting ranges

range-set.rb

require "minitest/autorun"

class RangeSet
  include Enumerable

  def initialize(ranges = [])
    @ranges = merge(ranges)
  end

  def <<(range)
    @ranges.push(range)
    @ranges = merge(@ranges)
  end

  def each(&block)
    @ranges.each(&block)
  end

  def empty?
    @ranges.empty?
  end

  private

  def merge(ranges)
    return [] if ranges.empty?
    ranges.sort_by!(&:min)
    stack = [ranges.shift]
    ranges.each do |range|
      peek = stack.last
      if peek.cover?(range.min)
        stack.pop
        max = peek.max > range.max ? peek.max : range.max
        stack.push(peek.min..max)
      else
        stack.push(range)
      end
    end
    stack
  end
end

describe "RangeSet" do
  it "is empty" do
    assert_empty RangeSet.new
  end

  it "merges intersecting ranges" do
    set = RangeSet.new([0..10, 20..25, 23..24, 24..30].shuffle)
    assert_equal [0..10, 20..30], set.to_a
  end

  it "merges an intersecting range" do
    set = RangeSet.new([0..10, 20..25, 24..30])
    set << (25..35)
    assert_equal [0..10, 20..35], set.to_a
  end

  it "inserts a disjoint range" do
    set = RangeSet.new([0..10, 20..25])
    set << (12..15)
    assert_equal [0..10, 12..15, 20..25], set.to_a
  end
end