001: /*
002: * Copyright Aduna (http://www.aduna-software.com/) (c) 2007.
003: *
004: * Licensed under the Aduna BSD-style license.
005: */
006: package org.openrdf.model.util;
007:
008: import java.util.ArrayList;
009: import java.util.HashMap;
010: import java.util.LinkedHashSet;
011: import java.util.List;
012: import java.util.Map;
013: import java.util.Set;
014:
015: import info.aduna.collections.iterators.Iterators;
016:
017: import org.openrdf.model.BNode;
018: import org.openrdf.model.Resource;
019: import org.openrdf.model.Statement;
020: import org.openrdf.model.URI;
021: import org.openrdf.model.Value;
022:
023: /**
024: * @author Arjohn Kampman
025: */
026: public class ModelUtil {
027:
028: /**
029: * Compares two models, defined by two statement collections, and returns
030: * <tt>true</tt> if they are equal. Models are equal if they contain the
031: * same set of statements. Blank node IDs are not relevant for model
032: * equality, they are mapped from one model to the other by using the
033: * attached properties.
034: */
035: public static boolean equals(Iterable<? extends Statement> model1,
036: Iterable<? extends Statement> model2) {
037: // Filter duplicates
038: Set<Statement> set1 = new LinkedHashSet<Statement>();
039: Iterators.addAll(model1.iterator(), set1);
040:
041: Set<Statement> set2 = new LinkedHashSet<Statement>();
042: Iterators.addAll(model2.iterator(), set2);
043:
044: return equals(set1, set2);
045: }
046:
047: /**
048: * Compares two models, defined by two statement collections, and returns
049: * <tt>true</tt> if they are equal. Models are equal if they contain the
050: * same set of statements. Blank node IDs are not relevant for model
051: * equality, they are mapped from one model to the other by using the
052: * attached properties.
053: */
054: public static boolean equals(Set<? extends Statement> model1,
055: Set<? extends Statement> model2) {
056: // Compare the number of statements in both sets
057: if (model1.size() != model2.size()) {
058: return false;
059: }
060:
061: return isSubsetInternal(model1, model2);
062: }
063:
064: /**
065: * Compares two models, defined by two statement collections, and returns
066: * <tt>true</tt> if the first model is a subset of the second model.
067: */
068: public static boolean isSubset(
069: Iterable<? extends Statement> model1,
070: Iterable<? extends Statement> model2) {
071: // Filter duplicates
072: Set<Statement> set1 = new LinkedHashSet<Statement>();
073: Iterators.addAll(model1.iterator(), set1);
074:
075: Set<Statement> set2 = new LinkedHashSet<Statement>();
076: Iterators.addAll(model2.iterator(), set2);
077:
078: return isSubset(set1, set2);
079: }
080:
081: /**
082: * Compares two models, defined by two statement collections, and returns
083: * <tt>true</tt> if the first model is a subset of the second model.
084: */
085: public static boolean isSubset(Set<? extends Statement> model1,
086: Set<? extends Statement> model2) {
087: // Compare the number of statements in both sets
088: if (model1.size() > model2.size()) {
089: return false;
090: }
091:
092: return isSubsetInternal(model1, model2);
093: }
094:
095: private static boolean isSubsetInternal(
096: Set<? extends Statement> model1,
097: Set<? extends Statement> model2) {
098: // try to create a full blank node mapping
099: return matchModels(model1, model2);
100: }
101:
102: private static boolean matchModels(Set<? extends Statement> model1,
103: Set<? extends Statement> model2) {
104: // Compare statements without blank nodes first, save the rest for later
105: List<Statement> model1BNodes = new ArrayList<Statement>(model1
106: .size());
107:
108: for (Statement st : model1) {
109: if (st.getSubject() instanceof BNode
110: || st.getObject() instanceof BNode) {
111: model1BNodes.add(st);
112: } else {
113: if (!model2.contains(st)) {
114: return false;
115: }
116: }
117: }
118:
119: return matchModels(model1BNodes, model2,
120: new HashMap<BNode, BNode>(), 0);
121: }
122:
123: /**
124: * A recursive method for finding a complete mapping between blank nodes in
125: * model1 and blank nodes in model2. The algorithm does a depth-first search
126: * trying to establish a mapping for each blank node occurring in model1.
127: *
128: * @param model1
129: * @param model2
130: * @param bNodeMapping
131: * @param idx
132: * @return true if a complete mapping has been found, false otherwise.
133: */
134: private static boolean matchModels(
135: List<? extends Statement> model1,
136: Iterable<? extends Statement> model2,
137: Map<BNode, BNode> bNodeMapping, int idx) {
138: boolean result = false;
139:
140: if (idx < model1.size()) {
141: Statement st1 = model1.get(idx);
142:
143: List<Statement> matchingStats = findMatchingStatements(st1,
144: model2, bNodeMapping);
145:
146: for (Statement st2 : matchingStats) {
147: // Map bNodes in st1 to bNodes in st2
148: Map<BNode, BNode> newBNodeMapping = new HashMap<BNode, BNode>(
149: bNodeMapping);
150:
151: if (st1.getSubject() instanceof BNode
152: && st2.getSubject() instanceof BNode) {
153: newBNodeMapping.put((BNode) st1.getSubject(),
154: (BNode) st2.getSubject());
155: }
156:
157: if (st1.getObject() instanceof BNode
158: && st2.getObject() instanceof BNode) {
159: newBNodeMapping.put((BNode) st1.getObject(),
160: (BNode) st2.getObject());
161: }
162:
163: // FIXME: this recursive implementation has a high risk of
164: // triggering a stack overflow
165:
166: // Enter recursion
167: result = matchModels(model1, model2, newBNodeMapping,
168: idx + 1);
169:
170: if (result == true) {
171: // models match, look no further
172: break;
173: }
174: }
175: } else {
176: // All statements have been mapped successfully
177: result = true;
178: }
179:
180: return result;
181: }
182:
183: private static List<Statement> findMatchingStatements(Statement st,
184: Iterable<? extends Statement> model,
185: Map<BNode, BNode> bNodeMapping) {
186: List<Statement> result = new ArrayList<Statement>();
187:
188: for (Statement modelSt : model) {
189: if (statementsMatch(st, modelSt, bNodeMapping)) {
190: // All components possibly match
191: result.add(modelSt);
192: }
193: }
194:
195: return result;
196: }
197:
198: private static boolean statementsMatch(Statement st1,
199: Statement st2, Map<BNode, BNode> bNodeMapping) {
200: URI pred1 = st1.getPredicate();
201: URI pred2 = st2.getPredicate();
202:
203: if (!pred1.equals(pred2)) {
204: // predicates don't match
205: return false;
206: }
207:
208: Resource subj1 = st1.getSubject();
209: Resource subj2 = st2.getSubject();
210:
211: if (!(subj1 instanceof BNode)) {
212: if (!subj1.equals(subj2)) {
213: // subjects are not bNodes and don't match
214: return false;
215: }
216: } else { // subj1 instanceof BNode
217: BNode mappedBNode = bNodeMapping.get(subj1);
218:
219: if (mappedBNode != null) {
220: // bNode 'subj1' was already mapped to some other bNode
221: if (!subj2.equals(mappedBNode)) {
222: // 'subj1' and 'subj2' do not match
223: return false;
224: }
225: } else {
226: // 'subj1' was not yet mapped. we need to check if 'subj2' is a
227: // possible mapping candidate
228: if (bNodeMapping.containsValue(subj2)) {
229: // 'subj2' is already mapped to some other value.
230: return false;
231: }
232: }
233: }
234:
235: Value obj1 = st1.getObject();
236: Value obj2 = st2.getObject();
237:
238: if (!(obj1 instanceof BNode)) {
239: if (!obj1.equals(obj2)) {
240: // objects are not bNodes and don't match
241: return false;
242: }
243: } else { // obj1 instanceof BNode
244: BNode mappedBNode = bNodeMapping.get(obj1);
245:
246: if (mappedBNode != null) {
247: // bNode 'obj1' was already mapped to some other bNode
248: if (!obj2.equals(mappedBNode)) {
249: // 'obj1' and 'obj2' do not match
250: return false;
251: }
252: } else {
253: // 'obj1' was not yet mapped. we need to check if 'obj2' is a
254: // possible mapping candidate
255: if (bNodeMapping.containsValue(obj2)) {
256: // 'obj2' is already mapped to some other value.
257: return false;
258: }
259: }
260: }
261:
262: return true;
263: }
264: }
|