Package generic.algorithms

Class Lcs<T>

  • Type Parameters:
    T - the type of the objects being compared
    Direct Known Subclasses:
    CodeUnitLCS, ReducingLcs
    public abstract class Lcs<T>
extends java.lang.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

      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
      java.util.List<T> getLcs()
      Returns a list of the longest common subsequence.
      java.util.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 Detail

      • Lcs

        public Lcs()

    • Method Detail

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