class Depression
  def self.process(items)
    graph = new(items)
    graph.process
    graph.result
  end
  
  attr_reader :items, :result
  
  def initialize(items)
    @items, @result, @changed = items, [], false
  end
  
  def process
    items.each do |item|
      unless item.respond_to?(:name) && item.name
        raise "Items need to have a name."
      end
    end
    
    @data = Hash[*items.map do |item|
      [item.name, Data.new(0, [])]
    end.flatten]
    
    build_dependencies
    
    @data.each do |name, data|
      increment(name) unless data.relations.empty?
      data.relations.each do |rel|
        increment(rel.name) if @data[rel.name].weight <= data.weight
      end
    end
    
    @result = items.sort do |item, other|
      @data[item.name].weight.<=>(@data[other.name].weight)
    end
  end
  
  protected
  
  def increment(name)
    @stack ||= []
    raise "Circular dep: #{@stack.inspect}" if @stack.include?(name)
    
    @stack.push(name)
    
    @data[name].weight += 1
    @data[name].relations.each {|dep| increment(dep.name) }
    
    @stack.delete(name)
  end
  
  def build_dependencies
    items.each do |item|
      data = @data[item.name]
      
      item.relations[:before] ||= []
      if item.relations[:before] == :all
        rels = items.map do |item2|
          next if item.name == item2.name
          Relation.new(item2.name, :greedy_reverse)
        end
        rels.delete(nil)
        data.relations.push(*rels)
      else
        item.relations[:before].each do |name|
          next unless @data[name]
          data.relations << Relation.new(name, :normal_reverse)
        end
      end
      
      item.relations[:after] ||= []
      if item.relations[:after] == :all
        @data.each do |name, data2|
          next if item.name == name
          data2.relations << Relation.new(item.name, :greedy)
        end
      else
        item.relations[:after].each do |name|
          next unless @data[name]
          @data[name].relations << Relation.new(item.name, :normal)
        end
      end
    end
  end
  
  class Data < Struct.new(:weight, :relations); end
  
  class Relation < Struct.new(:name, :type); end
end
