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