Package com.topologi.diffx.algorithm

Class DiffXFitopsy

java.lang.Object
com.topologi.diffx.algorithm.DiffXAlgorithmBase
com.topologi.diffx.algorithm.DiffXFitopsy
All Implemented Interfaces:
DiffXAlgorithm
public final class DiffXFitopsy extends DiffXAlgorithmBase
Performs the diff comparison using the LCS algorithm.

Implementation note: this algorithm effectively detects the correct changes in the sequences, but will not necessarily return events that can be serialised as well-formed XML as they stand.

Known problem in this implementation: elements that contain themselves tend to generate events that are harder to serialise as XML.

This class is said 'fit' because it will adapt the matrix to the sequences that it is being given in order to improve performance.

Note: The name of this class comes from a contracted version of the features of this algorithm, as explained below:

  • Weighted, each token is has a given weight;
  • Symmetrical, when possible, the algorithm will try to choose a path that is symmetrical in regards to the arrangement of the tokens;
  • Matrix, this class uses a matrix for its internal representation;

This class is not synchronised.

Version:
8 April 2005

  • Field Details

    • DEBUG

      private static final boolean DEBUG
      Set to true to show debug info.
      See Also:

    • matrix

      private transient Matrix matrix
      Matrix storing the paths.

    • estate

      private transient ElementState estate
      The state of the elements.

  • Constructor Details

    • DiffXFitopsy

      public DiffXFitopsy(EventSequence seq0, EventSequence seq1)
      Creates a new DiffXAlgorithmBase.
      Parameters:
      seq0 - The first sequence to compare.
      seq1 - The second sequence to compare.

  • Method Details

    • length

      public int length()
      Returns the length of the longest common sequence.
      Returns:
      the length of the longest common sequence.

    • process

      public void process(DiffXFormatter formatter) throws IOException
      Writes the diff sequence using the specified formatter.
      Parameters:
      formatter - The formatter that will handle the output.
      Throws:
      IOException - If thrown by the formatter.

    • processEmpty

      private void processEmpty(DiffXFormatter formatter) throws IOException
      Writes the diff sequence using the specified formatter when one of the sequences is empty.

      The result becomes either only insertions (when the second sequence is empty) or deletions (when the first sequence is empty).

      Parameters:
      formatter - The formatter that will handle the output.
      Throws:
      IOException - If thrown by the formatter.

    • setupMatrix

      private static Matrix setupMatrix(EventSequence s1, EventSequence s2)
      Determines the most appropriate matrix to use.

      Calculates the maximum length of the shortest weighted path if both sequences are totally different, which corresponds to the sum of all the events.

      Parameters:
      s1 - The first sequence.
      s2 - The second sequence.
      Returns:
      The most appropriate matrix.

    • printLost

      private void printLost(int i, int j)
      Print information when the algorithm gets lost in the matrix, ie when it does not know which direction to follow.
      Parameters:
      i - The X position.
      j - The Y position.