2 * Copyright 2005-2011 the original author or authors.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
16 package org.wamblee.xmlrouter.impl;
18 import java.util.ArrayList;
19 import java.util.Collection;
20 import java.util.HashSet;
21 import java.util.List;
24 import org.wamblee.xmlrouter.config.Transformation;
27 * This class manages transformations and computes the shortest transformations
28 * paths based on the provided transformations.
30 * @author Erik Brakkee
33 public class TransformationPaths {
35 private Collection<Transformation> transformations;
36 private List<String> vertices;
37 private TransformationPath[][] matrix;
40 * Construct the transformations.
42 public TransformationPaths(Collection<Transformation> aTransformations) {
43 transformations = aTransformations;
44 vertices = new ArrayList<String>();
45 matrix = new TransformationPath[0][0];
46 computeTransformationSequences();
50 * Gets the possible target types based on an input type.
54 * @return Possible target types.
56 public Collection<String> getPossibleTargetTypes(String aType) {
57 int index = vertices.indexOf(aType);
58 Set<String> res = new HashSet<String>();
59 for (int j = 0; j < vertices.size(); j++) {
60 if (matrix[index][j] != null) {
61 String value = matrix[index][j].getToType();
73 * Gets the transformation path from A to B.
79 * @return Transformatkon path or null if not found.
81 public TransformationPath getPath(String aFrom, String aTo) {
82 int i = vertices.indexOf(aFrom);
84 if (aFrom.equals(aTo)) {
85 return new TransformationPath();
90 int j = vertices.indexOf(aTo);
98 * Computest the transformation sequences using Floyd's algorithm.
100 private void computeTransformationSequences() {
101 vertices = new ArrayList<String>();
103 // Obtain possible starting points.
104 Set<String> v = new HashSet<String>();
105 for (Transformation transformation : transformations) {
106 v.add(transformation.getFromType());
107 v.add(transformation.getToType());
112 matrix = new TransformationPath[vertices.size()][vertices.size()];
114 // Floyd's algorithm.
115 int nvertices = vertices.size();
116 for (int i = 0; i < nvertices; i++) {
117 matrix[i][i] = new TransformationPath();
119 for (Transformation transformation : transformations) {
120 int from = vertices.indexOf(transformation.getFromType());
121 int to = vertices.indexOf(transformation.getToType());
122 TransformationPath path = new TransformationPath(transformation);
123 matrix[from][to] = path;
126 for (int k = 0; k < nvertices; k++) {
127 for (int i = 0; i < nvertices; i++) {
128 for (int j = 0; j < nvertices; j++) {
129 // if the path from i to j through k is shorter then the
130 // existing path then
132 int lij = getPathLength(i, j);
133 int lik = getPathLength(i, k);
134 int lkj = getPathLength(k, j);
135 if (lik + lkj < lij) {
136 matrix[i][j] = matrix[i][k].appendPath(matrix[k][j]);
143 private int getPathLength(int i, int j) {
144 // We use MAX_INT/3 as infinity. This ensures that the default integer
145 // comparison in Floyd's algorithm does not lead to overflow.
146 return matrix[i][j] == null ? Integer.MAX_VALUE / 3 : matrix[i][j]
151 public String toString() {
152 StringBuffer buf = new StringBuffer();
153 buf.append("Transformations(");
154 int nvertices = vertices.size();
155 for (int i = 0; i < nvertices; i++) {
156 for (int j = 0; j < nvertices; j++) {
157 TransformationPath path = matrix[i][j];
159 buf.append(vertices.get(i));
161 buf.append(vertices.get(j));
169 return buf.toString();