Package org.hippoecm.frontend.plugins.standards.diff

Class LCS

java.lang.Object

org.hippoecm.frontend.plugins.standards.diff.LCS

public class LCS
extends Object

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	LCS.Change<T>	Elemental change in an array of values.
static class	LCS.ChangeType

Method Summary

Modifier and Type	Method	Description
static <T> List<LCS.Change<T>>	getChangeSet(T[] a, T[] b)	Constructs the minimal changeset to turn the first array into the second one.
static <T> List<T>	getLongestCommonSubsequence(T[] a, T[] b)	Find the longest common subsequence between arrays a and b.
static <T extends Serializable> List<LCS.Change<T>>	getSerializableChangeSet(T[] a, T[] b)	Constructs the minimal changeset to turn the first array into the second one.

Methods inherited from class java.lang.Object

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

Method Detail

getSerializableChangeSet

public static <T extends Serializable> List<LCS.Change<T>> getSerializableChangeSet(T[] a,
                                                                                    T[] b)

Constructs the minimal changeset to turn the first array into the second one. The returned changeset is guaranteed to be serializable.

Type Parameters:

T - the type of the array elements

Parameters:

a - the first array

b - the second array

Returns:

the minimal changeset

getChangeSet

public static <T> List<LCS.Change<T>> getChangeSet(T[] a,
                                                   T[] b)

Constructs the minimal changeset to turn the first array into the second one. The returned changeset is only serializable when T is serializable.

Type Parameters:

T - the type of the array elements

Parameters:

a - the first array

b - the second array

Returns:

the minimal changeset

getLongestCommonSubsequence

public static <T> List<T> getLongestCommonSubsequence(T[] a,
                                                      T[] b)

Find the longest common subsequence between arrays a and b. The algorithm that's implemented creates an index of the items in the smallest array and iterates over the largest one. During this iteration, for each sub-array consisting of the elements 0..j of the small array (j < |smallest|), the sequence with most common elements is maintained.

The execution time and memory usage are linear for typical inputs, but will be quadratic in the worst case.