wamblee.org Git - xmlrouter/blob - impl/src/main/java/org/wamblee/xmlrouter/impl/TransformationPaths.java

   1 /*
   2  * Copyright 2005-2011 the original author or authors.
   3  *
   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
   7  *
   8  *      http://www.apache.org/licenses/LICENSE-2.0
   9  *
  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.
  15  */
  16 package org.wamblee.xmlrouter.impl;
  17
  18 import java.util.ArrayList;
  19 import java.util.Collection;
  20 import java.util.HashSet;
  21 import java.util.List;
  22 import java.util.Set;
  23
  24 import org.wamblee.xmlrouter.config.Transformation;
  25
  26 /**
  27  * This class manages transformations and computes the shortest transformations
  28  * paths based on the provided transformations.
  29  *
  30  * @author Erik Brakkee
  31  *
  32  */
  33 public class TransformationPaths {
  34
  35     private Collection<Transformation> transformations;
  36     private List<String> vertices;
  37     private TransformationPath[][] matrix;
  38
  39     /**
  40      * Construct the transformations.
  41      */
  42     public TransformationPaths(Collection<Transformation> aTransformations) {
  43         transformations = aTransformations;
  44         vertices = new ArrayList<String>();
  45         matrix = new TransformationPath[0][0];
  46         computeTransformationSequences();
  47     }
  48
  49     /**
  50      * Gets the possible target types based on an input type.
  51      *
  52      * @param aType
  53      *            Input type.
  54      * @return Possible target types.
  55      */
  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();
  62                 if (value == null) {
  63                     value = aType;
  64                 }
  65                 res.add(value);
  66             }
  67         }
  68         res.add(aType);
  69         return res;
  70     }
  71
  72     /**
  73      * Gets the transformation path from A to B.
  74      *
  75      * @param aFrom
  76      *            From
  77      * @param aTo
  78      *            To
  79      * @return Transformatkon path or null if not found.
  80      */
  81     public TransformationPath getPath(String aFrom, String aTo) {
  82         int i = vertices.indexOf(aFrom);
  83         if (i < 0) {
  84             if (aFrom.equals(aTo)) {
  85                 return new TransformationPath();
  86             }
  87             return null;
  88         }
  89
  90         int j = vertices.indexOf(aTo);
  91         if (j < 0) {
  92             return null;
  93         }
  94         return matrix[i][j];
  95     }
  96
  97     /**
  98      * Computest the transformation sequences using Floyd's algorithm.
  99      */
 100     private void computeTransformationSequences() {
 101         vertices = new ArrayList<String>();
 102
 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());
 108         }
 109
 110         vertices.addAll(v);
 111
 112         matrix = new TransformationPath[vertices.size()][vertices.size()];
 113
 114         // Floyd's algorithm.
 115         int nvertices = vertices.size();
 116         for (int i = 0; i < nvertices; i++) {
 117             matrix[i][i] = new TransformationPath();
 118         }
 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;
 124         }
 125
 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
 131                     // replace it.
 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]);
 137                     }
 138                 }
 139             }
 140         }
 141     }
 142
 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]
 147             .size();
 148     }
 149
 150     @Override
 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];
 158                 if (path != null) {
 159                     buf.append(vertices.get(i));
 160                     buf.append(" -> ");
 161                     buf.append(vertices.get(j));
 162                     buf.append(": ");
 163                     buf.append(path);
 164                     buf.append("\n");
 165                 }
 166             }
 167         }
 168         buf.append(")");
 169         return buf.toString();
 170     }
 171 }