DFS based topological sort implementation for TypeScript

topologicalSort.ts

type Id = number

export interface Dependency {
  id: Id
  dependencies: Id[]
}

const PENDING = 1
const WRITTEN = 2

export function sort<T extends Dependency>(dependencies: T[], entries: Id[]): Id[] {
  const dup: Record<Id, 1 | 2> = {}
  const result: Id[] = []

  function traverse(node: Dependency): void {
    if (dup[node.id] === PENDING) throw new Error('circular dependency detected')

    dup[node.id] = PENDING
    for (const dependentId of node.dependencies) {
      if (dup[dependentId] !== WRITTEN) {
        traverse(dependencies[dependentId])
      }
    }
    result.push(node.id)
    dup[node.id] = WRITTEN
  }

  entries.forEach(id => traverse(dependencies[id]))
  return result
}