X-Git-Url: https://gerrit.simantics.org/r/gitweb?a=blobdiff_plain;ds=sidebyside;f=bundles%2Forg.simantics.utils.datastructures%2Fsrc%2Forg%2Fsimantics%2Futils%2Fdatastructures%2FTreeProblem.java;h=e1576cccf0fe31ab5276af137ead426331c17e91;hb=refs%2Fchanges%2F38%2F238%2F2;hp=d3aaca74810cc2f3629918438b0a0396f9b19213;hpb=24e2b34260f219f0d1644ca7a138894980e25b14;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 index d3aaca748..e1576cccf 100644 --- 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 @@ -1,112 +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 list); - } - - private final static Comparator COST_COMPARATOR = - new Comparator() { - @Override - public int compare(ProblemNode o1, ProblemNode o2) { - double c1 = o1.getCost(); - double c2 = o2.getCost(); - if (c1c2) 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 - * null if no solution was found - */ - public static ProblemNode findSolution(ProblemNode root, int degree) - { - LinkedList> stack = new LinkedList>(); - LinkedList lst = new LinkedList(); - 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(); - 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 - * null if no solution exists. - */ - public static ProblemNode findOptimalSolution(ProblemNode root) - { - ArrayList lst = new ArrayList(); - PriorityQueue pq = new PriorityQueue(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; - } - -} +/******************************************************************************* + * 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 list); + } + + private final static Comparator COST_COMPARATOR = + new Comparator() { + @Override + public int compare(ProblemNode o1, ProblemNode o2) { + double c1 = o1.getCost(); + double c2 = o2.getCost(); + if (c1c2) 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 + * null if no solution was found + */ + public static ProblemNode findSolution(ProblemNode root, int degree) + { + LinkedList> stack = new LinkedList>(); + LinkedList lst = new LinkedList(); + 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(); + 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 + * null if no solution exists. + */ + public static ProblemNode findOptimalSolution(ProblemNode root) + { + ArrayList lst = new ArrayList(); + PriorityQueue pq = new PriorityQueue(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; + } + +}