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

I definitely like having the allocation object to put some of things on.

I'm torn on unrolling the recursion into an loop over a mutable list. I've tended to have problems coming back to those to make changes.

Are you referring to the .shift used for walking through the sorted allocations? I'm not too worried about it because the main entry point (merge_duplicates) makes a sorted copy, so only the local copy is modified, not the original. Perhaps this is a point where marking the secondary method (merge_sorted_duplicates) private would emphasize that it is not to be used externally (cf. our conversation about public/private at CodeMash).

Here's a version that doesn't modify the sorted allocations array:

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

Although it's flog score is actually less than the original version, the extra if check in the midst of the loop makes the algorithm less clear (IMHO).

Thoughts?

Found a better version of the non-destructive iterative version that I'm kinda liking. I've updated the Gist to reflect the new iterative version.

@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. :-)