

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object com.topologi.diffx.algorithm.DiffXAlgorithmBase com.topologi.diffx.algorithm.DiffXKumarRangan
public final class DiffXKumarRangan
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:
SmartXMLFormatter
helps in solving the
problem as it maintains a stack of the elements that are being written and actually
ignores the name of the closing element, so all the elements are closed properly.
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 SpringerVerlag 1987
This class reuses portions of code originally written by Mikko Koivisto and Tuomo Saarni.
http://dblp.unitrier.de/rec/bibtex/journals/acta/KumarR87
http://users.utu.fi/~tuiisa/Java/
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)
seq0
 The first sequence to compare.seq1
 The second sequence to compare.Method Detail 

public int length()
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(mp)) and the space complexity is O(n+m).
public void process(DiffXFormatter formatter) throws IOException
formatter
 The formatter that will handle the output.
IOException
 If thrown by the formatter.


PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 