TopologicalSort { public List<N> sort(Collection<N> nodes) { LinkedHashMap<ID, NodeInfo<ID, N>> nodeInfos = newLinkedHashMapWithExpectedSize(nodes.size()); List<NodeInfo<ID, N>> results = new ArrayList<>(nodes.size()); int pos = 0; boolean needsSorting = false; for (N node : nodes) { ID nodeID = identityExtractor.apply(node); Set<ID> preds = new HashSet<>(directPredecessorsExtractor.apply(node)); needsSorting = needsSorting || !preds.isEmpty(); NodeInfo<ID, N> nodeInfo = nodeInfos.computeIfAbsent(nodeID, __ -> new NodeInfo<>()); nodeInfo.id = nodeID; nodeInfo.predecessors = preds; nodeInfo.sourcePosition = pos++; nodeInfo.node = node; for (ID pred : preds) { NodeInfo<ID, N> predNode = nodeInfos.computeIfAbsent(pred, __ -> new NodeInfo<>()); if (predNode.successors == null) { predNode.successors = new HashSet<>(); } predNode.successors.add(nodeID); } } if (needsSorting) { TreeSet<NodeInfo<ID, N>> tmp = new TreeSet<>(Comparator.comparingInt(a -> a.sourcePosition)); tmp.addAll(nodeInfos.values()); nodeInfos.clear(); tmp.forEach(ni -> nodeInfos.put(ni.id, ni)); sort(nodeInfos, results); } else { results = new ArrayList<>(nodeInfos.values()); } return results.stream().map(ni -> ni.node).collect(Collectors.toList()); } TopologicalSort(
      Function<N, ID> identityExtractor, Function<N, Set<ID>> directPredecessorsExtractor); List<N> sort(Collection<N> nodes);  }
@Test(dataProvider = "sortingCases") public void shouldApplySorting(List<Var> list, List<Var> expectedSorting) throws Exception { sort(list); assertEquals(list, expectedSorting); }