|
||||||||||
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 Springer-Verlag 1987
This class reuses portions of code originally written by Mikko Koivisto and Tuomo Saarni.
http://dblp.uni-trier.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(m-p)) 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 |