Package generic.algorithms

# Class ReducingLcs<I,T>

java.lang.Object
generic.algorithms.Lcs<T>
generic.algorithms.ReducingLcs<I,T>

Type Parameters:
  `I` - The input sequence type
  `T` - 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` and `y`.

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

  Modifier and Type
  Method
  Description
  `protected List<T>`
  `doGetLcs(TaskMonitor monitor)`
  Get the actual LCS based upon the already created matrix
  `protected abstract int`
  `lengthOf(I i)`
  Return the length of the given sequence
  `protected int`
  `lengthOfX()`
  Returns the length of the x sequence
  `protected int`
  `lengthOfY()`
  Returns the length of the y sequence
  `protected boolean`
  `matches(T tx, T ty)`
  Returns true if the value of x and y match
  `protected 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 offset
  `protected T`
  `valueOfX(int index)`
  Gets the value of the x sequence at the given index, where index is 1-based
  `protected 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`

  ### Methods inherited from class java.lang.Object

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

- ## Constructor Details

  - ### ReducingLcs

    public ReducingLcs(I ix, I iy)
    Constructor
    Parameters:
      `ix` - the input sequence `x`
      `iy` - the input sequence `y`

- ## Method Details

  - ### 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 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 class `Lcs<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
    Specified by:
      `lengthOfX` in class `Lcs<T>`
    Returns:
      the length of the x sequence

  - ### lengthOfY

    protected int lengthOfY()
    Description copied from class: `Lcs`
    Returns the length of the y sequence
    Specified by:
      `lengthOfY` in class `Lcs<T>`
    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
    Specified by:
      `valueOfX` in class `Lcs<T>`
    Parameters:
      `index` - the 1-based position of interest in the x sequence
    Returns:
      the value in the x sequence at `index`

  - ### 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
    Specified by:
      `valueOfY` in class `Lcs<T>`
    Parameters:
      `index` - the 1-based position of interest in the Y sequence
    Returns:
      the value in the y sequence at `index`

  - ### matches

    protected boolean matches(T tx, T ty)
    Description copied from class: `Lcs`
    Returns true if the value of x and y match
    Specified by:
      `matches` in class `Lcs<T>`
    Parameters:
      `tx` - the x-sequence element of interest
      `ty` - the y-sequence element of interest
    Returns:
      true if `x` matches `y`; false otherwise