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 Object
Abstract class for finding the Longest Common Subsequence (LCS) between two sequences of Matchable objects, x and y.

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

    Modifier and Type
    Method
    Description
    protected List<T>
    doGetLcs(TaskMonitor monitor)
    Get the actual LCS based upon the already created matrix
    List<T>
    getLcs()
    Returns a list of the longest common subsequence.
    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 performed
    protected abstract int
    lengthOfX()
    Returns the length of the x sequence
    protected abstract int
    lengthOfY()
    Returns the length of the y sequence
    protected abstract boolean
    matches(T x, T y)
    Returns true if the value of x and y match
    void
    setSizeLimit(int newLimit)
    Changes the size limit of this LCS, past which no calculations will be performed
    protected abstract T
    valueOfX(int index)
    Gets the value of the x sequence at the given index, where index is 1-based
    protected abstract T
    valueOfY(int index)
    Gets the value of the y sequence at the given index, where index is 1-based

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • Lcs

      public Lcs()

  • Method Details

    • 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 interest
      y - the y-sequence element of interest
      Returns:
      true if x matches y; 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:

    • getLcs

      public List<T> getLcs()
      Returns a list of the longest common subsequence. This result will be empty if the getSizeLimit() has been reached.
      Returns:
      the list

    • getLcs

      public List<T> getLcs(TaskMonitor monitor) throws CancelledException
      Returns a list of the longest common subsequence. This result will be empty if the getSizeLimit() has been reached.
      Parameters:
      monitor - the task monitor
      Returns:
      the LCS list
      Throws:
      CancelledException - if the monitor is cancelled

    • doGetLcs

      protected 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