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