Package generic.algorithms

Class 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

      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 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 java.lang.Object

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

    • Constructor Detail

      • ReducingLcs

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

    • Method Detail

      • 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 java.util.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