LeoChen4891
BAN USERpublic class DependenciesTree {
private static final String input = "a->b\nb->c\nb->d\nc->d";
private static final String inputLoop = "a->b\nb->c\nb->d\nc->d\nd->a";
public static void main(String[] args) {
System.out.println(getCompileOrder(input));
System.out.println(getCompileOrder(inputLoop));
}
public static String getCompileOrder(String input) {
Map<String, Node> nodes = new HashMap<String, Node>();
List<Node> ret = new LinkedList<Node>();
BufferedReader reader = new BufferedReader(new StringReader(input));
try {
while (true) {
String line = reader.readLine();
if (null == line)
break;
// System.out.println(line);
String[] strs = line.split("->");
if (strs.length != 2)
throw new Exception("invalid rule:" + line);
String firstStr = strs[0];
String secondStr = strs[1];
Node first = nodes.get(firstStr);
Node second = nodes.get(secondStr);
if (null == second) {
second = new Node(secondStr);
nodes.put(secondStr, second);
}
if (null == first) {
first = new Node(firstStr);
nodes.put(firstStr, first);
}
first.dep.add(second);
}
// for (Node n : nodes.values()) {
// System.out.println(n);
// }
for (int i = 0; i < nodes.size(); i++) {
boolean nochange = true;
for (Node node : nodes.values()) {
// check if all dependencies are processed
if (!node.processed && node.isDepsAllProcessed()) {
node.processed = true;
ret.add(node);
nochange = false;
}
}
boolean allDone = true;
for (Node node : nodes.values()) {
if (!node.processed)
allDone = false;
}
if (allDone) {
break;
}
if (nochange) {
throw new Exception("loop found");
}
}
} catch (Exception e) {
e.printStackTrace();
}
return ret.toString();
}
}
As mentioned above, the 2 steps solution works fine.
1. get the diff array
2. use a hash map to save the first occurrence of a diff number
- LeoChen4891 August 25, 2014