1 /*******************************************************************************
2 * Copyright (c) 2007, 2010 Association for Decentralized Information Management
4 * All rights reserved. This program and the accompanying materials
5 * are made available under the terms of the Eclipse Public License v1.0
6 * which accompanies this distribution, and is available at
7 * http://www.eclipse.org/legal/epl-v10.html
10 * Foster Wheeler Energia Oy - initial API and implementation
11 *******************************************************************************/
12 package org.simantics.interop.test;
14 import java.util.ArrayList;
15 import java.util.Arrays;
16 import java.util.Collection;
17 import java.util.Collections;
18 import java.util.Comparator;
19 import java.util.HashMap;
20 import java.util.HashSet;
21 import java.util.List;
23 import java.util.Map.Entry;
25 import java.util.Stack;
27 import org.simantics.databoard.Bindings;
28 import org.simantics.db.ReadGraph;
29 import org.simantics.db.Resource;
30 import org.simantics.db.Session;
31 import org.simantics.db.Statement;
32 import org.simantics.db.common.request.ReadRequest;
33 import org.simantics.db.common.utils.NameUtils;
34 import org.simantics.db.exception.DatabaseException;
35 import org.simantics.layer0.Layer0;
36 import org.simantics.utils.datastructures.BijectionMap;
37 import org.simantics.utils.datastructures.MapList;
38 import org.simantics.utils.datastructures.Pair;
41 * Compares two subgraphs and reports differences.
43 * Assumes that subgraphs (defined using traverse relations) are not cyclic.
45 * Assumes that properties can be used to identify objects, if relation type is not enough.
49 * @author Marko Luukkainen <marko.luukkainen@vtt.fi>
52 public class GraphComparator {
54 private static final boolean DEBUG = false;
58 private Set<Resource> strong = new HashSet<Resource>(); // List of relations that identify object, if subject is already identified.
59 private List<Resource> traversed = new ArrayList<Resource>(); // list of relations that are traversed (and tested)
60 private List<Resource> tested = new ArrayList<Resource>(); // list of relations that are tested, but not traversed
61 private List<Resource> nonTraversed = new ArrayList<Resource>(); // list of relations that are not traversed
62 private List<Resource> nonTested = new ArrayList<Resource>(); // list of relations that are not tested
64 private List<Statement> changes1 = new ArrayList<Statement>();
65 private List<Statement> changes2 = new ArrayList<Statement>();
66 private List<Pair<Statement,Statement>> modifications = new ArrayList<Pair<Statement,Statement>>();
67 private Set<Statement> changes1Set = new HashSet<Statement>();
68 private Set<Statement> changes2Set = new HashSet<Statement>();
69 private Set<Pair<Statement,Statement>> modificationsSet = new HashSet<Pair<Statement,Statement>>();
71 private BijectionMap<Statement, Statement> comparableStatements = new BijectionMap<Statement, Statement>();
72 private BijectionMap<Resource, Resource> comparableResources = new BijectionMap<Resource, Resource>();
74 private Set<Resource> processedResources = new HashSet<Resource>();
76 private ResourceComparator comparator;
78 private Comparator<Statement> scomp = new PredicateComparator();
79 private Comparator<Resource> rcomp = new ResComparator();
81 private Set<Resource> nonMatchedLeft = new HashSet<Resource>();
82 private Set<Resource> nonMatchedRight = new HashSet<Resource>();
89 public GraphComparator(Resource r1, Resource r2) {
92 comparator = new TypeComparator();
95 public GraphComparator(Resource r1, Resource r2, ResourceComparator comparator) {
98 this.comparator = comparator;
101 ArrayList<Statement> ss1 = new ArrayList<Statement>();
102 ArrayList<Statement> ss2 = new ArrayList<Statement>();
105 public Comparator<Resource> getResourceComparator() {
109 public Comparator<Statement> getStatementComparator() {
113 public Resource getR1() {
117 public Resource getR2() {
121 public void addTraversed(Resource rel) {
125 public void addTraversed(Collection<Resource> rels) {
126 traversed.addAll(rels);
129 public void addNonTraversed(Resource rel) {
130 nonTraversed.add(rel);
133 public void addNonTraversed(Collection<Resource> rels) {
134 nonTraversed.addAll(rels);
137 public void addTested(Resource rel) {
141 public void addTested(Collection<Resource> rels) {
145 public void addNonTested(Resource rel) {
149 public void addNonTested(Collection<Resource> rels) {
150 nonTested.addAll(rels);
153 public void addComparableResources(Resource r1, Resource r2) {
154 comparableResources.map(r1, r2);
157 public void addComparableResources(BijectionMap<Resource, Resource> matching) {
158 comparableResources.addAll(matching);
161 public void addStrong(Resource r) {
165 public void addStrong(Collection<Resource> rels) {
169 public void addNonMatchedLeft(Resource r) {
170 nonMatchedLeft.add(r);
173 public void addNonMatchedRight(Resource r) {
174 nonMatchedRight.add(r);
177 public void test(ReadGraph g) throws DatabaseException {
179 this.b = Layer0.getInstance(g);
180 comparator.setComparator(this);
182 Stack<Resource> objectsLeft = new Stack<Resource>();
183 Stack<Resource> objectsRight = new Stack<Resource>();
184 objectsLeft.push(r1);
185 objectsRight.push(r2);
187 Set<Statement> unreliableLeft = new HashSet<Statement>();
188 Set<Statement> unreliableRight = new HashSet<Statement>();
191 if (objectsLeft.isEmpty())
195 // process compares objects that are identified and searches for more resources to process.
196 process(objectsLeft, objectsRight, unreliableLeft, unreliableRight);
197 // process unreliable handles cases where unidentified statements subject and object have been identified
198 processUnreliable(unreliableLeft, unreliableRight);
199 // process unreliable handles cases where unidentified resources have path of length one to identified resource
200 processUnreliable(unreliableLeft, unreliableRight,objectsLeft,objectsRight);
201 if (objectsLeft.isEmpty() && unreliableLeft.size() > 0 && unreliableRight.size() > 0) {
202 processUnreliable2(unreliableLeft, unreliableRight,objectsLeft,objectsRight);
204 if (objectsLeft.isEmpty() && unreliableLeft.size() > 0 && unreliableRight.size() > 0) {
205 // comparison is ending, but we have still unprocessed unidentified resources left.
206 // These cases have longer path than one to identified objects.
207 processUnreliableDeep(unreliableLeft, unreliableRight, objectsLeft, objectsRight);
211 for (Statement s : unreliableLeft) {
212 if (!comparableStatements.containsLeft(s))
215 for (Statement s : unreliableRight) {
216 if (!comparableStatements.containsRight(s))
221 public void test(Session session) throws DatabaseException {
222 test(session, r1, r2);
225 public void test(Session session, Resource r1, Resource r2) throws DatabaseException {
227 comparator.setComparator(this);
229 addComparable(r1, r2);
231 final Stack<Resource> objectsLeft = new Stack<Resource>();
232 final Stack<Resource> objectsRight = new Stack<Resource>();
233 objectsLeft.push(r1);
234 objectsRight.push(r2);
236 final Set<Statement> unreliableLeft = new HashSet<Statement>();
237 final Set<Statement> unreliableRight = new HashSet<Statement>();
240 if (objectsLeft.isEmpty())
242 session.syncRequest(new ReadRequest() {
245 public void run(ReadGraph graph) throws DatabaseException {
247 b = Layer0.getInstance(graph);
248 // process compares objects that are identified and searches for more resources to process.
249 process(objectsLeft, objectsRight, unreliableLeft, unreliableRight);
250 // process unreliable handles cases where unidentified statements subject and object have been identified
251 processUnreliable(unreliableLeft, unreliableRight);
252 // process unreliable handles cases where unidentified resources have path of length one to identified resource
253 processUnreliable(unreliableLeft, unreliableRight,objectsLeft,objectsRight);
254 if (objectsLeft.isEmpty() && unreliableLeft.size() > 0 && unreliableRight.size() > 0) {
255 processUnreliable2(unreliableLeft, unreliableRight,objectsLeft,objectsRight);
257 if (objectsLeft.isEmpty() && unreliableLeft.size() > 0 && unreliableRight.size() > 0) {
258 // comparison is ending, but we have still unprocessed unidentified resources left.
259 // These cases have longer path than one to identified objects.
260 processUnreliableDeep(unreliableLeft, unreliableRight, objectsLeft, objectsRight);
268 for (Statement s : unreliableLeft) {
269 if (!comparableStatements.containsLeft(s))
270 if (s.getObject().getResourceId() == 303248)
271 System.out.println();
274 for (Statement s : unreliableRight) {
275 if (!comparableStatements.containsRight(s))
282 private void process(Stack<Resource> objectsLeft, Stack<Resource> objectsRight, Set<Statement> unreliableLeft, Set<Statement> unreliableRight) throws DatabaseException {
283 List<Statement> ss1 = new ArrayList<Statement>();
284 List<Statement> ss2 = new ArrayList<Statement>();
286 while (!objectsLeft.isEmpty()) {
287 Resource r1 = objectsLeft.pop();
288 Resource r2 = objectsRight.pop();
293 if (processedResources.contains(r1))
295 processedResources.add(r1);
298 if((comparableResources.containsLeft(r1)||comparableResources.containsRight(r2)) && !comparableResources.contains(r1, r2)) {
299 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.");
301 addComparable(r1, r2);
303 //System.out.println("test " + NameUtils.getSafeName(g, r1) + " " + NameUtils.getSafeName(g, r2));
304 compareProps(r1, r2);
306 for (Resource rel : tested) {
307 ss1.addAll(g.getStatements(r1, rel));
308 ss2.addAll(g.getStatements(r2, rel));
309 ss1 = filterAsserted(r1, ss1);
310 ss2 = filterAsserted(r2, ss2);
311 ss1 = filterTraversed(ss1);
312 ss2 = filterTraversed(ss2);
313 ss1 = filterNonTested(ss1);
314 ss2 = filterNonTested(ss2);
317 compareStatements(ss1, ss2, null, null,null,null);
322 for (Resource rel : traversed) {
323 ss1.addAll(g.getStatements(r1, rel));
324 ss2.addAll(g.getStatements(r2, rel));
325 ss1 = filterAsserted(r1, ss1);
326 ss2 = filterAsserted(r2, ss2);
327 ss1 = filterNonTraversed(ss1);
328 ss2 = filterNonTraversed(ss2);
329 compareStatements(ss1, ss2, objectsLeft, objectsRight,unreliableLeft,unreliableRight);
337 private void processUnreliable(Set<Statement> unreliableLeft, Set<Statement> unreliableRight) throws DatabaseException {
338 MapList<Resource,Statement> subjectLeft = new MapList<Resource, Statement>();
339 MapList<Resource,Statement> subjectRight = new MapList<Resource, Statement>();
340 MapList<Resource,Statement> objectLeft = new MapList<Resource, Statement>();
341 MapList<Resource,Statement> objectRight = new MapList<Resource, Statement>();
343 for (Statement s : unreliableLeft) {
344 subjectLeft.add(s.getSubject(),s);
345 objectLeft.add(s.getObject(),s);
347 for (Statement s : unreliableRight) {
348 subjectRight.add(s.getSubject(),s);
349 objectRight.add(s.getObject(),s);
352 for (Resource left : subjectLeft.getKeys()) {
353 Resource right = comparableResources.getRight(left);
356 for (Statement leftS : subjectLeft.getValues(left)) {
357 Resource leftO = leftS.getObject();
358 if (!unreliableLeft.contains(leftS))
360 Resource rightO = comparableResources.getRight(leftO);
363 for (Statement rightS : subjectRight.getValues(right)) {
364 if (!rightS.getObject().equals(rightO))
366 if (!unreliableRight.contains(rightS))
368 if (leftS.getPredicate().equals(rightS.getPredicate()) ||
369 comparableResources.contains(leftS.getPredicate(), rightS.getPredicate())) {
370 unreliableLeft.remove(leftS);
371 unreliableRight.remove(rightS);
372 addComparable(leftS, rightS);
379 private void processUnreliable(Set<Statement> unreliableLeft, Set<Statement> unreliableRight, Stack<Resource> objectsLeft, Stack<Resource> objectsRight) throws DatabaseException {
380 MapList<Resource,Statement> subjectLeft = new MapList<Resource, Statement>();
381 MapList<Resource,Statement> subjectRight = new MapList<Resource, Statement>();
382 MapList<Resource,Statement> objectLeft = new MapList<Resource, Statement>();
383 MapList<Resource,Statement> objectRight = new MapList<Resource, Statement>();
385 for (Statement s : unreliableLeft) {
386 subjectLeft.add(s.getSubject(),s);
387 objectLeft.add(s.getObject(),s);
389 for (Statement s : unreliableRight) {
390 subjectRight.add(s.getSubject(),s);
391 objectRight.add(s.getObject(),s);
394 for (Resource ol : objectLeft.getKeys()) {
395 // all statements to the left side object
396 List<Statement> left = objectLeft.getValues(ol);
397 // all subjects that have statements to the left side object (ol)
398 Set<Resource> sLeft = new HashSet<Resource>();
399 // all matching subjects on the right side
400 Set<Resource> sRight = new HashSet<Resource>();
401 for (Statement s : left) {
402 sLeft.add(s.getSubject());
403 sRight.add(comparableResources.getRight(s.getSubject()));
406 // check if object left can be reliably identified by available statements
407 // if there are any objects on the left side with similar statements, object left cannot be mapped.
408 boolean hasSimilar = false;
409 MapList<Resource, Statement> comparableOLeft = new MapList<Resource, Statement>();
410 for (Resource sl : sLeft) {
411 for (Statement s : subjectLeft.getValues(sl)) {
412 if (!s.getObject().equals(ol)) {
413 comparableOLeft.add(s.getObject(),s);
418 compareStatements(ss1, ss2, objectsLeft, objectsRight,unreliableLeft,unreliableRight);
420 for (Resource similarOl : comparableOLeft.getKeys()) {
421 List<Statement> similarLeft = comparableOLeft.getValues(similarOl);
422 if (similarLeft.size() == left.size()) {
423 boolean useL[] = new boolean[left.size()];
424 boolean useSL[] = new boolean[left.size()];
425 for (int i = 0; i < left.size(); i++) {
429 for (int i = 0; i < left.size(); i++) {
430 for (int j = 0; j < left.size(); j++) {
433 // compare predicates
434 Resource pl = left.get(i).getPredicate();
435 Resource psl = similarLeft.get(j).getPredicate();
436 if (pl.equals(psl)) {
437 // compare objects (unreliable result is interpreted as positive match)
439 int comp = comparator.compare(g, left.get(i).getObject(), similarLeft.get(j).getObject(), true);
440 if (comp >= 0 && comp < Integer.MAX_VALUE) {
448 boolean diff = false;
449 for (int i = 0; i < left.size(); i++) {
450 if (!useL[i] || !useSL[i]) {
465 // all objects that subjects on the right side point to. Object left has its matching resource among these, if it has matching resource
466 MapList<Resource,Statement> possibleOR = new MapList<Resource, Statement>();
467 for (Resource sr : sRight) {
468 for (Statement s : subjectRight.getValues(sr))
469 possibleOR.add(s.getObject(),s);
472 // filter possible right side objects to those that have same amount of statements as the left side object
473 for (Resource or : possibleOR.getKeys().toArray(new Resource[possibleOR.getKeys().size()])) {
474 List<Statement> right = possibleOR.getValues(or);
475 if (right.size() != left.size())
476 possibleOR.remove(or);
480 // check for matching statements (comparable subjects, matching predicates)
481 MapList<Resource,Statement> matchingOR = new MapList<Resource, Statement>(); // list of objects that have matching statements
482 Map<Resource,Pair<int[], int[]>> matchingStatements = new HashMap<Resource, Pair<int[], int[]>>(); // matching statements
483 for (Resource or : possibleOR.getKeys()) {
484 List<Statement> right = possibleOR.getValues(or);
485 int iLeft[] = new int[left.size()];
486 int iRight[] = new int[right.size()];
488 for (int i = 0; i < left.size(); i++) {
493 for (int l = 0; l < left.size(); l++) {
494 Statement ls = left.get(l);
495 for (int r = 0; r < right.size(); r++) {
498 Statement rs = right.get(r);
499 if (!comparableResources.contains(ls.getSubject(), rs.getSubject()))
501 if (rcomp.compare(ls.getPredicate(),rs.getPredicate()) == 0) {
502 // compare objects (unreliable result is not accepted)
503 int comp = comparator.compare(g, ls.getObject(), rs.getObject());
504 if (comp > 0 && comp < Integer.MAX_VALUE) {
514 boolean success = true;
515 for (int i = 0; i < left.size(); i++) {
527 for (Statement s : right)
528 matchingOR.add(or,s);
529 matchingStatements.put(or, new Pair<int[], int[]>(iLeft, iRight));
532 // if there is only one matching right side object, we have found a match
533 if (matchingOR.getKeySize() == 1) {
534 Resource or = matchingOR.getKeys().iterator().next();
535 List<Statement> right = matchingOR.getValues(or);
536 Pair<int[], int[]> indices = matchingStatements.get(or);
539 objectsRight.add(or);
540 addComparable(ol, or);
541 for (int l = 0; l < left.size(); l++) {
542 int r = indices.first[l];
543 Statement sl = left.get(l);
544 Statement sr = right.get(r);
545 addComparable(sl, sr);
546 unreliableLeft.remove(sl);
547 unreliableRight.remove(sr);
559 private void processUnreliable2(Set<Statement> unreliableLeft, Set<Statement> unreliableRight, Stack<Resource> objectsLeft, Stack<Resource> objectsRight) throws DatabaseException {
560 MapList<Resource,Statement> subjectLeft = new MapList<Resource, Statement>();
561 MapList<Resource,Statement> subjectRight = new MapList<Resource, Statement>();
562 MapList<Resource,Statement> objectLeft = new MapList<Resource, Statement>();
563 MapList<Resource,Statement> objectRight = new MapList<Resource, Statement>();
565 for (Statement s : unreliableLeft) {
566 subjectLeft.add(s.getSubject(),s);
567 objectLeft.add(s.getObject(),s);
569 for (Statement s : unreliableRight) {
570 subjectRight.add(s.getSubject(),s);
571 objectRight.add(s.getObject(),s);
574 for (Resource ol : objectLeft.getKeys()) {
575 // all statements to the left side object
576 List<Statement> left = objectLeft.getValues(ol);
577 // all subjects that have statements to the left side object (ol)
578 Set<Resource> sLeft = new HashSet<Resource>();
579 // all matching subjects on the right side
580 Set<Resource> sRight = new HashSet<Resource>();
581 for (Statement s : left) {
582 sLeft.add(s.getSubject());
583 sRight.add(comparableResources.getRight(s.getSubject()));
586 if (sLeft.size() == 1 && sRight.size() == 1) {
587 List<Statement> ss1 = new ArrayList<Statement>(subjectLeft.getValues(sLeft.iterator().next()));
588 List<Statement> ss2 = new ArrayList<Statement>(subjectRight.getValues(sRight.iterator().next()));
590 int count = comparableStatements.size();
591 compareStatements(ss1, ss2, objectsLeft, objectsRight,unreliableLeft,unreliableRight);
592 if (comparableStatements.size() > count) {
593 for (Entry<Statement, Statement> entry : comparableStatements.getEntries()) {
594 unreliableLeft.remove(entry.getKey());
595 unreliableRight.remove(entry.getValue());
602 private void processUnreliableDeep(Set<Statement> unreliableLeft, Set<Statement> unreliableRight, Stack<Resource> objectsLeft, Stack<Resource> objectsRight) throws DatabaseException {
603 MapList<Resource,Statement> subjectLeft = new MapList<Resource, Statement>();
604 MapList<Resource,Statement> subjectRight = new MapList<Resource, Statement>();
605 MapList<Resource,Statement> objectLeft = new MapList<Resource, Statement>();
606 MapList<Resource,Statement> objectRight = new MapList<Resource, Statement>();
608 for (Statement s : unreliableLeft) {
609 subjectLeft.add(s.getSubject(),s);
610 objectLeft.add(s.getObject(),s);
612 for (Statement s : unreliableRight) {
613 subjectRight.add(s.getSubject(),s);
614 objectRight.add(s.getObject(),s);
616 for (Resource ol : objectLeft.getKeys()) {
617 Set<Path> pathsLeft = new HashSet<Path>();
618 for (Resource rel : traversed) {
619 pathsLeft.addAll(Path.create(g.getStatements(ol, rel)));
623 if (pathsLeft.size() == 0)
625 Collection<Path> endPaths = new ArrayList<Path>(1);
626 for (Path p : pathsLeft) {
627 if (comparableResources.containsLeft(p.getEnd())) {
631 if (endPaths.size() > 0) {
633 pathsLeft.addAll(endPaths);
637 if (pathsLeft.size() > 0) {
638 Resource sl = objectLeft.getValues(ol).get(0).getSubject();
639 Resource sr = comparableResources.getRight(sl);
640 Collection<Resource> possibleOR = new ArrayList<Resource>();
641 for (Statement s : subjectRight.getValues(sr)) {
642 possibleOR.add(s.getObject());
644 Map<Resource,Set<Path>> matchingPaths = new HashMap<Resource, Set<Path>>();
645 for (Resource or : possibleOR) {
646 Set<Path> possiblePathsRight = new HashSet<Path>();
647 for (Path leftPath : pathsLeft) {
648 possiblePathsRight.addAll(findComparableRight(leftPath, or));
650 if (hasMatchingPaths(pathsLeft, possiblePathsRight)) {
651 matchingPaths.put(or, possiblePathsRight);
654 if (matchingPaths.size() > 0) {
655 if (matchingPaths.size() == 1) {
656 Resource or = matchingPaths.keySet().iterator().next();
659 objectsRight.add(or);
660 addComparable(ol, or);
661 Collection<Statement> statementsLeft = objectLeft.getValues(ol);
662 Collection<Statement> statementsRight = objectRight.getValues(or);
663 unreliableLeft.removeAll(statementsLeft);
664 unreliableRight.removeAll(statementsRight);
665 BijectionMap<Path,Path> map = getMatchingPaths(pathsLeft, matchingPaths.get(or));
666 for (Path left : map.getLeftSet()) {
667 Path right = map.getRight(left);
668 for (int i = 0; i < left.getLength(); i++) {
669 addComparable(left.getStatements().get(i),right.getStatements().get(i));
680 private boolean hasMatchingPaths(Set<Path> leftPaths, Set<Path> rightPaths) {
681 if (leftPaths.size() != rightPaths.size())
683 BijectionMap<Path,Path> map = getMatchingPaths(leftPaths, rightPaths);
684 return map.size() == leftPaths.size();
687 private BijectionMap<Path,Path> getMatchingPaths(Set<Path> leftPaths, Set<Path> rightPaths) {
688 BijectionMap<Path,Path> map = new BijectionMap<Path, Path>();
689 for (Path leftPath : leftPaths) {
690 for (Path rightPath : rightPaths) {
691 if (map.containsRight(rightPath))
693 if (leftPath.getLength() != rightPath.getLength())
695 if (comparableResources.contains(leftPath.getEnd(), rightPath.getEnd())) {
696 map.map(leftPath, rightPath);
704 private void expand(Set<Path> paths) throws DatabaseException {
705 Set<Path> stepPathsLeft = new HashSet<Path>();
706 if (paths.size() == 0)
708 int length = paths.iterator().next().getLength() + 1;
709 for (Path p : paths) {
710 for (Resource rel : traversed) {
711 stepPathsLeft.addAll(Path.expand(p,g.getStatements(p.getEnd(), rel)));
715 for (Path p : stepPathsLeft) {
716 if (p.getLength() == length)
721 private Collection<Path> findComparableRight(Path leftPath, Resource beginRight) throws DatabaseException {
722 Set<Path> rightPaths = new HashSet<Path>();
723 rightPaths.addAll(Path.create(g.getStatements(beginRight, getRight(leftPath.getStatements().get(0).getPredicate()))));
724 for (int i = 1; i < leftPath.getLength(); i++) {
725 if (rightPaths.size() == 0)
727 Set<Path> stepPaths = new HashSet<Path>();
728 for (Path p : rightPaths) {
729 stepPaths.addAll(Path.expand(p, g.getStatements(p.getEnd(), getRight(leftPath.getStatements().get(i).getPredicate()))));
732 for (Path p : stepPaths)
733 if (p.getLength() == i+1)
740 private Resource getRight(Resource r) {
741 if (comparableResources.containsLeft(r))
742 return comparableResources.getRight(r);
748 public BijectionMap<Statement, Statement> getComparableStatements() {
749 return comparableStatements;
752 public BijectionMap<Resource, Resource> getComparableResources() {
753 return comparableResources;
756 public GraphChanges getChanges() {
757 return new GraphChanges(r1,r2,changes1,changes2,modifications,comparableResources);
760 private void addComparable(Statement left, Statement right) throws DatabaseException {
761 addComparable(left.getObject(), right.getObject());
762 comparableStatements.map(left, right);
763 //comparableResources.map(left.getObject(), right.getObject());
766 private void addComparable(Resource left, Resource right) throws DatabaseException {
767 if(!comparableResources.contains(left, right)) {
768 if (comparableResources.containsLeft(left)||comparableResources.containsRight(right)) {
769 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.");
771 if (DEBUG) System.out.println(left + " = " + right);
772 comparableResources.map(left, right);
778 public List<Statement> filterAsserted(Resource r, Collection<Statement> in) throws DatabaseException {
779 List<Statement> out = new ArrayList<Statement>();
780 for (Statement s : in) {
781 if (!s.isAsserted(r))
790 private String printStatement(ReadGraph graph, Statement s) throws DatabaseException {
791 return NameUtils.getSafeName(graph, s.getSubject()) + " " + NameUtils.getSafeName(graph, s.getPredicate()) + " " + NameUtils.getSafeName(graph, s.getObject());
794 private List<Statement> filterTraversed(List<Statement> in) throws DatabaseException {
795 return filter(traversed, in);
798 private List<Statement> filterNonTested(List<Statement> in) throws DatabaseException {
799 return filter(nonTested, in);
802 private List<Statement> filterNonTraversed(List<Statement> in) throws DatabaseException {
803 return filter(nonTraversed, in);
806 private List<Statement> filter(Collection<Resource> toFilter, List<Statement> in) throws DatabaseException {
807 if (toFilter.size() == 0)
809 List<Statement> out = new ArrayList<Statement>();
810 for (Statement s : in) {
811 boolean usable = true;
812 for (Resource r : toFilter) {
813 if (g.isSubrelationOf(s.getPredicate(),r)) {
827 private void addDeletion(Statement s) {
828 if (!changes1Set.contains(s)) {
834 private void addAddition(Statement s) {
835 if (!changes2Set.contains(s)) {
841 private void addModification(Statement s1, Statement s2) {
842 Pair<Statement, Statement> mod = new Pair<Statement, Statement>(s1,s2);
843 if (!modificationsSet.contains(mod)) {
844 modificationsSet.add(mod);
845 modifications.add(mod);
849 public void sortStatement(List<Statement> list1, List<Statement> list2) {
850 sortStatement(list1, list2, scomp);
853 public void sortStatement(List<Statement> list1, List<Statement> list2, Comparator<Statement> scomp) {
854 Collections.sort(list1,scomp);
855 Collections.sort(list2,scomp);
857 List<Statement> sorted1 = new ArrayList<Statement>(list1.size());
858 List<Statement> sorted2 = new ArrayList<Statement>(list2.size());
859 sorted1.addAll(list1);
860 sorted2.addAll(list2);
864 for (int i = 0; i < list1.size(); ) {
865 Statement s1 = list1.get(i);
866 int same1 = sameRel(list1, i);
867 for (int j = 0; j < list2.size(); j++) {
868 Statement s2 = list2.get(j);
869 if (scomp.compare(s1, s2) == 0) {
870 int same2 = sameRel(list2, j);
871 copy(sorted1,ss1,list1,i,same1);
873 copy(sorted2,ss2,list2,j,same2);
880 if (ss1 < sorted1.size()) {
881 for (Statement s : list1) {
882 if (!sorted1.contains(s)) {
888 if (ss2 < sorted2.size()) {
889 for (Statement s : list2) {
890 if (!sorted2.contains(s)) {
899 list1.addAll(sorted1);
900 list2.addAll(sorted2);
903 public <T> void copy(List<T> to, int toIndex, List<T> from, int fromIndex, int amount) {
904 for (int i = 0; i < amount; i++) {
905 to.set(toIndex + i, from.get(fromIndex+ i));
909 public void sortResource(List<Resource> list1, List<Resource> list2) {
910 Collections.sort(list1,rcomp);
912 for (int i = 0; i < list1.size(); i++) {
913 Resource s1 = list1.get(i);
914 for (int j = js; j < list2.size(); j++) {
915 Resource s2 = list2.get(j);
916 if (rcomp.compare(s1, s2) == 0) {
917 Resource t = list2.get(js);
927 private void compareStatements(List<Statement> ss1, List<Statement> ss2, Stack<Resource> objectsLeft, Stack<Resource> objectsRight, Collection<Statement> unreliableLeft, Collection<Statement> unreliableRight) throws DatabaseException {
928 sortStatement(ss1, ss2);
934 if (i1 >= ss1.size()) {
935 if (i2 >= ss2.size()) {
938 while (i2 < ss2.size()) {
939 if (DEBUG) System.out.println("Compare Statements addition " + printStatement(g,ss2.get(i2)));
941 addAddition(ss2.get(i2));
946 } else if (i2 >= ss2.size()) {
947 while (i1 < ss1.size()) {
948 if (DEBUG) System.out.println("Compare Statements deletion " + printStatement(g,ss1.get(i1)));
949 addDeletion(ss1.get(i1));
954 int same1 = sameRel(ss1, i1);
955 int same2 = sameRel(ss2, i2);
956 int c = rcomp.compare(ss1.get(i1).getPredicate(),ss2.get(i2).getPredicate());
958 compareStatements(ss1, i1, same1, ss2, i2, same2,objectsLeft,objectsRight,unreliableLeft,unreliableRight);
962 for (int i = 0; i < same1; i++) {
963 if (DEBUG) System.out.println("Compare Statements deletion " + printStatement(g,ss1.get(i+i1)));
964 addDeletion(ss1.get(i+i1));
968 for (int i = 0; i < same2; i++) {
969 if (DEBUG) System.out.println("Compare Statements addition " + printStatement(g,ss2.get(i+i2)));
970 addAddition(ss2.get(i+i2));
980 private int sameRel(List<Statement> statements, int off) {
981 if (statements.size() <= off)
984 long id = statements.get(off).getPredicate().getResourceId();
985 for (int i = off+1; i <statements.size(); i++) {
986 if (statements.get(i).getPredicate().getResourceId() == id)
995 private int compareObject(Resource o1, Resource o2) throws DatabaseException {
998 if (comparableResources.contains(o1, o2))
1000 if (comparableResources.containsLeft(o1))
1001 return Integer.MAX_VALUE;
1002 if (comparableResources.containsRight(o2))
1003 return Integer.MAX_VALUE;
1004 if (nonMatchedLeft.contains(o1))
1005 return Integer.MAX_VALUE;
1006 if (nonMatchedRight.contains(o2))
1007 return Integer.MAX_VALUE;
1008 return comparator.compare(g, o1, o2);
1011 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 {
1012 boolean[] used1 = new boolean[len1];
1013 for (int i = 0; i < used1.length; i++) {
1017 boolean[] used2 = new boolean[len2];
1018 for (int i = 0; i < used2.length; i++) {
1022 // left, right, difference
1023 List<List<Integer>> differences = new ArrayList<List<Integer>>();
1024 for (int i1 = off1; i1 < off1 + len1; i1++) {
1025 Statement s1 = ss1.get(i1);
1026 List<Integer> diff = new ArrayList<Integer>();
1027 for (int i2 = off2; i2 < off2 + len2; i2++) {
1028 Statement s2 = ss2.get(i2);
1029 int d = compareObject(s1.getObject(), s2.getObject());
1031 for (Resource t : strong) {
1032 if (s1.getPredicate().equals(t) || g.isSubrelationOf(s1.getPredicate(), t)) {
1040 differences.add(diff);
1043 MapList<Integer, Integer> priorities = new MapList<Integer, Integer>();
1044 for (int i = 0; i < differences.size(); i++) {
1045 List<Integer> list = differences.get(i);
1046 for (int j = 0; j < list.size(); j++) {
1047 priorities.add(list.get(j), i);
1051 Integer[] pris = priorities.getKeys(new Integer[]{});
1054 for (Integer pri : pris) {
1055 if (pri == Integer.MAX_VALUE) {
1057 } else if (pri == 0) {
1060 List<Integer> i1s = priorities.getValues(pri);
1061 for (Integer i1 : i1s) {
1064 List<Integer> i2diff = differences.get(i1);
1065 for (int i2 = 0; i2 < i2diff.size(); i2++) {
1066 if (i2diff.get(i2) == pri) {
1071 Statement s1 = ss1.get(i1+off1);
1072 Statement s2 = ss2.get(i2+off2);
1074 if (objectsLeft != null) {
1075 objectsLeft.add(s1.getObject());
1076 objectsRight.add(s2.getObject());
1078 addComparable(s1, s2);
1086 for (Integer pri : pris) {
1089 Set<Statement> s1s = new HashSet<Statement>();
1090 Set<Statement> s2s = new HashSet<Statement>();
1091 Set<Integer> s1i = new HashSet<Integer>();
1092 Set<Integer> s2i = new HashSet<Integer>();
1093 List<Integer> i1s = priorities.getValues(pri);
1094 for (Integer i1 : i1s) {
1097 List<Integer> i2diff = differences.get(i1);
1098 for (int i2 = 0; i2 < i2diff.size(); i2++) {
1099 if (i2diff.get(i2) == pri) {
1102 Statement s1 = ss1.get(i1+off1);
1103 Statement s2 = ss2.get(i2+off2);
1111 if (unreliableLeft != null) {
1112 unreliableLeft.addAll(s1s);
1113 unreliableRight.addAll(s2s);
1115 for (Integer i : s1i)
1117 for (Integer i : s2i)
1121 for (int i1 = off1; i1 < off1 + len1; i1++) {
1122 if (!used1[i1-off1]) {
1123 if (DEBUG) System.out.println("Compare Object deletion " + printStatement(g,ss1.get(i1)));
1124 addDeletion(ss1.get(i1));
1127 for (int i2 = off2; i2 < off2 + len2; i2++) {
1128 if (!used2[i2-off2]) {
1129 if (DEBUG) System.out.println("Compare Object addition " + printStatement(g,ss2.get(i2)));
1130 addAddition(ss2.get(i2));
1138 * compares properties, assumes functional relations
1141 * @throws ServiceException
1142 * @throws DoesNotContainValueException
1143 * @throws ValidationException
1145 private void compareProps(Resource r1, Resource r2) throws DatabaseException {
1146 if (DEBUG) System.out.println("compareProps " + r1 + " " + NameUtils.getSafeName(g, r1) + " " + r2 + " " + NameUtils.getSafeName(g, r2));
1147 List<Statement> ss1 = new ArrayList<Statement>();
1148 List<Statement> ss2 = new ArrayList<Statement>();
1149 ss1.addAll(g.getStatements(r1, b.HasProperty));
1150 ss2.addAll(g.getStatements(r2, b.HasProperty));
1151 ss1 = filterNonTested(ss1);
1152 ss2 = filterNonTested(ss2);
1153 sortStatement(ss1, ss2);
1159 if (i1 >= ss1.size()) {
1160 if (i2 >= ss2.size())
1163 while (i2 < ss2.size()) {
1164 if (DEBUG) System.out.println("Compare Prop diff2 " + printStatement(g,ss2.get(i2)));
1165 addAddition(ss2.get(i2));
1170 } else if (i2 >= ss2.size()) {
1171 while (i1 < ss1.size()) {
1172 if (DEBUG) System.out.println("Compare Prop diff1 " + printStatement(g,ss1.get(i1)));
1173 addDeletion(ss1.get(i1));
1178 Statement s1 = ss1.get(i1);
1179 Statement s2 = ss2.get(i2);
1180 if (s1.isAsserted(r1) && s2.isAsserted(r2)) {
1185 int c = scomp.compare(s1, s2);
1188 boolean b1 = g.hasValue(s1.getObject());
1189 boolean b2 = g.hasValue(s2.getObject());
1192 // Object v1 = g.getValue(s1.getObject());
1193 // Object v2 = g.getValue(s2.getObject());
1194 // boolean eq = compareValue(v1, v2);
1195 boolean eq = compareValue(g,b,s1.getObject(), s2.getObject());
1197 addModification(s1, s2);
1198 addComparable(s1, s2);
1201 if (!s1.getObject().equals(s1.getSubject()) && !s2.getObject().equals(s2.getSubject()))
1202 compareProps(s1.getObject(), s2.getObject());
1205 addModification(s1, s2);
1206 addComparable(s1, s2);
1213 if (DEBUG) System.out.println("Compare Prop diff1s " + printStatement(g,s1));
1220 if (DEBUG) System.out.println("Compare Prop diff2s " + printStatement(g,s2));
1234 public static boolean compareValue(ReadGraph g, Layer0 b, Resource r1, Resource r2) throws DatabaseException {
1235 Resource t1 = g.getSingleType(r1);
1236 Resource t2 = g.getSingleType(r2);
1239 if (t1.equals(b.Integer)) {
1240 int v1 = g.getValue(r1, Bindings.INTEGER);
1241 int v2 = g.getValue(r2, Bindings.INTEGER);
1243 } else if (t1.equals(b.Float)) {
1244 float v1 = g.getValue(r1, Bindings.FLOAT);
1245 float v2 = g.getValue(r2, Bindings.FLOAT);
1247 } else if (t1.equals(b.Double)) {
1248 double v1 = g.getValue(r1, Bindings.DOUBLE);
1249 double v2 = g.getValue(r2, Bindings.DOUBLE);
1251 } else if (t1.equals(b.String)) {
1252 String v1 = g.getValue(r1, Bindings.STRING);
1253 String v2 = g.getValue(r2, Bindings.STRING);
1254 return v1.equals(v2);
1255 } else if (t1.equals(b.Boolean)) {
1256 boolean v1 = g.getValue(r1, Bindings.BOOLEAN);
1257 boolean v2 = g.getValue(r2, Bindings.BOOLEAN);
1259 } else if (t1.equals(b.Byte)) {
1260 byte v1 = g.getValue(r1, Bindings.BYTE);
1261 byte v2 = g.getValue(r2, Bindings.BYTE);
1263 } else if (t1.equals(b.Long)) {
1264 long v1 = g.getValue(r1, Bindings.LONG);
1265 long v2 = g.getValue(r2, Bindings.LONG);
1267 } else if (t1.equals(b.IntegerArray)) {
1268 int[] v1 = g.getValue(r1, Bindings.INT_ARRAY);
1269 int[] v2 = g.getValue(r2, Bindings.INT_ARRAY);
1270 return Arrays.equals(v1,v2);
1271 } else if (t1.equals(b.FloatArray)) {
1272 float[] v1 = g.getValue(r1, Bindings.FLOAT_ARRAY);
1273 float[] v2 = g.getValue(r2, Bindings.FLOAT_ARRAY);
1274 return Arrays.equals(v1,v2);
1275 } else if (t1.equals(b.DoubleArray)) {
1276 double[] v1 = g.getValue(r1, Bindings.DOUBLE_ARRAY);
1277 double[] v2 = g.getValue(r2, Bindings.DOUBLE_ARRAY);
1278 return Arrays.equals(v1,v2);
1279 } else if (t1.equals(b.StringArray)) {
1280 String[] v1 = g.getValue(r1, Bindings.STRING_ARRAY);
1281 String[] v2 = g.getValue(r2, Bindings.STRING_ARRAY);
1282 return Arrays.equals(v1,v2);
1283 } else if (t1.equals(b.BooleanArray)) {
1284 boolean[] v1 = g.getValue(r1, Bindings.BOOLEAN_ARRAY);
1285 boolean[] v2 = g.getValue(r2, Bindings.BOOLEAN_ARRAY);
1286 return Arrays.equals(v1,v2);
1287 } else if (t1.equals(b.ByteArray)) {
1288 byte[] v1 = g.getValue(r1, Bindings.BYTE_ARRAY);
1289 byte[] v2 = g.getValue(r2, Bindings.BYTE_ARRAY);
1290 return Arrays.equals(v1,v2);
1291 } else if (t1.equals(b.LongArray)) {
1292 long[] v1 = g.getValue(r1, Bindings.LONG_ARRAY);
1293 long[] v2 = g.getValue(r2, Bindings.LONG_ARRAY);
1294 return Arrays.equals(v1,v2);
1296 Object v1 = g.getValue(r1);
1297 Object v2 = g.getValue(r2);
1298 return compareValue(v1, v2);
1303 public static boolean compareValue(Object v1, Object v2) {
1304 if (v1 instanceof Object[] && v2 instanceof Object[])
1305 return Arrays.deepEquals((Object[])v1, (Object[])v2);
1306 else if (v1 instanceof int[] && v2 instanceof int[])
1307 return Arrays.equals((int[])v1, (int[])v2);
1308 else if (v1 instanceof float[] && v2 instanceof float[])
1309 return Arrays.equals((float[])v1, (float[])v2);
1310 else if (v1 instanceof double[] && v2 instanceof double[])
1311 return Arrays.equals((double[])v1, (double[])v2);
1312 else if (v1 instanceof long[] && v2 instanceof long[])
1313 return Arrays.equals((long[])v1, (long[])v2);
1314 else if (v1 instanceof byte[] && v2 instanceof byte[])
1315 return Arrays.equals((byte[])v1, (byte[])v2);
1316 else if (v1 instanceof boolean[] && v2 instanceof boolean[])
1317 return Arrays.equals((boolean[])v1, (boolean[])v2);
1319 return v1.equals(v2);
1323 public class PredicateComparator implements Comparator<Statement> {
1325 public int compare(Statement o1, Statement o2) {
1326 if (comparableResources.contains(o1.getPredicate(), o2.getPredicate()))
1328 if (o1.getPredicate().getResourceId() < o2.getPredicate().getResourceId())
1330 if (o1.getPredicate().getResourceId() > o2.getPredicate().getResourceId())
1336 public class SubjectComparator implements Comparator<Statement> {
1338 public int compare(Statement o1, Statement o2) {
1339 if (comparableResources.contains(o1.getSubject(), o2.getSubject()))
1341 if (o1.getSubject().getResourceId() < o2.getSubject().getResourceId())
1343 if (o1.getSubject().getResourceId() > o2.getSubject().getResourceId())
1349 public class ObjectComparator implements Comparator<Statement> {
1351 public int compare(Statement o1, Statement o2) {
1352 if (comparableResources.contains(o1.getObject(), o2.getObject()))
1354 if (o1.getObject().getResourceId() < o2.getObject().getResourceId())
1356 if (o1.getObject().getResourceId() > o2.getObject().getResourceId())
1362 public static class FullStatementComparator implements Comparator<Statement> {
1364 public int compare(Statement o1, Statement o2) {
1365 if (o1.getSubject().getResourceId() < o2.getSubject().getResourceId())
1367 if (o1.getSubject().getResourceId() > o2.getSubject().getResourceId())
1369 if (o1.getPredicate().getResourceId() < o2.getPredicate().getResourceId())
1371 if (o1.getPredicate().getResourceId() > o2.getPredicate().getResourceId())
1373 if (o1.getObject().getResourceId() < o2.getObject().getResourceId())
1375 if (o1.getObject().getResourceId() > o2.getObject().getResourceId())
1381 public class ResComparator implements Comparator<Resource> {
1383 public int compare(Resource o1, Resource o2) {
1384 if (comparableResources.contains(o1, o2))
1386 if (o1.getResourceId() < o2.getResourceId())
1388 if (o1.getResourceId() > o2.getResourceId())