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