Skip to content

Instantly share code, notes, and snippets.

@jimweirich jimweirich/allocation.rb
Last active Jan 3, 2016

Embed
What would you like to do?
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 = 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
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
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
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
@coreyhaines

This comment has been minimized.

Copy link

commented Jan 14, 2014

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.

@jimweirich

This comment has been minimized.

Copy link
Owner Author

commented Jan 14, 2014

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?

@jimweirich

This comment has been minimized.

Copy link
Owner Author

commented Jan 15, 2014

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.

@adamlogic

This comment has been minimized.

Copy link

commented Jan 17, 2014

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.