bundles/org.simantics.graph/src/org/simantics/graph/matching/IdentityMatchingStrategy.java

   1 package org.simantics.graph.matching;\r
   2 \r
   3 import gnu.trove.map.hash.TIntIntHashMap;\r
   4 import gnu.trove.map.hash.TIntObjectHashMap;\r
   5 import gnu.trove.map.hash.TObjectIntHashMap;\r
   6 \r
   7 import java.util.ArrayList;\r
   8 \r
   9 import org.simantics.graph.representation.External;\r
  10 import org.simantics.graph.representation.Identity;\r
  11 import org.simantics.graph.representation.Internal;\r
  12 import org.simantics.graph.representation.Optional;\r
  13 import org.simantics.graph.representation.Root;\r
  14 \r
  15 /**\r
  16  * A strategy matching resources with equal URIs.\r
  17  * \r
  18  * @author Hannu Niemistö\r
  19  */\r
  20 public enum IdentityMatchingStrategy implements GraphMatchingStrategy {\r
  21 \r
  22         INSTANCE;\r
  23         \r
  24         static class NamedResource {\r
  25                 String name;\r
  26                 int resource;\r
  27                 \r
  28                 public NamedResource(String name, int resource) {\r
  29                         this.name = name;\r
  30                         this.resource = resource;\r
  31                 }\r
  32         }\r
  33         \r
  34         static class IdentityTree {\r
  35                 TIntObjectHashMap<ArrayList<NamedResource>> childMap = new TIntObjectHashMap<ArrayList<NamedResource>>();\r
  36                 ArrayList<NamedResource> roots = new ArrayList<NamedResource>(); \r
  37                 \r
  38                 public IdentityTree(Identity[] indentities) {\r
  39                         for(Identity id : indentities) {\r
  40                                 if(id.definition instanceof External) {\r
  41                                         External def = (External)id.definition;\r
  42                                         addChild(id.resource, def.parent, def.name);\r
  43                                 }\r
  44                                 else if(id.definition instanceof Internal) {\r
  45                                         Internal def = (Internal)id.definition;\r
  46                                         addChild(id.resource, def.parent, def.name);\r
  47                                 }\r
  48                                 else if(id.definition instanceof Optional) {\r
  49                                         Optional def = (Optional)id.definition;\r
  50                                         addChild(id.resource, def.parent, def.name);\r
  51                                 }\r
  52                                 else if(id.definition instanceof Root) {\r
  53                                         addRoot(id.resource, ((Root)id.definition).name);\r
  54                                 }\r
  55                         }\r
  56                 }\r
  57 \r
  58                 private void addRoot(int root, String name) {\r
  59                         roots.add(new NamedResource(name, root));\r
  60                 }\r
  61                 \r
  62                 private void addChild(int child, int parent, String name) {\r
  63                         ArrayList<NamedResource> children = childMap.get(parent);\r
  64                         if(children == null) {\r
  65                                 children = new ArrayList<NamedResource>();\r
  66                                 childMap.put(parent, children);\r
  67                         }\r
  68                         children.add(new NamedResource(name, child));\r
  69                 }\r
  70         }\r
  71         \r
  72         static class MatchingProcess {\r
  73                 int[] aToB; \r
  74                 int[] bToA; \r
  75                 TIntIntHashMap aInv;\r
  76                 TIntIntHashMap bInv;\r
  77                 IdentityTree aTree; \r
  78                 IdentityTree bTree;\r
  79                 \r
  80                 public MatchingProcess(int[] aToB, int[] bToA,\r
  81                                 TIntIntHashMap aInv, TIntIntHashMap bInv,\r
  82                                 IdentityTree aTree, IdentityTree bTree) {\r
  83                         this.aToB = aToB;\r
  84                         this.bToA = bToA;\r
  85                         this.aInv = aInv;\r
  86                         this.bInv = bInv;\r
  87                         this.aTree = aTree;\r
  88                         this.bTree = bTree;\r
  89                 }\r
  90 \r
  91                 public void execute() {\r
  92                         match(aTree.roots, bTree.roots);\r
  93                 }\r
  94 \r
  95                 private void match(ArrayList<NamedResource> as, ArrayList<NamedResource> bs) {\r
  96                         TObjectIntHashMap<String> map = new TObjectIntHashMap<String>();\r
  97                         for(NamedResource b : bs)\r
  98                                 map.put(b.name, b.resource);\r
  99                         for(NamedResource a : as)\r
 100                                 if(map.contains(a.name))\r
 101                                         match(a.resource, map.get(a.name));\r
 102                 }\r
 103 \r
 104                 private void match(int a, int b) {\r
 105                         if(aToB[a] < 0 && bToA[b] < 0) {\r
 106                                 aToB[a] = b;\r
 107                                 bToA[b] = a;\r
 108                                 \r
 109                                 if(aInv.contains(a) && bInv.contains(b))\r
 110                                         match(aInv.get(a), bInv.get(b));\r
 111                                 \r
 112                                 ArrayList<NamedResource> as = aTree.childMap.get(a);\r
 113                                 if(as == null)\r
 114                                         return;\r
 115                                 ArrayList<NamedResource> bs = bTree.childMap.get(b);\r
 116                                 if(bs == null)\r
 117                                         return;\r
 118                                 match(as, bs);\r
 119                         }\r
 120                 }\r
 121         }\r
 122         \r
 123         public void mapUnmapped(int[] map, TIntIntHashMap inverses, Identity[] identities, int rangeCount) {\r
 124                 for(Identity id : identities) {\r
 125                         int r = id.resource;\r
 126                         if(map[r] < 0) {\r
 127                                 map[r] = rangeCount++;\r
 128                                 if(inverses.containsKey(r))\r
 129                                         map[inverses.get(r)] = rangeCount++;\r
 130                         }\r
 131                 }\r
 132         }\r
 133         \r
 134         @Override\r
 135         public void applyTo(GraphMatching matching) {\r
 136                 new MatchingProcess(\r
 137                                 matching.aToB, matching.bToA, \r
 138                                 matching.aGraph.inverses, matching.bGraph.inverses,\r
 139                                 new IdentityTree(matching.aGraph.identities), new IdentityTree(matching.bGraph.identities)\r
 140                 ).execute();    \r
 141                 mapUnmapped(matching.aToB, matching.aGraph.inverses, \r
 142                                 matching.aGraph.identities, matching.bGraph.resourceCount);\r
 143                 mapUnmapped(matching.bToA, matching.bGraph.inverses, \r
 144                                 matching.bGraph.identities, matching.aGraph.resourceCount);\r
 145                 matching.recomputeSize();\r
 146         }\r
 147 }\r