graphpattern.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.query;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;

import org.openrdf.sesame.sail.RdfSource;

/**
 * A pattern consisting of a set of path expressions and boolean constraints
 * on the values in the path expressions, and zero or more optional child graph
 * patterns.
 *
 * @author Arjohn Kampman
 */
public class GraphPattern implements PathExpression {

/*----------+
| Variables |
+----------*/

	/**
	 * A List of PathExpression objects indicating the paths in the RDF graph
	 * that are relevant for the query.
	 **/
	private List _pathExpressions;

	/**
	 * A List of BooleanExpr objects that represent constraints on the variable
	 * values from the path expressions.
	 **/
	private List _constraints;

	/**
	 * A List of GraphPattern objects, to be interpreted as optional child graph
	 * patterns.
	 **/
	private List _optionals;

	/**
	 * A mixed list of PathExpression and BooleanExpr objects that is used for
	 * query evaluation. Verification of parts of the boolean constraints can be
	 * done before all path expressions have been instantiated. The order of
	 * objects in this list indicate when this verification takes place.
	 **/
	private List _expressions;

	/**
	 * Flag indicating whether a call to 'selectNext()' is the first call to
	 * this method.
	 **/
	private boolean _firstCall;

	/**
	 * Flag indicating whether this graph pattern has produced all possible
	 * results.
	 **/
	private boolean _exhausted;

/*------------------------+
| Constructors            |
+------------------------*/

	/**
	 * Creates a new GraphPattern.
	 **/
	public GraphPattern() {
		_pathExpressions = new ArrayList();
		_constraints = new ArrayList();
		_optionals = new ArrayList();
		_expressions = new ArrayList();
	}

/*------------------------+
| Methods                 |
+------------------------*/

	/**
	 * Adds a collection of PathExpression objects to this object.
	 **/
	public void addAll(Collection triplePatterns) {
		Iterator iter = triplePatterns.iterator();
		while (iter.hasNext()) {
			Object o = iter.next();

			if (o instanceof PathExpression) {
				add( (PathExpression)o );
			}
			else if (o instanceof BooleanExpr) {
				addConstraint( (BooleanExpr)o );
			}
			else {
				throw new IllegalArgumentException(
						"object in collection is not of type PathExpression or BooleanExpr but: " + o.getClass());
			}
		}
	}

	/**
	 * Adds a path expression to the this object.
	 **/
	public void add(PathExpression pathExpr) {
		_pathExpressions.add(pathExpr);
	}

	/**
	 * Gets a list of path expressions contained in this object.
	 *
	 * @return An unmodifiable List of PathExpression objects.
	 **/
	public List getPathExpressions() {
		return Collections.unmodifiableList(_pathExpressions);
	}

	/**
	 * Sets the list of path expressions for this object.
	 **/
	public void setPathExpressions(List pathExpressions) {
		_pathExpressions.clear();
		addAll(pathExpressions);
	}

	/**
	 * Gets a list of path expressions contained in this object
	 * and all of its optional child graph patterns recursively.
	 *
	 * @return An unmodifiable List of PathExpression objects.
	 **/
	public List getPathExpressionsRecursively() {
		List result = new ArrayList(_pathExpressions);

		Iterator iter = _optionals.iterator();
		while (iter.hasNext()) {
			GraphPattern optionalGP = (GraphPattern)iter.next();
			result.addAll(optionalGP.getPathExpressionsRecursively());
		}

		return Collections.unmodifiableList(result);
	}

	/**
	 * Gets the constraints on this graph pattern as a single boolean 'root'
	 * constraint. Separate constraints are joined using AND operators to create
	 * the root constraint.
	 *
	 * @return A BooleanExpr object representing all boolean constraints, or
	 * <tt>null</tt> if the graph pattern doesn't have any constraints.
	 * @see #getConjunctiveConstraints
	 **/
	public BooleanExpr getRootConstraint() {
		BooleanExpr result = null;

		ListIterator iter = _constraints.listIterator(_constraints.size());

		if (iter.hasPrevious()) {
			result = (BooleanExpr)iter.previous();

			while (iter.hasPrevious()) {
				BooleanExpr leftArg = (BooleanExpr)iter.previous();
				result = new And(leftArg, result);
			}
		}

		return result;
	}

	/**
	 * Gets a list of conjunctive constraints. Any constraints that have an
	 * <tt>AND</tt> operator as their root have been split (recursively) before
	 * being added to the list. If the graph pattern doesn't have any
	 * constraints, an empty list will be returned.
	 *
	 * @return An unmodifiableList containing BooleanExpr objects that, when
	 * applied conjunctively, result in the same constraint as the root
	 * constraint.
	 * @see #getRootConstraint
	 **/
	public List getConjunctiveConstraints() {
		return Collections.unmodifiableList(_constraints);
	}

	/**
	 * Sets the constraints for this graph pattern to the supplied constraint,
	 * removing any existing constraints.
	 *
	 * @param constraint The new constraint(s) for the graph pattern.
	 **/
	public void setConstraints(BooleanExpr constraint) {
		_constraints.clear();
		addConstraint(constraint);
	}

	/**
	 * Sets the constraints for this graph pattern to the supplied constraints,
	 * removing any existing constraints.
	 *
	 * @param constraints The new constraints for the graph pattern.
	 **/
	public void setConstraints(List constraints) {
		_constraints.clear();

		Iterator iter = constraints.iterator();
		while (iter.hasNext()) {
			BooleanExpr constraint = (BooleanExpr)iter.next();
			addConstraint(constraint);
		}
	}

	/**
	 * Adds the supplied constraint to the set of constraints for this graph
	 * pattern. Constraints that have an <tt>AND</tt> operator as their root
	 * are split into separate conjunctively constraints (recursively) before
	 * being added to the list.
	 *
	 * @param constraint A new constraint.
	 **/
	public void addConstraint(BooleanExpr constraint) {
		if (constraint instanceof And) {
			And and = (And)constraint;

			addConstraint(and.getLeftArg());
			addConstraint(and.getRightArg());
		}
		else {
			_constraints.add(constraint);
		}
	}

	/**
	 * Adds an optional child graph pattern to this graph pattern.
	 **/
	public void addOptional(GraphPattern optionalGP) {
		_optionals.add(optionalGP);
	}

	/**
	 * Gets a list of optional child graph patterns.
	 * @return An unmodifiable List of GraphPattern objects.
	 **/
	public List getOptionals() {
		return Collections.unmodifiableList(_optionals);
	}

	/**
	 * Sets the optional child graph patterns for this object to the supplied set.
	 **/
	public void setOptionals(Collection optionals) {
		_optionals.clear();
		_optionals.addAll(optionals);
	}

	public List getExpressions() {
		return Collections.unmodifiableList(_expressions);
	}

	public void setExpressions(List expressions) {
		_expressions.clear();
		_expressions.addAll(expressions);
	}

	public boolean findFirst(RdfSource rdfSource) 
		throws SailQueryException
	{
		initialize(rdfSource);
		return _findNext(rdfSource, true);
	}

	public boolean findNext(RdfSource rdfSource) 
		throws SailQueryException
	{
		return _findNext(rdfSource, false);
	}

	public void initialize(RdfSource rdfSource) {
		if (_expressions.size() == 0 && _pathExpressions.size() > 0) {
			_expressions.addAll(_pathExpressions);
			_expressions.addAll(_optionals);
			_expressions.addAll(_constraints);
		}

		_firstCall = true;
		_exhausted = false;
	}

	public boolean selectNext(RdfSource rdfSource) 
		throws SailQueryException
	{
		if (_exhausted) {
			return false;
		}

		boolean result;

		if (_firstCall) {
			_firstCall = false;

			result = _findNext(rdfSource, true);

			if (result == false) {
				_exhausted = true;
				result = true;
			}
		}
		else {
			result = _findNext(rdfSource, false);

			if (result == false) {
				_exhausted = true;
			}
		}

		return result;
	}

	/**
	 * Clears the internal state of this object.
	 **/
	public void clear() {
		for (int i = _expressions.size() - 1; i >= 0; i--) {
			Object expression = _expressions.get(i);
			if (expression instanceof PathExpression) {
				((PathExpression)expression).clear();
			}
		}
	}

	/**
	 * Gets all variables that are used in the path expressions of this
	 * GraphPattern. This does not include the variables that are used in any
	 * optional child graph patterns.
	 */
	public void getLocalVariables(Collection variables) {
		Iterator iter = _pathExpressions.iterator();
		while (iter.hasNext()) {
			PathExpression pe = (PathExpression)iter.next();
			pe.getVariables(variables);
		}
	}

	// Implements PathExpression.getVariables(Collection)
	public void getVariables(Collection variables) {
		getLocalVariables(variables);

		Iterator iter = _optionals.iterator();
		while (iter.hasNext()) {
			GraphPattern pel = (GraphPattern)iter.next();
			pel.getVariables(variables);
		}
	}

	/**
	 * Finds the next result. If 'firstCall' is true, then this method will
	 * start with the initialization of the first path expression.
	 * Otherwise, this method will assume that all path expressions have
	 * been initialization before and will continue with the last path
	 * expression.
	 *
	 * @return true If a next result has been found, false otherwise.
	 **/
	private boolean _findNext(RdfSource rdfSource, boolean firstCall) 
		throws SailQueryException
	{
		int lastIndex = _expressions.size() - 1;
		int index;
		Object expr = null;
		PathExpression pathExpr = null;
		BooleanExpr boolExpr = null;

		if (firstCall) {
			// Start at first expression
			index = 0;
			if (_expressions.size() == 0) {
				// no path expressions
				return true;
			}
			expr = _expressions.get(index);
			if (expr instanceof PathExpression) {
				((PathExpression)expr).initialize(rdfSource);
			}
		}
		else {
			// Continue with last expression
			index = lastIndex;
			
			if (_expressions.size() == 0) {
				// no path expressions
				return false;
			}
			expr = _expressions.get(index);

			// Boolean expressions don't have a state and shouldn't be
			// re-evaluated. Go back in the recursion until we come
			// accross a PathExpression
			while (expr instanceof BooleanExpr && index > 0) {
				index--;
				expr = _expressions.get(index);
			}

			if (expr instanceof BooleanExpr) {
				// No PathExpression has been found
				return false;
			}
		}

		while (true) {
			// Check expression at index 'index'
			boolean success = false;

			if (expr instanceof PathExpression) {
				pathExpr = (PathExpression)expr;
				success = pathExpr.selectNext(rdfSource);
			}
			else if (expr instanceof BooleanExpr) {
				// BooleanExpr
				boolExpr = (BooleanExpr)expr;
				try {
					success = boolExpr.isTrue(rdfSource);
				}
				catch (BooleanExprEvaluationException e) {
					// Boolean expression could not be evaluated, no success
				}
			}
			else {
				throw new RuntimeException("Unknown expression type: " +  expr.getClass().toString());
			}

			if (success) {
				// Expression evaluated successfully

				if (index == lastIndex) {
					// All expressions evaluated successfully
					return true;
				}
				else {
					// Evaluate next expression
					index++;
					expr = _expressions.get(index);
					if (expr instanceof PathExpression) {
						((PathExpression)expr).initialize(rdfSource);
					}
				}
			}
			else {
				// Expression evaluation failed
				if (expr instanceof PathExpression) {
					pathExpr.clear();
				}

				if (index == 0) {
					// First PathExpression exhausted, no more results
					return false;
				}
				else {
					index--;
					expr = _expressions.get(index);

					// Boolean expressions don't have a state and shouldn't be
					// re-evaluated. Go back in the recursion until we come
					// accross a PathExpression
					while (expr instanceof BooleanExpr && index > 0) {
						index--;
						expr = _expressions.get(index);
					}

					if (expr instanceof BooleanExpr) {
						// No PathExpression has been found
						return false;
					}
				}
			}
		}
	}

	public String toString() {
		List expressions = _expressions;

		if (expressions.size() == 0) {
			expressions = new ArrayList();

			expressions.addAll(_pathExpressions);
			expressions.addAll(_optionals);
			expressions.addAll(_constraints);
		}

		StringBuffer result = new StringBuffer(256);
		result.append("[\n");

		Iterator iter = expressions.iterator();
		while (iter.hasNext()) {
			Object expr = iter.next();
			result.append('\t');
			result.append(expr.toString());

			if (iter.hasNext()) {
				result.append(",\n");
			}
		}
		result.append("\n]");

		return result.toString();
	}
}