org.eclipse.compare.internal

Class LCS

java.lang.Object

org.eclipse.compare.internal.LCS

public abstract class LCS
extends Object

Constructor Summary

Constructors

Constructor and Description
LCS()

Method Summary

Modifier and Type	Method and Description
int	getLength()
protected abstract int	getLength1()
protected abstract int	getLength2()
protected abstract void	initializeLcs(int lcsLength)
protected abstract boolean	isRangeEqual(int i1, int i2)
void	longestCommonSubsequence(org.eclipse.core.runtime.SubMonitor subMonitor, LCSSettings settings) Myers' algorithm for longest common subsequence.
protected abstract void	setLcs(int sl1, int sl2)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

LCS

public LCS()

Method Detail

longestCommonSubsequence

public void longestCommonSubsequence(org.eclipse.core.runtime.SubMonitor subMonitor,
                                     LCSSettings settings)

Myers' algorithm for longest common subsequence. O((M + N)D) worst case time, O(M + N + D^2) expected time, O(M + N) space (http://citeseer.ist.psu.edu/myers86ond.html)

Note: Beyond implementing the algorithm as described in the paper I have added diagonal range compression which helps when finding the LCS of a very long and a very short sequence, also bound the running time to (N + M)^1.5 when both sequences are very long.

After this method is called, the longest common subsequence is available by calling getResult() where result[0] is composed of entries from l1 and result[1] is composed of entries from l2

Parameters:

subMonitor -

getLength2

protected abstract int getLength2()

getLength1

protected abstract int getLength1()

isRangeEqual

protected abstract boolean isRangeEqual(int i1,
                                        int i2)

setLcs

protected abstract void setLcs(int sl1,
                               int sl2)

initializeLcs

protected abstract void initializeLcs(int lcsLength)

getLength

public int getLength()