X-Git-Url: https://gerrit.simantics.org/r/gitweb?a=blobdiff_plain;f=bundles%2Forg.simantics.graph%2Fsrc%2Forg%2Fsimantics%2Fgraph%2Fmatching%2FIdentityMatchingStrategy.java;fp=bundles%2Forg.simantics.graph%2Fsrc%2Forg%2Fsimantics%2Fgraph%2Fmatching%2FIdentityMatchingStrategy.java;h=9caee5c3e934ea0082a7467944ad992d17828c0e;hb=969bd23cab98a79ca9101af33334000879fb60c5;hp=0000000000000000000000000000000000000000;hpb=866dba5cd5a3929bbeae85991796acb212338a08;p=simantics%2Fplatform.git

diff --git a/bundles/org.simantics.graph/src/org/simantics/graph/matching/IdentityMatchingStrategy.java b/bundles/org.simantics.graph/src/org/simantics/graph/matching/IdentityMatchingStrategy.java
new file mode 100644
index 000000000..9caee5c3e
--- /dev/null
+++ b/bundles/org.simantics.graph/src/org/simantics/graph/matching/IdentityMatchingStrategy.java
@@ -0,0 +1,147 @@
+package org.simantics.graph.matching;
+
+import gnu.trove.map.hash.TIntIntHashMap;
+import gnu.trove.map.hash.TIntObjectHashMap;
+import gnu.trove.map.hash.TObjectIntHashMap;
+
+import java.util.ArrayList;
+
+import org.simantics.graph.representation.External;
+import org.simantics.graph.representation.Identity;
+import org.simantics.graph.representation.Internal;
+import org.simantics.graph.representation.Optional;
+import org.simantics.graph.representation.Root;
+
+/**
+ * A strategy matching resources with equal URIs.
+ * 
+ * @author Hannu Niemistö
+ */
+public enum IdentityMatchingStrategy implements GraphMatchingStrategy {
+
+	INSTANCE;
+	
+	static class NamedResource {
+		String name;
+		int resource;
+		
+		public NamedResource(String name, int resource) {
+			this.name = name;
+			this.resource = resource;
+		}
+	}
+	
+	static class IdentityTree {
+		TIntObjectHashMap<ArrayList<NamedResource>> childMap = new TIntObjectHashMap<ArrayList<NamedResource>>();
+		ArrayList<NamedResource> roots = new ArrayList<NamedResource>(); 
+		
+		public IdentityTree(Identity[] indentities) {
+			for(Identity id : indentities) {
+				if(id.definition instanceof External) {
+					External def = (External)id.definition;
+					addChild(id.resource, def.parent, def.name);
+				}
+				else if(id.definition instanceof Internal) {
+					Internal def = (Internal)id.definition;
+					addChild(id.resource, def.parent, def.name);
+				}
+				else if(id.definition instanceof Optional) {
+					Optional def = (Optional)id.definition;
+					addChild(id.resource, def.parent, def.name);
+				}
+				else if(id.definition instanceof Root) {
+					addRoot(id.resource, ((Root)id.definition).name);
+				}
+			}
+		}
+
+		private void addRoot(int root, String name) {
+			roots.add(new NamedResource(name, root));
+		}
+		
+		private void addChild(int child, int parent, String name) {
+			ArrayList<NamedResource> children = childMap.get(parent);
+			if(children == null) {
+				children = new ArrayList<NamedResource>();
+				childMap.put(parent, children);
+			}
+			children.add(new NamedResource(name, child));
+		}
+	}
+	
+	static class MatchingProcess {
+		int[] aToB; 
+		int[] bToA; 
+		TIntIntHashMap aInv;
+		TIntIntHashMap bInv;
+		IdentityTree aTree; 
+		IdentityTree bTree;
+		
+		public MatchingProcess(int[] aToB, int[] bToA,
+				TIntIntHashMap aInv, TIntIntHashMap bInv,
+				IdentityTree aTree, IdentityTree bTree) {
+			this.aToB = aToB;
+			this.bToA = bToA;
+			this.aInv = aInv;
+			this.bInv = bInv;
+			this.aTree = aTree;
+			this.bTree = bTree;
+		}
+
+		public void execute() {
+			match(aTree.roots, bTree.roots);
+		}
+
+		private void match(ArrayList<NamedResource> as, ArrayList<NamedResource> bs) {
+			TObjectIntHashMap<String> map = new TObjectIntHashMap<String>();
+			for(NamedResource b : bs)
+				map.put(b.name, b.resource);
+			for(NamedResource a : as)
+				if(map.contains(a.name))
+					match(a.resource, map.get(a.name));
+		}
+
+		private void match(int a, int b) {
+			if(aToB[a] < 0 && bToA[b] < 0) {
+				aToB[a] = b;
+				bToA[b] = a;
+				
+				if(aInv.contains(a) && bInv.contains(b))
+					match(aInv.get(a), bInv.get(b));
+				
+				ArrayList<NamedResource> as = aTree.childMap.get(a);
+				if(as == null)
+					return;
+				ArrayList<NamedResource> bs = bTree.childMap.get(b);
+				if(bs == null)
+					return;
+				match(as, bs);
+			}
+		}
+	}
+	
+	public void mapUnmapped(int[] map, TIntIntHashMap inverses, Identity[] identities, int rangeCount) {
+		for(Identity id : identities) {
+			int r = id.resource;
+			if(map[r] < 0) {
+				map[r] = rangeCount++;
+				if(inverses.containsKey(r))
+					map[inverses.get(r)] = rangeCount++;
+			}
+		}
+	}
+	
+	@Override
+	public void applyTo(GraphMatching matching) {
+		new MatchingProcess(
+				matching.aToB, matching.bToA, 
+				matching.aGraph.inverses, matching.bGraph.inverses,
+				new IdentityTree(matching.aGraph.identities), new IdentityTree(matching.bGraph.identities)
+		).execute();	
+		mapUnmapped(matching.aToB, matching.aGraph.inverses, 
+				matching.aGraph.identities, matching.bGraph.resourceCount);
+		mapUnmapped(matching.bToA, matching.bGraph.inverses, 
+				matching.bGraph.identities, matching.aGraph.resourceCount);
+		matching.recomputeSize();
+	}
+}