bundles/org.simantics.graph/src/org/simantics/graph/diff/Diff.java

   1 package org.simantics.graph.diff;
   2
   3 import gnu.trove.map.hash.TIntObjectHashMap;
   4 import gnu.trove.procedure.TIntObjectProcedure;
   5 import gnu.trove.set.hash.THashSet;
   6
   7 import java.util.ArrayList;
   8 import java.util.Collection;
   9
  10 import org.simantics.databoard.binding.mutable.Variant;
  11 import org.simantics.graph.matching.GraphMatching;
  12 import org.simantics.graph.representation.External;
  13 import org.simantics.graph.representation.Identity;
  14 import org.simantics.graph.representation.IdentityDefinition;
  15 import org.simantics.graph.representation.Internal;
  16 import org.simantics.graph.representation.Optional;
  17 import org.simantics.graph.representation.Root;
  18 import org.simantics.graph.representation.TransferableGraph1;
  19 import org.simantics.graph.representation.Value;
  20
  21 public class Diff extends GraphMatching {
  22
  23         TransferableGraph1 a;
  24         TransferableGraph1 b;
  25
  26         public Diff(TransferableGraph1 a, TransferableGraph1 b) {
  27                 super(a, b);
  28                 this.a = a;
  29                 this.b = b;
  30         }
  31
  32         static THashSet<Statement> createStatementSet(int[] statements) {
  33                 THashSet<Statement> result = new THashSet<Statement>();
  34                 for(int i=0;i<statements.length;i+=4)
  35                         result.add(new Statement(
  36                                         statements[i],
  37                                         statements[i+1],
  38                                         statements[i+2],
  39                                         statements[i+3]
  40                         ));
  41                 return result;
  42         }
  43
  44         public TransferableGraphDelta1 diff() {
  45                 match();
  46
  47                 long begin = System.nanoTime();
  48
  49                 // Statement diff;
  50                 THashSet<Statement> aStatements = createStatementSet(a.statements);
  51                 ArrayList<Statement> bStatements = new ArrayList<Statement>();
  52
  53                 int[] statements = b.statements;
  54                 for(int i=0;i<statements.length;i+=4) {
  55                         Statement statement = new Statement(
  56                                         statements[i],
  57                                         statements[i+1],
  58                                         statements[i+2],
  59                                         statements[i+3]
  60                         );
  61                         Statement mappedStatement = statement.map(bToA);
  62                         if(mappedStatement == null || !aStatements.remove(mappedStatement))
  63                                 bStatements.add(statement);
  64                 }
  65
  66                 // Identity diff
  67                 TIntObjectHashMap<IdentityDefinition> aIdentities = new TIntObjectHashMap<IdentityDefinition>();
  68                 ArrayList<Identity> bIdentities = new ArrayList<Identity>();
  69                 for(Identity id : a.identities)
  70                         aIdentities.put(id.resource, id.definition);
  71                 for(Identity id : b.identities) {
  72                         int a = bToA[id.resource];
  73                         IdentityDefinition def = aIdentities.get(a);
  74                         if(def != null && identityDefinitionEquals(bToA, def, id.definition))
  75                                 aIdentities.remove(a);
  76                         else
  77                                 bIdentities.add(id);
  78                 }
  79
  80                 // Value diff
  81                 TIntObjectHashMap<Variant> aValues = new TIntObjectHashMap<Variant>();
  82                 ArrayList<Value> bValues = new ArrayList<Value>();
  83                 for(Value value : a.values)
  84                         aValues.put(value.resource, value.value);
  85
  86                 for(Value value : b.values) {
  87                         int a = bToA[value.resource]; // a may be -1
  88                         Variant aValue = aValues.get(a);
  89                         if(aValue != null && aValue.equals(value.value))
  90                                 aValues.remove(a);
  91                         else
  92                                 bValues.add(value);
  93                 }
  94
  95                 // Create result
  96                 TransferableGraphDelta1 result = new TransferableGraphDelta1(
  97                                 aToB,
  98                                 new TransferableGraph1(
  99                                         a.resourceCount,
 100                                         toIdentityArray(aIdentities),
 101                                         toStatementArray(aStatements),
 102                                         toValueArray(aValues)
 103                                 ),
 104                                 new TransferableGraph1(
 105                                         b.resourceCount,
 106                                         bIdentities.toArray(new Identity[bIdentities.size()]),
 107                                         toStatementArray(bStatements),
 108                                         bValues.toArray(new Value[bValues.size()])
 109                                 )
 110                         );
 111                 if(GraphMatching.TIMING) {
 112                         long end = System.nanoTime();
 113                         System.out.println("Diffing: " + (end-begin)*1e-6 + "ms");
 114                 }
 115                 return result;
 116         }
 117
 118         private static boolean identityDefinitionEquals(int[] bToA,
 119                         IdentityDefinition a, IdentityDefinition b) {
 120                 if(a instanceof Root)
 121                         return b instanceof Root && ((Root)a).name.equals(((Root)b).name);
 122                 if(b instanceof Root)
 123                         return false;
 124                 int aParent, bParent;
 125                 String aName, bName;
 126
 127                 if(b instanceof External) {
 128                         External def = (External)b;
 129                         bParent = def.parent;
 130                         bName = def.name;
 131                 }
 132                 else if(b instanceof Internal) {
 133                         Internal def = (Internal)b;
 134                         bParent = def.parent;
 135                         bName = def.name;
 136                 }
 137                 else if(b instanceof Optional) {
 138                         Optional def = (Optional)b;
 139                         bParent = def.parent;
 140                         bName = def.name;
 141                 }
 142                 else
 143                         return false;
 144                 bParent = bToA[bParent];
 145                 if(bParent < 0)
 146                         return false;
 147
 148                 if(a instanceof External) {
 149                         External def = (External)a;
 150                         aParent = def.parent;
 151                         aName = def.name;
 152                 }
 153                 else if(a instanceof Internal) {
 154                         Internal def = (Internal)a;
 155                         aParent = def.parent;
 156                         aName = def.name;
 157                 }
 158                 else if(a instanceof Optional) {
 159                         Optional def = (Optional)a;
 160                         aParent = def.parent;
 161                         aName = def.name;
 162                 }
 163                 else
 164                         return false;
 165                 return aParent == bParent && aName.equals(bName);
 166         }
 167
 168         static int[] toStatementArray(Collection<Statement> statements) {
 169                 int[] result = new int[4*statements.size()];
 170                 int i=0;
 171                 for(Statement statement : statements) {
 172                         result[i++] = statement.subject;
 173                         result[i++] = statement.predicate;
 174                         result[i++] = statement.inverse;
 175                         result[i++] = statement.object;
 176                 }
 177                 return result;
 178         }
 179
 180         static Value[] toValueArray(TIntObjectHashMap<Variant> values) {
 181                 final Value[] result = new Value[values.size()];
 182                 values.forEachEntry(new TIntObjectProcedure<Variant>() {
 183                         int i=0;
 184                         @Override
 185                         public boolean execute(int a, Variant b) {
 186                                 result[i++] = new Value(a, b);
 187                                 return true;
 188                         }
 189                 });
 190                 return result;
 191         }
 192
 193         static Identity[] toIdentityArray(TIntObjectHashMap<IdentityDefinition> identities) {
 194                 final Identity[] result = new Identity[identities.size()];
 195                 identities.forEachEntry(new TIntObjectProcedure<IdentityDefinition>() {
 196                         int i=0;
 197                         @Override
 198                         public boolean execute(int a, IdentityDefinition b) {
 199                                 result[i++] = new Identity(a, b);
 200                                 return true;
 201                         }
 202                 });
 203                 return result;
 204         }
 205
 206 }