Class DiffXKumarRangan

  extended by com.topologi.diffx.algorithm.DiffXAlgorithmBase
      extended by com.topologi.diffx.algorithm.DiffXKumarRangan
All Implemented Interfaces:

public final class DiffXKumarRangan
extends DiffXAlgorithmBase

Performs the diff comparison using an optimized version of the linear space algorithm of S.Kiran Kumar and C.Pandu Rangan.

Implementation note: this algorithm effectively detects the correct changes in the sequences, but suffers from two main problems:

For S. Kiran Kumar and C. Pandu Rangan. A linear space algorithm for the LCS problem, Acta Informatica. Volume 24 , Issue 3 (June 1987); Copyright Springer-Verlag 1987

This class reuses portions of code originally written by Mikko Koivisto and Tuomo Saarni.

9 March 2005
Christophe Lauret

Constructor Summary
DiffXKumarRangan(EventSequence seq0, EventSequence seq1)
          Creates a new DiffXAlgorithmBase.
Method Summary
 int length()
          Calculates the length of LCS and returns it.
 void process(DiffXFormatter formatter)
          Writes the diff sequence using the specified formatter.
Methods inherited from class com.topologi.diffx.algorithm.DiffXAlgorithmBase
getFirstSequence, getSecondSequence
Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail


public DiffXKumarRangan(EventSequence seq0,
                        EventSequence seq1)
Creates a new DiffXAlgorithmBase.

seq0 - The first sequence to compare.
seq1 - The second sequence to compare.
Method Detail


public int length()
Calculates the length of LCS and returns it.

If the length is calculated already it'll not be calculated repeatedly.

This algorithm starts from the length of the first sequence as the maximum possible LCS and reduces the length for every difference with the second sequence.

The time complexity is O(n(m-p)) and the space complexity is O(n+m).

The length of LCS


public void process(DiffXFormatter formatter)
             throws IOException
Writes the diff sequence using the specified formatter.

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