From 97c68766209d534318dfc146727eb5670fca848e Mon Sep 17 00:00:00 2001 From: Marko Luukkainen Date: Thu, 6 Apr 2017 13:53:06 +0300 Subject: [PATCH] Three-way comparison: utilise old changes in the update step refs #7045 Change-Id: Icb060716503992e2dbb69b779952f397e6df9169 --- .../update/editor/ModelUpdateEditor.java | 157 +- .../update/editor/UpdateEditorInput.java | 28 +- .../interop/test/GraphComparator.java | 2501 +++++++++-------- 3 files changed, 1388 insertions(+), 1298 deletions(-) diff --git a/org.simantics.interop.update/src/org/simantics/interop/update/editor/ModelUpdateEditor.java b/org.simantics.interop.update/src/org/simantics/interop/update/editor/ModelUpdateEditor.java index 860057d..0881a7b 100644 --- a/org.simantics.interop.update/src/org/simantics/interop/update/editor/ModelUpdateEditor.java +++ b/org.simantics.interop.update/src/org/simantics/interop/update/editor/ModelUpdateEditor.java @@ -4,8 +4,8 @@ import java.util.ArrayList; import java.util.Collection; import java.util.HashSet; import java.util.List; -import java.util.Stack; import java.util.Map.Entry; +import java.util.Stack; import org.eclipse.jface.resource.ImageDescriptor; import org.eclipse.jface.resource.JFaceResources; @@ -83,6 +83,7 @@ public abstract class ModelUpdateEditor extends Composite{ private UpdateList updateList; private GraphChanges changes2; + private GraphChanges changes3; private UpdateTree updateTree2; private UpdateList updateList2; @@ -401,23 +402,16 @@ public abstract class ModelUpdateEditor extends Composite{ addFilters(filters); - Resource r1 = uei.getR1(); - Resource r2 = uei.getR2(); - Resource r3 = uei.getR3(); + Resource oldModel = uei.getR1(); // old model that is being updated, contains user made changes + Resource newModel = uei.getR2(); // new model, + Resource originalModel = uei.getR3(); // original old model without user made changes try { - Pair result = getChanges(r1,r2); - GraphComparator comparator = result.first; - if (result.second != null) - showWarning(result.second); - comparator.test(getSession()); - changes = comparator.getChanges(); - changes = getSession().syncRequest(new FilterChangesRead(changes)); - updateTree = getUpdateTree(changes); - updateList = getUpdateList(changes); - if (r3 != null) { - Pair result2 = getChanges(r1,r3); + if (originalModel != null) { + // tree way comparison + // compare the original and the old model + Pair result2 = getChanges(originalModel, oldModel); GraphComparator comparator2 = result2.first; if (result2.second != null) showWarning(result2.second); @@ -427,8 +421,63 @@ public abstract class ModelUpdateEditor extends Composite{ updateTree2 = getUpdateTree(changes2); updateList2 = getUpdateList(changes2); + // compare the original and the new model + Pair result3 = getChanges(originalModel,newModel); + GraphComparator comparator3 = result3.first; + if (result3.second != null) + showWarning(result3.second); + comparator3.test(getSession()); + changes3 = comparator3.getChanges(); + changes3 = getSession().syncRequest(new FilterChangesRead(changes3)); + } + + Pair result = getChanges(oldModel,newModel); + GraphComparator comparator = result.first; + if (result.second != null) + showWarning(result.second); + if (originalModel != null) { + // three-way comparison: use change information to configure + // the comparison between the old and the new model. + + // 1. map comparable resources + for (Entry origToOld : changes2.getComparable().getEntries()) { + Resource oldR = origToOld.getValue(); + Resource newR = changes3.getComparable().getRight(origToOld.getKey()); + if (newR != null) { + comparator.addComparableResources(oldR, newR); + } + } + // 2. mark removed resources as distinct, so that comparison does not pair them + for (Statement s : changes2.getDeletions()) { + if (changes3.getComparable().containsLeft(s.getObject())) + comparator.addNonMatchedRight(changes3.getComparable().getRight(s.getObject())); + } + + for (Statement s : changes3.getDeletions()) { + if (changes2.getComparable().containsLeft(s.getObject())) + comparator.addNonMatchedLeft(changes2.getComparable().getRight(s.getObject())); + } + if (uei.isNewDistinct()) { + // 3. mark added resources as distinct, so that comparison does not pair them + for (Statement s : changes2.getAdditions()) { + comparator.addNonMatchedLeft(s.getObject()); + } + + for (Statement s : changes3.getAdditions()) { + comparator.addNonMatchedRight(s.getObject()); + } + } + } + comparator.test(getSession()); + changes = comparator.getChanges(); + changes = getSession().syncRequest(new FilterChangesRead(changes)); + updateTree = getUpdateTree(changes); + updateList = getUpdateList(changes); + + if (originalModel != null) { createDefaultSelections(); } + } catch (DatabaseException e) { Text text = new Text(this, SWT.MULTI); text.setText(e.getMessage()); @@ -529,6 +578,47 @@ public abstract class ModelUpdateEditor extends Composite{ } }); } + + protected void createDefaultSelections() { + // select all changes + for (Entry op : updateTree.getUpdateOps().getResourceMap().entrySet()) { + op.getValue().select(true); + } + + + for (Pair pair : updateList.getChanges()) { + updateList.addSelected(pair); + } + + // preserve user-made changes (by removing selections) + for (Entry op : updateTree.getUpdateOps().getResourceMap().entrySet()) { + UpdateOp op2 = updateTree2.getUpdateOps().getUpdateOp(op.getKey()); + if (op2 == null) { + if (changes3.getComparable().containsRight(op.getKey())){ + op2 = updateTree2.getUpdateOps().getUpdateOp(changes3.getComparable().getLeft(op.getKey())); + } + } + if (op2 != null && op.getValue().getClass() == op2.getClass()) { + op.getValue().select(false); + } + } + + for (Pair pair : updateList.getChanges()) { + if (pair.first != null) { + boolean found = false; + for (Pair pair2 : updateList2.getChanges()) { + if (pair.first.equals(pair2.first)) { + found = true; + break; + } + } + if (found) { + updateList.removeSelected(pair); + } + } + } + + } /** @@ -565,42 +655,7 @@ public abstract class ModelUpdateEditor extends Composite{ public interface ChangeFilter { public boolean accept(ReadGraph g, Pair change) throws DatabaseException; } - - - protected void createDefaultSelections() { - for (Entry op : updateTree.getUpdateOps().getResourceMap().entrySet()) { - UpdateOp op2 = updateTree2.getUpdateOps().getUpdateOp(op.getKey()); - if (op2 == null) { - op.getValue().select(true); - } - } - - for (Entry op : updateTree.getUpdateOps().getStatementMap().entrySet()) { - UpdateOp op2 = updateTree2.getUpdateOps().getUpdateOp(op.getKey()); - if (op2 == null) { - op.getValue().select(true); - } - } - - for (Pair pair : updateList.getChanges()) { - if (pair.first != null) { - boolean found = false; - for (Pair pair2 : updateList2.getChanges()) { - if (pair.first.equals(pair2.first)) { - found = true; - break; - } - } - if (!found) { - updateList.addSelected(pair); - } - } else { - updateList.addSelected(pair); - } - } - } - - + /** * diff --git a/org.simantics.interop.update/src/org/simantics/interop/update/editor/UpdateEditorInput.java b/org.simantics.interop.update/src/org/simantics/interop/update/editor/UpdateEditorInput.java index f54b1c9..0494b0b 100644 --- a/org.simantics.interop.update/src/org/simantics/interop/update/editor/UpdateEditorInput.java +++ b/org.simantics.interop.update/src/org/simantics/interop/update/editor/UpdateEditorInput.java @@ -18,13 +18,23 @@ public class UpdateEditorInput extends ResourceEditorInput2{ private Resource r1; private Resource r2; private Resource r3; + private boolean newDistinct = false; - public UpdateEditorInput(String editorID, Resource r1, Resource r2, Resource model, RVI rvi) { - this(editorID, r1, r2, null, model, rvi); + + public UpdateEditorInput(String editorID, Resource r1, Resource r2, RVI rvi) { + this(editorID, r1, r2, null,rvi); } - public UpdateEditorInput(String editorID, Resource r1, Resource r2, Resource r3, Resource model, RVI rvi) { - super(editorID, r1, model, rvi); + /** + * + * @param editorID + * @param r1 old model that is being updated + * @param r2 new model containing the changes that we want to apply + * @param r3 original model to detect user mace changes to the old model r1. This parameter can be + * @param rvi + */ + public UpdateEditorInput(String editorID, Resource r1, Resource r2, Resource r3, RVI rvi) { + super(editorID, r1, r1, rvi); this.r1 = r1; this.r2 = r2; this.r3 = r3; @@ -48,4 +58,14 @@ public class UpdateEditorInput extends ResourceEditorInput2{ WorkbenchUtils.openEditor(editorID, this); } + // With tree-way comparison, treat new resources for compared old and new models as distinct. + // default : false. Comparison may consider that new objects in models r1 and r2 are the same. + public boolean isNewDistinct() { + return newDistinct; + } + + public void setNewDistinct(boolean newDistinct) { + this.newDistinct = newDistinct; + } + } diff --git a/org.simantics.interop/src/org/simantics/interop/test/GraphComparator.java b/org.simantics.interop/src/org/simantics/interop/test/GraphComparator.java index 0f61e5d..aa2ddee 100644 --- a/org.simantics.interop/src/org/simantics/interop/test/GraphComparator.java +++ b/org.simantics.interop/src/org/simantics/interop/test/GraphComparator.java @@ -1,1243 +1,1258 @@ -/******************************************************************************* - * Copyright (c) 2007, 2010 Association for Decentralized Information Management - * in Industry THTH ry. - * All rights reserved. This program and the accompanying materials - * are made available under the terms of the Eclipse Public License v1.0 - * which accompanies this distribution, and is available at - * http://www.eclipse.org/legal/epl-v10.html - * - * Contributors: - * Foster Wheeler Energia Oy - initial API and implementation - *******************************************************************************/ -package org.simantics.interop.test; - -import java.util.ArrayList; -import java.util.Arrays; -import java.util.Collection; -import java.util.Collections; -import java.util.Comparator; -import java.util.HashMap; -import java.util.HashSet; -import java.util.List; -import java.util.Map; -import java.util.Set; -import java.util.Stack; - -import org.simantics.db.ReadGraph; -import org.simantics.db.Resource; -import org.simantics.db.Session; -import org.simantics.db.Statement; -import org.simantics.db.common.request.ReadRequest; -import org.simantics.db.common.utils.NameUtils; -import org.simantics.db.exception.DatabaseException; -import org.simantics.layer0.Layer0; -import org.simantics.utils.datastructures.BijectionMap; -import org.simantics.utils.datastructures.MapList; -import org.simantics.utils.datastructures.Pair; - -/** - * Compares two subgraphs and reports differences. - * - * Assumes that subgraphs (defined using traverse relations) are not cyclic. - * - * Assumes that properties can be used to identify objects, if relation type is not enough. - * - * - * - * @author Marko Luukkainen - * - */ -public class GraphComparator { - - private static final boolean DEBUG = false; - - private Resource r1; - private Resource r2; - private Set strong = new HashSet(); // List of relations that identify object, if subject is already identified. - private List traversed = new ArrayList(); // list of relations that are traversed (and tested) - private List tested = new ArrayList(); // list of relations that are tested, but not traversed - private List nonTraversed = new ArrayList(); // list of relations that are not traversed - private List nonTested = new ArrayList(); // list of relations that are not tested - - private List changes1 = new ArrayList(); - private List changes2 = new ArrayList(); - private List> modifications = new ArrayList>(); - private Set changes1Set = new HashSet(); - private Set changes2Set = new HashSet(); - private Set> modificationsSet = new HashSet>(); - - private BijectionMap comparableStatements = new BijectionMap(); - private BijectionMap comparableResources = new BijectionMap(); - private Set processedResources = new HashSet(); - - private ResourceComparator comparator; - - private Comparator scomp = new PredicateComparator(); - private Comparator rcomp = new ResComparator(); - - // runtime attributes - - private ReadGraph g; - private Layer0 b; - - public GraphComparator(Resource r1, Resource r2) { - this.r1 = r1; - this.r2 = r2; - comparator = new TypeComparator(); - } - - public GraphComparator(Resource r1, Resource r2, ResourceComparator comparator) { - this.r1 = r1; - this.r2 = r2; - this.comparator = comparator; - } - - ArrayList ss1 = new ArrayList(); - ArrayList ss2 = new ArrayList(); - - - public Comparator getResourceComparator() { - return rcomp; - } - - public Comparator getStatementComparator() { - return scomp; - } - - public Resource getR1() { - return r1; - } - - public Resource getR2() { - return r2; - } - - public void addTraversed(Resource rel) { - traversed.add(rel); - } - - public void addTraversed(Collection rels) { - traversed.addAll(rels); - } - - public void addNonTraversed(Resource rel) { - nonTraversed.add(rel); - } - - public void addNonTraversed(Collection rels) { - nonTraversed.addAll(rels); - } - - public void addTested(Resource rel) { - tested.add(rel); - } - - public void addTested(Collection rels) { - tested.addAll(rels); - } - - public void addNonTested(Resource rel) { - nonTested.add(rel); - } - - public void addNonTested(Collection rels) { - nonTested.addAll(rels); - } - - public void addComparableResources(Resource r1, Resource r2) { - comparableResources.map(r1, r2); - } - - public void addComparableResources(BijectionMap matching) { - comparableResources.addAll(matching); - } - - public void addStrong(Resource r) { - strong.add(r); - } - - public void addStrong(Collection rels) { - strong.addAll(rels); - } - - - public void test(ReadGraph g) throws DatabaseException { - this.g = g; - this.b = Layer0.getInstance(g); - comparator.setComparator(this); - - Stack objectsLeft = new Stack(); - Stack objectsRight = new Stack(); - objectsLeft.push(r1); - objectsRight.push(r2); - - Set unreliableLeft = new HashSet(); - Set unreliableRight = new HashSet(); - - while (true) { - if (objectsLeft.isEmpty()) - break; - - - // process compares objects that are identified and searches for more resources to process. - process(objectsLeft, objectsRight, unreliableLeft, unreliableRight); - // process unreliable handles cases where unidentified statements subject and object have been identified - processUnreliable(unreliableLeft, unreliableRight); - // process unreliable handles cases where unidentified resources have path of length one to identified resource - processUnreliable(unreliableLeft, unreliableRight,objectsLeft,objectsRight); - if (objectsLeft.isEmpty() && unreliableLeft.size() > 0 && unreliableRight.size() > 0) { - // comparison is ending, but we have still unprocessed unidentified resources left. - // These cases have longer path than one to identified objects. - processUnreliableDeep(unreliableLeft, unreliableRight, objectsLeft, objectsRight); - } - - } - for (Statement s : unreliableLeft) { - if (!comparableStatements.containsLeft(s)) - addDeletion(s); - } - for (Statement s : unreliableRight) { - if (!comparableStatements.containsRight(s)) - addAddition(s); - } - - - } - - public void test(Session session) throws DatabaseException { - test(session, r1, r2); - } - - public void test(Session session, Resource r1, Resource r2) throws DatabaseException { - - comparator.setComparator(this); - - addComparable(r1, r2, false); - - final Stack objectsLeft = new Stack(); - final Stack objectsRight = new Stack(); - objectsLeft.push(r1); - objectsRight.push(r2); - - final Set unreliableLeft = new HashSet(); - final Set unreliableRight = new HashSet(); - - while (true) { - if (objectsLeft.isEmpty()) - break; - session.syncRequest(new ReadRequest() { - - @Override - public void run(ReadGraph graph) throws DatabaseException { - g = graph; - b = Layer0.getInstance(graph); - // process compares objects that are identified and searches for more resources to process. - process(objectsLeft, objectsRight, unreliableLeft, unreliableRight); - // process unreliable handles cases where unidentified statements subject and object have been identified - processUnreliable(unreliableLeft, unreliableRight); - // process unreliable handles cases where unidentified resources have path of length one to identified resource - processUnreliable(unreliableLeft, unreliableRight,objectsLeft,objectsRight); - if (objectsLeft.isEmpty() && unreliableLeft.size() > 0 && unreliableRight.size() > 0) { - // comparison is ending, but we have still unprocessed unidentified resources left. - // These cases have longer path than one to identified objects. - processUnreliableDeep(unreliableLeft, unreliableRight, objectsLeft, objectsRight); - } - } - }); - - - - } - for (Statement s : unreliableLeft) { - if (!comparableStatements.containsLeft(s)) - addDeletion(s); - } - for (Statement s : unreliableRight) { - if (!comparableStatements.containsRight(s)) - addAddition(s); - } - - - } - - private void process(Stack objectsLeft, Stack objectsRight, Set unreliableLeft, Set unreliableRight) throws DatabaseException { - List ss1 = new ArrayList(); - List ss2 = new ArrayList(); - - while (!objectsLeft.isEmpty()) { - Resource r1 = objectsLeft.pop(); - Resource r2 = objectsRight.pop(); - - if (r1.equals(r2)) - continue; - - if (processedResources.contains(r1)) - continue; - processedResources.add(r1); - - - if((comparableResources.containsLeft(r1)||comparableResources.containsRight(r2)) && !comparableResources.contains(r1, r2)) { - throw new DatabaseException("Comparator error: Trying to map " + r1 + " to " + r2 + " while mappings " + r1 + " to " + comparableResources.getRight(r1) + " and " + comparableResources.getLeft(r2) + " to " + r2 + " exist."); - } - addComparable(r1, r2, false); - - //System.out.println("test " + NameUtils.getSafeName(g, r1) + " " + NameUtils.getSafeName(g, r2)); - compareProps(r1, r2); - - for (Resource rel : tested) { - ss1.addAll(g.getStatements(r1, rel)); - ss2.addAll(g.getStatements(r2, rel)); - ss1 = filterAsserted(r1, ss1); - ss2 = filterAsserted(r2, ss2); - ss1 = filterTraversed(ss1); - ss2 = filterTraversed(ss2); - ss1 = filterNonTested(ss1); - ss2 = filterNonTested(ss2); - - - compareStatements(ss1, ss2, null, null,null,null); - ss1.clear(); - ss2.clear(); - } - - for (Resource rel : traversed) { - ss1.addAll(g.getStatements(r1, rel)); - ss2.addAll(g.getStatements(r2, rel)); - ss1 = filterAsserted(r1, ss1); - ss2 = filterAsserted(r2, ss2); - ss1 = filterNonTraversed(ss1); - ss2 = filterNonTraversed(ss2); - compareStatements(ss1, ss2, objectsLeft, objectsRight,unreliableLeft,unreliableRight); - ss1.clear(); - ss2.clear(); - - } - } - } - - private void processUnreliable(Set unreliableLeft, Set unreliableRight) throws DatabaseException { - MapList subjectLeft = new MapList(); - MapList subjectRight = new MapList(); - MapList objectLeft = new MapList(); - MapList objectRight = new MapList(); - - for (Statement s : unreliableLeft) { - subjectLeft.add(s.getSubject(),s); - objectLeft.add(s.getObject(),s); - } - for (Statement s : unreliableRight) { - subjectRight.add(s.getSubject(),s); - objectRight.add(s.getObject(),s); - } - - for (Resource left : subjectLeft.getKeys()) { - if (!comparableResources.containsLeft(left)) - continue; - Resource right = comparableResources.getRight(left); - for (Statement leftS : subjectLeft.getValues(left)) { - Resource leftO = leftS.getObject(); - if (!comparableResources.containsLeft(leftO)) - continue; - if (!unreliableLeft.contains(leftS)) - continue; - Resource rightO = comparableResources.getRight(leftO); - for (Statement rightS : subjectRight.getValues(right)) { - if (!rightS.getObject().equals(rightO)) - continue; - if (!unreliableRight.contains(rightS)) - continue; - if (leftS.getPredicate().equals(rightS.getPredicate()) || - comparableResources.contains(leftS.getPredicate(), rightS.getPredicate())) { - unreliableLeft.remove(leftS); - unreliableRight.remove(rightS); - addComparable(leftS, rightS, false); - } - } - } - } - } - - private void processUnreliable(Set unreliableLeft, Set unreliableRight, Stack objectsLeft, Stack objectsRight) throws DatabaseException { - MapList subjectLeft = new MapList(); - MapList subjectRight = new MapList(); - MapList objectLeft = new MapList(); - MapList objectRight = new MapList(); - - for (Statement s : unreliableLeft) { - subjectLeft.add(s.getSubject(),s); - objectLeft.add(s.getObject(),s); - } - for (Statement s : unreliableRight) { - subjectRight.add(s.getSubject(),s); - objectRight.add(s.getObject(),s); - } - - for (Resource ol : objectLeft.getKeys()) { - // all statements to the left side object - List left = objectLeft.getValues(ol); - // all subjects that have statements to the left side object (ol) - Set sLeft = new HashSet(); - // all matching subjects on the right side - Set sRight = new HashSet(); - for (Statement s : left) { - sLeft.add(s.getSubject()); - sRight.add(comparableResources.getRight(s.getSubject())); - } - - // check if object left can be reliably identified by available statements - // if there are any objects on the left side with similar statements, object left cannot be mapped. - boolean hasSimilar = false; - MapList comparableOLeft = new MapList(); - for (Resource sl : sLeft) { - for (Statement s : subjectLeft.getValues(sl)) { - if (!s.getObject().equals(ol)) { - comparableOLeft.add(s.getObject(),s); - } - } - } - - for (Resource similarOl : comparableOLeft.getKeys()) { - List similarLeft = comparableOLeft.getValues(similarOl); - if (similarLeft.size() == left.size()) { - boolean useL[] = new boolean[left.size()]; - boolean useSL[] = new boolean[left.size()]; - for (int i = 0; i < left.size(); i++) { - useL[i] = false; - useSL[i] = false; - } - for (int i = 0; i < left.size(); i++) { - for (int j = 0; j < left.size(); j++) { - if (useSL[j]) - continue; - Resource pl = left.get(i).getPredicate(); - Resource psl = similarLeft.get(j).getPredicate(); - if (pl.equals(psl)) { - useL[i] = true; - useSL[j] = true; - break; - } - } - } - boolean diff = false; - for (int i = 0; i < left.size(); i++) { - if (!useL[i] || !useSL[i]) { - diff = true; - } - } - if (!diff) { - hasSimilar = true; - break; - } - } - } - - if (hasSimilar) - continue; - - - // all objects that subjects on the right side point to. Object left has its matching resource among these, if it has matching resource - MapList possibleOR = new MapList(); - for (Resource sr : sRight) { - for (Statement s : subjectRight.getValues(sr)) - possibleOR.add(s.getObject(),s); - } - - // filter possible right side objects to those that have same amount of statements as the left side object - for (Resource or : possibleOR.getKeys().toArray(new Resource[possibleOR.getKeys().size()])) { - List right = possibleOR.getValues(or); - if (right.size() != left.size()) - possibleOR.remove(or); - - } - - // check for matching statements (comparable subjects, matching predicates) - MapList matchingOR = new MapList(); // list of objects that have matching statements - Map> matchingStatements = new HashMap>(); // matching statements - for (Resource or : possibleOR.getKeys()) { - List right = possibleOR.getValues(or); - int iLeft[] = new int[left.size()]; - int iRight[] = new int[right.size()]; - - for (int i = 0; i < left.size(); i++) { - iLeft[i] = -1; - iRight[i] = -1; - } - - for (int l = 0; l < left.size(); l++) { - Statement ls = left.get(l); - for (int r = 0; r < right.size(); r++) { - if (iRight[r] >= 0) - continue; - Statement rs = right.get(r); - if (!comparableResources.contains(ls.getSubject(), rs.getSubject())) - continue; - if (rcomp.compare(ls.getPredicate(),rs.getPredicate()) == 0) { - iLeft[l] = r; - iRight[r] = l; - break; - } - } - - } - boolean success = true; - for (int i = 0; i < left.size(); i++) { - if (iLeft[i] < 0) { - success = false; - break; - } - if (iRight[i] < 0) { - success = false; - break; - } - - } - if (success) { - for (Statement s : right) - matchingOR.add(or,s); - matchingStatements.put(or, new Pair(iLeft, iRight)); - } - } - // if there is only one matching right side object, we have found a match - if (matchingOR.getKeySize() == 1) { - Resource or = matchingOR.getKeys().iterator().next(); - List right = matchingOR.getValues(or); - Pair indices = matchingStatements.get(or); - - objectsLeft.add(ol); - objectsRight.add(or); - addComparable(ol, or, false); - for (int l = 0; l < left.size(); l++) { - int r = indices.first[l]; - Statement sl = left.get(l); - Statement sr = right.get(r); - addComparable(sl, sr, true); - unreliableLeft.remove(sl); - unreliableRight.remove(sr); - } - - } - - } - - - } - - private void processUnreliableDeep(Set unreliableLeft, Set unreliableRight, Stack objectsLeft, Stack objectsRight) throws DatabaseException { - MapList subjectLeft = new MapList(); - MapList subjectRight = new MapList(); - MapList objectLeft = new MapList(); - MapList objectRight = new MapList(); - - for (Statement s : unreliableLeft) { - subjectLeft.add(s.getSubject(),s); - objectLeft.add(s.getObject(),s); - } - for (Statement s : unreliableRight) { - subjectRight.add(s.getSubject(),s); - objectRight.add(s.getObject(),s); - } - for (Resource ol : objectLeft.getKeys()) { - Set pathsLeft = new HashSet(); - for (Resource rel : traversed) { - pathsLeft.addAll(Path.create(g.getStatements(ol, rel))); - } - while (true) { - expand(pathsLeft); - if (pathsLeft.size() == 0) - break; - Collection endPaths = new ArrayList(1); - for (Path p : pathsLeft) { - if (comparableResources.containsLeft(p.getEnd())) { - endPaths.add(p); - } - } - if (endPaths.size() > 0) { - pathsLeft.clear(); - pathsLeft.addAll(endPaths); - break; - } - } - if (pathsLeft.size() > 0) { - Resource sl = objectLeft.getValues(ol).get(0).getSubject(); - Resource sr = comparableResources.getRight(sl); - Collection possibleOR = new ArrayList(); - for (Statement s : subjectRight.getValues(sr)) { - possibleOR.add(s.getObject()); - } - Map> matchingPaths = new HashMap>(); - for (Resource or : possibleOR) { - Set possiblePathsRight = new HashSet(); - for (Path leftPath : pathsLeft) { - possiblePathsRight.addAll(findComparableRight(leftPath, or)); - } - if (hasMatchingPaths(pathsLeft, possiblePathsRight)) { - matchingPaths.put(or, possiblePathsRight); - } - } - if (matchingPaths.size() > 0) { - if (matchingPaths.size() == 1) { - Resource or = matchingPaths.keySet().iterator().next(); - - objectsLeft.add(ol); - objectsRight.add(or); - addComparable(ol, or, false); - Collection statementsLeft = objectLeft.getValues(ol); - Collection statementsRight = objectRight.getValues(or); - unreliableLeft.removeAll(statementsLeft); - unreliableRight.removeAll(statementsRight); - BijectionMap map = getMatchingPaths(pathsLeft, matchingPaths.get(or)); - for (Path left : map.getLeftSet()) { - Path right = map.getRight(left); - for (int i = 0; i < left.getLength(); i++) { - addComparable(left.getStatements().get(i),right.getStatements().get(i),false); - } - } - } - } - } - - } - - } - - private boolean hasMatchingPaths(Set leftPaths, Set rightPaths) { - if (leftPaths.size() != rightPaths.size()) - return false; - BijectionMap map = getMatchingPaths(leftPaths, rightPaths); - return map.size() == leftPaths.size(); - } - - private BijectionMap getMatchingPaths(Set leftPaths, Set rightPaths) { - BijectionMap map = new BijectionMap(); - for (Path leftPath : leftPaths) { - for (Path rightPath : rightPaths) { - if (map.containsRight(rightPath)) - continue; - if (leftPath.getLength() != rightPath.getLength()) - continue; - if (comparableResources.contains(leftPath.getEnd(), rightPath.getEnd())) { - map.map(leftPath, rightPath); - break; - } - } - } - return map; - } - - private void expand(Set paths) throws DatabaseException { - Set stepPathsLeft = new HashSet(); - if (paths.size() == 0) - return; - int length = paths.iterator().next().getLength() + 1; - for (Path p : paths) { - for (Resource rel : traversed) { - stepPathsLeft.addAll(Path.expand(p,g.getStatements(p.getEnd(), rel))); - } - } - paths.clear(); - for (Path p : stepPathsLeft) { - if (p.getLength() == length) - paths.add(p); - } - } - - private Collection findComparableRight(Path leftPath, Resource beginRight) throws DatabaseException { - Set rightPaths = new HashSet(); - rightPaths.addAll(Path.create(g.getStatements(beginRight, getRight(leftPath.getStatements().get(0).getPredicate())))); - for (int i = 1; i < leftPath.getLength(); i++) { - if (rightPaths.size() == 0) - return rightPaths; - Set stepPaths = new HashSet(); - for (Path p : rightPaths) { - stepPaths.addAll(Path.expand(p, g.getStatements(p.getEnd(), getRight(leftPath.getStatements().get(i).getPredicate())))); - } - rightPaths.clear(); - for (Path p : stepPaths) - if (p.getLength() == i+1) - rightPaths.add(p); - } - return rightPaths; - - } - - private Resource getRight(Resource r) { - if (comparableResources.containsLeft(r)) - return comparableResources.getRight(r); - return r; - } - - - - public BijectionMap getComparableStatements() { - return comparableStatements; - } - - public BijectionMap getComparableResources() { - return comparableResources; - } - - public GraphChanges getChanges() { - return new GraphChanges(r1,r2,changes1,changes2,modifications,comparableResources); - } - - private void addComparable(Statement left, Statement right, boolean process) throws DatabaseException { - addComparable(left.getObject(), right.getObject(), process); - comparableStatements.map(left, right); - //comparableResources.map(left.getObject(), right.getObject()); - } - - private void addComparable(Resource left, Resource right, boolean process) throws DatabaseException { - if(!comparableResources.contains(left, right)) { - if (comparableResources.containsLeft(left)||comparableResources.containsRight(right)) { - throw new DatabaseException("Comparator error: Trying to map " + left + " to " + right + " while mappings " + left + " to " + comparableResources.getRight(left) + " and " + comparableResources.getLeft(right) + " to " + right + " exist."); - } else { - if (DEBUG) System.out.println(left + " = " + right); - comparableResources.map(left, right); - } - } - - } - - public List filterAsserted(Resource r, Collection in) throws DatabaseException { - List out = new ArrayList(); - for (Statement s : in) { - if (!s.isAsserted(r)) - out.add(s); - - } - return out; - } - - - - private String printStatement(ReadGraph graph, Statement s) throws DatabaseException { - return NameUtils.getSafeName(graph, s.getSubject()) + " " + NameUtils.getSafeName(graph, s.getPredicate()) + " " + NameUtils.getSafeName(graph, s.getObject()); - } - - private List filterTraversed(List in) throws DatabaseException { - return filter(traversed, in); - } - - private List filterNonTested(List in) throws DatabaseException { - return filter(nonTested, in); - } - - private List filterNonTraversed(List in) throws DatabaseException { - return filter(nonTraversed, in); - } - - private List filter(Collection toFilter, List in) throws DatabaseException { - if (toFilter.size() == 0) - return in; - List out = new ArrayList(); - for (Statement s : in) { - boolean usable = true; - for (Resource r : toFilter) { - if (g.isSubrelationOf(s.getPredicate(),r)) { - usable = false; - break; - } - } - if (usable) { - out.add(s); - } - - } - return out; - } - - - private void addDeletion(Statement s) { - if (!changes1Set.contains(s)) { - changes1Set.add(s); - changes1.add(s); - } - } - - private void addAddition(Statement s) { - if (!changes2Set.contains(s)) { - changes2Set.add(s); - changes2.add(s); - } - } - - private void addModification(Statement s1, Statement s2) { - Pair mod = new Pair(s1,s2); - if (!modificationsSet.contains(mod)) { - modificationsSet.add(mod); - modifications.add(mod); - } - } - - public void sortStatement(List list1, List list2) { - sortStatement(list1, list2, scomp); - } - - public void sortStatement(List list1, List list2, Comparator scomp) { - Collections.sort(list1,scomp); - Collections.sort(list2,scomp); - - List sorted1 = new ArrayList(list1.size()); - List sorted2 = new ArrayList(list2.size()); - sorted1.addAll(list1); - sorted2.addAll(list2); - - int ss1 = 0; - int ss2 = 0; - for (int i = 0; i < list1.size(); ) { - Statement s1 = list1.get(i); - int same1 = sameRel(list1, i); - for (int j = 0; j < list2.size(); j++) { - Statement s2 = list2.get(j); - if (scomp.compare(s1, s2) == 0) { - int same2 = sameRel(list2, j); - copy(sorted1,ss1,list1,i,same1); - ss1 += same1; - copy(sorted2,ss2,list2,j,same2); - ss2 += same2; - break; - } - } - i+= same1; - } - if (ss1 < sorted1.size()) { - for (Statement s : list1) { - if (!sorted1.contains(s)) { - sorted1.set(ss1,s); - ss1++; - } - } - } - if (ss2 < sorted2.size()) { - for (Statement s : list2) { - if (!sorted2.contains(s)) { - sorted2.set(ss2,s); - ss2++; - } - } - } - - list1.clear(); - list2.clear(); - list1.addAll(sorted1); - list2.addAll(sorted2); - } - - public void copy(List to, int toIndex, List from, int fromIndex, int amount) { - for (int i = 0; i < amount; i++) { - to.set(toIndex + i, from.get(fromIndex+ i)); - } - } - - public void sortResource(List list1, List list2) { - Collections.sort(list1,rcomp); - int js = 0; - for (int i = 0; i < list1.size(); i++) { - Resource s1 = list1.get(i); - for (int j = js; j < list2.size(); j++) { - Resource s2 = list2.get(j); - if (rcomp.compare(s1, s2) == 0) { - Resource t = list2.get(js); - list2.set(js, s2); - list2.set(j, t); - break; - } - } - js++; - } - } - - private void compareStatements(List ss1, List ss2, Stack objectsLeft, Stack objectsRight, Collection unreliableLeft, Collection unreliableRight) throws DatabaseException { - sortStatement(ss1, ss2); - - int i1 = 0; - int i2 = 0; - - while (true) { - if (i1 >= ss1.size()) { - if (i2 >= ss2.size()) { - break; - } else { - while (i2 < ss2.size()) { - if (DEBUG) System.out.println("Compare Statements addition " + printStatement(g,ss2.get(i2))); - - addAddition(ss2.get(i2)); - i2++; - } - break; - } - } else if (i2 >= ss2.size()) { - while (i1 < ss1.size()) { - if (DEBUG) System.out.println("Compare Statements deletion " + printStatement(g,ss1.get(i1))); - addDeletion(ss1.get(i1)); - i1++; - } - break; - } - int same1 = sameRel(ss1, i1); - int same2 = sameRel(ss2, i2); - int c = rcomp.compare(ss1.get(i1).getPredicate(),ss2.get(i2).getPredicate()); - if (c == 0) { - compareStatements(ss1, i1, same1, ss2, i2, same2,objectsLeft,objectsRight,unreliableLeft,unreliableRight); - i1+=same1; - i2+=same2; - } else if (c < 0) { - for (int i = 0; i < same1; i++) { - if (DEBUG) System.out.println("Compare Statements deletion " + printStatement(g,ss1.get(i+i1))); - addDeletion(ss1.get(i+i1)); - } - i1 += same1; - } else { - for (int i = 0; i < same2; i++) { - if (DEBUG) System.out.println("Compare Statements addition " + printStatement(g,ss2.get(i+i2))); - addAddition(ss2.get(i+i2)); - } - - i2 += same2; - } - } - } - - - - private int sameRel(List statements, int off) { - if (statements.size() <= off) - return 0; - int same = 1; - long id = statements.get(off).getPredicate().getResourceId(); - for (int i = off+1; i ss1, int off1, int len1, List ss2, int off2, int len2, Collection objectsLeft, Collection objectsRight, Collection unreliableLeft, Collection unreliableRight) throws DatabaseException { - boolean[] used1 = new boolean[len1]; - for (int i = 0; i < used1.length; i++) { - used1[i] = false; - } - - boolean[] used2 = new boolean[len2]; - for (int i = 0; i < used2.length; i++) { - used2[i] = false; - } - - // left, right, difference - List> differences = new ArrayList>(); - for (int i1 = off1; i1 < off1 + len1; i1++) { - Statement s1 = ss1.get(i1); - List diff = new ArrayList(); - for (int i2 = off2; i2 < off2 + len2; i2++) { - Statement s2 = ss2.get(i2); - int d = compareObject(s1.getObject(), s2.getObject()); - if (d == 0) { - for (Resource t : strong) { - if (s1.getPredicate().equals(t) || g.isSubrelationOf(s1.getPredicate(), t)) { - d = 1; - break; - } - } - } - diff.add(d); - } - differences.add(diff); - } - // difference, left - MapList priorities = new MapList(); - for (int i = 0; i < differences.size(); i++) { - List list = differences.get(i); - for (int j = 0; j < list.size(); j++) { - priorities.add(list.get(j), i); - } - } - - Integer[] pris = priorities.getKeys(new Integer[]{}); - Arrays.sort(pris); - - for (Integer pri : pris) { - if (pri == Integer.MAX_VALUE) { - - } else if (pri == 0) { - - } else { - List i1s = priorities.getValues(pri); - for (Integer i1 : i1s) { - if (used1[i1]) - continue; - List i2diff = differences.get(i1); - for (int i2 = 0; i2 < i2diff.size(); i2++) { - if (i2diff.get(i2) == pri) { - if (used2[i2]) - continue; - used1[i1] = true; - used2[i2] = true; - Statement s1 = ss1.get(i1+off1); - Statement s2 = ss2.get(i2+off2); - - if (objectsLeft != null) { - objectsLeft.add(s1.getObject()); - objectsRight.add(s2.getObject()); - } - addComparable(s1, s2, true); - break; - } - } - } - } - } - - for (Integer pri : pris) { - if (pri != 0) - continue; - Set s1s = new HashSet(); - Set s2s = new HashSet(); - Set s1i = new HashSet(); - Set s2i = new HashSet(); - List i1s = priorities.getValues(pri); - for (Integer i1 : i1s) { - if (used1[i1]) - continue; - List i2diff = differences.get(i1); - for (int i2 = 0; i2 < i2diff.size(); i2++) { - if (i2diff.get(i2) == pri) { - if (used2[i2]) - continue; - Statement s1 = ss1.get(i1+off1); - Statement s2 = ss2.get(i2+off2); - s1s.add(s1); - s2s.add(s2); - s1i.add(i1); - s2i.add(i2); - } - } - } - if (unreliableLeft != null) { - unreliableLeft.addAll(s1s); - unreliableRight.addAll(s2s); - } - for (Integer i : s1i) - used1[i] = true; - for (Integer i : s2i) - used2[i] = true; - - } - for (int i1 = off1; i1 < off1 + len1; i1++) { - if (!used1[i1-off1]) { - if (DEBUG) System.out.println("Compare Object deletion " + printStatement(g,ss1.get(i1))); - addDeletion(ss1.get(i1)); - } - } - for (int i2 = off2; i2 < off2 + len2; i2++) { - if (!used2[i2-off2]) { - if (DEBUG) System.out.println("Compare Object addition " + printStatement(g,ss2.get(i2))); - addAddition(ss2.get(i2)); - } - } - } - - - - /** - * compares properties, assumes functional relations - * @param r1 - * @param r2 - * @throws ServiceException - * @throws DoesNotContainValueException - * @throws ValidationException - */ - private void compareProps(Resource r1, Resource r2) throws DatabaseException { - if (DEBUG) System.out.println("compareProps " + r1 + " " + NameUtils.getSafeName(g, r1) + " " + r2 + " " + NameUtils.getSafeName(g, r2)); - List ss1 = new ArrayList(); - List ss2 = new ArrayList(); - ss1.addAll(g.getStatements(r1, b.HasProperty)); - ss2.addAll(g.getStatements(r2, b.HasProperty)); - ss1 = filterNonTested(ss1); - ss2 = filterNonTested(ss2); - sortStatement(ss1, ss2); - - int i1 = 0; - int i2 = 0; - - while (true) { - if (i1 >= ss1.size()) { - if (i2 >= ss2.size()) - break; - else { - while (i2 < ss2.size()) { - if (DEBUG) System.out.println("Compare Prop diff2 " + printStatement(g,ss2.get(i2))); - addAddition(ss2.get(i2)); - i2++; - } - break; - } - } else if (i2 >= ss2.size()) { - while (i1 < ss1.size()) { - if (DEBUG) System.out.println("Compare Prop diff1 " + printStatement(g,ss1.get(i1))); - addDeletion(ss1.get(i1)); - i1++; - } - break; - } - Statement s1 = ss1.get(i1); - Statement s2 = ss2.get(i2); - if (s1.isAsserted(r1) && s2.isAsserted(r2)) { - i1++; - i2++; - continue; - } - int c = scomp.compare(s1, s2); - switch (c) { - case 0:{ - boolean b1 = g.hasValue(s1.getObject()); - boolean b2 = g.hasValue(s2.getObject()); - if (b1 == b2) { - if (b1) { - Object v1 = g.getValue(s1.getObject()); - Object v2 = g.getValue(s2.getObject()); - boolean eq = compareValue(v1, v2); - if (!eq) { - addModification(s1, s2); - addComparable(s1, s2, false); - } - } else { - if (!s1.getObject().equals(s1.getSubject()) && !s2.getObject().equals(s2.getSubject())) - compareProps(s1.getObject(), s2.getObject()); - } - } else { - addModification(s1, s2); - addComparable(s1, s2, false); - } - i1++; - i2++; - break; - } - case -1:{ - if (DEBUG) System.out.println("Compare Prop diff1s " + printStatement(g,s1)); - addDeletion(s1); - i1++; - break; - } - - case 1:{ - if (DEBUG) System.out.println("Compare Prop diff2s " + printStatement(g,s2)); - addAddition(s2); - i2++; - break; - } - } - - } - - ss1.clear(); - ss2.clear(); - - } - - public static boolean compareValue(Object v1, Object v2) { - if (v1 instanceof Object[] && v2 instanceof Object[]) - return Arrays.deepEquals((Object[])v1, (Object[])v2); - else if (v1 instanceof int[] && v2 instanceof int[]) - return Arrays.equals((int[])v1, (int[])v2); - else if (v1 instanceof float[] && v2 instanceof float[]) - return Arrays.equals((float[])v1, (float[])v2); - else if (v1 instanceof double[] && v2 instanceof double[]) - return Arrays.equals((double[])v1, (double[])v2); - else if (v1 instanceof long[] && v2 instanceof long[]) - return Arrays.equals((long[])v1, (long[])v2); - else if (v1 instanceof byte[] && v2 instanceof byte[]) - return Arrays.equals((byte[])v1, (byte[])v2); - else if (v1 instanceof boolean[] && v2 instanceof boolean[]) - return Arrays.equals((boolean[])v1, (boolean[])v2); - else - return v1.equals(v2); - } - - - public class PredicateComparator implements Comparator { - @Override - public int compare(Statement o1, Statement o2) { - if (comparableResources.contains(o1.getPredicate(), o2.getPredicate())) - return 0; - if (o1.getPredicate().getResourceId() < o2.getPredicate().getResourceId()) - return -1; - if (o1.getPredicate().getResourceId() > o2.getPredicate().getResourceId()) - return 1; - return 0; - } - } - - public class SubjectComparator implements Comparator { - @Override - public int compare(Statement o1, Statement o2) { - if (comparableResources.contains(o1.getSubject(), o2.getSubject())) - return 0; - if (o1.getSubject().getResourceId() < o2.getSubject().getResourceId()) - return -1; - if (o1.getSubject().getResourceId() > o2.getSubject().getResourceId()) - return 1; - return 0; - } - } - - public class ObjectComparator implements Comparator { - @Override - public int compare(Statement o1, Statement o2) { - if (comparableResources.contains(o1.getObject(), o2.getObject())) - return 0; - if (o1.getObject().getResourceId() < o2.getObject().getResourceId()) - return -1; - if (o1.getObject().getResourceId() > o2.getObject().getResourceId()) - return 1; - return 0; - } - } - - public static class FullStatementComparator implements Comparator { - @Override - public int compare(Statement o1, Statement o2) { - if (o1.getSubject().getResourceId() < o2.getSubject().getResourceId()) - return -1; - if (o1.getSubject().getResourceId() > o2.getSubject().getResourceId()) - return 1; - if (o1.getPredicate().getResourceId() < o2.getPredicate().getResourceId()) - return -1; - if (o1.getPredicate().getResourceId() > o2.getPredicate().getResourceId()) - return 1; - if (o1.getObject().getResourceId() < o2.getObject().getResourceId()) - return -1; - if (o1.getObject().getResourceId() > o2.getObject().getResourceId()) - return 1; - return 0; - } - } - - public class ResComparator implements Comparator { - @Override - public int compare(Resource o1, Resource o2) { - if (comparableResources.contains(o1, o2)) - return 0; - if (o1.getResourceId() < o2.getResourceId()) - return -1; - if (o1.getResourceId() > o2.getResourceId()) - return 1; - return 0; - } - } - -} +/******************************************************************************* + * Copyright (c) 2007, 2010 Association for Decentralized Information Management + * in Industry THTH ry. + * All rights reserved. This program and the accompanying materials + * are made available under the terms of the Eclipse Public License v1.0 + * which accompanies this distribution, and is available at + * http://www.eclipse.org/legal/epl-v10.html + * + * Contributors: + * Foster Wheeler Energia Oy - initial API and implementation + *******************************************************************************/ +package org.simantics.interop.test; + +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Collection; +import java.util.Collections; +import java.util.Comparator; +import java.util.HashMap; +import java.util.HashSet; +import java.util.List; +import java.util.Map; +import java.util.Set; +import java.util.Stack; + +import org.simantics.db.ReadGraph; +import org.simantics.db.Resource; +import org.simantics.db.Session; +import org.simantics.db.Statement; +import org.simantics.db.common.request.ReadRequest; +import org.simantics.db.common.utils.NameUtils; +import org.simantics.db.exception.DatabaseException; +import org.simantics.layer0.Layer0; +import org.simantics.utils.datastructures.BijectionMap; +import org.simantics.utils.datastructures.MapList; +import org.simantics.utils.datastructures.Pair; + +/** + * Compares two subgraphs and reports differences. + * + * Assumes that subgraphs (defined using traverse relations) are not cyclic. + * + * Assumes that properties can be used to identify objects, if relation type is not enough. + * + * + * + * @author Marko Luukkainen + * + */ +public class GraphComparator { + + private static final boolean DEBUG = false; + + private Resource r1; + private Resource r2; + private Set strong = new HashSet(); // List of relations that identify object, if subject is already identified. + private List traversed = new ArrayList(); // list of relations that are traversed (and tested) + private List tested = new ArrayList(); // list of relations that are tested, but not traversed + private List nonTraversed = new ArrayList(); // list of relations that are not traversed + private List nonTested = new ArrayList(); // list of relations that are not tested + + private List changes1 = new ArrayList(); + private List changes2 = new ArrayList(); + private List> modifications = new ArrayList>(); + private Set changes1Set = new HashSet(); + private Set changes2Set = new HashSet(); + private Set> modificationsSet = new HashSet>(); + + private BijectionMap comparableStatements = new BijectionMap(); + private BijectionMap comparableResources = new BijectionMap(); + + private Set processedResources = new HashSet(); + + private ResourceComparator comparator; + + private Comparator scomp = new PredicateComparator(); + private Comparator rcomp = new ResComparator(); + + private Set nonMatchedLeft = new HashSet(); + private Set nonMatchedRight = new HashSet(); + + // runtime attributes + + private ReadGraph g; + private Layer0 b; + + public GraphComparator(Resource r1, Resource r2) { + this.r1 = r1; + this.r2 = r2; + comparator = new TypeComparator(); + } + + public GraphComparator(Resource r1, Resource r2, ResourceComparator comparator) { + this.r1 = r1; + this.r2 = r2; + this.comparator = comparator; + } + + ArrayList ss1 = new ArrayList(); + ArrayList ss2 = new ArrayList(); + + + public Comparator getResourceComparator() { + return rcomp; + } + + public Comparator getStatementComparator() { + return scomp; + } + + public Resource getR1() { + return r1; + } + + public Resource getR2() { + return r2; + } + + public void addTraversed(Resource rel) { + traversed.add(rel); + } + + public void addTraversed(Collection rels) { + traversed.addAll(rels); + } + + public void addNonTraversed(Resource rel) { + nonTraversed.add(rel); + } + + public void addNonTraversed(Collection rels) { + nonTraversed.addAll(rels); + } + + public void addTested(Resource rel) { + tested.add(rel); + } + + public void addTested(Collection rels) { + tested.addAll(rels); + } + + public void addNonTested(Resource rel) { + nonTested.add(rel); + } + + public void addNonTested(Collection rels) { + nonTested.addAll(rels); + } + + public void addComparableResources(Resource r1, Resource r2) { + comparableResources.map(r1, r2); + } + + public void addComparableResources(BijectionMap matching) { + comparableResources.addAll(matching); + } + + public void addStrong(Resource r) { + strong.add(r); + } + + public void addStrong(Collection rels) { + strong.addAll(rels); + } + + public void addNonMatchedLeft(Resource r) { + nonMatchedLeft.add(r); + } + + public void addNonMatchedRight(Resource r) { + nonMatchedRight.add(r); + } + + public void test(ReadGraph g) throws DatabaseException { + this.g = g; + this.b = Layer0.getInstance(g); + comparator.setComparator(this); + + Stack objectsLeft = new Stack(); + Stack objectsRight = new Stack(); + objectsLeft.push(r1); + objectsRight.push(r2); + + Set unreliableLeft = new HashSet(); + Set unreliableRight = new HashSet(); + + while (true) { + if (objectsLeft.isEmpty()) + break; + + + // process compares objects that are identified and searches for more resources to process. + process(objectsLeft, objectsRight, unreliableLeft, unreliableRight); + // process unreliable handles cases where unidentified statements subject and object have been identified + processUnreliable(unreliableLeft, unreliableRight); + // process unreliable handles cases where unidentified resources have path of length one to identified resource + processUnreliable(unreliableLeft, unreliableRight,objectsLeft,objectsRight); + if (objectsLeft.isEmpty() && unreliableLeft.size() > 0 && unreliableRight.size() > 0) { + // comparison is ending, but we have still unprocessed unidentified resources left. + // These cases have longer path than one to identified objects. + processUnreliableDeep(unreliableLeft, unreliableRight, objectsLeft, objectsRight); + } + + } + for (Statement s : unreliableLeft) { + if (!comparableStatements.containsLeft(s)) + addDeletion(s); + } + for (Statement s : unreliableRight) { + if (!comparableStatements.containsRight(s)) + addAddition(s); + } + + + } + + public void test(Session session) throws DatabaseException { + test(session, r1, r2); + } + + public void test(Session session, Resource r1, Resource r2) throws DatabaseException { + + comparator.setComparator(this); + + addComparable(r1, r2, false); + + final Stack objectsLeft = new Stack(); + final Stack objectsRight = new Stack(); + objectsLeft.push(r1); + objectsRight.push(r2); + + final Set unreliableLeft = new HashSet(); + final Set unreliableRight = new HashSet(); + + while (true) { + if (objectsLeft.isEmpty()) + break; + session.syncRequest(new ReadRequest() { + + @Override + public void run(ReadGraph graph) throws DatabaseException { + g = graph; + b = Layer0.getInstance(graph); + // process compares objects that are identified and searches for more resources to process. + process(objectsLeft, objectsRight, unreliableLeft, unreliableRight); + // process unreliable handles cases where unidentified statements subject and object have been identified + processUnreliable(unreliableLeft, unreliableRight); + // process unreliable handles cases where unidentified resources have path of length one to identified resource + processUnreliable(unreliableLeft, unreliableRight,objectsLeft,objectsRight); + if (objectsLeft.isEmpty() && unreliableLeft.size() > 0 && unreliableRight.size() > 0) { + // comparison is ending, but we have still unprocessed unidentified resources left. + // These cases have longer path than one to identified objects. + processUnreliableDeep(unreliableLeft, unreliableRight, objectsLeft, objectsRight); + } + } + }); + + + + } + for (Statement s : unreliableLeft) { + if (!comparableStatements.containsLeft(s)) + addDeletion(s); + } + for (Statement s : unreliableRight) { + if (!comparableStatements.containsRight(s)) + addAddition(s); + } + + + } + + private void process(Stack objectsLeft, Stack objectsRight, Set unreliableLeft, Set unreliableRight) throws DatabaseException { + List ss1 = new ArrayList(); + List ss2 = new ArrayList(); + + while (!objectsLeft.isEmpty()) { + Resource r1 = objectsLeft.pop(); + Resource r2 = objectsRight.pop(); + + if (r1.equals(r2)) + continue; + + if (processedResources.contains(r1)) + continue; + processedResources.add(r1); + + + if((comparableResources.containsLeft(r1)||comparableResources.containsRight(r2)) && !comparableResources.contains(r1, r2)) { + throw new DatabaseException("Comparator error: Trying to map " + r1 + " to " + r2 + " while mappings " + r1 + " to " + comparableResources.getRight(r1) + " and " + comparableResources.getLeft(r2) + " to " + r2 + " exist."); + } + addComparable(r1, r2, false); + + //System.out.println("test " + NameUtils.getSafeName(g, r1) + " " + NameUtils.getSafeName(g, r2)); + compareProps(r1, r2); + + for (Resource rel : tested) { + ss1.addAll(g.getStatements(r1, rel)); + ss2.addAll(g.getStatements(r2, rel)); + ss1 = filterAsserted(r1, ss1); + ss2 = filterAsserted(r2, ss2); + ss1 = filterTraversed(ss1); + ss2 = filterTraversed(ss2); + ss1 = filterNonTested(ss1); + ss2 = filterNonTested(ss2); + + + compareStatements(ss1, ss2, null, null,null,null); + ss1.clear(); + ss2.clear(); + } + + for (Resource rel : traversed) { + ss1.addAll(g.getStatements(r1, rel)); + ss2.addAll(g.getStatements(r2, rel)); + ss1 = filterAsserted(r1, ss1); + ss2 = filterAsserted(r2, ss2); + ss1 = filterNonTraversed(ss1); + ss2 = filterNonTraversed(ss2); + compareStatements(ss1, ss2, objectsLeft, objectsRight,unreliableLeft,unreliableRight); + ss1.clear(); + ss2.clear(); + + } + } + } + + private void processUnreliable(Set unreliableLeft, Set unreliableRight) throws DatabaseException { + MapList subjectLeft = new MapList(); + MapList subjectRight = new MapList(); + MapList objectLeft = new MapList(); + MapList objectRight = new MapList(); + + for (Statement s : unreliableLeft) { + subjectLeft.add(s.getSubject(),s); + objectLeft.add(s.getObject(),s); + } + for (Statement s : unreliableRight) { + subjectRight.add(s.getSubject(),s); + objectRight.add(s.getObject(),s); + } + + for (Resource left : subjectLeft.getKeys()) { + if (!comparableResources.containsLeft(left)) + continue; + Resource right = comparableResources.getRight(left); + for (Statement leftS : subjectLeft.getValues(left)) { + Resource leftO = leftS.getObject(); + if (!comparableResources.containsLeft(leftO)) + continue; + if (!unreliableLeft.contains(leftS)) + continue; + Resource rightO = comparableResources.getRight(leftO); + for (Statement rightS : subjectRight.getValues(right)) { + if (!rightS.getObject().equals(rightO)) + continue; + if (!unreliableRight.contains(rightS)) + continue; + if (leftS.getPredicate().equals(rightS.getPredicate()) || + comparableResources.contains(leftS.getPredicate(), rightS.getPredicate())) { + unreliableLeft.remove(leftS); + unreliableRight.remove(rightS); + addComparable(leftS, rightS, false); + } + } + } + } + } + + private void processUnreliable(Set unreliableLeft, Set unreliableRight, Stack objectsLeft, Stack objectsRight) throws DatabaseException { + MapList subjectLeft = new MapList(); + MapList subjectRight = new MapList(); + MapList objectLeft = new MapList(); + MapList objectRight = new MapList(); + + for (Statement s : unreliableLeft) { + subjectLeft.add(s.getSubject(),s); + objectLeft.add(s.getObject(),s); + } + for (Statement s : unreliableRight) { + subjectRight.add(s.getSubject(),s); + objectRight.add(s.getObject(),s); + } + + for (Resource ol : objectLeft.getKeys()) { + // all statements to the left side object + List left = objectLeft.getValues(ol); + // all subjects that have statements to the left side object (ol) + Set sLeft = new HashSet(); + // all matching subjects on the right side + Set sRight = new HashSet(); + for (Statement s : left) { + sLeft.add(s.getSubject()); + sRight.add(comparableResources.getRight(s.getSubject())); + } + + // check if object left can be reliably identified by available statements + // if there are any objects on the left side with similar statements, object left cannot be mapped. + boolean hasSimilar = false; + MapList comparableOLeft = new MapList(); + for (Resource sl : sLeft) { + for (Statement s : subjectLeft.getValues(sl)) { + if (!s.getObject().equals(ol)) { + comparableOLeft.add(s.getObject(),s); + } + } + } + + for (Resource similarOl : comparableOLeft.getKeys()) { + List similarLeft = comparableOLeft.getValues(similarOl); + if (similarLeft.size() == left.size()) { + boolean useL[] = new boolean[left.size()]; + boolean useSL[] = new boolean[left.size()]; + for (int i = 0; i < left.size(); i++) { + useL[i] = false; + useSL[i] = false; + } + for (int i = 0; i < left.size(); i++) { + for (int j = 0; j < left.size(); j++) { + if (useSL[j]) + continue; + Resource pl = left.get(i).getPredicate(); + Resource psl = similarLeft.get(j).getPredicate(); + if (pl.equals(psl)) { + useL[i] = true; + useSL[j] = true; + break; + } + } + } + boolean diff = false; + for (int i = 0; i < left.size(); i++) { + if (!useL[i] || !useSL[i]) { + diff = true; + } + } + if (!diff) { + hasSimilar = true; + break; + } + } + } + + if (hasSimilar) + continue; + + + // all objects that subjects on the right side point to. Object left has its matching resource among these, if it has matching resource + MapList possibleOR = new MapList(); + for (Resource sr : sRight) { + for (Statement s : subjectRight.getValues(sr)) + possibleOR.add(s.getObject(),s); + } + + // filter possible right side objects to those that have same amount of statements as the left side object + for (Resource or : possibleOR.getKeys().toArray(new Resource[possibleOR.getKeys().size()])) { + List right = possibleOR.getValues(or); + if (right.size() != left.size()) + possibleOR.remove(or); + + } + + // check for matching statements (comparable subjects, matching predicates) + MapList matchingOR = new MapList(); // list of objects that have matching statements + Map> matchingStatements = new HashMap>(); // matching statements + for (Resource or : possibleOR.getKeys()) { + List right = possibleOR.getValues(or); + int iLeft[] = new int[left.size()]; + int iRight[] = new int[right.size()]; + + for (int i = 0; i < left.size(); i++) { + iLeft[i] = -1; + iRight[i] = -1; + } + + for (int l = 0; l < left.size(); l++) { + Statement ls = left.get(l); + for (int r = 0; r < right.size(); r++) { + if (iRight[r] >= 0) + continue; + Statement rs = right.get(r); + if (!comparableResources.contains(ls.getSubject(), rs.getSubject())) + continue; + if (rcomp.compare(ls.getPredicate(),rs.getPredicate()) == 0) { + iLeft[l] = r; + iRight[r] = l; + break; + } + } + + } + boolean success = true; + for (int i = 0; i < left.size(); i++) { + if (iLeft[i] < 0) { + success = false; + break; + } + if (iRight[i] < 0) { + success = false; + break; + } + + } + if (success) { + for (Statement s : right) + matchingOR.add(or,s); + matchingStatements.put(or, new Pair(iLeft, iRight)); + } + } + // if there is only one matching right side object, we have found a match + if (matchingOR.getKeySize() == 1) { + Resource or = matchingOR.getKeys().iterator().next(); + List right = matchingOR.getValues(or); + Pair indices = matchingStatements.get(or); + + objectsLeft.add(ol); + objectsRight.add(or); + addComparable(ol, or, false); + for (int l = 0; l < left.size(); l++) { + int r = indices.first[l]; + Statement sl = left.get(l); + Statement sr = right.get(r); + addComparable(sl, sr, true); + unreliableLeft.remove(sl); + unreliableRight.remove(sr); + } + + } + + } + + + } + + private void processUnreliableDeep(Set unreliableLeft, Set unreliableRight, Stack objectsLeft, Stack objectsRight) throws DatabaseException { + MapList subjectLeft = new MapList(); + MapList subjectRight = new MapList(); + MapList objectLeft = new MapList(); + MapList objectRight = new MapList(); + + for (Statement s : unreliableLeft) { + subjectLeft.add(s.getSubject(),s); + objectLeft.add(s.getObject(),s); + } + for (Statement s : unreliableRight) { + subjectRight.add(s.getSubject(),s); + objectRight.add(s.getObject(),s); + } + for (Resource ol : objectLeft.getKeys()) { + Set pathsLeft = new HashSet(); + for (Resource rel : traversed) { + pathsLeft.addAll(Path.create(g.getStatements(ol, rel))); + } + while (true) { + expand(pathsLeft); + if (pathsLeft.size() == 0) + break; + Collection endPaths = new ArrayList(1); + for (Path p : pathsLeft) { + if (comparableResources.containsLeft(p.getEnd())) { + endPaths.add(p); + } + } + if (endPaths.size() > 0) { + pathsLeft.clear(); + pathsLeft.addAll(endPaths); + break; + } + } + if (pathsLeft.size() > 0) { + Resource sl = objectLeft.getValues(ol).get(0).getSubject(); + Resource sr = comparableResources.getRight(sl); + Collection possibleOR = new ArrayList(); + for (Statement s : subjectRight.getValues(sr)) { + possibleOR.add(s.getObject()); + } + Map> matchingPaths = new HashMap>(); + for (Resource or : possibleOR) { + Set possiblePathsRight = new HashSet(); + for (Path leftPath : pathsLeft) { + possiblePathsRight.addAll(findComparableRight(leftPath, or)); + } + if (hasMatchingPaths(pathsLeft, possiblePathsRight)) { + matchingPaths.put(or, possiblePathsRight); + } + } + if (matchingPaths.size() > 0) { + if (matchingPaths.size() == 1) { + Resource or = matchingPaths.keySet().iterator().next(); + + objectsLeft.add(ol); + objectsRight.add(or); + addComparable(ol, or, false); + Collection statementsLeft = objectLeft.getValues(ol); + Collection statementsRight = objectRight.getValues(or); + unreliableLeft.removeAll(statementsLeft); + unreliableRight.removeAll(statementsRight); + BijectionMap map = getMatchingPaths(pathsLeft, matchingPaths.get(or)); + for (Path left : map.getLeftSet()) { + Path right = map.getRight(left); + for (int i = 0; i < left.getLength(); i++) { + addComparable(left.getStatements().get(i),right.getStatements().get(i),false); + } + } + } + } + } + + } + + } + + private boolean hasMatchingPaths(Set leftPaths, Set rightPaths) { + if (leftPaths.size() != rightPaths.size()) + return false; + BijectionMap map = getMatchingPaths(leftPaths, rightPaths); + return map.size() == leftPaths.size(); + } + + private BijectionMap getMatchingPaths(Set leftPaths, Set rightPaths) { + BijectionMap map = new BijectionMap(); + for (Path leftPath : leftPaths) { + for (Path rightPath : rightPaths) { + if (map.containsRight(rightPath)) + continue; + if (leftPath.getLength() != rightPath.getLength()) + continue; + if (comparableResources.contains(leftPath.getEnd(), rightPath.getEnd())) { + map.map(leftPath, rightPath); + break; + } + } + } + return map; + } + + private void expand(Set paths) throws DatabaseException { + Set stepPathsLeft = new HashSet(); + if (paths.size() == 0) + return; + int length = paths.iterator().next().getLength() + 1; + for (Path p : paths) { + for (Resource rel : traversed) { + stepPathsLeft.addAll(Path.expand(p,g.getStatements(p.getEnd(), rel))); + } + } + paths.clear(); + for (Path p : stepPathsLeft) { + if (p.getLength() == length) + paths.add(p); + } + } + + private Collection findComparableRight(Path leftPath, Resource beginRight) throws DatabaseException { + Set rightPaths = new HashSet(); + rightPaths.addAll(Path.create(g.getStatements(beginRight, getRight(leftPath.getStatements().get(0).getPredicate())))); + for (int i = 1; i < leftPath.getLength(); i++) { + if (rightPaths.size() == 0) + return rightPaths; + Set stepPaths = new HashSet(); + for (Path p : rightPaths) { + stepPaths.addAll(Path.expand(p, g.getStatements(p.getEnd(), getRight(leftPath.getStatements().get(i).getPredicate())))); + } + rightPaths.clear(); + for (Path p : stepPaths) + if (p.getLength() == i+1) + rightPaths.add(p); + } + return rightPaths; + + } + + private Resource getRight(Resource r) { + if (comparableResources.containsLeft(r)) + return comparableResources.getRight(r); + return r; + } + + + + public BijectionMap getComparableStatements() { + return comparableStatements; + } + + public BijectionMap getComparableResources() { + return comparableResources; + } + + public GraphChanges getChanges() { + return new GraphChanges(r1,r2,changes1,changes2,modifications,comparableResources); + } + + private void addComparable(Statement left, Statement right, boolean process) throws DatabaseException { + addComparable(left.getObject(), right.getObject(), process); + comparableStatements.map(left, right); + //comparableResources.map(left.getObject(), right.getObject()); + } + + private void addComparable(Resource left, Resource right, boolean process) throws DatabaseException { + if(!comparableResources.contains(left, right)) { + if (comparableResources.containsLeft(left)||comparableResources.containsRight(right)) { + throw new DatabaseException("Comparator error: Trying to map " + left + " to " + right + " while mappings " + left + " to " + comparableResources.getRight(left) + " and " + comparableResources.getLeft(right) + " to " + right + " exist."); + } else { + if (DEBUG) System.out.println(left + " = " + right); + comparableResources.map(left, right); + } + } + + } + + public List filterAsserted(Resource r, Collection in) throws DatabaseException { + List out = new ArrayList(); + for (Statement s : in) { + if (!s.isAsserted(r)) + out.add(s); + + } + return out; + } + + + + private String printStatement(ReadGraph graph, Statement s) throws DatabaseException { + return NameUtils.getSafeName(graph, s.getSubject()) + " " + NameUtils.getSafeName(graph, s.getPredicate()) + " " + NameUtils.getSafeName(graph, s.getObject()); + } + + private List filterTraversed(List in) throws DatabaseException { + return filter(traversed, in); + } + + private List filterNonTested(List in) throws DatabaseException { + return filter(nonTested, in); + } + + private List filterNonTraversed(List in) throws DatabaseException { + return filter(nonTraversed, in); + } + + private List filter(Collection toFilter, List in) throws DatabaseException { + if (toFilter.size() == 0) + return in; + List out = new ArrayList(); + for (Statement s : in) { + boolean usable = true; + for (Resource r : toFilter) { + if (g.isSubrelationOf(s.getPredicate(),r)) { + usable = false; + break; + } + } + if (usable) { + out.add(s); + } + + } + return out; + } + + + private void addDeletion(Statement s) { + if (!changes1Set.contains(s)) { + changes1Set.add(s); + changes1.add(s); + } + } + + private void addAddition(Statement s) { + if (!changes2Set.contains(s)) { + changes2Set.add(s); + changes2.add(s); + } + } + + private void addModification(Statement s1, Statement s2) { + Pair mod = new Pair(s1,s2); + if (!modificationsSet.contains(mod)) { + modificationsSet.add(mod); + modifications.add(mod); + } + } + + public void sortStatement(List list1, List list2) { + sortStatement(list1, list2, scomp); + } + + public void sortStatement(List list1, List list2, Comparator scomp) { + Collections.sort(list1,scomp); + Collections.sort(list2,scomp); + + List sorted1 = new ArrayList(list1.size()); + List sorted2 = new ArrayList(list2.size()); + sorted1.addAll(list1); + sorted2.addAll(list2); + + int ss1 = 0; + int ss2 = 0; + for (int i = 0; i < list1.size(); ) { + Statement s1 = list1.get(i); + int same1 = sameRel(list1, i); + for (int j = 0; j < list2.size(); j++) { + Statement s2 = list2.get(j); + if (scomp.compare(s1, s2) == 0) { + int same2 = sameRel(list2, j); + copy(sorted1,ss1,list1,i,same1); + ss1 += same1; + copy(sorted2,ss2,list2,j,same2); + ss2 += same2; + break; + } + } + i+= same1; + } + if (ss1 < sorted1.size()) { + for (Statement s : list1) { + if (!sorted1.contains(s)) { + sorted1.set(ss1,s); + ss1++; + } + } + } + if (ss2 < sorted2.size()) { + for (Statement s : list2) { + if (!sorted2.contains(s)) { + sorted2.set(ss2,s); + ss2++; + } + } + } + + list1.clear(); + list2.clear(); + list1.addAll(sorted1); + list2.addAll(sorted2); + } + + public void copy(List to, int toIndex, List from, int fromIndex, int amount) { + for (int i = 0; i < amount; i++) { + to.set(toIndex + i, from.get(fromIndex+ i)); + } + } + + public void sortResource(List list1, List list2) { + Collections.sort(list1,rcomp); + int js = 0; + for (int i = 0; i < list1.size(); i++) { + Resource s1 = list1.get(i); + for (int j = js; j < list2.size(); j++) { + Resource s2 = list2.get(j); + if (rcomp.compare(s1, s2) == 0) { + Resource t = list2.get(js); + list2.set(js, s2); + list2.set(j, t); + break; + } + } + js++; + } + } + + private void compareStatements(List ss1, List ss2, Stack objectsLeft, Stack objectsRight, Collection unreliableLeft, Collection unreliableRight) throws DatabaseException { + sortStatement(ss1, ss2); + + int i1 = 0; + int i2 = 0; + + while (true) { + if (i1 >= ss1.size()) { + if (i2 >= ss2.size()) { + break; + } else { + while (i2 < ss2.size()) { + if (DEBUG) System.out.println("Compare Statements addition " + printStatement(g,ss2.get(i2))); + + addAddition(ss2.get(i2)); + i2++; + } + break; + } + } else if (i2 >= ss2.size()) { + while (i1 < ss1.size()) { + if (DEBUG) System.out.println("Compare Statements deletion " + printStatement(g,ss1.get(i1))); + addDeletion(ss1.get(i1)); + i1++; + } + break; + } + int same1 = sameRel(ss1, i1); + int same2 = sameRel(ss2, i2); + int c = rcomp.compare(ss1.get(i1).getPredicate(),ss2.get(i2).getPredicate()); + if (c == 0) { + compareStatements(ss1, i1, same1, ss2, i2, same2,objectsLeft,objectsRight,unreliableLeft,unreliableRight); + i1+=same1; + i2+=same2; + } else if (c < 0) { + for (int i = 0; i < same1; i++) { + if (DEBUG) System.out.println("Compare Statements deletion " + printStatement(g,ss1.get(i+i1))); + addDeletion(ss1.get(i+i1)); + } + i1 += same1; + } else { + for (int i = 0; i < same2; i++) { + if (DEBUG) System.out.println("Compare Statements addition " + printStatement(g,ss2.get(i+i2))); + addAddition(ss2.get(i+i2)); + } + + i2 += same2; + } + } + } + + + + private int sameRel(List statements, int off) { + if (statements.size() <= off) + return 0; + int same = 1; + long id = statements.get(off).getPredicate().getResourceId(); + for (int i = off+1; i ss1, int off1, int len1, List ss2, int off2, int len2, Collection objectsLeft, Collection objectsRight, Collection unreliableLeft, Collection unreliableRight) throws DatabaseException { + boolean[] used1 = new boolean[len1]; + for (int i = 0; i < used1.length; i++) { + used1[i] = false; + } + + boolean[] used2 = new boolean[len2]; + for (int i = 0; i < used2.length; i++) { + used2[i] = false; + } + + // left, right, difference + List> differences = new ArrayList>(); + for (int i1 = off1; i1 < off1 + len1; i1++) { + Statement s1 = ss1.get(i1); + List diff = new ArrayList(); + for (int i2 = off2; i2 < off2 + len2; i2++) { + Statement s2 = ss2.get(i2); + int d = compareObject(s1.getObject(), s2.getObject()); + if (d == 0) { + for (Resource t : strong) { + if (s1.getPredicate().equals(t) || g.isSubrelationOf(s1.getPredicate(), t)) { + d = 1; + break; + } + } + } + diff.add(d); + } + differences.add(diff); + } + // difference, left + MapList priorities = new MapList(); + for (int i = 0; i < differences.size(); i++) { + List list = differences.get(i); + for (int j = 0; j < list.size(); j++) { + priorities.add(list.get(j), i); + } + } + + Integer[] pris = priorities.getKeys(new Integer[]{}); + Arrays.sort(pris); + + for (Integer pri : pris) { + if (pri == Integer.MAX_VALUE) { + + } else if (pri == 0) { + + } else { + List i1s = priorities.getValues(pri); + for (Integer i1 : i1s) { + if (used1[i1]) + continue; + List i2diff = differences.get(i1); + for (int i2 = 0; i2 < i2diff.size(); i2++) { + if (i2diff.get(i2) == pri) { + if (used2[i2]) + continue; + used1[i1] = true; + used2[i2] = true; + Statement s1 = ss1.get(i1+off1); + Statement s2 = ss2.get(i2+off2); + + if (objectsLeft != null) { + objectsLeft.add(s1.getObject()); + objectsRight.add(s2.getObject()); + } + addComparable(s1, s2, true); + break; + } + } + } + } + } + + for (Integer pri : pris) { + if (pri != 0) + continue; + Set s1s = new HashSet(); + Set s2s = new HashSet(); + Set s1i = new HashSet(); + Set s2i = new HashSet(); + List i1s = priorities.getValues(pri); + for (Integer i1 : i1s) { + if (used1[i1]) + continue; + List i2diff = differences.get(i1); + for (int i2 = 0; i2 < i2diff.size(); i2++) { + if (i2diff.get(i2) == pri) { + if (used2[i2]) + continue; + Statement s1 = ss1.get(i1+off1); + Statement s2 = ss2.get(i2+off2); + s1s.add(s1); + s2s.add(s2); + s1i.add(i1); + s2i.add(i2); + } + } + } + if (unreliableLeft != null) { + unreliableLeft.addAll(s1s); + unreliableRight.addAll(s2s); + } + for (Integer i : s1i) + used1[i] = true; + for (Integer i : s2i) + used2[i] = true; + + } + for (int i1 = off1; i1 < off1 + len1; i1++) { + if (!used1[i1-off1]) { + if (DEBUG) System.out.println("Compare Object deletion " + printStatement(g,ss1.get(i1))); + addDeletion(ss1.get(i1)); + } + } + for (int i2 = off2; i2 < off2 + len2; i2++) { + if (!used2[i2-off2]) { + if (DEBUG) System.out.println("Compare Object addition " + printStatement(g,ss2.get(i2))); + addAddition(ss2.get(i2)); + } + } + } + + + + /** + * compares properties, assumes functional relations + * @param r1 + * @param r2 + * @throws ServiceException + * @throws DoesNotContainValueException + * @throws ValidationException + */ + private void compareProps(Resource r1, Resource r2) throws DatabaseException { + if (DEBUG) System.out.println("compareProps " + r1 + " " + NameUtils.getSafeName(g, r1) + " " + r2 + " " + NameUtils.getSafeName(g, r2)); + List ss1 = new ArrayList(); + List ss2 = new ArrayList(); + ss1.addAll(g.getStatements(r1, b.HasProperty)); + ss2.addAll(g.getStatements(r2, b.HasProperty)); + ss1 = filterNonTested(ss1); + ss2 = filterNonTested(ss2); + sortStatement(ss1, ss2); + + int i1 = 0; + int i2 = 0; + + while (true) { + if (i1 >= ss1.size()) { + if (i2 >= ss2.size()) + break; + else { + while (i2 < ss2.size()) { + if (DEBUG) System.out.println("Compare Prop diff2 " + printStatement(g,ss2.get(i2))); + addAddition(ss2.get(i2)); + i2++; + } + break; + } + } else if (i2 >= ss2.size()) { + while (i1 < ss1.size()) { + if (DEBUG) System.out.println("Compare Prop diff1 " + printStatement(g,ss1.get(i1))); + addDeletion(ss1.get(i1)); + i1++; + } + break; + } + Statement s1 = ss1.get(i1); + Statement s2 = ss2.get(i2); + if (s1.isAsserted(r1) && s2.isAsserted(r2)) { + i1++; + i2++; + continue; + } + int c = scomp.compare(s1, s2); + switch (c) { + case 0:{ + boolean b1 = g.hasValue(s1.getObject()); + boolean b2 = g.hasValue(s2.getObject()); + if (b1 == b2) { + if (b1) { + Object v1 = g.getValue(s1.getObject()); + Object v2 = g.getValue(s2.getObject()); + boolean eq = compareValue(v1, v2); + if (!eq) { + addModification(s1, s2); + addComparable(s1, s2, false); + } + } else { + if (!s1.getObject().equals(s1.getSubject()) && !s2.getObject().equals(s2.getSubject())) + compareProps(s1.getObject(), s2.getObject()); + } + } else { + addModification(s1, s2); + addComparable(s1, s2, false); + } + i1++; + i2++; + break; + } + case -1:{ + if (DEBUG) System.out.println("Compare Prop diff1s " + printStatement(g,s1)); + addDeletion(s1); + i1++; + break; + } + + case 1:{ + if (DEBUG) System.out.println("Compare Prop diff2s " + printStatement(g,s2)); + addAddition(s2); + i2++; + break; + } + } + + } + + ss1.clear(); + ss2.clear(); + + } + + public static boolean compareValue(Object v1, Object v2) { + if (v1 instanceof Object[] && v2 instanceof Object[]) + return Arrays.deepEquals((Object[])v1, (Object[])v2); + else if (v1 instanceof int[] && v2 instanceof int[]) + return Arrays.equals((int[])v1, (int[])v2); + else if (v1 instanceof float[] && v2 instanceof float[]) + return Arrays.equals((float[])v1, (float[])v2); + else if (v1 instanceof double[] && v2 instanceof double[]) + return Arrays.equals((double[])v1, (double[])v2); + else if (v1 instanceof long[] && v2 instanceof long[]) + return Arrays.equals((long[])v1, (long[])v2); + else if (v1 instanceof byte[] && v2 instanceof byte[]) + return Arrays.equals((byte[])v1, (byte[])v2); + else if (v1 instanceof boolean[] && v2 instanceof boolean[]) + return Arrays.equals((boolean[])v1, (boolean[])v2); + else + return v1.equals(v2); + } + + + public class PredicateComparator implements Comparator { + @Override + public int compare(Statement o1, Statement o2) { + if (comparableResources.contains(o1.getPredicate(), o2.getPredicate())) + return 0; + if (o1.getPredicate().getResourceId() < o2.getPredicate().getResourceId()) + return -1; + if (o1.getPredicate().getResourceId() > o2.getPredicate().getResourceId()) + return 1; + return 0; + } + } + + public class SubjectComparator implements Comparator { + @Override + public int compare(Statement o1, Statement o2) { + if (comparableResources.contains(o1.getSubject(), o2.getSubject())) + return 0; + if (o1.getSubject().getResourceId() < o2.getSubject().getResourceId()) + return -1; + if (o1.getSubject().getResourceId() > o2.getSubject().getResourceId()) + return 1; + return 0; + } + } + + public class ObjectComparator implements Comparator { + @Override + public int compare(Statement o1, Statement o2) { + if (comparableResources.contains(o1.getObject(), o2.getObject())) + return 0; + if (o1.getObject().getResourceId() < o2.getObject().getResourceId()) + return -1; + if (o1.getObject().getResourceId() > o2.getObject().getResourceId()) + return 1; + return 0; + } + } + + public static class FullStatementComparator implements Comparator { + @Override + public int compare(Statement o1, Statement o2) { + if (o1.getSubject().getResourceId() < o2.getSubject().getResourceId()) + return -1; + if (o1.getSubject().getResourceId() > o2.getSubject().getResourceId()) + return 1; + if (o1.getPredicate().getResourceId() < o2.getPredicate().getResourceId()) + return -1; + if (o1.getPredicate().getResourceId() > o2.getPredicate().getResourceId()) + return 1; + if (o1.getObject().getResourceId() < o2.getObject().getResourceId()) + return -1; + if (o1.getObject().getResourceId() > o2.getObject().getResourceId()) + return 1; + return 0; + } + } + + public class ResComparator implements Comparator { + @Override + public int compare(Resource o1, Resource o2) { + if (comparableResources.contains(o1, o2)) + return 0; + if (o1.getResourceId() < o2.getResourceId()) + return -1; + if (o1.getResourceId() > o2.getResourceId()) + return 1; + return 0; + } + } + +} -- 2.47.1