sailutil.java

这是外国一个开源推理机

/*  Sesame - Storage and Querying architecture for RDF and RDF Schema
 *  Copyright (C) 2001-2005 Aduna
 *
 *  Contact: 
 *  	Aduna
 *  	Prinses Julianaplein 14 b
 *  	3817 CS Amersfoort
 *  	The Netherlands
 *  	tel. [phone]
 *  	fax. [phone]
 *
 *  	http://aduna.biz/
 *  	http://www.openrdf.org/
 *  
 *  This library is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU Lesser General Public
 *  License as published by the Free Software Foundation; either
 *  version 2.1 of the License, or (at your option) any later version.
 *
 *  This library is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 *  Lesser General Public License for more details.
 *
 *  You should have received a copy of the GNU Lesser General Public
 *  License along with this library; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

package org.openrdf.sesame.sail;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import org.openrdf.model.BNode;
import org.openrdf.model.Resource;
import org.openrdf.model.Statement;
import org.openrdf.model.URI;
import org.openrdf.model.Value;

/**
 * Defines utility methods for working with Sails.
 *
 * @author Arjohn Kampman
 * @version $Revision: 1.6 $
 **/
public class SailUtil {

	/**
	 * Searches a stack of Sails from top to bottom for a Sail that is
	 * an instance of the suppied class or interface. The first Sail that
	 * matches (i.e. the one closest to the top) is returned.
	 *
	 * @param topSail The top of the Sail stack.
	 * @param sailClass A class or interface.
	 * @return A Sail that is an instance of sailClass, or null if no such
	 * Sail was found.
	 **/
	public static Sail findSailInStack(Sail topSail, Class sailClass) {
		if (sailClass == null) {
			return null;
		}

		// Check Sails on the stack one by one, starting with the top-most.
		Sail currentSail = topSail;

		while (currentSail != null) {
			// Check current Sail
			if (sailClass.isInstance(currentSail)) {
				break;
			}

			// Current Sail is not an instance of sailClass, check the
			// rest of the stack
			if (currentSail instanceof StackedSail) {
				currentSail = ((StackedSail)currentSail).getBaseSail();
			}
			else {
				// We've reached the bottom of the stack
				currentSail = null;
			}
		}

		return currentSail;
	}
	
	/**
	 * Compares the models of two RdfSource objects and returns true if they
	 * are equal. Models are equal if they contain the same set of statements.
	 * bNodes IDs are not relevant for model equality, they are mapped from
	 * one model to the other by using the attached properties.
	 **/
	public static boolean modelsEqual(RdfSource rdfSource1, RdfSource rdfSource2){
		// Fetch statements from rdfSource1 and rdfSource2
		List model1 = _getListFromSource(rdfSource1);
		List model2 = _getListFromSource(rdfSource2);

		// Compare the number of statements in both sets
		if (model1.size() != model2.size()) {
			return false;
		}

		return _isSubset(model1, model2);
	}

	private static List _getListFromSource(RdfSource source) {
		List model = new LinkedList();
		StatementIterator statIter = source.getStatements(null, null, null);
		while (statIter.hasNext()) {
			model.add(statIter.next());
		}
		statIter.close();
		return model;
	}

	/**
	 * Compares the models of two RdfSource objects and returns true if rdfSource1 is
	 * a subset of rdfSource2. 
	 **/
	public static boolean isSubset(RdfSource rdfSource1, RdfSource rdfSource2) {
		// Fetch statements from rdfSource1 and rdfSource2
		List model1 = _getListFromSource(rdfSource1);
		List model2 = _getListFromSource(rdfSource2);

		// Compare the number of statements in both sets
		if (model1.size() > model2.size()) {
			return false;
		}
		
		return _isSubset(model1, model2);
	}
	
	private static boolean _isSubset(List model1, List model2) {

		// Compare statements that don't contain bNodes
		Iterator iter1 = model1.iterator();
		while (iter1.hasNext()) {
			Statement st = (Statement)iter1.next();

			if (st.getSubject() instanceof BNode ||
				st.getObject() instanceof BNode)
			{
				// One or more of the statement's components is a bNode,
				// these statements are handled later
				continue;
			}

			// Try to remove the statement from model2
			boolean removed = model2.remove(st);
			if (removed) {
				iter1.remove();
			}
			else {
				// Statement could not be found in stat2; models are not equal
				return false;
			}
		}

		boolean result = _matchModels(model1, model2, new HashMap(), 0);

		return result;
	}

	protected static boolean _matchModels(List model1, List model2, Map bNodeMapping, int idx) {
		boolean result = false;

		// Find next statement with unmapped bNode(s)
		// in model1, starting from index 'idx'
		Statement st1 = null;
		for (; idx < model1.size(); idx++) {
			st1 = (Statement)model1.get(idx);

			if (st1.getSubject() instanceof BNode && !bNodeMapping.containsKey(st1.getSubject()) ||
				st1.getObject() instanceof BNode && !bNodeMapping.containsKey(st1.getObject()))
			{
				// Found a statement containing an unmapped bNode
				break;
			}
		}

		if (idx < model1.size()) {
			// Found a statement containing an unmapped bNode,
			// find statements in model2 that potentially matches st1
			List matchingStats = _findMatchingStatements(st1, model2, bNodeMapping);

			Iterator iter = matchingStats.iterator();
			while (iter.hasNext()) {
				Statement st2 = (Statement)iter.next();

				// Map bNodes in st1 to bNodes in st2
				Map newBNodeMapping = new HashMap(bNodeMapping);
				if (st1.getSubject() instanceof BNode && st2.getSubject() instanceof BNode) {
					newBNodeMapping.put(st1.getSubject(), st2.getSubject());
				}
				if (st1.getObject() instanceof BNode && st2.getObject() instanceof BNode) {
					newBNodeMapping.put(st1.getObject(), st2.getObject());
				}

				// Enter recursion
				result = _matchModels(model1, model2, newBNodeMapping, idx+1);

				if (result == true) {
					// models match, look no further
					break;
				}
			}
		}
		else {
			// All bNodes have been mapped, compare
			// the models using this mapping
			result = _modelsEqual(model1, model2, bNodeMapping);
		}

		return result;
	}

	protected static List _findMatchingStatements(Statement st, List model, Map bNodeMapping) {
		List result = new ArrayList();

		Iterator iter = model.iterator();
		while (iter.hasNext()) {
			Statement modelSt = (Statement)iter.next();

			if (_statementsMatch(st, modelSt, bNodeMapping)) {
				// All components possibly match
				result.add(modelSt);
			}
		}

		return result;
	}

	protected static boolean _statementsMatch(
			Statement st1, Statement st2, Map bNodeMapping)
	{
		URI pred1 = st1.getPredicate();
		URI pred2 = st2.getPredicate();

		if (!pred1.equals(pred2)) {
			// predicates don't match
			return false;
		}

		Resource subj1 = st1.getSubject();
		Resource subj2 = st2.getSubject();

		if (!(subj1 instanceof BNode) && !subj1.equals(subj2)) {
			// subjects are not bNodes and don't match
			return false;
		}
		else { // subj1 instanceof BNode
			BNode mappedBNode = (BNode)bNodeMapping.get(subj1);

			if (mappedBNode != null) {
				// bNode 'subj1' was already mapped to some other bNode
				if (!subj2.equals(mappedBNode)) {
					// subj2 doesn't match the previously mapped bNode
					return false;
				}
			}
		}

		Value obj1 = st1.getObject();
		Value obj2 = st2.getObject();

		if (!(obj1 instanceof BNode) && !obj1.equals(obj2)) {
			// objects are not bNodes and don't match
			return false;
		}
		else { // obj1 instanceof BNode
			BNode mappedBNode = (BNode)bNodeMapping.get(obj1);

			if (mappedBNode != null) {
				// bNode 'obj1' was already mapped to some other bNode
				if (!obj2.equals(mappedBNode)) {
					// obj2 doesn't match the previously mapped bNode
					return false;
				}
			}
		}

		return true;
	}

	protected static boolean _modelsEqual(List model1, List model2, Map bNodeMapping) {
		for (int i1 = 0; i1 < model1.size(); i1++) {
			Statement st1 = (Statement)model1.get(i1);

			int i2 = 0;
			for (; i2 < model2.size(); i2++) {
				Statement st2 = (Statement)model2.get(i2);

				if (_statementsMatch(st1, st2, bNodeMapping)) {
					// Found a matching statement
					break;
				}
			}

			if (i2 >= model2.size()) {
				// No statement matching st1 was found in model2
				return false;
			}
		}

		// All statements from model1 have matching statements in model2
		return true;
	}
}