Migrated source code from Simantics SVN

[simantics/platform.git] / bundles / org.simantics.utils.datastructures / src / org / simantics / utils / datastructures / TreeProblem.java

diff --git a/bundles/org.simantics.utils.datastructures/src/org/simantics/utils/datastructures/TreeProblem.java b/bundles/org.simantics.utils.datastructures/src/org/simantics/utils/datastructures/TreeProblem.java
new file mode 100644 (file)
index 0000000..d3aaca7
--- /dev/null
+++ b/bundles/org.simantics.utils.datastructures/src/org/simantics/utils/datastructures/TreeProblem.java
@@ -0,0 +1,112 @@
+/*******************************************************************************\r
+ * Copyright (c) 2007, 2010 Association for Decentralized Information Management\r
+ * in Industry THTH ry.\r
+ * All rights reserved. This program and the accompanying materials\r
+ * are made available under the terms of the Eclipse Public License v1.0\r
+ * which accompanies this distribution, and is available at\r
+ * http://www.eclipse.org/legal/epl-v10.html\r
+ *\r
+ * Contributors:\r
+ *     VTT Technical Research Centre of Finland - initial API and implementation\r
+ *******************************************************************************/\r
+package org.simantics.utils.datastructures;\r
+\r
+import java.util.ArrayList;\r
+import java.util.Collection;\r
+import java.util.Collections;\r
+import java.util.Comparator;\r
+import java.util.LinkedList;\r
+import java.util.PriorityQueue;\r
+\r
+\r
+/**\r
+ * This class contains utilities for finding solutions for a tree of problems.\r
+ * (e.g. path finding, routing, etc)\r
+ * \r
+ * @author Toni Kalajainen\r
+ */\r
+public class TreeProblem {\r
+\r
+       public interface ProblemNode {\r
+               /**\r
+                * Get the cost to reach this node\r
+                * @return cost of reaching this node\r
+                */\r
+               double getCost(); \r
+               \r
+               /** \r
+                * Is this problem node a solution\r
+                * @return true if this node is a solution\r
+                */\r
+               boolean isComplete();\r
+               \r
+               /**\r
+                * Branch this problem into sub-problem\r
+                * @param list add sub-problems to the list\r
+                */\r
+               void branch(Collection<ProblemNode> list);\r
+       }\r
+       \r
+       private final static Comparator<ProblemNode> COST_COMPARATOR =\r
+               new Comparator<ProblemNode>() {\r
+                       @Override\r
+                       public int compare(ProblemNode o1, ProblemNode o2) {\r
+                               double c1 = o1.getCost();\r
+                               double c2 = o2.getCost();\r
+                               if (c1<c2) return -1;\r
+                               if (c1>c2) return 1;\r
+                               return 0;\r
+                       }};\r
+\r
+    /**\r
+     * Find any solution greedily (not optimal)\r
+     * \r
+     * @param root\r
+     * @return a node that is complete, i.e. solves the specified problem or\r
+     *         <code>null</code> if no solution was found\r
+     */\r
+       public static ProblemNode findSolution(ProblemNode root, int degree)\r
+       {\r
+               LinkedList<LinkedList<ProblemNode>> stack = new LinkedList<LinkedList<ProblemNode>>();          \r
+               LinkedList<ProblemNode> lst = new LinkedList<ProblemNode>();            \r
+               lst.add(root);\r
+               stack.add(lst);\r
+               while (!stack.isEmpty()) {\r
+                       lst = stack.peekLast();\r
+                       ProblemNode b = lst.removeFirst();\r
+                       if (lst.isEmpty()) stack.removeLast();\r
+                       if (b.isComplete()) return b;\r
+                       lst = new LinkedList<ProblemNode>();\r
+                       b.branch(lst);\r
+                       if (!lst.isEmpty()) {\r
+                               Collections.sort(lst, COST_COMPARATOR);\r
+                               stack.addLast(lst);\r
+                       }\r
+               }\r
+               return null;\r
+       }\r
+\r
+    /**\r
+     * Find optimal solution\r
+     * \r
+     * @param root\r
+     * @return the optimal solution for the specified problem or\r
+     *         <code>null</code> if no solution exists.\r
+     */\r
+       public static ProblemNode findOptimalSolution(ProblemNode root)\r
+       {\r
+               ArrayList<ProblemNode> lst = new ArrayList<ProblemNode>();\r
+               PriorityQueue<ProblemNode> pq = new PriorityQueue<ProblemNode>(16, COST_COMPARATOR);\r
+               pq.add(root);\r
+               while (!pq.isEmpty()) {\r
+                       ProblemNode node = pq.poll();\r
+                       if (node.isComplete()) return node;\r
+                       //node.branch(pq);\r
+                       lst.clear();\r
+                       node.branch(lst);\r
+                       pq.addAll(lst);\r
+               }\r
+               return null;\r
+       }\r
+       \r
+}\r