-package org.simantics.modeling.scl;\r
-\r
-import gnu.trove.list.array.TIntArrayList;\r
-import gnu.trove.set.hash.THashSet;\r
-\r
-import java.util.ArrayList;\r
-import java.util.Arrays;\r
-import java.util.Collection;\r
-import java.util.List;\r
-\r
-import org.simantics.db.ReadGraph;\r
-import org.simantics.db.Resource;\r
-import org.simantics.db.exception.DatabaseException;\r
-import org.simantics.diagram.stubs.DiagramResource;\r
-\r
-public class RouteGraphMatching {\r
-\r
- public static boolean TRACE = false;\r
- \r
- private static class Link {\r
- public final int a;\r
- public final int b;\r
- \r
- public Link(int a, int b) {\r
- this.a = a;\r
- this.b = b;\r
- }\r
- }\r
- \r
- private static class MatchingProcess {\r
- ReadGraph graph;\r
- DiagramResource DIA;\r
- Resource[] result;\r
- ArrayList<Link>[] ls;\r
- ArrayList<Resource>[] alternatives;\r
- TIntArrayList stack = new TIntArrayList();\r
- THashSet<Resource> knownResources = new THashSet<Resource>(); \r
- \r
- @SuppressWarnings("unchecked")\r
- public MatchingProcess(ReadGraph graph, int size) {\r
- this.graph = graph;\r
- this.DIA = DiagramResource.getInstance(graph);\r
- this.result = new Resource[size];\r
- this.ls = new ArrayList[size];\r
- this.alternatives = new ArrayList[size];\r
- for(int i=0;i<size;++i)\r
- this.ls[i] = new ArrayList<Link>(2);\r
- }\r
- \r
- public void addLink(int a, int b) {\r
- Link link = new Link(a, b);\r
- ls[link.a].add(link);\r
- ls[link.b].add(link);\r
- }\r
-\r
- public boolean match(List<Resource> known) throws DatabaseException {\r
- for(int i=0;i<known.size();++i) {\r
- result[i] = known.get(i);\r
- stack.add(i);\r
- }\r
- while(!stack.isEmpty()) {\r
- while(!stack.isEmpty()) {\r
- int pos = stack.removeAt(stack.size()-1);\r
- if(!propagate(pos))\r
- return false;\r
- }\r
- if(!removeKnownResourcesFromAlternatives())\r
- return false;\r
- }\r
- for(int i=0;i<result.length;++i)\r
- if(result[i] == null) {\r
- System.err.println("Didn't resolve resource " + i + ".");\r
- printState();\r
- return false;\r
- }\r
- return true;\r
- }\r
-\r
- private boolean removeKnownResourcesFromAlternatives() throws DatabaseException {\r
- for(int i=0;i<result.length;++i) {\r
- ArrayList<Resource> alt = alternatives[i];\r
- if(alt != null) {\r
- alt.removeAll(knownResources);\r
- if(alt.isEmpty())\r
- return false;\r
- if(alt.size() == 1) {\r
- result[i] = alt.get(0);\r
- alternatives[i] = null;\r
- stack.add(i);\r
- }\r
- }\r
- }\r
- return true;\r
- }\r
-\r
- private void printState() {\r
- for(int i=0;i<result.length;++i) {\r
- System.out.print(" {" + i + "} ");\r
- if(result[i] != null)\r
- System.out.print(" = " + result[i].getResourceId());\r
- else if(alternatives[i] != null) {\r
- System.out.print(" in");\r
- for(Resource r : alternatives[i])\r
- System.out.print(" " + r.getResourceId());\r
- }\r
- else\r
- System.out.print(" unknown");\r
- if(!ls[i].isEmpty()) {\r
- System.out.print(", links to");\r
- for(Link l : ls[i])\r
- System.out.print(" " + (l.a==i ? l.b : l.a));\r
- }\r
- System.out.println();\r
- }\r
- }\r
-\r
- private boolean propagate(int pos) throws DatabaseException {\r
- if(TRACE)\r
- System.out.println("propagate(" + pos + ")");\r
- Resource r = result[pos];\r
- knownResources.add(r);\r
- ArrayList<Resource> neighbors = \r
- new ArrayList<Resource>(graph.getObjects(r, DIA.AreConnected));\r
- neighbors.removeAll(knownResources);\r
- \r
- for(Link link : ls[pos]) {\r
- int other = link.a == pos ? link.b : link.a;\r
- ls[other].remove(link);\r
- if(!setAlternatives(other, neighbors))\r
- return false;\r
- }\r
- ls[pos].clear();\r
- \r
- return true;\r
- }\r
-\r
- private boolean setKnown(int i, Resource value) throws DatabaseException {\r
- if(TRACE)\r
- System.out.println("setKnown(" + i + ", " + value + ")");\r
- if(result[i] != null) \r
- return result[i].equals(value);\r
- if(alternatives[i] != null) {\r
- if(!alternatives[i].contains(value))\r
- return false;\r
- alternatives[i] = null;\r
- }\r
- result[i] = value;\r
- stack.add(i);\r
- return true;\r
- }\r
- \r
- private boolean setAlternatives(int i, Collection<Resource> values) throws DatabaseException {\r
- if(TRACE)\r
- System.out.println("setAlternatives(" + i + ", " + values + ")");\r
- if(result[i] != null)\r
- return values.contains(result[i]);\r
- if(values.isEmpty())\r
- return false;\r
- if(values.size() == 1)\r
- return setKnown(i, values.iterator().next());\r
- ArrayList<Resource> oldAlternatives = alternatives[i];\r
- if(oldAlternatives == null) {\r
- alternatives[i] = new ArrayList<Resource>(values);\r
- return true;\r
- }\r
- oldAlternatives.retainAll(values);\r
- if(oldAlternatives.isEmpty())\r
- return false;\r
- if(oldAlternatives.size() == 1)\r
- return setKnown(i, oldAlternatives.get(0));\r
- return true;\r
- }\r
- }\r
- \r
- public static List<Resource> matchRouteGraph(ReadGraph graph, \r
- List<Resource> connectors, int routeLineCount, List<Integer> links) throws DatabaseException {\r
- MatchingProcess process = new MatchingProcess(graph, connectors.size() + routeLineCount);\r
- for(int i=0;i<links.size();i+=2)\r
- process.addLink(links.get(i), links.get(i+1));\r
- if(!process.match(connectors))\r
- return null;\r
- return Arrays.asList(process.result);\r
- }\r
- \r
-}\r
+package org.simantics.modeling.scl;
+
+import gnu.trove.list.array.TIntArrayList;
+import gnu.trove.set.hash.THashSet;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.List;
+
+import org.simantics.db.ReadGraph;
+import org.simantics.db.Resource;
+import org.simantics.db.exception.DatabaseException;
+import org.simantics.diagram.stubs.DiagramResource;
+
+public class RouteGraphMatching {
+
+ public static boolean TRACE = false;
+
+ private static class Link {
+ public final int a;
+ public final int b;
+
+ public Link(int a, int b) {
+ this.a = a;
+ this.b = b;
+ }
+ }
+
+ private static class MatchingProcess {
+ ReadGraph graph;
+ DiagramResource DIA;
+ Resource[] result;
+ ArrayList<Link>[] ls;
+ ArrayList<Resource>[] alternatives;
+ TIntArrayList stack = new TIntArrayList();
+ THashSet<Resource> knownResources = new THashSet<Resource>();
+
+ @SuppressWarnings("unchecked")
+ public MatchingProcess(ReadGraph graph, int size) {
+ this.graph = graph;
+ this.DIA = DiagramResource.getInstance(graph);
+ this.result = new Resource[size];
+ this.ls = new ArrayList[size];
+ this.alternatives = new ArrayList[size];
+ for(int i=0;i<size;++i)
+ this.ls[i] = new ArrayList<Link>(2);
+ }
+
+ public void addLink(int a, int b) {
+ Link link = new Link(a, b);
+ ls[link.a].add(link);
+ ls[link.b].add(link);
+ }
+
+ public boolean match(List<Resource> known) throws DatabaseException {
+ for(int i=0;i<known.size();++i) {
+ result[i] = known.get(i);
+ stack.add(i);
+ }
+ while(!stack.isEmpty()) {
+ while(!stack.isEmpty()) {
+ int pos = stack.removeAt(stack.size()-1);
+ if(!propagate(pos))
+ return false;
+ }
+ if(!removeKnownResourcesFromAlternatives())
+ return false;
+ }
+ for(int i=0;i<result.length;++i)
+ if(result[i] == null) {
+ System.err.println("Didn't resolve resource " + i + ".");
+ printState();
+ return false;
+ }
+ return true;
+ }
+
+ private boolean removeKnownResourcesFromAlternatives() throws DatabaseException {
+ for(int i=0;i<result.length;++i) {
+ ArrayList<Resource> alt = alternatives[i];
+ if(alt != null) {
+ alt.removeAll(knownResources);
+ if(alt.isEmpty())
+ return false;
+ if(alt.size() == 1) {
+ result[i] = alt.get(0);
+ alternatives[i] = null;
+ stack.add(i);
+ }
+ }
+ }
+ return true;
+ }
+
+ private void printState() {
+ for(int i=0;i<result.length;++i) {
+ System.out.print(" {" + i + "} ");
+ if(result[i] != null)
+ System.out.print(" = " + result[i].getResourceId());
+ else if(alternatives[i] != null) {
+ System.out.print(" in");
+ for(Resource r : alternatives[i])
+ System.out.print(" " + r.getResourceId());
+ }
+ else
+ System.out.print(" unknown");
+ if(!ls[i].isEmpty()) {
+ System.out.print(", links to");
+ for(Link l : ls[i])
+ System.out.print(" " + (l.a==i ? l.b : l.a));
+ }
+ System.out.println();
+ }
+ }
+
+ private boolean propagate(int pos) throws DatabaseException {
+ if(TRACE)
+ System.out.println("propagate(" + pos + ")");
+ Resource r = result[pos];
+ knownResources.add(r);
+ ArrayList<Resource> neighbors =
+ new ArrayList<Resource>(graph.getObjects(r, DIA.AreConnected));
+ neighbors.removeAll(knownResources);
+
+ for(Link link : ls[pos]) {
+ int other = link.a == pos ? link.b : link.a;
+ ls[other].remove(link);
+ if(!setAlternatives(other, neighbors))
+ return false;
+ }
+ ls[pos].clear();
+
+ return true;
+ }
+
+ private boolean setKnown(int i, Resource value) throws DatabaseException {
+ if(TRACE)
+ System.out.println("setKnown(" + i + ", " + value + ")");
+ if(result[i] != null)
+ return result[i].equals(value);
+ if(alternatives[i] != null) {
+ if(!alternatives[i].contains(value))
+ return false;
+ alternatives[i] = null;
+ }
+ result[i] = value;
+ stack.add(i);
+ return true;
+ }
+
+ private boolean setAlternatives(int i, Collection<Resource> values) throws DatabaseException {
+ if(TRACE)
+ System.out.println("setAlternatives(" + i + ", " + values + ")");
+ if(result[i] != null)
+ return values.contains(result[i]);
+ if(values.isEmpty())
+ return false;
+ if(values.size() == 1)
+ return setKnown(i, values.iterator().next());
+ ArrayList<Resource> oldAlternatives = alternatives[i];
+ if(oldAlternatives == null) {
+ alternatives[i] = new ArrayList<Resource>(values);
+ return true;
+ }
+ oldAlternatives.retainAll(values);
+ if(oldAlternatives.isEmpty())
+ return false;
+ if(oldAlternatives.size() == 1)
+ return setKnown(i, oldAlternatives.get(0));
+ return true;
+ }
+ }
+
+ public static List<Resource> matchRouteGraph(ReadGraph graph,
+ List<Resource> connectors, int routeLineCount, List<Integer> links) throws DatabaseException {
+ MatchingProcess process = new MatchingProcess(graph, connectors.size() + routeLineCount);
+ for(int i=0;i<links.size();i+=2)
+ process.addLink(links.get(i), links.get(i+1));
+ if(!process.match(connectors))
+ return null;
+ return Arrays.asList(process.result);
+ }
+
+}
Code Review / simantics / platform.git / blobdiff