Op transformation: breadth-first searching

gselzer · ctrueden · commit 1bd7b1938153 · 2019-09-22T17:22:16.000+02:00
This is better than depth-first because it provides the shortest
possible transformation
diff --git a/src/main/java/org/scijava/ops/OpService.java b/src/main/java/org/scijava/ops/OpService.java
@@ -319,7 +319,7 @@ public Object findOpInstance(final String opName, final OpRef ref) {
 
 			// If we can't find an op matching the original request, we try to find a
 			// transformation
-			transformation = transformer.findTransfromation(this, ref);
+			transformation = transformer.findTransformation(this, ref);
 			if (transformation == null) {
 				log.debug("No matching Op transformation found");
 				throw new IllegalArgumentException(e);
diff --git a/src/main/java/org/scijava/ops/transform/DefaultOpTransformerService.java b/src/main/java/org/scijava/ops/transform/DefaultOpTransformerService.java
@@ -34,7 +34,9 @@
 
 import java.util.ArrayList;
 import java.util.Collection;
+import java.util.LinkedList;
 import java.util.List;
+import java.util.stream.Collectors;
 
 import org.scijava.ops.OpEnvironment;
 import org.scijava.ops.matcher.OpCandidate;
@@ -59,16 +61,18 @@ public final class DefaultOpTransformerService extends AbstractSingletonService<
 	@Parameter
 	private OpTypeMatchingService matcher;
 	
+	private final int maxTransformations = 2;
+	
 	@Override
-	public List<OpTransformation> getTansformationsTo(OpRef toRef) {
+	public List<OpTransformation> getTransformationsTo(OpRef toRef, int currentChainLength) {
 		List<OpTransformation> transforms = new ArrayList<>();
 		
 		for (OpTransformer ot: getInstances()) {
 			final Collection<OpRef> fromRefs = ot.getRefsTransformingTo(toRef);
 			if (fromRefs != null) {
 				for (OpRef fromRef : fromRefs) {
 					if (fromRef != null) {
-						transforms.add(new OpTransformation(fromRef, toRef, ot));
+						transforms.add(new OpTransformation(fromRef, toRef, ot, currentChainLength + 1));
 					}
 				}
 			}
@@ -77,35 +81,27 @@ public List<OpTransformation> getTansformationsTo(OpRef toRef) {
 	}
 	
 	@Override
-	public OpTransformationCandidate findTransfromation(OpEnvironment opEnv, OpRef ref) {
-		List<OpTransformation> ts = getTansformationsTo(ref);
-		for (OpTransformation t : ts) {
-			OpTransformationCandidate match = findTransfromation(opEnv, t, 0);
-			if (match != null) {
-				return match;
-			}
-		}
-		return null;
-	}
-	
-	private OpTransformationCandidate findTransfromation(OpEnvironment opEnv, OpTransformation candidate, int depth) {
-		if (candidate == null || depth > 1) {
-			return null;
-		} else {
-			OpRef fromRef = candidate.getSource();
+	public OpTransformationCandidate findTransformation(OpEnvironment opEnv, OpRef ref) {
+		LinkedList<OpTransformation> tsQueue = new LinkedList<>();
+		tsQueue.addAll(getTransformationsTo(ref, 0));
+		while (!tsQueue.isEmpty()) {
+			OpTransformation t = tsQueue.pop();
+			OpRef fromRef = t.getSource();
 			try {
 				OpCandidate match = matcher.findSingleMatch(opEnv, fromRef);
-				return new OpTransformationCandidate(match, candidate);
+				return new OpTransformationCandidate(match, t);
 			} catch (OpMatchingException e) {
-				List<OpTransformation> ts = getTansformationsTo(fromRef);
-				for (OpTransformation t : ts) {
-					OpTransformationCandidate cand = findTransfromation(opEnv, t.chain(candidate), depth + 1);
-					if (cand != null) {
-						return cand;
-					}
-				}
+				// if we have done fewer than the maximum allowed number of transformations from
+				// ref, find more transformations from t
+				if (t.getChainLength() < maxTransformations)
+					// we need to make sure chain all of these transformations to t, thus we map the
+					// results of getTransformationsTo
+					tsQueue.addAll(getTransformationsTo(fromRef, t.getChainLength())//
+							.stream().map(next -> next.chain(t))//
+							.collect(Collectors.toList()));
 			}
 		}
 		return null;
 	}
+	
 }
diff --git a/src/main/java/org/scijava/ops/transform/OpTransformation.java b/src/main/java/org/scijava/ops/transform/OpTransformation.java
@@ -17,11 +17,25 @@ public class OpTransformation {
 	private OpTransformer transformation;
 	
 	private OpTransformation child;
+	private int chainLength;
 
-	public OpTransformation(OpRef from, OpRef to, OpTransformer transformer) {
+	/**
+	 * Constructor
+	 * 
+	 * @param from
+	 *            the OpRef we are transforming from
+	 * @param to
+	 *            the OpRef we are transforming to
+	 * @param transformer
+	 *            the OpTransformer that will take an Op with the fromRef signature
+	 *            and transform it to the toRef signature
+	 * @param chainLength the length of the chain from what was originally requested to toRef
+	 */
+	public OpTransformation(OpRef from, OpRef to, OpTransformer transformer, int chainLength) {
 		this.srcRef = from;
 		this.targetRef = to;
 		this.transformation = transformer;
+		this.chainLength = chainLength;
 	}
 
 	/**
@@ -59,6 +73,15 @@ public OpTransformer getTransformer() {
 	public OpTransformation getChild() {
 		return this.child;
 	}
+	
+	/**
+	 * Get the length of the transformation chain
+	 * 
+	 * @return
+	 */
+	public int getChainLength() {
+		return this.chainLength;
+	}
 
 	/**
 	 * Executes this transformation on the specified object.
diff --git a/src/main/java/org/scijava/ops/transform/OpTransformerService.java b/src/main/java/org/scijava/ops/transform/OpTransformerService.java
@@ -21,14 +21,19 @@ default Class<OpTransformer> getPluginType() {
 	
 	/**
 	 * Retrieve a list of {@link OpTransformation}s that describe a transformation
-	 * that is able to transform an Op matching an {@link OpRef} into another Op matching
-	 * the specified {@link OpRef}. This can be used to find Ops that are transformable 
-	 * into the specified {@link OpRef}.
+	 * that is able to transform an Op matching an {@link OpRef} into another Op
+	 * matching the specified {@link OpRef}. This can be used to find Ops that are
+	 * transformable into the specified {@link OpRef}.
 	 * 
-	 * @param opRef the ref which should be the target of the transformations to look for
+	 * @param opRef
+	 *            the ref which should be the target of the transformations to look
+	 *            for
+	 * @param currentChainLength
+	 *            the number of transformations between the requested OpRef and the
+	 *            passed argument
 	 * @return
 	 */
-	List<OpTransformation> getTansformationsTo (OpRef opRef);
+	List<OpTransformation> getTransformationsTo (OpRef opRef, int currentChainLength);
 	
 	/**
 	 * Attempts to find an {@link OpTransformationCandidate}, transforming an existing Op into another
@@ -44,5 +49,5 @@ default Class<OpTransformer> getPluginType() {
 	 * @param ref the ref which should be the target of the transformation to look for
 	 * @return
 	 */
-	OpTransformationCandidate findTransfromation(OpEnvironment opEnv, OpRef ref);
+	OpTransformationCandidate findTransformation(OpEnvironment opEnv, OpRef ref);
 }
