Package org.eclipse.compare.internal

Class LCS

java.lang.Object
org.eclipse.compare.internal.LCS
public abstract class LCS extends Object

  • Constructor Details

    • LCS

      public LCS()

  • Method Details

    • longestCommonSubsequence

      public void longestCommonSubsequence(org.eclipse.core.runtime.SubMonitor subMonitor, LCSSettings settings)
      Myers' algorithm for longest common subsequence. O((M + N)D) worst case time, O(M + N + D^2) expected time, O(M + N) space (http://citeseer.ist.psu.edu/myers86ond.html) Note: Beyond implementing the algorithm as described in the paper I have added diagonal range compression which helps when finding the LCS of a very long and a very short sequence, also bound the running time to (N + M)^1.5 when both sequences are very long. After this method is called, the longest common subsequence is available by calling getResult() where result[0] is composed of entries from l1 and result[1] is composed of entries from l2
      Parameters:
      subMonitor -

    • getLength2

      protected abstract int getLength2()

    • getLength1

      protected abstract int getLength1()

    • isRangeEqual

      protected abstract boolean isRangeEqual(int i1, int i2)

    • setLcs

      protected abstract void setLcs(int sl1, int sl2)

    • initializeLcs

      protected abstract void initializeLcs(int lcsLength)

    • getLength

      public int getLength()