/**
   * Sort the array of entry points so that the dependant entry points always come later than
   * their dependencies in the array.
   * @param entryPoints An array entry points to sort.
   * @returns the result of sorting the entry points.
   */
  sortEntryPointsByDependency(entryPoints: EntryPoint[]): SortedEntryPointsInfo {
    const invalidEntryPoints: InvalidEntryPoint[] = [];
    const ignoredDependencies: IgnoredDependency[] = [];
    const graph = new DepGraph<EntryPoint>();

    // Add the entry ponts to the graph as nodes
    entryPoints.forEach(entryPoint => graph.addNode(entryPoint.path, entryPoint));

    // Now add the dependencies between them
    entryPoints.forEach(entryPoint => {
      const entryPointPath = entryPoint.fesm2015 || entryPoint.esm2015;
      if (!entryPointPath) {
        throw new Error(
            `ESM2015 format (flat and non-flat) missing in '${entryPoint.path}' entry-point.`);
      }

      const dependencies = new Set<string>();
      const missing = new Set<string>();
      this.host.computeDependencies(entryPointPath, dependencies, missing);

      if (missing.size > 0) {
        // This entry point has dependencies that are missing
        // so remove it from the graph.
        removeNodes(entryPoint, Array.from(missing));
      } else {
        dependencies.forEach(dependencyPath => {
          if (graph.hasNode(dependencyPath)) {
            // The dependency path maps to an entry point that exists in the graph
            // so add the dependency.
            graph.addDependency(entryPoint.path, dependencyPath);
          } else if (invalidEntryPoints.some(i => i.entryPoint.path === dependencyPath)) {
            // The dependency path maps to an entry-point that was previously removed
            // from the graph, so remove this entry-point as well.
            removeNodes(entryPoint, [dependencyPath]);
          } else {
            // The dependency path points to a package that ngcc does not care about.
            ignoredDependencies.push({entryPoint, dependencyPath});
          }
        });
      }
    });

    // The map now only holds entry-points that ngcc cares about and whose dependencies
    // (direct and transitive) all exist.
    return {
      entryPoints: graph.overallOrder().map(path => graph.getNodeData(path)),
      invalidEntryPoints,
      ignoredDependencies
    };

    function removeNodes(entryPoint: EntryPoint, missingDependencies: string[]) {
      const nodesToRemove = [entryPoint.path, ...graph.dependantsOf(entryPoint.path)];
      nodesToRemove.forEach(node => {
        invalidEntryPoints.push({entryPoint: graph.getNodeData(node), missingDependencies});
        graph.removeNode(node);
      });
    }
  }

  /**
   * Computes a dependency graph of the given entry-points.
   *
   * The graph only holds entry-points that ngcc cares about and whose dependencies
   * (direct and transitive) all exist.
   */
  private computeDependencyGraph(entryPoints: EntryPoint[]): DependencyGraph {
    const invalidEntryPoints: InvalidEntryPoint[] = [];
    const ignoredDependencies: IgnoredDependency[] = [];
    const graph = new DepGraph<EntryPoint>();

    const angularEntryPoints = entryPoints.filter(entryPoint => entryPoint.compiledByAngular);

    // Add the Angular compiled entry points to the graph as nodes
    angularEntryPoints.forEach(entryPoint => graph.addNode(entryPoint.path, entryPoint));

    // Now add the dependencies between them
    angularEntryPoints.forEach(entryPoint => {
      const entryPointPath = getEntryPointPath(entryPoint);
      const {dependencies, missing, deepImports} = this.host.findDependencies(entryPointPath);

      if (missing.size > 0) {
        // This entry point has dependencies that are missing
        // so remove it from the graph.
        removeNodes(entryPoint, Array.from(missing));
      } else {
        dependencies.forEach(dependencyPath => {
          if (graph.hasNode(dependencyPath)) {
            // The dependency path maps to an entry point that exists in the graph
            // so add the dependency.
            graph.addDependency(entryPoint.path, dependencyPath);
          } else if (invalidEntryPoints.some(i => i.entryPoint.path === dependencyPath)) {
            // The dependency path maps to an entry-point that was previously removed
            // from the graph, so remove this entry-point as well.
            removeNodes(entryPoint, [dependencyPath]);
          } else {
            // The dependency path points to a package that ngcc does not care about.
            ignoredDependencies.push({entryPoint, dependencyPath});
          }
        });
      }

      if (deepImports.size) {
        const imports = Array.from(deepImports).map(i => `'${i}'`).join(', ');
        this.logger.warn(
            `Entry point '${entryPoint.name}' contains deep imports into ${imports}. ` +
            `This is probably not a problem, but may cause the compilation of entry points to be out of order.`);
      }
    });

    return {invalidEntryPoints, ignoredDependencies, graph};

    function removeNodes(entryPoint: EntryPoint, missingDependencies: string[]) {
      const nodesToRemove = [entryPoint.path, ...graph.dependantsOf(entryPoint.path)];
      nodesToRemove.forEach(node => {
        invalidEntryPoints.push({entryPoint: graph.getNodeData(node), missingDependencies});
        graph.removeNode(node);
      });
    }
  }

export function sortByDependency(items: Object | any[], afterProp?: string, beforeProp?: string, nameProp: string = 'name') {

  let map = {};
  let depGraph = new DepGraph();

  let addDependencies = function(item, dependencyProp, addBefore: boolean = false) {
    if ( dependencyProp && item[dependencyProp]) {
      if ( !Array.isArray(item[dependencyProp]) ) {
        throw new Error('Error in item "' + item[nameProp] + '" - ' + dependencyProp + ' must be an array');
      }
      item[dependencyProp].forEach(function(dependency) {
        if ( !map[dependency] ) {
          throw new Error('Missing dependency: "' + dependency + '"  on "' + item[nameProp] + '"');
        }
        if ( addBefore ) {
          depGraph.addDependency(dependency, item[nameProp]);
        } else {
          depGraph.addDependency(item[nameProp], dependency);
        }
      });
    }
  };

  _.forEach(items, function(item, index) {
    if ( !item[nameProp] ) {
      throw new Error('Missing ' + nameProp + ' property on item #' + (index + 1));
    }
    map[item[nameProp]] = item;
    depGraph.addNode(item[nameProp]);
  });


  _.forEach(items, function(item) {
    addDependencies(item, afterProp);
    addDependencies(item, beforeProp, true);
  });

  return depGraph.overallOrder().map(function(itemName) {
    return map[itemName];
  });
};

 dependencies.forEach(dependencyPath => {
   if (graph.hasNode(dependencyPath)) {
     // The dependency path maps to an entry point that exists in the graph
     // so add the dependency.
     graph.addDependency(entryPoint.path, dependencyPath);
   } else if (invalidEntryPoints.some(i => i.entryPoint.path === dependencyPath)) {
     // The dependency path maps to an entry-point that was previously removed
     // from the graph, so remove this entry-point as well.
     removeNodes(entryPoint, [dependencyPath]);
   } else {
     // The dependency path points to a package that ngcc does not care about.
     ignoredDependencies.push({entryPoint, dependencyPath});
   }
 });

 function removeNodes(entryPoint: EntryPoint, missingDependencies: string[]) {
   const nodesToRemove = [entryPoint.path, ...graph.dependantsOf(entryPoint.path)];
   nodesToRemove.forEach(node => {
     invalidEntryPoints.push({entryPoint: graph.getNodeData(node), missingDependencies});
     graph.removeNode(node);
   });
 }

 nodesToRemove.forEach(node => {
   invalidEntryPoints.push({entryPoint: graph.getNodeData(node), missingDependencies});
   graph.removeNode(node);
 });