org.conqat.lib.commons.algo

Class Diff<T>

java.lang.Object

org.conqat.lib.commons.algo.Diff<T>

Type Parameters:

T - The type of objects for which the diff is constructed.

public class Diff<T>
extends java.lang.Object

Implementation of the diff algorithm described in: E.W. Myers: "An O(ND) Difference Algorithm and Its Variations".

Let N be the sum of the concatenated input strings and D the size of the delta (i.e. the number of changes required to transform one string into the other). Then the time complexity is O(ND) and the space complexity is O(D^2).

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	Diff.Delta<T> Objects of this class describe the additions and deletions used to transform between two words.

Method Summary

Modifier and Type	Method and Description
static <T> Diff.Delta<T>	computeDelta(java.util.List<T> a, java.util.List<T> b) Applies the diff algorithm on the supplied lists and returns the delta between them.
static <T> Diff.Delta<T>	computeDelta(java.util.List<T> a, java.util.List<T> b, IEquator<? super T> equator) Applies the diff algorithm on the supplied lists and returns the delta between them.
static <T> Diff.Delta<T>	computeDelta(java.util.List<T> a, java.util.List<T> b, int maxDeltaSize) Applies the diff algorithm on the supplied lists and returns the delta between them.
static <T> Diff.Delta<T>	computeDelta(java.util.List<T> a, java.util.List<T> b, int maxDeltaSize, IEquator<? super T> equator) Applies the diff algorithm on the supplied lists and returns the delta between them.
static <T> Diff.Delta<T>	computeDelta(T[] a, T[] b) Applies the diff algorithm on the supplied arrays and returns the delta between them.
static <T> Diff.Delta<T>	computeDelta(T[] a, T[] b, IEquator<? super T> equator) Applies the diff algorithm on the supplied arrays and returns the delta between them.
static <T> Diff.Delta<T>	computeDelta(T[] a, T[] b, int maxDeltaSize) Applies the diff algorithm on the supplied arrays and returns the delta between them.

Methods inherited from class java.lang.Object

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

Method Detail

computeDelta

public static <T> Diff.Delta<T> computeDelta(T[] a,
                                             T[] b)

Applies the diff algorithm on the supplied arrays and returns the delta between them.

Parameters:

a - the first "word", i.e., array of objects to produce a delta for.

b - the second "word", i.e., array of objects to produce a delta for.

Returns:

a delta containing the differences between a and b.

computeDelta

public static <T> Diff.Delta<T> computeDelta(T[] a,
                                             T[] b,
                                             int maxDeltaSize)

Applies the diff algorithm on the supplied arrays and returns the delta between them.

Parameters:

a - the first "word", i.e., array of objects to produce a delta for.

b - the second "word", i.e., array of objects to produce a delta for.

maxDeltaSize - the maximal size of the delta produced. As the running size depends linearly on this size and the space required depends quadratically on it, limiting this value can reduce calculation overhead at the risk of receiving partial/incomplete deltas.

Returns:

a delta containing the differences between a and b.

computeDelta

public static <T> Diff.Delta<T> computeDelta(T[] a,
                                             T[] b,
                                             IEquator<? super T> equator)

Applies the diff algorithm on the supplied arrays and returns the delta between them.

Parameters:

a - the first "word", i.e., array of objects to produce a delta for.

b - the second "word", i.e., array of objects to produce a delta for.

equator - an object that can check whether two elements are equal.

Returns:

a delta containing the differences between a and b.

computeDelta

public static <T> Diff.Delta<T> computeDelta(java.util.List<T> a,
                                             java.util.List<T> b)

Applies the diff algorithm on the supplied lists and returns the delta between them.

Parameters:

a - the first "word", i.e., list of objects to produce a delta for.

b - the second "word", i.e., list of objects to produce a delta for.

Returns:

a delta containing the differences between a and b.

computeDelta

public static <T> Diff.Delta<T> computeDelta(java.util.List<T> a,
                                             java.util.List<T> b,
                                             IEquator<? super T> equator)

Applies the diff algorithm on the supplied lists and returns the delta between them.

Parameters:

a - the first "word", i.e., list of objects to produce a delta for.

b - the second "word", i.e., list of objects to produce a delta for.

equator - an object that can check whether two elements are equal.

Returns:

a delta containing the differences between a and b.

computeDelta

public static <T> Diff.Delta<T> computeDelta(java.util.List<T> a,
                                             java.util.List<T> b,
                                             int maxDeltaSize)

Applies the diff algorithm on the supplied lists and returns the delta between them.

Parameters:

a - the first "word", i.e., list of objects to produce a delta for.

b - the second "word", i.e., list of objects to produce a delta for.

maxDeltaSize - the maximal size of the delta produced. As the running size depends linearly on this size and the space required depends quadratically on it, limiting this value can reduce calculation overhead at the risk of receiving partial/incomplete deltas.

Returns:

a delta containing the differences between a and b.

computeDelta

public static <T> Diff.Delta<T> computeDelta(java.util.List<T> a,
                                             java.util.List<T> b,
                                             int maxDeltaSize,
                                             IEquator<? super T> equator)

Applies the diff algorithm on the supplied lists and returns the delta between them.

Parameters:

a - the first "word", i.e., list of objects to produce a delta for.

b - the second "word", i.e., list of objects to produce a delta for.

maxDeltaSize - the maximal size of the delta produced. As the running size depends linearly on this size and the space required depends quadratically on it, limiting this value can reduce calculation overhead at the risk of receiving partial/incomplete deltas.

equator - an object that can check whether two elements are equal.

Returns:

a delta containing the differences between a and b.