org.eclipse.compare.rangedifferencer

Class RangeComparatorLCS [ source ]

java.lang.Object

org.eclipse.compare.internal.core.LCS

org.eclipse.compare.rangedifferencer.RangeComparatorLCS

 class RangeComparatorLCS
extends LCS

Constructor Summary

Constructors

Constructor and Description
RangeComparatorLCS(IRangeComparator comparator1, IRangeComparator comparator2)

Method Summary

Methods

Modifier and Type	Method and Description
static RangeDifference[]	findDifferences(AbstractRangeDifferenceFactory factory, IProgressMonitor pm, IRangeComparator left, IRangeComparator right)
RangeDifference[]	getDifferences(SubMonitor subMonitor, AbstractRangeDifferenceFactory factory)
protected int	getLength1()
protected int	getLength2()
protected void	initializeLcs(int lcsLength)
protected boolean	isRangeEqual(int i1, int i2)
void	longestCommonSubsequence(SubMonitor subMonitor) Myers' algorithm for longest common subsequence.
protected void	setLcs(int sl1, int sl2)

Methods inherited from class org.eclipse.compare.internal.core.LCS

getLength

Methods inherited from class java.lang.Object

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

Constructor Detail

RangeComparatorLCS

public RangeComparatorLCS(IRangeComparator comparator1,
                  IRangeComparator comparator2)

Method Detail

findDifferences

public static RangeDifference[] findDifferences(AbstractRangeDifferenceFactory factory,
                                IProgressMonitor pm,
                                IRangeComparator left,
                                IRangeComparator right)

getLength1

protected int getLength1()

Specified by:

getLength1 in class LCS

getLength2

protected int getLength2()

Specified by:

getLength2 in class LCS

initializeLcs

protected void initializeLcs(int lcsLength)

Specified by:

initializeLcs in class LCS

isRangeEqual

protected boolean isRangeEqual(int i1,
                   int i2)

Specified by:

isRangeEqual in class LCS

setLcs

protected void setLcs(int sl1,
          int sl2)

Specified by:

setLcs in class LCS

getDifferences

public RangeDifference[] getDifferences(SubMonitor subMonitor,
                               AbstractRangeDifferenceFactory factory)

longestCommonSubsequence

public void longestCommonSubsequence(SubMonitor subMonitor)

Description copied from class: LCS

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

Overrides:

longestCommonSubsequence in class LCS