Package generic.algorithms
Class Lcs<T>
- java.lang.Object
-
- generic.algorithms.Lcs<T>
-
- Type Parameters:
T
- the type of the objects being compared
- Direct Known Subclasses:
CodeUnitLCS
,ReducingLcs
public abstract class Lcs<T> extends java.lang.Object
Abstract class for finding the Longest Common Subsequence (LCS) between two sequences of Matchable objects,x
andy
.The performance of this algorithm is O(n^2). Thus, large inputs can cause much processor and memory usage. This class has an upper limit (see
getSizeLimit()
) to prevent accidental system failure.
-
-
Constructor Summary
Constructors Constructor Description Lcs()
-
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 matrixjava.util.List<T>
getLcs()
Returns a list of the longest common subsequence.java.util.List<T>
getLcs(TaskMonitor monitor)
Returns a list of the longest common subsequence.int
getSizeLimit()
Returns the current size limit, past which no calculations will be performedprotected abstract int
lengthOfX()
Returns the length of the x sequenceprotected abstract int
lengthOfY()
Returns the length of the y sequenceprotected abstract boolean
matches(T x, T y)
Returns true if the value of x and y matchvoid
setSizeLimit(int newLimit)
Changes the size limit of this LCS, past which no calculations will be performedprotected abstract T
valueOfX(int index)
Gets the value of the x sequence at the given index, where index is 1-basedprotected abstract T
valueOfY(int index)
Gets the value of the y sequence at the given index, where index is 1-based
-
-
-
Method Detail
-
lengthOfX
protected abstract int lengthOfX()
Returns the length of the x sequence- Returns:
- the length of the x sequence
-
lengthOfY
protected abstract int lengthOfY()
Returns the length of the y sequence- Returns:
- the length of the y sequence
-
valueOfX
protected abstract T valueOfX(int index)
Gets the value of the x sequence at the given index, where index is 1-based- Parameters:
index
- the 1-based position of interest in the x sequence- Returns:
- the value in the x sequence at
index
-
valueOfY
protected abstract T valueOfY(int index)
Gets the value of the y sequence at the given index, where index is 1-based- Parameters:
index
- the 1-based position of interest in the Y sequence- Returns:
- the value in the y sequence at
index
-
matches
protected abstract boolean matches(T x, T y)
Returns true if the value of x and y match- Parameters:
x
- the x-sequence element of interesty
- the y-sequence element of interest- Returns:
- true if
x
matchesy
; false otherwise
-
setSizeLimit
public void setSizeLimit(int newLimit)
Changes the size limit of this LCS, past which no calculations will be performed- Parameters:
newLimit
- the new limit
-
getSizeLimit
public int getSizeLimit()
Returns the current size limit, past which no calculations will be performed- Returns:
- the size limit
- See Also:
setSizeLimit(int)
-
getLcs
public java.util.List<T> getLcs()
Returns a list of the longest common subsequence. This result will be empty if thegetSizeLimit()
has been reached.- Returns:
- the list
-
getLcs
public java.util.List<T> getLcs(TaskMonitor monitor) throws CancelledException
Returns a list of the longest common subsequence. This result will be empty if thegetSizeLimit()
has been reached.- Parameters:
monitor
- the task monitor- Returns:
- the LCS list
- Throws:
CancelledException
- if the monitor is cancelled
-
doGetLcs
protected java.util.List<T> doGetLcs(TaskMonitor monitor) throws CancelledException
Get the actual LCS based upon the already created matrix- Parameters:
monitor
- the task monitor- Returns:
- the LCS list
- Throws:
CancelledException
- if the monitor is cancelled
-
-