You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@jena.apache.org by an...@apache.org on 2012/04/24 21:52:12 UTC
svn commit: r1329970 - in
/incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/eval:
PathEngine.java PathEngineSPARQL.java PathEval.java PathEvaluator.java
Author: andy
Date: Tue Apr 24 19:52:11 2012
New Revision: 1329970
URL: http://svn.apache.org/viewvc?rev=1329970&view=rev
Log:
Some tidying up in preparation for a new evaluator with the latest SPARQL semantics.
Added:
incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/eval/PathEngineSPARQL.java
Modified:
incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/eval/PathEngine.java
incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/eval/PathEval.java
incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/eval/PathEvaluator.java
Modified: incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/eval/PathEngine.java
URL: http://svn.apache.org/viewvc/incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/eval/PathEngine.java?rev=1329970&r1=1329969&r2=1329970&view=diff
==============================================================================
--- incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/eval/PathEngine.java (original)
+++ incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/eval/PathEngine.java Tue Apr 24 19:52:11 2012
@@ -62,12 +62,12 @@ abstract public class PathEngine {
protected final Iter<Node> eval(Graph graph, Path path, Node node)
{
- return PathEvaluator.eval(graph, node, path, this) ;
+ return PathEval.eval$(graph, node, path, this) ;
}
protected final void eval(Graph graph, Path path, Node node, Collection<Node> output)
{
- PathEvaluator.eval(graph, node, path, this, output) ;
+ PathEval.eval$(graph, node, path, this, output) ;
}
protected abstract void flipDirection() ;
Added: incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/eval/PathEngineSPARQL.java
URL: http://svn.apache.org/viewvc/incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/eval/PathEngineSPARQL.java?rev=1329970&view=auto
==============================================================================
--- incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/eval/PathEngineSPARQL.java (added)
+++ incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/eval/PathEngineSPARQL.java Tue Apr 24 19:52:11 2012
@@ -0,0 +1,237 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.hp.hpl.jena.sparql.path.eval;
+
+import java.util.ArrayList ;
+import java.util.Collection ;
+import java.util.Iterator ;
+import java.util.LinkedList ;
+
+import org.openjena.atlas.iterator.Iter ;
+
+import com.hp.hpl.jena.graph.Graph ;
+import com.hp.hpl.jena.graph.Node ;
+import com.hp.hpl.jena.sparql.path.P_FixedLength ;
+import com.hp.hpl.jena.sparql.path.P_Mod ;
+import com.hp.hpl.jena.sparql.path.P_NegPropSet ;
+import com.hp.hpl.jena.sparql.path.Path ;
+
+/** Simple implementation */
+
+public class PathEngineSPARQL extends PathEngine
+{
+ private final Graph graph ;
+ private boolean forwardMode ;
+
+ private PathEngineSPARQL(Graph graph, boolean forward)
+ {
+ this.graph = graph ;
+ this.forwardMode = forward ;
+ }
+
+ @Override
+ protected void doSeq(Path pathStepLeft, Path pathStepRight, Node node, Collection<Node> output)
+ {
+ Path part1 = forwardMode ? pathStepLeft : pathStepRight ;
+ Path part2 = forwardMode ? pathStepRight : pathStepLeft ;
+
+ // Feed one side into the other
+ Iter<Node> iter = eval(graph, part1, node) ;
+ for ( Node n : iter )
+ eval(graph, part2, n, output) ;
+ }
+
+ @Override
+ protected void doAlt(Path pathStepLeft, Path pathStepRight, Node node, Collection<Node> output)
+ {
+ // Try both sizes, accumulate into output.
+ Iterator<Node> iter = eval(graph, pathStepLeft, node) ;
+ fill(iter, output) ;
+ iter = eval(graph, pathStepRight, node) ;
+ fill(iter, output) ;
+ }
+
+ @Override
+ protected void doNegatedPropertySet(P_NegPropSet pathNotOneOf, Node node, Collection<Node> output)
+ {
+ if ( pathNotOneOf.getFwdNodes().size() > 0 )
+ {
+ Iterator<Node> nodes1 = stepExcludeForwards(graph, node, pathNotOneOf.getFwdNodes()) ;
+ fill(nodes1, output) ;
+ }
+ if ( pathNotOneOf.getBwdNodes().size() > 0 )
+ {
+ Iterator<Node> nodes2 = stepExcludeBackwards(graph, node, pathNotOneOf.getBwdNodes()) ;
+ fill(nodes2, output) ;
+ }
+ }
+
+ @Override
+ protected void doZeroOrOne(Path pathStep, Node node, Collection<Node> output)
+ {
+ // Unique.
+ eval(graph, pathStep, node, output) ;
+ if ( ! output.contains(node) )
+ output.add(node) ;
+ }
+
+ @Override
+ protected void doZeroOrMore(Path pathStep, Node node, Collection<Node> output)
+ {
+ // Reuse "output"
+ Collection<Node> visited = new LinkedList<Node>() ; //new HashSet<Node>() ;
+ ALP1(graph, forwardMode, 0, -1, node, pathStep, visited) ;
+ output.addAll(visited) ;
+ }
+
+ @Override
+ protected void doOneOrMore(Path pathStep, Node node, Collection<Node> output)
+ {
+ // Reuse "output"
+ Collection<Node> visited = new LinkedList<Node>() ; // new HashSet<Node>() ;
+ // Do one step without including.
+ Iter<Node> iter1 = eval(graph, pathStep, node) ;
+ for ( ; iter1.hasNext() ; )
+ {
+ Node n1 = iter1.next();
+ ALP1(graph, forwardMode, 0, -1, n1, pathStep, visited) ;
+ }
+ output.addAll(visited) ;
+ }
+
+ private void ALP1(Graph graph, boolean forwardMode, int stepCount, int maxStepCount, Node node, Path path, Collection<Node> visited)
+ {
+ if ( false ) System.out.printf("ALP1 node=%s\n visited=%s\n output=%s\n", node, visited) ;
+ if ( maxStepCount >=0 && stepCount > maxStepCount ) return ;
+ if ( visited.contains(node) ) return ;
+
+ if ( ! visited.add(node) )
+ return ;
+
+ Iter<Node> iter1 = eval(graph, path, node) ;
+ // For each step, add to results and recurse.
+ for ( ; iter1.hasNext() ; )
+ {
+ Node n1 = iter1.next();
+ ALP1(graph, forwardMode, stepCount+1, maxStepCount, n1, path, visited) ;
+ }
+ }
+
+ @Override
+ protected void doZero(Path path, Node node, Collection<Node> output)
+ {
+ // Not SPARQL
+ output.add(node) ;
+ }
+
+ @Override
+ protected void doMultiLengthPath(Path pathStep, Node node, long min1, long max1, Collection<Node> output)
+ {
+ // Not SPARQL
+ // Why not always reduce {N,M} to {N} and {0,M-N}
+ // Why not iterate, not recurse, for {N,}
+ // -- optimizer will have expanded this so only in unoptimized mode.
+
+ if ( min1 == P_Mod.UNSET )
+ // {,N}
+ min1 = 0 ;
+
+ // ----------------
+ // This code is for p{n,m} and :p{,n} inc :p{0,n}
+ // and for :p{N,}
+
+ //if ( max1 == P_Mod.UNSET ) max1 = 0 ;
+
+ if ( min1 == 0 )
+ output.add(node) ;
+
+ if ( max1 == 0 )
+ return ;
+
+ // The next step
+ long min2 = dec(min1) ;
+ long max2 = dec(max1) ;
+
+ // TODO Rewrite
+ Path p1 = pathStep ;
+ Path p2 = new P_Mod(pathStep, min2, max2) ;
+
+ if ( !forwardMode )
+ {
+ // Reverse order. Do the second bit first.
+ Path tmp = p1 ;
+ p1 = p2 ; p2 = tmp ;
+ // This forces execution to be in the order that it's written, when working backwards.
+ // {N,*} is {*} then {N} backwards != do {N} then do {*} as cardinality of the
+ // two operations is different.
+ }
+ // ****
+
+ // One step.
+ Iterator<Node> iter = eval(graph, p1, node) ;
+
+ // Moved on one step
+ for ( ; iter.hasNext() ; )
+ {
+ Node n2 = iter.next() ;
+ Iterator<Node> iter2 = eval(graph, p2, n2) ;
+ fill(iter2, output) ;
+ }
+
+ // If no matches, will not call eval and we drop out.
+ }
+
+ @Override
+ protected void doFixedLengthPath(Path pathStep, Node node, long fixedLength, Collection<Node> output)
+ {
+ // Not SPARQL
+ if ( fixedLength == 0 )
+ {
+ output.add(node) ;
+ return ;
+ }
+ // P_Mod(path, count, count)
+ // One step.
+ Iterator<Node> iter = eval(graph, pathStep, node) ;
+ // Build a path for all remaining steps.
+ long count2 = dec(fixedLength) ;
+ P_FixedLength nextPath = new P_FixedLength(pathStep, count2) ;
+ // For each element in the first step, do remaining step
+ // Accumulate across everything from first step.
+ for ( ; iter.hasNext() ; )
+ {
+ Node n2 = iter.next() ;
+ Iterator<Node> iter2 = eval(graph, nextPath, n2) ;
+ fill(iter2, output) ;
+ }
+ }
+
+ @Override
+ protected void flipDirection()
+ { forwardMode = ! forwardMode ; }
+
+ @Override
+ protected boolean direction()
+ { return forwardMode ; }
+
+ @Override
+ protected Collection<Node> collector() { return new ArrayList<Node>() ; }
+
+}
+
Modified: incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/eval/PathEval.java
URL: http://svn.apache.org/viewvc/incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/eval/PathEval.java?rev=1329970&r1=1329969&r2=1329970&view=diff
==============================================================================
--- incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/eval/PathEval.java (original)
+++ incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/eval/PathEval.java Tue Apr 24 19:52:11 2012
@@ -18,8 +18,12 @@
package com.hp.hpl.jena.sparql.path.eval;
+import java.util.ArrayList ;
+import java.util.Collection ;
import java.util.Iterator ;
+import org.openjena.atlas.iterator.Iter ;
+
import com.hp.hpl.jena.graph.Graph ;
import com.hp.hpl.jena.graph.Node ;
import com.hp.hpl.jena.sparql.path.Path ;
@@ -31,39 +35,56 @@ public class PathEval
/** Evaluate a path : SPARQL semantics */
static public Iterator<Node> eval(Graph graph, Node node, Path path)
{
- //return PathEvaluator.eval(graph, node, path, new PathEngineSPARQL(graph, true)) ;
- return PathEvaluator.eval(graph, node, path, new PathEngineN(graph, true)) ;
+ //return eval$(graph, node, path, new PathEngineSPARQL(graph, true)) ;
+ return eval$(graph, node, path, new PathEngineN(graph, true)) ;
}
/** Evaluate a path */
static public Iterator<Node> evalReverse(Graph graph, Node node, Path path)
{
- //return PathEvaluator.eval(graph, node, path, new PathEngineSPARQL(graph, false)) ;
- return PathEvaluator.eval(graph, node, path, new PathEngineN(graph, false)) ;
+ //return eval$(graph, node, path, new PathEngineSPARQL(graph, false)) ;
+ return eval$(graph, node, path, new PathEngineN(graph, false)) ;
}
/** Evaluate a path : counting semantics */
static public Iterator<Node> evalN(Graph graph, Node node, Path path)
{
- return PathEvaluator.eval(graph, node, path, new PathEngineN(graph, true)) ;
+ return eval$(graph, node, path, new PathEngineN(graph, true)) ;
}
/** Evaluate a path : counting semantics */
static public Iterator<Node> evalReverseN(Graph graph, Node node, Path path)
{
- return PathEvaluator.eval(graph, node, path, new PathEngineN(graph, false)) ;
+ return eval$(graph, node, path, new PathEngineN(graph, false)) ;
}
/** Evaluate a path : unique results */
static public Iterator<Node> eval1(Graph graph, Node node, Path path)
{
- return PathEvaluator.eval(graph, node, path, new PathEngine1(graph, true)) ;
+ return eval$(graph, node, path, new PathEngine1(graph, true)) ;
}
/** Evaluate a path : unique results */
static public Iterator<Node> evalReverse1(Graph graph, Node node, Path path)
{
- return PathEvaluator.eval(graph, node, path, new PathEngine1(graph, false)) ;
+ return eval$(graph, node, path, new PathEngine1(graph, false)) ;
+ }
+
+ /** Evaluate a path */
+ static void eval$(Graph graph, Node node, Path path, PathEngine engine, Collection<Node> acc)
+ {
+ PathEvaluator evaluator = new PathEvaluator(graph, node, acc, engine) ;
+ path.visit(evaluator) ;
}
+
+ /** Evaluate a path */
+ static Iter<Node> eval$(Graph graph, Node node, Path path, PathEngine engine)
+ {
+ Collection<Node> acc = new ArrayList<Node>() ;
+ PathEvaluator evaluator = new PathEvaluator(graph, node, acc, engine) ;
+ path.visit(evaluator) ;
+ return Iter.iter(acc) ;
+ }
+
}
Modified: incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/eval/PathEvaluator.java
URL: http://svn.apache.org/viewvc/incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/eval/PathEvaluator.java?rev=1329970&r1=1329969&r2=1329970&view=diff
==============================================================================
--- incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/eval/PathEvaluator.java (original)
+++ incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/eval/PathEvaluator.java Tue Apr 24 19:52:11 2012
@@ -18,7 +18,6 @@
package com.hp.hpl.jena.sparql.path.eval;
-import java.util.ArrayList ;
import java.util.Collection ;
import java.util.Iterator ;
@@ -39,26 +38,6 @@ final class PathEvaluator implements Pat
protected final Collection<Node> output ;
private PathEngine engine ;
- //protected abstract void eval(Graph graph, Node node, Path p, boolean forward) ;
- //protected abstract Iterator<Node> doOne(Node property) ;
-
- /** Evaluate a path */
- static void eval(Graph graph, Node node, Path path, PathEngine engine, Collection<Node> acc)
- {
- PathEvaluator evaluator = new PathEvaluator(graph, node, acc, engine) ;
- path.visit(evaluator) ;
- }
-
- /** Evaluate a path */
- static Iter<Node> eval(Graph graph, Node node, Path path, PathEngine engine)
- {
- Collection<Node> acc = new ArrayList<Node>() ;
- PathEvaluator evaluator = new PathEvaluator(graph, node, acc, engine) ;
- path.visit(evaluator) ;
- return Iter.iter(acc) ;
- }
-
- // Pass in graph, node only to PathEngine?
protected PathEvaluator(Graph g, Node n, Collection<Node> output, PathEngine engine)
{
this.graph = g ;