A solution to Martin Rue's Ordered Jobs Kata

ordered_jobs_spec.rb

class Job
  attr_reader :dependency, :name

  def initialize(spec)
    @name, @dependency = spec.split('=>').map(&:strip)

    if @name == @dependency
      raise ArgumentError
    end
  end
end

class OrderedJobs
  def self.parse(structure)
    jobs = structure.split("\n").map {|i| Job.new(i)}

    if self.cyclic_dependency?(jobs)
      raise ArgumentError
    end

    self.print( self.order(jobs) )
  end

  private
    def self.order(jobs)
      ordered_jobs = []

      jobs.each do |job|
        if job.dependency && ordered_jobs.index(job.dependency).nil?
          ordered_jobs << Job.new(job.dependency)
        end

        ordered_jobs << job
      end

      ordered_jobs
    end

    def self.print(jobs)
      jobs.map(&:name)
    end

    def self.cyclic_dependency?(jobs)
      jobs.each do |job|
        tree = []

        while (dependency_name = job.dependency)
          dependency = jobs.select {|j| j.name == dependency_name}.first

          if tree.include? dependency
            return true
          end

          tree << dependency
          job = dependency
        end
      end

      return false
    end
end

require 'rspec'

describe OrderedJobs do
  context 'passing an empty string' do
    it 'should return an empty sequence' do
      OrderedJobs.parse('').should be_empty
    end
  end

  context 'passing a single job' do
    it 'should return the job' do
      OrderedJobs.parse('a =>').should == ['a']
    end
  end

  context 'passing multiple jobs' do
    context 'without dependencies' do
      it 'should return jobs in the correct order' do
        OrderedJobs.parse("a =>
                           b =>
                           c =>").should == %w{a b c}
      end
    end

    context 'with a dependency' do
      it 'should return jobs in the correct order' do
        OrderedJobs.parse("a =>
                           b => c
                           c =>").join.should =~ /c.*b/
      end
    end

    context 'with multiple dependencies' do
      let (:output) do
        OrderedJobs.parse("a =>
                           b => c
                           c => f
                           d => a
                           e => b
                           f =>")
      end

      it 'should return f before c' do
        output.join.should =~ /f.*c/
      end

      it 'should return c before b' do
        output.join.should =~ /c.*b/
      end

      it 'should return b before e' do
        output.join.should =~ /b.*e/
      end

      it 'should return a before d' do
        output.join.should =~ /a.*d/
      end
    end

    context 'with a circular dependency' do
      it 'should raise an error' do
        expect do
          OrderedJobs.parse("a =>
                             b => c
                             c => f
                             d => a
                             e =>
                             f => b")
        end.to raise_error(ArgumentError)
      end
    end
  end
end

describe Job do
  context 'when creating a job' do
    context 'with no dependency' do
      it 'should have a name' do
        Job.new('a =>').name.should == 'a'
      end
    end

    context 'with a dependency' do
      it 'should return dependents name' do
        Job.new('b => c').dependency.should == 'c'
      end

      it 'should not allow self-referential jobs' do
        expect { Job.new('c => c') }.to raise_error(ArgumentError)
      end
    end
  end
end