--- /dev/null
+/*
+ * Copyright 2005-2011 the original author or authors.
+ *
+ * Licensed 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 org.wamblee.xmlrouter.impl;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Set;
+
+import org.wamblee.xmlrouter.config.Transformation;
+
+/**
+ * This class manages transformations and computes the shortest transformations
+ * paths based on the provided transformations.
+ *
+ * @author Erik Brakkee
+ *
+ */
+public class TransformationPaths {
+
+ private Collection<Transformation> transformations;
+ private List<String> vertices;
+ private TransformationPath[][] matrix;
+
+ /**
+ * Construct the transformations.
+ */
+ public TransformationPaths(Collection<Transformation> aTransformations) {
+ transformations = aTransformations;
+ vertices = new ArrayList<String>();
+ matrix = new TransformationPath[0][0];
+ computeTransformationSequences();
+ }
+
+ /**
+ * Gets the possible target types based on an input type.
+ *
+ * @param aType
+ * Input type.
+ * @return Possible target types.
+ */
+ public Collection<String> getPossibleTargetTypes(String aType) {
+ int index = vertices.indexOf(aType);
+ Set<String> res = new HashSet<String>();
+ for (int j = 0; j < vertices.size(); j++) {
+ if (matrix[index][j] != null) {
+ String value = matrix[index][j].getToType();
+ if (value == null) {
+ value = aType;
+ }
+ res.add(value);
+ }
+ }
+ res.add(aType);
+ return res;
+ }
+
+ /**
+ * Gets the transformation path from A to B.
+ *
+ * @param aFrom
+ * From
+ * @param aTo
+ * To
+ * @return Transformatkon path or null if not found.
+ */
+ public TransformationPath getPath(String aFrom, String aTo) {
+ int i = vertices.indexOf(aFrom);
+ if (i < 0) {
+ if (aFrom.equals(aTo)) {
+ return new TransformationPath();
+ }
+ return null;
+ }
+
+ int j = vertices.indexOf(aTo);
+ if (j < 0) {
+ return null;
+ }
+ return matrix[i][j];
+ }
+
+ /**
+ * Computest the transformation sequences using Floyd's algorithm.
+ */
+ private void computeTransformationSequences() {
+ vertices = new ArrayList<String>();
+
+ // Obtain possible starting points.
+ Set<String> v = new HashSet<String>();
+ for (Transformation transformation : transformations) {
+ v.add(transformation.getFromType());
+ v.add(transformation.getToType());
+ }
+
+ vertices.addAll(v);
+
+ matrix = new TransformationPath[vertices.size()][vertices.size()];
+
+ // Floyd's algorithm.
+ int nvertices = vertices.size();
+ for (int i = 0; i < nvertices; i++) {
+ matrix[i][i] = new TransformationPath();
+ }
+ for (Transformation transformation : transformations) {
+ int from = vertices.indexOf(transformation.getFromType());
+ int to = vertices.indexOf(transformation.getToType());
+ TransformationPath path = new TransformationPath(transformation);
+ matrix[from][to] = path;
+ }
+
+ for (int k = 0; k < nvertices; k++) {
+ for (int i = 0; i < nvertices; i++) {
+ for (int j = 0; j < nvertices; j++) {
+ // if the path from i to j through k is shorter then the
+ // existing path then
+ // replace it.
+ int lij = getPathLength(i, j);
+ int lik = getPathLength(i, k);
+ int lkj = getPathLength(k, j);
+ if (lik + lkj < lij) {
+ matrix[i][j] = matrix[i][k].appendPath(matrix[k][j]);
+ }
+ }
+ }
+ }
+ }
+
+ private int getPathLength(int i, int j) {
+ // We use MAX_INT/3 as infinity. This ensures that the default integer
+ // comparison in Floyd's algorithm does not lead to overflow.
+ return matrix[i][j] == null ? Integer.MAX_VALUE / 3 : matrix[i][j]
+ .size();
+ }
+
+ @Override
+ public String toString() {
+ StringBuffer buf = new StringBuffer();
+ buf.append("Transformations(");
+ int nvertices = vertices.size();
+ for (int i = 0; i < nvertices; i++) {
+ for (int j = 0; j < nvertices; j++) {
+ TransformationPath path = matrix[i][j];
+ if (path != null) {
+ buf.append(vertices.get(i));
+ buf.append(" -> ");
+ buf.append(vertices.get(j));
+ buf.append(": ");
+ buf.append(path);
+ buf.append("\n");
+ }
+ }
+ }
+ buf.append(")");
+ return buf.toString();
+ }
+}
git://wamblee.org / xmlrouter / blobdiff