class Bundler::Molinillo::DependencyGraph

def self.tsort(vertices)
  TSort.tsort(
    lambda { |b| vertices.each(&b) },
    lambda { |v, &b| (v.successors & vertices).each(&b) }
  )
end

def ==(other)
  root_vertices == other.root_vertices
end

def add_child_vertex(name, payload, parent_names, requirement)
  is_root = parent_names.include?(nil)
  parent_nodes = parent_names.compact.map { |n| vertex_named(n) }
  vertex = vertex_named(name) || if is_root
                                   add_root_vertex(name, payload)
                                 else
                                   add_vertex(name, payload)
                                 end
  vertex.payload ||= payload
  parent_nodes.each do |parent_node|
    add_edge(parent_node, vertex, requirement)
  end
  vertex
end

def add_edge(origin, destination, requirement)
  if origin == destination || destination.path_to?(origin)
    raise CircularDependencyError.new([origin, destination])
  end
  Edge.new(origin, destination, [requirement]).tap { |e| edges << e }
end

def add_root_vertex(name, payload)
  add_vertex(name, payload).tap { |v| root_vertices[name] = v }
end

def add_vertex(name, payload)
  vertex = vertices[name] ||= Vertex.new(self, name, payload)
  vertex.tap { |v| v.payload = payload }
end

def detach_vertex_named(name)
  vertex = vertex_named(name)
  return unless vertex
  successors = vertex.successors
  vertices.delete(name)
  edges.reject! { |e| e.origin == vertex || e.destination == vertex }
  successors.each { |v| detach_vertex_named(v.name) unless root_vertices[v.name] || v.predecessors.any? }
end

def each
  vertices.values.each { |v| yield v }
end

def initialize
  @vertices = {}
  @edges = Set.new
  @root_vertices = {}
end

def initialize_copy(other)
  super
  @vertices = other.vertices.reduce({}) do |vertices, (name, vertex)|
    vertices.tap do |hash|
      hash[name] = vertex.dup.tap { |v| v.graph = self }
    end
  end
  @root_vertices = Hash[@vertices.select { |n, _v| other.root_vertices[n] }]
  @edges = other.edges.map do |edge|
    Edge.new(
      vertex_named(edge.origin.name),
      vertex_named(edge.destination.name),
      edge.requirements.dup
    )
  end
end

def inspect
  "#{self.class}:#{vertices.values.inspect}"
end

def root_vertex_named(name)
  root_vertices[name]
end

def tsort_each_child(vertex, &block)
  vertex.successors.each(&block)
end

def vertex_named(name)
  vertices[name]
end