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

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