scheduler - ryan's task

scheduler.rb

# scheduler.rb

class Scheduler
  
  class CyclicalDependsError < StandardError
  end
  
  attr_accessor :tasks, :queue, :runables
  
  def initialize(tasks, depends = [])
    @tasks=tasks
    @depends=depends
  end
  
  def run  
    validate_dependencies
    @runables = create_tasks
    @queue=[]
    
    enqueue(@runables.shift) while !@runables.empty?  
    @queue
  end
  
  private 
  
  def enqueue(task)
    return unless is_enqueued?(task.name)
    task.depends_on.each{|d| 
      t = @runables.select{|t| t.name.eql?(d)}.first
      enqueue(t) unless t.nil?
    }
    @queue << task
  end
  
  def is_enqueued?(name)
    @queue.select{|t| t.name.eql?(name) }.empty?
  end
  
  def create_tasks
    @tasks.map {|n| 
      depends_on = @depends.map{|k, v| 
        v if k.eql?(n)
      }.compact
      Task.new(n, depends_on) 
    }
  end
  
  def validate_dependencies
    @depends.each{|k,v|
      validate_depends(k,v) unless @depends[v].nil?
    }
  end
  
  def validate_depends(parent_depends, current_depends)
    raise CyclicalDependsError, "The dependency task:#{current_depends}->task:#{parent_depends} results in a cycle of doom" if @depends[current_depends].eql?(parent_depends)
    validate_depends(parent_depends, @depends[current_depends]) unless current_depends.nil?
  end
  
end

scheduler_spec.rb

# scheduler_spec.rb

require 'scheduler'
require 'task'

describe Scheduler do
  context "adding list tasks" do
  
    let (:scheduler) do
      Scheduler.new ['a','b']
    end
    
    it "returns the correct number of tasks" do
      scheduler.run.should have(2).tasks
    end
    
    it "return tasks in the correct order" do
      tasks = scheduler.run
      tasks[0].name.should eq("a")
    end

  end
  
  context "acceptance criteria" do
    
    let(:no_tasks) do
      scheduler = Scheduler.new [], {}
      scheduler.run
    end
    
    let(:two_tasks_no_dependencies) do
      scheduler = Scheduler.new ['a','b'], {}
      scheduler.run
    end
    
    let(:two_tasks) do
      scheduler = Scheduler.new ['a','b'],  {'a' => 'b'}
      scheduler.run
    end
    
    let(:four_tasks) do
      scheduler = Scheduler.new ['a','b','c','d'],  {'a' => 'b', 'c' => 'd'}
      scheduler.run
    end
  
    let(:three_tasks) do
      scheduler = Scheduler.new ['a','b','c'],  {'a' => 'b', 'b' => 'c'}
      scheduler.run
    end
    
    let(:cyclical) do
      Scheduler.new ['a','b','c','d'], {'a' => 'b', 'b' => 'c', 'c' => 'a'}
    end
     
    it "deals with no tasks" do
      no_tasks.collect{|t| t.name}.should eq([]) 
    end
    
    it "retains ordering with no dependencies" do
      two_tasks_no_dependencies.collect{|t| t.name}.should eq(['a','b'])
    end
    
    it "orders two tasks by dependencies" do
      two_tasks.collect{|t| t.name}.should eq(['b','a'])    
    end
    
    it "orders three tasks by dependencies" do
       three_tasks.collect{|t| t.name}.should eq(['c','b','a'])
    end
    
    it "orders four tasks by dependencies" do
       four_tasks.collect{|t| t.name}.should eq(['b','a','d','c'])
    end
    
    it "finds cyclical dependencies" do
      expect{cyclical.run}.to raise_error(Scheduler::CyclicalDependsError)
    end
    
  end

end

task.rb

# task.rb

class Task
  attr_accessor :name, :depends_on
  
  def initialize(name, depends_on)
    @name=name
    @depends_on=depends_on
  end
end