Created
June 20, 2013 18:38
-
-
Save modocache/5825385 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
require "dependencies/version" | |
require 'set' | |
module Dependencies | |
class Dependencies | |
def initialize | |
@graph = Hash.new([]) | |
end | |
def add_direct(dependent, dependencies) | |
@graph[dependent] += dependencies | |
end | |
def dependencies_for(dependent) | |
resolve(Set.new([dependent]), | |
Set.new(@graph[dependent])).to_a.sort | |
end | |
private | |
def resolve(resolved_set, to_be_resolved_set) | |
result_set = to_be_resolved_set.dup | |
to_be_resolved_set.each do |dependency| | |
next if resolved_set.include? dependency | |
result_set.merge(@graph[dependency]) | |
resolved_set.add(dependency) | |
result_set = resolve(resolved_set, result_set) | |
end | |
result_set | |
end | |
end | |
end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
require 'spec_helper' | |
require 'dependencies' | |
describe Dependencies::Dependencies do | |
describe 'add_direct' do | |
it 'sets dependencies' do | |
subject.add_direct('A', %w{ B C } ) | |
subject.dependencies_for('A').should == %w{ B C } | |
end | |
it 'adds to existing dependencies' do | |
subject.add_direct('A', %w{ B } ) | |
subject.add_direct('A', %w{ C } ) | |
subject.dependencies_for('A').should == %w{ B C } | |
end | |
end | |
describe 'dependencies_for' do | |
it 'returns a list of dependencies' do | |
subject.add_direct('B', %w{ C E } ) | |
subject.dependencies_for('B').should == %w{ C E } | |
end | |
it 'returns a list of transitive dependencies' do | |
subject.add_direct('A', %w{ B C } ) | |
subject.add_direct('B', %w{ C E } ) | |
subject.dependencies_for('A').should == %w{ B C E } | |
end | |
it 'returns an exhaustive list of transitive dependencies' do | |
subject.add_direct('A', %w{ B C } ) | |
subject.add_direct('B', %w{ C E } ) | |
subject.add_direct('E', %w{ G } ) | |
subject.dependencies_for('A').should == %w{ B C E G } | |
end | |
it 'returns a list of circular dependencies' do | |
subject.add_direct('A', %w{ B } ) | |
subject.add_direct('B', %w{ C } ) | |
subject.add_direct('C', %w{ A } ) | |
subject.dependencies_for('A').should == %w{ A B C } | |
subject.dependencies_for('B').should == %w{ A B C } | |
subject.dependencies_for('C').should == %w{ A B C } | |
end | |
end | |
describe 'integration' do | |
it 'works like http://codekata.pragprog.com/2007/01/kata_eighteen_t.html' do | |
subject.add_direct('A', %w{ B C } ) | |
subject.add_direct('B', %w{ C E } ) | |
subject.add_direct('C', %w{ G } ) | |
subject.add_direct('D', %w{ A F } ) | |
subject.add_direct('E', %w{ F } ) | |
subject.add_direct('F', %w{ H } ) | |
subject.dependencies_for('A').should == %w{ B C E F G H } | |
subject.dependencies_for('B').should == %w{ C E F G H } | |
subject.dependencies_for('C').should == %w{ G } | |
subject.dependencies_for('D').should == %w{ A B C E F G H } | |
subject.dependencies_for('E').should == %w{ F H } | |
subject.dependencies_for('F').should == %w{ H } | |
end | |
end | |
end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment