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.interop.test.GraphChanges.Modification;
36 import org.simantics.layer0.Layer0;
37 import org.simantics.utils.datastructures.BijectionMap;
38 import org.simantics.utils.datastructures.MapList;
39 import org.simantics.utils.datastructures.Pair;
42 * Compares two subgraphs and reports differences.
44 * Assumes that subgraphs (defined using traverse relations) are not cyclic.
46 * Assumes that properties can be used to identify objects, if relation type is not enough.
50 * @author Marko Luukkainen <marko.luukkainen@vtt.fi>
53 public class GraphComparator {
55 private static final boolean DEBUG = false;
59 private Set<Resource> strong = new HashSet<>(); // List of relations that identify object, if subject is already identified.
60 private List<Resource> traversed = new ArrayList<>(); // list of relations that are traversed (and tested)
61 private List<Resource> tested = new ArrayList<>(); // list of relations that are tested, but not traversed
62 private List<Resource> nonTraversed = new ArrayList<>(); // list of relations that are not traversed
63 private List<Resource> nonTested = new ArrayList<>(); // list of relations that are not tested
65 private List<Statement> changes1 = new ArrayList<>();
66 private List<Statement> changes2 = new ArrayList<>();
67 private List<Modification> modifications = new ArrayList<>();
68 private Set<Statement> changes1Set = new HashSet<>();
69 private Set<Statement> changes2Set = new HashSet<>();
70 private Set<Modification> modificationsSet = new HashSet<>();
72 private BijectionMap<Statement, Statement> comparableStatements = new BijectionMap<>();
73 private BijectionMap<Resource, Resource> comparableResources = new BijectionMap<>();
75 private Set<Resource> processedResources = new HashSet<Resource>();
77 private ResourceComparator comparator;
79 private Comparator<Statement> scomp = new PredicateComparator();
80 private Comparator<Resource> rcomp = new ResComparator();
82 private Set<Resource> nonMatchedLeft = new HashSet<Resource>();
83 private Set<Resource> nonMatchedRight = new HashSet<Resource>();
90 public GraphComparator(Resource r1, Resource r2) {
93 comparator = new TypeComparator();
96 public GraphComparator(Resource r1, Resource r2, ResourceComparator comparator) {
99 this.comparator = comparator;
102 ArrayList<Statement> ss1 = new ArrayList<Statement>();
103 ArrayList<Statement> ss2 = new ArrayList<Statement>();
106 public Comparator<Resource> getResourceComparator() {
110 public Comparator<Statement> getStatementComparator() {
114 public Resource getR1() {
118 public Resource getR2() {
122 public void addTraversed(Resource rel) {
126 public void addTraversed(Collection<Resource> rels) {
127 traversed.addAll(rels);
130 public void addNonTraversed(Resource rel) {
131 nonTraversed.add(rel);
134 public void addNonTraversed(Collection<Resource> rels) {
135 nonTraversed.addAll(rels);
138 public void addTested(Resource rel) {
142 public void addTested(Collection<Resource> rels) {
146 public void addNonTested(Resource rel) {
150 public void addNonTested(Collection<Resource> rels) {
151 nonTested.addAll(rels);
154 public void addComparableResources(Resource r1, Resource r2) {
155 comparableResources.map(r1, r2);
158 public void addComparableResources(BijectionMap<Resource, Resource> matching) {
159 comparableResources.addAll(matching);
162 public void addStrong(Resource r) {
166 public void addStrong(Collection<Resource> rels) {
170 public void addNonMatchedLeft(Resource r) {
171 nonMatchedLeft.add(r);
174 public void addNonMatchedRight(Resource r) {
175 nonMatchedRight.add(r);
178 public void test(ReadGraph g) throws DatabaseException {
180 this.b = Layer0.getInstance(g);
181 comparator.setComparator(this);
183 Stack<Resource> objectsLeft = new Stack<Resource>();
184 Stack<Resource> objectsRight = new Stack<Resource>();
185 objectsLeft.push(r1);
186 objectsRight.push(r2);
188 Set<Statement> unreliableLeft = new HashSet<Statement>();
189 Set<Statement> unreliableRight = new HashSet<Statement>();
192 if (objectsLeft.isEmpty())
196 // process compares objects that are identified and searches for more resources to process.
197 process(objectsLeft, objectsRight, unreliableLeft, unreliableRight);
198 // process unreliable handles cases where unidentified statements subject and object have been identified
199 processUnreliable(unreliableLeft, unreliableRight);
200 // process unreliable handles cases where unidentified resources have path of length one to identified resource
201 processUnreliable(unreliableLeft, unreliableRight,objectsLeft,objectsRight);
202 if (objectsLeft.isEmpty() && unreliableLeft.size() > 0 && unreliableRight.size() > 0) {
203 processUnreliable2(unreliableLeft, unreliableRight,objectsLeft,objectsRight);
205 if (objectsLeft.isEmpty() && unreliableLeft.size() > 0 && unreliableRight.size() > 0) {
206 // comparison is ending, but we have still unprocessed unidentified resources left.
207 // These cases have longer path than one to identified objects.
208 processUnreliableDeep(unreliableLeft, unreliableRight, objectsLeft, objectsRight);
212 for (Statement s : unreliableLeft) {
213 if (!comparableStatements.containsLeft(s))
216 for (Statement s : unreliableRight) {
217 if (!comparableStatements.containsRight(s))
222 public void test(Session session) throws DatabaseException {
223 test(session, r1, r2);
226 public void test(Session session, Resource r1, Resource r2) throws DatabaseException {
228 comparator.setComparator(this);
230 addComparable(r1, r2);
232 final Stack<Resource> objectsLeft = new Stack<Resource>();
233 final Stack<Resource> objectsRight = new Stack<Resource>();
234 objectsLeft.push(r1);
235 objectsRight.push(r2);
237 final Set<Statement> unreliableLeft = new HashSet<Statement>();
238 final Set<Statement> unreliableRight = new HashSet<Statement>();
241 if (objectsLeft.isEmpty())
243 session.syncRequest(new ReadRequest() {
246 public void run(ReadGraph graph) throws DatabaseException {
248 b = Layer0.getInstance(graph);
249 // process compares objects that are identified and searches for more resources to process.
250 process(objectsLeft, objectsRight, unreliableLeft, unreliableRight);
251 // process unreliable handles cases where unidentified statements subject and object have been identified
252 processUnreliable(unreliableLeft, unreliableRight);
253 // process unreliable handles cases where unidentified resources have path of length one to identified resource
254 processUnreliable(unreliableLeft, unreliableRight,objectsLeft,objectsRight);
255 if (objectsLeft.isEmpty() && unreliableLeft.size() > 0 && unreliableRight.size() > 0) {
256 processUnreliable2(unreliableLeft, unreliableRight,objectsLeft,objectsRight);
258 if (objectsLeft.isEmpty() && unreliableLeft.size() > 0 && unreliableRight.size() > 0) {
259 // comparison is ending, but we have still unprocessed unidentified resources left.
260 // These cases have longer path than one to identified objects.
261 processUnreliableDeep(unreliableLeft, unreliableRight, objectsLeft, objectsRight);
269 for (Statement s : unreliableLeft) {
270 if (!comparableStatements.containsLeft(s))
271 if (s.getObject().getResourceId() == 303248)
272 System.out.println();
275 for (Statement s : unreliableRight) {
276 if (!comparableStatements.containsRight(s))
283 private void process(Stack<Resource> objectsLeft, Stack<Resource> objectsRight, Set<Statement> unreliableLeft, Set<Statement> unreliableRight) throws DatabaseException {
284 List<Statement> ss1 = new ArrayList<Statement>();
285 List<Statement> ss2 = new ArrayList<Statement>();
287 while (!objectsLeft.isEmpty()) {
288 Resource r1 = objectsLeft.pop();
289 Resource r2 = objectsRight.pop();
294 if (processedResources.contains(r1))
296 processedResources.add(r1);
299 if((comparableResources.containsLeft(r1)||comparableResources.containsRight(r2)) && !comparableResources.contains(r1, r2)) {
300 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.");
302 addComparable(r1, r2);
304 //System.out.println("test " + NameUtils.getSafeName(g, r1) + " " + NameUtils.getSafeName(g, r2));
305 compareProps(r1, r2);
307 for (Resource rel : tested) {
308 ss1.addAll(g.getStatements(r1, rel));
309 ss2.addAll(g.getStatements(r2, rel));
310 ss1 = filterAsserted(r1, ss1);
311 ss2 = filterAsserted(r2, ss2);
312 ss1 = filterTraversed(ss1);
313 ss2 = filterTraversed(ss2);
314 ss1 = filterNonTested(ss1);
315 ss2 = filterNonTested(ss2);
318 compareStatements(ss1, ss2, null, null,null,null);
323 for (Resource rel : traversed) {
324 ss1.addAll(g.getStatements(r1, rel));
325 ss2.addAll(g.getStatements(r2, rel));
326 ss1 = filterAsserted(r1, ss1);
327 ss2 = filterAsserted(r2, ss2);
328 ss1 = filterNonTraversed(ss1);
329 ss2 = filterNonTraversed(ss2);
330 compareStatements(ss1, ss2, objectsLeft, objectsRight,unreliableLeft,unreliableRight);
338 private void processUnreliable(Set<Statement> unreliableLeft, Set<Statement> unreliableRight) throws DatabaseException {
339 MapList<Resource,Statement> subjectLeft = new MapList<Resource, Statement>();
340 MapList<Resource,Statement> subjectRight = new MapList<Resource, Statement>();
341 MapList<Resource,Statement> objectLeft = new MapList<Resource, Statement>();
342 MapList<Resource,Statement> objectRight = new MapList<Resource, Statement>();
344 for (Statement s : unreliableLeft) {
345 subjectLeft.add(s.getSubject(),s);
346 objectLeft.add(s.getObject(),s);
348 for (Statement s : unreliableRight) {
349 subjectRight.add(s.getSubject(),s);
350 objectRight.add(s.getObject(),s);
353 for (Resource left : subjectLeft.getKeys()) {
354 Resource right = comparableResources.getRight(left);
357 for (Statement leftS : subjectLeft.getValues(left)) {
358 Resource leftO = leftS.getObject();
359 if (!unreliableLeft.contains(leftS))
361 Resource rightO = comparableResources.getRight(leftO);
364 for (Statement rightS : subjectRight.getValues(right)) {
365 if (!rightS.getObject().equals(rightO))
367 if (!unreliableRight.contains(rightS))
369 if (leftS.getPredicate().equals(rightS.getPredicate()) ||
370 comparableResources.contains(leftS.getPredicate(), rightS.getPredicate())) {
371 unreliableLeft.remove(leftS);
372 unreliableRight.remove(rightS);
373 addComparable(leftS, rightS);
380 private void processUnreliable(Set<Statement> unreliableLeft, Set<Statement> unreliableRight, Stack<Resource> objectsLeft, Stack<Resource> objectsRight) throws DatabaseException {
381 MapList<Resource,Statement> subjectLeft = new MapList<Resource, Statement>();
382 MapList<Resource,Statement> subjectRight = new MapList<Resource, Statement>();
383 MapList<Resource,Statement> objectLeft = new MapList<Resource, Statement>();
384 MapList<Resource,Statement> objectRight = new MapList<Resource, Statement>();
386 for (Statement s : unreliableLeft) {
387 subjectLeft.add(s.getSubject(),s);
388 objectLeft.add(s.getObject(),s);
390 for (Statement s : unreliableRight) {
391 subjectRight.add(s.getSubject(),s);
392 objectRight.add(s.getObject(),s);
395 for (Resource ol : objectLeft.getKeys()) {
396 // all statements to the left side object
397 List<Statement> left = objectLeft.getValues(ol);
398 // all subjects that have statements to the left side object (ol)
399 Set<Resource> sLeft = new HashSet<Resource>();
400 // all matching subjects on the right side
401 Set<Resource> sRight = new HashSet<Resource>();
402 for (Statement s : left) {
403 sLeft.add(s.getSubject());
404 sRight.add(comparableResources.getRight(s.getSubject()));
407 // check if object left can be reliably identified by available statements
408 // if there are any objects on the left side with similar statements, object left cannot be mapped.
409 boolean hasSimilar = false;
410 MapList<Resource, Statement> comparableOLeft = new MapList<Resource, Statement>();
411 for (Resource sl : sLeft) {
412 for (Statement s : subjectLeft.getValues(sl)) {
413 if (!s.getObject().equals(ol)) {
414 comparableOLeft.add(s.getObject(),s);
419 compareStatements(ss1, ss2, objectsLeft, objectsRight,unreliableLeft,unreliableRight);
421 for (Resource similarOl : comparableOLeft.getKeys()) {
422 List<Statement> similarLeft = comparableOLeft.getValues(similarOl);
423 if (similarLeft.size() == left.size()) {
424 boolean useL[] = new boolean[left.size()];
425 boolean useSL[] = new boolean[left.size()];
426 for (int i = 0; i < left.size(); i++) {
430 for (int i = 0; i < left.size(); i++) {
431 for (int j = 0; j < left.size(); j++) {
434 // compare predicates
435 Resource pl = left.get(i).getPredicate();
436 Resource psl = similarLeft.get(j).getPredicate();
437 if (pl.equals(psl)) {
438 // compare objects (unreliable result is interpreted as positive match)
440 int comp = comparator.compare(g, left.get(i).getObject(), similarLeft.get(j).getObject(), true);
441 if (comp >= 0 && comp < Integer.MAX_VALUE) {
449 boolean diff = false;
450 for (int i = 0; i < left.size(); i++) {
451 if (!useL[i] || !useSL[i]) {
466 // all objects that subjects on the right side point to. Object left has its matching resource among these, if it has matching resource
467 MapList<Resource,Statement> possibleOR = new MapList<Resource, Statement>();
468 for (Resource sr : sRight) {
469 for (Statement s : subjectRight.getValues(sr))
470 possibleOR.add(s.getObject(),s);
473 // filter possible right side objects to those that have same amount of statements as the left side object
474 for (Resource or : possibleOR.getKeys().toArray(new Resource[possibleOR.getKeys().size()])) {
475 List<Statement> right = possibleOR.getValues(or);
476 if (right.size() != left.size())
477 possibleOR.remove(or);
481 // check for matching statements (comparable subjects, matching predicates)
482 MapList<Resource,Statement> matchingOR = new MapList<Resource, Statement>(); // list of objects that have matching statements
483 Map<Resource,Pair<int[], int[]>> matchingStatements = new HashMap<Resource, Pair<int[], int[]>>(); // matching statements
484 for (Resource or : possibleOR.getKeys()) {
485 List<Statement> right = possibleOR.getValues(or);
486 int iLeft[] = new int[left.size()];
487 int iRight[] = new int[right.size()];
489 for (int i = 0; i < left.size(); i++) {
494 for (int l = 0; l < left.size(); l++) {
495 Statement ls = left.get(l);
496 for (int r = 0; r < right.size(); r++) {
499 Statement rs = right.get(r);
500 if (!comparableResources.contains(ls.getSubject(), rs.getSubject()))
502 if (rcomp.compare(ls.getPredicate(),rs.getPredicate()) == 0) {
503 // compare objects (unreliable result is not accepted)
504 int comp = comparator.compare(g, ls.getObject(), rs.getObject());
505 if (comp > 0 && comp < Integer.MAX_VALUE) {
515 boolean success = true;
516 for (int i = 0; i < left.size(); i++) {
528 for (Statement s : right)
529 matchingOR.add(or,s);
530 matchingStatements.put(or, new Pair<int[], int[]>(iLeft, iRight));
533 // if there is only one matching right side object, we have found a match
534 if (matchingOR.getKeySize() == 1) {
535 Resource or = matchingOR.getKeys().iterator().next();
536 List<Statement> right = matchingOR.getValues(or);
537 Pair<int[], int[]> indices = matchingStatements.get(or);
540 objectsRight.add(or);
541 addComparable(ol, or);
542 for (int l = 0; l < left.size(); l++) {
543 int r = indices.first[l];
544 Statement sl = left.get(l);
545 Statement sr = right.get(r);
546 addComparable(sl, sr);
547 unreliableLeft.remove(sl);
548 unreliableRight.remove(sr);
560 private void processUnreliable2(Set<Statement> unreliableLeft, Set<Statement> unreliableRight, Stack<Resource> objectsLeft, Stack<Resource> objectsRight) throws DatabaseException {
561 MapList<Resource,Statement> subjectLeft = new MapList<Resource, Statement>();
562 MapList<Resource,Statement> subjectRight = new MapList<Resource, Statement>();
563 MapList<Resource,Statement> objectLeft = new MapList<Resource, Statement>();
564 MapList<Resource,Statement> objectRight = new MapList<Resource, Statement>();
566 for (Statement s : unreliableLeft) {
567 subjectLeft.add(s.getSubject(),s);
568 objectLeft.add(s.getObject(),s);
570 for (Statement s : unreliableRight) {
571 subjectRight.add(s.getSubject(),s);
572 objectRight.add(s.getObject(),s);
575 for (Resource ol : objectLeft.getKeys()) {
576 // all statements to the left side object
577 List<Statement> left = objectLeft.getValues(ol);
578 // all subjects that have statements to the left side object (ol)
579 Set<Resource> sLeft = new HashSet<Resource>();
580 // all matching subjects on the right side
581 Set<Resource> sRight = new HashSet<Resource>();
582 for (Statement s : left) {
583 sLeft.add(s.getSubject());
584 sRight.add(comparableResources.getRight(s.getSubject()));
587 if (sLeft.size() == 1 && sRight.size() == 1) {
588 List<Statement> ss1 = new ArrayList<Statement>(subjectLeft.getValues(sLeft.iterator().next()));
589 List<Statement> ss2 = new ArrayList<Statement>(subjectRight.getValues(sRight.iterator().next()));
591 int count = comparableStatements.size();
592 compareStatements(ss1, ss2, objectsLeft, objectsRight,unreliableLeft,unreliableRight);
593 if (comparableStatements.size() > count) {
594 for (Entry<Statement, Statement> entry : comparableStatements.getEntries()) {
595 unreliableLeft.remove(entry.getKey());
596 unreliableRight.remove(entry.getValue());
603 private void processUnreliableDeep(Set<Statement> unreliableLeft, Set<Statement> unreliableRight, Stack<Resource> objectsLeft, Stack<Resource> objectsRight) throws DatabaseException {
604 MapList<Resource,Statement> subjectLeft = new MapList<Resource, Statement>();
605 MapList<Resource,Statement> subjectRight = new MapList<Resource, Statement>();
606 MapList<Resource,Statement> objectLeft = new MapList<Resource, Statement>();
607 MapList<Resource,Statement> objectRight = new MapList<Resource, Statement>();
609 for (Statement s : unreliableLeft) {
610 subjectLeft.add(s.getSubject(),s);
611 objectLeft.add(s.getObject(),s);
613 for (Statement s : unreliableRight) {
614 subjectRight.add(s.getSubject(),s);
615 objectRight.add(s.getObject(),s);
617 for (Resource ol : objectLeft.getKeys()) {
618 Set<Path> pathsLeft = new HashSet<Path>();
619 for (Resource rel : traversed) {
620 pathsLeft.addAll(Path.create(g.getStatements(ol, rel)));
624 if (pathsLeft.size() == 0)
626 Collection<Path> endPaths = new ArrayList<Path>(1);
627 for (Path p : pathsLeft) {
628 if (comparableResources.containsLeft(p.getEnd())) {
632 if (endPaths.size() > 0) {
634 pathsLeft.addAll(endPaths);
638 if (pathsLeft.size() > 0) {
639 Resource sl = objectLeft.getValues(ol).get(0).getSubject();
640 Resource sr = comparableResources.getRight(sl);
641 Collection<Resource> possibleOR = new ArrayList<Resource>();
642 for (Statement s : subjectRight.getValues(sr)) {
643 possibleOR.add(s.getObject());
645 Map<Resource,Set<Path>> matchingPaths = new HashMap<Resource, Set<Path>>();
646 for (Resource or : possibleOR) {
647 Set<Path> possiblePathsRight = new HashSet<Path>();
648 for (Path leftPath : pathsLeft) {
649 possiblePathsRight.addAll(findComparableRight(leftPath, or));
651 if (hasMatchingPaths(pathsLeft, possiblePathsRight)) {
652 matchingPaths.put(or, possiblePathsRight);
655 if (matchingPaths.size() > 0) {
656 if (matchingPaths.size() == 1) {
657 Resource or = matchingPaths.keySet().iterator().next();
660 objectsRight.add(or);
661 addComparable(ol, or);
662 Collection<Statement> statementsLeft = objectLeft.getValues(ol);
663 Collection<Statement> statementsRight = objectRight.getValues(or);
664 unreliableLeft.removeAll(statementsLeft);
665 unreliableRight.removeAll(statementsRight);
666 BijectionMap<Path,Path> map = getMatchingPaths(pathsLeft, matchingPaths.get(or));
667 for (Path left : map.getLeftSet()) {
668 Path right = map.getRight(left);
669 for (int i = 0; i < left.getLength(); i++) {
670 addComparable(left.getStatements().get(i),right.getStatements().get(i));
681 private boolean hasMatchingPaths(Set<Path> leftPaths, Set<Path> rightPaths) {
682 if (leftPaths.size() != rightPaths.size())
684 BijectionMap<Path,Path> map = getMatchingPaths(leftPaths, rightPaths);
685 return map.size() == leftPaths.size();
688 private BijectionMap<Path,Path> getMatchingPaths(Set<Path> leftPaths, Set<Path> rightPaths) {
689 BijectionMap<Path,Path> map = new BijectionMap<Path, Path>();
690 for (Path leftPath : leftPaths) {
691 for (Path rightPath : rightPaths) {
692 if (map.containsRight(rightPath))
694 if (leftPath.getLength() != rightPath.getLength())
696 if (comparableResources.contains(leftPath.getEnd(), rightPath.getEnd())) {
697 map.map(leftPath, rightPath);
705 private void expand(Set<Path> paths) throws DatabaseException {
706 Set<Path> stepPathsLeft = new HashSet<Path>();
707 if (paths.size() == 0)
709 int length = paths.iterator().next().getLength() + 1;
710 for (Path p : paths) {
711 for (Resource rel : traversed) {
712 stepPathsLeft.addAll(Path.expand(p,g.getStatements(p.getEnd(), rel)));
716 for (Path p : stepPathsLeft) {
717 if (p.getLength() == length)
722 private Collection<Path> findComparableRight(Path leftPath, Resource beginRight) throws DatabaseException {
723 Set<Path> rightPaths = new HashSet<Path>();
724 rightPaths.addAll(Path.create(g.getStatements(beginRight, getRight(leftPath.getStatements().get(0).getPredicate()))));
725 for (int i = 1; i < leftPath.getLength(); i++) {
726 if (rightPaths.size() == 0)
728 Set<Path> stepPaths = new HashSet<Path>();
729 for (Path p : rightPaths) {
730 stepPaths.addAll(Path.expand(p, g.getStatements(p.getEnd(), getRight(leftPath.getStatements().get(i).getPredicate()))));
733 for (Path p : stepPaths)
734 if (p.getLength() == i+1)
741 private Resource getRight(Resource r) {
742 if (comparableResources.containsLeft(r))
743 return comparableResources.getRight(r);
749 public BijectionMap<Statement, Statement> getComparableStatements() {
750 return comparableStatements;
753 public BijectionMap<Resource, Resource> getComparableResources() {
754 return comparableResources;
757 public GraphChanges getChanges() {
758 return new GraphChanges(r1,r2,changes1,changes2,modifications,comparableResources);
761 private void addComparable(Statement left, Statement right) throws DatabaseException {
762 addComparable(left.getObject(), right.getObject());
763 comparableStatements.map(left, right);
764 //comparableResources.map(left.getObject(), right.getObject());
767 private void addComparable(Resource left, Resource right) throws DatabaseException {
768 if(!comparableResources.contains(left, right)) {
769 if (comparableResources.containsLeft(left)||comparableResources.containsRight(right)) {
770 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.");
772 if (DEBUG) System.out.println(left + " = " + right);
773 comparableResources.map(left, right);
779 public List<Statement> filterAsserted(Resource r, Collection<Statement> in) throws DatabaseException {
780 List<Statement> out = new ArrayList<Statement>();
781 for (Statement s : in) {
782 if (!s.isAsserted(r))
791 private String printStatement(ReadGraph graph, Statement s) throws DatabaseException {
792 return NameUtils.getSafeName(graph, s.getSubject()) + " " + NameUtils.getSafeName(graph, s.getPredicate()) + " " + NameUtils.getSafeName(graph, s.getObject());
795 private List<Statement> filterTraversed(List<Statement> in) throws DatabaseException {
796 return filter(traversed, in);
799 private List<Statement> filterNonTested(List<Statement> in) throws DatabaseException {
800 return filter(nonTested, in);
803 private List<Statement> filterNonTraversed(List<Statement> in) throws DatabaseException {
804 return filter(nonTraversed, in);
807 private List<Statement> filter(Collection<Resource> toFilter, List<Statement> in) throws DatabaseException {
808 if (toFilter.size() == 0)
810 List<Statement> out = new ArrayList<Statement>();
811 for (Statement s : in) {
812 boolean usable = true;
813 for (Resource r : toFilter) {
814 if (g.isSubrelationOf(s.getPredicate(),r)) {
828 private void addDeletion(Statement s) {
829 if (!changes1Set.contains(s)) {
835 private void addAddition(Statement s) {
836 if (!changes2Set.contains(s)) {
842 private void addModification(Resource sub1, Statement s1, Resource sub2, Statement s2) {
843 Modification mod = new Modification(sub1, sub2, s1, s2);
844 if (!modificationsSet.contains(mod)) {
845 modificationsSet.add(mod);
846 modifications.add(mod);
850 public void sortStatement(List<Statement> list1, List<Statement> list2) {
851 sortStatement(list1, list2, scomp);
854 public void sortStatement(List<Statement> list1, List<Statement> list2, Comparator<Statement> scomp) {
855 Collections.sort(list1,scomp);
856 Collections.sort(list2,scomp);
858 List<Statement> sorted1 = new ArrayList<Statement>(list1.size());
859 List<Statement> sorted2 = new ArrayList<Statement>(list2.size());
860 sorted1.addAll(list1);
861 sorted2.addAll(list2);
865 for (int i = 0; i < list1.size(); ) {
866 Statement s1 = list1.get(i);
867 int same1 = sameRel(list1, i);
868 for (int j = 0; j < list2.size(); j++) {
869 Statement s2 = list2.get(j);
870 if (scomp.compare(s1, s2) == 0) {
871 int same2 = sameRel(list2, j);
872 copy(sorted1,ss1,list1,i,same1);
874 copy(sorted2,ss2,list2,j,same2);
881 if (ss1 < sorted1.size()) {
882 for (Statement s : list1) {
883 if (!sorted1.contains(s)) {
889 if (ss2 < sorted2.size()) {
890 for (Statement s : list2) {
891 if (!sorted2.contains(s)) {
900 list1.addAll(sorted1);
901 list2.addAll(sorted2);
904 public <T> void copy(List<T> to, int toIndex, List<T> from, int fromIndex, int amount) {
905 for (int i = 0; i < amount; i++) {
906 to.set(toIndex + i, from.get(fromIndex+ i));
910 public void sortResource(List<Resource> list1, List<Resource> list2) {
911 Collections.sort(list1,rcomp);
913 for (int i = 0; i < list1.size(); i++) {
914 Resource s1 = list1.get(i);
915 for (int j = js; j < list2.size(); j++) {
916 Resource s2 = list2.get(j);
917 if (rcomp.compare(s1, s2) == 0) {
918 Resource t = list2.get(js);
928 private void compareStatements(List<Statement> ss1, List<Statement> ss2, Stack<Resource> objectsLeft, Stack<Resource> objectsRight, Collection<Statement> unreliableLeft, Collection<Statement> unreliableRight) throws DatabaseException {
929 sortStatement(ss1, ss2);
935 if (i1 >= ss1.size()) {
936 if (i2 >= ss2.size()) {
939 while (i2 < ss2.size()) {
940 if (DEBUG) System.out.println("Compare Statements addition " + printStatement(g,ss2.get(i2)));
942 addAddition(ss2.get(i2));
947 } else if (i2 >= ss2.size()) {
948 while (i1 < ss1.size()) {
949 if (DEBUG) System.out.println("Compare Statements deletion " + printStatement(g,ss1.get(i1)));
950 addDeletion(ss1.get(i1));
955 int same1 = sameRel(ss1, i1);
956 int same2 = sameRel(ss2, i2);
957 int c = rcomp.compare(ss1.get(i1).getPredicate(),ss2.get(i2).getPredicate());
959 compareStatements(ss1, i1, same1, ss2, i2, same2,objectsLeft,objectsRight,unreliableLeft,unreliableRight);
963 for (int i = 0; i < same1; i++) {
964 if (DEBUG) System.out.println("Compare Statements deletion " + printStatement(g,ss1.get(i+i1)));
965 addDeletion(ss1.get(i+i1));
969 for (int i = 0; i < same2; i++) {
970 if (DEBUG) System.out.println("Compare Statements addition " + printStatement(g,ss2.get(i+i2)));
971 addAddition(ss2.get(i+i2));
981 private int sameRel(List<Statement> statements, int off) {
982 if (statements.size() <= off)
985 long id = statements.get(off).getPredicate().getResourceId();
986 for (int i = off+1; i <statements.size(); i++) {
987 if (statements.get(i).getPredicate().getResourceId() == id)
996 private int compareObject(Resource o1, Resource o2) throws DatabaseException {
999 if (comparableResources.contains(o1, o2))
1001 if (comparableResources.containsLeft(o1))
1002 return Integer.MAX_VALUE;
1003 if (comparableResources.containsRight(o2))
1004 return Integer.MAX_VALUE;
1005 if (nonMatchedLeft.contains(o1))
1006 return Integer.MAX_VALUE;
1007 if (nonMatchedRight.contains(o2))
1008 return Integer.MAX_VALUE;
1009 return comparator.compare(g, o1, o2);
1012 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 {
1013 boolean[] used1 = new boolean[len1];
1014 for (int i = 0; i < used1.length; i++) {
1018 boolean[] used2 = new boolean[len2];
1019 for (int i = 0; i < used2.length; i++) {
1023 // left, right, difference
1024 List<List<Integer>> differences = new ArrayList<List<Integer>>();
1025 for (int i1 = off1; i1 < off1 + len1; i1++) {
1026 Statement s1 = ss1.get(i1);
1027 List<Integer> diff = new ArrayList<Integer>();
1028 for (int i2 = off2; i2 < off2 + len2; i2++) {
1029 Statement s2 = ss2.get(i2);
1030 int d = compareObject(s1.getObject(), s2.getObject());
1032 for (Resource t : strong) {
1033 if (s1.getPredicate().equals(t) || g.isSubrelationOf(s1.getPredicate(), t)) {
1041 differences.add(diff);
1044 MapList<Integer, Integer> priorities = new MapList<Integer, Integer>();
1045 for (int i = 0; i < differences.size(); i++) {
1046 List<Integer> list = differences.get(i);
1047 for (int j = 0; j < list.size(); j++) {
1048 priorities.add(list.get(j), i);
1052 Integer[] pris = priorities.getKeys(new Integer[]{});
1055 for (Integer pri : pris) {
1056 if (pri == Integer.MAX_VALUE) {
1058 } else if (pri == 0) {
1061 List<Integer> i1s = priorities.getValues(pri);
1062 for (Integer i1 : i1s) {
1065 List<Integer> i2diff = differences.get(i1);
1066 for (int i2 = 0; i2 < i2diff.size(); i2++) {
1067 if (i2diff.get(i2) == pri) {
1072 Statement s1 = ss1.get(i1+off1);
1073 Statement s2 = ss2.get(i2+off2);
1075 if (objectsLeft != null) {
1076 objectsLeft.add(s1.getObject());
1077 objectsRight.add(s2.getObject());
1079 addComparable(s1, s2);
1087 for (Integer pri : pris) {
1090 Set<Statement> s1s = new HashSet<Statement>();
1091 Set<Statement> s2s = new HashSet<Statement>();
1092 Set<Integer> s1i = new HashSet<Integer>();
1093 Set<Integer> s2i = new HashSet<Integer>();
1094 List<Integer> i1s = priorities.getValues(pri);
1095 for (Integer i1 : i1s) {
1098 List<Integer> i2diff = differences.get(i1);
1099 for (int i2 = 0; i2 < i2diff.size(); i2++) {
1100 if (i2diff.get(i2) == pri) {
1103 Statement s1 = ss1.get(i1+off1);
1104 Statement s2 = ss2.get(i2+off2);
1112 if (unreliableLeft != null) {
1113 unreliableLeft.addAll(s1s);
1114 unreliableRight.addAll(s2s);
1116 for (Integer i : s1i)
1118 for (Integer i : s2i)
1122 for (int i1 = off1; i1 < off1 + len1; i1++) {
1123 if (!used1[i1-off1]) {
1124 if (DEBUG) System.out.println("Compare Object deletion " + printStatement(g,ss1.get(i1)));
1125 addDeletion(ss1.get(i1));
1128 for (int i2 = off2; i2 < off2 + len2; i2++) {
1129 if (!used2[i2-off2]) {
1130 if (DEBUG) System.out.println("Compare Object addition " + printStatement(g,ss2.get(i2)));
1131 addAddition(ss2.get(i2));
1139 * compares properties, assumes functional relations
1142 * @throws ServiceException
1143 * @throws DoesNotContainValueException
1144 * @throws ValidationException
1146 private void compareProps(Resource r1, Resource r2) throws DatabaseException {
1147 if (DEBUG) System.out.println("compareProps " + r1 + " " + NameUtils.getSafeName(g, r1) + " " + r2 + " " + NameUtils.getSafeName(g, r2));
1148 List<Statement> ss1 = new ArrayList<Statement>();
1149 List<Statement> ss2 = new ArrayList<Statement>();
1150 ss1.addAll(g.getStatements(r1, b.HasProperty));
1151 ss2.addAll(g.getStatements(r2, b.HasProperty));
1152 ss1 = filterNonTested(ss1);
1153 ss2 = filterNonTested(ss2);
1154 sortStatement(ss1, ss2);
1160 if (i1 >= ss1.size()) {
1161 if (i2 >= ss2.size())
1164 while (i2 < ss2.size()) {
1165 if (DEBUG) System.out.println("Compare Prop diff2 " + printStatement(g,ss2.get(i2)));
1166 addAddition(ss2.get(i2));
1171 } else if (i2 >= ss2.size()) {
1172 while (i1 < ss1.size()) {
1173 if (DEBUG) System.out.println("Compare Prop diff1 " + printStatement(g,ss1.get(i1)));
1174 addDeletion(ss1.get(i1));
1179 Statement s1 = ss1.get(i1);
1180 Statement s2 = ss2.get(i2);
1181 if (s1.isAsserted(r1) && s2.isAsserted(r2)) {
1186 int c = scomp.compare(s1, s2);
1189 boolean b1 = g.hasValue(s1.getObject());
1190 boolean b2 = g.hasValue(s2.getObject());
1193 // Object v1 = g.getValue(s1.getObject());
1194 // Object v2 = g.getValue(s2.getObject());
1195 // boolean eq = compareValue(v1, v2);
1196 boolean eq = compareValue(g,b,s1.getObject(), s2.getObject());
1198 addModification(r1,s1,r2,s2);
1199 if (!s1.isAsserted(r1) && !s2.isAsserted(r2))
1200 addComparable(s1, s2);
1203 if (!s1.getObject().equals(s1.getSubject()) && !s2.getObject().equals(s2.getSubject()))
1204 compareProps(s1.getObject(), s2.getObject());
1207 addModification(r1,s1,r2,s2);
1208 if (!s1.isAsserted(r1) && !s2.isAsserted(r2))
1209 addComparable(s1, s2);
1216 if (DEBUG) System.out.println("Compare Prop diff1s " + printStatement(g,s1));
1223 if (DEBUG) System.out.println("Compare Prop diff2s " + printStatement(g,s2));
1237 public static boolean compareValue(ReadGraph g, Layer0 b, Resource r1, Resource r2) throws DatabaseException {
1238 Resource t1 = g.getSingleType(r1);
1239 Resource t2 = g.getSingleType(r2);
1242 if (t1.equals(b.Integer)) {
1243 int v1 = g.getValue(r1, Bindings.INTEGER);
1244 int v2 = g.getValue(r2, Bindings.INTEGER);
1246 } else if (t1.equals(b.Float)) {
1247 float v1 = g.getValue(r1, Bindings.FLOAT);
1248 float v2 = g.getValue(r2, Bindings.FLOAT);
1250 } else if (t1.equals(b.Double)) {
1251 double v1 = g.getValue(r1, Bindings.DOUBLE);
1252 double v2 = g.getValue(r2, Bindings.DOUBLE);
1254 } else if (t1.equals(b.String)) {
1255 String v1 = g.getValue(r1, Bindings.STRING);
1256 String v2 = g.getValue(r2, Bindings.STRING);
1257 return v1.equals(v2);
1258 } else if (t1.equals(b.Boolean)) {
1259 boolean v1 = g.getValue(r1, Bindings.BOOLEAN);
1260 boolean v2 = g.getValue(r2, Bindings.BOOLEAN);
1262 } else if (t1.equals(b.Byte)) {
1263 byte v1 = g.getValue(r1, Bindings.BYTE);
1264 byte v2 = g.getValue(r2, Bindings.BYTE);
1266 } else if (t1.equals(b.Long)) {
1267 long v1 = g.getValue(r1, Bindings.LONG);
1268 long v2 = g.getValue(r2, Bindings.LONG);
1270 } else if (t1.equals(b.IntegerArray)) {
1271 int[] v1 = g.getValue(r1, Bindings.INT_ARRAY);
1272 int[] v2 = g.getValue(r2, Bindings.INT_ARRAY);
1273 return Arrays.equals(v1,v2);
1274 } else if (t1.equals(b.FloatArray)) {
1275 float[] v1 = g.getValue(r1, Bindings.FLOAT_ARRAY);
1276 float[] v2 = g.getValue(r2, Bindings.FLOAT_ARRAY);
1277 return Arrays.equals(v1,v2);
1278 } else if (t1.equals(b.DoubleArray)) {
1279 double[] v1 = g.getValue(r1, Bindings.DOUBLE_ARRAY);
1280 double[] v2 = g.getValue(r2, Bindings.DOUBLE_ARRAY);
1281 return Arrays.equals(v1,v2);
1282 } else if (t1.equals(b.StringArray)) {
1283 String[] v1 = g.getValue(r1, Bindings.STRING_ARRAY);
1284 String[] v2 = g.getValue(r2, Bindings.STRING_ARRAY);
1285 return Arrays.equals(v1,v2);
1286 } else if (t1.equals(b.BooleanArray)) {
1287 boolean[] v1 = g.getValue(r1, Bindings.BOOLEAN_ARRAY);
1288 boolean[] v2 = g.getValue(r2, Bindings.BOOLEAN_ARRAY);
1289 return Arrays.equals(v1,v2);
1290 } else if (t1.equals(b.ByteArray)) {
1291 byte[] v1 = g.getValue(r1, Bindings.BYTE_ARRAY);
1292 byte[] v2 = g.getValue(r2, Bindings.BYTE_ARRAY);
1293 return Arrays.equals(v1,v2);
1294 } else if (t1.equals(b.LongArray)) {
1295 long[] v1 = g.getValue(r1, Bindings.LONG_ARRAY);
1296 long[] v2 = g.getValue(r2, Bindings.LONG_ARRAY);
1297 return Arrays.equals(v1,v2);
1299 Object v1 = g.getValue(r1);
1300 Object v2 = g.getValue(r2);
1301 return compareValue(v1, v2);
1306 public static boolean compareValue(Object v1, Object v2) {
1307 if (v1 instanceof Object[] && v2 instanceof Object[])
1308 return Arrays.deepEquals((Object[])v1, (Object[])v2);
1309 else if (v1 instanceof int[] && v2 instanceof int[])
1310 return Arrays.equals((int[])v1, (int[])v2);
1311 else if (v1 instanceof float[] && v2 instanceof float[])
1312 return Arrays.equals((float[])v1, (float[])v2);
1313 else if (v1 instanceof double[] && v2 instanceof double[])
1314 return Arrays.equals((double[])v1, (double[])v2);
1315 else if (v1 instanceof long[] && v2 instanceof long[])
1316 return Arrays.equals((long[])v1, (long[])v2);
1317 else if (v1 instanceof byte[] && v2 instanceof byte[])
1318 return Arrays.equals((byte[])v1, (byte[])v2);
1319 else if (v1 instanceof boolean[] && v2 instanceof boolean[])
1320 return Arrays.equals((boolean[])v1, (boolean[])v2);
1322 return v1.equals(v2);
1326 public class PredicateComparator implements Comparator<Statement> {
1328 public int compare(Statement o1, Statement o2) {
1329 if (comparableResources.contains(o1.getPredicate(), o2.getPredicate()))
1331 if (o1.getPredicate().getResourceId() < o2.getPredicate().getResourceId())
1333 if (o1.getPredicate().getResourceId() > o2.getPredicate().getResourceId())
1339 public class SubjectComparator implements Comparator<Statement> {
1341 public int compare(Statement o1, Statement o2) {
1342 if (comparableResources.contains(o1.getSubject(), o2.getSubject()))
1344 if (o1.getSubject().getResourceId() < o2.getSubject().getResourceId())
1346 if (o1.getSubject().getResourceId() > o2.getSubject().getResourceId())
1352 public class ObjectComparator implements Comparator<Statement> {
1354 public int compare(Statement o1, Statement o2) {
1355 if (comparableResources.contains(o1.getObject(), o2.getObject()))
1357 if (o1.getObject().getResourceId() < o2.getObject().getResourceId())
1359 if (o1.getObject().getResourceId() > o2.getObject().getResourceId())
1365 public static class FullStatementComparator implements Comparator<Statement> {
1367 public int compare(Statement o1, Statement o2) {
1368 if (o1.getSubject().getResourceId() < o2.getSubject().getResourceId())
1370 if (o1.getSubject().getResourceId() > o2.getSubject().getResourceId())
1372 if (o1.getPredicate().getResourceId() < o2.getPredicate().getResourceId())
1374 if (o1.getPredicate().getResourceId() > o2.getPredicate().getResourceId())
1376 if (o1.getObject().getResourceId() < o2.getObject().getResourceId())
1378 if (o1.getObject().getResourceId() > o2.getObject().getResourceId())
1384 public class ResComparator implements Comparator<Resource> {
1386 public int compare(Resource o1, Resource o2) {
1387 if (comparableResources.contains(o1, o2))
1389 if (o1.getResourceId() < o2.getResourceId())
1391 if (o1.getResourceId() > o2.getResourceId())