User:Margusmartsepp/Contributions/Java/Utils.java: Difference between revisions

Content added Content deleted

Inline

@@ Line 56: / Line 56: @@
 	 * href="http://en.wikipedia.org/wiki/Topological_sort#Algorithms" > Kahn's
 	 * pseudo code</a> and traverses over vertices as they are returned by input
-	 * map. Leaf nodes can have null or empty values.
+	 * map. Leaf nodes can have null or empty values. Every missing definition
+	 * is considered as a leaf node.
 	 * </p>
 	 *
@@ Line 79: / Line 80: @@
 	 *
 	 */
-	public <T> ArrayList<T> tSort(java.util.Map<T, ArrayList<T>> g) {
+	public static <T> ArrayList<T> tSort(java.util.Map<T, ArrayList<T>> g)
+	/**
-		T n; // Current element.
+	 * @param L
-		ArrayList<T> L = /* Answer */
+	 *            Answer.
-		new ArrayList<T>(g.size());
+	 * @param S
-		java.util.HashSet<T> V = /* ! Visited elements */
+	 *            Not visited leaf vertices.
-		new java.util.HashSet<T>();
+	 * @param V
-		java.util.Queue<T> S = /* ! Visited leaf nodes */
+	 *            Visited vertices.
-		new java.util.concurrent.LinkedBlockingDeque<T>();
+	 * @param P
+	 *            Predefined vertices.
+	 * @param n
+	 *            Current element.
+	 */
+	{
+		java.util.ArrayList<T> L = new ArrayList<T>(g.size());
+		java.util.Queue<T> S = new java.util.concurrent.LinkedBlockingDeque<T>();
+		java.util.HashSet<T> V = new java.util.HashSet<T>(), P = new java.util.HashSet<T>();
+		P.addAll(g.keySet());
+		T n;
-		// Find leaf nodes.
+		// Find leaf nodes and missing leaf nodes.
 		for (T t : g.keySet())
 			if (g.get(t) == null || g.get(t).isEmpty())
 				S.add(t);
+			else
+				for (T m : g.get(t))
+					if (!P.contains(m))
+						S.add(t);
 		// Visit all leaf nodes.