# [dep-graph](http://github.com/TrevorBurnham/dep-graph)

_ = require 'underscore'

class DepGraph
  constructor: ->
    # The internal representation of the dependency graph in the format
    # `id: [ids]`, indicating only *direct* dependencies.
    @map = {}

  # Add a direct dependency. Returns `false` if that dependency is a duplicate.
  add: (id, depId) ->
    @map[id] ?= []
    return false if depId in @map[id]
    @map[id].push depId
    @map[id]

  # Generate a list of all dependencies (direct and indirect) for the given id,
  # in logical order with no duplicates.
  getChain: (id) ->
    # First, get a list of all dependencies (unordered)
    deps = @descendantsOf id

    # Second, order them (using the Tarjan algorithm)
    chain = []
    visited = {}
    visit = (node) =>
      return if visited[node] or node is id
      visited[node] = true
      visit parent for parent in @parentsOf(node) when parent in deps
      chain.unshift node

    for leafNode in _.intersection(deps, @leafNodes()).reverse()
      visit leafNode

    chain

  leafNodes: ->
    allNodes = _.uniq _.flatten _.values @map
    node for node in allNodes when !@map[node]?.length

  parentsOf: (child) ->
    node for node in _.keys(@map) when child in @map[node]

  descendantsOf: (parent, descendants = [], branch = []) ->
    descendants.push parent
    branch.push parent
    for child in @map[parent] ? []
      if child in branch                # cycle
        throw new Error("Cyclic dependency from #{parent} to #{child}")
      continue if child in descendants  # duplicate
      @descendantsOf child, descendants, branch.slice(0)
    descendants[1..]

# Export the class in Node, make it global in the browser.
if module?.exports?
  module.exports = DepGraph
else
  @DepGraph = DepGraph