*
* Contributors:
* Foster Wheeler Energia Oy - initial API and implementation
+ * VTT Technical Research Centre of Finland - Improvements to comparison.
+ * Semantum Oy - Improvements to comparison, various bug fixes.
*******************************************************************************/
package org.simantics.interop.test;
import java.util.Set;
import java.util.Stack;
+import org.eclipse.core.runtime.IProgressMonitor;
+import org.eclipse.core.runtime.NullProgressMonitor;
import org.simantics.databoard.Bindings;
import org.simantics.db.ReadGraph;
import org.simantics.db.Resource;
import org.simantics.db.common.request.ReadRequest;
import org.simantics.db.common.utils.NameUtils;
import org.simantics.db.exception.DatabaseException;
+import org.simantics.db.request.Read;
import org.simantics.interop.test.GraphChanges.Modification;
import org.simantics.layer0.Layer0;
import org.simantics.utils.datastructures.BijectionMap;
*/
public class GraphComparator {
- private static final boolean DEBUG = true;
+ private static final boolean DEBUG = false;
private Resource r1;
private Resource r2;
private Set<Resource> nonMatchedLeft = new HashSet<Resource>();
private Set<Resource> nonMatchedRight = new HashSet<Resource>();
+ private long iter = 0;
+ private long maxIter = -1;
+
// runtime attributes
private ReadGraph g;
private Layer0 b;
+ private boolean mapLiterals = true;
+
public GraphComparator(Resource r1, Resource r2) {
this.r1 = r1;
this.r2 = r2;
this.comparator = comparator;
}
- ArrayList<Statement> ss1 = new ArrayList<Statement>();
- ArrayList<Statement> ss2 = new ArrayList<Statement>();
-
public Comparator<Resource> getResourceComparator() {
return rcomp;
nonMatchedRight.add(r);
}
+ public long getMaxIter() {
+ return maxIter;
+ }
+
+ /**
+ * Sets maximum iteration done on a single DB transaction. Affects only test(Session) methods.
+ * Default value is -1, which disables iteration limit.
+ * Note that using iteration limit causes comparison to repeat some work, thus total execution time will increase.
+ *
+ * @param maxIter
+ */
+ public void setMaxIter(long maxIter) {
+ this.maxIter = maxIter;
+ }
+
+ public boolean isMapLiterals() {
+ return mapLiterals;
+ }
+
+ public void setMapLiterals(boolean mapLiterals) {
+ this.mapLiterals = mapLiterals;
+ }
+
+ private void clear() {
+ changes1.clear();
+ changes1Set.clear();
+ changes2.clear();
+ changes2Set.clear();
+ comparableResources.clear();
+ comparableStatements.clear();
+ modifications.clear();
+ modificationsSet.clear();
+ processedResources.clear();
+ }
+
+ public void dispose() {
+ changes1 = null;
+ changes1Set = null;
+ changes2 = null;
+ changes2Set = null;
+ comparableResources = null;
+ comparableStatements = null;
+ comparator = null;
+ modifications = null;
+ modificationsSet = null;
+ processedResources = null;
+ nonMatchedLeft = null;
+ nonMatchedRight = null;
+ nonTested = null;
+ nonTraversed = null;
+ strong = null;
+ tested = null;
+ traversed = null;
+ }
+
public void test(ReadGraph g) throws DatabaseException {
+ test(g,null);
+ }
+
+ public void test(ReadGraph g, IProgressMonitor monitor) throws DatabaseException {
this.g = g;
this.b = Layer0.getInstance(g);
comparator.setComparator(this);
comparator.initialize(g, r1, r2);
+ if (monitor == null)
+ monitor = new NullProgressMonitor();
+
Stack<Resource> objectsLeft = new Stack<Resource>();
Stack<Resource> objectsRight = new Stack<Resource>();
objectsLeft.push(r1);
Set<Statement> unreliableLeft = new HashSet<Statement>();
Set<Statement> unreliableRight = new HashSet<Statement>();
+ boolean changed = false;
while (true) {
- if (objectsLeft.isEmpty())
+ if (objectsLeft.isEmpty() && !changed)
break;
-
+ if (monitor.isCanceled()) {
+ clear();
+ return;
+ }
+ monitor.subTask(monitorTaskName(objectsLeft, objectsRight, unreliableLeft, unreliableRight));
+ changed = false;
// 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) {
- processUnreliable2(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);
- }
+ changed = compareIter(g, objectsLeft, objectsRight, unreliableLeft, unreliableRight);
+ monitor.worked(1);
}
for (Statement s : unreliableLeft) {
- if (!comparableStatements.containsLeft(s))
+ if (!comparableStatements.containsLeft(s)) {
+ if (DEBUG) System.out.println("Unreliable Object deletion " + printStatement(g,s));
addDeletion(s);
+ }
}
for (Statement s : unreliableRight) {
- if (!comparableStatements.containsRight(s))
+ if (!comparableStatements.containsRight(s)) {
+ if (DEBUG) System.out.println("Unreliable Object addition " + printStatement(g,s));
addAddition(s);
+ }
}
+ monitor.subTask(monitorTaskName(objectsLeft, objectsRight, unreliableLeft, unreliableRight) + " done.");
+ //printStats();
}
public void test(Session session) throws DatabaseException {
- test(session, r1, r2);
+ test(session, r1, r2, null);
+ }
+
+ public void test(Session session, IProgressMonitor monitor) throws DatabaseException {
+ test(session, r1, r2, monitor);
}
public void test(Session session, Resource r1, Resource r2) throws DatabaseException {
+ test(session, r1, r2, null);
+ }
+
+ public void test(Session session, Resource r1, Resource r2, IProgressMonitor monitor) throws DatabaseException {
comparator.setComparator(this);
+ if (monitor == null)
+ monitor = new NullProgressMonitor();
+
session.syncRequest(new ReadRequest() {
@Override
final Set<Statement> unreliableLeft = new HashSet<Statement>();
final Set<Statement> unreliableRight = new HashSet<Statement>();
+ boolean changed = false;
while (true) {
- if (objectsLeft.isEmpty())
+ if (objectsLeft.isEmpty() && !changed)
break;
- session.syncRequest(new ReadRequest() {
+ if (monitor.isCanceled()) {
+ clear();
+ return;
+ }
+ monitor.subTask(monitorTaskName(objectsLeft, objectsRight, unreliableLeft, unreliableRight));
+ changed = session.syncRequest(new Read<Boolean>() {
@Override
- public void run(ReadGraph graph) throws DatabaseException {
+ public Boolean perform(ReadGraph graph) throws DatabaseException {
+ //System.out.println("Iter " + monitorTaskName(objectsLeft, objectsRight, unreliableLeft, unreliableRight));
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) {
- processUnreliable2(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);
- }
- 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);
- }
+ return compareIter(graph, objectsLeft, objectsRight, unreliableLeft, unreliableRight);
}
});
-
+ monitor.worked(1);
}
if (!comparableStatements.containsRight(s))
addAddition(s);
}
+ unreliableLeft.clear();
+ unreliableRight.clear();
-
+ monitor.subTask(monitorTaskName(objectsLeft, objectsRight, unreliableLeft, unreliableRight) + " done.");
+ //printStats();
}
- private void process(Stack<Resource> objectsLeft, Stack<Resource> objectsRight, Set<Statement> unreliableLeft, Set<Statement> unreliableRight) throws DatabaseException {
+ private boolean compareIter(ReadGraph graph, Stack<Resource> objectsLeft, Stack<Resource> objectsRight, Set<Statement> unreliableLeft, Set<Statement> unreliableRight) throws DatabaseException {
+ // process compares objects that are identified and searches for more resources to process.
+ iter = 0;
+ boolean c = process(objectsLeft, objectsRight, unreliableLeft, unreliableRight,false);
+ if (objectsLeft.isEmpty()) {
+ // process unreliable handles cases where unidentified statements subject and object have been identified
+ c |= processUnreliable(unreliableLeft, unreliableRight);
+ // process unreliable handles cases where unidentified resources have path of length one to identified resource
+ if (!c) {
+ c |= processUnreliable(unreliableLeft, unreliableRight,objectsLeft,objectsRight,false);
+ if (!c && objectsLeft.isEmpty() && unreliableLeft.size() > 0 && unreliableRight.size() > 0) {
+ c |= processUnreliable(unreliableLeft, unreliableRight,objectsLeft,objectsRight,true);
+ }
+ if (!c && objectsLeft.isEmpty() && unreliableLeft.size() > 0 && unreliableRight.size() > 0) {
+ c |= processUnreliable2(unreliableLeft, unreliableRight,objectsLeft,objectsRight,false);
+ }
+ if (!c && objectsLeft.isEmpty() && unreliableLeft.size() > 0 && unreliableRight.size() > 0) {
+ c |= processUnreliable2(unreliableLeft, unreliableRight,objectsLeft,objectsRight,true);
+ }
+ if (!c && 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.
+ c |= processUnreliableDeep(unreliableLeft, unreliableRight, objectsLeft, objectsRight);
+ }
+ if (!c && 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.
+ c |= processUnreliableDeep(unreliableLeft, unreliableRight, objectsLeft, objectsRight);
+ }
+ }
+ }
+ if (!c)
+ process(objectsLeft, objectsRight, unreliableLeft, unreliableRight,true);
+ return c;
+
+ }
+
+ private String monitorTaskName(Stack<Resource> objectsLeft, Stack<Resource> objectsRight, Set<Statement> unreliableLeft, Set<Statement> unreliableRight) {
+ int cr = comparableResources.size();
+ int ch = Math.max(changes1.size(), changes2.size());
+ return "Graph compare " + (cr + ch) + " / " + (cr+ch+(Math.max(objectsLeft.size(), objectsRight.size())+Math.max(unreliableLeft.size(), unreliableRight.size())));
+ }
+
+ private boolean process(Stack<Resource> objectsLeft, Stack<Resource> objectsRight, Set<Statement> unreliableLeft, Set<Statement> unreliableRight, boolean useBest) throws DatabaseException {
List<Statement> ss1 = new ArrayList<Statement>();
List<Statement> ss2 = new ArrayList<Statement>();
-
- while (!objectsLeft.isEmpty()) {
+ boolean didSomething = false;
+ while (!objectsLeft.isEmpty()&& (maxIter < 0 || iter < maxIter)) {
Resource r1 = objectsLeft.pop();
Resource r2 = objectsRight.pop();
if (r1.equals(r2))
continue;
- if (r1.getResourceId() == 610446L)
- System.out.println();
if (processedResources.contains(r1))
continue;
processedResources.add(r1);
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);
-
+ didSomething = true;
//System.out.println("test " + NameUtils.getSafeName(g, r1) + " " + NameUtils.getSafeName(g, r2));
compareProps(r1, r2);
ss2 = filterTraversed(ss2);
ss1 = filterNonTested(ss1);
ss2 = filterNonTested(ss2);
+ ss1 = filter(Collections.singletonList(b.HasProperty), ss1);
+ ss2 = filter(Collections.singletonList(b.HasProperty), ss2);
-
- compareStatements(ss1, ss2, null, null,null,null);
+ compareStatements(ss1, ss2, null, null,null,null, useBest);
ss1.clear();
ss2.clear();
}
ss2 = filterAsserted(r2, ss2);
ss1 = filterNonTraversed(ss1);
ss2 = filterNonTraversed(ss2);
- compareStatements(ss1, ss2, objectsLeft, objectsRight,unreliableLeft,unreliableRight);
+ compareStatements(ss1, ss2, objectsLeft, objectsRight,unreliableLeft,unreliableRight, useBest);
ss1.clear();
ss2.clear();
}
+ iter++;
}
+ return didSomething;
}
- private void processUnreliable(Set<Statement> unreliableLeft, Set<Statement> unreliableRight) throws DatabaseException {
+ private boolean processUnreliable(Set<Statement> unreliableLeft, Set<Statement> unreliableRight) throws DatabaseException {
MapList<Resource,Statement> subjectLeft = new MapList<Resource, Statement>();
MapList<Resource,Statement> subjectRight = new MapList<Resource, Statement>();
MapList<Resource,Statement> objectLeft = new MapList<Resource, Statement>();
MapList<Resource,Statement> objectRight = new MapList<Resource, Statement>();
-
+ boolean didSomething = false;
for (Statement s : unreliableLeft) {
subjectLeft.add(s.getSubject(),s);
objectLeft.add(s.getObject(),s);
}
for (Resource left : subjectLeft.getKeys()) {
+ if (maxIter > 0 && iter > maxIter)
+ break;
Resource right = comparableResources.getRight(left);
if (right == null)
continue;
unreliableLeft.remove(leftS);
unreliableRight.remove(rightS);
addComparable(leftS, rightS);
+ didSomething = true;
+ iter++;
}
}
}
}
+ return didSomething;
}
- private void processUnreliable(Set<Statement> unreliableLeft, Set<Statement> unreliableRight, Stack<Resource> objectsLeft, Stack<Resource> objectsRight) throws DatabaseException {
+ private boolean processUnreliable(Set<Statement> unreliableLeft, Set<Statement> unreliableRight, Stack<Resource> objectsLeft, Stack<Resource> objectsRight, boolean useBest) throws DatabaseException {
MapList<Resource,Statement> subjectLeft = new MapList<Resource, Statement>();
MapList<Resource,Statement> subjectRight = new MapList<Resource, Statement>();
MapList<Resource,Statement> objectLeft = new MapList<Resource, Statement>();
MapList<Resource,Statement> objectRight = new MapList<Resource, Statement>();
-
+ boolean didSomething = false;
for (Statement s : unreliableLeft) {
subjectLeft.add(s.getSubject(),s);
objectLeft.add(s.getObject(),s);
subjectRight.add(s.getSubject(),s);
objectRight.add(s.getObject(),s);
}
-
for (Resource ol : objectLeft.getKeys()) {
+ if (maxIter > 0 && iter > maxIter)
+ break;
// all statements to the left side object
List<Statement> left = objectLeft.getValues(ol);
// all subjects that have statements to the left side object (ol)
}
}
- compareStatements(ss1, ss2, objectsLeft, objectsRight,unreliableLeft,unreliableRight);
-
for (Resource similarOl : comparableOLeft.getKeys()) {
List<Statement> similarLeft = comparableOLeft.getValues(similarOl);
if (similarLeft.size() == left.size()) {
// compare objects (unreliable result is interpreted as positive match)
int comp = comparator.compare(g, left.get(i).getObject(), similarLeft.get(j).getObject(), true);
- if (comp >= 0 && comp < Integer.MAX_VALUE) {
+ if (comp >= 0 && comp < ResourceComparator.NO_MATCH) {
useL[i] = true;
useSL[j] = true;
break;
Statement rs = right.get(r);
if (!comparableResources.contains(ls.getSubject(), rs.getSubject()))
continue;
+ if ((comparableResources.containsLeft(ls.getObject()) || comparableResources.containsRight(rs.getObject())) && !comparableResources.contains(ls.getObject(), rs.getObject()))
+ continue;
if (rcomp.compare(ls.getPredicate(),rs.getPredicate()) == 0) {
// compare objects (unreliable result is not accepted)
int comp = comparator.compare(g, ls.getObject(), rs.getObject());
objectsLeft.add(ol);
objectsRight.add(or);
addComparable(ol, or);
+ didSomething = true;
for (int l = 0; l < left.size(); l++) {
int r = indices.first[l];
Statement sl = left.get(l);
unreliableLeft.remove(sl);
unreliableRight.remove(sr);
}
+ iter++;
} else {
}
}
+ return didSomething;
}
- private void processUnreliable2(Set<Statement> unreliableLeft, Set<Statement> unreliableRight, Stack<Resource> objectsLeft, Stack<Resource> objectsRight) throws DatabaseException {
+ private boolean processUnreliable2(Set<Statement> unreliableLeft, Set<Statement> unreliableRight, Stack<Resource> objectsLeft, Stack<Resource> objectsRight, boolean useBest) throws DatabaseException {
MapList<Resource,Statement> subjectLeft = new MapList<Resource, Statement>();
MapList<Resource,Statement> subjectRight = new MapList<Resource, Statement>();
MapList<Resource,Statement> objectLeft = new MapList<Resource, Statement>();
MapList<Resource,Statement> objectRight = new MapList<Resource, Statement>();
-
+ boolean didSomething = false;
for (Statement s : unreliableLeft) {
subjectLeft.add(s.getSubject(),s);
objectLeft.add(s.getObject(),s);
subjectRight.add(s.getSubject(),s);
objectRight.add(s.getObject(),s);
}
-
+ Set<Pair<Resource, Resource>> processed = new HashSet<Pair<Resource,Resource>>();
for (Resource ol : objectLeft.getKeys()) {
+ if (maxIter > 0 && iter > maxIter)
+ break;
// all statements to the left side object
List<Statement> left = objectLeft.getValues(ol);
// all subjects that have statements to the left side object (ol)
}
if (sLeft.size() == 1 && sRight.size() == 1) {
- List<Statement> ss1 = new ArrayList<Statement>(subjectLeft.getValues(sLeft.iterator().next()));
- List<Statement> ss2 = new ArrayList<Statement>(subjectRight.getValues(sRight.iterator().next()));
+ Resource sl = sLeft.iterator().next();
+ Resource sr = sRight.iterator().next();
+ Pair<Resource, Resource> p = new Pair<Resource, Resource>(sl, sr);
+ if (processed.contains(p))
+ continue;
+ processed.add(p);
+ List<Statement> ss1 = new ArrayList<Statement>(subjectLeft.getValuesSnapshot(sl));
+ List<Statement> ss2 = new ArrayList<Statement>(subjectRight.getValuesSnapshot(sr));
+ for (int i = ss1.size() -1; i >= 0; i--) {
+ if (!unreliableLeft.contains(ss1.get(i)))
+ ss1.remove(i);
+ }
+ for (int i = ss2.size() -1; i >= 0; i--) {
+ if (!unreliableRight.contains(ss2.get(i)))
+ ss2.remove(i);
+ }
+
+ int ccount = comparableStatements.size();
+ int lcount = changes1.size();
+ int rcount = changes2.size();
- int count = comparableStatements.size();
- compareStatements(ss1, ss2, objectsLeft, objectsRight,unreliableLeft,unreliableRight);
- if (comparableStatements.size() > count) {
+ compareStatements(ss1, ss2, objectsLeft, objectsRight,unreliableLeft,unreliableRight, useBest);
+ if (comparableStatements.size() > ccount) {
+ didSomething = true;
for (Entry<Statement, Statement> entry : comparableStatements.getEntries()) {
unreliableLeft.remove(entry.getKey());
unreliableRight.remove(entry.getValue());
+ iter++;
+ }
+ }
+ if (changes1.size() > lcount) {
+ didSomething = true;
+ for (Statement stm : changes1) {
+ unreliableLeft.remove(stm);
+ iter++;
+ }
+ }
+ if (changes2.size() > rcount) {
+ didSomething = true;
+ for (Statement stm : changes2) {
+ unreliableRight.remove(stm);
+ iter++;
}
}
}
}
+ return didSomething;
}
- private void processUnreliableDeep(Set<Statement> unreliableLeft, Set<Statement> unreliableRight, Stack<Resource> objectsLeft, Stack<Resource> objectsRight) throws DatabaseException {
+ private boolean processUnreliableDeep(Set<Statement> unreliableLeft, Set<Statement> unreliableRight, Stack<Resource> objectsLeft, Stack<Resource> objectsRight) throws DatabaseException {
MapList<Resource,Statement> subjectLeft = new MapList<Resource, Statement>();
MapList<Resource,Statement> subjectRight = new MapList<Resource, Statement>();
MapList<Resource,Statement> objectLeft = new MapList<Resource, Statement>();
MapList<Resource,Statement> objectRight = new MapList<Resource, Statement>();
-
+ boolean didSomething = false;
for (Statement s : unreliableLeft) {
subjectLeft.add(s.getSubject(),s);
objectLeft.add(s.getObject(),s);
objectRight.add(s.getObject(),s);
}
for (Resource ol : objectLeft.getKeys()) {
+ if (maxIter > 0 && iter > maxIter)
+ break;
Set<Path> pathsLeft = new HashSet<Path>();
for (Resource rel : traversed) {
pathsLeft.addAll(Path.create(g.getStatements(ol, rel)));
if (matchingPaths.size() > 0) {
if (matchingPaths.size() == 1) {
Resource or = matchingPaths.keySet().iterator().next();
-
- objectsLeft.add(ol);
- objectsRight.add(or);
- addComparable(ol, or);
- Collection<Statement> statementsLeft = objectLeft.getValues(ol);
- Collection<Statement> statementsRight = objectRight.getValues(or);
- unreliableLeft.removeAll(statementsLeft);
- unreliableRight.removeAll(statementsRight);
BijectionMap<Path,Path> map = getMatchingPaths(pathsLeft, matchingPaths.get(or));
+ BijectionMap<Resource,Resource> toMap = new BijectionMap<Resource, Resource>();
+ toMap.map(ol, or);
+ boolean pass = true;
+ // Path matching may create conflicting results, prevent selecting them.
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));
+ Resource l = left.getStatements().get(i).getObject();
+ Resource r = right.getStatements().get(i).getObject();
+ if (comparableResources.contains(l, r))
+ continue;
+ if (comparableResources.containsLeft(l)) {
+ pass = false;
+ break;
+ }
+ if (comparableResources.containsRight(r)) {
+ pass = false;
+ break;
+ }
+ if (toMap.contains(l,r))
+ continue;
+ if (toMap.containsLeft(l)) {
+ pass = false;
+ break;
+ }
+ if (toMap.containsRight(r)) {
+ pass = false;
+ break;
+ }
+ toMap.map(l, r);
+
+ }
+ }
+ if (pass) {
+ didSomething = true;
+
+ objectsLeft.add(ol);
+ objectsRight.add(or);
+ addComparable(ol, or);
+ Collection<Statement> statementsLeft = objectLeft.getValues(ol);
+ Collection<Statement> statementsRight = objectRight.getValues(or);
+ unreliableLeft.removeAll(statementsLeft);
+ unreliableRight.removeAll(statementsRight);
+ 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));
+ iter++;
+ }
}
+ iter++;
+ } else {
+ iter++;
}
}
}
}
}
+ return didSomething;
}
- private boolean hasMatchingPaths(Set<Path> leftPaths, Set<Path> rightPaths) {
+ private boolean hasMatchingPaths(Set<Path> leftPaths, Set<Path> rightPaths) throws DatabaseException {
if (leftPaths.size() != rightPaths.size())
return false;
BijectionMap<Path,Path> map = getMatchingPaths(leftPaths, rightPaths);
return map.size() == leftPaths.size();
}
- private BijectionMap<Path,Path> getMatchingPaths(Set<Path> leftPaths, Set<Path> rightPaths) {
+ private BijectionMap<Path,Path> getMatchingPaths(Set<Path> leftPaths, Set<Path> rightPaths) throws DatabaseException {
BijectionMap<Path,Path> map = new BijectionMap<Path, Path>();
for (Path leftPath : leftPaths) {
for (Path rightPath : rightPaths) {
if (leftPath.getLength() != rightPath.getLength())
continue;
if (comparableResources.contains(leftPath.getEnd(), rightPath.getEnd())) {
- map.map(leftPath, rightPath);
- break;
+ boolean match = true;
+ for (int i = 0; i < leftPath.getLength(); i++) {
+ Statement sl = leftPath.getStatements().get(i);
+ Statement sr = rightPath.getStatements().get(i);
+ if (!sl.getPredicate().equals(sr.getPredicate()) && !comparableResources.contains(sl.getPredicate(), sr.getPredicate())) {
+ match = false;
+ break;
+ }
+ if ((getComparableResources().containsLeft(sl.getObject()) || getComparableResources().containsRight(sr.getObject())) && !getComparableResources().contains(sl.getObject(), sr.getObject())) {
+ match = false;
+ break;
+ }
+ if (comparator.compare(g, sl.getObject(), sr.getObject()) == ResourceComparator.NO_MATCH) {
+ match = false;
+ break;
+ }
+ }
+ if (match) {
+ map.map(leftPath, rightPath);
+ break;
+ }
}
}
}
return new GraphChanges(r1,r2,changes1,changes2,modifications,comparableResources);
}
+ public List<Statement> getChanges1() {
+ return changes1;
+ }
+
+ public List<Statement> getChanges2() {
+ return changes2;
+ }
+
private void addComparable(Statement left, Statement right) throws DatabaseException {
addComparable(left.getObject(), right.getObject());
comparableStatements.map(left, right);
- //comparableResources.map(left.getObject(), right.getObject());
}
private void addComparable(Resource left, Resource right) throws DatabaseException {
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);
- if (left.getResourceId() == 610381L)
- System.out.println();
comparableResources.map(left, right);
+
+// if (comparableResources.size() % 1000 == 0)
+// printStats();
}
}
}
+ public void printStats() {
+ System.out.println("Comp " + comparableResources.size() + " L " + changes1.size() + " R " + changes2.size() + " M " + modifications.size() + " P " + processedResources.size());
+ }
+
public List<Statement> filterAsserted(Resource r, Collection<Statement> in) throws DatabaseException {
List<Statement> out = new ArrayList<Statement>();
for (Statement s : in) {
return out;
}
+ public List<Statement> filterAssertedDuplicates(Resource r, List<Statement> in) throws DatabaseException {
+ List<Statement> out = new ArrayList<Statement>();
+ for (int i = 0; i < in.size(); i++) {
+ Statement s = in.get(i);
+ if (!s.isAsserted(r))
+ out.add(s);
+ else {
+ boolean has = false;
+ if (i > 0 && in.get(i-1).getPredicate().equals(s.getPredicate()))
+ has = true;
+ else if (i < in.size()-1 && in.get(i+1).getPredicate().equals(s.getPredicate()))
+ has = true;
+ if (!has)
+ out.add(s);
+ }
+
+ }
+ return out;
+ }
+
private String printStatement(ReadGraph graph, Statement s) throws DatabaseException {
private void addDeletion(Statement s) {
if (!changes1Set.contains(s)) {
+ if (DEBUG) System.out.println("- " +s.getSubject() + " " + s.getPredicate() + " " + s.getObject()) ;
changes1Set.add(s);
changes1.add(s);
- if (s.getObject().getResourceId() == 532631L)
- System.out.println();
}
}
private void addAddition(Statement s) {
if (!changes2Set.contains(s)) {
changes2Set.add(s);
+ if (DEBUG) System.out.println("+ " +s.getSubject() + " " + s.getPredicate() + " " + s.getObject()) ;
changes2.add(s);
}
}
- private void addModification(Resource sub1, Statement s1, Resource sub2, Statement s2) {
- Modification mod = new Modification(sub1, sub2, s1, s2);
+ private void addModification(Resource left, Statement leftstm, Resource right, Statement rightstm) throws DatabaseException {
+ Modification mod = new Modification(left, right, leftstm, rightstm);
if (!modificationsSet.contains(mod)) {
modificationsSet.add(mod);
modifications.add(mod);
+ if (mapLiterals && leftstm != null && rightstm != null)
+ addComparable(leftstm, rightstm);
}
}
}
}
- private void compareStatements(List<Statement> ss1, List<Statement> ss2, Stack<Resource> objectsLeft, Stack<Resource> objectsRight, Collection<Statement> unreliableLeft, Collection<Statement> unreliableRight) throws DatabaseException {
+ private void compareStatements(List<Statement> ss1, List<Statement> ss2, Stack<Resource> objectsLeft, Stack<Resource> objectsRight, Collection<Statement> unreliableLeft, Collection<Statement> unreliableRight, boolean useBest) throws DatabaseException {
sortStatement(ss1, ss2);
int i1 = 0;
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);
+ compareStatements(ss1, i1, same1, ss2, i2, same2,objectsLeft,objectsRight,unreliableLeft,unreliableRight, useBest);
i1+=same1;
i2+=same2;
} else if (c < 0) {
return comparator.compare(g, o1, o2);
}
- private void compareStatements(List<Statement> ss1, int off1, int len1, List<Statement> ss2, int off2, int len2, Collection<Resource> objectsLeft, Collection<Resource> objectsRight, Collection<Statement> unreliableLeft, Collection<Statement> unreliableRight) throws DatabaseException {
+ private void compareStatements(List<Statement> ss1, int off1, int len1, List<Statement> ss2, int off2, int len2, Collection<Resource> objectsLeft, Collection<Resource> objectsRight, Collection<Statement> unreliableLeft, Collection<Statement> unreliableRight, boolean useBest) throws DatabaseException {
boolean[] used1 = new boolean[len1];
for (int i = 0; i < used1.length; i++) {
used1[i] = false;
for (int i = 0; i < used2.length; i++) {
used2[i] = false;
}
-
+
// left, right, difference
List<List<Integer>> differences = new ArrayList<List<Integer>>();
for (int i1 = off1; i1 < off1 + len1; i1++) {
Integer[] pris = priorities.getKeys(new Integer[]{});
Arrays.sort(pris);
+ boolean matchFail = priorityMatching(ss1, off1, len1, ss2, off2, len2, pris, differences, priorities, used1, used2, objectsLeft, objectsRight, false);
+ if (matchFail && objectsLeft == null)
+ matchFail = priorityMatching(ss1, off1, len1, ss2, off2, len2, pris, differences, priorities, used1, used2, objectsLeft, objectsRight,true);
+ if (unreliableLeft != null) {
+ if (matchFail) {
+ if (useBest)
+ bestMatching(ss1, off1, len1, ss2, off2, len2, differences, priorities, used1, used2, objectsLeft, objectsRight);
+ // With match failure, statement matching was aborted. We must move all unmatched statements to unreliable.
+ for (Integer pri : pris) {
+ if (pri == 0 || pri == Integer.MAX_VALUE)
+ continue;
+ priorityProcessUnmatched(ss1, off1, len1, ss2, off2, len2, differences, priorities, used1, used2, unreliableLeft, unreliableRight, pri);
+ }
+ }
+ // Zero means unreliable comparison result, move all unmatched to unreliable.
+ if (org.simantics.utils.datastructures.Arrays.contains(pris, 0)) {
+ priorityProcessUnmatched(ss1, off1, len1, ss2, off2, len2, differences, priorities, used1, used2, unreliableLeft, unreliableRight, 0);
+ }
+ }
+// Previous version processed 0 priority statements, even when unreliableLeft collection was null.
+// The problem was that property relations were not filtered in process() from "tested" statements.
+// else {
+// if (org.simantics.utils.datastructures.Arrays.contains(pris, 0)) {
+// priorityProcessUnmatched(ss1, off1, len1, ss2, off2, len2, differences, priorities, used1, used2, unreliableLeft, unreliableRight, 0);
+// }
+// }
+ // Report unmatched statements as changes.
+ 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));
+ }
+ }
+ }
+
+ /**
+ * Moves unmatched statements to unreliable collections.
+ * @param ss1
+ * @param off1
+ * @param len1
+ * @param ss2
+ * @param off2
+ * @param len2
+ * @param differences
+ * @param priorities
+ * @param used1
+ * @param used2
+ * @param unreliableLeft
+ * @param unreliableRight
+ * @param pri
+ */
+ private void priorityProcessUnmatched(List<Statement> ss1, int off1, int len1, List<Statement> ss2, int off2, int len2,List<List<Integer>> differences,MapList<Integer, Integer> priorities,boolean used1[],boolean used2[], Collection<Statement> unreliableLeft, Collection<Statement> unreliableRight, int pri) {
+ Set<Statement> s1s = new HashSet<Statement>();
+ Set<Statement> s2s = new HashSet<Statement>();
+ Set<Integer> s1i = new HashSet<Integer>();
+ Set<Integer> s2i = new HashSet<Integer>();
+ List<Integer> i1s = priorities.getValues(pri);
+ for (Integer i1 : i1s) {
+ if (used1[i1])
+ continue;
+ List<Integer> 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;
+ }
+ /**
+ * Matches left and right side statements.
+ *
+ * When there are two or more equally good matching objects, the behaviour depends on force flag.
+ * False: Matching is aborted and matchFail is returned (method return true).
+ * True: equally good matches will be paired randomly. Method always returns false.
+ * @param ss1
+ * @param off1
+ * @param len1
+ * @param ss2
+ * @param off2
+ * @param len2
+ * @param pris
+ * @param differences
+ * @param priorities
+ * @param used1
+ * @param used2
+ * @param objectsLeft
+ * @param objectsRight
+ * @param force
+ * @return
+ * @throws DatabaseException
+ */
+ private boolean priorityMatching(List<Statement> ss1, int off1, int len1, List<Statement> ss2, int off2, int len2, Integer[] pris, List<List<Integer>> differences, MapList<Integer, Integer> priorities, boolean used1[],boolean used2[], Collection<Resource> objectsLeft, Collection<Resource> objectsRight, boolean force) throws DatabaseException {
+ boolean matchFail = false;
for (Integer pri : pris) {
if (pri == Integer.MAX_VALUE) {
} else {
List<Integer> i1s = priorities.getValues(pri);
+
for (Integer i1 : i1s) {
if (used1[i1])
continue;
List<Integer> i2diff = differences.get(i1);
+ List<Integer> matches = new ArrayList<Integer>();
for (int i2 = 0; i2 < i2diff.size(); i2++) {
- if (i2diff.get(i2) == pri) {
+ 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);
- break;
+ matches.add(i2);
}
}
- }
- }
- }
-
- for (Integer pri : pris) {
- if (pri != 0)
- continue;
- Set<Statement> s1s = new HashSet<Statement>();
- Set<Statement> s2s = new HashSet<Statement>();
- Set<Integer> s1i = new HashSet<Integer>();
- Set<Integer> s2i = new HashSet<Integer>();
- List<Integer> i1s = priorities.getValues(pri);
- for (Integer i1 : i1s) {
- if (used1[i1])
- continue;
- List<Integer> i2diff = differences.get(i1);
- for (int i2 = 0; i2 < i2diff.size(); i2++) {
- if (i2diff.get(i2) == pri) {
- if (used2[i2])
- continue;
+ if (matches.size() == 1 || (force && matches.size() > 1)) {
+ int i2 = matches.get(0);
+ used1[i1] = true;
+ used2[i2] = true;
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 (objectsLeft != null) {
+ objectsLeft.add(s1.getObject());
+ objectsRight.add(s2.getObject());
+ }
+ addComparable(s1, s2);
+ } else if (matches.size() > 1) {
+ matchFail = true;
}
}
+ if (matchFail)
+ break;
}
- 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));
+ return matchFail;
+ }
+
+ /**
+ * priority matching has a flaw, if lowest priority produces conflicting results, it is not able to match anything.
+ * This matching logic looks for a best match, and if it is non conflicting applies the match.
+ *
+ * TODO: now this applies all unique lowest priority matches for each object. Should this pick only the object with global lowest priority,
+ * so that new matches improve situation with conflicting (non unique) matches?
+ *
+ * @param ss1
+ * @param off1
+ * @param len1
+ * @param ss2
+ * @param off2
+ * @param len2
+ * @param differences
+ * @param priorities
+ * @param used1
+ * @param used2
+ * @param objectsLeft
+ * @param objectsRight
+ * @throws DatabaseException
+ */
+ private void bestMatching(List<Statement> ss1, int off1, int len1, List<Statement> ss2, int off2, int len2, List<List<Integer>> differences, MapList<Integer, Integer> priorities, boolean used1[],boolean used2[], Collection<Resource> objectsLeft, Collection<Resource> objectsRight) throws DatabaseException {
+ for (int i1 = 0; i1 < differences.size(); i1++) {
+ if (used1[i1])
+ continue;
+ List<Integer> diffs = differences.get(i1);
+ int min = Integer.MAX_VALUE;
+ int minIndex = -1;
+ for (int j = 0; j < diffs.size(); j++) {
+ int p = diffs.get(j);
+ if (p < 0)
+ continue;
+ if (p < min) {
+ min = p;
+ minIndex = j;
+ } else if (p == min) {
+ minIndex = -1;
+ }
}
- }
- 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));
+ if (minIndex >= 0 && min > 0) {
+ int i2 = minIndex;
+ if (!used2[i2]) {
+ 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);
+ }
}
}
}
-
-
+
/**
* compares properties, assumes functional relations
* @param r1
* @param r2
- * @throws ServiceException
- * @throws DoesNotContainValueException
- * @throws ValidationException
+ * @throws DatabaseException
*/
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));
ss1 = filterNonTested(ss1);
ss2 = filterNonTested(ss2);
sortStatement(ss1, ss2);
+ // getStatements(r1, b.HasProperty) returns both instance and asserted statements for the same property relation.
+ ss1 = filterAssertedDuplicates(r1, ss1);
+ ss2 = filterAssertedDuplicates(r2, ss2);
int i1 = 0;
int i2 = 0;
break;
else {
while (i2 < ss2.size()) {
- if (DEBUG) System.out.println("Compare Prop diff2 " + printStatement(g,ss2.get(i2)));
- addAddition(ss2.get(i2));
+ Statement s = ss2.get(i2);
+ if (DEBUG) System.out.println("Compare Prop diff2 " + printStatement(g,s));
+ if (!s.isAsserted(r2))
+ addAddition(s);
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));
+ Statement s = ss1.get(i1);
+ if (DEBUG) System.out.println("Compare Prop diff1 " + printStatement(g,s));
+ if (!s.isAsserted(r1))
+ addDeletion(s);
i1++;
}
break;
case 0:{
boolean b1 = g.hasValue(s1.getObject());
boolean b2 = g.hasValue(s2.getObject());
+ boolean a1 = s1.isAsserted(r1);
+ boolean a2 = s2.isAsserted(r2);
if (b1 == b2) {
if (b1) {
-// Object v1 = g.getValue(s1.getObject());
-// Object v2 = g.getValue(s2.getObject());
-// boolean eq = compareValue(v1, v2);
+ // Literals
boolean eq = compareValue(g,b,s1.getObject(), s2.getObject());
if (!eq) {
addModification(r1,s1,r2,s2);
- if (!s1.isAsserted(r1) && !s2.isAsserted(r2))
- addComparable(s1, s2);
}
+ if (mapLiterals && !a1 && !a2)
+ addComparable(s1, s2);
} else {
- if (!s1.getObject().equals(s1.getSubject()) && !s2.getObject().equals(s2.getSubject()))
- compareProps(s1.getObject(), s2.getObject());
+ // Non literal properties.
+ int comp = comparator.compare(g, s1.getObject(), s2.getObject());
+ if (comp == ResourceComparator.NO_MATCH) {
+ addModification(r1,s1,r2,s2);
+ } else if (comp != ResourceComparator.EXACT_MATCH) {
+ if (!s1.getObject().equals(s1.getSubject()) && !s2.getObject().equals(s2.getSubject())) {
+ if (!a1 && !a2) {
+ // compare props matches objects, so we can call that only for non asserted statements
+ compareProps(s1.getObject(), s2.getObject());
+ } else if (a1 && a2) {
+ // TODO : compare asserted statements?
+ } else {
+ addModification(r1,s1,r2,s2);
+ }
+ } else {
+ addModification(r1,s1,r2,s2);
+ }
+ } else {
+ // Exact match, nothing to do.
+ if (!a1 && !a2)
+ addComparable(s1, s2);
+ }
}
} else {
addModification(r1,s1,r2,s2);
- if (!s1.isAsserted(r1) && !s2.isAsserted(r2))
- addComparable(s1, s2);
}
i1++;
i2++;
}
case -1:{
if (DEBUG) System.out.println("Compare Prop diff1s " + printStatement(g,s1));
- addDeletion(s1);
+ // Use modification, since deletions do not support asserted statements
+ addModification(r1,s1,r2,null);
+ //addDeletion(s1);
i1++;
break;
}
case 1:{
if (DEBUG) System.out.println("Compare Prop diff2s " + printStatement(g,s2));
- addAddition(s2);
+ // Use modification, since additions do not support asserted statements
+ addModification(r1,null,r2,s2);
+ //addAddition(s2);
i2++;
break;
}