Logo Search packages:      
Sourcecode: pauker version File versions  Download package

PathNodeDiff.java

/*
 * PathCopyDiff.java
 *
 * Created on 27. Oktober 2005, 08:04
 *
 */
package tools;

import java.util.LinkedList;
import java.util.List;

/**
 * Implements the diff algorithm using a new approach:
 * We do not need D^2 space for determining the path because we store
 * back-references instead of plain x-values in the distance vector.
 * 
 * @author Ronny.Standtke@gmx.net
 */
00019 public class PathNodeDiff {

    private final List<Integer> stringAScript = new LinkedList<Integer>();
    private final List<Integer> stringBScript = new LinkedList<Integer>();

    /**
     * Creates a new instance of PathCopyDiff
     * @param stringA the first string
     * @param stringB the second string
     * @param matchCase if we match the case
     */
00030     public PathNodeDiff(String stringA, String stringB, boolean matchCase) {

        if (!matchCase) {
            stringA = stringA.toLowerCase();
            stringB = stringB.toLowerCase();
        }

        int lengthA = stringA.length();
        int lengthB = stringB.length();
        int maxDistance = lengthA + lengthB;
        // stores the PathNodes of furthes reaching path endpoints
        PathNode[] distanceNodes = new PathNode[maxDistance * 2 + 1];

        // test (increasingly) every distance
        for (int distance = 0; distance <= maxDistance; distance++) {
            // System.out.println("distance = " + distance);
            // test every diagonal relevant for the current distance
            for (int k = -distance; k <= distance; k += 2) {
                // System.out.println(" k = " + k);
                // index of k in distanceNodes
                int ik = k + maxDistance;
                // the x-value of the endpoint in diagonal k
                int x;
                PathNode previousNode = null;
                // move right or down?
                if (k == -distance) {
                    previousNode = distanceNodes[ik + 1];
                    if (previousNode == null) {
                        x = 0;
                    } else {
                        x = previousNode.getX();
                    }
                // System.out.println("  we are at the very left diagonal");
                // System.out.println("  moved down (x = " + x + ")");
                } else if (k == distance) {
                    previousNode = distanceNodes[ik - 1];
                    if (previousNode == null) {
                        x = 0;
                    } else {
                        x = previousNode.getX() + 1;
                    }
                // System.out.println("  we are at the very right diagonal");
                // System.out.println("  moved right (x = " + x + ")");
                } else {
                    // we are somewhere in the middle and must look at the left
                    // and right diagonales
                    PathNode leftNode = distanceNodes[ik - 1];
                    PathNode rightNode = distanceNodes[ik + 1];
                    int leftX = leftNode.getX();
                    int rightX = rightNode.getX();
                    // System.out.println("  left: " + leftX + " right: " + rightX);
                    if (leftX < rightX) {
                        x = rightX;
                        previousNode = rightNode;
                    // System.out.println("  moved down (x = " + x + ")");
                    } else {
                        x = leftX + 1;
                        previousNode = leftNode;
                    // System.out.println("  moved right (x = " + x + ")");
                    }
                }

                // the y-value of the endpoint in diagonal k
                int y = x - k;
                // System.out.println("  y = " + y);

                // store node for current diagonal
                PathNode currentNode = null;
                if (previousNode == null) {
                    // this happens only at start
                    currentNode = new PathNode();
                } else {
                    // link the nodes
                    currentNode = new PathNode(previousNode, new Point(x, y));
                }

                // move along diagonals
                while ((x < lengthA) && (y < lengthB) && 
                        (stringA.charAt(x) == stringB.charAt(y))) {
                    x++;
                    y++;
                    currentNode = new PathNode(currentNode, new Point(x, y));
                }
                // System.out.println("  after moving along diagonals: x = " + x + ", y = " + y);

                distanceNodes[ik] = currentNode;

                if ((x >= lengthA) && (y >= lengthB)) {

                    // we are done!

                    // create edit scripts
                    List<Point> points = currentNode.getPointList();
                    for (int i = 0; i < points.size() - 1; i++) {
                        Point point = points.get(i);
                        Point nextPoint = points.get(i + 1);
                        if (point.getX() == nextPoint.getX()) {
                            int stringIndex = point.getY();
                            stringBScript.add(Integer.valueOf(stringIndex));
                        }
                        if (point.getY() == nextPoint.getY()) {
                            int stringIndex = point.getX();
                            stringAScript.add(Integer.valueOf(stringIndex));
                        }
                    }

                    return;
                }
            }
        }
    }

    /**
     * returns a List of Integers that mark the deletions in
     * <CODE>stringA</CODE>
     * @return a List of Integers that mark the deletions in
     * <CODE>stringA</CODE>
     */
00148     public List<Integer> getStringAScript() {
        return stringAScript;
    }

    /**
     * returns a List of Integers that mark the deletions in
     * <CODE>stringA</CODE>
     * @return a List of Integers that mark the deletions in
     * <CODE>stringB</CODE>
     */
00158     public List<Integer> getStringBScript() {
        return stringBScript;
    }

    private static class Point {

        private final int x;
        private final int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public int getX() {
            return x;
        }

        public int getY() {
            return y;
        }

        @Override
        public String toString() {
            return "(" + x + "," + y + ")";
        }
    }

    private static class PathNode {

        private final PathNode previousNode;
        private final Point point;

        public PathNode() {
            previousNode = null;
            point = new Point(0, 0);
        }

        public PathNode(PathNode previousNode, Point point) {
            this.previousNode = previousNode;
            this.point = point;
        }

        public int getX() {
            return point.getX();
        }

        public List<Point> getPointList() {
            return getPointList(null);
        }

        private List<Point> getPointList(List<Point> pointList) {
            if (previousNode == null) {
                pointList = new LinkedList<Point>();
            } else {
                pointList = previousNode.getPointList(pointList);
            }
            pointList.add(point);
            return pointList;
        }
    }
}

Generated by  Doxygen 1.6.0   Back to index