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:
      - `setSizeLimit(int)`

  - ### 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