Class ReducingLcs<I,T>
- java.lang.Object
-
- generic.algorithms.Lcs<T>
-
- generic.algorithms.ReducingLcs<I,T>
-
- Type Parameters:
I
- The input sequence typeT
- the individual element type of the input sequence
- Direct Known Subclasses:
ReducingListBasedLcs
public abstract class ReducingLcs<I,T> extends Lcs<T>
Calculates the longest common subsequence (LCS) between two sequences of Matchable objects,x
andy
.This is an optimizing version of the
Lcs
that will pre-calculate all similar items from the beginning and end of the two given sequences. Doing this will reduce the size of the matrix created by the parent class, greatly so in the case that the two inputs are mostly the same in the beginning and end. (Imagine an edit of a source code file, where the typical change is somewhere in the middle of the file. In this example, the optimization performed here can greatly decrease the amount of work to be performed when calculating the LCS.)Note: the parent LCS algorithm is bound by
Lcs.getSizeLimit()
. However, this class allows clients to work around this restriction when the data has a similar beginning and ending, as the similar parts will not be counted against the size limit.
-
-
Constructor Summary
Constructors Constructor Description ReducingLcs(I ix, I iy)
Constructor
-
Method Summary
All Methods Instance Methods Abstract Methods Concrete Methods Modifier and Type Method Description protected java.util.List<T>
doGetLcs(TaskMonitor monitor)
Get the actual LCS based upon the already created matrixprotected abstract int
lengthOf(I i)
Return the length of the given sequenceprotected int
lengthOfX()
Returns the length of the x sequenceprotected int
lengthOfY()
Returns the length of the y sequenceprotected boolean
matches(T tx, T ty)
Returns true if the value of x and y matchprotected abstract I
reduce(I i, int start, int end)
Create a subsequence from the given input sequence.protected abstract T
valueOf(I i, int offset)
Return the value at the given 0-based offsetprotected T
valueOfX(int index)
Gets the value of the x sequence at the given index, where index is 1-basedprotected T
valueOfY(int index)
Gets the value of the y sequence at the given index, where index is 1-based-
Methods inherited from class generic.algorithms.Lcs
getLcs, getLcs, getSizeLimit, setSizeLimit
-
-
-
-
Method Detail
-
reduce
protected abstract I reduce(I i, int start, int end)
Create a subsequence from the given input sequence.- Parameters:
i
- the input sequence; 0-based (x or y)start
- the start index; 0-based (inclusive)end
- the end index (exclusive)- Returns:
- the subsequence
-
lengthOf
protected abstract int lengthOf(I i)
Return the length of the given sequence- Parameters:
i
- the input sequence (x or y)- Returns:
- the length
-
valueOf
protected abstract T valueOf(I i, int offset)
Return the value at the given 0-based offset- Parameters:
i
- the input sequence (x or y)offset
- the offset- Returns:
- the value
-
doGetLcs
protected java.util.List<T> doGetLcs(TaskMonitor monitor) throws CancelledException
Description copied from class:Lcs
Get the actual LCS based upon the already created matrix- Overrides:
doGetLcs
in classLcs<T>
- Parameters:
monitor
- the task monitor- Returns:
- the LCS list
- Throws:
CancelledException
- if the monitor is cancelled
-
lengthOfX
protected int lengthOfX()
Description copied from class:Lcs
Returns the length of the x sequence
-
lengthOfY
protected int lengthOfY()
Description copied from class:Lcs
Returns the length of the y sequence
-
valueOfX
protected T valueOfX(int index)
Description copied from class:Lcs
Gets the value of the x sequence at the given index, where index is 1-based
-
valueOfY
protected T valueOfY(int index)
Description copied from class:Lcs
Gets the value of the y sequence at the given index, where index is 1-based
-
-