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;
24 import java.util.Stack;
26 import org.simantics.db.ReadGraph;
27 import org.simantics.db.Resource;
28 import org.simantics.db.Session;
29 import org.simantics.db.Statement;
30 import org.simantics.db.common.request.ReadRequest;
31 import org.simantics.db.common.utils.NameUtils;
32 import org.simantics.db.exception.DatabaseException;
33 import org.simantics.layer0.Layer0;
34 import org.simantics.utils.datastructures.BijectionMap;
35 import org.simantics.utils.datastructures.MapList;
36 import org.simantics.utils.datastructures.Pair;
39 * Compares two subgraphs and reports differences.
41 * Assumes that subgraphs (defined using traverse relations) are not cyclic.
43 * Assumes that properties can be used to identify objects, if relation type is not enough.
47 * @author Marko Luukkainen <marko.luukkainen@vtt.fi>
50 public class GraphComparator {
52 private static final boolean DEBUG = false;
56 private Set<Resource> strong = new HashSet<Resource>(); // List of relations that identify object, if subject is already identified.
57 private List<Resource> traversed = new ArrayList<Resource>(); // list of relations that are traversed (and tested)
58 private List<Resource> tested = new ArrayList<Resource>(); // list of relations that are tested, but not traversed
59 private List<Resource> nonTraversed = new ArrayList<Resource>(); // list of relations that are not traversed
60 private List<Resource> nonTested = new ArrayList<Resource>(); // list of relations that are not tested
62 private List<Statement> changes1 = new ArrayList<Statement>();
63 private List<Statement> changes2 = new ArrayList<Statement>();
64 private List<Pair<Statement,Statement>> modifications = new ArrayList<Pair<Statement,Statement>>();
65 private Set<Statement> changes1Set = new HashSet<Statement>();
66 private Set<Statement> changes2Set = new HashSet<Statement>();
67 private Set<Pair<Statement,Statement>> modificationsSet = new HashSet<Pair<Statement,Statement>>();
69 private BijectionMap<Statement, Statement> comparableStatements = new BijectionMap<Statement, Statement>();
70 private BijectionMap<Resource, Resource> comparableResources = new BijectionMap<Resource, Resource>();
72 private Set<Resource> processedResources = new HashSet<Resource>();
74 private ResourceComparator comparator;
76 private Comparator<Statement> scomp = new PredicateComparator();
77 private Comparator<Resource> rcomp = new ResComparator();
79 private Set<Resource> nonMatchedLeft = new HashSet<Resource>();
80 private Set<Resource> nonMatchedRight = new HashSet<Resource>();
87 public GraphComparator(Resource r1, Resource r2) {
90 comparator = new TypeComparator();
93 public GraphComparator(Resource r1, Resource r2, ResourceComparator comparator) {
96 this.comparator = comparator;
99 ArrayList<Statement> ss1 = new ArrayList<Statement>();
100 ArrayList<Statement> ss2 = new ArrayList<Statement>();
103 public Comparator<Resource> getResourceComparator() {
107 public Comparator<Statement> getStatementComparator() {
111 public Resource getR1() {
115 public Resource getR2() {
119 public void addTraversed(Resource rel) {
123 public void addTraversed(Collection<Resource> rels) {
124 traversed.addAll(rels);
127 public void addNonTraversed(Resource rel) {
128 nonTraversed.add(rel);
131 public void addNonTraversed(Collection<Resource> rels) {
132 nonTraversed.addAll(rels);
135 public void addTested(Resource rel) {
139 public void addTested(Collection<Resource> rels) {
143 public void addNonTested(Resource rel) {
147 public void addNonTested(Collection<Resource> rels) {
148 nonTested.addAll(rels);
151 public void addComparableResources(Resource r1, Resource r2) {
152 comparableResources.map(r1, r2);
155 public void addComparableResources(BijectionMap<Resource, Resource> matching) {
156 comparableResources.addAll(matching);
159 public void addStrong(Resource r) {
163 public void addStrong(Collection<Resource> rels) {
167 public void addNonMatchedLeft(Resource r) {
168 nonMatchedLeft.add(r);
171 public void addNonMatchedRight(Resource r) {
172 nonMatchedRight.add(r);
175 public void test(ReadGraph g) throws DatabaseException {
177 this.b = Layer0.getInstance(g);
178 comparator.setComparator(this);
180 Stack<Resource> objectsLeft = new Stack<Resource>();
181 Stack<Resource> objectsRight = new Stack<Resource>();
182 objectsLeft.push(r1);
183 objectsRight.push(r2);
185 Set<Statement> unreliableLeft = new HashSet<Statement>();
186 Set<Statement> unreliableRight = new HashSet<Statement>();
189 if (objectsLeft.isEmpty())
193 // process compares objects that are identified and searches for more resources to process.
194 process(objectsLeft, objectsRight, unreliableLeft, unreliableRight);
195 // process unreliable handles cases where unidentified statements subject and object have been identified
196 processUnreliable(unreliableLeft, unreliableRight);
197 // process unreliable handles cases where unidentified resources have path of length one to identified resource
198 processUnreliable(unreliableLeft, unreliableRight,objectsLeft,objectsRight);
199 if (objectsLeft.isEmpty() && unreliableLeft.size() > 0 && unreliableRight.size() > 0) {
200 // comparison is ending, but we have still unprocessed unidentified resources left.
201 // These cases have longer path than one to identified objects.
202 processUnreliableDeep(unreliableLeft, unreliableRight, objectsLeft, objectsRight);
206 for (Statement s : unreliableLeft) {
207 if (!comparableStatements.containsLeft(s))
210 for (Statement s : unreliableRight) {
211 if (!comparableStatements.containsRight(s))
218 public void test(Session session) throws DatabaseException {
219 test(session, r1, r2);
222 public void test(Session session, Resource r1, Resource r2) throws DatabaseException {
224 comparator.setComparator(this);
226 addComparable(r1, r2, false);
228 final Stack<Resource> objectsLeft = new Stack<Resource>();
229 final Stack<Resource> objectsRight = new Stack<Resource>();
230 objectsLeft.push(r1);
231 objectsRight.push(r2);
233 final Set<Statement> unreliableLeft = new HashSet<Statement>();
234 final Set<Statement> unreliableRight = new HashSet<Statement>();
237 if (objectsLeft.isEmpty())
239 session.syncRequest(new ReadRequest() {
242 public void run(ReadGraph graph) throws DatabaseException {
244 b = Layer0.getInstance(graph);
245 // process compares objects that are identified and searches for more resources to process.
246 process(objectsLeft, objectsRight, unreliableLeft, unreliableRight);
247 // process unreliable handles cases where unidentified statements subject and object have been identified
248 processUnreliable(unreliableLeft, unreliableRight);
249 // process unreliable handles cases where unidentified resources have path of length one to identified resource
250 processUnreliable(unreliableLeft, unreliableRight,objectsLeft,objectsRight);
251 if (objectsLeft.isEmpty() && unreliableLeft.size() > 0 && unreliableRight.size() > 0) {
252 // comparison is ending, but we have still unprocessed unidentified resources left.
253 // These cases have longer path than one to identified objects.
254 processUnreliableDeep(unreliableLeft, unreliableRight, objectsLeft, objectsRight);
262 for (Statement s : unreliableLeft) {
263 if (!comparableStatements.containsLeft(s))
266 for (Statement s : unreliableRight) {
267 if (!comparableStatements.containsRight(s))
274 private void process(Stack<Resource> objectsLeft, Stack<Resource> objectsRight, Set<Statement> unreliableLeft, Set<Statement> unreliableRight) throws DatabaseException {
275 List<Statement> ss1 = new ArrayList<Statement>();
276 List<Statement> ss2 = new ArrayList<Statement>();
278 while (!objectsLeft.isEmpty()) {
279 Resource r1 = objectsLeft.pop();
280 Resource r2 = objectsRight.pop();
285 if (processedResources.contains(r1))
287 processedResources.add(r1);
290 if((comparableResources.containsLeft(r1)||comparableResources.containsRight(r2)) && !comparableResources.contains(r1, r2)) {
291 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.");
293 addComparable(r1, r2, false);
295 //System.out.println("test " + NameUtils.getSafeName(g, r1) + " " + NameUtils.getSafeName(g, r2));
296 compareProps(r1, r2);
298 for (Resource rel : tested) {
299 ss1.addAll(g.getStatements(r1, rel));
300 ss2.addAll(g.getStatements(r2, rel));
301 ss1 = filterAsserted(r1, ss1);
302 ss2 = filterAsserted(r2, ss2);
303 ss1 = filterTraversed(ss1);
304 ss2 = filterTraversed(ss2);
305 ss1 = filterNonTested(ss1);
306 ss2 = filterNonTested(ss2);
309 compareStatements(ss1, ss2, null, null,null,null);
314 for (Resource rel : traversed) {
315 ss1.addAll(g.getStatements(r1, rel));
316 ss2.addAll(g.getStatements(r2, rel));
317 ss1 = filterAsserted(r1, ss1);
318 ss2 = filterAsserted(r2, ss2);
319 ss1 = filterNonTraversed(ss1);
320 ss2 = filterNonTraversed(ss2);
321 compareStatements(ss1, ss2, objectsLeft, objectsRight,unreliableLeft,unreliableRight);
329 private void processUnreliable(Set<Statement> unreliableLeft, Set<Statement> unreliableRight) throws DatabaseException {
330 MapList<Resource,Statement> subjectLeft = new MapList<Resource, Statement>();
331 MapList<Resource,Statement> subjectRight = new MapList<Resource, Statement>();
332 MapList<Resource,Statement> objectLeft = new MapList<Resource, Statement>();
333 MapList<Resource,Statement> objectRight = new MapList<Resource, Statement>();
335 for (Statement s : unreliableLeft) {
336 subjectLeft.add(s.getSubject(),s);
337 objectLeft.add(s.getObject(),s);
339 for (Statement s : unreliableRight) {
340 subjectRight.add(s.getSubject(),s);
341 objectRight.add(s.getObject(),s);
344 for (Resource left : subjectLeft.getKeys()) {
345 if (!comparableResources.containsLeft(left))
347 Resource right = comparableResources.getRight(left);
348 for (Statement leftS : subjectLeft.getValues(left)) {
349 Resource leftO = leftS.getObject();
350 if (!comparableResources.containsLeft(leftO))
352 if (!unreliableLeft.contains(leftS))
354 Resource rightO = comparableResources.getRight(leftO);
355 for (Statement rightS : subjectRight.getValues(right)) {
356 if (!rightS.getObject().equals(rightO))
358 if (!unreliableRight.contains(rightS))
360 if (leftS.getPredicate().equals(rightS.getPredicate()) ||
361 comparableResources.contains(leftS.getPredicate(), rightS.getPredicate())) {
362 unreliableLeft.remove(leftS);
363 unreliableRight.remove(rightS);
364 addComparable(leftS, rightS, false);
371 private void processUnreliable(Set<Statement> unreliableLeft, Set<Statement> unreliableRight, Stack<Resource> objectsLeft, Stack<Resource> objectsRight) throws DatabaseException {
372 MapList<Resource,Statement> subjectLeft = new MapList<Resource, Statement>();
373 MapList<Resource,Statement> subjectRight = new MapList<Resource, Statement>();
374 MapList<Resource,Statement> objectLeft = new MapList<Resource, Statement>();
375 MapList<Resource,Statement> objectRight = new MapList<Resource, Statement>();
377 for (Statement s : unreliableLeft) {
378 subjectLeft.add(s.getSubject(),s);
379 objectLeft.add(s.getObject(),s);
381 for (Statement s : unreliableRight) {
382 subjectRight.add(s.getSubject(),s);
383 objectRight.add(s.getObject(),s);
386 for (Resource ol : objectLeft.getKeys()) {
387 // all statements to the left side object
388 List<Statement> left = objectLeft.getValues(ol);
389 // all subjects that have statements to the left side object (ol)
390 Set<Resource> sLeft = new HashSet<Resource>();
391 // all matching subjects on the right side
392 Set<Resource> sRight = new HashSet<Resource>();
393 for (Statement s : left) {
394 sLeft.add(s.getSubject());
395 sRight.add(comparableResources.getRight(s.getSubject()));
398 // check if object left can be reliably identified by available statements
399 // if there are any objects on the left side with similar statements, object left cannot be mapped.
400 boolean hasSimilar = false;
401 MapList<Resource, Statement> comparableOLeft = new MapList<Resource, Statement>();
402 for (Resource sl : sLeft) {
403 for (Statement s : subjectLeft.getValues(sl)) {
404 if (!s.getObject().equals(ol)) {
405 comparableOLeft.add(s.getObject(),s);
410 for (Resource similarOl : comparableOLeft.getKeys()) {
411 List<Statement> similarLeft = comparableOLeft.getValues(similarOl);
412 if (similarLeft.size() == left.size()) {
413 boolean useL[] = new boolean[left.size()];
414 boolean useSL[] = new boolean[left.size()];
415 for (int i = 0; i < left.size(); i++) {
419 for (int i = 0; i < left.size(); i++) {
420 for (int j = 0; j < left.size(); j++) {
423 Resource pl = left.get(i).getPredicate();
424 Resource psl = similarLeft.get(j).getPredicate();
425 if (pl.equals(psl)) {
432 boolean diff = false;
433 for (int i = 0; i < left.size(); i++) {
434 if (!useL[i] || !useSL[i]) {
449 // all objects that subjects on the right side point to. Object left has its matching resource among these, if it has matching resource
450 MapList<Resource,Statement> possibleOR = new MapList<Resource, Statement>();
451 for (Resource sr : sRight) {
452 for (Statement s : subjectRight.getValues(sr))
453 possibleOR.add(s.getObject(),s);
456 // filter possible right side objects to those that have same amount of statements as the left side object
457 for (Resource or : possibleOR.getKeys().toArray(new Resource[possibleOR.getKeys().size()])) {
458 List<Statement> right = possibleOR.getValues(or);
459 if (right.size() != left.size())
460 possibleOR.remove(or);
464 // check for matching statements (comparable subjects, matching predicates)
465 MapList<Resource,Statement> matchingOR = new MapList<Resource, Statement>(); // list of objects that have matching statements
466 Map<Resource,Pair<int[], int[]>> matchingStatements = new HashMap<Resource, Pair<int[], int[]>>(); // matching statements
467 for (Resource or : possibleOR.getKeys()) {
468 List<Statement> right = possibleOR.getValues(or);
469 int iLeft[] = new int[left.size()];
470 int iRight[] = new int[right.size()];
472 for (int i = 0; i < left.size(); i++) {
477 for (int l = 0; l < left.size(); l++) {
478 Statement ls = left.get(l);
479 for (int r = 0; r < right.size(); r++) {
482 Statement rs = right.get(r);
483 if (!comparableResources.contains(ls.getSubject(), rs.getSubject()))
485 if (rcomp.compare(ls.getPredicate(),rs.getPredicate()) == 0) {
493 boolean success = true;
494 for (int i = 0; i < left.size(); i++) {
506 for (Statement s : right)
507 matchingOR.add(or,s);
508 matchingStatements.put(or, new Pair<int[], int[]>(iLeft, iRight));
511 // if there is only one matching right side object, we have found a match
512 if (matchingOR.getKeySize() == 1) {
513 Resource or = matchingOR.getKeys().iterator().next();
514 List<Statement> right = matchingOR.getValues(or);
515 Pair<int[], int[]> indices = matchingStatements.get(or);
518 objectsRight.add(or);
519 addComparable(ol, or, false);
520 for (int l = 0; l < left.size(); l++) {
521 int r = indices.first[l];
522 Statement sl = left.get(l);
523 Statement sr = right.get(r);
524 addComparable(sl, sr, true);
525 unreliableLeft.remove(sl);
526 unreliableRight.remove(sr);
536 private void processUnreliableDeep(Set<Statement> unreliableLeft, Set<Statement> unreliableRight, Stack<Resource> objectsLeft, Stack<Resource> objectsRight) throws DatabaseException {
537 MapList<Resource,Statement> subjectLeft = new MapList<Resource, Statement>();
538 MapList<Resource,Statement> subjectRight = new MapList<Resource, Statement>();
539 MapList<Resource,Statement> objectLeft = new MapList<Resource, Statement>();
540 MapList<Resource,Statement> objectRight = new MapList<Resource, Statement>();
542 for (Statement s : unreliableLeft) {
543 subjectLeft.add(s.getSubject(),s);
544 objectLeft.add(s.getObject(),s);
546 for (Statement s : unreliableRight) {
547 subjectRight.add(s.getSubject(),s);
548 objectRight.add(s.getObject(),s);
550 for (Resource ol : objectLeft.getKeys()) {
551 Set<Path> pathsLeft = new HashSet<Path>();
552 for (Resource rel : traversed) {
553 pathsLeft.addAll(Path.create(g.getStatements(ol, rel)));
557 if (pathsLeft.size() == 0)
559 Collection<Path> endPaths = new ArrayList<Path>(1);
560 for (Path p : pathsLeft) {
561 if (comparableResources.containsLeft(p.getEnd())) {
565 if (endPaths.size() > 0) {
567 pathsLeft.addAll(endPaths);
571 if (pathsLeft.size() > 0) {
572 Resource sl = objectLeft.getValues(ol).get(0).getSubject();
573 Resource sr = comparableResources.getRight(sl);
574 Collection<Resource> possibleOR = new ArrayList<Resource>();
575 for (Statement s : subjectRight.getValues(sr)) {
576 possibleOR.add(s.getObject());
578 Map<Resource,Set<Path>> matchingPaths = new HashMap<Resource, Set<Path>>();
579 for (Resource or : possibleOR) {
580 Set<Path> possiblePathsRight = new HashSet<Path>();
581 for (Path leftPath : pathsLeft) {
582 possiblePathsRight.addAll(findComparableRight(leftPath, or));
584 if (hasMatchingPaths(pathsLeft, possiblePathsRight)) {
585 matchingPaths.put(or, possiblePathsRight);
588 if (matchingPaths.size() > 0) {
589 if (matchingPaths.size() == 1) {
590 Resource or = matchingPaths.keySet().iterator().next();
593 objectsRight.add(or);
594 addComparable(ol, or, false);
595 Collection<Statement> statementsLeft = objectLeft.getValues(ol);
596 Collection<Statement> statementsRight = objectRight.getValues(or);
597 unreliableLeft.removeAll(statementsLeft);
598 unreliableRight.removeAll(statementsRight);
599 BijectionMap<Path,Path> map = getMatchingPaths(pathsLeft, matchingPaths.get(or));
600 for (Path left : map.getLeftSet()) {
601 Path right = map.getRight(left);
602 for (int i = 0; i < left.getLength(); i++) {
603 addComparable(left.getStatements().get(i),right.getStatements().get(i),false);
614 private boolean hasMatchingPaths(Set<Path> leftPaths, Set<Path> rightPaths) {
615 if (leftPaths.size() != rightPaths.size())
617 BijectionMap<Path,Path> map = getMatchingPaths(leftPaths, rightPaths);
618 return map.size() == leftPaths.size();
621 private BijectionMap<Path,Path> getMatchingPaths(Set<Path> leftPaths, Set<Path> rightPaths) {
622 BijectionMap<Path,Path> map = new BijectionMap<Path, Path>();
623 for (Path leftPath : leftPaths) {
624 for (Path rightPath : rightPaths) {
625 if (map.containsRight(rightPath))
627 if (leftPath.getLength() != rightPath.getLength())
629 if (comparableResources.contains(leftPath.getEnd(), rightPath.getEnd())) {
630 map.map(leftPath, rightPath);
638 private void expand(Set<Path> paths) throws DatabaseException {
639 Set<Path> stepPathsLeft = new HashSet<Path>();
640 if (paths.size() == 0)
642 int length = paths.iterator().next().getLength() + 1;
643 for (Path p : paths) {
644 for (Resource rel : traversed) {
645 stepPathsLeft.addAll(Path.expand(p,g.getStatements(p.getEnd(), rel)));
649 for (Path p : stepPathsLeft) {
650 if (p.getLength() == length)
655 private Collection<Path> findComparableRight(Path leftPath, Resource beginRight) throws DatabaseException {
656 Set<Path> rightPaths = new HashSet<Path>();
657 rightPaths.addAll(Path.create(g.getStatements(beginRight, getRight(leftPath.getStatements().get(0).getPredicate()))));
658 for (int i = 1; i < leftPath.getLength(); i++) {
659 if (rightPaths.size() == 0)
661 Set<Path> stepPaths = new HashSet<Path>();
662 for (Path p : rightPaths) {
663 stepPaths.addAll(Path.expand(p, g.getStatements(p.getEnd(), getRight(leftPath.getStatements().get(i).getPredicate()))));
666 for (Path p : stepPaths)
667 if (p.getLength() == i+1)
674 private Resource getRight(Resource r) {
675 if (comparableResources.containsLeft(r))
676 return comparableResources.getRight(r);
682 public BijectionMap<Statement, Statement> getComparableStatements() {
683 return comparableStatements;
686 public BijectionMap<Resource, Resource> getComparableResources() {
687 return comparableResources;
690 public GraphChanges getChanges() {
691 return new GraphChanges(r1,r2,changes1,changes2,modifications,comparableResources);
694 private void addComparable(Statement left, Statement right, boolean process) throws DatabaseException {
695 addComparable(left.getObject(), right.getObject(), process);
696 comparableStatements.map(left, right);
697 //comparableResources.map(left.getObject(), right.getObject());
700 private void addComparable(Resource left, Resource right, boolean process) throws DatabaseException {
701 if(!comparableResources.contains(left, right)) {
702 if (comparableResources.containsLeft(left)||comparableResources.containsRight(right)) {
703 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.");
705 if (DEBUG) System.out.println(left + " = " + right);
706 comparableResources.map(left, right);
712 public List<Statement> filterAsserted(Resource r, Collection<Statement> in) throws DatabaseException {
713 List<Statement> out = new ArrayList<Statement>();
714 for (Statement s : in) {
715 if (!s.isAsserted(r))
724 private String printStatement(ReadGraph graph, Statement s) throws DatabaseException {
725 return NameUtils.getSafeName(graph, s.getSubject()) + " " + NameUtils.getSafeName(graph, s.getPredicate()) + " " + NameUtils.getSafeName(graph, s.getObject());
728 private List<Statement> filterTraversed(List<Statement> in) throws DatabaseException {
729 return filter(traversed, in);
732 private List<Statement> filterNonTested(List<Statement> in) throws DatabaseException {
733 return filter(nonTested, in);
736 private List<Statement> filterNonTraversed(List<Statement> in) throws DatabaseException {
737 return filter(nonTraversed, in);
740 private List<Statement> filter(Collection<Resource> toFilter, List<Statement> in) throws DatabaseException {
741 if (toFilter.size() == 0)
743 List<Statement> out = new ArrayList<Statement>();
744 for (Statement s : in) {
745 boolean usable = true;
746 for (Resource r : toFilter) {
747 if (g.isSubrelationOf(s.getPredicate(),r)) {
761 private void addDeletion(Statement s) {
762 if (!changes1Set.contains(s)) {
768 private void addAddition(Statement s) {
769 if (!changes2Set.contains(s)) {
775 private void addModification(Statement s1, Statement s2) {
776 Pair<Statement, Statement> mod = new Pair<Statement, Statement>(s1,s2);
777 if (!modificationsSet.contains(mod)) {
778 modificationsSet.add(mod);
779 modifications.add(mod);
783 public void sortStatement(List<Statement> list1, List<Statement> list2) {
784 sortStatement(list1, list2, scomp);
787 public void sortStatement(List<Statement> list1, List<Statement> list2, Comparator<Statement> scomp) {
788 Collections.sort(list1,scomp);
789 Collections.sort(list2,scomp);
791 List<Statement> sorted1 = new ArrayList<Statement>(list1.size());
792 List<Statement> sorted2 = new ArrayList<Statement>(list2.size());
793 sorted1.addAll(list1);
794 sorted2.addAll(list2);
798 for (int i = 0; i < list1.size(); ) {
799 Statement s1 = list1.get(i);
800 int same1 = sameRel(list1, i);
801 for (int j = 0; j < list2.size(); j++) {
802 Statement s2 = list2.get(j);
803 if (scomp.compare(s1, s2) == 0) {
804 int same2 = sameRel(list2, j);
805 copy(sorted1,ss1,list1,i,same1);
807 copy(sorted2,ss2,list2,j,same2);
814 if (ss1 < sorted1.size()) {
815 for (Statement s : list1) {
816 if (!sorted1.contains(s)) {
822 if (ss2 < sorted2.size()) {
823 for (Statement s : list2) {
824 if (!sorted2.contains(s)) {
833 list1.addAll(sorted1);
834 list2.addAll(sorted2);
837 public <T> void copy(List<T> to, int toIndex, List<T> from, int fromIndex, int amount) {
838 for (int i = 0; i < amount; i++) {
839 to.set(toIndex + i, from.get(fromIndex+ i));
843 public void sortResource(List<Resource> list1, List<Resource> list2) {
844 Collections.sort(list1,rcomp);
846 for (int i = 0; i < list1.size(); i++) {
847 Resource s1 = list1.get(i);
848 for (int j = js; j < list2.size(); j++) {
849 Resource s2 = list2.get(j);
850 if (rcomp.compare(s1, s2) == 0) {
851 Resource t = list2.get(js);
861 private void compareStatements(List<Statement> ss1, List<Statement> ss2, Stack<Resource> objectsLeft, Stack<Resource> objectsRight, Collection<Statement> unreliableLeft, Collection<Statement> unreliableRight) throws DatabaseException {
862 sortStatement(ss1, ss2);
868 if (i1 >= ss1.size()) {
869 if (i2 >= ss2.size()) {
872 while (i2 < ss2.size()) {
873 if (DEBUG) System.out.println("Compare Statements addition " + printStatement(g,ss2.get(i2)));
875 addAddition(ss2.get(i2));
880 } else if (i2 >= ss2.size()) {
881 while (i1 < ss1.size()) {
882 if (DEBUG) System.out.println("Compare Statements deletion " + printStatement(g,ss1.get(i1)));
883 addDeletion(ss1.get(i1));
888 int same1 = sameRel(ss1, i1);
889 int same2 = sameRel(ss2, i2);
890 int c = rcomp.compare(ss1.get(i1).getPredicate(),ss2.get(i2).getPredicate());
892 compareStatements(ss1, i1, same1, ss2, i2, same2,objectsLeft,objectsRight,unreliableLeft,unreliableRight);
896 for (int i = 0; i < same1; i++) {
897 if (DEBUG) System.out.println("Compare Statements deletion " + printStatement(g,ss1.get(i+i1)));
898 addDeletion(ss1.get(i+i1));
902 for (int i = 0; i < same2; i++) {
903 if (DEBUG) System.out.println("Compare Statements addition " + printStatement(g,ss2.get(i+i2)));
904 addAddition(ss2.get(i+i2));
914 private int sameRel(List<Statement> statements, int off) {
915 if (statements.size() <= off)
918 long id = statements.get(off).getPredicate().getResourceId();
919 for (int i = off+1; i <statements.size(); i++) {
920 if (statements.get(i).getPredicate().getResourceId() == id)
929 private int compareObject(Resource o1, Resource o2) throws DatabaseException {
932 if (comparableResources.contains(o1, o2))
934 if (comparableResources.containsLeft(o1))
935 return Integer.MAX_VALUE;
936 if (comparableResources.containsRight(o2))
937 return Integer.MAX_VALUE;
938 if (nonMatchedLeft.contains(o1))
939 return Integer.MAX_VALUE;
940 if (nonMatchedRight.contains(o2))
941 return Integer.MAX_VALUE;
942 return comparator.compare(g, o1, o2);
945 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 {
946 boolean[] used1 = new boolean[len1];
947 for (int i = 0; i < used1.length; i++) {
951 boolean[] used2 = new boolean[len2];
952 for (int i = 0; i < used2.length; i++) {
956 // left, right, difference
957 List<List<Integer>> differences = new ArrayList<List<Integer>>();
958 for (int i1 = off1; i1 < off1 + len1; i1++) {
959 Statement s1 = ss1.get(i1);
960 List<Integer> diff = new ArrayList<Integer>();
961 for (int i2 = off2; i2 < off2 + len2; i2++) {
962 Statement s2 = ss2.get(i2);
963 int d = compareObject(s1.getObject(), s2.getObject());
965 for (Resource t : strong) {
966 if (s1.getPredicate().equals(t) || g.isSubrelationOf(s1.getPredicate(), t)) {
974 differences.add(diff);
977 MapList<Integer, Integer> priorities = new MapList<Integer, Integer>();
978 for (int i = 0; i < differences.size(); i++) {
979 List<Integer> list = differences.get(i);
980 for (int j = 0; j < list.size(); j++) {
981 priorities.add(list.get(j), i);
985 Integer[] pris = priorities.getKeys(new Integer[]{});
988 for (Integer pri : pris) {
989 if (pri == Integer.MAX_VALUE) {
991 } else if (pri == 0) {
994 List<Integer> i1s = priorities.getValues(pri);
995 for (Integer i1 : i1s) {
998 List<Integer> i2diff = differences.get(i1);
999 for (int i2 = 0; i2 < i2diff.size(); i2++) {
1000 if (i2diff.get(i2) == pri) {
1005 Statement s1 = ss1.get(i1+off1);
1006 Statement s2 = ss2.get(i2+off2);
1008 if (objectsLeft != null) {
1009 objectsLeft.add(s1.getObject());
1010 objectsRight.add(s2.getObject());
1012 addComparable(s1, s2, true);
1020 for (Integer pri : pris) {
1023 Set<Statement> s1s = new HashSet<Statement>();
1024 Set<Statement> s2s = new HashSet<Statement>();
1025 Set<Integer> s1i = new HashSet<Integer>();
1026 Set<Integer> s2i = new HashSet<Integer>();
1027 List<Integer> i1s = priorities.getValues(pri);
1028 for (Integer i1 : i1s) {
1031 List<Integer> i2diff = differences.get(i1);
1032 for (int i2 = 0; i2 < i2diff.size(); i2++) {
1033 if (i2diff.get(i2) == pri) {
1036 Statement s1 = ss1.get(i1+off1);
1037 Statement s2 = ss2.get(i2+off2);
1045 if (unreliableLeft != null) {
1046 unreliableLeft.addAll(s1s);
1047 unreliableRight.addAll(s2s);
1049 for (Integer i : s1i)
1051 for (Integer i : s2i)
1055 for (int i1 = off1; i1 < off1 + len1; i1++) {
1056 if (!used1[i1-off1]) {
1057 if (DEBUG) System.out.println("Compare Object deletion " + printStatement(g,ss1.get(i1)));
1058 addDeletion(ss1.get(i1));
1061 for (int i2 = off2; i2 < off2 + len2; i2++) {
1062 if (!used2[i2-off2]) {
1063 if (DEBUG) System.out.println("Compare Object addition " + printStatement(g,ss2.get(i2)));
1064 addAddition(ss2.get(i2));
1072 * compares properties, assumes functional relations
1075 * @throws ServiceException
1076 * @throws DoesNotContainValueException
1077 * @throws ValidationException
1079 private void compareProps(Resource r1, Resource r2) throws DatabaseException {
1080 if (DEBUG) System.out.println("compareProps " + r1 + " " + NameUtils.getSafeName(g, r1) + " " + r2 + " " + NameUtils.getSafeName(g, r2));
1081 List<Statement> ss1 = new ArrayList<Statement>();
1082 List<Statement> ss2 = new ArrayList<Statement>();
1083 ss1.addAll(g.getStatements(r1, b.HasProperty));
1084 ss2.addAll(g.getStatements(r2, b.HasProperty));
1085 ss1 = filterNonTested(ss1);
1086 ss2 = filterNonTested(ss2);
1087 sortStatement(ss1, ss2);
1093 if (i1 >= ss1.size()) {
1094 if (i2 >= ss2.size())
1097 while (i2 < ss2.size()) {
1098 if (DEBUG) System.out.println("Compare Prop diff2 " + printStatement(g,ss2.get(i2)));
1099 addAddition(ss2.get(i2));
1104 } else if (i2 >= ss2.size()) {
1105 while (i1 < ss1.size()) {
1106 if (DEBUG) System.out.println("Compare Prop diff1 " + printStatement(g,ss1.get(i1)));
1107 addDeletion(ss1.get(i1));
1112 Statement s1 = ss1.get(i1);
1113 Statement s2 = ss2.get(i2);
1114 if (s1.isAsserted(r1) && s2.isAsserted(r2)) {
1119 int c = scomp.compare(s1, s2);
1122 boolean b1 = g.hasValue(s1.getObject());
1123 boolean b2 = g.hasValue(s2.getObject());
1126 Object v1 = g.getValue(s1.getObject());
1127 Object v2 = g.getValue(s2.getObject());
1128 boolean eq = compareValue(v1, v2);
1130 addModification(s1, s2);
1131 addComparable(s1, s2, false);
1134 if (!s1.getObject().equals(s1.getSubject()) && !s2.getObject().equals(s2.getSubject()))
1135 compareProps(s1.getObject(), s2.getObject());
1138 addModification(s1, s2);
1139 addComparable(s1, s2, false);
1146 if (DEBUG) System.out.println("Compare Prop diff1s " + printStatement(g,s1));
1153 if (DEBUG) System.out.println("Compare Prop diff2s " + printStatement(g,s2));
1167 public static boolean compareValue(Object v1, Object v2) {
1168 if (v1 instanceof Object[] && v2 instanceof Object[])
1169 return Arrays.deepEquals((Object[])v1, (Object[])v2);
1170 else if (v1 instanceof int[] && v2 instanceof int[])
1171 return Arrays.equals((int[])v1, (int[])v2);
1172 else if (v1 instanceof float[] && v2 instanceof float[])
1173 return Arrays.equals((float[])v1, (float[])v2);
1174 else if (v1 instanceof double[] && v2 instanceof double[])
1175 return Arrays.equals((double[])v1, (double[])v2);
1176 else if (v1 instanceof long[] && v2 instanceof long[])
1177 return Arrays.equals((long[])v1, (long[])v2);
1178 else if (v1 instanceof byte[] && v2 instanceof byte[])
1179 return Arrays.equals((byte[])v1, (byte[])v2);
1180 else if (v1 instanceof boolean[] && v2 instanceof boolean[])
1181 return Arrays.equals((boolean[])v1, (boolean[])v2);
1183 return v1.equals(v2);
1187 public class PredicateComparator implements Comparator<Statement> {
1189 public int compare(Statement o1, Statement o2) {
1190 if (comparableResources.contains(o1.getPredicate(), o2.getPredicate()))
1192 if (o1.getPredicate().getResourceId() < o2.getPredicate().getResourceId())
1194 if (o1.getPredicate().getResourceId() > o2.getPredicate().getResourceId())
1200 public class SubjectComparator implements Comparator<Statement> {
1202 public int compare(Statement o1, Statement o2) {
1203 if (comparableResources.contains(o1.getSubject(), o2.getSubject()))
1205 if (o1.getSubject().getResourceId() < o2.getSubject().getResourceId())
1207 if (o1.getSubject().getResourceId() > o2.getSubject().getResourceId())
1213 public class ObjectComparator implements Comparator<Statement> {
1215 public int compare(Statement o1, Statement o2) {
1216 if (comparableResources.contains(o1.getObject(), o2.getObject()))
1218 if (o1.getObject().getResourceId() < o2.getObject().getResourceId())
1220 if (o1.getObject().getResourceId() > o2.getObject().getResourceId())
1226 public static class FullStatementComparator implements Comparator<Statement> {
1228 public int compare(Statement o1, Statement o2) {
1229 if (o1.getSubject().getResourceId() < o2.getSubject().getResourceId())
1231 if (o1.getSubject().getResourceId() > o2.getSubject().getResourceId())
1233 if (o1.getPredicate().getResourceId() < o2.getPredicate().getResourceId())
1235 if (o1.getPredicate().getResourceId() > o2.getPredicate().getResourceId())
1237 if (o1.getObject().getResourceId() < o2.getObject().getResourceId())
1239 if (o1.getObject().getResourceId() > o2.getObject().getResourceId())
1245 public class ResComparator implements Comparator<Resource> {
1247 public int compare(Resource o1, Resource o2) {
1248 if (comparableResources.contains(o1, o2))
1250 if (o1.getResourceId() < o2.getResourceId())
1252 if (o1.getResourceId() > o2.getResourceId())