TUM CCSM Commons

edu.tum.cs.commons.algo
Class Diff<T>

java.lang.Object
  extended by edu.tum.cs.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).

Version:
$Rev: 26283 $
Author:
hummelb, $Author: juergens $
Rating:
GREEN Hash: 2B0182DC254FAFBACB0727A1A353E51C

Nested Class Summary
static class Diff.Delta<T>
          Objects of this class describe the additions and deletions used to transform between two words.
 
Method Summary
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(T[] a, T[] b)
          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(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.

TUM CCSM Commons

TUM CCSM Commons - 2.7