depthFirstTraverse function

List<String> depthFirstTraverse(Map<String, List<String>> dependencies, String root)

Implementation

List<String> depthFirstTraverse(
    Map<String, List<String>> dependencies, String root) {
  List<String> result = <String>[];
  List<_Dependency> stack = <_Dependency>[];
  Set<String> set = <String>{};

  stack.add(_Dependency(root));
  set.add(root);

  while (stack.isNotEmpty) {
    final last = stack.last;
    String? key;
    if (last.index < dependencies[last.key]!.length) {
      key = dependencies[last.key]![last.index];
    }
    if (key == null) {
      final removeItem = stack.removeLast();
      set.remove(removeItem.key);
      if (stack.isNotEmpty) {
        stack.last.index++;
      }
    } else {
      if (set.contains(key)) {
        String error = stack.skipWhile((value) => value.key != key).join('->');
        throw Exception('Circular dependency: $error->$key');
      }
      result.add(key);
      set.add(key);
      stack.add(_Dependency(key));
    }
  }

  return result;
}