This is a refactoring of the Allocation Elimination code. The original code (by Mike Doel and Adam McRae) was originally refactored by a large group at the Neo pairing booth at CodeMash. I then took the final version there and continued to refactor over the course of an evening and this is the result of that. I hope to blog about the refactoring…

allocation.rb

Allocation = Struct.new(:project, :person, :start, :finish) do
  include Comparable

  def mergable_with?(other)
    if start > other.start
      other.mergable_with?(self)
    else
      same_assignment?(other) &&
        finish >= other.start - 1
    end
  end

  def same_assignment?(other)
    person == other.person && project == other.project
  end

  def merge(other)
    fail unless mergable_with?(other)
    Allocation.new(
      project, person,
      [start,  other.start ].min,
      [finish, other.finish].max)
  end

  def <=>(other)
    (person <=> other.person).nonzero? ||
      (project <=> other.project).nonzero? ||
      (start <=> other.start)
  end

  def inspect
    "<#{project}/#{person} #{start}..#{finish}>"
  end
end

allocation_eliminator.rb

module AllocationEliminator
  module_function

  def merge_duplicates(allocations)
    return [] if allocations.empty?
    merge_sorted_duplicates(allocations.sort)
  end

  def merge_sorted_duplicates(sorted_allocations)
    result = []
    candidate = sorted_allocations.first
    sorted_allocations.drop(1).each do |next_allocation|
      if candidate.mergable_with?(next_allocation)
        candidate = candidate.merge(next_allocation)
      else
        result << candidate
        candidate = next_allocation
      end
    end
    result << candidate
    result
  end

end

allocation_eliminator_spec.rb

require 'rspec-given'
require 'allocation_eliminator'

describe AllocationEliminator do

  Given(:base_date) { Date.parse("2013-01-01") }

  def day(n)
    base_date + n - 1
  end

  When(:result) { AllocationEliminator.merge_duplicates(raw_allocations) }

  context "handles empty allocations" do
    Given(:raw_allocations) { [ ] }
    Then { result == [] }
  end

  context "handles a single allocation" do
    Given(:raw_allocations) {
      [
        Allocation.new('proj', 'Bob', day(1), day(30))
      ]
    }
    Then {
      result == [
        Allocation.new('proj', 'Bob', day(1), day(30))
      ]
    }
  end

  context "eliminates overlaps in range" do
    Given(:raw_allocations) {
      [
        Allocation.new('proj1', 'Bob', day(1),  day(20)),
        Allocation.new('proj1', 'Bob', day(11), day(30)),
      ]
    }
    Then { result == [Allocation.new('proj1', 'Bob', day(1), day(30))] }
  end

  context "does not eliminate disjoints in range" do
    Given(:raw_allocations) {
      [
        Allocation.new('proj1', 'Bob', day(1), day(20)),
        Allocation.new('proj1', 'Bob', day(28), day(30)),
      ]
    }
    Then { result == raw_allocations.sort }
  end

  context "multiple people with one overlap" do
    Given(:raw_allocations) {
      [
        Allocation.new('proj1', 'Bob', day(1), day(20)),
        Allocation.new('proj1', 'Bob', day(11), day(30)),
        Allocation.new('proj1', 'Ada', day(11), day(30)),
      ]
    }
    Then {
      result == [
        Allocation.new('proj1','Bob', day(1), day(30)),
        Allocation.new('proj1','Ada', day(11), day(30)),
      ].sort
    }
  end

  context "multiple projects with one overlap" do
    Given(:raw_allocations) {
      [
        Allocation.new('proj1', 'Bob', day(1), day(20)),
        Allocation.new('proj1', 'Bob', day(11), day(30)),
        Allocation.new('proj2', 'Bob', day(11), day(30)),
      ].sort
    }
    Then {
      result == [
        Allocation.new('proj1', 'Bob', day(1), day(30)),
        Allocation.new('proj2', 'Bob', day(11), day(30))
      ].sort
    }
  end

  context "one range completely within another" do
    Given(:raw_allocations) {
      [
        Allocation.new('proj1', 'Bob', day(1), day(20)),
        Allocation.new('proj1', 'Bob', day(11), day(15)),
      ]
    }
    Then { result == [
        Allocation.new('proj1', 'Bob', day(1), day(20))
      ].sort
    }
  end

  context "more than two ranges overlapping" do
    Given(:raw_allocations) {
      [
        Allocation.new('proj1', 'Bob', day(1), day(10)),
        Allocation.new('proj1', 'Bob', day(8), day(15)),
        Allocation.new('proj1', 'Bob', day(11), day(20))
      ]
    }
    Then { result == [
        Allocation.new('proj1', 'Bob', day(1), day(20))
      ]
    }
  end

  context "more than two ranges overlapping moar" do
    Given(:raw_allocations) { [
        Allocation.new('proj1', 'Bob', day(1), day(10)),
        Allocation.new('proj1', 'Bob', day(11), day(15)),
        Allocation.new('proj1', 'Bob', day(8), day(20)),
      ]
    }
    Then { result == [
        Allocation.new('proj1', 'Bob', day(1), day(20))
      ]
    }
  end
end

allocation_spec.rb

require 'allocation'

describe Allocation do
  Given(:mon) { Date.parse("2014-01-13") }
  Given(:tue) { mon + 1 }
  Given(:wed) { mon + 2 }
  Given(:thu) { mon + 3 }
  Given(:fri) { mon + 4 }
  Given(:sat) { mon + 5 }

  describe "merging" do
    Given(:first_start)  { mon }
    Given(:first_finish) { fri }
    Given(:second_person) { "Bob" }
    Given(:second_project) { "Proj" }
    Given(:first)  { Allocation.new("Proj", "Bob", first_start,  first_finish)  }
    Given(:second) { Allocation.new(second_project, second_person, second_start, second_finish) }

    When(:result) { first.merge(second) }

    context "when ummergable" do
      Invariant { ! first.mergable_with?(second) }
      Invariant { result.should have_failed }

      context "when disjoint" do
        Given(:second_start) { first_finish + 2 }
        Given(:second_finish) { first_finish + 4 }
        Then { }
      end

      context "when disjoint in reverse" do
        Given(:second_start) { first_start - 4 }
        Given(:second_finish) { first_start - 2 }
        Then { }
      end

      context "when different people" do
        Given(:second_start) { first_start }
        Given(:second_finish) { first_finish }
        Given(:second_person) { "Ada" }
        Then { }
      end

      context "when different project" do
        Given(:second_start) { first_start }
        Given(:second_finish) { first_finish }
        Given(:second_project) { "bench" }
        Then { }
      end
    end

    context "when merge-able" do
      Invariant { result.start  == [first_start, second_start].min }
      Invariant { result.finish == [first_finish, second_finish].max }
      Invariant { first.mergable_with?(second) }

      context "when overlapping" do
        Given(:second_start)  { first_finish - 2 }
        Given(:second_finish) { first_finish + 2 }
        Then { result == Allocation.new("Proj", "Bob", first_start, second_finish) }
      end

      context "when overlapping in reverse" do
        Given(:second_start)  { first_start - 2 }
        Given(:second_finish) { first_start + 2 }
        Then { result == Allocation.new("Proj", "Bob", second_start, first_finish) }
      end

      context "when adjacent" do
        Given(:second_start)  { first_finish + 1 }
        Given(:second_finish) { first_finish + 3 }
        Then { result == Allocation.new("Proj", "Bob", first_start, second_finish) }
      end

      context "when adjacent in reverse" do
        Given(:second_start)  { first_start - 3 }
        Given(:second_finish) { first_start - 1 }
        Then { result == Allocation.new("Proj", "Bob", second_start, first_finish) }
      end

      context "when first contains second" do
        Given(:second_start)  { first_start  + 2 }
        Given(:second_finish) { first_finish - 2 }
        Then { result == Allocation.new("Proj", "Bob", first_start, first_finish) }
      end

      context "when second contains first" do
        Given(:second_start)  { first_start  - 2 }
        Given(:second_finish) { first_finish + 2 }
        Then { result == Allocation.new("Proj", "Bob", second_start, second_finish) }
      end
    end
  end
end

@jimweirich Very nice! I especially like the simplicity of Allocation#merge. I do hope you blog about this. It was a fun way to end CodeMash, and I loved how into it @coreyhaines and @aeden got. :-)