X-Git-Url: https://gerrit.simantics.org/r/gitweb?a=blobdiff_plain;f=bundles%2Forg.simantics.utils.datastructures%2Fsrc%2Forg%2Fsimantics%2Futils%2Fdatastructures%2FTreeProblem.java;fp=bundles%2Forg.simantics.utils.datastructures%2Fsrc%2Forg%2Fsimantics%2Futils%2Fdatastructures%2FTreeProblem.java;h=d3aaca74810cc2f3629918438b0a0396f9b19213;hb=969bd23cab98a79ca9101af33334000879fb60c5;hp=0000000000000000000000000000000000000000;hpb=866dba5cd5a3929bbeae85991796acb212338a08;p=simantics%2Fplatform.git

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
index 000000000..d3aaca748
--- /dev/null
+++ b/bundles/org.simantics.utils.datastructures/src/org/simantics/utils/datastructures/TreeProblem.java
@@ -0,0 +1,112 @@
+/*******************************************************************************
+ * 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;
+	}
+	
+}